Keywords

1 Introduction

After the beginning of public-key cryptography [13] many new computational problems were devised, and along with them came cryptographic schemes based on the difficulty of solving those problems. At first, asymptotic security analysis was enough to claim the robustness of a given scheme, but it was realized later that a more precise analysis was required to measure the security of a scheme under a realistic scenario. A security proof is built upon computational complexity theory, using polynomial-time reductions from a well established hard problem to the problem of solving (or breaking) the cryptographic scheme. If this reduction is possible, we can say that breaking the cryptographic scheme is as difficult as solving the well established hard problem (up to a polynomial). If this polynomial is of a high degree, it can degrade the security of the scheme considerably, even rendering it useless for practical applications. Bellare and Rogaway [4] started dealing with security reductions that explicitly stated the polynomial factors involved in those reductions, making it possible to build tight reductions, in which the polynomial is a small constant.

1.1 Hash-then-Sign Signature Schemes

In 1993, Bellare and Rogaway [3] introduced the Full Domain Hash (FDH) signature scheme based on RSA (RSA-FDH), where the message is hashed to the full domain of the underlying trapdoor function before being signed (also known as “hash-then-sign” schemes). The security proof presented in [3] for RSA-FDH was not tight, making the actual scheme potentially impractical for an acceptable level of security. Fortunately, probabilistic FDH (PFDH) schemes, which prepend a short random string to the message, already allow for tight proofs. In particular, Katz and Wang [22] showed that even a single bit of randomness is enough for achieving tight proofs.

Signature schemes that behave deterministically are usually more efficient and easier to implement, what makes them invaluable for practical applications. Moreover, it is a fact that signature schemes secure in the Random Oracle Model (ROM) are much more practical than schemes secure in the standard model [6, 8, 10, 16, 34], therefore, in this paper we only focus on FDH schemes with deterministic signatures in the ROM.

We mainly categorize signature schemes into four distinct classes, namely probabilistic, derandomized, deterministic and unique, that we describe next.

  • Probabilistic schemes utilize randomness during the signing process; signatures are always different (with high probability) even if the same message is signed twice with the same signing key. Some examples of probabilistic schemes are PSS [4], Schnorr [28], El-Gamal [14], and Bitcoin’s ECDSA.

  • Derandomized schemes are probabilistic schemes that demonstrate a deterministic behavior but still requires an internal use of randomness. It is folklore that any randomized signature scheme can be turned into a deterministic one; merely generate the random coins used during the signing algorithm through a pseudo-random function (PRF) that takes the message as input. Then, the random coins used to sign a particular message will be fixed, therefore producing a deterministic signature for each message. Unfortunately, in some cases, the derandomization process can lead to several vulnerabilities [23]. Signature schemes in the derandomized category include the Derandomized Rabin-Williams (DRW) scheme, where the signature is a square root selected uniformly at random out of four possibilities, and returned systematically (by using the PRF “trick”).

  • Deterministic schemes always produce the same signature for each message without relying on randomness (or derandomization) for signing, but the verification algorithm accepts more than 1 valid signature per message (for each key pair).

  • Lastly, unique schemes are deterministic schemes where the verification algorithm only accepts as valid the only signature ever produced by its signing algorithm (for each message and key). Schemes in this category are the Absolute Principal Rabin-Williams (APRW) scheme, and the RSA-FDH (since RSA [27] defines a permutation over \(\mathbb {Z}_n^*\)).

In Table 1 we show a quick comparison between FDH signature schemes.

Table 1. Comparison of different hash-then-sign signature schemes.
Full size table

1.2 Previous Work

A seminal impossibility result by Coron [12] states that any FDH signature scheme with unique signatures could not hope to have a tight security proof. Kakvi and Kiltz [20] clarified that Coron’s impossibility result only holds when the trapdoor permutation is certified. They also presented a tight security proof for RSA-FDH based on the \(\varPhi \)-Hiding assumption [9].

Bernstein [5] studied all variants of Rabin-Williams signatures and devised an ingenious tight proof for the DRW scheme (which he calls “fixed unstructured”), where it releases systematically one of the four square roots that is initially selected at random. Bernstein also provides a non-tight security proof for APRW (the unique signature version of the scheme) and left as an open problem finding a tight proof for it. Seurin [30] first showed that the Rabin function is lossy and then presented a tight security proof for APRW, but under a new assumption dubbed 2-\(\varPhi /4\)-Hiding assumption.

