Keywords

1 Introduction

1.1 Background

A signature scheme is a cryptographic public key primitive which guarantees validity of messages. Up until now, many schemes have been proposed such as the ElGamal signature scheme [15], the Schnorr signature scheme [28], and DSA [1].The commonly accepted security notion for a signature scheme is existential unforgeability against chosen message attacks, which guarantees that even if an adversary can obtain signatures on arbitrarymessages of its choice, the adversary cannot forge a valid signature on a new message. The Schnorr signature scheme, and two variants of DSA were proven to satisfy this notion in the random oracle model [25, 26], under the discrete logarithm (DL) assumption.

Related-key attacks (RKA), stronger attacks, were formalized by Bellare and Kohno [5]. RKA security captures security against practical attacks such as tampering or fault injection, which enable adversaries to alter a hardware-stored secret key and observe the output of the algorithm using the modified key. Thus, RKA security captures practical attacks which might cause security issues in practice. Therefore, it is an important question whether primitives are secure against RKA attacks even if they are already shown to be secure against ordinary attacks.

RKA for signature schemes allows an adversary to obtain not only valid message and signature pairs, but also signatures under a modified key. RKA security is defined with respect to the related-key deriving (RKD) functions with which an adversary is allowed to modify the secret key. For example, we consider linear functions, affine functions, and polynomial functions. Since RKA considers a broader class of attacks than ordinary attacks, security against RKA is much stronger than ordinary security.

However, only a few generic constructions for achieving RKA secure signatures have been proposed. Bellare, Cash, and Miller [4] studied relations between RKA secure primitives, and in particular showed that an RKA secure pseudorandom function (PRF) can be used to convert a signature scheme secure against ordinary attacks, into a scheme providing RKA security. The conversion is relatively simple: before generating the verification and signing key, apply the PRF to the randomness used by the key generation algorithm, and then store the randomness instead of the generated signing key. Now, since the signing key of the original scheme is no longer stored, this has to be re-generated whenever a message is signed. This is done by applying the PRF to the stored randomness, and then re-running the key generation algorithm. Bellare, Cash, and Miller [4] showed that, via this conversion, it is possible to lift the RKA security of the PRF to the signature scheme. Used in combination with the recently proposed RKA secure PRF by Abdalla et al. [2], which is shown to be secure under the q-Diffie Hellman Inversion assumption, this allows the conversion of any (ordinary) signature scheme to a scheme which is RKA secure with respect to polynomial functions.

Goyal et al. [21] showed a similar conversion for achieving RKA secure signatures, but based on a correlated-input secure (CIS) hash function. Furthermore, Goyal et al. constructed a very efficient CIS hash function secure under the q-Diffie Hellman Inversion assumption, which would lead to signatures that are RKA secure with respect to polynomials. However, this construction only achieves selective security; a weak and non-adaptive security notion that requires the adversary to submit the RKD functions before seeing the verification key of the signature scheme.

Building upon the work on non-malleable key derivation functions (nm-KDFs) [17], Qin et al. [27] introduced the notion of continuous nm-KDFs, and used these in a similar conversion to the above to construct an RKA secure signature scheme with respect to polynomial functions under standard assumptions. The proposed construction of an nm-KDF can furthermore be extended to provide security with respect to any RKD function class that has the properties the authors denote “high output entropy” and “input-output collision resistant”. Interestingly, the transformation into RKA-secure primitives shown in [12] can be understood as applying an nm-KDF [17, 27] to the secret key.

Since a signature scheme is an essential cryptographic primitive, clarifying the RKA security of various constructions is of interest from both a practical and a theoretical point of view. Specifically, studying the RKA security of well-known signatures such as the Schnorr signature scheme and DSA is important due to their widespread use, in particular in the case of DSA, which is employed in many practical implementations. However, besides the negative result by Bao et al. [3], who showed that the Schnorr signature scheme and DSA are not RKA secure against bit flipping attack, it is not known whether either scheme can provide any form of RKA security. Furthermore, simply applying the above transformations might not always be desirable due to the relatively high performance penalties these conversions imply.

1.2 Our Contributions

In this paper, we first show that both the Schnorr signature scheme and a DSA variant are secure against a weak notion of RKA (wRKA) that does not allow messages queried to the RKA signing oracle to be a part of a forgery. Second, we show that the Schnorr signature scheme and the original DSA are vulnerable to the standard notion of simple linear RKA. We then construct (standard) RKA secure signature schemes based on the Schnorr signature scheme and DSA. Specifically, as our main technical results, we show the following four results:

  • The Schnorr signature scheme is secure against wRKA with respect to polynomial functions.

  • A well-known variant of DSA by [26] is secure against wRKA with respect to polynomial functions.

  • Slightly modifying the signing and verification algorithms of the Schnorr signature scheme yields an RKA secure scheme with respect to polynomial functions.

  • Slightly modifying the signing and verification algorithms of DSA yields an RKA secure scheme with respect to polynomial functions.

In other words, the Schnorr signature scheme, which is secure against wRKA with respect to polynomial functions, but not RKA secure even for weak attacks with respect to linear functions, can achieve full RKA security with respect to polynomial functions by slightly modifying the scheme. While DSA is not RKA secure with respect to linear functions, the DSA variant from [26] is secure against wRKA, and by slightly modifying this scheme, full RKA security with respect to polynomial functions can be achieved. Both the improved Schnorr signature scheme and the improved DSA variant are proven to be RKA secure with respect to polynomial functions in the random oracle model, under the d-strong discrete logarithm (d-SDL) assumption. As a corollary, the improved signature schemes are RKA secure with respect to affine functions under the standard discrete logarithm (DL) assumption, since the 1-SDL assumption is equivalent to the DL assumption, and polynomials of degree 1 are affine functions.

