Summary of Affine Determinant Programs: A Framework for Obfuscation and Witness Encryption

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+ϵ})$, 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

Construction

An affine determinant program ADP:

$\{0,1{\}}^n\to \{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

$\mathsf{\text{Eval}}:{\mathbb{F}}_q\to \{0,1\}$ and is evaluated on a in put

$\mathbf{x}\in \{0,1{\}}^n$ by computing

$\mathsf{\text{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

$\mathsf{\text{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
  $${\mathsf{\text{M}}}_{h,\ell }=({\mathsf{\text{A}}}^{(h,ell)},{\mathsf{\text{B}}}_1^{(h,\ell )},\dots ,{\mathsf{\text{B}}}_n^{(h,\ell )})$$
• A bit-encoding ADP
  $${\mathsf{\text{M}}}_b=(b\mathsf{\text{S}},0,\dots ,0)$$
• An all-accept ADP
  $${\mathsf{\text{M}}}_{AA}=({\mathsf{\text{A}}}^{(AA)},{\mathsf{\text{B}}}_1^{(AA)},\dots ,{\mathsf{\text{B}}}_n^{(AA)})$$

And the ciphertext is the ADP

$${\mathsf{\text{M}}}_{h,\ell }+{\mathsf{\text{M}}}_b+{\mathsf{\text{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:
  $\mathrm{\forall }\mathbf{x}\in \{0,1{\}}^n,\text{det}({\mathsf{M}}_{\mathsf{noise}}(\mathbf{x}))=0$
• Non-Zero on all non-binary inputs:
  $\mathrm{\forall }\mathbf{x}\in {\mathbb{F}}_q/\{0,1{\}}^n$,
  $\text{Pr}[\text{det}({\mathsf{\text{M}}}_{\mathsf{\text{noise}}}(\mathbf{x}))=0]\le \mathsf{\text{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 ADPs.
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

${\mathsf{\text{NC}}}^1$ into an ADP and IO for

${\mathsf{\text{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
   $B{P}^{\prime }$.
2. Represent
   $B{P}^{\prime }$ 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+ϵ})$, i.e. super-polynomial in

$\ell$.
An example is given: if

$\ell =2^{13}$, then the ADP would be around 100 terabytes.