Lamport Signature Scheme Article Index for
Lamport 		Shopping
Scheme 		Website Links For
Signature 		 

Information About

Lamport Signature Scheme
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...




KEYS


Let k be a positive integer and let P=\{0,1\}^k be the set of messages.
Let f:\,Y ightarrow Z be a one-way function and let Y be the set of "signatures".

For 1\leq i\leq k, j=0,1 let y_{ij}\in Y be chosen randomly and z_{ij}=f(y_{ij}).

The key K consists of 2k ys and zs. ys are secret, zs are public.


SIGNING OF A MESSAGE


Let x = x_1\ldots x_k \in\{0,1\}^k be a message.

sig(x_1\ldots x_k)=(y_{1,x_1},\ldots, y_{k,x_k})=(a_1,\ldots,a_k) - notation
and
ver_K(x_1\ldots x_k, a_1,\ldots, a_k) = true \Leftrightarrow f(a_i) = z_{i,x_i}, 1\leq i\leq k

Eve cannot forge a signature because she is unable to invert one-way functions.

Note: A Lamport signature can only be used to sign one message. However combined with Hash Tree s, it is possible to only publish a single hash instead of (z_{ij}) making the signing of many messages more efficient space-wise.

When used in Merkle trees, Lamport signatures form a digital signature scheme that is secure against Quantum Computer s, the only known digital signature scheme to do so.


SEE ALSO




EXTERNAL LINKS