Unique signatures received renewed attention lately, as Bader et al. [2] extended the seminal meta-reduction of Coron [12] by showing that any security proof for unique signatures based on static assumptions or in the security of the underlying trapdoor permutation must lose a factor of \(q_s\) in its security reduction, where \(q_s\) is the number of signature queries asked by the adversary. Later, Guo et al. [18] clarified that the authors of [2] implicitly assumed in their meta-reduction that the simulator is only allowed to extract information from the adversary’s forgeries when trying to invert the underlying trapdoor permutation; [18] circumvents the impossibility of [2] by allowing the simulator (in addition) to extract information from the adversary’s hash queries. In [18] the authors present a unique signature scheme based on Computational Diffie-Hellman (CDH) with a tight security proof, with the drawback that the size of a signature is logarithmic in the number of hash queries asked by the adversary. Shacham [31] improves on the results of [18] and presents a version of the unique scheme of [18] with succinct signatures, where each signature consists of 2 group elements. Unfortunately, the scheme of [31] is still not as fast as RSA-FDH or any Rabin-Williams variant.

Thus, to summarize: All the unique schemes with tight security proofs from the assumption that the underlying trapdoor function (or permutation) is one-way are not efficient. On the other hand, efficient unique schemes such as RSA-FDH and APRW have a tight security proof that relies on the lossiness of the trapdoor function and are based on variants of the \(\varPhi \)-Hiding assumption. Seurin (cf. Theorem 5 in [30]) noted that it is very unlikely that FDH-RSA and APRW will have a tight security reduction from, respectively, inverting RSA or factoring. It is evident that the state of affairs is a bit confusing. FDH-RSA and Rabin-Williams signatures with non-tight proofs were criticized as being potentially impractical due to the large size of the parameters involved. Their tight proofs, however, rely on new assumptions that appear to be markedly stronger than factoring [19, 29]. How should these results be interpreted in practice? Should we trust these new assumptions and keep parameters short or should we use large parameters to account for possible cryptanalytic attacks on these new assumptions?

1.3 State of Affairs

What is wrong with randomness? Generating cryptographically-strong random or pseudo-random numbers (RNG or PRNG) has always been a challenging endeavor. Several devices are even unable to generate random numbers that are good enough for cryptographic purposes. For instance, smart cards and sensors are not usually capable of collecting enough entropy. Some are susceptible to reset attacks where the PRNG is brought back to previous states. A reset attack can be devastating for signature schemes since it could be possible even to recover the signing keys of the user [26]. The same attack can be applied to virtualized systems where the adversary can take snapshots of a virtual machine and later replay them with distinct messages to recover the signing key. When possible, probabilistic schemes should be avoided in these circumstances.

What is wrong with derandomization? Despite showing a deterministic behavior, derandomized schemes still require randomness to sign messages. Therefore, it is crucial to have a sound derandomization process; otherwise, it can be a source of vulnerabilities [17, 23]. For instance, a simple fault attack during the derandomization leads to a full key recovery attack in the derandomized Rabin-Williams scheme (by outputting 2 different square roots of the same message), while deterministic schemes are immune to such attacks.

What is wrong with the \(\varPhi \)-Hiding assumption? The \(\varPhi \)-Hiding assumption appears to be much stronger than factoring, and it does not hold in some cases, as shown in [19, 29]. The RSA-FDH scheme is tightly secure under the \(\varPhi \)-Hiding assumption, while the APRW scheme is tightly secure under a new assumption dubbed 2-\(\varPhi /4\)-Hiding assumption [30]. As reported by Seurin [30], the 2-\(\varPhi /4\)-Hiding assumption is clearly stronger than quadratic residuosity (on which our schemes rely instead): When \(n\equiv 1 \mod 4\), the 2-\(\varPhi /4\)-Hiding problem is equivalent to the problem of establishing whether \(-1\) is a square in \(\mathbb {Z}^*_n\); thus, it’s enough to provide \(y=-x^2\mod n\), for a random \(x\in \mathbb {Z}^*_n\), to a quadratic residuosity solver to violate the 2-\(\varPhi /4\)-Hiding assumption.

