Think of PQC As A Cyber World (As Mostly) Without Trapdoors

I attended a NIST workshop on PQC yesterday, and the chat was all around crypto agility. The move to PQC is basically just a natural part of our migration away from methods that do not have the core security proofs that we need. These existing methods all seem a bit out of date these days, and were often based on trap-door methods.

The problem with a trap door is that eventually the target will find out where the catch is and not fall down the trap door. For many of our existing public key methods, we have used a trap door — a magical way to reverse an operation. The strength of the method is then the strength of the trap door method. This is the case for the RSA method, and which uses Fermat’s Little Theorem to perform the trap door.

Many of our new post-quantum cryptography methods avoid the trapdoor technique and focus on more difficult problems. For the recently defined NIST standards for digital signatures, there are two main methods: lattice approaches with the Fiat-Shamir method for a non-interactive approach (Dilithium — ML-DSA, FIPS 204), and hash-based methods (SPHINCS+ — SLH-DSA, FIPS 205):

I appreciate it is difficult to see what is going on in my little Doodle, so I will try to explain in English.

SPHINCS+ — Hash-based signatures

On the right-hand side of the above graphic, we see the approach of a Lamport signature, and where we generate 256 private keys for A, and 256 private keys for B. The public key is then the hash of all of these keys (512 in total). When we sign, we take a hash of the message (giving us 256 bits of a hash). We then go through each bit, and if we have a 0, we select the associated private key from A. Otherwise, we select it from B. We then go through the bits and end up with 256 keys, either from A or B. This gives us a 256x256 signature size (8kB). When verifying, we check that each of the hashed values is contained in the public key. This is, of course, a one-time signature, and we would have to create new keys for the next signature and republish our public key. The method is illustrated here [here]:

To improve this, we can define the WOTS+ approach. The method is:

• Initially, we create 32 256-bit random numbers. These 32 values will be our private key.
• We then hash each of these values 256 times. These 32 values will be our public key.
• We now take the message and hash it using SHA-256. This produces 32 8-bit values (N1, N2 … N32).
• For the signature, we take each 8-bit value in the hash of the message, and then hash 256-N times (where N is the value of the 8-bit value).
• To prove the signature, we take the message and hash it with SHA-256, and then take each 8-bit value. We then hash the 8-bit signature value by the number of times defined by the message hash value (N1, N2..). The result of each operation should equal the public key value.

This is illustrated as [here]:

In this way, we cut down the size of the signature and of the public key. We can then produce a Merkle Root of our public key and private key, and reduce them down to a single 256-bit value. We can then create a tree of these keys, so that we can sign more than once and have different private key, but still a single 256-bit private key and a 256-bit public key. This is the method that SPHINCS+ uses, and which has small public and private keys, but has a larger signature (around 17KB for 128-bit security):

Method                   Public key size    Private key size   Signature size  Security level
------------------------------------------------------------------------------------------------------
SPHINCS+ SHA-256 128-bit      32                 64             17,088         1 (128-bit)
SPHINCS+ SHA-256 192-bit      48                 96             35,664         3 (192-bit)
SPHINCS+ SHA-256 256-bit      64                128             49,856         5 (256-bit)

ML-DSA — Fiat Shamir signatures using Zero Knowledge Proofs

Now we will look at the right-hand side, and see that we do not need a trap door any more with our lattice methods for signature generation:

The method for creating the lattice-based signatures is actually based on the Schnorr signature method for proof of identity (a Zero Knowledge Proof) and then applies the Fiat-Shamir method to make it non-interactive. Basically, it’s a NI-ZKP (Non-interactive Zero Knowledge Proof) of a secret (a person’s private key).

If Bob wants to prove that he knows a secret, he creates a short random secret vector (x). He then creates a random matrix array of A, and an error matrix of small errors (e1). His public key (u) is then:

Let’s ignore the error, as it will eventually be removed when we perform the calculations. So let’s just use:

This value will be sent to Alice. She then can send a challenge ( c) to Bob, and which is a random integer value. Bob then creates a random short vector of y, and computes:

Let’s ignore e2 again, as it will eventually be removed. Bob then computes using the Schnorr identity proof:

Bob then sends x and v to Alice, and she checks if these are equal:

If they are, then Bob has proven that he knows the value of x (his private key). This works because:

Now, we can turn a zero-knowledge proof into a signature by using the Fiat-Shamir heuristic. With this, there is no need for Alice to send a challenge, as Bob can compute:

and where M is the message, “||” is a concatenation of the values, and H() is a hash. We can then just perform the same operations, and Alice will be able to regenerate c from the values of the message and v, and check that:

Genius, and no trap doors! [here]