Boneh–Lynn–Shacham

In cryptography, the BonehLynnShacham (BLS) signature scheme allows a user to verify that a signer is authentic. The scheme uses a bilinear pairing for verification and signatures are group elements in some elliptic curve. Working in an elliptic curve provides defense against index calculus attacks against allowing shorter signatures than FDH signatures. Signatures are often referred to as short signatures, BLS short signatures, or simply BLS signatures. The signature scheme is provably secure (that is, the scheme is existentially unforgeable under adaptive chosen-message attacks) assuming both the existence of random oracles and the intractability of the computational Diffie–Hellman problem.[1]

Pairing functions

A gap group is a group in which the computational Diffie–Hellman problem is intractable but the decisional DiffieHellman problem can be efficiently solved. Non-degenerate, efficiently computable, bilinear pairings permit such groups.

Let e\colon G\times G\rightarrow G_T be a non-degenerate, efficiently computable, bilinear pairing where G, G_T are groups of prime order, r. Let g be a generator of G. Consider an instance of the CDH problem, g,g^x, g^y. Intuitively, the pairing function e does not help us compute g^{xy}, the solution to the CDH problem. It is conjectured that this instance of the CDH problem is intractable. Given g^z, we may check to see if g^z=g^{xy} without knowledge of x, y, and z, by testing whether e(g^x,g^y)=e(g,g^z) holds.

By using the bilinear property x+y+z times, we see that if e(g^x,g^y)=e(g,g)^{xy}=e(g,g)^{z}=e(g,g^z), then since G_T is a prime order group, xy=z.

The scheme

A signature scheme consists of three functions: generate, sign, and verify.

Key generation

The key generation algorithm selects a random integer x in the interval [0, r  1]. The private key is x. The holder of the private key publishes the public key, g^x.

Signing

Given the private key x, and some message m, we compute the signature by hashing the bitstring m, as h=H(m). We output the signature \sigma=h^x.

Verification

Given a signature \sigma and a public key g^x, we verify that e(\sigma,g)=e(H(m),g^x).

Properties

See also

References

  1. Dan Boneh, Ben Lynn, and Hovav Shacham (2004). "Short Signatures from the Weil Pairing". Journal of Cryptology 17: 297–319. doi:10.1007/s00145-004-0314-9.
  2. D. Boneh, C. Gentry, H. Shacham, and B. Lynn In proceedings of Eurocrypt 2003, LNCS 2656, pp. 416-432, 2003

External links

This article is issued from Wikipedia - version of the Sunday, February 14, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.