A Case for Unique Signatures. Ateniese et al. [1] shows a generic subversion attack against virtually all probabilistic and deterministic signature schemes that leads to the complete recovery of the signing key. The intuition behind the attack is that the adversary builds a subverted signing algorithm that leaks bits of the signing key through the produced signatures; this is only possible because the signature contains randomness that is used to “disguise” the parts of the signing key that is being leaked. Deterministic schemes are also susceptible to such attacks since the bits of the signing key can still be leaked through the choice of the signature that is returned among the possible options. On the other hand, [1] shows that unique signature schemes are secure against the class of subversion attacks that satisfies the verifiability conditionFootnote 1. When used in tandem with a cryptographic reverse firewall [25] unique signature schemes are secure against all classes of subversion attacks [1]. Therefore, unique signatures are recommended for settings where the generation of randomness is problematic, and subversion attacks are a concern.

1.4 Our Contribution

Our contribution is a family of FDH signature schemes in the ROM with tight security proofs to the Quadratic Residuosity (QR) assumptionFootnote 2. The family consists of a unique scheme and a deterministic scheme, both based on a variation of a lossy function from [15]. To argue tight security for the unique signature scheme, we leverage the results of Kakvi and Kiltz [20] that show a generic proof for any unique scheme based on a lossy trapdoor function. As far as we could ascertain, this is the first unique signature scheme tightly secure under the quadratic residuosity assumption (and non-tightly secure under factoring). Besides, the reduction is tighter than the one in [30], i.e., our unique scheme is closer to quadratic residuosity than principal Rabin-Williams is to the 2-\(\varPhi /4\)-Hiding assumption.

The efficiency of the schemes in our family is comparable to that of the Rabin-Williams family, which are considered the fastest (for signature verification) signature schemes ever devised [5]. The unique scheme does require the computation of a Jacobi symbol (as the unique variant of Rabin-Williams also does) but we believe such a computation carries an unfair stigma. In reality, computing Jacobi symbols can be performed very efficiently [24, 32] (in particular in \(O(n^2/\log n)\) as reported in [24]), and can be parallelized [24] to harness recent multicore and/or distributed platforms. Nevertheless, for applications where the verification process has to be even faster, we provide a deterministic signature scheme that does not require the computation of Jacobi symbols.

2 Preliminaries

2.1 Basic Notations

When \(\mathsf {A}\) is a deterministic algorithm, we write \(y := \mathsf {A}(x)\) to denote a run of \(\mathsf {A}\) on input x and output y; if \(\mathsf {A}\) is a randomized algorithm then \(y \leftarrow \mathsf {A}(x;r)\) denotes a run of \(\mathsf {A}\) on input x and randomness r; when it is clear from context we simply write \(y \leftarrow \mathsf {A}(x)\). An algorithm \(\mathsf {A}\) is probabilistic polynomial-time (PPT) if \(\mathsf {A}\) is randomized and for any input \(x,r\in \{0,1\}^*\) the computation of \(\mathsf {A}(x;r)\) terminates in at most \( poly (|x|)\) steps. We denote with \(\kappa \in \mathbb {N}\) the security parameter. A function \(\nu :\mathbb {N}\rightarrow [0,1]\) is negligible in the security parameter (or simply negligible) if it vanishes faster than the inverse of any polynomial in \(\kappa \), i.e., \(\nu (\kappa ) = \kappa ^{-\omega (1)}\). For a random variable \(\mathbf {X}\), we write \({\mathbb P\left[ \mathbf {X} = x\right] }\) for the probability that \(\mathbf {X}\) takes on a particular value \(x\in \mathcal {X}\) (where \(\mathcal {X}\) is the set where \(\mathbf {X}\) is defined).

2.2 Number Theory

We denote by the set of all \(x \in \mathbb {Z}_n^*\) with Jacobi symbol 1, by the set of all \(x \in \mathbb {Z}_n^*\) with Jacobi symbol \(-1\), and by \(\mathbb {QR}_n\) the set of all quadratic residues of \(\mathbb {Z}_n^*\). For \(n \in \mathbb {Z}\), we call n a Williams integer if \(n = pq\) for primes p and q of the form \(p \equiv 3 \mod 8\) and \(q \equiv 7 \mod 8\). Our results rely on the following lemmas from [15, 33].

