BLS (Cryptography)

BLS (Cryptography)

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 group elements in some elliptic curve. Working in an elliptic curve provides defense against index calculus attacks against allowing shorter signatures than FDH 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 existence of random oracles and the intractability of the computational Diffie-Hellman problem.cite journal
author = Dan Boneh, Ben Lynn, and Hovav 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, bilinear pairing functions permit such groups.

Let ecolon G imes G ightarrow G_T be a non-degenerate, efficiently computable, bilinear pairing function 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^x, g^x. Intuitively, the pairing function e does not help us compute g^{xy} a 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^{xy}=g^z without knowledge of x, y, and z, by computing e(g^x,g^y)=e(g,g^z).

By using the bilinear property x+y+z times, we see that if e(g^x,g^y)=e(g,g)^{xy}=e(g,g)^{z}=e(g,g^z), then since G_T is a prime order group, 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 x in the interval [0,r-1] . 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.

Verificaion

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

References


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • BLS — may stand for:*Basic life support, an emergency medical protocol; *Bell South Corporation, ticker symbol for the United States telephone company; *Bern Lötschberg Simplon railway, a former railway company in Switzerland (successor is BLS AG);… …   Wikipedia

  • Digital signature — This article is about secure cryptographic signatures. For simple signatures in digital form, see Electronic signature. A digital signature or digital signature scheme is a mathematical scheme for demonstrating the authenticity of a digital… …   Wikipedia

  • Электронная цифровая подпись — Стиль этой статьи неэнциклопедичен или нарушает нормы русского языка. Статью следует исправить согласно стилистическим правилам Википедии. Электронная подпись (ЭП) информация в электронной форме, присоединенная к другой информации в электронной… …   Википедия

  • Software engineering — (SE) is the application of a systematic, disciplined, quantifiable approach to the development, operation, and maintenance of software, and the study of these approaches; that is, the application of engineering to software.[1] It is the… …   Wikipedia

  • List of software engineering topics — This list complements the software engineering article, giving more details and examples. For an alphabetical listing of topics, please see List of software engineering topics (alphabetical).Influence on societySoftware engineers affect society… …   Wikipedia

  • Bicycle messenger — Bicycle courier, London, UK, riding a fixed gear bicycle with spoke cards …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”