Double-authentication-preventing signatures in the standard model 1

Abstract

A double-authentication preventing signature (DAPS) scheme is a digital signature scheme equipped with a self-enforcement mechanism. Messages consist of an address and a payload component, and a signer is penalized if she signs two messages with the same addresses but different payloads. The penalty is the disclosure of the signer’s signing key. Most of the existing DAPS schemes are proved secure in the random oracle model (ROM), while the efficient ones in the standard model only support address spaces of polynomial size.

We present DAPS schemes that are efficient, secure in the standard model under standard assumptions and support large address spaces. Our main construction builds on vector commitments (VC) and double-trapdoor chameleon hash functions (DCH). We also provide a DAPS realization from Groth–Sahai (GS) proofs that builds on a generic construction by Derler et al., which they instantiate in the ROM. The GS-based construction, while less efficient than our main one, shows that a general yet efficient instantiation of DAPS in the standard model is possible.

An interesting feature of our main construction is that it can be easily modified to guarantee security even in the most challenging setting where no trusted setup is provided. To the best of our knowledge, ours seems to be the first construction achieving this in the standard model.

Keywords

Digital signature double-spending self-enforcement chameleon hash function

1. Introduction

Digital signatures (DS) are a cryptographic primitive that guarantees authenticity and integrity. Security is defined via the notion of unforgeability, which protects the signer (and the verifier in the sens of non-repudiation), but there is no notion of a signer behaving badly. There are however applications in which the signer should be restricted; for example, a certificate authority should not certify two different public keys for the same domain.

Double-authentication-prevention signatures (DAPS) are a natural extension of digital signatures that prevent malicious behavior of the signer by a self-enforcement strategy. A message for DAPS consists of two parts, called the address and payload i.e., $m = (a, p)$ . A signer behaves maliciously if it signs two messages with the same addresses but different payloads, that is, $m_{1} = (a_{1}, p_{1})$ and $m_{2} = (a_{2}, p_{2})$ with $a_{1} = a_{2}$ and $p_{1} \neq p_{2}$ . Such a pair $(m_{1}, m_{2})$ is called compromising, and the signer is penalized for signing a compromising pair by having its signing key revealed. We next discuss typical applications of DAPS.

Certificate subversion. Consider a certificate authority (CA) issuing certificates to different severs. A certificate is of the form $(server.com, {pk}_{s}, σ_{s})$ , where server.com is the domain, ${pk}_{s}$ is the server’s public key and $σ_{s}$ is a signature on $(server . c o m, {pk}_{s})$ by the CA. Entities that trust the CA’s public key can now securely communicate with server.com by using ${pk}_{s}$ . Consider a national state court that has jurisdiction over the CA and compels it to issue a rogue certificate for server.com for a public key under the control of an intelligence agency. The latter can then impersonate server.com without its clients detecting the attack. Using DAPS for certification gives the CA a strong argument to deny the order, as otherwise its key is leaked. It leads to an all-or-nothing situation where if one certificate has been subverted then all have (as once the key is revealed, everything can be signed).

Cryptocurrencies and non-equivocation contracts. In cryptographic e-cash systems (a.k.a. “Chaumian” e-cash), double-spending is prevented by revealing the identity of the misbehaving party [13]. This works well in systems where some central authority (e.g. a bank) can take concrete actions to penalize dishonest behaviors (such as blocking their accounts). In the setting of “cryptocurrencies”, disclosing the identity of users is much harder to implement because of the decentralized nature of these systems, and indeed double-spending is typically prevented by consensus. Transactions are considered effective only after a certain amount of time. This naturally prevents double-spending but induces delays to reach agreement. Using DAPS to sign transactions could provide a strong deterrent to malicious behaviors. Double-spenders would disclose their secret signing keys, which, for the case of Bitcoin, could translate to a financial loss.

Translating to the DAPS setting, the address would be the coin and the payload the receiver when spending it. For cryptocurrencies it is natural to implement this mechanism via DAPS, as digital signatures are already needed to authenticate transactions.

Concretely, one can make non-equivocation contracts (i.e. contracts that allow penalizing parties that make conflicting statements to others, by the loss of money) by combining a DAPS scheme and a deposit. To ensure that an extracted DAPS secret key is a worthy secret, it can be associated to a deposit. Each party is required to put aside a certain amount of currency in a deposit which can be securely retrieved by the owner at the end of a time-locked session if the owner has not made conflicting statements during the session. Otherwise, anyone obtaining the extracted secret key also has access to the funds.

Moreover, by finding the secret key a user can give a fraud-proof against a malicious signer (by getting the access to its deposit) without revealing any information about its claim (as others may also want to copy its claim).

Whether the solutions based on DAPS are effective for the real world problems still has remained to be seen, but the idea itself is interesting from the cryptographic point of view.

1.1. Challenges in constructing DAPS

We next discuss some general challenges in constructing DAPS regarding their security, efficiency and functionality. Our aim is to construct a scheme that achieves a good balance among them.

Exponentially large address space. The address part of a message for DAPS typically refers to a user/coin identity. Only allowing a polynomial number of predefined identities [17,28] severely limits the possible applications, while an exponential number of addresses practically amounts to no restrictions, as one can use a collision-resistant hash function to map into the address space.

Security when no trusted setup is provided. DAPS schemes should satisfy two security notions. Unforgeability ensures that signatures from an honest signer (who does not sign compromising message pairs) are secure against an outside attacker. Key extractability requires that issuing signatures on compromising message pairs leaks the signer’s signing key; the notion can be defined with respect to a trusted or untrusted setup. The former assumes that the signer generates its own key material honestly (or by a trusted party) while the latter notion allows for malicious behavior.

The majority of existing DAPS constructions assume a trusted setup [3,17,28,29]. Those that do not are in the random oracle model [30] or have polynomial-size signatures (w.r.t. the length of the address) [6] or only support small address spaces [17,28].

Standard assumptions. While giving reductionist security proofs is the preferred method of gaining trust in a cryptosystem, these guarantees are only meaningful if the underlying hardness assumptions have been well-studied. Moreover, such analyses often rely on idealizations like assuming hash functions are random functions (in the ROM). Our schemes are proven secure from very well-studied assumptions (e.g. RSA, CDH) and we do not make idealizing assumptions in our proofs, i.e., they are in the standard model.

The challenge of realizing DAPS, in the standard model and based on simple assumption, mainly is due to the key extractability property. One may wonder if it is not possible to convert a usual signature scheme to a DAPS. In particular, discrete logarithm based constructions might seem good candidates to also realize key extractability (i.e., beyond unforgeability). Indeed this idea is followed in some DAPS constructions in ROM (e.g., [3] which can be seen as a DAPS version of Schnorr signature) but it seems hard to implement it in the standard model. Beyond the obvious difficulty that no single, stateless, scheme directly relying on the discrete logarithm assumption is currently known [26], another (more subtle) issue comes from the fact that, to prove the key extractability, one should be able to extract the secret key without controlling in any way the public key material. Let us clarify this point more in detail. A typical approach when proving the security of a cryptographic scheme consists in constructing a simulator that given some hard to solve mathematical problem P should be able to turn successful attacks to the scheme into solutions to P. A key aspect of this methodology is that the simulator is allowed to create the (public) key material so to embed the hard problem P into the scheme it wants to prove its security. Such a possibility however is precluded when proving the key extractability as, here, the adversary is the signer itself. This makes standard approaches for proving the security of signatures much harder to implement in the context of DAPS.

Efficient/concrete instantiations. Some prior DAPS schemes [16] that claim short signatures or achieve some of the above properties are black-box constructions from building blocks whose instantiation is often left open. This can be a non-trivial task and leaves the concrete efficiency of such schemes unclear.

1.2. Our contribution

In this paper we present new DAPS constructions that address all of the above challenges. Our main contributions are as follows.

1.2.1. Exponentially large address spaces without random oracles

We circumvent many of the difficulties arising in previous works by presenting our DAPS-VC-DCH scheme which combings the vector commitments (VC) [11,24] and double-trapdoor chameleon hash functions (DCH) [8,10]. Our methodology follows the authentication tree approach also adopted in previous work (e.g. [30]): a signature is an authenticated path from a leaf (whose position is the address part of the message) to a given root (the public key).

In previous work, the signer either had to create the whole tree in advance (thus forcing the address space to be polynomial-size) or use the random oracle to be able to deal with exponentially large address spaces. In our construction the signer creates the tree incrementally using the equivocation properties of the chameleon hash. Moreover, we prove our schemes secure by relying on the double-trapdoor property: the simulator will be able to issue signatures by knowing only one of the two trapdoors. If an adversary manages to create a forgery (or if it signs a compromising pair), our reduction uses this information to extract the other trapdoor with non-negligible probability. We moreover use vector commitments [11] to realize a “flat” authentication tree (i.e. a tree with branching degree $q > 2$ ). Since both vector commitments [11] and double-trapdoor chameleon hash [8,10] (see also our DCH scheme in Section 4) can be realized under standard assumptions, the security of our schemes relies on the same assumptions (w.r.t. the trusted setup for the VC scheme).

1.2.2. Security without trusted setup

Interestingly, our construction can be easily adapted to the setting where no trusted setup is available. This comes at the cost of longer signatures and is in contrast to previous proposals that all rely on trusted setup (or random oracles). The basic intuition here is that double-trapdoor chameleon hash functions can be realized in the untrusted setup setting (we present a candidate construction in Section 4), and substituting the vector commitments with a standard collision-resistant hash function, the construction highlighted above still works. The downside is that the produced signatures are now longer, as more values have to be stored in the authentication chain. Very informally this is because, replacing Vector Commitments with collision-resistant hash functions, leads to a binary (rather than “flat”) authentication tree.

We remark that the DCH schemes originally suggested in [8,10] implicitly assume trusted setup. Here we present a DCH scheme that does not need a trusted setup. While our proposed DCH scheme was informally suggested in [10] (Section 3.1 of the full version), here we present a concrete construction and prove its security for the general setting where no trusted setup is available.

1.2.3. A more general definition

We also propose a slightly more general (with respect to previous work) definition of key-extractability that, we believe, could be useful in other contexts as well. Our definition introduces a predicate ${Comp}_{vk} (\cdot)$ that indicates evidence that the signer misbehaved. Slightly more in detail, the predicate aims at formalizing the fact that, from a compromising pair of signed messages, it may be possible to extract some sensitive information ${sk}^{'}$ (not necessarily the full signing key $sk$ ) that is compatible with the verification key, i.e. ${Comp}_{vk} ({sk}^{'}) = 1$ . In order for this formalization to be any useful we also require that producing an ${sk}^{'}$ such that ${Comp}_{vk} ({sk}^{'}) = 1$ is hard (without a compromising pair of signed messages).

1.2.4. A Groth–Sahai-based construction

As additional contribution of this paper we propose a DAPS construction from Groth Sahai proofs [20] (DAPS-GS), which builds upon a construction proposed by Derler et al. [16]. The latter scheme, which we will refer to as DAPS-DRS, supports an exponentially large address space and is based on NIZK proofs which is reminiscent of the technique used in compact e-cash to trace double-spenders [9]. The authors instantiated their construction in the random oracle model (ROM). We modify their construction so that the NIZK proof system can be instantiated with the Groth–Sahai proof system [20]. This system provides efficient NIZK proofs in the standard model and under standard assumptions (for a restricted class of languages).

An interesting difference between our DAPS-GS scheme and DAPS-DRS is that the latter uses a fixed-value key-binding PRF. We assign this task to a commitment scheme and can therefore relax the requirements on the PRF to standard PRF security. The authors of DAPS-DRS instantiate their key-value binding PRF F with the block cipher LowMC [1]. They thus need to make the (arguably non-standard) assumption that this block cipher is a fixed-value key-binding PRF. The commonality of our DAPS schemes (DAPS-VC-DCH and DAPS-GS) is that they are both in the standard model and support large address spaces. In fact, we instantiate the generic construction of [16] by Groth–Sahai NIZK proof system (as DAPS-GS) to provide a standard-model scheme and compare it against our main, more efficient, DAPS-VC-DCH (DAPS-DCH).

As a final note, we remark that our solutions compare favorably to previous work not only in terms of security guarantees, but also in terms of efficiency. Our most efficient construction (for a large address space) based on vector commitments also provides nice trade-offs between the size of its signatures and the size of its verification keys: verification keys grow with the branching degree q of the underlying authentication tree, while signatures grow with the depth h of the tree. A more precise comparison with previous works is given in Table 1.

Table 1
Comparison to prior work. Here n is the bit length of the address, written as $n = h \cdot log q$ for integers h and q; values $n_{0}$ and $q_{0} = poly (n_{0})$ are LWE parameters, and $ℓ_{π} (n)$ denotes the proof size in the underlying NIZK system for statements of length n. Finally, $| G |$ stands for the size of group elements, and p comes from the order of the group $Z_{p}$ , $λ_{H}$ is the bit length of the random oracle/hash function output, and N is an RSA modulus

Scheme Signature size $vk$ size Address space Assumption ROM No trusted setup

Poet18 [28] $| G |$ $O (2^{n})$ poly. DLog yes no

RKS15 [30] $q \cdot h \cdot | G |$ $O (1)$ exp. DLog yes yes

PS14 [29] $(λ_{H} + 1) \cdot log N$ $O (1)$ exp. Fact yes no

BPS17 [3] $log N$ $O (1)$ exp. Fact yes no

BKN17 [6] $O (n_{0}^{2} log q_{0})$ $O (n_{0}^{4} {log}^{3} q_{0})$ exp. LWE/SIS yes yes

DRS18a [17] $ℓ_{π} (n)$ $O (2^{n})$ poly. DLog yes yes

LGWCT19 [23] $log N$ or $2 \cdot | G |$ $O (1)$ exp. Fact or CDH yes yes

DRS18b [16] $ℓ_{π} (n)$ $O (1)$ exp. PRF & OWF yes yes

DAPS-GS $(38 n + 114) \cdot | G |$ $O (1)$ exp. SXDH no no

DAPS-VC-DCH $h \cdot (2 | G | + log p)$ $q^{2}$ exp. CDH no no

DAPS-DCH $h \cdot ((q - 1) λ_{H} + log p)$ $O (1)$ exp. DLog no yes

Scheme	Signature size	$vk$ size	Address space	Assumption	ROM	No trusted setup
Poet18 [28]	$\| G \|$	$O (2^{n})$	poly.	DLog	yes	no
RKS15 [30]	$q \cdot h \cdot \| G \|$	$O (1)$	exp.	DLog	yes	yes
PS14 [29]	$(λ_{H} + 1) \cdot log N$	$O (1)$	exp.	Fact	yes	no
BPS17 [3]	$log N$	$O (1)$	exp.	Fact	yes	no
BKN17 [6]	$O (n_{0}^{2} log q_{0})$	$O (n_{0}^{4} {log}^{3} q_{0})$	exp.	LWE/SIS	yes	yes
DRS18a [17]	$ℓ_{π} (n)$	$O (2^{n})$	poly.	DLog	yes	yes
LGWCT19 [23]	$log N$ or $2 \cdot \| G \|$	$O (1)$	exp.	Fact or CDH	yes	yes
DRS18b [16]	$ℓ_{π} (n)$	$O (1)$	exp.	PRF & OWF	yes	yes
DAPS-GS	$(38 n + 114) \cdot \| G \|$	$O (1)$	exp.	SXDH	no	no
DAPS-VC-DCH	$h \cdot (2 \| G \| + log p)$	$q^{2}$	exp.	CDH	no	no
DAPS-DCH	$h \cdot ((q - 1) λ_{H} + log p)$	$O (1)$	exp.	DLog	no	yes

1.3. Related work

Ruffing, Kate, and Schröder [30] present a DAPS scheme based on Merkle trees and chameleon hash functions in the random oracle model. Their scheme supports an exponentially large address space by using a flat-tree construction. They associate each leaf with a unique address and some values are assigned on the fly to nodes from a leaf to the root. A signature is an authentication chain. This flat-tree construction and the idea of assigning values on the fly has also been used in other constructions [12,14].

Poettering [28] gives a DAPS scheme based on a three-move identification scheme in the ROM. The scheme only supports small address spaces, essentially because each address is associated with a verification key.

Bellare, Poettering and Stebila [3] propose a similar solution but managed to avoid the restriction to small address spaces by introducing a trapdoor-ID scheme. Their solution still relies on random oracles and requires a trusted setup.

Poettering and Stebila [29] present a DAPS based on extractable 2-to-1 trapdoor functions (2:1-TF) in the ROM. A 2:1-TF is a trapdoor one-way function for which every element of the range has precisely two preimages and holding the trapdoor allows to efficiently invert the function. Again, the scheme requires a trusted setup and the ROM.

Other schemes in the random oracle model are those of Boneh, Kim, and Nikolaenko [6] and Gao et al. [23].

Derler, Ramacher, and Slamanig [16] present a generic DAPS construction from non-interactive zero-knowledge (NIZK) proof systems that supports an exponentially large address space. They instantiate the construction in the ROM using the Fiat–Shamir transformation [18].

NIZK proofs in the common reference string (CRS) model rely on a trusted setup, and so does any DAPS construction based on NIZK.

2. Preliminaries

Notation. We denote the security parameter by $κ \in N$ and $x \leftarrow X$ means that element x is chosen uniformly at random from a set X. If A is a probabilistic algorithm, $y \leftarrow A (x_{1}, x_{2}, \dots)$ denotes running A on input $x_{1}, x_{2}, \dots$ , and assigning its output to y. An algorithm is $p . p . t .$ if it runs in probabilistic polynomial-time ( $p . p . t .$ ). We denote concatenation by $| |$ and the set ${1, \dots, n}$ by $[n]$ . We say $f (κ)$ is negligible, and write $f (κ) = negl (κ)$ , if for every positive polynomial $p (κ)$ there exists $κ_{0} \in N$ such that for all $κ > κ_{0}$ : $f (κ) < 1 / p (κ)$ .

2.1. Computational assumptions

Here we present the computational assumptions used in the paper. In the following, let $G = (G, p, g)$ be the description of a cyclic group $G$ of prime order p with the generator g.

Definition 2.1 (Discrete Logarithm Assumption (DL)).

The DL assumption states that given $G$ and $g^{a}$ , it is hard to find a when a is chosen uniformly at random. More precisely, for any $p . p . t .$ adversary $A$ , there is a negligible function negl such that: $\begin{matrix} Pr [a \leftarrow A (G, g^{a}) : a \overset{_{R}}{\leftarrow} Z_{p}] ⩽ negl (κ) \end{matrix}$

Definition 2.2 (Decisional Diffie–Hellman Assumption (DDH).

The DDH assumption states that given $G, g^{a}, g^{b}$ , it is hard to distinguish $g^{a b}$ from a random group element, for a and b chosen uniformly at random. More precisely, for any $p . p . t .$ adversary $A$ , there is a negligible function negl such that: $\begin{matrix} | Pr [A (G, g^{a}, g^{b}, g^{a b}) = 1 : a, b \overset{_{R}}{\leftarrow} Z_{p}] - Pr [A (G, g^{a}, g^{b}, g^{r}) = 1 : a, b, r \overset{_{R}}{\leftarrow} Z_{p}] | ⩽ negl (κ) \end{matrix}$

Definition 2.3 (Computational Diffie–Hellman Assumption (CDH)).

The CDH assumption states that given $G, g^{a}, g^{b}$ , it is hard to compute $g^{a b}$ , for a and b chosen uniformly at random. More precisely, for any $p . p . t .$ adversary $A$ , there is a negligible function negl such that: $\begin{matrix} Pr [g^{a b} \leftarrow A (G, g^{a}, g^{b}) : a, b \overset{_{R}}{\leftarrow} Z_{p}] ⩽ negl (κ) \end{matrix}$

Definition 2.4 (Advanced Computational Diffie–Hellman problem (CDH+)).

Let $G = (G_{1}, G_{2}, p, g_{1}, g_{2})$ be the description of two cyclic groups $G_{1}, G_{2}$ of prime order p with the generator $g_{1}$ and $g_{2}$ respectively, the CDH+ assumption states that given $G, g_{1}^{a}, g_{2}^{a}, g_{1}^{b}$ , it is hard to compute $g_{1}^{a b}$ , for a and b chosen uniformly at random. More precisely, for any $p . p . t .$ adversary $A$ , there is a negligible function negl such that: $\begin{matrix} Pr [g_{1}^{a b} \leftarrow A (G, g_{1}^{a}, g_{2}^{a}, g_{1}^{b}) : a, b \overset{_{R}}{\leftarrow} Z_{p}] ⩽ negl (κ) \end{matrix}$

2.2. Digital signatures

A digital signature (DS) scheme is defined as follows. Later, we present its DAPS variant which prevents signing the compromising messages in a cryptographic way.

Definition 2.5 (Digital signature scheme).

A digital signature scheme Σ consists of $p . p . t .$ algorithms $(KeyGen, Sign, Verif)$ where

$KeyGen (1^{κ})$ , on input the security parameter κ in unary, outputs a signing key $sk$ and a verification key $vk$ (which implicitly defines the message space $M$ ).

$Sign (sk, m)$ , on input signing key $sk$ and message $m \in M$ , outputs a signature σ.

$Verif (vk, m, σ)$ , on input verification key $vk$ , message $m \in M$ and signature σ, outputs either 0 or 1.

Correctness. Signature scheme Σ is correct if for all $κ \in N$ , for all $(sk, vk) \leftarrow KeyGen (1^{κ})$ , for all $m \in M$ , and $σ \leftarrow Sign (sk, m)$ , we have $Verif (vk, m, σ) = 1$ .

2.3. Double-authentication-preventing signatures

Double-authentication-preventing signature (DAPS) schemes are a subclass of digital signatures where the message to be signed is split into two parts; an address and a payload,2

²
In [29] these two parts are referred as subject and message, and in [30] as context and statement. Here we follow the terminology from [28].

i.e., in Definition 2.5 we have

m = (a, p) \in U \times P

Informally, compromising messages are (signed) pairs of messages with the same addresses but different payloads.

Definition 2.6 (Compromising pair of signatures [29]).

For a verification key $vk$ , a pair $(S_{1}, S_{2})$ where $S_{1} = (a_{1}, p_{1}; σ_{1})$ and $S_{2} = (a_{2}, p_{2}; σ_{2})$ , is compromising if $\begin{matrix} Verif (vk, (a_{1}, p_{1}), σ_{1}) = 1, Verif (vk, (a_{2}, p_{2}), σ_{2}) = 1, a_{1} = a_{2} and p_{1} \neq p_{2} . \end{matrix}$

A key property of DAPS schemes is key-extractability (KE). It requires that no malicious signer can produce a compromising pair of signatures which does not lead to the revelation of a signing key that is compatible with its verification key. To make the definition more general, we allow the adversary to succeed even when it manages to produce compromising messages that do not reveal sensitive information about the secret key (and not necessarily the whole secret key).

This is captured via the $Comp$ predicate that, informally, outputs 1 if the input is compatible with the public verification key. The exact meaning of this “compatible” depends on the specific application, but clearly for any $(sk, vk) \leftarrow KeyGen (1^{κ})$ it should be the case that $1 \leftarrow {Comp}_{vk} (sk)$ . For example, we will see that in our scheme the extracted secret key is compatible with the public key, if the secret key is the discrete logarithm of one of the public-key elements. If ${Comp}_{vk} (\cdot) = 1$ is constant, we have nothing more than an ordinary signature without any prevention. The main requirement here is that producing ${sk}^{'}$ such that ${Comp}_{vk} ({sk}^{'}) = 1$ must be hard without a compromising pair of signed messages.

Definition 2.7 (Key-extractability [29]).

A DAPS scheme is key-extractable w.r.t to the predicate $Comp$ , if there exists a $p . p . t .$ algorithm $Ext$ as follows:

