论文标题
与基础良好的假设相混淆
Indistinguishability Obfuscation from Well-Founded Assumptions
论文作者
论文摘要
在这项工作中，我们展示了如何从四个有充分基础的假设的次指数硬度中构建不可区分性混淆。我们证明： 令$τ\ in（0，\ infty），δ\ in（0,1），ε\ in（0,1）$为任意常数。假设以下假设的子指数安全性，其中$λ$是一个安全参数，而参数$ \ ell，k，n $以下是$λ$的足够大的多项式。 -SXDH对素数的非对称双线性组的假设$ p = o（2^λ）$， - $ \ mathbb {z} _ {p} $的LWE假设带有子指数模量与噪声比率$ 2^{k^ε} $，其中$ k $是lwe Secret的维度， - $ \ mathbb {z} _p $带有多个LPN样本的LPN假设，错误率$ 1/\ ell^δ$，其中$ \ ell $是LPN SECRED的维度， - $ \ mathsf {nc}^0 $中的布尔prg的存在与stretch $ n^{1+τ} $， 然后，（非指数安全）所有多项式大小的电路都不可区分性混淆。
In this work, we show how to construct indistinguishability obfuscation from subexponential hardness of four well-founded assumptions. We prove: Let $τ\in (0,\infty), δ\in (0,1), ε\in (0,1)$ be arbitrary constants. Assume sub-exponential security of the following assumptions, where $λ$ is a security parameter, and the parameters $\ell,k,n$ below are large enough polynomials in $λ$: - The SXDH assumption on asymmetric bilinear groups of a prime order $p = O(2^λ)$, - The LWE assumption over $\mathbb{Z}_{p}$ with subexponential modulus-to-noise ratio $2^{k^ε}$, where $k$ is the dimension of the LWE secret, - The LPN assumption over $\mathbb{Z}_p$ with polynomially many LPN samples and error rate $1/\ell^δ$, where $\ell$ is the dimension of the LPN secret, - The existence of a Boolean PRG in $\mathsf{NC}^0$ with stretch $n^{1+τ}$, Then, (subexponentially secure) indistinguishability obfuscation for all polynomial-size circuits exists.
