Informally the DLIN assumption states that given , with random group elements and random exponents, it is hard to distinguish from an independent random group element .
Motivation
In symmetric pairing-based cryptography the group is equipped with a pairing which is bilinear. This map gives an efficient algorithm to solve the decisional Diffie-Hellman problem. [2] Given input , it is easy to check if is equal to . This follows by using the pairing: note that
Thus, if , then the values and 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 be a cyclic group of primeorder. Let , , and be uniformly random generators of . Let be uniformly random elements of . Define a distribution
Let be another uniformly random element of . Define another distribution
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 . The private key is two exponents such that . Encryption combines a message with the public key to create a ciphertext
.
To decrypt the ciphertext, the private key can be used to compute
To check that this encryption scheme is correct, i.e. when both parties follow the protocol, note that
Then using the fact that yields
Further, this scheme is IND-CPAsecure assuming that the DLIN assumption holds.
Short group signatures
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.