Boneh–Lynn–Shacham
   HOME

TheInfoList



OR:

A BLS digital signature—also known as Boneh–Lynn–Shacham (BLS)—is a cryptographic signature scheme which 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 In mathematics, an elliptic curve is a smooth, projective, algebraic curve of genus one, on which there is a specified point . An elliptic curve is defined over a field and describes points in , the Cartesian product of with itself. If ...
group. Working in an elliptic curve group provides some defense against
index calculus In computational number theory, the index calculus algorithm is a probabilistic algorithm for computing discrete logarithms. Dedicated to the discrete logarithm in (\mathbb/q\mathbb)^* where q is a prime, index calculus leads to a family of algo ...
attacks (with the caveat that such attacks are still possible in the target group 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 Provable security refers to any type or level of computer security that can be proved. It is used in different ways by different fields. Usually, this refers to mathematical proofs, which are common in cryptography. In such a proof, the capabiliti ...
(the scheme is existentially unforgeable under adaptive chosen-message attacks) in the random oracle model assuming the intractability of the computational Diffie–Hellman problem in a gap Diffie–Hellman group.


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 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^, 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^ 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)^=e(g,g)^=e(g,g^z), then, since G_T is a prime order group, xy=z.


BLS signature scheme

A signature scheme consists of three functions: ''generate'', ''sign'', and ''verify''. ;Key generation The key generation algorithm selects a random integer x such as 0 < x < r. 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

*Simple Threshold Signatures *Signature Aggregation: Multiple signatures generated under multiple public keys for multiple messages can be aggregated into a single signature.D. Boneh, C. Gentry, H. Shacham, and B. Lyn
Aggregate and Verifiably Encrypted Signatures from Bilinear Maps
proceedings of Eurocrypt 2003, LNCS 2656, pp. 416-432, 2003
*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).


Applications

* Chia network has used BLS signaturesBLS signatures
/ref> * By 2020, BLS signatures were used extensively in
version 2 Version may refer to: Computing * Software version, a set of numbers that identify a unique evolution of a computer program * VERSION (CONFIG.SYS directive), a configuration directive in FreeDOS Music * Cover version * Dub version * Remix * ' ...
(Eth2) of the
Ethereum Ethereum is a decentralized, open-source blockchain with smart contract functionality. Ether (Abbreviation: ETH; sign: Ξ) is the native cryptocurrency of the platform. Among cryptocurrencies, ether is second only to bitcoin in market capita ...
blockchain, as specified in the
IETF The Internet Engineering Task Force (IETF) is a standards organization for the Internet and is responsible for the technical standards that make up the Internet protocol suite (TCP/IP). It has no formal membership roster or requirements and a ...
draft BLS signature specification—for cryptographically assuring that a specific Eth2 validator has actually verified a particular transaction. The use of BLS signatures in Ethereum is considered a solution to the verification bottleneck only for the medium term, as BLS signatures are not quantum secure. Over the longer term—say, 2025–2030— STARK aggregation is expected to be a drop-in replacement for BLS aggregation.


See also

*
Pairing-based cryptography Pairing-based cryptography is the use of a pairing between elements of two cryptographic groups to a third group with a mapping e :G_1 \times G_2 \to G_T to construct or analyze cryptographic systems. Definition The following definition is commonl ...


References


External links


Summary description of the Algorand draft standard effortBen Lynn's PBC LibraryChia Network's BLS signatures implementation (C++)
{{DEFAULTSORT:Boneh-Lynn-Shacham Digital signature schemes Pairing-based cryptography