[Cryptography] Improving SHPINCS with integer compositions

[S. J.]

Hi. I'd like to share some improvements over SPHINCS, that I think
might be useful.

There is a well known connection between hash-based signatures and
combinatorics, since  nearly all schemes use Merkle trees. But there
is another: we can also draw a connection to the composition of
integers.

Below is a simple description explaining how integer compositions can
be used to build a one-time signature. I've posted here about it
before. It's more efficient than WOTS. And tough it uses hash chains
just like WOTS, it is actually a generalization of the Lamport OTS.

Also, I add a connection between compositions and the few-times
signatures HORS/PORS.


Integer Compositions, and One Time Signatures
--------------------------------------------------------------------------------

Let's start by defining compositions: a composition of an integer N is
a way of writing N as a sum of elements, considering their order. For
example, the integer 10 can be written as 4+3+2+1, so the tuple (4, 3,
2, 1) is a composition of 10. Since the order also matters, the tuple
(1, 2, 3, 4) is a different composition of 10. In our example, the set
of tuples (10), (9,1), (1,9), (1,1,8), (1,8,1)... are the integer
compositions of 10.

Rather than arbitrary compositions, we'll consider restricted
compositions in our signature. That is, compositions that satisfy some
conditions: we'll use compositions that have exactly k parts, with
each part in the range 0...z.

# Parameters

First of all, we need to define the parameters. Let's choose values N,
k, z such that there are at least 2^256 integer compositions of N with
k parts, with each part in the range 0...z.

Just to see how it works, we'll use smaller values in our example.
Let's define N=10, k=5, z=4.

# Generating the keys

We pick k random values, each the size of the hash. This is our private key.
To each number, we apply the hash function z times. The result is the
public key.

# Signing

We hash the message we want to sign, to get a value m. Then, we pick
the m-th composition from the set of all possible restricted
compositions. We'll call the composition u. Suppose in our example we
have:
u = 1, 4, 3, 0, 2

We compute a complementary tuple y, such that each y[n]=z-u[n]. In our example:
y = 3, 0, 1, 4, 2

We take the values in our private key, and we apply the hash function
to each value, a number of times given by y. In our example we hash
the first value 3 times, 0 times the second, once the third, 4 times
the forth, and 2 the last.

The result is the signature.

# Verifying

To verify, we need to complete the path going from the signature to
the public key, and check that the result matches.

First, we compute the hash m of the message. We take the m-th
composition, that is the tuple u.
We apply the hash function u[n] times to each value in the signature,
and compare the results against the public key.

In our example, we hash the first value once, 4 times the second, 3
times the third, 0 times the forth, and 2 the last.

# Security

To understand the security, let's imagine ourselves in the place of an
attacker, and see what he would need to do to break the signature.

Suppose we know a signature for a valid message. In our example, we
know the signature of a message m that corresponds to the tuples
u = 1, 4, 3, 0, 2
y = 3, 0, 1, 4, 2

Now, suppose the attacker wants to forge a signature for a message m'.
Since m' is different from m, it will correspond to a different tuple
u'. And, since the elements in u' must add up to N, at least one
element must be smaller and at least one must be greater compared to
u. The same will hold for y'. Suppose the tuple u', and its
corresponding tuple y' are:
u' = *0*, 4, *2*, 0, 2
y' = *4*, 0, *2*, 4, 1

The attacker knows how to compute the first value. To go from y[0]=3
to y'[0]=4 he simply applies the hash function once more.

Then he needs to go from y[2]=1 to y'[2]=2. But to get that value, one
needs to apply the hash function *one less time* to the secret key,
and the attacker doesn't know the secret key. So, the attacker knows a
value that is an output of a hash function, and he needs to know its
input. That means breaking the hash function.

Then, the problem of forging a signature is equivalent to the problem
of breaking the hash function. In other words, if the hash function we
use is secure, the signature is secure.

# Advantages

There are two main advantages over WOTS:
First, there is no need to append a checksum. This results in a more
efficient signature.
Second, the parameters N and z adjust how the cost is distributed
between the person that signs the message, and those who verify it. A
small N leads to fast verification, and a small z leads to fast keys
generation and fast signing.


HORS, PORS, Compositions, and Few Times Signatures
--------------------------------------------------------------------------------

PORS is an improved variant of the HORS few-times signature, more
secure under adaptive attacks. In HORS, we pick at most k elements,
and reveal them to generate a signature. In PORS, de picks *exactly* k
elements instead.

If we pick k random positions, it is possible there are collisions,
and two or more are the same. To avoid that, PORS uses a PRF to
generate many elements at random until k different elements are found.

Instead, we could use a composition. Picking k elements out of t
relates to an integer composition in a trivial way: the k elements we
choose split the remaining elements in exactly k+1 groups. As an
example, let's pick 4 out of 11 elements:
- x - - - x x - x - -

The composition is represented by the number of consecutive elements
(marked "-") separated by the picked elements (marked "x"). In the
example, the composition is:
(1, 3, 0, 1, 2)

A way of picking k elements out of t corresponds to a weak (that is,
counting from zero) restricted composition of t-k with exactly k
parts.

(Python code to compute a composition is available at the links below).

--------------------------------

Picking exactly k elements (as in PORS) allows an improvement: we can
replace each element with a hash chain.

So, we compute the hash of the message we want to sign, and split it
into two parts. From the two parts we get 2 independent compositions:
p, and u.

p = (1, 3, 0, 1, 2)
u = (3, 0, 2, 1)

The tuple p determines the hash chains we choose, just like we did
before with PORS.

Then, we use those hash chains to generate a signature, as we did in
the OTS: the tuple u determines the number of hash iterations from the
signature to the top of the chains,

In the illustration, each column represents a hash chain. The 'o's
represent the signature:

-   ^   -   -   -   o   ^   -   ^   -   -
-   ^   -   -   -   -   ^   -   o   -   -
-   ^   -   -   -   -   o   -   -   -   -
-   o   -   -   -   -   -   -   -   -   -

Using hash chains adds a second constraint to an attacker. In addition
to finding a message that picks k elements that were already revealed,
the message needs to map to hash values in the chains that were also
already revealed.

This can make few-times signature more compact for a same level of security.

--------------------------------

Regards,
Santi J.
@jotasapiens

http://jotasapiens.com/research
Integer Compositions Signatures (2016-oct-24)