$Ext (vk, S_{1}, S_{2})$ , on input a verification key $vk$ and a compromising pair $(S_{1}, S_{2})$ , outputs a signing key ${sk}^{'}$ ,

such that

Pr [{KExt}_{DAPS, A} (κ) = 1] ⩽ negl (κ)

for all

p . p . t .

adversaries

A

, where experiment

{KExt}_{DAPS, A} (κ)

is as described in Fig. 1.

Fig. 1.

Game for key-extractability of DAPS.

We say that a DAPS scheme is KE for trusted setups if this holds for the experiment ${KExt}_{DAPS, A}^{Tr}$ , and it is KE without trusted setup if it holds for ${KExt}_{DAPS, A}^{nTr}$ .

Since DAPS schemes are a subclass of digital signatures, the standard existential unforgeability (Definition A.1) should also be satisfied for a DAPS scheme. This requires a restriction though, as the adversary could obtain the signing key if it was allowed to query compromising pairs to its signing oracle.

Fig. 2.

Game for EUF-CMA security of DAPS.

Definition 2.8 (Unforgeability of DAPS).

A DAPS scheme Σ is existentially unforgeable under adaptive chosen-message attacks (EUF-CMA) if for all $p . p . t .$ adversaries $A$ , we have $Pr [{Forg}_{DAPS}^{A} (κ) = 1] ⩽ negl (κ)$ , where ${Forg}_{DAPS}^{A} (κ)$ is as described in Fig. 2.

2.4. Vector commitments

A vector commitment (VC) is a primitive allowing one to commit to an ordered sequence of q values, rather than to single messages [11,24]. One can later open the commitment at a specific position.

Definition 2.9 (Vector commitments [11,24]).

A VC scheme is a tuple of $p . p . t .$ algorithms $VC = (Setup, Cmt, Open, Verif)$ where

$Setup (1^{κ}, q)$ , on input the security parameter κ and the length q of committed vectors (with $q = p o l y (k)$ ), outputs public parameters $pp$ (which defines the message space $M$ ).

${Cmt}_{pp} (m_{0}, \dots, m_{q - 1})$ , on input a sequence of q messages $m_{0}, \dots, m_{q - 1} \in M$ , outputs a commitment string C.

${Open}_{pp} (m_{0}, \dots, m_{q - 1}, m, i)$ produces a proof $Λ_{i}$ that m is the i-th committed message in the sequence $m_{0}, \dots, m_{q - 1}$ .

${Verif}_{pp} (C, m, i, Λ_{i})$ outputs 1 if $Λ_{i}$ is a valid proof that C commits to a sequence $m_{0}, \dots, m_{q - 1}$ with $m = m_{i}$ , and 0 otherwise

Definition 2.10 (Correctness of VC).

A $VC$ is correct if for all $κ \in N$ and $q = poly (κ)$ , all $pp \leftarrow Setup (1^{κ}, q)$ and all vectors $(m_{0}, \dots, m_{q - 1}) \in M^{q}$ , we have $\begin{matrix} Pr [\begin{matrix} C \leftarrow {Cmt}_{pp} (m_{0}, \dots, m_{q - 1}) \\ Λ_{i} \leftarrow {Open}_{pp} (m_{i}, i) \end{matrix} : {Verif}_{pp} (C, m_{i}, i, Λ_{i}) = 1] = 1 . \end{matrix}$

The security notion for a VC scheme is called position-binding and requires that for any $p . p . t .$ adversary, given $pp$ , it should be infeasible to produce a commitment C and openings to two different messages for the same position. Note that while some applications may require the VC scheme to hide the message (hiding-property), we do not need such property in our scheme.

Definition 2.11 (Position-binding).

A VC scheme $VC$ is position-binding if for all $i \in {0, \dots, q - 1}$ and $p . p . t .$ adversaries $A$ we have $Pr [{PBind}_{VC}^{A} (κ) = 1] ⩽ negl (κ)$ , where game ${PBind}_{VC}^{A} (κ)$ is as defined in Fig. 3.

Finally, a VC scheme is concise if the size of the commitment string C and the output of algorithm

Open

are both independent of q.

Fig. 3.

Game for position-binding of a VC scheme.

2.5. Double-trapdoor chameleon hash functions

A chameleon hash function is a (collision-resistant) hash function, where given a trapdoor one can find collisions efficiently. A double-trapdoor chameleon hash (DCH) function scheme has two independent such trapdoors.

Definition 2.12 (DC hash function [10]).

A DCH scheme $H$ is a tuple of $p . p . t .$ algorithms $H = (KeyGen, TrChos, CHash, Coll)$ where

$KeyGen (1^{κ})$ , on input the security parameter κ, outputs a public key $pk$ (which implicitly defines the message space $M$ ) and private keys ${tk}_{0}$ and ${tk}_{1}$ .

$TrChos (1^{κ}, i)$ , on input the security parameter κ and a bit i, outputs a pair of public/private keys $(pk, {tk}_{i})$ .

${CHash}_{pk} (m, r)$ , on input the public key $pk$ , a message $m \in M$ and one (or more) random nonce $r \in R$ , outputs a hash value.

$Coll (pk, {tk}_{i}, m^{'}, m, r)$ , on input one of the two trapdoor keys ${tk}_{i}$ , two different messages $m, m^{'}$ and a nonce r, outputs a nonce $r^{'}$ such that ${CHash}_{pk} (m, r) = {CHash}_{pk} (m^{'}, r^{'})$ .

In the definition of algorithm $Coll$ , the pair $(m, r)$ and $(m^{'}, r^{'})$ is called a collision pair where ${CHash}_{pk} (m, r) = {CHash}_{pk} (m^{'}, r^{'})$ . For a DCH scheme, the following security requirements were given [10].

Definition 2.13 (Security of DCH).

We require double-trapdoor chameleon hash functions to satisfy the following properties: Distribution of keys.

The output of $TrChos (1^{κ}, i)$ is distributed like a public key $pk$ and the i-th private key ${tk}_{i}$ output by $KeyGen (1^{κ})$ .3

³
This property alongside the definition of $Coll$ algorithm essentially means having only one of the trapdoors is enough to simulate signature queries in the security game.

Double-trapdoor collision-resistance (DTCR).

Let $(pk, {tk}_{0}, {tk}_{1})$ be output by $KeyGen (1^{κ})$ . For all $i = 0, 1$ , given $pk$ and ${tk}_{i}$ it is infeasible to find ${tk}_{1 - i}$ . Formally, for all $p . p . t .$ adversary $A$ , we have $Pr [{DTCR}_{DCH}^{A} (κ) = 1] ⩽ negl (κ)$ , where game ${DTCR}_{DCH}^{A}$ is defined in Fig. 4.

Fig. 4.

Collision-resistance game for a DCH scheme.

Key-extractability (KE) (w.r.t. predicate

Comp (\cdot)

) .

There exists a $p . p . t .$ algorithm $Ext$ as follows:

$Ext (pk, S_{1}, S_{2})$ , on input the public key $pk$ and a collision pair $(S_{1}, S_{2})$ , outputs a (single) secret key ${tk}^{'}$ ,

such that

Pr [{KExt}_{DCH, A} (κ) = 1] ⩽ negl (κ)

for all

p . p . t .

adversaries

A

, with game

{KExt}_{DCH, A} (κ)

as defined in Fig. 5.

Fig. 5.

KE game for a DCH scheme. The left game is in the trusted setup and the right game is in the untrusted setup.

Fig. 6.

Game for the distribution of collisions.

Uniformity.

For r chosen uniformly at random in $R$ , all messages m induce the same probability distribution on ${CHash}_{pk} (m, r)$ . This implies that ${CHash}_{pk} (m, r)$ for randomly chosen r information-theoretically hides m. As for standard chameleon hash functions [22] this can be relaxed to computational indistinguishability of the above distributions for any two messages.

Distribution of collisions.

For every $m, m^{'}$ , and a uniformly random r, the distributions of $r^{'} = Coll ({tk}_{i}, m, m^{'}, r)$ are identical (uniform) for $i = 0, 1$ , even when given ${CHash}_{pk} (m, r)$ , m and $m^{'}$ . More precisely, for any adversary $A$ we have, $Pr [{Dis}_{DCH}^{A} (κ) = 1] = 1 / 2$ where the experiment ${Dis}_{DCH}^{A}$ is defined in Fig. 6. This also can be relaxed to its computational variant.

Remark 2.1 (On defining Key Extractability).

Our definitions above of Key Extractability implicitly assume that some appropriate predicate $Comp$ is always associated with a DCH. This might seem surprising at first as, for DCH, $Comp$ is formally required only for the untrusted setup setting. However, even if one only cares about the trusted setup setting, we require the underlying $DCH$ to have an associated predicate $Comp$ , which lets us define Key Extractability for DAPS.

We thus assume, unless otherwise stated, that every $DCH$ has an efficiently computable predicate $Comp$ , so that for any $κ \in N$ and any $(pk, {tk}_{0}, {tk}_{1})$ output by $KeyGen (1^{κ})$ we have ${Comp}_{pk} ({tk}_{0}) = {Comp}_{pk} ({tk}_{1}) = 1$ and ${Comp}_{pk} ({tk}^{'}) = 0$ for any ${tk}^{'} \notin {{tk}_{0}, {tk}_{1}}$ .

2.6. Non-interactive zero-knowledge proofs

Let $L = {x | \exists w : R (x, w) = 1}$ be a language in NP. A non-interactive zero knowledge (NIZK) proof system for L is formally defined as follows.

Definition 2.14 (NIZK proof system [5]).

A NIZK proof system Π for the language L consists of three $p . p . t .$ algorithms $(Setup, Prove, Verif)$ where

$Setup (1^{κ})$ takes the security parameter κ as input and outputs a common reference string $crs$ .

$Prove (crs, x, w)$ , takes the $crs$ , a statement x and a witness w as input and outputs a proof π.

$Verif (crs, x, π)$ takes the $crs$ , the statement x, and a proof π as input and outputs either 0 or 1.

Security Requirements for NIZK Proof System. Let $Π = (Setup, Prove, Verif)$ be a NIZK proof system for the language $L = {x | \exists w : R (x, w) = 1}$ . For Π, the following security requirements are defined [19].

Definition 2.15 (Perfect Completeness).

For all adversaries $A$ whose output $(x, w)$ satisfies $R (x, w) = 1$ we have $\begin{array}{l} Pr [\begin{matrix} crs \leftarrow Setup (1^{κ}); (x, w) \leftarrow A (crs) \\ π \leftarrow Prove (crs, x, w) \end{matrix} : Verif (crs, x, π) = 1] = 1 \end{array}$

Definition 2.16 (Perfect Soundness).

For all adversaries $A$ we have $\begin{matrix} Pr [crs \leftarrow Setup (1^{κ}); (x, π) \leftarrow A (crs) : Verif (crs, x, π) = 1 \land x \notin L] = 0 . \end{matrix}$ This can be relaxed to its computational version.4

⁴
If $A$ is $p . p . t .$ , we call the system as the “Argument System”, while it is called “Proof System” for an unbounded $A$ .

Definition 2.17 (Perfect knowledge-soundness).

Π is a proof of knowledge for relation R, if there exists a knowledge extractor $E = (E_{1}, E_{2})$ such that for all adversaries $D$ and $A$ we have $\begin{array}{l} Pr [crs \leftarrow Setup (1^{κ}) : D (crs) = 1] = Pr [(crs, ξ) \leftarrow E_{1} (1^{κ}) : D (crs) = 1] \\ and Pr [\begin{matrix} (crs, ξ) \leftarrow E_{1} (1^{κ}) \\ (x, π) \leftarrow A (crs) \\ w \leftarrow E_{2} (crs, ξ, x, π) \end{matrix} : \begin{matrix} Verif (crs, x, π) = 0 \\ \lor R (x, w) = 1 \end{matrix}] = 1 . \end{array}$

Definition 2.18 (Composable Zero-Knowledge).

Π is composable zero-knowledge if there exists a simulator $(S_{1}, S_{2})$ such that for all $p . p . t .$ adversaries $D$ and $A$ whose output $(x, w)$ satisfies $R (x, w) = 1$ : $\begin{array}{l} | Pr [crs \leftarrow Setup (1^{κ}) : D (crs) = 1] \\ - Pr [(crs, τ) \leftarrow S_{1} (1^{κ}) : D (crs) = 1] | ⩽ negl (κ) and \\ | Pr [(crs, τ) \leftarrow S_{1} (1^{κ}), (x, w) \leftarrow A (crs, τ), π \leftarrow Prove (crs, x, w) : A (crs, π) = 1] \\ - Pr [(crs, τ) \leftarrow S_{1} (1^{κ}), (x, w) \leftarrow A (crs, τ), π \leftarrow S_{2} (crs, τ, x) : A (crs, π) = 1] | \\ ⩽ negl (κ) . \end{array}$

We may require that even after seeing many simulated proofs, whenever the adversary makes a new proof we are able to extract a witness. This property is called the simulation-sound-extractability (SE) [19], formally defined as follows.

Definition 2.19 (Simulation-sound-extractability (SE)).

Let Π be a NIZK proof of knowledge equipped with $(S_{1}, S_{2}, E_{1}, E_{2})$ as in the above definitions, Π is SE if there exists a simulator ${SE}_{1}$ , that outputs $(crs, τ, ξ)$ and is identical to $S_{1}$ when restricted to the first two parts $(crs, τ)$ , such that for all $p . p . t .$ adversaries $A$ : $\begin{array}{l} Pr [\begin{matrix} (crs, τ, ξ) \leftarrow {SE}_{1} (1^{κ}) \\ (x, π) \leftarrow A^{S_{2} (crs, τ, \cdot)} (crs) \\ w \leftarrow E_{2} (crs, ξ, x, π) \end{matrix} : \begin{matrix} Verif (crs, x, π) = 1 \\ \land R (x, w) = 0 \\ \land x \notin Q \end{matrix}] ⩽ negl (κ), \end{array}$ where Q is the set of all the statements that adversary has asked its oracle.

3. A DAPS scheme from VC and DCH (DAPS-VC-DCH)

3.1. Construction

In this section we present our DAPS scheme based on vector commitments and double-trapdoor chameleon hash function. Our scheme will make use of a “flat” q-ary tree (i.e. a tree with branching degree q) of height h, which we call the signing tree. The root of the tree will be a public value $C_{ϵ}$ that will be part of the public key. Recall that in DAPS, messages are tuples of the form $(a, p)$ . The first component is interpreted as an integer in the range ${0, \dots, q^{h} - 1}$ . We can univocally associate each a to a path connecting the root with one leaf of the tree. In particular, a can be viewed as a number representing the labeling of the leaf in q-ary encoding (see the toy example in Fig. 7 for $q = 3$ ). In what follows, ${path}_{u \to w}$ denotes the ordered sequence of nodes connecting node u to node w. The root will be denoted by ϵ. Note that each node u has a unique position in the tree which we denote by ${pos}_{u}$ ; when u is the i-th node, from left-to-right, in the j-th level of the tree, we define ${pos}_{u} = j | | i$ .

Fig. 7.

The assignment of addresses.

Overview of the scheme. We start with an informal description of the stateful version of our scheme where the signer needs to keep track of the produced signatures. The public key contains the public parameters for a vector commitment scheme $VC$ and for a double-trapdoor chameleon hash function $DCH$ . The private key is the corresponding trapdoor information. The public key also contains a value $C_{ϵ}$ which is computed as follows. The signer first computes $CHash$ on q random inputs to get the output values $m_{0}, \dots, m_{q - 1}$ . Next, she sets $C_{ϵ}$ as a $VC$ commitment to the vector $m_{0}, \dots, m_{q - 1}$ . The value $C_{ϵ}$ is assigned to the root of an initially empty tree.

The signature algorithm will “fill up” this tree on the fly. To sign the message $(a, p)$ , the signer will place p as the a-th leaf and will output an authentication chain that links p to the root $C_{ϵ}$ . The verifier will follow this authentication chain and if the end of the chain matches the value in the public key, accepts the signature.

We describe more in detail how the signer creates the authentication chain. Starting from the a-th leaf the signer produces the signature by augmenting the existing tree with the new authentication path. This is done using the following create-and-connect approach. First, the signer generates the possibly missing portion of the subtree containing the a-th leaf. Next, it connects this portion to the signing tree. Creating the missing portion of the tree essentially amounts to creating all the missing nodes. Specifically, and letting $a = (a_{0}, \dots, a_{h})$ be the q-ary encoding of a, the signer computes $m_{a_{h}} = CHash (p_{h}, r)$ where $p_{h} = p$ (for some randomness r) and, for $i \in {0, \dots, q - 1} ∖ {a_{h}}$ , $m_{i} = CHash (ρ_{i}, r_{i})$ for random $ρ_{i}, r_{i}$ . Next the signer computes $p_{h - 1} = Cmt (\vec{m})$ with $\vec{m} = (m_{0}, \dots, m_{q - 1})$ . The process is then repeated node by node moving up the path until no more nodes need to be created. This happens when the newly created $p_{j}$ needs to be inserted in a position already occupied by some other value $ρ_{j} \neq p_{j}$ (i.e. for which a value $CHash (ρ_{j}, r_{j})$ was previously computed). This is when the connect phase begins. The signer uses knowledge of the trapdoor key to find a “colliding” r such that $CHash (ρ_{j}, r_{j}) = CHash (p_{j}, r)$ .

In Fig. 8 we provide a pictorial representation of the key generation phase (for the toy case with branching degree 3). Black nodes indicate values that are obtained as outputs of the (vector) commitment and will not be altered any further in the future. Gray nodes indicate the frontier of the tree, i.e., nodes that are either leaves or roots of subtrees not yet explored (and are visited through their parents i.e., the black nodes). White nodes are the ones which are not visited so far.

Similarly, Fig. 9 pictorially describes (a toy example of) the signing procedure. To sign the message $(a = 000, p)$ , one first creates the missing part of the tree, as sketched above. This also requires the signer to store all the commitments associated to each node. Once the procedure reaches a frontier node, the signer uses knowledge of the trapdoor to find a collision for $CHash$ . In Fig. 9 this is what happens to node 1 that, once connected with the newly created subtree, becomes black. Notice that the collision finding procedure typically alters the associated randomness ${\hat{r}}_{10}$ . This change will be done once and for all at this stage, as once the node is blackened no further modifications are allowed. To complete the procedure, the signer also produces valid openings Λ for all the commitments encountered in the path from the leaf p to the root and updates the lists of data associated to each node.

Fig. 8.

Generation of the verification key.

Fig. 9.

Signature phase.

Formal description of the scheme. We are now ready to present a formal description of our scheme. Let $VC = (VC . Setup, Cmt, Open, VC . Verif)$ be a vector commitment (VC) scheme and $DCH = (DCH . KeyGen, Trapdr, CHash, Coll)$ be a double-trapdoor chameleon hash (DCH) function with $Cmt : M^{q} \to O_{vc}$ and $CHash : (P, R) \to O_{DCH}$ . Let $H_{1} : O_{vc} \to P$ and $H_{2} : O_{DCH} \to M$ be two collision-resistant hash functions, used to map between different data types. The underlying data structure will be a tree T of branching degree q and height h. Messages are tuples of the form $(a, p)$ with payload component $p \in P$ and address $a \in U : = {0, \dots, q^{h} - 1}$ . We use the label ϵ for the root. Also, we say that v is a child of u in position i when v is the i-th child of u (counting from left).

Fig. 10.

Our DAPS-VC-DCH scheme.

Fig. 11.

Detailed figure for the construction and the security proof. Here dotted edges denote operations in a single node.

We use a pseudo-random function F to generate the random values $(ρ_{j i}, r_{j i})$ as $ρ_{j i} = F_{k} (j | | i, 0)$ and $r_{j i} = F_{k} (j | | i, 1)$ , where k is part of the signing key. This makes signing deterministic (but still stateful, see below) and minimizes the information that has to be stored by the signer. Recall that ${pos}_{u} = j | | i$ denotes the unique position of node u in the tree. A complete description of the scheme is given in Fig. 10 and Fig. 11.

Remark 3.1.

For DAPS schemes, signing is inherently stateful as the signer needs to remember the signed addresses in order not to sign a compromising pair. This is important for unforgeability rather than for correctness. Keeping track of the signed addresses can be efficiently done using a bloom filter [30]. In our scheme, the signer must in addition remember the payloads that it has signed in the past (but no further information, such as past signatures). This suffices to regenerate the tree during the signing of a new message.

3.2. Security analysis

We prove the security of our construction via the following two theorems, first key-extractability (Definition 2.7), then unforgeability (Definition 2.8).

The general intuition of the proof of key-extractability is as follows. Assume that a malicious signer can produce two valid signatures for a compromising pair without leaking the required information on secret keys (as defined by the predicate $Comp$ ). We show that this can be used to break one of the underlying primitives.

For any compromising pair, the authentication path passes through the same nodes to the root and the commitment at the end of the chain is fixed by the verification key. This means the two valid signatures for a compromising pair have a “collision node” on the path, where at and above that node, the commitments of the authentication chains for these two signatures must be equal. Due to the security of hash functions $H_{1}$ and $H_{2}$ and the position-binding property of the VC scheme (which only rely on public parameters over which the signer has no control), and the fact that the two payloads are different, the signer must create a DCH collision. As this DCH collision can be obtained from the signatures, and extraction did not work, this breaks key-extractability of DCH. Now we make this intuition more formal.

Theorem 3.1.
If $VC$ is position-binding, $DCH$ is key-extractable and $H_{1}, H_{2}$ are collision-resistant, then our construction (Fig. 10 ) is key-extractable (w.r.t. the trusted setup for VC).
Proof.
We prove the theorem via a sequence of hybrid games. Game 0 denotes the original ${KExt}_{DAPS, A}^{Tr} (κ)$ experiment given in Definition 2.7. We denote with $G_{i} (A)$ the event that the experiment Game i, ran with adversary $A$ , outputs 1. Game 1.
This is the same as Game 0 except that we modify the condition to return 1 in ${KExt}_{DAPS, A}^{Tr} (κ)$ (winning condition from now on) as follows.

Return 1 iff

– $(S_{1}, S_{2})$ is compromising

– $0 \leftarrow {Comp}_{vk} ({sk}^{'})$

– $(S_{1}, S_{2})$ do not contain collisions for $H_{1}$

$Pr [{KExt}_{DAPS, A}^{Tr} (κ) = 1] - Pr [G_{1} (A) = 1]$ is negligible assuming that $H_{1}$ is collision-resistant. Namely, the probability of finding a pair $(C_{u}^{1}, C_{u}^{2})$ , from the signatures associated with $(S_{1}, S_{2})$ , such that $H_{1} (C_{u}^{1}) = H_{1} (C_{u}^{2})$ and $C_{u}^{1} \neq C_{u}^{2}$ is negligible where $C_{u}^{1}$ and $C_{u}^{2}$ are the (VC) commitment values at a node u present in the signatures (see Fig. 11).
Game 2.
Here we modify the winning condition as follows

Return 1 iff

– $(S_{1}, S_{2})$ is compromising

– $0 \leftarrow {Comp}_{vk} ({sk}^{'})$

– $(S_{1}, S_{2})$ do not contain collisions for $H_{1}$ and $H_{2}$

As before $Pr [G_{1} (A) = 1] - Pr [G_{2} (A) = 1]$ is negligible assuming that $H_{2}$ is collision-resistant. Namely, the probability of finding a pair $(C_{u}^{1}, r_{u}^{1}), (C_{u}^{1}, r_{u}^{1})$ from the signatures associated with $S_{1}$ and $S_{2}$ such that $H_{2} (h_{u}^{1}) = H_{2} (h_{u}^{2})$ and $h_{u}^{1} \neq h_{u}^{2}$ is negligible (where $h_{u}$ is the chameleon-evaluation based on $C_{u}$ and $r_{u}$ , see Fig. 11).
Game 3.
Now we modify the winning condition as follows

Return 1 iff

– $(S_{1}, S_{2})$ is compromising

– $0 \leftarrow {Comp}_{vk} ({sk}^{'})$

– $(S_{1}, S_{2})$ do not contain collisions for $H_{1}$ and $H_{2}$

– $(S_{1}, S_{2})$ do not contain different openings for the same position

of the same vector commitment.

Under the assumption that the underlying vector commitment scheme is position-binding, Games 2 and 3 are indistinguishable, i.e. $Pr [G_{2} (A) = 1] - Pr [G_{3} (A) = 1]$ is negligible. Namely, the probability of finding a pair $(m_{u}^{1}, m_{u}^{2})$ from the signatures associated with $S_{1}$ and $S_{2}$ such that $m_{u}^{1} \neq m_{u}^{2}$ but the VC-evaluations over vectors including these values are equal. The value $m_{u}$ can be constructed from $C_{u}$ and $r_{u}$ given in the signature (Fig. 11).

Now we claim that, under the assumption that the underlying DCH guarantees Key-Extractability $Pr [G_{3} (A) = 1]$ is negligible. Indeed, notice that, in order for the experiment related to Game 3 to output 1, it has to be the case that $A$ produced a compromising pair that contains a DCH collision. This is because, by definition of compromising pair, $(S_{1}, S_{2})$ are such that $S_{1} = ((a_{1}, p_{1}), σ_{1})$ and $S_{2} = ((a_{2}, p_{2}), σ_{2})$ , where $a_{1} = a_{2}$ but $p_{1} \neq p_{2}$ and all other possible forms of collisions have been removed in previous games.

If $(S_{1}, S_{2})$ contains a collision for the DCH, the key-extractability property (of DCH) implies that such a collision can be used to extract a valid trapdoor ${tk}^{'}$ with all but negligible probability.

This concludes the proof. □
Theorem 3.2.
If $VC$ is position-binding, $DCH$ is a secure DCH scheme (Definition 2.13 ), F is pseudo-random, and $H_{1}$ and $H_{2}$ are collision-resistant, then our DAPS scheme (Fig. 10 ) is EUF-CMA secure.
Proof.
Once again the proof proceeds by a sequence of hybrid games. Game 0 denotes the original unforgeability experiment from Definition 2.8. We denote with $G_{i} (A)$ the event that the experiment Game i, ran with adversary $A$ , outputs 1. Game 1.
This is the same as Game 0 except that we replace the PRF with a truly random function. Clearly the security of the underlying pseudorandom function implies that $Pr [G_{0} (A) = 1] - Pr [G_{1} (A) = 1]$ is negligible.
Game 2.
Here we modify $KeyGen (1^{κ}, q, h)$ as follows. Rather than using $DCH . KeyGen (1^{κ})$ to produce the public/secret key material for the Double Trapdoor Collision-resistant hash function we choose a random bit b and run $DCH . TrChos (1^{κ}, b)$ instead. This results in using ${tk}_{b}$ (instead of ${tk}_{0}$ ) when answering $A$ ’s signing queries. Notice that, by the security of DCH (Definition 2.13, distribution of keys property) the output of $DCH . TrChos (1^{κ}, b)$ is distributed exactly as that of $DCH . KeyGen (1^{κ})$ . Moreover the Distribution of collisions property (again Definition 2.13) implies that Game 2 is perfectly indistinguishable from Game 1. Thus, $Pr [G_{1} (A) = 1] = Pr [G_{2} (A) = 1]$ .

Notice that, in order for the reasoning above to go through the restriction on the signing queries in the unforgeability game (Fig. 2) is crucial: if the adversary could obtain signatures on compromising pairs, then these would reveal ${tk}_{b}$ . This is due to the fact that ${tk}_{b}$ and ${tk}_{1 - b}$ are indistinguishable (last property of Definition 2.13) as far as the randomness of the collision pairs is not given, but signing the compromising pairs will give access to the randomness (as it is embedded in the signature).
Game 3.
Here we modify the condition to return 1 in ${Forg}_{DAPS}^{A} (κ)$ (winning condition from now on) by explicitly disallow certain forgeries. Specifically, consider a forgery $σ^{} = (r_{h}^{}, (r_{h - 1}^{}, C_{h - 1}^{}, Λ_{h - 1}^{}), \dots, (r_{1}^{}, C_{1}^{}, Λ_{1}^{}), Λ_{ϵ}^{})$ for a message $(a^{}, p^{})$ that was not signed by the game. Let i be the signing query whose address $a_{i}$ shares the longest prefix with $a^{}$ and let ℓ be the length of this prefix. Let also $(r_{ℓ + 1}, (r_{ℓ}, C_{ℓ}, Λ_{ℓ}), \dots, (r_{1}, C_{1}, Λ_{1}), Λ_{ϵ})$ be the part of the signature resulting from this i-th signing query (note that all signatures on addresses with the same prefix end with the same elements). In the followings, let j be the largest index $j ⩽ ℓ$ such that $(C_{j}^{}, \dots, C_{1}^{}) = (C_{j}, \dots, C_{1})$ . We call $Bad$ the following event: $Bad$ .
$(C_{j}^{}, \dots, C_{1}^{}) = (C_{j}, \dots, C_{1})$ and, denoting with $(ρ_{ℓ + 1}, r_{ℓ + 1}^{'})$ the inputs of the DCH chosen for the $a_{ℓ + 1}^{}$ -th child of the node corresponding to $C_{ℓ}$ when $C_{ℓ}$ was first computed, it happens that $H_{1} (C_{j + 1}^{}) = H_{1} (C_{j + 1})$ , where for the case $j = ℓ$ the last equality is equivalent with $H_{1} (C_{ℓ + 1}^{}) = ρ_{ℓ + 1}$ .

In this game we modify the winning condition by imposing that we abort if $Bad$ occurs. Clearly $\begin{matrix} | Pr [G_{2} (A) = 1] - Pr [G_{3} (A) = 1] | ⩽ Pr [Bad] \end{matrix}$

Now we observe that by the uniformity* property of $DCH$ (Definition 2.13), for $j = ℓ$ , $Bad$ happens only with negligible probability. Specifically, this is because the adversary has no information whatsoever on the $ρ_{ℓ + 1}$ value chosen by the simulator when computing $C_{ℓ}$ .5
⁵
The simulator here is the attacker to the security of DCH, the uniformity property.

And for $j < ℓ$ , $Bad$ happens with negligible probability due to the collision-resistance of $H_{1}$ (since $C_{j + 1}^{} \neq C_{j + 1}$ ).
Game 4.
Using the same notation as above, here we further modify the winning condition by explicitly disallowing more forgeries of the form $(C_{j}^{}, \dots, C_{1}^{}) = (C_{j}, \dots, C_{1})$ .

Again let $(ρ_{ℓ + 1}, r_{ℓ + 1}^{'})$ be the values chosen for the $a_{ℓ + 1}^{}$ -th child of the node corresponding to $C_{ℓ}$ when $C_{ℓ}$ was first computed.

Also let $ρ_{h}^{} : = p^{}$ ; else let $ρ_{j + 1}^{} : = H_{1} (C_{j + 1}^{})$ . Also $h_{j + 1}^{} : = {CHash}_{{pk}_{DCH}} (ρ_{j + 1}^{}, r_{j + 1}^{})$ and $: h_{j + 1} : = {CHash}_{{pk}_{DCH}} (ρ_{j + 1}, r_{j + 1})$ .6
⁶
for $j = ℓ$ , the randomness is $r_{ℓ + 1}^{'}$ .

We modify the wining condition by disallowing forgeries of the form $(C_{j}^{}, \dots, C_{1}^{}) = (C_{j}, \dots, C_{1})$ where $H_{1} (C_{j + 1}^{}) \neq H_{1} (C_{j + 1})$ and $h_{j + 1}^{} = h_{j + 1}$ (again for $j = ℓ$ we define $H_{1} (C_{ℓ + 1}) : = ρ_{ℓ + 1}$ ).

Clearly, (since $ρ_{j + 1}^{} \neq ρ_{j + 1}$ ) by key-extractability of $DCH$ , we extract a trapdoor ${tk}^{}$ .

To complete the argument let us discuss what happens when, by the key-extractability of $DCH$ , we extract a valid trapdoor ${tk}^{}$ . Since the adversary obtains no information on the bit b (determining which trapdoor was used by the game), the probability that ${tk}^{} = {tk}_{1 - b}$ is $\frac{1}{2}$ . The reduction can thus return ${tk}^{}$ and break double-trapdoor collision-resistance (Definition 2.13). Notice that, again, this argument crucially relies on the fact that the adversary cannot ask signing queries on compromising pairs.

Thus, under the collision-resistance of $DCH$ , games 3 and 4 are indistinguishable, i.e. $Pr [G_{4} (A) = 1] - Pr [G_{3} (A) = 1]$ is negligible.
Game 5.
Using the same notation as above, here we further modify the winning condition by explicitly disallowing forgeries of the form $(C_{j}^{}, \dots, C_{1}^{}) = (C_{j}, \dots, C_{1})$ where $h_{j + 1}^{} \neq h_{j + 1}$ and $m_{j + 1}^{} : = H_{2} (h_{j + 1}^{}) = H_{2} (h_{j + 1}^{}) : = m_{j + 1}$ .

Under the assumption that $H_{2}$ is collision-resistant, we have $Pr [G_{5} (A) = 1] - Pr [G_{4} (A) = 1]$ is negligible.

Now we claim that, under the assumption that $VC$ is position-binding, $Pr [G_{5} (A) = 1]$ is negligible. Note that in this game, the experiment can output 1 only if $A$ has found a collision for $VC$ . Namely, $C_{j}^{} = C_{j}$ but $m_{j + 1}^{} \neq m_{j + 1}$ where $C_{j}$ is a (VC) commitment to a vector including $m_{j}$ , and similarly about $C_{j}^{*}$ . This is due to the fact that all the possible forgeries are removed by the previous games.
□

3.3. Extension to untrusted setup (DAPS-DCH)

We discuss a simple modification of DAPS-VC-DCH that makes it secure when there is no trusted setup. What we mean by this is that, while we might trust standardized hash functions (such as SHA3) to be collision-resistant (CR), and the common choice of public parameters for the underlying assumptions, we might not trust a malicious signer to honestly generate its public key $vk$ .

Under a maliciously generated key, the signer might be able to produce signatures on a compromising pair from which no secret key can be extracted, unless the DAPS scheme satisfies key extractability for untrusted setups (defined via the game on the right in Fig. 2). For this to hold for our DAPS, the underlying primitives need to be secure in untrusted setups. For DCH, a candidate satisfying this was informally discussed in [10] and is explicitly formalized in Section 4. Unfortunately, for VC no instantiations without a trusted setup are known.

We therefore remove the VC scheme (and $H_{1}$ ) from the construction and replace it with a CR hash function $H : M^{q} \to P$ . For each node u we include all chameleon-hash values associated with its children (except the child on the current path to the root) in the authentication chain. This modification, which we call DAPS-DCH, has q times longer signatures. Security of the scheme is immediate, since we could view H as a VC with an opening of $(m_{0}, \dots, m_{q - 1}, m, i)$ defined as $(m_{0}, \dots, m_{i - 1}, m_{i + 1}, \dots, m_{q - 1})$ (Definition 2.9), which is position-binding by CR of H.

3.4. Extension to N-times-authentication

Assume that a domain server.com is allowed to participate maximum at $N - 1$ sessions where in each session it has a new pair of public/private key. This means that a CA should issue maximum $N - 1$ certificates associated with the mentioned domain, and as soon as the Nth certificate is issued the secret-key of CA would be revealed.

To extend our construction to N-Times-Authentication, we replace each node of the tree with a bucket of size $N - 1$ , where the signer uses a counter to keep track of used cells (to prevent using the same cell of a bucket for valid messages). The trapdoor of DCH is leaked as soon as a signer signs N-th message with the same address and different payloads.

4. Instantiations of building blocks for DAPS-VC-DCH

We instantiate the building blocks for our DAPS construction in Fig. 10. We use the VC scheme proposed by Catalano and Fiore [11], presented in Fig. 12 and we propose an instantiation for DCH.

Fig. 12.

Catalano–Fiore VC scheme [11].

Theorem 4.1 (Catalano–Fiore’s VC scheme [11]).

If the CDH assumption holds in group $G$ , then the scheme of Catalano–Fiore in Fig. 12 is a position-binding VC scheme.

In Appendix B, we also present an asymmetric version of Catalano–Fiore scheme and prove its security. This makes it more meaningful to compare our DAPS-VC-DCH scheme with the schemes in the asymmetric settings (e.g., DAPS-GS).

A we discussed, our DAPS-VC-DCH construction can be modified to be secure against untrusted setup, if the underlying DCH scheme is secure in the untrusted setup setting. This fact gives a strong argument why we need to realize a DCH scheme in an untrusted setup.

A possible candidate to instantiate the DCH scheme is the chameleon hash given in [8] where $CHash (m; r, s) = g^{m} {pk}_{1}^{r} {pk}_{2}^{s}$ , ${pk}_{1} = g^{x}$ , ${pk}_{2} = g^{y}$ . This scheme, however, does not satisfy the security requirements of DCH in the untrusted setup setting. The trouble is that in order to get the second trapdoor the extractor needs to know the first one. While this fits perfectly the application considered in [8], it does not cope well with our scenario where the signer might have both trapdoors and the (KE) challenger none (in such a case a collision results in an equation with two unknowns). A way around this would be to have one of the trapdoors chosen by a trusted setup and the other one by the signer. To avoid the need of trusted setup, we build a DCH scheme based on two layers of CHF such that being given a collision ensures that there is a collision either in the first layer or in the second layer. This means a collision gives enough equations to solve the system and extract unknowns.

The idea was implicitly given in [10] (Section 3.1, full version). However, since a more efficient DCH with security under a trusted setup was enough for them, they do not detail a construction or the security property. We note that not any arbitrary chaining may work here, and it is important to put the message in the first layer instead of the second layer (see Fig. 13).

Fig. 13.

Our DCH scheme.

Let $H_{i} = ({KeyGen}_{i}, {CHash}_{i}, {Coll}_{i})$ for $i = 0, 1$ , be two CHFs (see Definitions A.2 and A.3), and $H : O_{0} ⟶ M_{1}$ be a hash function where $O_{0}$ and $M_{1}$ are respectively the image of $H_{0}$ and the message space $H_{1}$ . The randomness space of $H_{i}$ is denoted by $R_{i}$ . Our suggested DCH scheme is given in Fig. 13.

In the following theorem we consider the predicate $Comp (\cdot)$ associated with DCH scheme to be defined as ${Comp}_{pk} ({tk}^{'}) = 1$ (with $pk = ({pk}_{0}, {pk}_{1})$ ) iff ${Comp}_{{pk}_{0}}^{'} ({tk}^{'}) = 1$ or ${Comp}_{{pk}_{1}}^{'} ({tk}^{'}) = 1$ . Where ${Comp}^{'} (\cdot)$ is the predicate associated with the CHF scheme.

Theorem 4.2.

If H is a collision-resistant hash function, $H_{0}, H_{1}$ are secure chameleon hash functions (w.r.t the predicate ${Comp}^{'}$ ), then our proposed construction in Fig. 13 is a secure DCH scheme (w.r.t the predicate $Comp$ ).

Proof.

We check the required security properties for DCH.

Distribution of the keys. Clearly, two distributions ${KeyGen (1^{κ})}$ , restricted to the output $pk, {tk}_{i}$ , and ${TrChos (1^{κ}, i)}$ are indistinguishable.

Collision-resistance (CR). Let $A$ be an adversary against collision-resistance of $DCH$ . We construct adversaries $B_{i}$ against collision-resistance of $H_{i}$ for $i = 0, 1$ . Simply, $B_{i}$ runs $H_{1 - i} . KeyGen (1^{κ})$ and returns $pk = ({pk}_{0}, {pk}_{1})$ and ${tk}_{1 - i} | | 1 - i$ to $A$ . When $A$ outputs ${tk}_{i}$ , $B_{i}$ uses it to find a collision.

Key-extractability (KE). Here we discuss the untrusted setup, i.e., the game ${KExt}_{DCH, A}^{nTr} (κ)$ in Fig. 5 where the extractor algorithm $Ext$ is given in Fig. 13. Let $A$ be the attacker to the KE of DCH, we construct an adversary $B$ that breaks either the KE of $H_{0}$ , or the KE of $H_{1}$ or the collision resistance of H.

Let $(pk; (m, r, s), (m^{'}, r^{'}, s^{'}))$ be the output of $A$ in the KE game, meaning that $(m, r, s), (m^{'}, r^{'}, s^{'})$ is a collision for the DCH scheme while ${Comp}_{{pk}_{0}}^{'} ({tk}^{'}) = 0$ and ${Comp}_{{pk}_{1}}^{'} ({tk}^{'}) = 0$ for a extracted ${tk}^{'}$ through $Ext$ algorithm.

Three following cases are possible where $w, w^{'}$ are defined as $w = H_{0} . CHash (m, r)$ and $w^{'} = H_{0} . CHash (m^{'}, r^{'})$ :

$(m, r) \neq (m^{'}, r^{'})$ and $w = w^{'}$

$(m, r) \neq (m^{'}, r^{'})$ and $w \neq w^{'}$ and $H (w) = H (w^{'})$

rest (either $(m, r) = (m^{'}, r^{'})$ (and thus $s \neq s^{'}$ ) or $H (w) \neq H (w^{'})$ must be the case)

In case 1

B

outputs

({pk}_{0}; (m, r), (m^{'}, r^{'}))

, in case 2

B

outputs

(w, w^{'})

and, finally, in case 3

B

outputs

({pk}_{1}; (H (w), s), (H (w^{'}), s^{'})

Notice that, in case 2, $B$ breaks the collision resistance of H. On the other hand, if ${Comp}_{{pk}_{0}}^{'} ({tk}^{'}) = 0$ and ${Comp}_{{pk}_{1}}^{'} ({tk}^{'}) = 0$ $B$ breaks either the KE of $H_{0}$ or that of $H_{1}$ .

Uniformity. is directly resulted from the uniformity of $H_{0}$ .

Distribution of collisions. One needs to show that for random $r \overset{_{R}}{\leftarrow} R_{0}$ and $s \overset{_{R}}{\leftarrow} R_{1}$ , $\begin{array}{l} {pk, {CHash}_{pk} (m, r, s), m, m^{'}, Coll (pk, {tk}_{0}, m^{'}, m, r, s)} \\ ≅ {pk, {CHash}_{pk} (m, r, s), m, m^{'}, Coll (pk, {tk}_{1}, m^{'}, m, r, s)}, \end{array}$ where ≅ stands for the indistinguishability of distributions and $Coll$ is given in Fig. 13. We show that if the distributions of collisions for $H_{0}$ and $H_{1}$ are uniform, then $(r^{'}, s^{'})$ (the output of $Coll (pk, {tk}_{i}, m^{'}, m, r, s)$ ) which is generated either by $H_{0}$ or by $H_{1}$ has uniform distribution (see the last security requirement of chameleon hash function for $H_{0}$ and $H_{1}$ Definition A.3).

if the collision has happened in $H_{0}$ : then we have $s^{'} = s$ which is uniform if s is uniform and $H_{1}$ generates uniform collisions. Particularly, one can write $s^{'} \leftarrow H_{1} . Coll ({tk}_{1}, H (w), H (w^{'}), s)$ , since $H (w) = H (w^{'})$ . On the other hand, since $H_{0}$ generates uniform collisions, $r^{'}$ is also uniform.

if the collision has happened in $H_{1}$ : clearly, $r^{'}$ is uniform and again since $H_{1}$ generates uniform collisions, $s^{'}$ is also uniform.

□

The CHF $H$ required for the previous theorem can be realized by Pedersen-commitment [27] where $CHash (m, r) = g^{m} {pk}^{r}$ , $pk = g^{x}$ and $tk = x$ . It is easily seen that this is a secure CHF in untrusted setup where the predicate $Comp (\cdot)$ is defined to be 1 iff the extracted trapdoor is the discrete logarithm of the public-key. The exact construction is depicted in Fig. 14 where $G = (G, q, g)$ describe the group $G$ of order q generated by g and bit length q is $poly (κ)$ . The group description $G$ is the implicit input of all algorithms.

Fig. 14.

Pedersen commitment as a CHF scheme [7].

5. A DAPS scheme based on NIZK proofs

We start with recalling the generic DAPS construction proposed by Derler et al. [16]. Their scheme, which we will refer to as DAPS-DRS, supports an exponentially large address space and is based on (simulation-sound) NIZK proofs of knowledge, which they instantiated using the Fiat–Shamir transformation [18] in the random oracle model. We will give an instantiation without random oracles and from standard assumptions by relying on the Groth–Sahai proof system [20]. This allows us to compare a standard-model version of an existing work to our DAPS-VC-DCH.

In DAPS-DRS scheme a signature contains a value $z : = γ \cdot p + {sk}_{Σ}$ where p is the payload of the message, ${sk}_{Σ}$ is a signing key for a digital signature scheme Σ, and γ is derived from the address part a of the message via a pseudo-random function (PRF) F as $γ : = F (k_{PRF}, a)$ . If the values $z, z^{'}$ for a compromising pair $(a, p), (a, p^{'})$ have been correctly computed then they reveal ${sk}_{Σ} = (z p^{'} - z^{'} p) / (p^{'} - p)$ .

To “commit” the signer to the values ${sk}_{Σ}$ and $k_{PRF}$ , a one-way function is used: the public key contains ${vk}_{Σ} : = f ({sk}_{Σ})$ and moreover values β and $c : = F (k_{PRF}, β)$ . For $(β, c)$ to fix $k_{PRF}$ , the PRF needs to assumed to be fixed-value key-binding, that is, it should be hard to find another key $k_{PRF}^{'}$ with $F (k_{PRF}, β) = F (k_{PRF}^{'}, β)$ .

A DAPS signature on a message $m = (a, p)$ under a public key $pk = (crs, {vk}_{Σ}, (β, c))$ then consists of the value z together with a NIZK proof under $crs$ that $({vk}_{Σ}, β, c, a, p, z)$ belongs to the following language: $\begin{matrix} L = \{({vk}_{Σ}, β, c, a, p, z) | \begin{matrix} \exists ({sk}_{Σ}, k_{PRF}) : c = F (k_{PRF}, β) \\ \land {vk}_{Σ} = f ({sk}_{Σ}) \land z = F (k_{PRF}, a) \cdot p + {sk}_{Σ} \end{matrix}\} . \end{matrix}$ The full description of their scheme is given in Fig. 22.

We instantiate the NIZK proofs using the Groth–Sahai system over asymmetric bilinear groups. While the security of this proof system relies on a standard assumption (SXDH, that is, decisional Diffie–Hellman (DDH) holds in $G_{1}$ and $G_{2}$ ), it only supports a restricted class of languages, so the signature scheme and the PRF need to be compatible.

This is the case for the variant [4] of Waters’ signature scheme [31] over asymmetric bilinear groups, which is secure under a variant of the computational Diffie–Hellman assumption, and the Naor–Reingold PRF [25], which is pseudo-random under DDH. Waters secret keys and Naor–Reingold PRF outputs are in $G_{1}$ . These instantiations are detailed in Section 5.2.

In order to avoid additional assumptions on the PRF, we slightly modify the DAPS-DRS construction [16] (and call it DAPS-GS, see Fig. 15): to bind the signer to the value $k_{PRF}$ , we simply commit to it in the public key using a commitment scheme $C = (Setup, Cmt, Open)$ . This lets us only rely on standard assumptions, while DRS had to assume that LowMC [1] is a fixed-value key-binding PRF.

Fig. 15.

A DAPS scheme based on Groth–Sahai proofs (DAPS-GS).

In our variant DAPS-GS (Fig. 15) the language for the proof system is as follows: $\begin{matrix} L^{'} = \{({vk}_{Σ}, {pp}_{C}, C_{PRF}, a, p, z) | \begin{matrix} \exists ({sk}_{Σ}, k_{PRF}) : C_{PRF} = Cmt ({pp}_{C}, k_{PRF}) \\ \land {vk}_{Σ} = f ({sk}_{Σ}) \land z = F {(k_{PRF}, a)}^{p} \cdot {sk}_{Σ} \end{matrix}\} \end{matrix}$ (recall that secret keys and PRF outputs are group elements, hence the multiplicative notation). Despite our efforts in optimizing the scheme, DAPS-GS is less efficient than our scheme DAPS-VC-DCH from Section 3, as shown in Table 1.

Figure 15 describes our DAPS-GS. In this construction $G_{i} \in {G_{1}, G_{2}, G_{T}}$ where $G_{i}$ is a cyclic group of order q and e is a bilinear map $e : G_{1} \times G_{2} \to G_{T}$ . Again, the signature scheme $Σ = ({KeyGen}_{Σ}, {Sign}_{Σ}, {Verif}_{Σ})$ only needs to have the property that a public key is a OWF image of the corresponding signing key: ${vk}_{Σ} = f ({sk}_{Σ})$ . Finally $Π = ({Setup}_{Π}, {Prove}_{Π}, {Verif}_{Π})$ is a NIZK proof system for the language $L^{'}$ .

The following theorems are the straightforward adaptations from the ones in [16].

Theorem 5.1 (Unforgeability).

If the NIZK proof system Π is simulation-sound extractable, F is a PRF, and f is a OWF, then the scheme DAPS-DRS is EUF-CMA secure.

Theorem 5.2 (Key-extractability).

If the NIZK proof system Π is simulation-sound extractable and $C$ is a secure commitment scheme, then the scheme DAPS-DRS is key-extractable in the trusted setup.

5.1. An overview of the Groth–Sahai proof system

In this section, we consider three groups $G_{1}$ , $G_{2}$ and $G_{T}$ of order p with generators $g_{1}$ , $g_{2}$ and $e (g_{1}, g_{2})$ , respectively. Groth and Sahai [20] presented an efficient NIZK proof system for languages defined over such bilinear groups; in Fig. 16 we overview the types of supported equations we require. The use of the instantiation (of GS proof) based on the SXDH assumption results in the proofs consisting of 6 group elements for each equation in $G_{1}$ (similarly for $G_{2}$ ), and poofs of size 8 for each pairing product equation. For each variable in $G_{1}$ , $G_{2}$ or $Z_{p}$ we have to add 2 group elements to the proof (the size of a commitment to the variable). The general size of the proof can thus be derived from the number (and type) of equations and variables.

Fig. 16.

Equations for Groth–Sahai proofs (for our language).

5.1.1. Making Groth–Sahai simulation-extractable

In our DAPS-GS we need a NIZK proof system with simulation-sound-extractability (SE). There are standard techniques for making a knowledge-sound/sound NIZK proof system (unbounded) simulation-sound [2,19]: Let L be an NP language defined via $x \in L$ iff $\exists w s . t . R (x, w) = 1$ and Π be a Groth–Sahai proof. Then Π can be made (weakly) simulation-sound-extractable by proving the following new relation, $\begin{matrix} (1) & R^{'} ((vk, x), (w)) \Leftrightarrow R (x, w) = 1 \lor Verif (vk, x, w) = 1 \end{matrix}$ where $σ \leftarrow {Sign}_{sk} (x)$ composed of elements from $G_{1}$ and $G_{2}$ , is a EUF-CMA signature on the statement x. The verification key $vk$ for the signature scheme is added to the CRS. Informally, this disjunction relation lets the simulator in the SE game simulate proofs satisfying the second clause in Eq. (1). When the adversary outputs a new statement $x^{*}$ for which the related extractor fails to extract a witness, then there are two types of failures; either no witness for the disjunction relation could be extracted, which breaks the knowledge-soundness of Groth–Sahai. Or, there is a witness for the signature part, which gives a forgery for the signature scheme.

Regarding the knowledge-soundness of GS-proof we have the following lemma.

Lemma 5.1 ([20]).

Let NIZK be the Groth–Shahi proof system for the equations in the form of Fig. 16 , in Definition 2.17 , if the witness is in $G_{i}$ for $i = 1, 2$ , then the extractor can completely extract it. Moreover, for the witness $a \in Z_{p}$ , it can only extract $g_{1}^{a}$ or $g_{2}^{a}$ but not a.

Since for the witnesses in $Z_{p}$ , the extractor of GS-proof system can not extract them, it is not knowledge-sound. But in our DAPS scheme, we just need the extraction of elements in the group $G_{i}$ . Thus, for our case we can assume that GS-proofs are knowledge-sound.

Waters’s signatures (defined below) are defined over bilinear groups so that signatures consist of group elements only. Thus, the scheme can be used to instantiate our DAPS scheme and it also can properly instantiate the simulation-sound-extractable transform just discussed.

To prove a disjunction relation like equation (1) in the Groth–Sahai framework, one needs to represent it as a conjunctions of equations. Groth [19] already suggested an elegant technique for this conversion by adding a variable and equations in a special way (see also Appendix C of the full version [2]). Assume that we want a disjunction relation between some equations of the following form where P and Q are known constants: $\begin{matrix} (2) & \prod_{i = 1}^{n} e (A_{i}, Y_{i}) \cdot \prod_{i = 1}^{m} e (X_{i}, B_{i}) \cdot \prod_{i = 1}^{m} \prod_{j = 1}^{n} e {(X_{i}, Y_{i})}^{γ_{i j}} = e (P, Q) \end{matrix}$ Then each of the above equations would be replaced with the following equations where $Q^{'}$ and $T$ are variables: $\begin{matrix} \prod_{i = 1}^{n} e (A_{i}, Y_{i}) \cdot \prod_{i = 1}^{m} e (X_{i}, B_{i}) \cdot \prod_{i = 1}^{m} \prod_{j = 1}^{n} e {(X_{i}, Y_{i})}^{γ_{i j}} = e (P, Q^{'}), e (T, Q^{- 1} \cdot Q^{'}) = 1_{G_{T}} . \end{matrix}$ Note that if $T \neq 1_{G_{1}}$ , then the only solution is $Q^{'} = Q$ , which in turn means that Eq. (2) is satisfied. Now for each equation (2) we have a separate variable $T$ . To express a disjunction of two equations of this kind, we add $e (T_{1} \cdot T_{2} \cdot g_{1}^{- 1}, g_{2}) = 1_{G_{T}}$ , which guarantees that not both $T_{1}$ and $T_{2}$ are $1_{G_{1}}$ and thus one of the equations (2) must be satisfied.

5.2. Instantiation of DAPS-GS

As we mentioned in the previous section, Groth–Sahai proofs work for statements over bilinear groups. Thus to use Groth–Sahai proofs when instantiating DAPS-DRS, we need to find proper instantiations of the statements over bilinear groups. Here are some theorems regarding such possible instantiations.

Theorem 5.3 (Naor–Reingold PRF [25]).

If the DDH assumption holds in the group $G$ , then the function F defined as follows is a PRF. $\begin{matrix} F_{k} (x) = F_{0}^{w} where F_{0} = g^{k_{0}} \in G, k = (F_{0}, k_{1}, \dots, k_{n}), x_{i} \in {0, 1}, w = \prod_{i = 1}^{n} k_{i}^{x_{i}} \end{matrix}$

The signature scheme Σ can be instantiated with Waters’ signature scheme since the signatures of this scheme are elements of bilinear groups. The following gives an improvement of Waters’ scheme and its security analysis [21] over asymmetric bilinear maps [4]. The need for an asymmetric variant of Waters’ signature comes from our instantiation for PRF based on DDH and GS- proofs for SXDH assumption.

Let $G = (p, G_{1}, G_{2}, G_{T}, g_{1}, g_{2}, e)$ be the description of a bilinear group. The hash function $H : {0, 1}^{l} \to G_{1}$ is defined by $H (m_{1}, \dots, m_{ℓ}) = h_{0} \prod_{i = 1}^{ℓ} h_{i}^{m_{i}}$ for $m_{i} \in {0, 1}$ and $h_{i} \in G_{1}$ .

Theorem 5.4 (Waters’ signature scheme [4,21,31]).

If the ${CDH}^{+}$ assumption holds for the bilinear group $G$ , then the scheme in Fig. 17 is EUF-CMA secure (Definition A.1 ).

To instantiate the commitment scheme

C

, we use Pedersen commitments.

Fig. 17.

Asymmetric variant of Waters’ signature scheme [4,31].

Theorem 5.5 (Pedersen commitments [27]).

The commitment scheme in Fig. 18 is perfectly hiding and computationally binding under the discrete logarithm assumption in group $G$ .

Fig. 18.

Pedersen’s commitment scheme [27].

In Appendix C, Figs 23 and 24 we show how to combine these instantiations together to get a Groth–Sahai compatible system of statements. As mentioned we have 6 group elements for each equation in $G_{1}$ (and similarly for $G_{2}$ ), thus if the address a is a bit-sting of size n, then from Fig. 24, one can see that we have $2 n$ equations in $G_{1}$ or $G_{2}$ . For each pairing equation, the proof includes 8 group elements and we have $11 + 2 n$ pairing equations. Finally, for each variable we have 2 group elements, and we have $5 n + 13$ variables. Putting together, we have $38 n + 114$ group elements in the proof.

Footnotes

Acknowledgments

The first author is supported by the Programma ricerca di ateneo UNICT 2020-22 linea 2. The second author is supported by the Vienna Science and Technology Fund (WWTF) through project VRG18-002. The third author benefited from the support of the Chair «Blockchain & B2B Platforms», led by l’X – Ecole polytechnique and the Fondation de l’Ecole polytechnique, sponsored by Capgemini.

Background material

Here we provide some standard definitions used in the paper.

Efficient CHF schemes have been instantiated based on the discrete-logarithm assumption [7] and the RSA (factorization) assumption [14,15].

An asymmetric variant of catalano-fiore VC scheme

To have a meaningful comparison between our DAPS-VC-DCH and DAPS-GS, we bring both schemes in the same setting. In [11], authors present a VC scheme under the CDH assumption, here we extend their construction to its asymmetric variant (see Fig. 21). To do so, we just replicate the public keys $h_{i}$ in group $G_{2}$ . We prove the security of this variant under a new assumption called square-CDH+ assumption which is similar to the square-CDH assumption where the term $g_{2}^{a}$ is also given in the input. In the following, let $G = (G_{1}, G_{2}, p, g_{1}, g_{2})$ be the description of groups $G_{1}, G_{2}$ of prime order p and with the generators $g_{1}$ and $g_{2}$ (res.).

We show that, if one can break the square-CDH+ assumption, then it can break a variant of CDH+ assumption ([4]) where an extra term $g_{2}^{b}$ is also given which we call CDH++ and defined as follows. Again let $G$ be the discreption of the group as before.

Clearly, if CDH++ holds then CDH+ also holds which makes it more reasonable to compare the mentioned schemes in the same setting and based on the same assumption CDH++.

Let $A$ be the adversary to the CDH++ assumption and $B$ be the adversary to the square-CDH+ assumption. The adversary $A$ simulates the game for the adversary $B$ as follows:

It receives the input $(G, g_{1}^{a}, g_{2}^{a}, g_{1}^{b}, g_{2}^{b})$ and runs the adversary $B$ three times on different inputs as $w_{1} \leftarrow B (G, g_{1}^{a}, g_{2}^{a})$ , $w_{2} \leftarrow B (G, g_{1}^{b}, g_{2}^{b})$ and $w_{3} \leftarrow B (G, g_{1}^{a + b}, g_{2}^{a + b})$ . Then it extracts $g_{1}^{a b}$ as ${(w_{3} \cdot w_{1}^{- 1} \cdot w_{2}^{- 1})}^{1 / 2}$ .

Overview of DAPS-DRS

In Fig. 22 we recall the DAPS-DRS construction. $F : K \times U \to SK$ is a value-key-binding PRF where $U$ is the DAPS address space and $SK$ is the space of signing keys for ${sk}_{Σ}$ , that is, the image of F is a subset of the signing-key space $SK$ . The signature scheme $Σ = ({KeyGen}_{Σ}, {Sign}_{Σ}, {Verif}_{Σ})$ is only required to have a very weak level of security namely, a public key is a OWF image of the corresponding signing key: ${vk}_{Σ} = f ({sk}_{Σ})$ . Finally $Π = ({Setup}_{Π}, {Prove}_{Π}, {Verif}_{Π})$ is a NIZK proof system for the language L defined in Section 5.

References

M.R.

Albrecht,

Rechberger,

Schneider,

Tiessen and

Zohner, Ciphers for MPC and FHE, in: EUROCRYPT 2015, Part I. LNCS, Vol. 9056,

Oswald and

Fischlin, eds, Springer, Heidelberg, 2015, pp. 430–454. doi:10.1007/978-3-662-46800-5_17.

Bellare and

Fuchsbauer, Policy-based signatures, in: PKC 2014. LNCS, Vol. 8383,

Krawczyk, ed., Springer, Heidelberg, 2014, pp. 520–537. doi:10.1007/978-3-642-54631-0_30.

Bellare,

Poettering and

Stebila, Deterring certificate subversion: Efficient double-authentication-preventing signatures, in: PKC 2017, Part II,

Fehr, ed., LNCS, Vol. 10175, Springer, Heidelberg, 2017, pp. 121–151. doi:10.1007/978-3-662-54388-7_5.

Blazy,

Fuchsbauer,

Pointcheval and

Vergnaud, Signatures on randomizable ciphertexts, in: PKC 2011. LNCS, Vol. 6571,

Catalano,

Fazio,

Gennaro and

Nicolosi, eds, Springer, Heidelberg, 2011, pp. 403–422. doi:10.1007/978-3-642-19379-8_25.

Blum,

Feldman and

Micali, Non-interactive zero-knowledge and its applications (extended abstract), in: 20th ACM STOC, ACM Press, 1988, pp. 103–112. doi:10.1145/62212.62222.

Boneh,

Kim and

Nikolaenko, Lattice-based DAPS and generalizations: Self-enforcement in signature schemes, in: ACNS 17. LNCS, Vol. 10355,

Gollmann,

Miyaji and

Kikuchi, eds, Springer, Heidelberg, 2017, pp. 457–477. doi:10.1007/978-3-319-61204-1_23.

Boyar,

S.A.

Kurtz and

M.W.

Krentel, A discrete logarithm implementation of perfect zero-knowledge blobs, Journal of Cryptology2(2) (1990), 63–76. doi:10.1007/BF00204448.

Bresson,

Catalano and

Gennaro, Improved on-line/off-line threshold signatures, in: PKC 2007. LNCS, Vol. 4450,

Okamoto and

Wang, eds, Springer, Heidelberg, 2007, pp. 217–232. doi:10.1007/978-3-540-71677-8_15.

Camenisch,

Hohenberger and

Lysyanskaya, Compact e-cash, in: EUROCRYPT 2005. LNCS, Vol. 3494,

Cramer, ed., Springer, Heidelberg, 2005, pp. 302–321. doi:10.1007/11426639_18.

10.

Catalano,

Di Raimondo,

Fiore and

Gennaro, Off-line/on-line signatures: Theoretical aspects and experimental results, in: PKC 2008. LNCS, Vol. 4939,

Cramer, ed., Springer, Heidelberg, 2008, pp. 101–120. doi:10.1007/978-3-540-78440-1_7.

11.

Catalano and

Fiore, Vector commitments and their applications, in: PKC 2013, Feb / Mar 2013. LNCS, Vol. 7778,

Kurosawa and

Hanaoka, eds, Springer, Heidelberg, 2013, pp. 55–72. doi:10.1007/978-3-642-36362-7_5.

12.

Catalano and

Gennaro, Cramer–Damgård signatures revisited: Efficient flat-tree signatures based on factoring, in: PKC 2005. LNCS, Vol. 3386,

Vaudenay, ed., Springer, Heidelberg, 2005, pp. 313–327. doi:10.1007/978-3-540-30580-4_22.

13.

Chaum,

Fiat and

Naor, Untraceable electronic cash, in: CRYPTO’88. LNCS, Vol. 403,

Goldwasser, ed., Springer, Heidelberg, 1990, pp. 319–327. doi:10.1007/0-387-34799-2_25.

14.

Cramer and

Damgård, New generation of secure and practical RSA-based signatures, in: CRYPTO’96. LNCS, Vol. 1109,

Koblitz, ed., Springer, Heidelberg, 1996, pp. 173–185. doi:10.1007/3-540-68697-5_14.

15.

Cramer and

Shoup, Signature schemes based on the strong RSA assumption, in: ACM CCS, Vol. 99,

Motiwalla and

Tsudik, eds, ACM Press, 1999, pp. 46–51. doi:10.1145/319709.319716.

16.

Derler,

Ramacher and

Slamanig, Generic double-authentication preventing signatures and a post-quantum instantiation, in: ProvSec 2018. LNCS, Vol. 11192,

Baek,

Susilo and

Kim, eds, Springer, Heidelberg, 2018, pp. 258–276. doi:10.1007/978-3-030-01446-9_15.

17.

Derler,

Ramacher and

Slamanig, Short double- and n-times-authentication-preventing signatures from ECDSA and more, in: 2018 IEEE European Symposium on Security and Privacy, EuroS&P 2018, London, United Kingdom, April 24–26, 2018, 2018, pp. 273–287.

18.

Fiat and

Shamir, How to prove yourself: Practical solutions to identification and signature problems, in: CRYPTO’86. LNCS, Vol. 263,

A.M.

Odlyzko, ed., Springer, Heidelberg, 1987, pp. 186–194. doi:10.1007/3-540-47721-7_12.

19.

Groth, Simulation-sound NIZK proofs for a practical language and constant size group signatures, in: ASIACRYPT 2006. LNCS, Vol. 4284,

Lai and

Chen, eds, Springer, Heidelberg, 2006, pp. 444–459. doi:10.1007/11935230_29.

20.

Groth and

Sahai, Efficient non-interactive proof systems for bilinear groups, in: EUROCRYPT 2008. LNCS, Vol. 4965,

N.P.

Smart, ed., Springer, Heidelberg, 2008, pp. 415–432. doi:10.1007/978-3-540-78967-3_24.

21.

Hofheinz and

Kiltz, Programmable hash functions and their applications, in: CRYPTO 2008. LNCS, Vol. 5157,

Wagner, ed., Springer, Heidelberg, 2008, pp. 21–38. doi:10.1007/978-3-540-85174-5_2.

22.

Krawczyk and

Rabin, Chameleon signatures, in: NDSS 2000, The Internet Society, 2000.

23.

Li,

Gao,

Wang,

Chen and

Tang, Double-authentication-preventing signatures revisited: New definition and construction from chameleon hash, Frontiers of IT & EE20(2) (2019), 176–186. doi:10.1631/FITEE.1700005.

24.

Libert and

Yung, Concise mercurial vector commitments and independent zero-knowledge sets with short proofs, in: TCC 2010. LNCS, Vol. 5978,

Micciancio, ed., Springer, Heidelberg, 2010, pp. 499–517. doi:10.1007/978-3-642-11799-2_30.

25.

Naor and

Reingold, Number-theoretic constructions of efficient pseudo-random functions, in: 38th FOCS, IEEE Computer Society Press, 1997, pp. 458–467. doi:10.1109/SFCS.1997.646134.

26.

Paillier and

Vergnaud, Discrete-log-based signatures may not be equivalent to discrete log, in: ASIACRYPT 2005. LNCS, Vol. 3788,

B.K.

Roy, ed., Springer, Heidelberg, 2005, pp. 1–20. doi:10.1007/11593447_1.

27.

T.P.

Pedersen, Non-interactive and information-theoretic secure verifiable secret sharing, in: CRYPTO’91. LNCS, Vol. 576,

Feigenbaum, ed., Springer, Heidelberg, 1992, pp. 129–140. doi:10.1007/3-540-46766-1_9.

28.

Poettering, Shorter double-authentication preventing signatures for small address spaces, in: AFRICACRYPT 18. LNCS, Vol. 10831,

Joux,

Nitaj and

Rachidi, eds, Springer, Heidelberg, 2018, pp. 344–361. doi:10.1007/978-3-319-89339-6_19.

29.

Poettering and

Stebila, Double-authentication-preventing signatures, in: ESORICS 2014, Part I. LNCS, Vol. 8712,

Kutylowski and

Vaidya, eds, Springer, Heidelberg, 2014, pp. 436–453. doi:10.1007/978-3-319-11203-9_25.

30.

Ruffing,

Kate and

Schröder, Liar, liar, coins on fire!: Penalizing equivocation by loss of bitcoins, in: ACM CCS 2015,

Ray,

Li and

Kruegel, eds, ACM Press, 2015, pp. 219–230. doi:10.1145/2810103.2813686.

31.

B.R.

Waters, Efficient identity-based encryption without random oracles, in: EUROCRYPT 2005. LNCS, Vol. 3494,

Cramer, ed., Springer, Heidelberg, 2005, pp. 114–127. doi:10.1007/11426639_7.

Double-authentication-preventing signatures in the standard model 1

Abstract

Keywords

1. Introduction

1.1. Challenges in constructing DAPS

1.2. Our contribution

1.2.1. Exponentially large address spaces without random oracles

1.2.2. Security without trusted setup

1.2.3. A more general definition

1.2.4. A Groth–Sahai-based construction

2. Preliminaries

2.1. Computational assumptions

Definition 2.1 (Discrete Logarithm Assumption (DL)).

Definition 2.2 (Decisional Diffie–Hellman Assumption (DDH).

Definition 2.3 (Computational Diffie–Hellman Assumption (CDH)).

Definition 2.4 (Advanced Computational Diffie–Hellman problem (CDH+)).

2.2. Digital signatures

Definition 2.5 (Digital signature scheme).

2.3. Double-authentication-preventing signatures

2 In [29] these two parts are referred as subject and message, and in [30] as context and statement. Here we follow the terminology from [28].

Definition 2.7 (Key-extractability [29]).

2.4. Vector commitments

Definition 2.9 (Vector commitments [11,24]).

Definition 2.10 (Correctness of VC).

Definition 2.11 (Position-binding).

Definition 2.12 (DC hash function [10]).

Definition 2.13 (Security of DCH).

3 This property alongside the definition of Coll algorithm essentially means having only one of the trapdoors is enough to simulate signature queries in the security game.

2.6. Non-interactive zero-knowledge proofs

Definition 2.14 (NIZK proof system [5]).

Definition 2.15 (Perfect Completeness).

Definition 2.16 (Perfect Soundness).

4 If A is p . p . t . , we call the system as the “Argument System”, while it is called “Proof System” for an unbounded A .

Definition 2.18 (Composable Zero-Knowledge).

Definition 2.19 (Simulation-sound-extractability (SE)).

3. A DAPS scheme from VC and DCH (DAPS-VC-DCH)

3.1. Construction

3.4. Extension to N-times-authentication

4. Instantiations of building blocks for DAPS-VC-DCH

Theorem 5.2 (Key-extractability).

5.1. An overview of the Groth–Sahai proof system

Lemma 5.1 ([20]).

5.2. Instantiation of DAPS-GS

Theorem 5.3 (Naor–Reingold PRF [25]).

Theorem 5.4 (Waters’ signature scheme [4,21,31]).

Footnotes

Acknowledgments

Background material

An asymmetric variant of catalano-fiore VC scheme

Overview of DAPS-DRS

References

²
In [29] these two parts are referred as subject and message, and in [30] as context and statement. Here we follow the terminology from [28].

³
This property alongside the definition of $Coll$ algorithm essentially means having only one of the trapdoors is enough to simulate signature queries in the security game.

⁴
If $A$ is $p . p . t .$ , we call the system as the “Argument System”, while it is called “Proof System” for an unbounded $A$ .