Linear-only encryption

A linear-only encryption scheme is an additively homomorphic encryption scheme whose only efficiently computable valid ciphertexts, given encryptions of $a_1,\dots ,a_m$, are encryptions of affine combinations of the $a_j$ that an extractor can name — BCIOP13.

Assumption

Let $\mathsf{PKE}=(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$ be a CPA-secure public-key encryption scheme with plaintext space ${\mathbb{F}}_p$ for a prime $p=p(\lambda )$ super-polynomial in $\lambda$, additively homomorphic: an efficient public algorithm, given $\mathsf{pk}$, ciphertexts of $a_1,\dots ,a_m$ and coefficients $\vec{\pi }\in {\mathbb{F}}_p^m$, $b\in {\mathbb{F}}_p$, outputs a ciphertext of $⟨\vec{\pi },\vec{a}⟩+b$. In the game below, $\vec{a}\in {\mathbb{F}}_p^m$ is fixed and the extractor ${\mathcal{E}}_{\mathcal{A}}$ receives the input and random coins $\rho$ of $\mathcal{A}$.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{lo}}_{\PKE,\calA,\calE_\calA,\vec a}(\secpar)$}
\begin{algorithmic}
\State $(\pk, \sk) \gets \KeyGen(1^\secpar)$; $\rho \getsr \bits^{*}$
\State $c_j \gets \Enc(\pk, a_j)$ for $j \in [m]$
\State $c' \gets \calA(\pk, c_1, \ldots, c_m; \rho)$
\State $(\vec\pi, b) \gets \calE_\calA(\pk, c_1, \ldots, c_m, \rho)$
\Comment{$\calE_\calA$ gets $\calA$'s input and coins}
\State $y \gets \Dec(\sk, c')$
\Return $[y \ne \bot \wedge y \ne \langle \vec\pi, \vec a \rangle + b]$
\end{algorithmic}
\end{algorithm}

$\mathsf{PKE}$ is linear-only if for all efficient $\mathcal{A}$ there exists an efficient ${\mathcal{E}}_{\mathcal{A}}$ such that for every polynomial $m=m(\lambda )$ and every $\vec{a}\in {\mathbb{F}}_p^m$,

$${\mathbf{Adv}}_{\mathsf{PKE},\mathcal{A},{\mathcal{E}}_{\mathcal{A}},\vec{a}}^{\mathrm{lo}}(\lambda ):=\mathrm{Pr}\left[{\mathbf{G}}_{\mathsf{PKE},\mathcal{A},{\mathcal{E}}_{\mathcal{A}},\vec{a}}^{\mathrm{lo}}(\lambda )=1\right]$$

is negligible — BCIOP13.

Known Results

• Linear-only encryption gives designated-verifier preprocessing SNARGs for $\mathbf{NP}$ with proofs of a constant number of ciphertexts: Linear-only encryption ⇒ Designated-verifier SNARG — BCIOP13.
• Like the knowledge of exponent assumption, it has the $\forall \mathcal{A}\exists {\mathcal{E}}_{\mathcal{A}}$ form of a knowledge assumption — BCIOP13; such assumptions are not falsifiable in Naor’s sense — standard.
• BCIOP13 base the compilation more generally on forms of linear targeted malleability, which earlier knowledge assumptions imply — BCIOP13.

Variations

Linear-only vector encryption

Plaintexts are vectors in ${\mathbb{F}}_p^{\ell }$ for a prime $p=p(\lambda )$, the homomorphic operations act on whole vectors, and in the game above $\vec{a}=({\vec{a}}_1,\dots ,{\vec{a}}_m)$ with ${\vec{a}}_j\in {\mathbb{F}}_p^{\ell }$, the extractor outputs $\vec{\pi }\in {\mathbb{F}}_p^m$ and $\vec{b}\in {\mathbb{F}}_p^{\ell }$, and $\mathcal{A}$ wins if $\mathsf{Dec}(\mathsf{sk},c^{\prime })\notin \{\perp ,{\sum }_j{\pi }_j{\vec{a}}_j+\vec{b}\}$. A prover is thus constrained to one linear function applied to all coordinates at once — BISW17. Linear-only vector encryption holds if there is a family of CPA-secure schemes, one for each polynomial dimension $\ell =\ell (\lambda )$, each linear-only in this sense.

BISW17 conjecture that variants of Regev encryption are linear-only vector encryption schemes, and use them for designated-verifier SNARGs from lattices: Linear-only vector encryption ⇒ Designated-verifier SNARG — BISW17.

Attacks

• TODO: cryptanalysis of the candidate schemes.

Participates in

Builds on Linear-only encryption

• Linear-only encryption ⇒ Designated-verifier SNARG
• Linear-only vector encryption ⇒ Designated-verifier SNARG (lattice-based) (via Linear-only vector encryption)