DLIN ⇒ PKE (Linear Encryption)

Fully-black-box reduction · standard model · BBS04 · security loss: tight up to an additive $O(1/p)$: one oracle call

Statement

If the decisional linear assumption holds for a group generator $\mathsf{GrGen}$, Linear Encryption over $(\mathbb{G},g,p)\leftarrow \mathsf{GrGen}(1^{\lambda })$ is a CPA-secure PKE scheme; no pairing is needed. The secret key is $(x_1,x_2)\stackrel{\$}{\leftarrow }({\mathbb{Z}}_p^{\ast }{)}^2$ and the public key is $(u,v,h)\in {\mathbb{G}}^3$ with $u^{x_1}=v^{x_2}=h$. A message $m\in \mathbb{G}$ is encrypted as $(T_1,T_2,T_3)=(u^a,v^b,m\cdot h^{a+b})$ for $a,b\stackrel{\$}{\leftarrow }{\mathbb{Z}}_p$, and decrypted as $T_3/(T_1^{x_1}{T}_2^{x_2})$ — BBS04.

Sketch

On a DLIN challenge $(u,v,h,u^a,v^b,Z)$ the reduction sets $\mathsf{pk}=(u,v,h)$ and answers the challenge query with $(u^a,v^b,m_{\beta }\cdot Z)$: for $Z=h^{a+b}$ this is a correctly distributed encryption of $m_{\beta }$ under a public key distributed as in the scheme up to statistical distance $O(1/p)$, and for uniform $Z$ the ciphertext is independent of $\beta$ — standard.

Notes

• A ciphertext is three group elements for a one-element message, and the public key is three group elements — BBS04.
• DLIN is believed to hold in groups with a symmetric bilinear pairing, where DDH is easy and ElGamal (DDH ⇒ PKE) is insecure; Linear Encryption is the counterpart of ElGamal for such groups — BBS04.