More Efficient Digital Signatures with Tight Multi-user Security

Abstract

We construct the currently most efficient signature schemes with tight multi-user security against adaptive corruptions. It is the first generic construction of such schemes, based on lossy identification schemes (Abdalla et al.; JoC 2016), and the first to achieve strong existential unforgeability. It also has significantly more compact signatures than the previously most efficient construction by Gjøsteen and Jager (CRYPTO 2018). When instantiated based on the decisional Diffie–Hellman assumption, a signature consists of only three exponents.

We propose a new variant of the generic construction of signatures from sequential OR-proofs by Abe, Ohkubo, and Suzuki (ASIACRYPT 2002) and Fischlin, Harasser, and Janson (EUROCRYPT 2020). In comparison to Fischlin et al., who focus on constructing signatures in the non-programmable random oracle model (NPROM), we aim to achieve tight security against adaptive corruptions, maximize efficiency, and to directly achieve strong existential unforgeability (also in the NPROM). This yields a slightly different construction and we use slightly different and additional properties of the lossy identification scheme.

Signatures with tight multi-user security against adaptive corruptions are a commonly-used standard building block for tightly-secure authenticated key exchange protocols. We also show how our construction improves the efficiency of all existing tightly-secure AKE protocols.

Supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant agreement 802823.

Appendices

A Proof of Theorem 20

Random Self-reducibility of DDH. It is well-known that the DDH problem is random self-reducible, which we summarize in the following lemma. See [7, Lemma 5.2] for a proof.

Lemma 22

There exists an efficient algorithm $\mathsf {ReRand}$ that takes as input (g, h) and a DDH instance $(u,v) \in \mathbb {G} ^{2}$ and an integer $N$, and outputs $N$ new DDH instances $(u^{(i)},v^{(i)})$ such that

$$ (u,v) \in \mathsf {DDH}(\mathbb {G}, g, h) \iff (u^{(i)},v^{(i)}) \in \mathsf {DDH}(\mathbb {G}, g, h) $$

for all $i \in [N ]$. The running time of this algorithm mainly consists of $\mathcal O(N)$ exponentiations in $\mathbb {G}$.

Proof. To show that $\mathsf {LID}$ is lossy, we need to show that it satisfies all properties presented in Definition 4.

• Completeness of normal keys. We claim that the above scheme is perfectly-complete. To prove this, we show that for any honest transcript it holds that $\mathsf {LID}.\mathsf {Vrfy} ( pk , \mathsf {cmt}, \mathsf {ch}, \mathsf {resp}) = 1$. Let be an (honest) key pair and let $(\mathsf {cmt}, \mathsf {ch}, \mathsf {resp})$ be an honest transcript, that is, , and . By definition of the scheme, we have $pk = (g,h,u,v)$ with $(u,v) \in \mathsf {DDH}(\mathbb {G}, g, h)$ and $sk = x$ and $\mathsf {cmt} = (e,f) = (g^r, h^r)$ and $\mathsf {resp} = r - \mathsf {ch} \cdot x$. Further, $\mathsf {LID}.\mathsf {Vrfy} ( pk , \mathsf {cmt}, \mathsf {ch}, \mathsf {resp}) = 1$ if and only if $e = g^\mathsf {resp} \cdot u^\mathsf {ch}$ and $f = h^\mathsf {resp} \cdot v^\mathsf {ch}$. Observe that

  $$ g^\mathsf {resp} \cdot u^\mathsf {ch} = g^{r - \mathsf {ch} \cdot x} \cdot g^{\mathsf {ch} \cdot x} = g^r = e. $$

  An analogous equation holds for f if g is replaced by h. Hence, $\mathsf {LID}.\mathsf {Vrfy}$ outputs 1 for every honest transcript.

