14 Signature schemes
Besides encryption, signatures are one of the most widely used applications of cryptography, from signing e-mails to authenticating webpage access with HTTPS.
In a signature scheme, we typically have a signature algorithm (Sign) and a verification algorithm (Verify). We input the message \(m\) to Sign and we sign \(m\) using a \(sk\), producing a signature \(\sigma\). Then, \(\sigma\) and \(m\) are sent to Verify, that uses the public key \(pk\) to output 0 or 1 to indicate whether the signature was accepted. Our goal is to build a signature scheme so that if you know \(sk\), you can produce a valid signature (i.e. Verify outputs 1), otherwise you cannot. Some common signature schemes are RSA, the digital signal algorithms (DSA), and elliptic curve DSA (ECDSA), all of which can be broken by Shor’s algorithm.
We will study two post-quantum approaches to building a signature scheme, namely applying the Fiat-Shamir transform to an identification-scheme, and hash-based signatures.
14.1 Identification-Schemes
Identification-schemes (or ID-schemes, for short) allow users to identify themselves, for example when logging into an account. We also require that the server cannot impersonate the user after login. Important differences from signatures are that ID-schemes can be interactive, and that no message is aythenticated. ID-schemes can be of a specific form, called \(\Sigma\)-protocols, schematized below. There are two agents in this protocol, a Prover (\(P\)) and a Verifier (\(V\)). \(P\) uses a randomized algorithm to produce an initial message called “commitment” and sends it to \(V\); replies with another message, the “challenge”, drawn from a uniformly random distribution over the challenge space \(\mathcal{C}\); finally \(P\) sends back a “response” message to \(V\), who accepts or rejects the whole interaction by applying a deterministic function to the three messages and the public key.
We will demonstrate these properties using a weakly sound modular LWE (MLWE) based ID-scheme (notation, especially the ring of polynomials \(R_q\), is as discussed when we looked at Kyber/ML-KEM):
KeyGen:Define \(\mathcal{C}\) as a set of small values in \(R_q\). The protocol works as follows:
Verify then checks if \(z\) is small, and if the difference \(Az-cb\approx w\).
Let’s first check if this protocol has the desired properties. Since \(y\), \(c\), and \(s\) are all small, then \(z\) is small. Moreover, \(Az-cb-w=Ay+cAs-cAs-ce-Ay+e'=-ce-e'\) is also small, so Verify accepts with high probability and the protocol has correctness. This protocol does not have zero-knowledge, so it does not have soundness either. We will now show that it has weak soundness at least.
We claim that the MLWE protocol is \((t,\epsilon)\)-weakly sound (for some \(\epsilon\) to be determined in the proof).
: Assume \(P^*\) is \(\delta\)-successful malicious \(t\)-time prover with \(\delta>\epsilon\). Consider the following program \(E\):
We have:
\[\begin{align} \Pr[\textrm{ok}_1 = 1\wedge \textrm{ok}_2 = 1] & \geq \delta^2 \label{eq:14.1} \\ \Pr[\textrm{ok}_1 = 1\wedge \textrm{ok}_2 = 1 \wedge c_1\neq c_2] & \geq \delta^2-\frac{1}{\lvert\mathcal{C}\rvert} \label{eq:14.2} \end{align}\]
(Note: \(\ref{eq:14.1}\) does not follow trivially from \(\Pr[\textrm{ok}_1=1]\geq\delta\), \(\Pr[\textrm{ok}_2=1]\geq\delta\), one needs to consider that \(\textrm{ok}_1\), \(\textrm{ok}_2\) are not stochastically independent.) If this hapens then:
That is, if there is a \(\delta\)-successful \(t\)-time \(P^*\), then there exists an algorithm with runtime \(\approx 2t\) that finds \(\hat{z}, \hat{c}\) with \(\hat{z}, \hat{c}\) small and \(\hat{c}\neq 0\) and \(A\hat{z}\approx\hat{c}b\) with probability \(\delta^2-\frac{1}{\lvert\mathcal{C}\rvert}\).
Could an algorithm do this efficiently? Let \(D:=\begin{bmatrix}A & b\end{bmatrix}\) and \(f = \begin{bmatrix}\hat{z}\\ -\hat{c}\end{bmatrix}\), so that \(Df=A\hat{z}-\hat{c}b\approx 0\). Since \(b\) ``looks random” by the MLWE assumption, \(D\) looks random, and we have that \(f\) is small and \(f\neq0\), so we found a small \(f\neq 0\) with \(Df\approx 0\), contradicting the MSIS assumption. Therefore, \(E\) breaks MLWE or MSIS with probability \(\approx \delta^2+\frac{1}{\lvert\mathcal{C}\rvert}\), which is a contradiction for suitable \(\epsilon\).
The property that one gets ``forbidden value” from two interactions with different challenges but same commitment is called “special soundness”, we study this some more in Chapter 16.
Note that the rewinding technique as used above does not work for quantum \(P^*\). We cannot make a memory snapshot since we cannot copy quantum data in general (no-cloning theorem). In some cases, instead of copying, we could do a reverse computation. That is the case if the computation of the response is implemented by a unitary \(U^{P^*}_c\) that depends on the challenge \(c\), so that applying \((U^{P^*}_c)^\dagger\) brings it back to the state before the computation. Whether this works requires careful analysis to account for effects of measurements in between. If it does, then the probability of finding valid \((w,c_1,z_1)\) and \((w,c_2,z_2)\) is \(\geq\delta^3\). We will look at this more in Chapter 16.
14.2 Fiat-Shamir transform
The Fiat-Shamir transform takes an ID-scheme and produces a signature scheme.
We begin with the \(\Sigma\)-scheme from before and we will try to make it non-interactive. Our first approach could be to make sender run both \(P\) and \(V\), and send (\(com,ch,resp\)) as the signature. This, however, is insecure, as nothing forces a malicious sender to honestly run the interaction. For example, sender could pick \(ch\) first, then find a \(com\) so that this makes it easy to find a \(resp\). Therefore, we need some way to produce \(ch\) such that:We can solve this by making \(ch:=H(com)\) for some sufficiently good hash function \(H\). Then the sender outputs \((com, ch, resp)\) and the recipient checks that \(\textrm{Verify}(pk,com,ch,resp)=1\) and that \(ch=H(com)\). It is possible to prove that a prover cannot produce a \((com,ch,resp)\) triple accepting those conditions if the prover cannot succeed in authenticating in an ID-scheme.
The problem is that we have not included the message to be signed. We want our scheme to produce a separate triple for each message \(m\). This can be done by setting \(ch:=H(com,m)\) and making Verify additionally check that this is the case. The resulting scheme is schematized below:
With that, we can define the Fiat-Shamir transform:
We can build then apply the Fiat-Shamir transform to one toy \(\Sigma\)-protocol and get a signature scheme:
14.3 Security definition of signatures
For a signature scheme to be secure, we want that:
- Adversary cannot produce valid \(\sigma^*\) for message \(m^*\) that adversary picked
- This should hold even if adversary sees signatures \(\sigma\) of other messages \(m\neq m^*\) for messages that the adversary picked (“chosen message attack”).
This motivates the definition below: