- BLS (Cryptography)
In
cryptography , the Boneh-Lynn-Shacham signature scheme allows a user to verify that a signer is "authentic". The scheme uses apairing function for verification and signatures are group elements in someelliptic curve . Working in an elliptic curve provides defense againstindex calculus attacks against allowing shorter signatures thanFDH signatures. Signatures are often referred to as "short signatures", "BLS short signatures", or simply "BLS signatures". The signature scheme isprovably secure (that is, the scheme is existentially unforgeable underadaptive chosen-message attack s) assuming both the existence ofrandom oracle s and the intractability of thecomputational Diffie-Hellman problem .cite journal
author =Dan Boneh ,Ben Lynn , andHovav Shacham
title = Short Signatures from the Weil Pairing
journal = Journal of Cryptology
volume = 17
date = 2004
pages = 297-319]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, bilinearpairing function s permit such groups.Let be a non-degenerate, efficiently computable, bilinear
pairing function where , are groups of prime order, . Let be a generator of . Consider an instance of the CDH problem, , . Intuitively, the pairing function does not help us compute a solution to the CDH problem. It is conjectured that this instance of the CDH problem is intractable. Given , we may check to see if without knowledge of , , and , by computing .By using the bilinear property times, we see that if , then since is 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 integer in 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 .
Verificaion
Given a signature and a public key , we verify that .
References
Wikimedia Foundation. 2010.