International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Cryptanalysis of Candidate Obfuscators for Affine Determinant Programs

Li Yao , Shanghai Jiao Tong University
Yilei Chen , Tsinghua University
Yu Yu , Shanghai Jiao Tong University
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2022
Abstract: At ITCS 2020, Bartusek et al. proposed a candidate indistinguishability obfuscator (iO) for affine determinant programs (ADPs). The candidate is special since it is the only unbroken candidate iO to date that does not rely on the hardness of traditional cryptographic assumptions like discrete-log or learning with errors. Instead, it directly applies specific randomization techniques to the underlying ADP. It is relatively efficient compared to the rest of the iO candidates. However, the obfuscation scheme requires further cryptanalysis since it was not known to be based on any well-formed mathematical assumptions. In this paper, we show cryptanalytic attacks on the iO candidate provided by Bartusek et al. Our attack exploits the weakness of one of the randomization steps in the candidate. The attack applies to a fairly general class of programs. At the end of the paper we discuss plausible countermeasures to defend against our attacks.
Video from EUROCRYPT 2022
  title={Cryptanalysis of Candidate Obfuscators for Affine Determinant Programs},
  author={Li Yao and Yilei Chen and Yu Yu},