#include "include/jlmots.h"
Detailed Description
Leighton-Micali One-Time Signature Scheme
One-time signature systems, and general-purpose signature systems built out of one-time signature systems, have been known since 1979, were well studied in the 1990s, and have benefited from renewed attention in the last decade. The characteristics of these signature systems are small private and public keys and fast signature generation and verification, but large signatures and moderately slow key generation (in comparison with RSA and ECDSA). Private keys can be made very small by appropriate key generation. In recent years, there has been interest in these systems because of their post-quantum security and their suitability for compact verifier implementations
A signature system provides asymmetric message authentication. The key-generation algorithm produces a public/private key pair. A message is signed by a private key, producing a signature, and a message/signature pair can be verified by a public key. A one-time signature (OTS) system can be used to sign one message securely but will become insecure if more than one is signed with the same public/private key pair. An N-time signature system can be used to sign N or fewer messages securely. A Merkle-tree signature scheme is an N-time signature system that uses an OTS system as a component
The Leighton-Micali Signature (LMS) system (a variant of the Merkle scheme) with the Hierarchical Signature System (HSS) built on top of it that allows it to efficiently scale to larger numbers of signatures
The LMS signing algorithm is stateful; it modifies and updates the private key as a side effect of generating a signature
The key-generation algorithm takes as input an indication of the parameters for the signature system. If it is successful, it returns both a private and public key
The signing algorithm takes as input the message to be signed and the current value of the private key. After the private key of an N-time signature system has signed N messages, the signing algorithm returns the signature and an indication that there is no next value of the private key that can be used for signing
The verification algorithm takes as input the public key, a message, and a signature; it returns an indication of whether or not the signature-and-message pair is valid
A message/signature pair is valid if the signature was returned by the signing algorithm upon input of the message and the private key corresponding to the public key; otherwise, the signature and message pair is not valid with probability very close to one
LMS-OTS Parameters
The signature system uses the parameters n and w, which are both positive integers. The algorithm description also makes use of the internal parameters p and ls, which are dependent on n and w. These parameters are summarized as follows:
- n - the number of bytes of the output of the hash function
- w - the width (in bits) of the Winternitz coefficients; that is, the number of bits from the hash or checksum that is used with a single Winternitz chain. It is a member of the set {1, 2, 4, 8}
- p - the number of n-byte string elements that make up the LM-OTS signature. This is a function of n and w; the values for the defined parameter sets are listed in Table 1 it can also be computed by the algorithm given in Appendix B
- ls - the number of left-shift bits used in the checksum function Cksm
- H - a second-preimage-resistant cryptographic hash function that accepts byte strings of any length and returns an n-byte string
The parameter w determines the length of the Winternitz chains computed as a part of the OTS signature (which involve 
invocations of the hash function); it has little effect on security. Increasing w will shorten the signature, but at a cost of a larger computation to generate and verify a signature. Table 1 illustrates various combinations of n, w, p, and ls, along with the resulting signature length
In general, the LM-OTS signature is 
bytes long, and public key generation will take 
hash computations (a signature generation and verification will take approximately half that on average)
| Parameter Set Name | H | n | w | p | ls | sig_len | type value |
|---|---|---|---|---|---|---|---|
| LMOTS_SHA256_N32_W1 | SHA256 | 32 | 1 | 265 | 7 | 8516 | 0x00000001 |
| LMOTS_SHA256_N32_W2 | SHA256 | 32 | 2 | 133 | 6 | 4292 | 0x00000002 |
| LMOTS_SHA256_N32_W4 | SHA256 | 32 | 4 | 67 | 4 | 2180 | 0x00000003 |
| LMOTS_SHA256_N32_W8 | SHA256 | 32 | 8 | 34 | 0 | 1124 | 0x00000004 |
LMS-OTS Private Key
The format of the LM-OTS private key is defined as
An implementation MAY use a psuedorandom method to compute x[i]. The details of the psuedorandom method do not affect interoperability, but the cryptographic strength MUST match that of the LM-OTS algorithm
LMS-OTS Public Key
The LM-OTS public key is generated from the private key by iteratively applying the function H to each individual element of x, for iterations, then hashing all of the resulting values. The format of the LM-OTS public key is defined as
where K
![$ H(I | Q | u16str(D_PBLC) | y[0] | ... | y[p-1]) $](form_474.png)
where D_PBLC is the fixed two-byte value 0x8080, which is used to distinguish the last hash from every other hash in this system
LMS-OTS Checksum
A checksum is used to ensure that any forgery attempt that manipulates the elements of an existing signature will be detected. This checksum is needed because an attacker can freely advance any of the Winternitz chains. That is, if this checksum were not present, then an attacker who could find a hash that has every digit larger than the valid hash could replace it (and adjust the Winternitz chains)
LMS-OTS Signature Generation
The LM-OTS signature of a message is generated by doing the following in sequence: prepending the LMS key identifier I, the LMS leaf indentifier Q, the value D_MESG (0x8181), and the randomizer C to the message; computing the hash; concatenating the checkum of the hash to the hash itself; considering the resulting value as a sequence of w-bit values; and using each of the w-bit values to determine the number of times to apply the function H to corresponding element of the private key. The outputs of the function H are concatenated together to form the signature. The format of the LM-OTS Signature is defined as
LMS-OTS Signature Verification
In order to verify a message with its signature (an array of n-byte strings, denoted by y), the receiver must "complete" the chain of iterations of H using the w-bit coefficients of the string resulting from the concatenation of the message hash and it's checksum. This computation should result in a value that matches the provided public key
The source code contained or described herein and all documents related to the source code (herein called "Material") are owned by John Peter Greninger and Sheila Rocha Greninger. Title to the Material remains with John Peter Greninger and Sheila Rocha Greninger. The Material contains trade secrets and proprietary and confidential information of John Peter Greninger and Sheila Rocha Greninger. The Material is protected by worldwide copyright and trade secret laws and treaty provisions. No part of the Material may be used, copied, reproduced, modified, published, uploaded, posted, transmitted, distributed, or disclosed in any way without prior express written consent of John Peter Greninger and Sheila Rocha Greninger (both are required)
No license under any patent, copyright, trade secret, or other intellectual property right is granted to or conferred upon you by disclosure or delivery of the Materials, either expressly, by implication, inducement, estoppel, or otherwise. Any license under such intellectual property rights must be express and approved by John Peter Greninger and Sheila Rocha Greninger in writing
Licensing information can be found at www.protocolpp.com/license with use of the binary forms permitted provided that the following conditions are met:
- Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution
- Any and all modifications must be returned to John Peter Greninger at GitHub.com https://github.com/jpgreninger/protocolpp for evaluation. Inclusion of modifications in the source code shall be determined solely by John Peter Greninger. Failure to provide modifications shall render this license NULL and VOID and revoke any rights to use of Protocol++®
- Commercial use (incidental or not) requires a fee-based license obtainable at www.protocolpp.com/shop
- Academic or research use requires prior written and notarized permission from John Peter and Sheila Rocha Greninger
Use of the source code requires purchase of the source code. Source code can be purchased at www.protocolpp.com/shop
- US Copyrights at https://www.copyright.gov/
- TXu002059872 (Version 1.0.0)
- TXu002066632 (Version 1.2.7)
- TXu002082674 (Version 1.4.0)
- TXu002097880 (Version 2.0.0)
- TXu002169236 (Version 3.0.1)
- TXu002182417 (Version 4.0.0)
- TXu002219402 (Version 5.0.0)
- TXu002272076 (Version 5.2.1)
- TXu002383571 (Version 5.4.3)
The name of its contributor may not be used to endorse or promote products derived from this software without specific prior written permission and licensing
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER AND CONTRIBUTOR "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE
The documentation for this class was generated from the following file:
- jlms/include/jlmots.h