Lemma 1

Let \(n=pq\) be a Williams integer and let \(x \in \mathbb {QR}_n\). The equation \(x \equiv y^2 \mod n\) takes four distinct values, namely \(\{\pm y_0,\pm y_1\}\), where

  1. (i)

    for \(b\in \{0,1\}\), we have that \(y_b\) and \(-y_b\) are both either in or ,

  2. (ii)

    if and only if .

Lemma 2

Let \(n=pq\) be a Williams integer, then .

Lemma 3

For \(n, x, y \in \mathbb {Z}\), where \(x \not \equiv \pm y \mod n\), if \(x^2 \equiv y^2 \mod n\) then \(\gcd (n, x-y)\) gives a non-trivial factor of n.

2.3 Signature Schemes

A signature scheme is a triple of algorithms \(\varPi = (\mathsf {KGen},\mathsf {Sign}, \mathsf {Vrfy})\) specified as follows:

  • \(\mathsf {KGen}\) takes as input the security parameter \(\kappa \) and outputs a verification/ signing key pair \(( vk ,sk)\in \mathcal {VK}\times \mathcal {SK}\), where \(\mathcal {VK}:= \mathcal {VK}_\kappa \) and \(\mathcal {SK}:= \mathcal {SK}_\kappa \) denote the sets of all verification and secret keys produced by \(\mathsf {KGen}(1^\kappa )\).

  • \(\mathsf {Sign}\) takes as input the signing key \( sk \in \mathcal {SK}\), a message \(m\in \mathcal {M}\) and random coins \(r \in \mathcal {R}\), and outputs a signature \(\sigma \in \varSigma \).

  • \(\mathsf {Vrfy}\) takes as input the verification key \( vk \in \mathcal {VK}\) and a pair \((m,\sigma )\), and outputs a decision bit that equals 1 iff \(\sigma \) is a valid signature for message m under the key \( vk \).

The correctness of a signature scheme informally says that verifying honestly generated signatures always works.

Definition 1

(Correctness). Let \(\varPi = (\mathsf {KGen}, \mathsf {Sign}, \mathsf {Vrfy})\) be a signature scheme. We say that \(\varPi \) satisfies (perfect) correctness if for all \(( vk , sk )\) output by \(\mathsf {KGen}\), and all \(m \in \mathcal {M}\),

$$ {\mathbb P\left[ \mathsf {Vrfy}( vk ,(m,\mathsf {Sign}( sk ,m)))=1\right] } = 1, $$

where the probability is taken over the randomness of the signing algorithm.

The standard notion of security for a signature scheme demands that no PPT adversary given access to a signing oracle returning signatures for arbitrary messages, can forge a signature on a “fresh” message (not asked to the signing oracle).

Definition 2

(Existential unforgeability). Let \(\varPi = (\mathsf {KGen}, \mathsf {Sign}, \mathsf {Vrfy})\) be a signature scheme. We say that \(\varPi \) is \((t,q,\varepsilon )\)-existentially unforgeable under chosen-message attacks if for all adversaries \(\mathsf {A}\) running in time t it holds:

$$ \mathbb {P}\Bigg [\mathsf {Vrfy}( vk ,(m^*,\sigma ^*)) = 1 \wedge m^*\not \in \mathcal {Q}:~\begin{array}{c}( vk , sk )\leftarrow \mathsf {KGen}(1^\kappa );\\ (m^*,\sigma ^*)\leftarrow \mathsf {A}^{\mathsf {Sign}( sk ,\cdot )}( vk )\end{array}\Bigg ] \le \varepsilon , $$

where \(\mathcal {Q}= \{m_1,\ldots ,m_{q}\}\) denotes the set of queries to the signing oracle. If for all \(t,q = poly (\kappa )\) there exists \(\varepsilon (\kappa )= negl (\kappa )\) such that \(\varPi \) is \((t,q,\varepsilon )\)-existentially unforgeable under chosen-message attacks (EUF-CMA for short), then we simply say \(\varPi \) is EUF-CMA.

We define the so-called unique signatures next. Informally, a signature scheme is unique if, for any message, there is only a single signature that verifies w.r.t. an honestly generated verification key.

Definition 3

