Module falcon512_poseidon2 

A deterministic Falcon512 Poseidon2 signature over a message.

This version differs from the reference implementation in its use of the Poseidon2 algebraic hash function in its hash-to-point algorithm.

Another point of difference is the determinism in the signing process. The approach used to achieve this is the one proposed in 1. The main challenge in making the signing procedure deterministic is ensuring that the same secret key is never used to produce two inequivalent signatures for the same c. For a precise definition of equivalence of signatures see 1. The reference implementation uses a random nonce per signature in order to make sure that, with overwhelming probability, no two c-s will ever repeat and this non-repetition turns out to be enough to make the security proof of the underlying construction go through in the random-oracle model.

Making the signing process deterministic means that we cannot rely on the above use of nonce in the hash-to-point algorithm, i.e., the hash-to-point algorithm is deterministic. It also means that we have to derandomize the trapdoor sampling process and use the entropy in the secret key, together with the message, as the seed of a CPRNG. This is exactly the approach taken in 2 but, as explained at length in 1, this is not enough. The reason for this is that the sampling process during signature generation must be ensured to be consistent across the entire computing stack i.e., hardware, compiler, OS, sampler implementations …

This is made even more difficult by the extensive use of floating-point arithmetic by the sampler. In relation to this point, the current implementation does not use any platform specific optimizations (e.g., AVX2, NEON, FMA …) and relies solely on the builtin f64 type. Moreover, as per the time of this writing, the implementation does not use any methods or functions from std::f64 that have non-deterministic precision mentioned in their documentation.

Structs

Nonce

Nonce of the Falcon signature.

Polynomial

Represents a polynomial with coefficients of type F.

PublicKey

Public key represented as a polynomial with coefficients over the Falcon prime field.

SecretKey

Represents the secret key for Falcon DSA.

Signature

A deterministic Falcon512 Poseidon2 signature over a message.

SignatureHeader

The header byte used to encode the signature metadata.

SignaturePoly

A polynomial used as the s2 component of the signature.

Constants

PK_LEN

Public key length as a u8 vector.

SK_LEN

Secret key length as a u8 vector.