notes

LamportSignature.md (4811B)

---

 # Lamport Signature
 
 **Source:** MIT MAS.S62 Cryptocurrency Engineering and Design L1
 
 **Definition:** The Lamport signature scheme is a single use signature scheme where portions of a private key are leaked to prove the private key is known by the sender of the message, as a way to sign the message.
 
 ## Specifics
 
 ### Key Generation
 
 To generate a private key you generate a pair of 256 256 bit segments of random data. Since 256 bits is 32 bytes, we see the total size of the private key is 16kb (16384 bytes)
 
 To generate the public key we perform hashing on the data from the private key. Specifically, since the sha256 hash function gives hashes that are exactly 256 bits, we apply the hash function to each of the 512 segments of 256 bits above to generate a public key where each of the resulting segments is the hash of the associated segment from the private key. It is still worthwhile to consider the public key as two keys each with 256 segments, but for the purposes of public key generation this doesn't matter. 
 
 ### Signing Messages
 
 To sign a message we first hash the message using the sha256 hash function. This gives us 256 bits of data to work with. 
 
 Using these 256 bits of data, we perform the operations specified in the below pseudocode:
 
 ```
 
 signature = ""
 for idx in range(hash)
     if hash[idx] == 0:
         signature += privateKey.first[idx]
     if hash[idx] == 1:
         signature += privateKey.second[idx]
 return signature
 
 ```
 
 The signature is thus exactly half of the private key where the half revealed is (generally) some portion of the first half and some portion second half of the private key, based on value of the current bit from the message hash.
 
 ### Verifying Messages
 
 To verify a message we iterate over each of the bits from the message's hash and verify the segments revealed as the private key hash to the associated segments of the public key. 
 
 ```
 for idx in range(hash):
     if hash[idx] == 0:
         assert sha256sum(privateKey.first[idx]) == publicKey[idx]
     if hash[idx] == 1:
         assert sha256sum(privateKey.second[idx]) == publicKey[idx]
 ```
 
 ## Limitations
 
 - The keys for lamport signatures, along with the signatures themselves, are large
     - public / private keys are 16kb
     - signatures are 8kb
 - Keys should only be used once
     - One iteration leaks half of the key
     - Two iterations leaks ~3/4 of the key
         - Depending on the message being signed, even more segments may be revealed
     - ...
 
 ## Benefits
 
 - Simple to implement
 - Cheap to compute
     - No large primes
 - Quantum resistant
     - Impacted by grover's algorithm so expect 128 bits of security instead of 256 when facing quantum computers
         - This is generally considered acceptable
 
 ## Implementation
 
 ```go
 
 package main
 
 import (
 	"crypto/rand"
 	"crypto/sha256"
 	"fmt"
 )
 
 type Key struct {
 	firstRow  [256][32]byte
 	secondRow [256][32]byte
 }
 
 func GenerateKeys() (Key, Key) {
 
 	privateKey := Key{}
 
 	for i := range 256 {
 		_, err := rand.Read(privateKey.firstRow[i][:])
 		if err != nil {
 			panic(err)
 		}
 	}
 
 	for i := range 256 {
 		_, err := rand.Read(privateKey.secondRow[i][:])
 		if err != nil {
 			panic(err)
 		}
 	}
 
 	publicKey := Key{}
 
 	for i := range 256 {
 		publicKey.firstRow[i] = sha256.Sum256(privateKey.firstRow[i][:])
 	}
 
 	for i := range 256 {
 		publicKey.secondRow[i] = sha256.Sum256(privateKey.secondRow[i][:])
 
 	}
 
 	return publicKey, privateKey
 }
 
 func Sign(privateKey Key, message string) [256][32]byte {
 
 	messageHash := sha256.Sum256([]byte(message))
 
 	signature := [256][32]byte{}
 
 	for index := range 32 {
 		currentByteString := fmt.Sprintf("%08b", messageHash[index])
 		for idx := range 8 {
 			currentBit := currentByteString[idx]
 			if currentBit == '0' {
 				signature[(index*8)+idx] = privateKey.firstRow[(index*8)+idx]
 			} else {
 				signature[(index*8)+idx] = privateKey.secondRow[(index*8)+idx]
 			}
 		}
 	}
 
 	return signature
 }
 
 func Verify(publicKey Key, message string, signature [256][32]byte) bool {
 
 	messageHash := sha256.Sum256([]byte(message))
 
 	for index := range 32 {
 		currentByteString := fmt.Sprintf("%08b", messageHash[index])
 		for idx := range 8 {
 			currentBit := currentByteString[idx]
 			if currentBit == '0' {
 				// signature[(index * 8) + idx] = privateKey.firstRow[(index * 8) + idx]
 				if sha256.Sum256(signature[(index*8)+idx][:]) != publicKey.firstRow[(index*8)+idx] {
 					return false
 				}
 			} else {
 				if sha256.Sum256(signature[(index*8)+idx][:]) != publicKey.secondRow[(index*8)+idx] {
 					return false
 				}
 			}
 		}
 	}
 
 	return true
 
 }
 
 func main() {
 
 	publicKey, privateKey := GenerateKeys()
 	message := rand.Text()
 	signature := Sign(privateKey, message)
 	valid := Verify(publicKey, message, signature)
 	fmt.Printf("Verified message matches signature: %v\n", valid)
 
 }
 ```