Decision Linear assumption

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.Dan Boneh, Xavier Boyen, Hovav Shacham: [http://crypto.stanford.edu/~dabo/papers/groupsigs.pdf Short Group Signatures]. CRYPTO 2004: 41–55

Informally the DLIN assumption states that given $(u, \, v, \, h, \, u^x, \, v^y)$ , with $u, \, v, \, h$ random group elements and $x, \, y$ random exponents, it is hard to distinguish $h^{x+y}$ from an independent random group element $\eta$ .

Motivation

In symmetric pairing-based cryptography the group $G$ is equipped with a pairing $e :G \times G \to T$ which is bilinear. This map gives an efficient algorithm to solve the decisional Diffie-Hellman problem. John Bethencourt: [https://people.csail.mit.edu/alinush/6.857-spring-2015/papers/bilinear-maps.pdf Intro to Bilinear Maps] Given input $(g, \, g^a, \, g^b, \, h)$ , it is easy to check if $h$ is equal to $g^{ab}$ . This follows by using the pairing: note that

: $e(g^a, g^b) = e(g,g)^{ab} = e(g,g^{ab}).$

Thus, if $h = g^{ab}$ , then the values $e(g^a, g^b)$ and $e(g,h)$ will be equal.

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.

Formal definition

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

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

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

: $D_2 = (u, \, v, \, h, \, u^a, \, v^b, \, \eta).$

The Decision Linear assumption states that $D_1$ and $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 $u,v,h$ . The private key is two exponents such that $u^x = v^y = h$ . Encryption combines a message $m \in G$ with the public key to create a ciphertext

: $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

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

To check that this encryption scheme is correct, i.e. $m' = m$ when both parties follow the protocol, note that

: $m' = 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 $u^x = v^y = h$ yields

: $m' = 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 $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, Allison Bishop Lewko, Brent Waters: [https://dl.acm.org/citation.cfm?id=1653662.1653677 Efficient pseudorandom functions from the decisional linear assumption and weaker variants]. CCS 2009: 112-120 an attribute-based encryption scheme, Lucas Kowalczyk, Allison Bishop Lewko: [https://link.springer.com/chapter/10.1007/978-3-662-48000-7_26 Bilinear Entropy Expansion from the Decisional Linear Assumption]. CRYPTO 2015: 524-541 and a special class of non-interactive zero-knowledge proofs. Benoît Libert, Thomas Peters, Marc Joye, Moti Yung: [https://link.springer.com/chapter/10.1007/978-3-662-48797-6_28 Compactly Hiding Linear Spans]. ASIACRYPT 2015: 681-707

References

Category:Computational hardness assumptions

Category:Elliptic curve cryptography

Category:Pairing-based cryptography