• Simulatability of transcripts. We claim that the above scheme is perfectly simulatable. To show this, we need to argue that the two distributions

  

  and

  

  are identical. Recall that we have $pk = (g,h,u,v)$ with $(u,v) \in \mathsf {DDH}(\mathbb {G}, g, h)$, $sk = x$, $\mathsf {cmt} = (e,f) = (g^r, h^r)$ with , and $\mathsf {resp} = r - \mathsf {ch} \cdot x$ for an honest transcript (i.e., in the former distribution). Thus, we have that $\mathsf {cmt} = (e,f)$ is uniformly distributed over $\mathbb {G} ^2$. Consequently, since and , we also have that the response $\mathsf {resp}$ is distributed uniformly and independently (of $\mathsf {cmt}$ and $\mathsf {ch}$) over $\mathbb {Z} _q$.

  We will now take a look at the later distribution. Note that $\mathsf {ch}$ and $\mathsf {resp}$ are both uniformly random elements over $\mathbb {Z} _p$. It remains to show that $\mathsf {cmt}$ in the simulated transcript is distributed uniformly over $\mathbb {G} ^2$.

  Recall that is defined as . Observe that $\log _g(e) = \mathsf {resp} + \mathsf {ch} \cdot x$ and $\log _g(f) = \log _g(h) \cdot \left( \mathsf {resp} + \mathsf {ch} \cdot x \right)$. Since and , we have that both $\log _g(e)$ and $\log _g(f)$ are distributed uniformly and independently (of $\mathsf {ch}$ and $\mathsf {resp}$) over $\mathbb {Z} _q$ and thus (e, f) is distributed uniformly over $\mathbb {G} ^2$. Note that e, f are not distributed independently of each other (as it is the case in the honest transcript).

• Indistinguishability of keys. As already remarked above, honest keys contain a DDH tuple, whereas lossy keys contain a non-DDH tuple. Therefore, we claim that for every adversary $\mathcal {A}$ trying to distinguish honest from lossy keys of $\mathsf {LID}$, we can construct an adversary $\mathcal {B}$ such that

  

  To prove this claim, we give a construction of $\mathcal {B}$ running $\mathcal {A}$ as a subroutine. The adversary $\mathcal {B}$ receives a tuple (g, h, u, v) such that (u, v) either is a DDH tuple (i.e., $(u,v) \in \mathsf {DDH}(\mathbb {G}, g, h)$) or not. Then, it uses the algorithm of Lemma 22 to re-randomize (u, v) into N tuples such that

  $$ (u,v) \in \mathsf {DDH}(\mathbb {G}, g, h) \iff \forall i \in [N] : (u^{(i)}, v^{(i)}) \in \mathsf {DDH}(\mathbb {G}, g, h) $$

  and hands $( pk _i = (g,h,u^{(i)}, v^{(i)}))_{i \in [N]}$ to $\mathcal {A}$ as input. When $\mathcal {A}$ halts and outputs a bit b, $\mathcal {B}$ halts and outputs b as well. Observe that by Lemma 22, we have

  $$ \Pr [ \mathcal {B} (g,h,u,v) = 1 ] \ge \Pr [ \mathcal {A} ( pk ^{(1)}, \dotsc , pk ^{(N)}) ] $$

  with , , and . Further, we have

  $$ \Pr [ \mathcal {B} (g,h,\bar{u},\bar{v}) = 1 ] \ge \Pr [ \mathcal {A} ( pk '^{(1)}, \dotsc , pk '^{(N)}) ] $$

  with , for every $i \in [N]$, and . In conclusion, we have

  

