Haircomb Signature Scheme

Haircomb Signature Scheme Documentation

Introduction

The Haircomb signature scheme is a digital signature scheme designed for post-quantum cryptography. It is based on hash-based cryptography and provides a compact, efficient, and secure method for one time digital signatures. This documentation describes the key components and operational details of the Haircomb signature scheme.

Key Generation

The Haircomb signature scheme generates a public-private key pair using a set of values A to U, which constitute the private key. To generate the public key (X), the system creates 21 hash-chains, each comprising 59,213 hashes. The final result of these chains is hashed to obtain a 256-bit public key. The private key consists of the values A to U.

Pseudo code for key generation (C++):

privkey = randombytes()
data = privkey
for (int j = 0; j < CHAINS; j++) {
    for (int i = 0; i < LEVELS; i++) {
        data[j] = sha256(data[j])
    }
}
pubkey = sha256(data)

Signature Generation

To sign a message, the Haircomb scheme uses Pascal's triangle (the Comb Cutting Function) to calculate a set of 21 numbers (a...u) that sum to 59,213. It then derives the a-th to u-th hash in the corresponding hash chains to produce the signature.

Pseudo code for signature generation (C++):

data = privkey
msg = sha256(message)
cut_comb_where = C(msg, LEVELS, CHAINS)
for (int j = 0; j < CHAINS; j++) {
    for (int i = 0; i < LEVELS - cut_comb_where[j]; i++) {
        data[j] = sha256(data[j])
    }
}
signature = data

Signature Verification

To verify a message, the system recalculates the hash values and obtains X. It then compares X with the provided public key to determine the authenticity of the signature.

Pseudo code for public key re-calculator (C++):

data = signature
msg = sha256(message)
cut_comb_where = C(msg, LEVELS, CHAINS)
for (int j = 0; j < CHAINS; j++) {
    for (int i = 0; i < cut_comb_where[j]; i++) {
        data[j] = sha256(data[j])
    }
}
recalculated_pubkey = sha256(data)

Pseudo code for signature verifier (C++):

recalculated_pubkey = recalculate(signature, message)
if (recalculated_pubkey == pubkey) {
    return ACCEPT_SIGNATURE;
} else {
    return REJECT_SIGNATURE;
}

Comb Cutting Function

The Comb Cutting Function is a mathematical subroutine used by the sign and verify stages of the algorithm. It generates a unique set of 21 numbers in the range [0-59,213] that sum to 59,213 for every 256-bit message digest. The function is bijective, ensuring that a valid original message digest can be uniquely determined from the set of 21 numbers.

Pseudo code for comb cutting function (Python):

from math import factorial as f

def Z(n,c):
    return int(f(n+c-1)/(f(n)*f(c-1)))

def C(m,n,c):
    if c == 1:
        return [n]
    q = 0
    for d in range(0,n+1):
        z = Z(n-d,c-1)
        if q + z > m:
            return [d] + C(m-q,n-d,c-1)
        q += z

Example invocations of the comb cutting function (Python):

C(0,59213,21) #to cut comb for msg 0 (all zero byte transaction)
C(1,59213,21) #to cut comb for msg 1
C(2**256,59213,21) #takes ages because python cannot do large factorials

Derivation of Constants

The constants used in the Haircomb signature scheme are derived based on the mathematical properties of the algorithm. The choice of parameter BYTES, is made to ensure the security of the scheme and of the public keys. The choice of the chains number (21) controls the tradeoff between signature size (CHAINS * BYTES) and the speed of the scheme (time) as measured in the number of hash function invocations (with time proportional to LEVELS). The time to perform one hash invocation is hardware dependent.

Performance Analysis

The Haircomb signature scheme has been implemented in software and evaluated on various platforms. It offers efficient key generation and signature generation, making it suitable for resource-constrained devices. The scheme's memory requirements are also modest. The parallelizability of the algorithm enhances its performance on multi-core processors.

Expected Security Strength

The security of the Haircomb signature scheme is based on the hardness of the collision search problem for the underlying hash function. It is designed to resist both classical and quantum attacks. The expected security strength, when using SHA-256 as the underlying hash function, is estimated to be at least 128 bits.

Analysis of the Algorithm with Respect to Known Attacks

The Haircomb signature scheme has been analyzed for potential attacks, including direct collision attacks on the message digest, parallel hash collision search by Rho method with distinguished points, signature malleability using Grover pre-image search, and collisions in the Comb Cutting Function. While some theoretical vulnerabilities are considered, practical attacks have not been identified.

Conclusion

The Haircomb signature scheme offers advantages in terms of compactness, efficiency, and resistance to side-channel attacks. It is suitable for various applications, including IoT and mobile devices. While the scheme has undergone limited adoption, it presents a promising option for post-quantum cryptography. The security of the scheme is based on strong mathematical foundations and heuristic arguments, with further analysis needed to confirm its robustness.

Statement of Advantages and Limitations

Advantages:

• Compact signature size.

• Efficient key generation and signing.

• Robustness against side-channel attacks.

• Flexibility in parameter selection.

• Blinded use for privacy.

• Double spending problem resolution.

Limitations:

• Limited security analysis.

• Limited adoption.

• Key reuse is not supported.

Please note that this documentation provides only a high level overview of the Haircomb signature scheme and its components. For detailed implementation and deployment, refer to the relevant technical resources and specifications.

Appendix 1: Constants

#define BIG    9
#define LEVELS 59213
#define CHAINS 21
#define BYTES  32