Note that our modifications of the Schnorr signature scheme and DSA only increase the computational cost of signing with a single exponentiation, while the computational cost of verification, signature size, and key sizes remain unchanged. Hence, in contrast to using a conversion based on continuous nm-KDF [17, 27] or RKA secure PRFs [2, 4], our modifications maintain the efficiency of the Schnorr signature scheme and DSA. Furthermore, unlike all of the above mentioned conversions for achieving RKA security, our modifications of the Schnorr signature scheme and DSA do not require the verification and signing key to change. This is a virtue for schemes which are already deployed, such as DSA, since key management and verification key certificates remain unchanged. Lastly, we would like to emphasize that in our proofs of security for our improved Schnorr signature scheme and the improved DSA, we do not restrict the number of RKA signing oracle queries or rely on a “self-destruct” mechanism [16, 17] which prevents the adversary from making any further queries once it is detected that the signing key has been tampered with.

1.3 Related Work

Gennaro et al. [18] show how to recover the key of almost any cryptographic primitive assuming the adversary can tamper arbitrarily with the key of the primitive. This implies that RKA security cannot be achieved for every set of RKD functions. On the other hand, Damgård et al. [11, 12] showed that in a security model which restricts the number of RKA queries that an adversary is allowed to make, it is possible to achieve security for arbitrary RKD functions. In contrast to this model, which is denoted the bounded leakage and tampering model, we will in this paper consider unrestricted adversaries which are allowed to make an arbitrary number of RKA signing oracle queries. Since Dziembowski, Pietrzak, and Wichs introduced non-malleable codes [14], they have been studied and found to have a good application in the construction of RKA secure cryptosystems. While non-malleable codes in themselves are not sufficient to provide full RKA security, continuous non-malleable codes, which were initiated in [16], enables this. However, the security of the constructions presented in [16] relies on a self-destruct mechanism that will prevent an attacker from interacting with the system once it has been detected that the internal state of the systems is being tampered with. In contrast, the continuous nm-KDF proposed by Qin et al. [27] does not require a self-destruct mechanism, and can be used to construct RKA secure public key primitives for a large class of RKD functions. Jafargholi and Wichs [22] defined two factors which yield four levels of security of continuous nm-KDF depending on (I) whether tampering is applied to the original secret key persistently or applied to the changed secret key (classified by “persistent” and “non-persistent”), (II) whether tampering to an invalid codeword causes a “self-destruct” or not. Lastly, Bellare, Cash, and Miller [4] showed how any RKA secure identity-based encryption scheme leads to an RKA secure signature scheme, and Goyal et al. [21] showed that the Boneh-Boyen signature scheme [10] satisfied RKA security with respect to a class of certain polynomial RKD functions.

We note that the signature schemes EdDSA by Bernstein et al. [7] and ECDSA\(^+\) by Koblitz and Menezes [24] resemble our schemes provided in Sects. 5.1 and 6.1, respectively, in the sense that one of the inputs to the hash function is the verification key. However, the schemes in [7, 24] are proposed for a different context and RKA security is not considered.

2 Preliminaries

Here, we review basic notation and definitions of terminology.

2.1 Notation

Throughout the paper, we will use the following notation: For the set of natural numbers \(\mathbb {N}\), let \(\lambda \in \mathbb {N}\) be a security parameter. Let \(\mathbb {G}\) be a group of prime order q, where q is a \(\lambda \)-bit prime. Let g be a generator of \(\mathbb {G}\). Let \(\mathbb {Z}_q^*= \mathbb {Z}_q \setminus \{0\}\). A function \(F:\mathbb {N}\rightarrow \mathbb {R}\) is negligible if it vanishes faster than the inverse of any polynomial. We write \(\Pr [A : B]\) to denote a probability that the predicate A is true after the event B occurred. \(\mathcal {O}(\cdot )\) denotes an order.

2.2 d-Strong Discrete Logarithm Assumption

We recall the d-strong discrete logarithm (d-SDL) assumption introduced by Goyal et al. [21]. Let d be a natural number. The d-SDL problem is to compute x given an input \((g, g^x, g^{x^2}, \dots , g^{x^d})\in \mathbb {G}^{d+1}\), where \(x \overset{\$}{\leftarrow }\mathbb {Z}_q\).

For an adversary \(\mathcal {A}\) that solves the d-SDL problem over \(\mathbb {G}\), we define the advantage as follows:

$$ \mathrm {Adv}_{\mathcal {A}, \mathbb {G}}^{ { d}-sdl }(\lambda ) = \Pr \left[ x^\prime = x : \begin{array}{l} x\overset{\$}{\leftarrow }\mathbb {Z}_q\\ x^\prime \leftarrow \mathcal {A}(g, g^x, g^{x^2}, \dots , g^{x^d}) \end{array} \right] . $$

The d-SDL assumption over \(\mathbb {G}\) says that the advantage \(\mathrm {Adv}_{\mathcal {A}, \mathbb {G}}^{ d-sdl }(\lambda )\) is negligible for any polynomial time algorithm \(\mathcal {A}\).

