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.