Paper 2019/1254

Cryptanalysis of FRS Obfuscation based on the CLT13 Multilinear Map

Jiseung Kim and Changmin Lee

Abstract

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.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
CLT13 multilinear mapFRS obfuscationindistinguishable obfuscationinput partitionabilityzeroizing attack.
Contact author(s)
changmin lee @ ens-lyon fr
tory154 @ snu ac kr
History
2019-12-08: revised
2019-10-28: received
See all versions
Short URL
https://ia.cr/2019/1254
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1254,
      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{https://eprint.iacr.org/2019/1254}},
      url = {https://eprint.iacr.org/2019/1254}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.