(Uniqueness). Let \(\varPi \) be a signature scheme. We say that \(\varPi \) satisfies uniqueness if for all \( vk \) output by \(\mathsf {KGen}\), and all \(m \in \mathcal {M}\), there exists a single value \(\sigma \in \varSigma \) such that \(\mathsf {Vrfy}( vk ,(m,\sigma )) = 1\).

3 The Signature Scheme Family

In this section, we describe the two components of our hash-and-sign family of signature schemes. Our family is a variant of the Rabin-Williams family [5], and is inspired by a lossy trapdoor function from [15]. We first describe the unique signature scheme based on QR in Sect. 3.1, followed by the deterministic scheme based on QR in Sect. 3.2.

3.1 Unique Scheme \(\varPi _{\mathsf {u}}\)

Let the functions \(h,j: \mathbb {Z}_n \rightarrow \{0,1\}\) be defined as

We build the unique signature scheme \(\varPi _{\mathsf {u}}= (\mathsf {KGen}, \mathsf {Sign}, \mathsf {Vrfy})\) as follows:

  • \(( vk , sk ) \leftarrow \mathsf {KGen}(1^\kappa )\): The key generation algorithm takes as input the security parameter \(1^\kappa \) and produces a pair of corresponding verification and signing keys. The signing key \( sk \) is composed of two randomly sampled \(\kappa /2\)-bit primes p and q of the form \(p \equiv 3 \mod 8\) and \(q \equiv 7 \mod 8\). The verification key \( vk \) is defined by \(n := p q\) and a randomly sampled parameter .

  • \(\sigma := \mathsf {Sign}( sk , m)\): Set \(b:=0\) and hash the message m to obtain \(x := H(m)\), where \(H: \{0,1\}^* \rightarrow \mathbb {Z}^*_n\) is a collision-resistant hash function. Compute \(x' := x \cdot 2^{j(x)} \mod n\) and iff \(x' \notin \mathbb {QR}_n\) set \(b:=1\) and compute \(x':=x' \cdot s \mod n\) with the public parameter s. Now that \(x'\in \mathbb {QR}_n\) we use the signing key to compute the four modular square roots of \(x'\) and select the single root y such that \(j(y) = j(x)\) and \(h(y) = b\) (according to Lemma 1); set \(\sigma :=y\) and output \(\sigma \).

  • \(b := \mathsf {Vrfy}( vk , m, \sigma )\): If \(\sigma \notin \{1,\dots ,n-1\}\) then output 0, otherwise output \(H(m) = \sigma ^2 \cdot 2^{-j(\sigma )} \cdot s^{-h(\sigma )} \mod n\).

On uniqueness. We note that for a signature scheme to be considered unique, it is necessary, but not sufficient, that the signing algorithm always returns the same signature when the same message is signed more than once. To fully characterize a unique signature scheme, the verification algorithm needs (for each verification key \( vk \)) to reject as invalid all the signatures for a particular message m, except the only signature for m that is ever returned by the signing algorithm. It is easy to see that the scheme \(\varPi _{\mathsf {u}}\) above satisfies these requirements, as for each key a single signature \(\sigma \) is ever produced for some message m, and only \(\sigma \) is ever accepted as a signature for m.

3.2 Deterministic Scheme \(\varPi _{\mathsf {d}}\)