It is clear that the 1-SDL assumption is equivalent to the standard DL assumption. Similar to the d-Strong Diffie-Hellman problem [10], the d-SDL problem is easier than the standard DL problem. In particular, more efficient solving algorithms, similar to Jao and Yoshida’s algorithm [23] for the d-Strong Diffie-Hellman problem, can likely be constructed for the d-SDL problem.

2.3 Signature

We recall the syntax of signature schemes, introduce functions with respect to which RKA security is considered, and lastly define RKA security for a signature scheme.

Signature Scheme. A signature scheme \(\varSigma \) consists of three algorithms: key generation algorithm, signing algorithm, and verification algorithm. We write

$$ \varSigma =(\text {KeyGen}, \text {Sign}, \text {Verify}), $$

where these algorithms have the following interfaces:

$$\begin{aligned} (sk, vk)&\leftarrow \text {KeyGen}(1^\lambda ),\\ \sigma&\leftarrow \text {Sign}(m, sk),\\ 1/0&\leftarrow \text {Verify}(m, \sigma , vk), \end{aligned}$$

and sk, vk, and \(\sigma \) are a signing key, a verification key and a signature, respectively. For any message m and any key pair (sk, vk) generated by KeyGen, the following correctness should be satisfied:

$$ \text {Verify}(m,\text {Sign}(m, sk), vk) = 1. $$

Related-Key Attack. In the ordinary attack model, an adversary is allowed to obtain signatures on arbitrary messages of its choice. In the RKA model, an adversary is also allowed to modify the signing key and obtain signatures on arbitrary messages of its choice under the modified signing key.

The RKA model, for instance, captures a realistic attack in which an adversary manipulates a hardware-stored secret key by electromagnetic radiation and obtains the outputs of the signing algorithm. This is called tampering or a fault injection attack. RKA is formalized as a security game that also allows an adversary to obtain signatures for modified keys. Thus, an adversary is allowed to query related-key deriving (RKD) functions [5] as well as messages to the signing oracle.

An RKD function is a function \(\phi : K \rightarrow K\), where K is the signing key space. Let \(\varPhi \) be a class of RKD functions. The RKD function class \(\varPhi \) consists of operations by which an adversary is allowed to manipulate a signing key. Normally, \(\varPhi \) is assumed to contain the identity function \(\mathrm {id}\) so that RKA security implies standard EUF-CMA [20]. We assume that it is easy to check whether a function is contained in a class \(\varPhi \), and that RKD functions are efficiently computable.

Following [6], we consider three types of RKD functions: linear functions, affine functions, and polynomial functions. In the following, K is assumed to have an appropriate algebraic structure (group or finite field). In this paper, we will consider signature schemes whose signing key space is \(\mathbb {Z}_q\) with prime q, which constitutes a field, as required.

  • Linear functions. Assume that \((K, *)\) is a group. The class of linear functions is defined as follows: \(\varPhi ^\mathrm{{lin}}=\{\phi _{\varDelta }\mid \varDelta \in K\},\) where \(\phi _{\varDelta }(k)= k *\varDelta \) for a key \(k \in K\). Note that “\(*\)” represents addition or multiplication depending on the group that is considered.

  • Affine functions. Assume that K is a finite field. The class of affine functions is defined as follows: \( \varPhi ^{\text {aff}} =\{\phi _{\alpha , \beta }\mid \alpha , \beta \in K\}, \) where \( \phi _{\alpha , \beta }(k)=\alpha \cdot k + \beta \) for a key \(k \in K\).

  • Polynomial functions. Assume that K is a finite field. The class of polynomial functions is defined as follows: \( \varPhi ^\mathrm{{poly}(d)} =\{\phi _f\mid f \in K_d[x] \}, \) where \(K_d[x]\) is the set of polynomials over K with degree at most d, and \( \phi _f(k)= f(k) \) for a key \(k \in K\).

RKA security is getting stronger and harder to achieve, as it moves from linear functions to affine functions to polynomial functions. In this paper, we only consider such algebraic operations.

\({\varvec{\varPhi }}\) -EUF-CM-RKA [4]. We recall existential unforgeability under chosen message and RKA defined by RKD function class \(\varPhi \). This security of a signature scheme, which we will denote by \(\varPhi \)-EUF-CM-RKA, is formalized by the following game between an adversary \(\mathcal {A}\) and a challenger \(\mathcal {B}\).

  • Initialization. The challenger \(\mathcal {B}\) runs \(\text {KeyGen}(1^\lambda )\) to obtain a signing key sk and a verification key vk. \(\mathcal {B}\) sets a list \(M \leftarrow \emptyset \). Then, \(\mathcal {B}\) gives vk to \(\mathcal {A}\).

  • RKA signing oracle query. For adaptive queries \((m_i, \phi _i)\) by \(\mathcal {A}\), \(\mathcal {B}\) returns the signatures \(\sigma _i\leftarrow \text {Sign}(m_i, \phi _i(sk))\), where \(\phi _i \in \varPhi \). If \(\phi _i(sk)=sk\), \(\mathcal {B}\) records \(m_i\) in the list M.

  • Output. Suppose that \(\mathcal {A}\) outputs \((m^*, \sigma ^*)\). If \(\text {Verify}(m^*, \sigma ^*, vk)=1\) and \(m^*\not \in M\), then \(\mathcal {B}\) outputs 1. Otherwise, \(\mathcal {B}\) outputs 0.

