WAMS  Winternitz Abstract Merkle Signature Scheme
Author: Herman Schoenfeld
Version: 1.0
Date: 20200720
Copyright: (c) Sphere 10 Software Pty Ltd
License: MIT
Abstract
A quantumresistant, manytime signature scheme combining Winternitz and MerkleSignature schemes is proposed. This construction is compatible with the Abstract Merkle Signature (AMS) Scheme[1] and thus is an AMSalgorithm called "WAMS".
1. Introduction
WAMS is a specialization of the AMS[1] scheme parameterized with the standard Winternitz onetime signature scheme (WOTS). WAMS is a quantumresistant cryptographic scheme suitable for blockchainbased applications.
This document focuses only on the OTSlayer of WAMS. The merkle signatures themselves are performed as part of the AMSlayer of WAMS which is defined in the AMS document[1]. The reader should familiarize themselves with the AMS document as it provides the background context for AMSalgorithms of which WAMS is one.
2. WAMS Scheme
The Winternitz Abstracted Merkle Signature (WAMS) Scheme is a general purpose, quantumresistant digital signature scheme. WAMS is an AMS algorithm that selects the standard Winternitz OTS (WOTS) as the OTS parameter. As part of the parameter set inherited from AMS, WAMS includes the additional parameters H
a cryptographic hash function and w
, the Winternitz parameter.
The cryptographic hash function used is fundamental to the security of WAMS (an analysis of which is not provided in this document). So long as the user selects a standard Cryptographic Hash Function (CHF) such as SHA2256
or Blake2b
the security of WAMS is equivalent to standard WOTS constructions. For performance, the use of WOTS# may be used in conjunction with Blake2b128
to reduce signature sizes without introducing vulnerability to birthdayclass attacks.
In this construction, the Winternitz parameter w
refers to the number of bits being simultaneously signed as famously proposed by Merkle3 (who was inspired by Winternitz). Varying the parameter w
changes the size/speed tradeoff without affecting security. For example, the higher the value the more expensive (and slower) the computations but the shorter the signature and private key size. The lower the value the faster the computation but larger the signature and key size. The range of values for w
supported in WAMS is 1 <= w <= 16
.
Since the WAMS scheme inherits the AMS scheme, it is required to define the following:

The OTS private key which is a standard WOTS private key.

The OTS public key is a standard WOTS public key (hash).

Definitions for
GenOTSSig
andVerOTSSig
which generate and verify WOTS signatures in accordance to the WAMS1specification.
Definitions for all of the above are provided below.
2.1 Notation & Definitions

Notations and definitions from AMS1 are inherited by this document.

