Paper 2019/1254

Cryptanalysis of FRS Obfuscation based on the CLT13 Multilinear Map

Jiseung Kim and Changmin Lee


We present a classical polynomial time attack against the FRS branching program obfuscator of Fernando-Rasmussen-Sahai (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 CLT13 multilinear map. To achieve the goal, we apply the Coron and Notarnicola (Asiacrypt'19) algorithm. However, because of parameter issues, the algorithm cannot be used directly. In order to detour the issue, we convert a FRS obfuscator into a new program containing a small message space. Through the conversion, we obtain two zerotest parameters and encodings of zero except for two nonzero slots. Then, they are used to mitigate parameter constraints of the message space recovering algorithm. Then, we propose a cryptanalysis of the FRS obfuscation based on the recovered message space. We show that there exist two functionally equivalent programs such that their obfuscated programs are computationally distinguishable. Thus, the FRS scheme does not satisfy the desired security without any additional constraints.

Available format(s)
Publication info
Preprint. MINOR revision.
CLT13 multilinear mapFRS obfuscationindistinguishable obfuscationinput partitionabilityzeroizing attack.
Contact author(s)
changmin lee @ ens-lyon fr
tory154 @ snu ac kr
2019-12-08: revised
2019-10-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jiseung Kim and Changmin Lee},
      title = {Cryptanalysis of FRS Obfuscation based on the CLT13 Multilinear Map},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1254},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.