Boneh–Lynn–Shacham

In cryptography, the Boneh–Lynn–Shacham (BLS) signature scheme allows a user to verify that a signer is authentic. The scheme uses a bilinear pairing for verification, and signatures are elements of an elliptic curve group. Working in an elliptic curve group provides some defense against index calculus attacks (with the caveat that such attacks are still possible in the target group ${\displaystyle G_{T}}$ of the pairing), allowing shorter signatures than FDH signatures for a similar level of security. Signatures produced by the BLS signature scheme are often referred to as short signatures, BLS short signatures, or simply BLS signatures. The signature scheme is provably secure (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 in a gap Diffie–Hellman group.[1]

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 pairings permit such groups.

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

By using the bilinear property ${\displaystyle x+y+z}$ times, we see that if ${\displaystyle e(g^{x},g^{y})=e(g,g)^{xy}=e(g,g)^{z}=e(g,g^{z})}$, then, since ${\displaystyle G_{T}}$ is a prime order group, ${\displaystyle 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 ${\displaystyle x}$ in the interval [0, r − 1]. The private key is ${\displaystyle x}$. The holder of the private key publishes the public key, ${\displaystyle g^{x}}$.

Signing

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

Verification

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

Properties

• Simple Threshold Signatures
• Signature Aggregation: Multiple signatures generated under multiple public keys for multiple messages can be aggregated into a single signature.[2]
• Unique and deterministic: for a given key and message, there is only one valid signature (like RSA PKCS1 v1.5, EdDSA and unlike RSA PSS, DSA, ECDSA and Schnorr).

See also

• Pairing-based cryptography

References

1. Dan Boneh; Ben Lynn & Hovav Shacham (2004). "Short Signatures from the Weil Pairing". Journal of Cryptology. 17 (4): 297–319. CiteSeerX 10.1.1.589.9141. 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

• Ben Lynn's PBC Library
• Chia Network's BLS signatures implementation (C++)