Let F be the event that \(\mathcal {B}\)’s output is 1 in the above game. We define the advantage of \(\mathcal {A}\) against \(\varPhi \)-EUF-CM-RKA security as

$$ \mathrm {Adv}_{\mathcal {A},\varSigma }^{\varPhi -euf-cm-rka }(\lambda ):= \Pr [F]. $$

If the advantage \(\mathrm {Adv}_{\mathcal {A},\varSigma }^{\varPhi -euf-cm-rka }(\lambda )\) is negligible for any probabilistic polynomial time algorithm \(\mathcal {A}\), a signature scheme \(\varSigma \) is said to be \(\varPhi \)-EUF-CM-RKA secure.

We note that the security definition is strong in the sense that the adversary can reuse the message \(m_i\) as the forgery even if \((m_i, \phi _i)\) has been queried to the RKA signing oracle as long as \(\phi _i(sk)\ne sk\).

\({\varvec{\varPhi }}\) -wEUF-CM-RKA. We also consider a weaker variant of the above notion following the traditional weak existential unforgeability against adaptive chosen-message attacks [20] and the weak existential unforgeability of message authentication codes against RKA [8]. By requiring that the adversary in the above security experiment, produces a forgery on a message \(m^*\) which has not previously been submitted to the RKA signing oracle, we obtain the weaker security notion \(\varPhi \)-wEUF-CM-RKA.

Although it can be argued that, in some scenarios, the weaker notion \(\varPhi \)-wEUF-CM-RKA is sufficient to guarantee security, we note that the standard notion used in the literature, corresponds to the stronger notion \(\varPhi \)-EUF-CM-RKA defined above. We will show that the Schnorr signature scheme is \(\varPhi ^\mathrm{{poly}(d)}\)-wEUF-CM-RKA secure, but the scheme is vulnerable with respect to \(\varPhi ^\mathrm{{lin}}\)-EUF-CM-RKA as we demonstrate in Sect. 4.1. The improved Schnorr signature scheme presented in Sect. 5.1 will be proven to be \(\varPhi ^\mathrm{{poly}(d)}\)-EUF-CM-RKA secure. We furthermore show that one of the DSA variants from [26] is \(\varPhi ^\mathrm{{poly}(d)}\)-wEUF-CM-RKA secure, but the original DSA is vulnerable with respect to \(\varPhi ^\mathrm{{lin}}\)-EUF-CM-RKA as we demonstrate in Sect. 4.2. Note that it is not known whether the DSA variant is vulnerable to \(\varPhi ^\mathrm{{poly}(d)}\)-EUF-CM-RKA, but the improved DSA presented in Sect. 6.1 will be proven to be \(\varPhi ^\mathrm{{poly}(d)}\)-EUF-CM-RKA secure. For further details, see Sects. 4, 5, and 6.

We note that, stronger models of RKA security that is often called fault attacks have been considered for round-based symmetric encryption schemes [9, 13, 19]. These models allow the adversary to introduce faults (i.e. modification of the input or the internal state) in the individual rounds of the encryption algorithm, which, for example, lead to recovering a secret key. A similar extension, in which the adversary can choose when in the execution of the signing algorithm it would like to modify the signing key, could be considered for the RKA security of signature schemes. However, in this paper, we focus on the standard RKA notion (and its weaker variant) introduced above.

2.4 Schnorr Signature Scheme

The Schnorr signature scheme was proposed by Schnorr in 1989 [28] and was proven to be secure in the random oracle model based on the discrete logarithm assumption [25]. Recall that \(\mathbb {G}\) is a group of prime order q, and g is a generator. The three algorithms, key generation, signing, and verification algorithms, are defined as follows.

  • KeyGen: This algorithm takes \(1^\lambda \) as input, and generates a signing key sk and a verification key vk as follows.

    1. 1.

      Choose \(x \overset{\$}{\leftarrow }\mathbb {Z}_q\) and let \(y \leftarrow g^x\).

    2. 2.

      Choose a hash function \(H:\{0, 1\}^*\rightarrow \mathbb {Z}_q\).

    3. 3.

      Output \(sk = x, vk = (y, H)\).

  • Sign: This algorithm takes a message \(m\in \{0, 1\}^*\) and the signing key sk as input, and generates a signature \(\sigma \) as follows.

    1. 1.

      Choose \(t \overset{\$}{\leftarrow }\mathbb {Z}_q\) and let \(r\leftarrow g^t\).

    2. 2.

      Let \(h\leftarrow H(m\,\Vert \,r)\).

    3. 3.

      Let \(s\leftarrow x \cdot h+t \mod q\).

    4. 4.

      Output \(\sigma \leftarrow (h,s)\).

  • Verify: This algorithm takes a message m, a signature \(\sigma \), and the verification key vk as input, and verifies the signature as follows.

    1. 1.

      Let \(r^\prime \leftarrow g^sy^{-h}\).

    2. 2.

      Let \(h^\prime \leftarrow H(m \,\Vert \,r^\prime )\).

    3. 3.

      If \(h^\prime = h\), return 1, otherwise return 0.

2.5 DSA

DSA was proposed as the US Digital Signature Standard [1] in 1994. First, we recall the original DSA scheme.

