Protocol++® (Protocolpp®)  v5.6.2
jwots Class Reference

#include "include/jwots.h"

Detailed Description

The eXtended Merkel Signature Scheme (XMSS), a hash-bashed digital signature scheme that is based on existing descriptions in scientific literature. There are three types of signatures specified for Winternitz One-Time Signature Plus (WOTS+), a one-time signature scheme; XMSS, a single-tree scheme; and XMSS^MT, a multi-tree variant of XMSS. Both XMSS and XMSS^MT use WOTS+ as a main bulding block. XMSS provides cryptographic digital signatures without relying on the conjectured hardness of mathematical problems. Instead, it is proven that it only relies on the properties of cryptographic hash functions. XMSS provides strong security guarantees and is even secure when the collison resistance of the underlying hash function is broken. Its is suitable for compact implementations, is relatively simple to implement, and naturally resists side-channel attacks. Unlike most other signature systems, hash-based signatures can so far withstand known attacks using quantum computers

WOTS+ One-Time Signatures

WOTS+ is an OTS scheme; while a private key can be used to sign any message, each private key MUST be used only once to sign a single message. In particular, if a private key is used to sign two different messages, the scheme becomes insecure

WOTS+ Parameters

WOTS+ uses the parameters 'n' and 'w'; both tak positive integer values and are summarized below

  • n - the message length as well as the length of a private key, public key, or signature element in bytes
  • w - the Winternitz parameter; it is a member of the set {4, 16}

The parameters are used to compute the values len, len1, and len2 as defined below

  • len - The number of n-byte string elements in a WOTS+ private key, public key, and signature. Its is computed as $ len = len1 + len2 $
  • len1 - Computed as $ len1 = std::ceil(8n/std::log2(w)) $
  • len2 - Computed as $ len2 = std::floor(std::log2(len1 * (w-1))/std::log2(2)) + 1 $

The value of 'n' is determined by the cryptographic hash function used for WOTS+. The value of 'n' is the input length that can be processed by the signing algorithm. It is often the length of a message digest

The parameter 'w' can be chosen from the set {4, 16}. Larger 'w' values result in shorter signatures but slower overall signing operations. Values of 4 and 16 yeild the optimal trade-offs and easy implementation

Conversion to Base W

A byte string can be considered as a string of base 'w' number or integers in the set {0, ..., w - 1}. If X is a len_X-byte string, and 'w' is a member of the {4, 16}, then base_w(X, w, out_len) outputs an array of out_len integers between 0 and w-1. The length out_len is REQUIRED to be less than or equal to $ out_len = 8 * len_X / std::log2(w) $ See Algorithm 1 in RFC8391

WOTS+ Chaining Function

The chaining function computes an interation of F on an n-byte input using outputs of PRF It takes an OTS hash address as input. This address willl have the first six 32-bit words set to encode the address of this chain. In each iteration, PRF is ised to generate a key F and a bitmask that is XORed to the intermediate result before it is processed by F. In the following, ADRS is a 32-byte OTS hash address and SEED is an n-byte string. To generate keys and bitmasks, PRF is called with SEED as key and ADRS as input. The chaining function takes as input an n-byte string X, a start index i, and a number of steps 's', as well as ADRS and SEED. The chaining function returns as output the value obtained by iterating F for 's' times on input X, using the outputs of PRF. See Algorithm 2 in RFC8391

WOTS+ Private Key

The private key in WOTS+ is denoted as 'sk', it is a length 'len' array of n-byte strings This private key MUST be only used to sign at most one message. Each n-byte string MUST either be selected randomly from a uniform distribution procedure, or be selected using a crytpographically secure pseudorandom procedure. See Algorithm 3 in RFC8391

WOTS+ Public Key

A WOTS+ key pair defines a virtual structure that consists of 'len' hash chains of length w. The len 'n' byte strings in the private key each define the start node for one hash chain. The public key consists of the end nodes of these hash chains. Like the private key, the public key is also a length 'len' array of n-byte strings. To compute the hash chain, the chaining function (Algorithm 2) is used. An OTS hash address and a seed have to be provided by the calling algorithm. This address will encode the address of the WOTS+ key pair within a greater structure. The WOTS+ algorithm MUST NOT manipulate any parts of ADRS except for the last three 32-bit words. See Algorithm 4 in RFC8391

WOTS+ Signature

A WOTS+ signature is a length 'len' array of n-byte strings. The WOTS+ signature is generated by mapping a message to 'len' integers between 0 and w-1. The message is transformed into len1 base_w numbers using Algorithm 1. Next a checksum is computed and appended ot the transformed message as len2 base_w numbers. The maxiumum possible checksum is $ csum = len1 * (w - 1) * {2}^{8} $. Due to this fact a uint32_t is sufficient to hold the checksum. Each of the base_w integers is used to select a node from a different hash chain. The signature is formed by concatenating the selected nodes. An OTS hash address and seed have to be provided by the calling algorithm. See Algorithm 5 in RFC8391

0 ... n bytes
+----------------+
| sig_ots[0] |
+----------------+
| ... |
+----------------+
| sig_ots[len-1] |
+----------------+

WOTS+ Signature Verification

In order to verify a signature on a message M, the verifier computes a WOTS+ public key vaue from the signature. This can be done by 'completing' the chain computation starting from the signature values, using the base_w values of the message hash and its checksum. The result is then compared given public key. If the values are equal, the signature is accepted. Please note that the SEED used here is public information also available to the verifier. See Algorithm 6 of RFC8391

XMSS Tree
Protocol++® (ProtocolPP®) written by : John Peter Greninger • © John Peter Greninger 2015-2024 • All Rights Reserved
All copyrights and trademarks are the property of their respective owners

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)

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: