Everipedia Logo
Everipedia is now IQ.wiki - Join the IQ Brainlist and our Discord for early access to editing on the new platform and to participate in the beta testing.
Boneh–Lynn–Shacham

Boneh–Lynn–Shacham

Incryptography, the Boneh–Lynn–Shacham (BLS)signature schemeallows a user to verify that a signer is authentic. The scheme uses abilinear pairingfor verification, and signatures are elements of anelliptic curvegroup. Working in an elliptic curve group provides some defense againstindex calculusattacks (with the caveat that such attacks are still possible in the target groupof the pairing), allowing shorter signatures thanFDHsignatures for a similarlevel 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 isprovably secure(the scheme isexistentially unforgeableunderadaptive chosen-message attacks) assuming both the existence ofrandom oraclesand the intractability of thecomputational Diffie–Hellman problemin 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.

Letbe a non-degenerate, efficiently computable, bilinear pairing where,are groups of prime order,. Letbe a generator of. Consider an instance of theCDH problem,,,. Intuitively, the pairing functiondoes not help us compute, the solution to the CDH problem. It is conjectured that this instance of the CDH problem is intractable. Given, we may check to see ifwithout knowledge of,, and, by testing whetherholds.
By using the bilinear propertytimes, we see that if, then, sinceis a prime order group,.

The scheme

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

Key generation

The key generation algorithm selects a random integerin the interval [0, r − 1]. The private key is. The holder of the private key publishes the public key,.

Signing

Given the private key, and some message, we compute the signature by hashing the bitstring, as. We output the signature.

Verification

Given a signatureand a public key, we verify that.

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]
Citation Link//doi.org/10.1007%2Fs00145-004-0314-9Dan 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.
Oct 1, 2019, 5:52 PM
[2]
Citation Linkcrypto.stanford.eduD. Boneh, C. Gentry, H. Shacham, and B. Lynn [1] In proceedings of Eurocrypt 2003, LNCS 2656, pp. 416-432, 2003
Oct 1, 2019, 5:52 PM
[3]
Citation Linkcrypto.stanford.eduBen Lynn's PBC Library
Oct 1, 2019, 5:52 PM
[4]
Citation Linkgithub.comChia Network's BLS signatures implementation (C++)
Oct 1, 2019, 5:52 PM
[5]
Citation Linkciteseerx.ist.psu.edu10.1.1.589.9141
Oct 1, 2019, 5:52 PM
[6]
Citation Linkdoi.org10.1007/s00145-004-0314-9
Oct 1, 2019, 5:52 PM
[7]
Citation Linkcrypto.stanford.edu[1]
Oct 1, 2019, 5:52 PM
[8]
Citation Linkcrypto.stanford.eduBen Lynn's PBC Library
Oct 1, 2019, 5:52 PM
[9]
Citation Linkgithub.comChia Network's BLS signatures implementation (C++)
Oct 1, 2019, 5:52 PM
[10]
Citation Linken.wikipedia.orgThe original version of this page is from Wikipedia, you can edit the page right here on Everipedia.Text is available under the Creative Commons Attribution-ShareAlike License.Additional terms may apply.See everipedia.org/everipedia-termsfor further details.Images/media credited individually (click the icon for details).
Oct 1, 2019, 5:52 PM