Let p and q be primes, where q is a prime factor of \(p-1\). Let \(g\in \mathbb {Z}_p^*\) be a generator of prime order q. DSA is defined by the following three algorithms:

  • KeyGen: This algorithm takes \(1^\lambda \) as input, and generates a signing key sk and a verification key vk as follows.

    1. 1.

      Choose \(x \overset{\$}{\leftarrow }\mathbb {Z}_q^*\) and let \(y \leftarrow g^x\mod p\).

    2. 2.

      Choose a hash function \(H:\{0, 1\}^*\rightarrow \mathbb {Z}_q\).

    3. 3.

      Output \(sk = x, vk = (y, H)\).

  • Sign: This algorithm takes a message \(m\in \{0, 1\}^*\) and the signing key sk as input, and generates a signature \(\sigma \) as follows.

    1. 1.

      Choose \(t \overset{\$}{\leftarrow }\mathbb {Z}_q^*\) and let \(r \leftarrow (g^t \mod p) \mod q\).

    2. 2.

      Let \(s \leftarrow t^{-1}(H(m) + x\cdot r) \mod q\).

    3. 3.

      Output \(\sigma \leftarrow (r,s)\).

  • Verify: This algorithm takes a message m, a signature \(\sigma =(r, s)\), and the verification key \(vk = (y, H)\) as input, and verifies the signature as follows.

    1. 1.

      Let \(r^\prime \leftarrow (g^{H(m)/s}y^{r/s} \mod p)\mod q\).

    2. 2.

      If \(r^\prime = r\), output 1, otherwise output 0.

Variants of DSA. While the original scheme has not been proven to be secure, Pointcheval and Vaudenay [26] proved that two variants of DSA are secure in the sense of standard security in the random oracle model. The first DSA variant uses one additional random oracle \(H^\prime \), and the first step of signing algorithm computes \(r\leftarrow H^\prime (g^t \mod p)\). The second DSA variant’s main difference is that a hash function takes as input not only a message but also the value r. Looking ahead, we will consider a slight modified version of this second variant of DSA in Sect. 6.

On the Collision Resistance of the DSA Mapping from \(\mathbb {Z}^*_p\) to \(\mathbb {Z}_q\) . Note that in Step 1 of the signing algorithm of DSA, we have to map an element \(g^t \in \mathbb {Z}^*_p\) to an element \(r \in \mathbb {Z}_q\). In [26], Pointcheval and Vaudenay considered this mapping an abstract function from \(\mathbb {G}\) to \(\mathbb {Z}_q\), where \(\mathbb {G}\) is a subgroup of \(\mathbb {Z}^*_p\) of order q. To prove security of their second variant of DSA, Pointcheval and Vaudenay made the assumption that this function has a certain collision resistance property. In this paper, we take a similar approach as [26], and assume this function, which we will denote \(F_{p,q}\), has the following property:

Let \(F_{p,q} : \mathbb {G}\rightarrow \mathbb {Z}_q\) be the mapping defined by \(\overline{g} \mapsto \overline{g} \mod q\), where \(\overline{g} \in \mathbb {G}\), and \(\mathbb {G},q,p\) are the parameters of the group over which DSA is constructed (i.e. \(\mathbb {G}\) is a subgroup of \(\mathbb {Z}_p^*\) of order q). We say that \(F_{p,q}\) is \(\epsilon \)-collision-resistant if no probabilistic polynomial time algorithm \(\mathcal {A}\) can find two distinct elements \(\overline{g}_1, \overline{g}_2 \in \mathbb {G}\) such that \(F_{p,q}(\overline{g}_1) = F_{p,q}(\overline{g}_2)\) with probability more than \(\epsilon \). When \(\epsilon \) is negligible in the security parameter, we simply say that \(F_{p,q}\) is collision resistant.

3 wRKA Security of Signature Schemes

In this section, we show that the Schnorr signature scheme and the second variant of DSA from [26] are \(\varPhi ^{\text {poly}(d)}\)-wEUF-CM-RKA secure. We remind the reader that \(\varPhi ^{\text {poly}(d)}\)-wEUF-CM-RKA security requires that the message \(m^*\) in the forgery must be new and that it has not been submitted to the RKA signing oracle.

First, we show the following theorem regarding the Schnorr signature scheme.

Theorem 1

Let d be a positive integer. Under the d-SDL assumption over \(\mathbb {G}\), the Schnorr signature scheme is \(\varPhi ^{\text {poly}(d)}\)-wEUF-CM-RKA secure in the random oracle model.

More precisely, for any probabilistic polynomial time algorithm \(\mathcal {A}\) with running time \(t_\mathcal {A}\), making \(q_S\) RKA signing oracle queries, and \(q_H\) random oracle queries to H, there exists a probabilistic polynomial time algorithm \(\mathcal {B}\) with running time \(t_\mathcal {B}= 2t_\mathcal {A}+ \mathcal {O}(q_S+q_H)\) that satisfies the following equation:

$$\begin{aligned} \mathrm {Adv}_{\mathcal {A},\varSigma }^{\varPhi ^{\text {poly}(d)} -euf-cm-rka }(\lambda ) \le \left( (q_H+q_S) \left( \mathrm {Adv}_{\mathcal {B}, \mathbb {G}}^{ d-sdl }(\lambda )+\dfrac{2q_S+1}{q}\right) \right) ^{{1}/{2}}. \end{aligned}$$

We leave the proof for the full version of the paper.

Next, we show the following theorem regarding the second DSA variant from [26].

Theorem 2

