Module falcon512_poseidon2
Expand description
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.
- Public
Key - Public key represented as a polynomial with coefficients over the Falcon prime field.
- Secret
Key - Represents the secret key for Falcon DSA.
- Signature
- A deterministic Falcon512 Poseidon2 signature over a message.
- Signature
Header - The header byte used to encode the signature metadata.
- Signature
Poly - A polynomial used as the
s2component of the signature.