• Lossiness. We claim that the above scheme $\mathsf {LID}$ is 1/q-lossy. To show this, we first recall a classical result showing the soundness of the protocol to “prove DDH tuples” by Chaum et al. presented above. Namely, we claim that if $\log _g(u) \ne \log _h(v)$ holds for the public key $pk = (g,h,u,v)$ (i.e., $pk$ is a lossy key and $(u,v) \not \in \mathsf {DDH}(\mathbb {G}, g, h)$), for any commitment $\mathsf {cmt}$ there can only be at most one challenge $\mathsf {ch}$ such that the transcript is valid. We prove this statement by contradiction.

  Let $\mathcal {A}$ be an unbounded adversary that on input of a lossy public key , outputs commitment $\mathsf {cmt} = (e,f)$. We now show that $\mathcal {A}$ can only output a correct $\mathsf {resp}$ for one $\mathsf {ch}$ such that $\mathsf {LID}.\mathsf {Vrfy} ( pk , \mathsf {cmt}, \mathsf {ch}, \mathsf {resp}) = 1$. Suppose that $\mathcal {A}$ was able to come up with two responses $\mathsf {resp} _1$ and $\mathsf {resp} _2$ for two different challenge $\mathsf {ch} _1 \ne \mathsf {ch} _2$ such that $\mathsf {LID}.\mathsf {Vrfy} ( pk , \mathsf {cmt}, \mathsf {ch} _1, \mathsf {resp} _1) = 1$ and $\mathsf {LID}.\mathsf {Vrfy} ( pk , \mathsf {cmt}, \mathsf {ch} _2, \mathsf {resp} _2) = 1$ holds. This implies by the definition of $\mathsf {LID}.\mathsf {Vrfy}$ that

  $$ e = g^{\mathsf {resp} _1} u^{\mathsf {ch} _1} = g^{\mathsf {resp} _2} u^{\mathsf {ch} _2} \qquad \text{ and } \qquad f = h^{\mathsf {resp} _1} v^{\mathsf {ch} _1} = h^{\mathsf {resp} _2} v^{\mathsf {ch} _2}. $$

  Equivalently, we get by using the assumption that $\mathsf {ch} _1 \ne \mathsf {ch} _2$:

  $$ \log _g(u) = \frac{(\mathsf {resp} _1 - \mathsf {resp} _2)}{\mathsf {ch} _2 - \mathsf {ch} _1} \qquad \text{ and } \qquad \log _h(v) = \frac{(\mathsf {resp} _1 - \mathsf {resp} _2)}{\mathsf {ch} _2 - \mathsf {ch} _1}. $$

  However, this is a contraction to the assumption that $\log _g(u) \ne \log _h(v)$. Thus, $pk$ must be a lossy key.

  Using this, we have that for every commitment $\mathcal {A}$ outputs, there can only be at most one challenge $\mathsf {ch}$ such that the adversary generated a valid transcript. Note that we have an unbounded adversary and based on $\mathsf {cmt}$ and $\mathsf {ch}$ it can compute a response. As there is only one challenge for $\mathsf {cmt}$ output by $\mathcal {A}$ and the challenge is chosen uniformly at random, the adversary can only win with a probability of at most 1/q.

• Uniqueness with respect to lossy keys. Let $pk = (g,h,u,v)$ with $(u,v) \not \in \mathsf {DDH}(\mathbb {G}, g, h)$ and $(\mathsf {cmt}, \mathsf {ch}, \mathsf {resp})$ with $\mathsf {LID}.\mathsf {Vrfy} ( pk , \mathsf {cmt}, \mathsf {ch}, \mathsf {resp}) = 1$. Suppose that there is a $\mathsf {resp} ' \ne \mathsf {resp}$ such that $\mathsf {LID}.\mathsf {Vrfy} ( pk , \mathsf {cmt}, \mathsf {ch}, \mathsf {resp} ') = 1$. In this case, we have for $\mathsf {cmt} = (e,f)$ that

  $$ e = g^\mathsf {resp} u^\mathsf {ch} = g^{\mathsf {resp} '} u^\mathsf {ch} \qquad \text{ and } \qquad f = h^\mathsf {resp} v^\mathsf {ch} = h^{\mathsf {resp} '} v^\mathsf {ch}. $$

  However, this implies that

  $$ g^\mathsf {resp} = g^{\mathsf {resp} '} \qquad \text{ and } \qquad h^\mathsf {resp} = h^{\mathsf {resp} '}, $$

  which implies that $\mathsf {resp} = \mathsf {resp} '$, contradicting the initial assumption.

