ADP - HackMD

Summary of [Affine Determinant Programs: A Framework for Obfuscation and Witness Encryption ](https://eprint.iacr.org/2020/889) ## TLDR This paper proposes practical witness encryption from **ADP** and uses it to construct a public-key encryption scheme with very short secret and public keys (around 300 bits) but large ciphertexts (around 400MB). The **ADP** construction is then used as a potential candidate for **IO**, but it is not practical yet, essentially because it requires a super-polynomial error in the depth of the branching program to protect against invalid inputs. Given $\ell$ the size of the branching program, modulus $p$ (error is sampled mod $p$) must be $\mathcal{O}(\ell^{4+\epsilon})$, i.e. super-polynomial in $\ell$. An example is given: if $\ell = 2^{13}$, then the **ADP** would be around 100 terabytes. ## More Recent Attacks - [Cryptanalysis of Candidate Obfuscators for Affine Determinant Programs](https://eprint.iacr.org/2021/1684) ## Construction An *affine determinant program* **ADP**: $\{0, 1\}^n\rightarrow\{0, 1\}$ is specified by a tuple $(\mathbf{A}, \mathbf{B}_{1}, \dots, \mathbf{B}_{n})$ of squares matrices over $\mathbb{F}_{q}$ and a function $\textsf{Eval}:\mathbb{F}_{q}\rightarrow\{0, 1\}$ and is evaluated on a in put $\mathbf{x}\in\{0, 1\}^{n}$ by computing $\textsf{Eval}(\text{det}(\mathbf{A} + \sum_{i\in[n]}x_{i}\mathbf{B}_{i}))$. **ADP** is conceptually very simple and might offer a route toward implementable applications. This work has the following results: - A new framework for building obfuscation using **ADP** - A candidate for witness encryption with a practical public-key encryption concrete instantiation - First steps toward a candidate for **iO** ## Witness Encryption - Initial Idea A ciphetext $c$ is encrypted with respect to an instance $x$ of some $\textsf{NP}$ language $L$. The ciphertext can be decrypted using any witness $\pi$ that attests that $x\in L$. The security stipulates that, for any false instance where $s\notin L$, the encryptions relative to $x$ completely hides the message for computationaly bounded adversaries. Note that the instance $x$ is considered public (e.g. a public-key). Witness encryption can be used to build a public-key encryption scheme where public keys are extremly short and generated efficiently. ### Generic Construction - An instance-encoding **ADP** $$\textsf{M}_{h, \ell}=(\textsf{A}^{(h, ell)}, \textsf{B}_{1}^{(h, \ell)}, \dots, \textsf{B}_{n}^{(h, \ell)})$$ - A bit-encoding **ADP** $$\textsf{M}_{b} = (b\textsf{S}, 0, \dots, 0)$$ - An all-accept **ADP** $$\textsf{M}_{AA} = (\textsf{A}^{(AA)}, \textsf{B}_{1}^{(AA)}, \dots, \textsf{B}_{n}^{(AA)})$$ And the ciphertext is the **ADP** $$\textsf{M}_{h, \ell}+\textsf{M}_{b}+\textsf{M}_{AA}$$ The all-accept program is here to prevent leakage of the bit $b$ on evaluations $\mathbf{x}\notin\{0, 1\}^{n}$. This is done by adding noise wich must satisfy the following propeties: - Zero on all binary inputs: $\forall \mathbf{x}\in\{0, 1\}^{n}, \text{det}(\mathsf{M}_{\mathsf{noise}}(\mathbf{x}))=0$ - Non-Zero on all non-binary inputs: $\forall \mathbf{x}\in\mathbb{F}_{q}/\{0, 1\}^{n}$, $\text{Pr}[\text{det}(\textsf{M}_{\textsf{noise}}(\mathbf{x}))=0] \leq \textsf{negl}(n)$. In other words, the noise is sampled as an all-accept branching program over the set of all binary strings. ## Indistinguishability Obfuscation This is much more challenging than witness encryption: 1. How to convert general computations into **ADP**s. 2. The security requirements for witness encryption are much weaker: it only needs to hold on the evasive setting, where the adversary cannot find an accepting input, and allow to know the entire program, except for a single bit that is encrypted. Fortunately there are many ways to convert an $\textsf{NC}^{1}$ into an **ADP** and **IO** for $\textsf{NC}^{1}$ can be bootstrapped into **IO** for any circuit. This work makes use of branching programs as the underlying computational model, which can be represented as an **ADP**. In particular, this representation has the property that for any binary input $\mathbf{x}\in\{0, 1\}^{n}$, $\text{det}(\mathbf{A}+\sum_{i}x_{i}\mathbf{B}_{i})=1$ if $\mathbf{x}$ induces an accepting path in the branching program and $\text{det}(\mathbf{A}+\sum_{i}x_{i}\mathbf{B}_{i})=0$ otherwise. The authors arg that **ADP** has better properties than matrix branching programs, because the later gives rise to "mixed-input" attacks, since matrix branching program have multiple matrices associated with each input bit. ### Generic Approach for Obfuscating a Deterministic Branching Program $BP$ 1. Apply a random local functionality preserving transformation to $BP$, producing $BP'$. 2. Represent $BP'$ as an **ADP** 3. Add a random even-valued error to each matrix, fixing the evaluation function to compute the parity of the determinant 4. Left- and right-randomize the matrices with $\mathbf{R}$, $\mathbf{S}$ such that $\text{det}(\mathbf{R})\times\text{det}(\mathbf{S})=1$. ### Even-Valued-Error Any read-once oblivious branching program can be efficiencly learned. Thus some noise has to be introduced in the obfuscation procedure such that the read once nature of the program is destroyed. The random even-valued error acts as adding edge between each pair of vertices of the branching program, labeled with a random, small, even linear combination of the entire input vector. The resulting program is thus far from being read-once, as evaluating every edge requries reading the entire input. This requires to change the evaluation of the program to computing the parity of the output. ### Super-Polynomial-Error and Modulus Essentially, without a super-polynomial error it is possible to distinguish two different **ADP**, even if they are valide, by looking at the distribution of the norm of their determinant on random inputs. This is prevented by adding a super-polynomial noise as an **ADP** mod $p$ that evaluates to the original **ADP** when both are taken mod $2$ (and changes the evaluation to extracting the parity). The noise will create an overflow mod $p$ that hides the evaluation on non-binary inputs. Given $\ell$ the size of the branching program, modulus $p$ must be $\mathcal{O}(\ell^{4+\epsilon})$, i.e. super-polynomial in $\ell$. An example is given: if $\ell = 2^{13}$, then the **ADP** would be around 100 terabytes.