The Decision Linear (DLIN) assumption is a computational hardness assumption used in elliptic curve cryptography. In particular, the DLIN assumption is useful in settings where the decisional Diffie - Hellman assumption does not hold (as is often the case in pairing-based cryptography). The Decision Linear assumption was introduced by Boneh, Boyen, and Shacham.[1]
Informally the DLIN assumption states that given
(u,v,h,ux,vy)
u,v,h
x,y
hx+y
η
In symmetric pairing-based cryptography the group
G
e:G x G\toT
(g,ga,gb,h)
h
gab
e(ga,gb)=e(g,g)ab=e(g,gab).
h=gab
e(ga,gb)
e(g,h)
Since this cryptographic assumption, essential to building ElGamal encryption and signatures, does not hold in this case, new assumptions are needed to build cryptography in symmetric bilinear groups. The DLIN assumption is a modification of Diffie-Hellman type assumptions to thwart the above attack.
Let
G
p
u
v
h
G
a,b
\{1,2,...,p-1\}
D1=(u,v,h,ua,vb,ha+b).
η
G
D2=(u,v,h,ua,vb,η).
D1
D2
Boneh, Boyen, and Shacham define a public key encryption scheme by analogy to ElGamal encryption.[1] In this scheme, a public key is the generators
u,v,h
ux=vy=h
m\inG
c:=(c1,c2,c3)=(ua,vb,m ⋅ ha+b)
m':=c3 ⋅
x | |
(c | |
1 |
⋅
y) | |
c | |
2 |
-1.
m'=m
m'=c3 ⋅
x | |
(c | |
1 |
⋅
y) | |
c | |
2 |
-1=m ⋅ ha+b ⋅ ((ua)x ⋅ (vb)y)-1=m ⋅ ha+b ⋅ ((ux)a ⋅ (vy)b)-1.
ux=vy=h
m'=m ⋅ ha+b ⋅ (ha ⋅ hb)-1=m ⋅ (ha+b ⋅ h-a-b)=m.
Boneh, Boyen, and Shacham also use DLIN in a scheme for group signatures. [1] 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
q
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, [3] an attribute-based encryption scheme, [4] and a special class of non-interactive zero-knowledge proofs. [5]