Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden.
powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden.
powered by
Abstract
In this work, we study what minimal sets of assumptions suffice for constructing indistinguishability obfuscation (\(i\mathcal {O}\)). We prove:
Theorem(Informal): Assume sub-exponential security of the following assumptions:
– the Learning Parity with Noise (\(\mathsf {LPN}\)) assumption over general prime fields\(\mathbb {F}_p\)with polynomially many\(\mathsf {LPN}\)samples and error rate\(1/k^\delta \), wherekis the dimension of the\(\mathsf {LPN}\)secret, and\(\delta >0\)is any constant;
– the existence of a Boolean Pseudo-Random Generator (\(\mathsf {PRG}\)) in\(\mathsf {NC}^0\)with stretch\(n^{1+\tau }\), wherenis the length of the\(\mathsf {PRG}\)seed, and\(\tau >0\)is any constant;
– the Decision Linear (\(\mathsf {DLIN}\)) assumption on symmetric bilinear groups of prime order.
Then, (subexponentially secure) indistinguishability obfuscation for all polynomial-size circuits exists. Further, assuming only polynomial security of the aforementioned assumptions, there exists collusion resistant public-key functional encryption for all polynomial-size circuits.
This removes the reliance on the Learning With Errors (LWE) assumption from the recent work of [Jain, Lin, Sahai STOC’21]. As a consequence, we obtain the first fully homomorphic encryption scheme that does not rely on any lattice-based hardness assumption.
Our techniques feature a new notion of randomized encoding called Preprocessing Randomized Encoding (PRE), that essentially can be computed in the exponent of pairing groups. When combined with other new techniques, PRE gives a much more streamlined construction of \(i\mathcal {O}\) while still maintaining reliance only on well-studied assumptions.
Anzeige
Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.
Besides [20], there are other works that contain FE security amplification techniques [4, 5, 26]. However, it has been recently acknowledged that there is a common issue in these techniques due to an incorrect application of the leakage simulation lemma. The work of [20] circumvents the use leakage simulation lemma, but achieves only weaker security amplification, which nevertheless is still sufficient for constructing \(i\mathcal {O}\).