In order to achieve even better efficiency, we construct additionally the deterministic variant \(\varPi _{\mathsf {d}}\) of the previous signature scheme. We define the deterministic scheme \(\varPi _{\mathsf {d}}= (\mathsf {KGen}', \mathsf {Sign}', \mathsf {Vrfy}')\), where the algorithms \(\mathsf {KGen}'\) and \(\mathsf {Sign}'\) are exactly the same as \(\mathsf {KGen}\) and \(\mathsf {Sign}\) in \(\varPi _{\mathsf {u}}\), and the verification algorithm \(\mathsf {Vrfy}'\) is described below:

  • \(b:=\mathsf {Vrfy}'( vk , m, \sigma )\): If \(\sigma \notin \{1,\dots ,n-1\}\) then output 0, otherwise output \((H(m) = \sigma ^2 \cdot s^{-h(\sigma )} \mod n) \vee (H(m) = \sigma ^2 \cdot s^{-h(\sigma )} \cdot 2^{-1} \mod n)\).

Note that although the signing algorithm will always return a unique signature for each message, the verification algorithm does accept 2 different signatures for a message. The main advantage of the deterministic scheme over the unique scheme is efficiency; while the unique scheme requires computation of a Jacobi symbol in the signature verification, the deterministic scheme only needs to perform 3 modular multiplications (in the worst case).

4 Security Analysis

In this section, we analyze the security of the signature schemes presented in Sect. 3. We first present a security proof for \(\varPi _{\mathsf {u}}\) based on the hardness of factoring, and then a tight security proof based on QR. To achieve the latter, we leverage the results of Kakvi and Kiltz [21] on unique signatures based on lossy functions. Later we also present a tight security proof for the \(\varPi _{\mathsf {d}}\) signature scheme based on QR.

4.1 Security of \(\varPi _{\mathsf {u}}\) Based on Factoring

Theorem 1

If the Integer Factorization Problem (IFP) is \((t, \varepsilon )\)-hard, then the unique signature scheme \(\varPi _{\mathsf {u}}\) is \((t^{\prime },q_h, q_s,\varepsilon ^{\prime })\)-secure, with

$$ t = t^{\prime } + (q_h + q_s + 1) \cdot O(\kappa ^2) \quad \text{ and } \quad \varepsilon = \frac{\varepsilon ^{\prime }}{4 \cdot (q_h + q_s +1)}. $$

Proof

Let \(\mathsf {A}\) be an adversary that \((t^{\prime }, q_h, q_s, \varepsilon ^{\prime })\)-breaks \(\varPi _{\mathsf {u}}\). We build a reduction \(\mathsf {R}\) that uses \(\mathsf {A}\) as a subroutine and \((t, \varepsilon )\)-breaks the IFP.

The reduction \(\mathsf {R}\) receives a modulus \(n=pq\) from the challenger, and its objective is to factor n. Instead of sampling , which \(\mathsf {R}\) is not able to, it simply samples an . When \(s \in \mathbb {QR}_n\) the reduction aborts, what happens with probability 1/2. The reduction \(\mathsf {R}\) sends \( vk :=(n,s)\) to \(\mathsf {A}\). We allow the adversary \(\mathsf {A}\) to make two types of oracle queries, namely hash and sign queries, that \(\mathsf {R}\) must answer with the same distribution as a real signing oracle would. The reduction \(\mathsf {R}\) maintains a list \(\mathcal {L}:=\emptyset \) of hash queries and a counter i that is initialized by 0. \(\mathsf {R}\) chooses a random \(\ell \in \{1,...,q\}\), where \(q := q_h+q_s\), and answers the queries as follows:

  • Hash queries: Upon a hash query for message m check if \(m \in \mathcal {L}\); if yes, then return x from the triple \((m,x,y) \in \mathcal {L}\), otherwise proceed as follows. Increment the counter i, and if \(i \ne \ell \) the reduction \(\mathsf {R}\) chooses a random \(y_i \in \mathbb {Z}_n^*\) and sets \(x_i = y_i^2 \cdot 2^{-j(y_i)} \cdot s^{-h(y_i)} \mod n\). However, when \(i=\ell \), reduction \(\mathsf {R}\) chooses random values \(y_i \in \mathbb {Z}_n^*, \alpha , \beta \in \{0, 1\}\) and sets \(x_i = y_i^2 \cdot 2^{-\alpha } \cdot s^{-\beta } \mod n\). Store the triple \((m_i,x_i,y_i)\) in the list \(\mathcal {L}\) and return \(x_i\).

  • Sign queries: When \(\mathsf {A}\) makes a sign query for a message m, reduction \(\mathsf {R}\) checks if there exists a triple \((m,x,y) \in \mathcal {L}\); if not, \(\mathsf {R}\) simply makes the corresponding hash query itself. Return y as the signature of message m.

The adversary \(\mathsf {A}\) eventually outputs a forgery \((m_i, \sigma _i)\), and we assume wlog that \((m_i,x_i,y_i) \in \mathcal {L}\). If \(i=l\) we have that both \(y' = \sigma _i \cdot 2^{-j(\sigma )} \cdot s^{-h(\sigma )} \mod n\) and \(y_i\) are square roots of \(y_i^2\). With probability 1 / 2, the roots \(y'\) and \(y_i\) are not the complement of each other, and in that case we can factor n by computing \(\gcd (n,y' - y_i)\), due to Lemma 3. The running time for \(\mathsf {R}\) is the running time of the adversary \(\mathsf {A}\) plus all the oracle queries. \(\square \)

The reduction \(\mathsf {R}\) is required to answer all the oracle queries that \(\mathsf {A}\) makes; in particular, \(\mathsf {R}\) needs to produce valid signatures to all the messages queried by \(\mathsf {A}\) without knowing the signing key. Before every signature query for message m is made, a corresponding hash query for m needs to be made to the reduction \(\mathsf {R}\); the reduction first samples a random \(y \in \mathbb {Z}^*_n\) and returns \(H(m):=y^2 \cdot 2^{-j(y)} \cdot s^{-h(y)} \mod n\) as the answer to the hash query. To answer a signature query for message m, the reduction \(\mathsf {R}\) returns y as a valid signature for m.

In order to factor, \(\mathsf {R}\) selects an index \(\ell \in \{1, \dots , q\}\) during initialization, and for the \(\ell \)-th hash query made by \(\mathsf {A}\) the reduction \(\mathsf {R}\) replies with \(x_\ell = y_\ell ^2 \cdot 2^{-\alpha } \cdot s^{-\beta } \mod n\) for \(y_\ell \in \mathbb {Z}_n^*, \alpha , \beta \in \{0, 1\}\). The reduction is then able to factor with probability 1/2 if \(\mathsf {A}\) produces a pair \((m_\ell ,\sigma _\ell )\) as a forgery for the message \(m_\ell \).

We note that the above security reduction can be further improved to roughly \(\varepsilon = \varepsilon ^{\prime }/4 q_s\) by applying a technique by Coron [11].

4.2 Tight Security of \(\varPi _{\mathsf {u}}\) Based on QR

The unique signature scheme \(\varPi _{\mathsf {u}}\) of Sect. 3.1 is a variant of a lossy trapdoor function based on QR from [15]. In fact, the changes made to our scheme were carefully crafted so the scheme would still maintain its lossiness; the main difference is that n is a Williams integer so that .

To instantiate the lossy version of our scheme, \(\mathsf {KGen}\) needs to be modified to sample the public parameter \(s \in \mathbb {QR}_n\), in contrast to the injective version, where . Note that the only difference between the lossy and the injective version of the scheme is the domain of s; in both cases , but in the lossy version \(s \in \mathbb {QR}_n\), while in the injective version \(s \notin \mathbb {QR}_n\). Distinguishing among these two cases is precisely the QR assumption, so an adversary that is able to distinguish must solve the QR problem. Since the lossy version of the scheme is 2-to-1 [15] and the injective version is a permutation in \(\{1,\dots ,n\}\), the scheme has lossiness of 1-bit.

For the tight security proof of the scheme \(\varPi _{\mathsf {u}}\) we leverage the generic result of Kakvi and Kiltz [21] for unique signatures based on lossy functions, that intuitively states that any unique signature scheme based on a lossy function has a tight security reduction based on the lossiness of the function. From that, we achieve the following result.

Theorem 2

If the Quadratic Residuosity assumption is \((t_{QR}, \varepsilon _{QR})\)-hard, then for any \(q_h, q_s\) the unique signature scheme \(\varPi _{\mathsf {u}}\) is \((t,q_h,q_s,\varepsilon )\)-EUF-CMA secure in the random oracle model with

$$ t = t_{QR} - q_h \cdot \mathcal {O}(\kappa ^2) \quad \text{ and } \quad \varepsilon = 3 \cdot \varepsilon _{QR}. $$

4.3 Tight Security of \(\varPi _{\mathsf {d}}\) Based on QR

In this section, we build a reduction from breaking the security of the \(\varPi _{\mathsf {d}}\) scheme to breaking the security of the \(\varPi _{\mathsf {u}}\) scheme. Since the \(\varPi _{\mathsf {u}}\) scheme has tight security to the QR problem, then \(\varPi _{\mathsf {d}}\) has also tight security to the QR problem.

Theorem 3

If the \(\varPi _{\mathsf {u}}\) scheme is \((t',q_h,q_s,\varepsilon ')\)-EUF-CMA secure, then the deterministic signature scheme \(\varPi _{\mathsf {d}}\) is \((t,q_h, q_s,\varepsilon )\)-EUF-CMA secure, with \(t = t'\), and \(\varepsilon = 2\cdot \varepsilon '\).

Proof

Assume there exists an adversary \(\mathsf {A}\) that \((t,q_h,q_s,\varepsilon )\)-breaks the security of \(\varPi _{\mathsf {d}}\). Then, we build another adversary \(\mathsf {A}'\) that \((t',q_h, q_s,\varepsilon ')\)-breaks the security of \(\varPi _{\mathsf {u}}\).

\(\underline{\mathrm{Adversary}\, \mathsf {A}'}\):

  • Receive the verification key \( vk :=(n,s)\) from the challenger and send it to \(\mathsf {A}\).

  • Upon any hash or signature query from \(\mathsf {A}\), forward the query to its corresponding oracle and send the reply to \(\mathsf {A}\).

  • Eventually, receive a forgery \((m,\sigma )\) from \(\mathsf {A}\). Sample a random bit b and return the pair \((m,\sigma \cdot 2^b)\) to the challenger as a forgery for message m.

For the analysis, we note that the simulation performed by \(\mathsf {A}'\) is perfect since the hash and signature oracles from both schemes are exactly the same. By assumption, \(\mathsf {A}\) produces a valid forgery \((m,\sigma )\) with non-negligible probability, and in that case, \((m,\sigma \cdot 2^b)\) is a valid forgery for \(\mathsf {A}'\) when \(\sigma \cdot 2^b\) has the same Jacobi symbol as H(m), what happens with probability 1 / 2 when b is sampled at random. Therefore, if \(\mathsf {A}\) breaks the security of \(\varPi _{\mathsf {d}}\) with probability \(\varepsilon \), then \(\mathsf {A}'\) breaks the security of \(\varPi _{\mathsf {u}}\) with probability \(\varepsilon /2\). \(\square \)

5 Performance

When the factors p and q are known, calculating the Jacobi symbol of an element is very efficient since it is enough to compute two Legendre symbols. In particular, for \(x \in \mathbb {Z}_n^*\), if \(x^{(p-1)/2}\mod p = x^{(q-1)/2}\mod q\), otherwise .Footnote 3 The signature \(\sigma \) is the unique square root y of the square x such that \(j(y) = j(x)\) and \(y>n/2\) iff \(x>n/2\). Computing such a square root is very efficient thanks to the Chinese remainder theorem.

In general, when p and q are known, the computation of the Jacobi symbol and a square root share several calculations and can be optimized when performed simultaneously. Since computing Jacobi symbols when p and q are unknown is computationally more expensive than other modular operations, we recommend the deterministic version \(\varPi _{\mathsf {d}}\) of our scheme for applications where unique signatures are not necessary.

While in the unique signature scheme the computation of a Jacobi symbol (for signature verification) is necessary, in the deterministic scheme it is enough to compute \(t:=\sigma ^2\cdot s^{-h(\sigma )} \mod n\) and then check whether any of \(H(m)=t\) or \(H(m)=t\cdot 2^{-1} \mod n\) holds to consider the signature \(\sigma \) as valid.

A note on efficiency. Our \(\varPi _{\mathsf {u}}\) scheme has comparable speed to the unique signature scheme from the Rabin-Williams family, denoted by APRW* in [30]. The running time of the verification algorithm is dominated by the computation of a Jacobi symbol in both schemes. Our deterministic scheme \(\varPi _{\mathsf {d}}\) is very efficient, requiring at most 3 modular multiplications for signature verification.

6 Conclusions

We presented a family of FDH signature schemes with tight security based on a standard assumption (QR). The schemes are as efficient as other variants of Rabin-Williams which hold the record for fastest signature verification schemes  [5]. A tight security proof for the APRW scheme was presented only recently by Seurin [30], and his proof is based on the lossiness of the APRW function, which is based on a new assumption called 2-\(\varPhi /4\)-Hiding, that is a variation of the \(\varPhi \)-Hiding problem [9]. Unlike QR, the \(\varPhi \)-Hiding problem is a new and poorly understood assumption as remarked in [19, 29].

In practice, since the security of our signature scheme is based on the QR assumption, in comparison to RSA-FDH and APRW, it is possible to safely employ smaller parameters for comparable levels of security, which leads to even better efficiency.