Let d be a positive integer, and assume the mapping \(F_{p,q}\) is collision resistant. Under the d-SDL assumption over \(\mathbb {G}\), the second DSA variant is \(\varPhi ^{\text {poly}(d)}\)-wEUF-CM-RKA secure in the random oracle model.

More precisely, assume that \(F_{p,q}\) is \(\epsilon \)-collision-resistant. Then, for any probabilistic polynomial time algorithm \(\mathcal {A}\) with running time \(t_\mathcal {A}\), making \(q_S\) RKA signing oracle queries, and \(q_H\) random oracle queries to H, there exists a probabilistic polynomial time algorithm \(\mathcal {B}\) with running time \(t_\mathcal {B}= 2t_\mathcal {A}+ \mathcal {O}(q_S+q_H)\) that satisfies the following equation:

$$\begin{aligned} \mathrm {Adv}_{\mathcal {A},\varSigma }^{\varPhi ^{\text {poly}(d)} -euf-cm-rka }(\lambda ) \le \left( (q_H+q_S) \left( \mathrm {Adv}_{\mathcal {B}, \mathbb {G}}^{ d-sdl }(\lambda )+\dfrac{1}{q}+\dfrac{2\epsilon }{q_H+q_S}\right) \right) ^{{1}/{2}}. \end{aligned}$$

We leave the proof for the full version of the paper.

4 Related-Key Attacks Against Signature Schemes

In this section, we show related-key attacks against the Schnorr signature scheme and DSA. As mentioned in Sect. 2.3, linear functions as RKD functions can be described as addition or multiplication depending on the group used as the signing key space.

4.1 Related-Key Attack Against Schnorr Signature

We show that the Schnorr signature scheme is not RKA secure with respect to linear functions or addition by providing a simple and efficient attack. That is, we show that the Schnorr signature scheme is not \(\varPhi ^\mathrm{lin}\)-EUF-CM-RKA secure.

An adversary \(\mathcal {A}\) forges a signature as follows.

  1. 1.

    Choose an arbitrary message \(m^\prime \in \{0, 1\}^*\) and an arbitrary value \(b\in \mathbb {Z}_q^*\).

  2. 2.

    Query \((m^\prime , \phi (x)=x-b)\) to the RKA signing oracle and obtain the signature \((h^\prime , s^\prime )\) as a response.

  3. 3.

    Output a message \(m^\prime \) and forgery \((h^\prime , s^\prime +b\cdot h^\prime )\).

Now, let us confirm that the forgery is valid. First, the reply from the RKA signing oracle, \((h^\prime , s^\prime )\), must have been computed by the following procedure:

  • Choose \(t^\prime \overset{\$}{\leftarrow }\mathbb {Z}_q\) and let \(r^\prime \leftarrow g^{t^\prime }\).

  • Let \(h^\prime \leftarrow H(m^\prime \,\Vert \,r^\prime )\).

  • Let \(s^\prime \leftarrow (x-b)\cdot h^\prime +t^\prime \mod q\).

The forged signature \((h^\prime , s^\prime +b\cdot h^\prime )\) on the message \(m^\prime \) is verified as follows.

$$\begin{aligned} r^{\prime \prime }&= g^{s^\prime +b\cdot h^\prime }y^{-h^\prime } = g^{(x-b)\cdot h^\prime +t^\prime +b\cdot h^\prime }y^{-h^\prime } = g^{(x-b)\cdot h^\prime +t^\prime +b\cdot h^\prime -x\cdot h^\prime } =g^{t^\prime } =r^\prime . \end{aligned}$$

4.2 Related-Key Attack Against DSA

We next show that DSA is not RKA secure with respect to linear functions or multiplication by providing a simple and efficient attack. That is, we show that DSA is not \(\varPhi ^\mathrm{lin}\)-EUF-CM-RKA secure.

An adversary \(\mathcal {A}\) forges a signature as follows.

  1. 1.

    Choose two distinct messages \(m_0, m_1 \in \{0, 1\}^*\) and let \(z_0 \leftarrow H(m_0), z_1 \leftarrow H(m_1)\).

  2. 2.

    Let \(a \leftarrow \dfrac{z_1}{z_0} \mod q\).

  3. 3.

    Query \((m_1, \phi (x) = ax)\) to the RKA signing oracle and obtain the signature \((r, s=t^{-1}(z_1+axr))\).

  4. 4.

    Output a message \(m^*= m_0\) and the signature \((r^*, s^*) = (r, \dfrac{s}{a} \mod q)\).

Note that even if a is 1, the attack still works.

The forged signature \((r, \dfrac{s}{a} \mod q)\) on the message \(m_0\) will be verified as follows.

First, we compute \(w^*= (s^*)^{-1} = a/s = ta/(z_1 + axr) = ta/(a\cdot z_0 + axr) = t/(z_0 + xr).\) Then, we compute \(u_1 = w^*z_0 \mod q\) and \(u_2 = rw^*\mod q\). Now we can check

$$\begin{aligned} r^\prime&= (g^{H(m_0)/s^*}y^{r^*/s^*} \mod p)\mod q = (g^{u_1} y^{u_2}\mod p)\mod q\\&=(g^{w^*z_0} y^{rw^*}\mod p)\mod q =(g^{w^*z_0 + xrw^*}\mod p)\mod q\\&=(g^{w^*(z_0 + xr)}\mod p)\mod q =(g^t \mod p)\mod q=r. \end{aligned}$$

Thus, the forgery output by \(\mathcal {A}\) is valid.

