Post Quantum Cryptography (PQC) Signatures Without Trapdoors
William J. Buchanan · 2025
Read Post Quantum Cryptography (PQC) Signatures Without Trapdoors by William J. Buchanan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-14016.txt.
Introduction
William Buchanan surveys post-quantum cryptography signatures without trapdoors in a 2025 paper. Many current signature schemes rest on a trapdoor, a secret shortcut that could one day be exposed or broken.
RSA signatures, for instance, lean on a classic number theorem to build that shortcut. Quantum-era methods aim to drop trapdoors and gain stronger security proofs. Two families lead: hash-based signatures, as in SPHINCS+, and Fiat-Shamir signatures built on zero knowledge proofs, as in Dilithium. Both avoid hidden back routes by design. The paper explains how each works and why trapdoor-free design matters for long-term trust in digital signatures.
Catalog record
| CREATOR | William J. Buchanan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 8 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-14016
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Post Quantum Cryptography (PQC) Signatures Without Trapdoors William J. Buchanan Abstract Some of our current public key methods use a trap door to implement digital signature methods. This includes the RSA method, which uses Fermat’s little theorem to support the creation and verification of a digital signature. The problem with a back-door is that the actual trap-door method could, in the end, be discovered. With the rise of PQC (Post Quantum Cryptography), we will see a range of methods that will not use trap doors and provide stronger proof of security. In this case, we use hash-based signatures (as used with SPHINCS+) and Fiat Shamir signatures using Zero Knowledge Proofs (as used with Dilithium). 1 Introduction Some of our existing public key methods, such as RSA, use a trapdoor method to produce a digital signature. 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. Our new post-quantum cryptography methods avoid the trapdoor technique and focus on more difficult problems. For quantum robust signatures which do not use trap doors, there are two main methods: lattice approaches with the Fiat-Shamir method [ 1 ] for a non-interactive approach. For PQC (Post Quantum Cryptography, NIST has standardised the hash-based methods as SLH-DSA (FIPS 205, aka SPHINCS+ [ 2 ] ), and the Fiat-Shamir approach with ML-DSA (FIPS 204, aka CRYSTALS Dilithium [ 3 ] . 2 A trap door method First, let’s look at a trap door method. We generate the RSA key pair with two prime numbers ( p and q ), and compute the modulus ( N ) [ 4 ] : \displaystyle N=pq (1) We then compute: \displaystyle\phi=(p-1).(q-1) (2) We then pick an encryption key value ( e=0x010001 ) and compute: \displaystyle d=e^{-1}\pmod{\phi} (3) The public key is then (e,N) and the private key is (d,N) . To sign the hash of a message ( H ), we create a signature with: \displaystyle S=H^{d}\pmod{N} (4) and then verify with: \displaystyle H=S^{d}\pmod{N} (5) This all works because of Little Fermat’s Theorem, and which is defined as: \displaystyle a^{p-1}\equiv 1\pmod{p} (6) 3 Hash-based signatures We can create a one-time signature using the Lamport approach [ 5 ] . With this, we generate 256 private keys for A and 256 private keys for B [ 6 ] . 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 (8 kB). 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 (Figure 1 ). To improve this, we can define the WOTS+ (Winternitz one-time signature scheme) approach [ 7 , 8 ] . The method is (Figure 2 ): • 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 ( N_{1} , N_{2} … N_{32} ). • 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 ( N_{1} , N_{2} ..). The result for each operation should equal the public key value. • 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). 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): Table 1: SPHINCS+ key and cipher sizes 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) Figure 1: Lamport one-time signatures Figure 2: WOTS+ one-time signatures 4 Fiat Shamir signatures using Zero Knowledge Proofs The method for creating the lattice-based signatures is actually based on the Schnorr signature method [ 9 ] for proof of identity (a Zero Knowledge Proof) and then applies the Fiat-Shamir method [ 1 ] to make it non-interactive. Basically, it is 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 ( e_{1} ). His public key ( textbf{u} ) is then: \displaystyle u=\textbf{A}.x+e_{1} (7) Let’s ignore the error, as it will eventually be removed when we perform the calculations. So let’s just use: \displaystyle u=\textbf{A}.x (8) 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: \displaystyle v=\textbf{A}.y+e_{2} (9) Let’s ignore e_{2} again, as it will eventually be removed. Bob then computes using the Schnorr identity proof: \displaystyle z=c.x+y (10) Bob then sends x and v to Alice, and she checks if these are equal: \displaystyle\textbf{A}.z=c.\textbf{u}+\textbf{v} (11) If they are, then Bob has proven that he knows the value of x (his private key). This works because: \displaystyle\textbf{A}.z=\textbf{A}(c.x+y)=\textbf{A}.c.x+\textbf{A}.y (12) \displaystyle c.\textbf{u}+\textbf{v}=c.\textbf{A}.x+\textbf{A}.y (13) 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: \displaystyle c=\textrm{H}(v||M) (14) and where M is the message, “——”