• Min-entropy. For any secret key $sk$, the commitment equals $(g^r,h^r)$ for , which is independent of $sk$. So the min-entropy of $\mathsf {cmt}$ is $\alpha =\log _2(q)$.

• Commitment-recoverable. The verification algorithm of $\mathsf {LID}$ first recovers a commitment using the simulator and then compares the result with the commitment in the transcript. So $\mathsf {LID}$ is commitment-recoverable.

• Injective simulator. For any normal public key $pk =(g,h,u,v)$, any response $\mathsf {resp}$ and any challenge $\mathsf {ch} \ne \mathsf {ch} '$, we have that

  $$\begin{aligned} \begin{aligned} \mathsf {LID}.\mathsf {Sim} ( pk , \mathsf {ch}, \mathsf {resp})&= (g^{\mathsf {resp}} u^{\mathsf {ch}}, h^{\mathsf {resp}} v^{\mathsf {ch}}),\\ \mathsf {LID}.\mathsf {Sim} ( pk , \mathsf {ch} ', \mathsf {resp})&= (g^{\mathsf {resp}} u^{\mathsf {ch} '}, h^{\mathsf {resp}} v^{\mathsf {ch} '}). \end{aligned} \end{aligned}$$

  Thus, if the above two pairs are equal, we must have that $(u^{\mathsf {ch}}, v^{\mathsf {ch}}) = (u^{\mathsf {ch} '}, v^{\mathsf {ch} '})$. That implies $\mathsf {ch} = \mathsf {ch} '$.

   $\square$

B Proof of Theorem 21

The following definition is from [1].

Definition 23

(RSA modulus generation algorithm). Let $\ell _N$ be a positive integer and let $\mathsf {RSA}_{\ell _N}$ be the set of all tuples $(N,p_1,p_2)$ such that $N=p_1p_2$ is a $\ell _N$-bit number and $p_1,p_2$ are two distinct primes in the set of $\ell _N/2$-bit primes $\mathbb {P}_{\ell _N/2}$. Let R be any relation on $p_1$ and $p_2$, define $\mathsf {RSA}_{\ell _N}[R]:=\{(N,p_1,p_2)\in \mathsf {RSA}_{\ell _N} \mid R(p_1,p_2)=1\}$.

We can use it to define the n-fold higher residuosity assumption as well as the $\phi$-hiding assumption [1, 9, 31].

Definition 24

(n-fold higher residuosity assumption). Let e be a random prime of length $\ell _e\le \ell _N/4$ and

and let $\mathsf {HR}_{N}[e]:=\{g^e\bmod N \mid g\in \mathbb {Z} _N^*\}$ be the set of e-th residues modulo N. We define the advantage of any $\mathcal {A}$ in solving the higher residuosity problem as

$$ \mathsf {Adv}_{}^{n\text {-}\mathsf {HR}} (\mathcal {A}):=\left| \Pr [\mathcal {A} (N,e,y_{1}, \ldots , y_{n})=1] - \Pr [\mathcal {A} (N,e,y'_{1}, \ldots , y'_{n})=1] \right| , $$

where and . The e-residuosity problem is $(t,\varepsilon )$-hard if for any $\mathcal {A}$ with running time at most t, $\mathsf {Adv}_{}^{n\text {-}\mathsf {HR}} (\mathcal {A})$ is at most $\varepsilon$.

We prove the following lemma.

Lemma 25

For any adversary $\mathcal {A}$ with running time $t_\mathcal {A}$ against the n-key-indistinguishability of $\mathsf {LID}$ in Fig. 2, we can construct an adversary $\mathcal {B}$ with running time $t_{\mathcal {B}}\approx t_\mathcal {A}$ such that

Proof

The proof is a straightforward reduction. $\mathcal {B}$ receives $(N,e,y_{1}, \ldots , y_{n})$ as input and defines the common parameters as (N, e) and

$$ \left( pk ^{(1)},\cdots , pk ^{(n)}\right) =\left( y_{1}, \ldots , y_{n}\right) . $$

Note that this defines real keys if the $y_{i}$ are e-th residues, and lossy keys if the $y_{i}$ are e-th non-residues.    $\square$

Finally, we can show that the n-fold higher residuosity assumption is tightly implied by the $\phi$-hiding assumption, for any polynomially-bounded n.

Definition 26

($\phi$-hiding assumption [1, 9, 31]). Let $c\le 1/4$ be a constant. For any adversary $\mathcal {A}$, define the advantage of $\mathcal {A}$ in solving the $\phi$-hiding problem to be

$$ \mathsf {Adv}_{}^{\phi \text {H}} (\mathcal {A}):=\left| \Pr [\mathcal {A} (N,e)=1] - \Pr [\mathcal {A} (N',e)=1] \right| , $$

where , and . The $\phi$-hiding problem is $(t,\varepsilon )$-hard if for any $\mathcal {A}$ with running time at most t, $\mathsf {Adv}_{}^{\phi \text {H}} (\mathcal {A})$ is at most $\varepsilon$.

Lemma 27

For any adversary $\mathcal {A}$ with running time $t_\mathcal {A}$ we can construct an adversary $\mathcal {B}$ with running time $t_{\mathcal {B}}\approx t_\mathcal {A}$ such that

$$ \mathsf {Adv}_{}^{n\text {-}\mathsf {HR}} (\mathcal {A}) \le 2\cdot \mathsf {Adv}_{}^{\phi \text {H}} (\mathcal {B}). $$

Proof

First, we have that

$$\begin{aligned} \begin{aligned} \mathsf {Adv}_{}^{n\text {-}\mathsf {HR}} (\mathcal {A})&=\left| \Pr [\mathcal {A} (N,e,y_{1}, \ldots , y_{n})=1] - \Pr [\mathcal {A} (N,e,y'_{1}, \ldots , y'_{n})=1] \right| \\&\le \left| \Pr [\mathcal {A} (N,e,y_{1}, \ldots , y_{n})=1] - \Pr [\mathcal {A} (N',e,y'_{1}, \ldots , y'_{n})=1] \right| \\&\quad +\left| \Pr [\mathcal {A} (N',e,y'_{1}, \ldots , y'_{n})=1] - \Pr [\mathcal {A} (N,e,y'_{1}, \ldots , y'_{n})=1] \right| , \end{aligned} \end{aligned}$$

where and . We can prove the following claim.

Claim

$\left| \Pr [\mathcal {A} (N,e,y_{1}, \ldots , y_{n})=1] - \Pr [\mathcal {A} (N',e,y'_{1}, \ldots , y'_{n})=1] \right| \le \mathsf {Adv}_{}^{\phi \text {H}} (\mathcal {B})$.

The proof is again a very straightforward reduction. $\mathcal {B}$ receives as input (N, e). It samples uniformly random and then defines $y_{i} := x_{i}^{e} \bmod N$ for $i \in \{1, \ldots , n\}$. Then it runs $\mathcal {A}$ on input $(N,e,y_{1}, \ldots , y_{n})$ and returns whatever $\mathcal {A}$ returns.

Note that if (N, e) is a “lossy” key, so that $e \mid \phi (N)$, then the $y_{i}$ are random e-th residues. However, if $\gcd (e, \phi (N))=1$, then all $y_{i}$ are random e-th non-residues, since the map $x \mapsto x^{e} \bmod N$ is a permutation.

Using a similar idea, we can prove that

Claim

$\left| \Pr [\mathcal {A} (N',e,y'_{1}, \ldots , y'_{n})=1] - \Pr [\mathcal {A} (N,e,y'_{1}, \ldots , y'_{n})=1] \right| \le \mathsf {Adv}_{}^{\phi \text {H}} (\mathcal {B})$.

Putting the two claims together, we have that $\mathsf {Adv}_{}^{n\text {-}\mathsf {HR}} (\mathcal {A}) \le 2\mathsf {Adv}_{}^{\phi \text {H}} (\mathcal {B})$ and Lemma 27 follows.    $\square$