5 Improved Schnorr Signature Scheme and Its RKA Security

As described in Sect. 4.1, the original Schnorr signature scheme is not RKA secure with respect to linear functions. In this section, we show that a slight modification yields an RKA-secure signature scheme with respect to polynomial functions. We refer to this scheme as the improved Schnorr signature scheme.

5.1 Construction

Our slight modification of the Schnorr signature scheme is as follows. The hash function is modified to take an extra input, which will correspond to a recalculated value of the verification key. Suppose that \(\mathbb {G}\) is a group of prime order q, and g is a generator. The improved Schnorr signature scheme is defined as follows:

  • KeyGen: This algorithm takes \(1^\lambda \) as input, and generates a signing key sk and a verification key vk as follows.

    1. 1.

      Choose \(x \overset{\$}{\leftarrow }\mathbb {Z}_q\) and let \(y \leftarrow g^x\).

    2. 2.

      Choose a hash function \(H:\{0, 1\}^*\rightarrow \mathbb {Z}_q\).

    3. 3.

      Output \(sk = x\) and \(vk = (y, H)\).

  • Sign: This algorithm takes a message \(m\in \{0, 1\}^*\) and the signing key sk as input, and generates a signature \(\sigma \) as follows.

    1. 1.

      Choose \(t \overset{\$}{\leftarrow }\mathbb {Z}_q\) and let \(r \leftarrow g^t\).

    2. 2.

      Let \(\psi \leftarrow g^x\).

    3. 3.

      Obtain \(h\leftarrow H(m\,\Vert \,r\,\Vert \,\psi )\).

    4. 4.

      Let \(s\leftarrow x\cdot h+t \mod q\).

    5. 5.

      Output \(\sigma \leftarrow (h,s)\).

  • Verify: This algorithm takes a message m, a signature \(\sigma \), and the verification key vk as input, and verifies the signature as follows.

    1. 1.

      Let \(r^\prime \leftarrow g^sy^{-h}\).

    2. 2.

      Let \(h^\prime \leftarrow H(m \,\Vert \,r^\prime \,\Vert \,y)\).

    3. 3.

      If \(h^\prime = h\), output 1, otherwise output 0.

Note that the second step of the signing algorithm, computation of \(\psi \leftarrow g^x\), should not be altered to simply use the verification key y as \(\psi \). That is, the signing algorithm computes \(\psi = g^x\) each time it computes a signature.

Given that the verification key is recomputed from the signing key, one might wonder whether RKA security can be achieved simply by comparing the recomputed verification key with the original (assuming that the original verification key is available to the signing algorithm). However, for this to work, the additional assumption that the original verification key is stored and remains unchanged, is required. In the RKA setting, this seems unlikely to hold since the adversary is assumed to be capable of modifying the signing key, which should be better protected than the verification key. Furthermore, if the adversary is capable of modifying the stored signing key, a similar attack to Sects. 4.1 and 4.2 will be possible: an attacker queries \((m^\prime , \phi (x)=x-b)\) under the modified verification key \(yg^{-b}\) in the second step of the attack. In contrast, our schemes provided in this section and in Sect. 6.1 can be shown RKA secure without any additional assumptions regarding stored values.

5.2 Theorem Statement

We prove the following theorem about the improved Schnorr signature scheme.

Theorem 3

Let d be a positive integer. Under the d-SDL assumption over \(\mathbb {G}\), the signature scheme in Sect. 5.1 is \(\varPhi ^{\text {poly}(d)}\)-EUF-CM-RKA secure in the random oracle model.

More precisely, for any probabilistic polynomial time algorithm \(\mathcal {A}\) with running time \(t_\mathcal {A}\), making \(q_S\) RKA signing oracle queries, and \(q_H\) random oracle queries to H, there exists a probabilistic polynomial time algorithm \(\mathcal {B}\) with running time \(t_\mathcal {B}= 2t_\mathcal {A}+ \mathcal {O}(q_S+q_H)\) that satisfies the following equation:

$$\begin{aligned} \mathrm {Adv}_{\mathcal {A},\varSigma }^{\varPhi ^{\text {poly}(d)} -euf-cm-rka }(\lambda ) \le \left( (q_H+q_S) \left( \mathrm {Adv}_{\mathcal {B}, \mathbb {G}}^{ d-sdl }(\lambda )+\dfrac{2q_S+1}{q}\right) \right) ^{{1}/{2}}. \end{aligned}$$
(1)

The proof is given in the full version of the paper.

The 1-SDL assumption is equivalent to the ordinary DL assumption, which leads to the following result.

Corollary 1

The improved Schnorr signature scheme is RKA secure with respect to affine functions in the random oracle model under the DL assumption over \(\mathbb {G}\).

6 Improved DSA and Its RKA Security

As described in Sect. 4.2, the original DSA is not RKA secure with respect to linear functions. In this section, we show that a slight modification yields an RKA-secure signature scheme with respect to polynomial functions. We refer to this scheme as the improved DSA.

6.1 Construction

Based on one of DSA variants (introduced as “second variant” in [26]), we construct an RKA secure variant of DSA with respect to polynomial functions. The slight modification of DSA variant is as follows. The hash function is modified to take an extra input, which will correspond to a recalculated value of the verification key. Suppose that q is a prime, p is a prime such that \(p-1 \mod q=0\), and \(\mathbb {G}\subseteq \mathbb {Z}_p^*\) is a group of prime order q. Let \(g\in \mathbb {G}\) be a generator. Let \(F_{p,q} : \mathbb {G}\rightarrow \mathbb {Z}_q\) be the mapping defined by \(\overline{g} \mapsto \overline{g} \mod q\), where \(\overline{g} \in \mathbb {G}\), and \(\mathbb {G},q,p\) are the parameters of the group.

