Implementing The Lamport-Diffie One-Time Signature

The Lamport-Diffie one-time signature is used to securely sign a message only once, and a new signature is generated for every time a message is to be signed.

Overview: The Lamport-Diffie OTS

To sign a one bit message, two values of x, x1 and x2 are chosen, and corresponding values of y are computed using a hash function. All y values are sent to the recipient. If the bit to be signed is a '1', then the signer sends x1 only to the recipient, else if the bit to be signed is a zero, then the signer sends the value x2 only.

The recipient can verify the signature by computing y1 from the given x1. If the given y and the computed y match, it confirms that only the signer could have sent the message, as only he would know the value of x that could be used to generate y1.

The recipient cannot alter the signature, since if he/she claims to have not received x1, then he/she should have a value for x2 (i.e. if the bit isn't a '1', it has to be a zero), which is only known to the signer.

This one-bit-signing system can be applied to multiple bits to sign longer messages.

Disadvantages

1. Generating two x and two y values for each bit does not work well for larger systems with many users and a large number of messages to be signed.

The Project

This Project consists of a User class. The user can generate, send, receive, and verify one-time signatures.

Generating one-time signatures

1. The user's message is converted into binary.
2. Two x's and corresponding y's are generated for each bit in the message using SHA-256 hashing algorithm.
3. All generated y-values are sent to the user that has requested for the signature.
4. If the bit is a '1', the first x-value of the pair is sent and the second x-value is withheld. If the bit is a '0', the second x-value of the pair is sent, and the first is withheld.
5. To ensure that no x-value is reused, an offset is kept that is incremented periodically. Any signature starts from the offset and generates new x-values for every signature. In this way, no x-value is ever reused.

Verifying the signature's authenticity

1. The recipient can verify the authenticity of the signature by computing the value of y from the given value of x, and comparing it to the value of y it received. If they match, the signature is valid; Else it is invalid.
2. The receiver cannot alter any of the values for the reasons given in the initial description.
3. The receiver can then convert the binary data to characters that will form the message.

Screenshots

The screenshots attached below show the result of User "Aburi" sending a message to user "Maguro" who verifies it on receipt.

Future Scope

1. Apply Merkle's improvement to the Lamport-Diffie OTS.
2. Apply Winternitz improvement to the Lamport-Diffie OTS.