Witness encryption is a powerful cryptographic primitive, which allows a ciphertext to be decrypted by anyone who holds a valid witness to a chosen NP statement, with no prior interaction between sender and receiver. A practical construction would unlock a wide set of applications, including time-lock and event-triggered disclosure, sealed-bid auctions, conditional on-chain payments, fair exchange, and access control gated by zero-knowledge proofs. Today, many of these are realized only with trusted parties or other workarounds.
Recently, we proposed a new witness encryption scheme that is more efficient than previous approaches and can be implemented in practice. It is based on an earlier construction from 2020, extending it to general arithmetic programs. However, in both the original construction and our adaptation, the cryptanalysis relies on heuristics rather than reductions of known hard problems.
In particular, since these constructions are of algebraic nature, cryptanalytic attacks like (re)linearization approaches and more specialized attacks on certain classes of instances seem to be the most promising directions. This is true both for the original construction and for our adaptation.
Although neither construction is broken and there have been extensive efforts in cryptography to optimize algebraic attacks (see, e.g., XSL approaches on the AES and recent research in Gröbner basis attacks), a better understanding of the security of AADPs is desirable, especially when using them in high-stakes settings like Bitcoin.
For this purpose, we designed cryptographic challenges given in the following. We welcome anyone to attempt to break small instances of our new scheme or to discover structural properties that were unknown before.
We refer to our construction as the AADP (arithmetic affine determinant programs). It consists of a setup phase and an encryption/decryption phase. For the purpose of this description, we briefly recall the specification without going into the details. Interested readers are referred to our paper.
We denote by $m$ the number of arithmetic gates (constraints) and by $n$ the number of variables. In our instances, $n \approx m$ (we emphasize that this condition is important in order to prevent certain classes of attacks).
Given a projectively safe constraint system $(A, B, C, D)$, the setup produces public matrices $M^{(0)}, \dots, M^{(n)} \in \mathbb{F}^{k \times k}$ with $k = 2m+1$. For each gate $i \in \{0, \dots, m-1\}$, we define the linear forms $a_i(\overline{X}), b_i(\overline{X}), c_i(\overline{X}), d_i(\overline{X})$ from the constraint system and a secret random linear form $\xi_i(\overline{X}) = \sum_j \xi_{i,j} X_j$ with $\xi_{i,j} \stackrel{\$}{\leftarrow} \mathbb{F}$. The $4 \times 4$ gate matrix is then defined as
$$ U_i(\overline{X}) = \begin{pmatrix} a_i(\overline{X}) & c_i(\overline{X}) & -\xi_i(\overline{X}) & 0 \\ d_i(\overline{X}) & b_i(\overline{X}) & 0 & \xi_i(\overline{X}) \\ 0 & 0 & b_i(\overline{X}) & c_i(\overline{X}) \\ 0 & 0 & d_i(\overline{X}) & a_i(\overline{X}) \\ \end{pmatrix}. $$
Secret random masking matrices $L_i \stackrel{\$}{\leftarrow} \mathbb{F}^{k \times 4}$ and $R_i \stackrel{\$}{\leftarrow} \mathbb{F}^{4 \times k}$ are sampled, and the public matrix is then defined as a sum over the gates s.t.
$$ M(\overline{X}) = \sum_{i=0}^{m-1} L_i \cdot U_i(\overline{X}) \cdot R_i. $$
If $x$ is a valid witness, each $U_i(x)$ has rank $2$ and $M(x)$ has rank $2m$, so $\det(M(x)) = 0$. Otherwise, $M(x)$ has full rank with high probability.
To encrypt a message $\texttt{msg} \in \mathbb{F}$, we set the ciphertext to
$$ \widehat{M} \leftarrow M + \texttt{msg} \cdot \underbrace{x_0}_{= 1} \cdot (0, \dots, 0, 1)^\top \cdot (0, \dots, 0, 1), $$
i.e., the message is added to the bottom-right entry of $M^{(0)}$. Decryption with a valid witness $\overline{x}$ evaluates $\widehat{M}$ at $(x_0, \overline{x}) = (1, \overline{x})$ and recovers $\texttt{msg}$ as the unique root $t$ of $\det(\widehat{M}(1, \overline{x}) - t \cdot (0, \dots, 0, 1)^\top (0, \dots, 0, 1)) = 0$, which is linear in $t$.