OTS (One-Time signature)

The name of the algorithm type implies that it can be securely used only once. The reason is that every time a message is signed, a part of the private key is being exposed. If used multiple times, all the private key parts will eventually become exposed and, therefore, compromised. However, OTS algorithms were developed in the 1970s, and if properly used, they were safe enough for the time.

Specialists distinguish two most widely known types of digital signatures:

1.1 LOTS (Lamport One-Time Signature)¹

In 1979 Leslie Lamport suggested an improvement of M.Rabin's digital signature algorithm (1978) and introduced the concept of OTS that can be built from any one-way function, for example, a hash function. Lamport defined the one-way function as easy to compute but hard to revert. By contrast, with RSA (an algorithm suggested in 1977 by Ron Rivers, Adi Shamir, and Leonard Adleman), LOTS' hash is longer and, thus, believed to be more secure.

Since OTS belongs to Asymmetric Cryptography, the first step in using the algorithm is Public & private key pair generation.

1.1.1 LOTS Private Key Generation

The length of the private key depends on the length of the hash function used to generate it. If a hashing algorithm has length $n$ then $2n$ random secret values must be generated to form the private key:

$$PrivateKey = X_0 || Y_0 ~||~ X_1 || Y_1 ~||...||~ X_{n-1} || Y_{n-1}$$

1.1.2 LOTS Public Key Generation

The Public Key is generated by concatenating the hashed values of the generated secrets.

$$PublicKey = hash(X_0) || hash(Y_0) ~||~ hash(X_1) || hash(Y_1) ~||...||~ hash(X_{n-1}) || hash(Y_{n-1})$$

1.1.3 Signature Generation

Before signing, a hash is generated from the message or the transaction. This resulting hash can be represented as a bit string $|~0~|~1~|~1~|~0~|~1~|~0~|~0~|~...~|~0~|$ To sign a message we must publish one of the keys from the pair depending on whether the corresponding bit is $|~0~|$ or $|~1~|$. The final signature (SIG)

$$|~0~| ~=>~ SK(~X_0~ || ~Y_0~) ~=>~ SIG_0(X_0) \\ |~1~| ~=>~ SK(~X_1~ || ~Y_1~) ~=>~ SIG_1(Y_0) \\ ... \\ |0| => SK(X_{n-1} || Y_{n-1}) => SIG_{n-1}(X_{n-1})$$

Since both the message and the signature are public an adversary can reconstruct a part, potentially, one half of the secret key (SK). If the key is reused, every time where there is a different bit value ($1$ instead of $0$ or vice versa) the second part of the secret key will be exposed.

$$bit_0 ~ is ~|~0~| ~ and ~ SIG_0(X_0) ~=>~ SK(~X_0~ || ~?_0~) \\ bit_1 |~1~| ~ and ~ SIG_1(Y_1) ~=>~ SK(~?_1~ || ~Y_1~) \\ ... \\ bit_{n-1} ~ |0| ~ and ~ SIG_{n-1}(X_{n-1}) => SK(X_{n-1} || ?_{n-1})$$

1.1.4 LOTS Signature Verification

Since the public key is a compilation of hashes of the $(X||Y)$ values of the secret key, we can run the signature trough the same hashing algorithm and if the hashes match, the signature is valid.

$$hash(SIG_0(X_0)) == hash(X_0) || hash(Y_0) \\ hash(SIG_1(Y_1)) == hash(X_1) || hash(Y_1) \\ ... \\ hash(SIG_{n-1}(X_{n-1})) == hash(X_{n-1}) || hash(Y_{n-1})$$

1.2 WOTS (Winternitz One-Time Signature)

The major difference of WOTS is that a single secret value is used per a signed message block rather than each bit of a signed message which is the case for LOTS.

The paper² mathematically proves the WOTS to be existentially unforgeable by a chosen message attack (EU-CMA) if used only once. The paper states that the signature is forgeable should it be used multiple times and the adversary has $t-time$ and $q$ attempts to break it.

$$Sig (t,\in,q) ~ is ~ EU-CMA, ~ with ~ probability ~\ge ~\in~ after ~ making ~ \le~ q ~ querries$$

1.2.1 Secret Key Generation

1. The first step is choosing $\omega$ or the Winternitz parameter responsible for the compression level. It must be a natural number greater than 1.

$$\omega \in \N,~ \omega \in~ > 1$$

2. Then we generate an array or a string of random values of length $n$ where

$$x = Rand\{0,1\}^{(n,l)}$$

3. $l$ is the length of each $x$ secret key item:
   $$sk = \{sk_1,...sk_l\} = Rand\{0,1\}^{(n,l)}$$

1.2.2 Public Key Generation

The Public Key (PK) used for the signature verification is generated by applying a hash function to each $x$ value:

$$pk = (pk_0,...,pk_l) = (x, \int_{sk_1}^{\omega-1}(x),~...~,\int_{sk_l}^{\omega-1}(x))$$

The above can be represented as:

Key	Representation
sk	$x_1$	$...$	$x_l$
	$\vee$	$\vee$	$\vee$
pk	hash($x_1$)	...	hash($x_l$)

1.2.3 Signing a Message

The $M$ message is signed the following way:

1. Step one, checksum computation:

$$C = \sum_{i=1}^{l_1}(\omega-1-M_i)$$

2. Base $B$ computation:

$$B = (b_1, ... , b_l) = M || C$$

3. The message signature computation:

$$\sigma = (\sigma_1, ... , \sigma_l) = (\int_{sk_1}^{b_1}(x), ... , \int_{sk_l}^{b_l}(x))$$

1.2.4 Signature verification

The signature is considered valid if the comparison of the hashed signed message blocks result exactly in the public key elements exactly in their order:

$$(\int_{\sigma_1}^{\omega-1-b_1}(pk_0), ~ ... ~ ,\int_{\sigma_l}^{\omega-1-b_l}(pk_0)) ~ ?= (pk_0,...,pk_l)$$

Conclusion

OTS can be used quite securely to sign messages only once. However, they cannot be conveniently used in our case since they imply a new key generation for every new message alongside the new public key transportation to the verifying smart contract on the chain of destination. The last implies the introduction of another trusted entity or, in case of receiving the public key from an untrusted entity, it should have its secure way of verification. All that brings additional overhead and complexity while we strive to keep the system simple, maintainable, and stable.

---

1. https://www.microsoft.com/en-us/research/uploads/prod/2016/12/Constructing-Digital-Signatures-from-a-One-Way-Function.pdf↩
2. https://huelsing.net/wordpress/wp-content/uploads/2013/05/wotsspr.pdf↩