Lamport Signature Scheme

What is Lamport Signature?

Lamport signature is a technique for creating cryptographic digital signatures. Any cryptographically secure one-way function can be used to create Lamport signatures. It involves the use of the hash function.

A single message can only be signed with a single Lamport key. This is a fairly effective digital signature scheme because it can be used with hash trees to sign many digital messages with a single key.

The Lamport signature work in three steps:-

1. Generation of Key

2. Generation of Signature

3. Verification of Signature

Generation of Key

Generation of a key in mathematical notation:-

• Let k be a positive integer, and P = {0,1}^k be the set of messages. Let f: Y -> Z be a one-way hash function.
• For 1<=i<=k  and j belongs to {0,1}, Mohit randomly chooses y_(i,j) and applies the one-way hash function to calculate z_(i,j)=f(y_{i,j}).
• The private and public keys have 2k  values, y_{i,j}  and z_{i,j}, respectively.
   

Suppose Mohit wants to sign his signature digitally; he will need to create a Lamport key pair, mainly a private key and its public key.

A secure random number generator produces 256 pairs of random numbers combined to form the private key. A number has 256 bits in total. Mohit will safely store this private key. A private key is secure, so for proper authentication, it should not be shared with anyone.

Mohit hashes every 512 digits in his private key to produce the public key. This will generate an additional 1024 numbers with 256 bits each. This public key can be shared with everyone.

Generation of Signature

Generation of a Signature in mathematical notations:-

• Let M = m1,m2,m3,....,mk belongs to {0,1}^k be the message Mohit wants to sign.
• The signature generated is in the form sig(m1,m2,....mk)= (y_{1,m1},y_{2,m2},....)= (s1,s2,....sk).
• The signature is sent along with the message to the receiver.
   

To create a 256-bit digest, Mohit hashes her message using a 256-bit cryptographic hash function.

Now, Mohit will choose the corresponding number from the pair of numbers in her private key for each bit based on whether the bit value is 1 or 0, i.e., the first number is chosen if the bit is 0, and the second number is chosen if the bit is 1. His signature is a series of 256 numbers produced as a result.

Noting that Mohit’s private key has now been used, it should never be used again. He must never publish or use the remaining 256 random numbers that he did not use for the signature. He should delete them ideally. Otherwise, someone else might be able to make fake signatures.

Verification of Signature

Rohit, to whom Mohit is sending a message, creates a 256-bit digest by hashing the message using the same 256-bit cryptographic hash function.

Rohit chooses the number from Mohit's public key for each bit based on whether the bit value is 1 or 0. For example, if the first bit of the digital message hash is 0, Rohit chooses the first hash in the first pair of digest, and so on. The process is carried out, and as a result, 256 numbers are generated.

Rohit generates a 256-bit digest by hashing each number in Mohit's signature. The signature is legitimate if this matches the run of 256 numbers that Rohit had previously selected.

It is to be noted that Mohit published the signature of a message whose private key's 2256 random numbers were unknown to anyone else. As a result, nobody else can generate the correct list of 256 random numbers for the signature. Additionally, even after Mohit published the signature, nobody else knew the remaining 256 random numbers, making it impossible for them to make signatures that work with other message hashes.

Frequently Asked Questions

What is Public Key?

A public key is defined as the numerical value that is used to encrypt the data in cryptography. It is employed to validate a digital signature.

What is a Private Key?

In cryptography, a private key, also called a secret key, is a variable that works with an algorithm to encrypt and decrypt data.

What is Hashing?

Any data type can be transformed into a distinct text string using the cryptographic technique called hashing. For Example, SHA1 is a Hashing function.

What is Digital Signature?

A digital signature is a particular electronic signature that uses public-key cryptography, which supports identity authentication and ensures data integrity and transactions.

What is Encoding?

Encoding transforms data into a format needed for various information processing requirements, such as assembling and running programs, data transmission, archival, and decompression.

Conclusion 

Congratulations on finishing the blog! We have discussed the Lamport Signature Scheme. We further show the Lamport signatures scheme works on message encrypting and decrypting in cryptography.

We hope this blog has helped you enhance your knowledge of the Lamport Signature Scheme. Do not stop learning! We recommend you read some cryptography articles: 

1. What is Cryptography?
2. RSA Signature Scheme in Cryptography
3. ElGamal Signature Scheme
    

Refer to our Guided Path to upskill yourself in DSA, Competitive Programming, JavaScript, System Design, and many more! If you want to test your competency in coding, check out the mock test series and participate in the contests hosted on Coding Ninjas Studio!

But suppose you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. For placement preparations, you must look at the problems, interview experiences, and interview bundles.

We wish you Good Luck! 

Happy Learning!