The improved DSA is defined as follows:

  • KeyGen: This algorithm takes \(1^\lambda \) as input, and generates the signing key sk and the verification key vk as follows.

    1. 1.

      Choose \(x \overset{\$}{\leftarrow }\mathbb {Z}_q^*\) and let \(y\leftarrow g^x\mod p\).

    2. 2.

      Choose a hash function \(H:\{0, 1\}^*\rightarrow \mathbb {Z}_q\).

    3. 3.

      Output \(sk = x\) and \(vk = (y, H)\).

  • Sign: This algorithm takes a message \(m\in \{0, 1\}^*\), the verification key vk, and the signing key sk as input, and generates a signature \(\sigma \) as follows.

    1. 1.

      Choose \(t \overset{\$}{\leftarrow }\mathbb {Z}_q^*\) and let \(r\leftarrow F_{p,q}(g^t \mod p)\).

    2. 2.

      Let \(\psi \leftarrow g^x\mod p\).

    3. 3.

      Let \(s\leftarrow t^{-1}(H(m\,\Vert \,r \,\Vert \,\psi ) + x\cdot r) \mod q\).

    4. 4.

      Output \(\sigma \leftarrow (r,s)\).

  • Verify: This algorithm takes a message m, a signature \(\sigma \), and the verification key vk as input, and verifies the signature as follows.

    1. 1.

      Let \(r^\prime \leftarrow F_{p,q}(g^{H(m\,\Vert \,r\,\Vert \,y)/s}y^{r/s} \mod p)\).

    2. 2.

      If \(r^\prime = r\), output 1, otherwise output 0.

Note that the computation of a hash function at the third step of the signing algorithm takes as input not only a message and the value r, but also \(\psi = g^x\). This computation is different from that of the second DSA variant [26].

6.2 Theorem Statement

We prove the following theorem about the improved DSA.

Theorem 4

Let d be a positive integer, and assume the mapping \(F_{p,q}\) is collision resistant. Under the d-SDL assumption over \(\mathbb {G}\), the signature scheme in Sect. 6.1 is \(\varPhi ^{\text {poly}(d)}\)-EUF-CM-RKA secure in the random oracle model.

More precisely, assume that \(F_{p,q}\) is \(\epsilon \)-collision-resistant. Then, for any probabilistic polynomial time algorithm \(\mathcal {A}\) with running time \(t_\mathcal {A}\), making \(q_S\) RKA signing oracle queries, and \(q_H\) random oracle queries to H, there exists a probabilistic polynomial time algorithm \(\mathcal {B}\) with running time \(t_\mathcal {B}= 2t_\mathcal {A}+ \mathcal {O}(q_S+q_H)\) that satisfies the following equation:

$$\begin{aligned} \mathrm {Adv}_{\mathcal {A},\varSigma }^{\varPhi ^{\text {poly}(d)} -euf-cm-rka }(\lambda ) \le \left( (q_H+q_S) \left( \mathrm {Adv}_{\mathcal {B}, \mathbb {G}}^{ d-sdl }(\lambda )+\dfrac{1}{q}+\dfrac{2\epsilon }{q_H+q_S}\right) \right) ^{{1}/{2}}. \end{aligned}$$
(2)

The proof is given in the full version of the paper.

The 1-SDL assumption is equivalent to the ordinary DL assumption, which leads to the following result.

Corollary 2

If the DL assumption over \(\mathbb {G}\) holds and the function \(F_{p,q}\) is collision-resistant, then the improved DSA is RKA secure with respect to affine functions in the random oracle model.

7 Conclusions

We analyzed the RKA security of the Schnorr signature scheme and DSA. We showed that the Schnorr signature scheme and the second DSA variant from [26] are weak RKA secure with respect to polynomial functions (\(\varPhi ^{\text {poly}(d)}\)-wEUF-CM-RKA), but the Schnorr signature scheme and the original DSA are not fully secure against relatively weak attacks based on linear functions (\(\varPhi ^\mathrm{lin}\)-EUF-CM-RKA). It is not known whether the second DSA variant is vulnerable with respect to \(\varPhi ^{\text {poly}(d)}\)-EUF-CM-RKA. We leave this as an open problem. However, we proved that simple modifications yield schemes, the improved Schnorr signature scheme and the improved DSA scheme, which are RKA secure with respect to polynomial functions (\(\varPhi ^{\text {poly}(d)}\)-EUF-CM-RKA) in the random oracle model. The RKA security with respect to polynomial functions is proven under the d-SDL assumption. Interestingly, considering the case of \(d=1\), our results show that our improved Schnorr scheme and the improved DSA are RKA secure with respect to affine functions in the random oracle model under the ordinary DL assumption. Moreover, our simple modification of the original Schnorr scheme and the considered DSA variant does not require the public or private key from the original schemes to change, and only increases the computational cost of the signing algorithm with a single exponentiation while no other computational cost or the signature size will increase. However, the improved schemes do not address bit-flipping attacks, such as those highlighted by Bao et al. [3]. It remains future work to construct schemes which are provably secure against these attacks.