Paper 2024/392

Heuristic Ideal Obfuscation Scheme based on LWE Problem, its Variants and Quantum Oracle

Abstract

This paper introduces a heuristic ideal obfuscation scheme grounded in the learning problem, which differs from that proposed by Jain, Lin, and Luo [JLLW23]. The approach in this paper follows a methodology akin to that of Brakerski, Dottling, Garg, and Malavolta [BDGM22,BDGM20] for building iO. We construct a new ideal obfuscation by leveraging a variant of LWR to build LHE and employing Evasive LWR to construct multilinear maps. In contrast to the methodology of Jain et al., this paper provides a more detailed approach. Initially, we reprove the hardness of LWR using the prime number theorem and the fixed-point theorem, showing that the statistical distance between $\lfloor As\rfloor_p$ and $\lfloor u\rfloor_p$ does not exceed $\exp\left(-\frac{n\log_2n\ln p}{\sqrt{5}}\right)$ when the security parameter $q>2^{n}p$. Additionally, we provide definitions for Evasive LWR and composite homomorphic pseudorandom function, and based on these, we construct multilinear maps, thereby establishing the ideal obfuscation scheme proposed in this paper.