Decision Linear assumption

Formal definition

Let ${\displaystyle G}$ be a cyclic group of prime order ${\displaystyle p}$. Let ${\displaystyle u}$, ${\displaystyle v}$, and ${\displaystyle h}$ be uniformly random generators of ${\displaystyle G}$. Let ${\displaystyle a,b}$ be uniformly random elements of ${\displaystyle \{1,2,\dots ,p-1\}}$. Define a distribution

${\displaystyle D_1=(u,v,h,u^a,v^b,h^{a+b}).}$

Let ${\displaystyle \eta }$ be another uniformly random element of ${\displaystyle G}$. Define another distribution

${\displaystyle D_2=(u,v,h,u^a,v^b,\eta ).}$

The Decision Linear assumption states that ${\displaystyle D_1}$ and ${\displaystyle D_2}$ are computationally indistinguishable.

Applications

Linear encryption

Boneh, Boyen, and Shacham define a public key encryption scheme by analogy to ElGamal encryption. In this scheme, a public key is the generators ${\displaystyle u,v,h}$. The private key is two exponents such that ${\displaystyle u^x=v^y=h}$. Encryption combines a message ${\displaystyle m\in G}$ with the public key to create a ciphertext

${\displaystyle c:=(c_1,c_2,c_3)=(u^a,v^b,m\cdot h^{a+b})}$.

To decrypt the ciphertext, the private key can be used to compute

${\displaystyle m^{\prime }:=c_3\cdot (c_1^x\cdot c_2^y{)}^{-1}.}$

To check that this encryption scheme is correct, i.e. ${\displaystyle m^{\prime }=m}$ when both parties follow the protocol, note that

${\displaystyle m^{\prime }=c_3\cdot (c_1^x\cdot c_2^y{)}^{-1}=m\cdot h^{a+b}\cdot ((u^a{)}^x\cdot (v^b{)}^y{)}^{-1}=m\cdot h^{a+b}\cdot ((u^x{)}^a\cdot (v^y{)}^b{)}^{-1}.}$

Then using the fact that ${\displaystyle u^x=v^y=h}$ yields

${\displaystyle m^{\prime }=m\cdot h^{a+b}\cdot (h^a\cdot h^b{)}^{-1}=m\cdot (h^{a+b}\cdot h^{-a-b})=m.}$

Further, this scheme is IND-CPA secure assuming that the DLIN assumption holds.

Short group signatures

Boneh, Boyen, and Shacham also use DLIN in a scheme for group signatures. The signatures are called "short group signatures" because, with a standard security level, they can be represented in only 250 bytes.

Their protocol first uses linear encryption in order to define a special type of zero-knowledge proof. Then the Fiat–Shamir heuristic is applied to transform the proof system into a digital signature. They prove this signature fulfills the additional requirements of unforgeability, anonymity, and traceability required of a group signature.

Their proof relies on not only the DLIN assumption but also another assumption called the ${\displaystyle q}$-strong Diffie–Hellman assumption. It is proven in the random oracle model.

Other applications

Since its definition in 2004, the Decision Linear assumption has seen a variety of other applications. These include the construction of a pseudorandom function that generalizes the Naor–Reingold construction, an attribute-based encryption scheme, and a special class of non-interactive zero-knowledge proofs.