User:Skippydo/working

From Wikipedia, the free encyclopedia

In cryptography, the Boneh-Lynn-Shacham signature scheme allows a user to verify that a signer is authentic. The scheme uses a pairing function for verification and signatures are elements in some elliptic curve. This provides defence against index calculus attacks against allowing shorter 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 existance of random oracles and the intractability of the computational Diffie-Hellman (CDH) problem.

Contents

[edit] Gap groups and pairing functions

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

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

By using the bilinear property x + y + z times, we see that if e(gx,gy) = e(g,g)xy = e(g,g)z = e(g,gz), then since GT is a prime order group, xy = z.

[edit] The scheme

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

[edit] 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, gx.

[edit] 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 σ = hx.

[edit] Verificaion

Given a signature σ and a public key gx, we verify that e(σ,g) = e(H(m),g).

[edit] Provable security

          • Coron's upper and lower bounds, commentary on tightness, katz-wang bit.*****