Cryptology ePrint Archive: Report 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.

Category / Keywords: CLT13 multilinear map, FRS obfuscation, indistinguishable obfuscation, input partitionability, zeroizing attack.

Date: received 27 Oct 2019, last revised 8 Dec 2019

Contact author: changmin lee at ens-lyon fr, tory154 at snu ac kr

Available format(s): PDF | BibTeX Citation

Version: 20191208:125532 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]