ReadBits(arr, N, M)
is a function that skipsN
bits and then readsM
bits from the byte arrayarr
and reinterprets the bits as a bigendian unsigned 32bit integer. 
WriteBits(x, arr, N, M)
is a function that converts unsigned 32bit integerx
to bigendian byte array of 4 bytes and writes the firstM
bits of the array into arrayarr
start at bit offsetN
. 
Bitordering in (2) and (3) is such that bit
i
ofarr
maps to bytearr[i SHR 3]
and to inbyte bitindex(i SHR 3)  (i SHL 3)
. Explained below:
Bitordering within `ReadBits` and `WriteBits` are such that the
leastsignificant bit (LSB) is the leftmost bit of that byte.
For example, consider an array of two bytes C = [A,B]:
Memory layout of C=[a,b] with their inbyte indexes marked.
A:[7][6][5][4][3][2][1][0] B:[7][6][5][4][3][2][1][0]
C:[0][1][2][3][4][5][6][7] [8][9]...
The bit indexes of the 16bit array C are such that:
Bit 0 maps to A[7]
Bit 1 maps to A[6]
Bit 7 maps to A[0]
Bit 8 maps to B[7]
Bit 16 maps to B[0]
2.2 WAMS Parameters
Parameters  Description  Bits 
h 
Tree height (used in AMS layer)  8 
w 
Winternitz parameter, how many bits are simultaneously signed via the Winternitz process  8 
H 
Cryptographic hash function, and security parameter for the scheme (digest length)  8 
Note that the Winternitz w
and H
are stored in the RESERVED part of the AMS private key. The cryptographic hash function is stored as a code, defined as follows:
2.2.1 Cryptographic Hash Function Code
Value  Cryptographic Hash Function 
0  user specified 
1  SHA2256 
2  Blake2b256 
3  Blake2b160 
4  Blake2b128 
The author reserves the right to update this list as new usecases emerge.
2.3 WAMS Variables
During key generation, signing and verification the following variables are calculated based on the parameter set.
Variable  Formula  Description 
U 
sizeof(H(x)) * 8 for any x 
Security parameter for the scheme (and number of bits in a hash H ) 
DigitBase 
2^w 
The number of values a signed "digit" can take 
SigDigits 
ceil(256 / w) 
Number of digits in the messagedigest being signed 
CheckDigits 
Log((2^w  1) * (256/w))_{2^w} 
Number of digits in checksum being signed 
OTS_KeyDigits 
SigDigits + CheckDigits 
Number of "digit keys" in a WOTS private key (used by AMSlayer) 
OTS_SigLen 
OTS_KeyDigits 
Number of "digit signatures" in a WOTS sig (used by AMSlayer) 
2.4 WOTS Theory Basics
The WOTS scheme follows the Lamport5 signature approach but allows a signer to sign w
bits of a messagedigest simultaneously rather than 1. This collection of bits is a treated as a "digit" of base 2^w
.
For example, in the case of w=8
the digits simply become bytes since each digit can take any value within 0..255
. The fundamental cryptographic mechanism in WOTS is the ability to sign individual digits using a unique "digit private key".
For example, to sign the byte b
(for w=8
), a signer first derives a "private digit key" as K = H(secret)
and a "public digit key" P = H^255(K)
. Notice that all the values of b
map to a unique hash in that chain of hashes. The signer advertises the "public digit key" prior to signing any digit. When signing a digit b
, the signer provides the verifier the value S=H^(255b)(K)
referred to as the "signature of b
". The verifier need only perform b
more iterations on the signature s
to arrive at the public key P
, since H^b(S) = H^b(H^(255b)(K)) = H^255(K) = P
.
At this point, the verifier has cryptographically determined the signer had knowledge of K
since the signature S
was the b'th
preimage of P
. This process of signing digits is repeated for each digit in the message and each digit signature is concatenated to form the signature. The message being signed is always a digest of an actual logical message, and thus referred to as the "messagedigest".
In WOTS, the individual "digit keys" and "digit signatures" are concatenated to comprise the "key" and "signatures" respectively. This results in order of magnitude larger key and signature objects when compared to traditional ellipticcurve / discrete logarithm schemes. This is a significant downside of OTS schemes when used in postquantum cryptography (PQC) use cases. The burden of large keys can be optimized by using the hash of a public key as WAMSD prescribes. The burden of large signatures can be halved by choosing shorter hash functions without impacting security, as prescribed by the WOTS#4 variant. .
NOTE In order to prevent signature forgeries arising from digit signature reuse for prior messages, a checksum is calculated and appended to the messagedigest and cosigned. The checksum is calculated in such a way that any increment to a message digit necessarily decreases a checksum digit. Thus it is impossible to forge a signature since it requires the preimage of at least one checksum digit signature.
The reader can further their understanding of the theory and basics of WOTS by reviewing the literature and through this succinct diagram2.
2.4.1 WOTS Private Key
A WOTS private key P'
is a onetime key used to generate WOTS signatures and defined as follows:
1: P' = bytearray[OTS_KeyDigits, U/8]
2: for n in {0, OTS_KeyDigits  1}
3: P'[n] = cryptographically random U bits
The WOTS private key is an array of OTS_KeyDigits
"digit keys" each of U/8
bytes in length. The total size of the WOTS private key is thus (OTS_KeyDigits) * (U/8)
bytes.
Whilst the WOTS scheme requires that private keys be cryptographically random, they can be deterministically derived from a secret seed. In WAMS the AMS Private Key is used (see below).
2.4.2 WOTS Public Key Hash
A WOTS public key hash K'
is a onetime key used to verify WOTS signatures signed by a WOTS private key P'
and defined as follows:
1: k = bytearray[OTS_KeyDigits, U/8]
2: for n in {0, OTS_KeyDigits  1}
3: k[n] = H^(DigitBase  1)( P'[n] )
4: K' = H( k[0]  k[1]  ...  k[OTS_KeyDigits  1] )
The length of a WOTS public key hash is U/8
bytes.
NOTE In WAMS, the WOTS public key hash is used rather than the WOTS public key since signature verification always rebuilds the public key from the signature. Since the verifier derives the public key it can derive the public key hash with one additional step. By using the hash rather than the key in the AMS signature, a ~50% space saving is made to the AMS signature length.
NOTE 2 Since the OTS layer passes the public key hash to the AMS layer, the AMS layer does not need hash the public keys when building the hashtree of OTS keys, it simply reuses the OTS public key value which is itself a hash digest (saving 2^h
hash computations when computing a batch).
2.5 WAMS Key Generation
Given a AMS Private Key P
and batch number B
, the i'th
WOTS keypair (P'
, K'
) are derived as follows:
1: algorithm GenOTSKeys
2: Input:
3: P: AMS Private Key
4: B: batch number (UInt64)
5: i: index (UInt16)
6: Output:
7: P': the WOTS private key that derives K'
8: K': the i'th WOTS public key hash in the batch
9: PseudoCode:
10: P' = bytearray[OTS_KeyDigits, U/8]
11: k = bytearray[OTS_KeyDigits, U/8]
12: let seed = ToBytes(i)  ToBytes(B)  P
13: for n in {0, OTS_KeyDigits  1}
14: P'[n] = H^2( n  seed )
15: k[n] = H^(DigitBase  1) ( P'[n] )
16: K' = H( k[0]  k[1]  ...  k[OTS_KeyDigits  1] )
17: end algorithm
2.6 WOTS Signature Generation
A WOTS signature is an 2D array of bytes of dimensions [OTS_KeyDigits, U/8]
and generated as follows:
1: algorithm GenOTSSig
2: Input:
3: m: a messagedigest (U/8 bytes)
4: P': a WOTS private key
5: Output:
6: S': a WOTS signature
7: PseudoCode:
8: S' = bytearray[OTS_KeyDigits, U/8]
9: // sign message part
10: let c = 0 ; checksum value
11: for n in {0, SigDigits  1}
12: let v = 2^w  ReadBits(m, w*n, w)  1
13: c = c + v;
14: S'[n] = H^v( P'[n] )
15:
16: // sign checksum part
17: let c_bytes = bytearray[4]
19: WriteBits(c, c_bytes, 0, 32)
20: for n in {0, CheckDigits  1}
21: let v = 2^w  ReadBits(c_bytes, w*n, w)  1
22: S'[SigDigits + n] = H^v( P'[SigDigits + n] )
24: end algorithm
2.7 WOTS Signature Verification
Here a WOTS signature is verified to a WOTS public key hash by rebuilding the WOTS public key from the signature, hashing it and comparing with public key hash provided by the AMS layer.
1: algorithm VerOTSSig
2: Input:
3: S': a WOTS signature (byte[ OTS_KeyDigits, U/8 ])
4: m: a messagedigest (byte[U/8])
5: K': WOTS public key/hash (byte[U/8])
6: Output: Boolean
7: PseudoCode:
8: k = byte[ OTS_KeyDigits, U/8 ] ; the WOTS public key
9: ; verify message part
10: let c = 0 ; checksum value
11: for n in {0, SigLen  1}
12: let d = ReadBits(m, w * n, w) ; note: d + v = 2^w  1
13: c = 2^w + d  1
14: k[n] = H^d( S'[n] ) ; note: k[n] = H^d(H^c(P'[n]))
15:
16: ; verify checksum part
17: let c_bytes = bytearray[4]
18: WriteBits(c, c_bytes, 0, 32)
19: for n in {0, CheckDigits  1}
20: let d = ReadBits(c_bytes, w * n, w)
21: k[SigDigits + n] = H^d( S'[SigDigits + n] )
22:
23: ; compare pub key hash
24: let PKH = H( k[0]  k[1]  ...  k[OTS_KeyDigits  1] )
25: return (K' = PKH) ; check sig rebuilt the public key hash
26: end algorithm
3. WAMS#
WAMS# is a variant of WAMS which selects WOTS#4 rather than WOTS as the OTS. WOTS# is virtually identical to WOTS except the messagedigest is salted to harden the signature security to a sufficient level that thwarts birthdayclass attacks. This allows the selection of shorter hash functions which produce shorter and faster signatures for same security as WOTS.
The WAMS# implementation is virtually identical to WAMS except for the following changes:

A cryptographically random salt
R
ofU
bits is generated during signing. 
For any message
m
, the signer signs the "sigmac"SMAC(m, R)
rather than the messagedigestH(m)
which is defined asSMAC(m, R) = H(R  H (R  H(m)))
. 
R
is appended to the signature. 
During verification, the verifier similarly verifies
SMAC(m, R)
rather than the ordinary messagedigest.
The reader is referred to the reference implementation of WAMS# which succinctly overloads WAMS with these minor changes.
4. Object Lengths & Throughput
A C# implementation in .NET 7 was developed and object lengths and performance metrics are measured below. All tests were performed on a single thread on an Intel Core i910900K CPU 3.70 GHz with 32GB RAM. The implementation was not performance tuned so the throughput metrics are useful when compared relative to each other.
OTS  CHF bits  Winternitz w 
Height h 
Public Key Length (b)  Signature Length (b)  Sign Throughput  Verify Throughput 
WOTS  128  2  0  32  2163  3620  18098 
WOTS#  128  2  0  32  2211  3425  13139 
WOTS  128  2  8  32  2163  3832  17919 
WOTS#  128  2  8  32  2211  3523  12056 
WOTS  128  2  16  32  2163  3759  18137 
WOTS#  128  2  16  32  2211  3528  12111 
WOTS  128  4  0  32  1107  2821  11479 
WOTS#  128  4  0  32  1155  2619  10403 
WOTS  128  4  8  32  1107  2803  13454 
WOTS#  128  4  8  32  1155  2610  9861 
WOTS  128  4  16  32  1107  2810  13470 
WOTS#  128  4  16  32  1155  2602  9515 
WOTS  128  8  0  32  579  432  2406 
WOTS#  128  8  0  32  627  414  2079 
WOTS  128  8  8  32  579  434  2403 
WOTS#  128  8  8  32  627  419  2749 
WOTS  128  8  16  32  579  432  2411 
WOTS#  128  8  16  32  627  404  2749 
WOTS  160  2  0  36  2703  3850  17026 
WOTS#  160  2  0  36  2763  3607  11620 
WOTS  160  2  8  36  2703  3828  16875 
WOTS#  160  2  8  36  2763  3567  11800 
WOTS  160  2  16  36  2703  3871  16969 
WOTS#  160  2  16  36  2763  3551  11572 
WOTS  160  4  0  36  1383  2864  12419 
WOTS#  160  4  0  36  1443  2702  9318 
WOTS  160  4  8  36  1383  2841  12564 
WOTS#  160  4  8  36  1443  2685  9841 
WOTS  160  4  16  36  1383  2854  12586 
WOTS#  160  4  16  36  1443  2680  9120 
WOTS  160  8  0  36  723  434  2154 
WOTS#  160  8  0  36  783  417  2184 
WOTS  160  8  8  36  723  428  2145 
WOTS#  160  8  8  36  783  422  2425 
WOTS  160  8  16  36  723  427  2156 
WOTS#  160  8  16  36  783  421  2032 
WOTS  256  2  0  48  4323  3937  12474 
WOTS#  256  2  0  48  4419  3662  9235 
WOTS  256  2  8  48  4323  3951  12275 
WOTS#  256  2  8  48  4419  3620  8829 
WOTS  256  2  16  48  4323  3905  12373 
WOTS#  256  2  16  48  4419  3666  9168 
WOTS  256  4  0  48  2211  3059  8653 
WOTS#  256  4  0  48  2307  2885  7711 
WOTS  256  4  8  48  2211  3081  8549 
WOTS#  256  4  8  48  2307  2873  7151 
WOTS  256  4  16  48  2211  3025  8527 
WOTS#  256  4  16  48  2307  2865  7035 
WOTS  256  8  0  48  1155  485  1299 
WOTS#  256  8  0  48  1251  464  1849 
WOTS  256  8  8  48  1155  489  1345 
WOTS#  256  8  8  48  1251  471  1372 
WOTS  256  8  16  48  1155  487  1331 
WOTS#  256  8  16  48  1251  458  1502 
Throughput is measured in "Signatures Per Second"
References
[1] Herman Schoenfeld. "An Abstract Merkle Signature Scheme (AMS)", 2020.
[2] Crypto4A. "Hash Chains and the Winternitz OneTime Signature Scheme". URL: https://crypto4a.com/sectorizationdefunct/WOTS/. Accessed on: 20200720.
[3] Ralph Merkle. "Secrecy, authentication and public key systems / A certified digital signature". Ph.D. dissertation, Dept. of Electrical Engineering, Stanford University, 1979. URL: http://www.merkle.com/papers/Certified1979.pdf.
[4] Herman Schoenfeld. "WOTS#  Shorter and Faster Winternitz Signatures". URL: https://vixra.org/abs/2007.0194. Accessed on: 20200720.
[5] L. Lamport. "Constructing digital signatures from a oneway function". Technical Report SRICSL98, SRI International Computer Science Laboratory, Oct. 1979.