Cryptanalysis of FRS obfuscation based on the CLT13 multilinear map
Abstract The authors present a classical polynomial‐time attack against the branching program obfuscator of Fernando–Rasmussen–Sahai (for short FRS, Asiacrypt’17) (with one zerotest parameter), which is robust against all known classical cryptanalyses on obfuscators when instantiated with the CLT13...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2022-05-01
|
| Series: | IET Information Security |
| Online Access: | https://doi.org/10.1049/ise2.12055 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832546686723948544 |
|---|---|
| author | Jiseung Kim Changmin Lee |
| author_facet | Jiseung Kim Changmin Lee |
| author_sort | Jiseung Kim |
| collection | DOAJ |
| description | Abstract The authors present a classical polynomial‐time attack against the branching program obfuscator of Fernando–Rasmussen–Sahai (for short FRS, Asiacrypt’17) (with one zerotest parameter), which is robust against all known classical cryptanalyses on obfuscators when instantiated with the CLT13 multilinear map. The first step is to recover a plaintext modulus of the CLT13 multilinear map. To achieve the goal, the Coron and Notarnicola (Asiacrypt’19) algorithm is applied. However, because of parameter issues, the algorithm cannot be used directly. In order to detour the issue, the authors convert an FRS obfuscator into a new programme containing a small message space. Through the conversion, the authors obtain two zerotest parameters and encodings of zero except for two non‐zero slots. Then, they are used to mitigate parameter constraints of the message space recovering algorithm. Then, a cryptanalysis of the FRS obfuscation based on the recovered message space is proposed. The authors show that there exist two functionally equivalent programmes such that their obfuscated programmes are computationally distinguishable. Thus, the FRS scheme does not satisfy the desired security without any additional constraints. |
| format | Article |
| id | doaj-art-ac60ab0199b04d5984eefa1c1b0f406d |
| institution | Kabale University |
| issn | 1751-8709 1751-8717 |
| language | English |
| publishDate | 2022-05-01 |
| publisher | Wiley |
| record_format | Article |
| series | IET Information Security |
| spelling | doaj-art-ac60ab0199b04d5984eefa1c1b0f406d2025-02-03T06:47:34ZengWileyIET Information Security1751-87091751-87172022-05-0116320821910.1049/ise2.12055Cryptanalysis of FRS obfuscation based on the CLT13 multilinear mapJiseung Kim0Changmin Lee1School of Computational Sciences Korea Institute for Advanced Study Seoul South KoreaSchool of Computational Sciences Korea Institute for Advanced Study Seoul South KoreaAbstract The authors present a classical polynomial‐time attack against the branching program obfuscator of Fernando–Rasmussen–Sahai (for short FRS, Asiacrypt’17) (with one zerotest parameter), which is robust against all known classical cryptanalyses on obfuscators when instantiated with the CLT13 multilinear map. The first step is to recover a plaintext modulus of the CLT13 multilinear map. To achieve the goal, the Coron and Notarnicola (Asiacrypt’19) algorithm is applied. However, because of parameter issues, the algorithm cannot be used directly. In order to detour the issue, the authors convert an FRS obfuscator into a new programme containing a small message space. Through the conversion, the authors obtain two zerotest parameters and encodings of zero except for two non‐zero slots. Then, they are used to mitigate parameter constraints of the message space recovering algorithm. Then, a cryptanalysis of the FRS obfuscation based on the recovered message space is proposed. The authors show that there exist two functionally equivalent programmes such that their obfuscated programmes are computationally distinguishable. Thus, the FRS scheme does not satisfy the desired security without any additional constraints.https://doi.org/10.1049/ise2.12055 |
| spellingShingle | Jiseung Kim Changmin Lee Cryptanalysis of FRS obfuscation based on the CLT13 multilinear map IET Information Security |
| title | Cryptanalysis of FRS obfuscation based on the CLT13 multilinear map |
| title_full | Cryptanalysis of FRS obfuscation based on the CLT13 multilinear map |
| title_fullStr | Cryptanalysis of FRS obfuscation based on the CLT13 multilinear map |
| title_full_unstemmed | Cryptanalysis of FRS obfuscation based on the CLT13 multilinear map |
| title_short | Cryptanalysis of FRS obfuscation based on the CLT13 multilinear map |
| title_sort | cryptanalysis of frs obfuscation based on the clt13 multilinear map |
| url | https://doi.org/10.1049/ise2.12055 |
| work_keys_str_mv | AT jiseungkim cryptanalysisoffrsobfuscationbasedontheclt13multilinearmap AT changminlee cryptanalysisoffrsobfuscationbasedontheclt13multilinearmap |