Double-Authentication-Preventing Signatures in the Standard Model

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. It seems to be the first construction achieving this in the standard model.

1 Introduction

Digital signatures (DS) are a cryptographic primitive that guarantees authenticity and integrity. Its security is defined via the notion of unforgeability, which protects the signer, and 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 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\ne 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 $(\textit{server.com},\mathsf {pk}_s,\sigma _s)$, where server.com is the domain, $\mathsf {pk}_s$ is the server’s public key and $\sigma _s$ is a signature on $(\textit{server}.com,\mathsf {pk}_s)$ by the CA. Entities that trust the CA’s public key can now securely communicate with server.com by using $\mathsf {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 [9]. 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. This is reminiscent to accountable assertions [20] (who give a ROM instantiation). For cryptocurrencies it is natural to implement this mechanism via DAPS, as digital signatures are already needed to authenticate transactions.

Practically, one can make non-equivocation contracts (i.e. contracts that allow to penalize 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.

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 [12, 18] 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. In the latter case, each signer generates its own key pair, while assuming a trusted setup, which generates and distributes key pairs to the signers, is arguably unrealistic.

The majority of existing DAPS constructions assumes a trusted setup [2, 12, 18, 19]. Those that do not, are in the random oracle model [20] or have polynomial-size signatures (w.r.t. the length of the address) [4] or only support small address spaces [12, 18].

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.

Efficient/Concrete Instantiations. Some prior DAPS schemes [11] that claim short signatures or achieve others 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.

Exponentially Large Address Spaces Without Random Oracles. Most of the existing DAPS schemes supporting an exponentially large address space need to rely on the RO heuristic (e.g. [2, 4, 19, 20]). For some of these constructions such as the one based on ID-protocols, the need for the RO assumption is a result of the transformation of an interactive protocol to an non-interactive version like Poettering’s scheme [18]. In the other schemes it is due to the fact that the simulator cannot simulate the signatures in the security reduction. The RO assumption then lets the simulator program its responses without having access to the signing key [20]. We circumvent many of the difficulties arising in previous works by combining vector commitments [7] and double-trapdoor chameleon hash functions [5, 6]. Our methodology follows the authentication tree approach also adopted in a previous work [20]: 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 [7] to realize a “flat” authentication tree (i.e. a tree with branching degree $q>2$). Since both vector commitments [7] and double-trapdoor chameleon hash [5, 6] (see also our DCH scheme in the full version) 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).

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 slightly 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 an untrusted setup (we present one in the full version), 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 [5, 6] 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 [6] (Sect. 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.

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 $\mathsf {Comp}_\mathsf {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 $\mathsf {sk}'$ (not necessarily the full signing key $\mathsf {sk}$) that is compatible with the verification key, i.e. $\mathsf {Comp}_\mathsf {vk}(\mathsf {sk}')=1$. In order for this formalization to be any useful we also require that producing an $\mathsf {sk}'$ such that $\mathsf {Comp}_\mathsf {vk}(\mathsf {sk}')=1$ is hard (without a compromising pair of signed messages).

A Groth-Sahai-Based Construction. As additional contribution of this paper we propose a DAPS construction from Groth Sahai proofs [14] (DAPS-GS), which builds upon a construction proposed by Derler et al. [11]. The scheme, which we will refer to as DAPS-DRS, supports an exponentially large address space and is based on NIZK proofs, which the authors instantiated 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 [14]. 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 [11] 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 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=\mathrm {poly}(n_0)$ are LWE parameters, and $\ell _\pi (n)$ denotes the proof size in the underlying NIZK system for statements of length n. Finally, $|\mathbb {G}|$ stands for the size of group elements, $\lambda _H$ is the bit length of the random oracle output, and N is an RSA modulus.

1.3 Related Work

Ruffing, Kate, and Schröder [20] 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 [8, 10].

Poettering [18] 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 [2] 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 [19] 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 [4] and Gao et al. [16].

Derler, Ramacher, and Slamanig [11] 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  [13]. 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

Notations. We denote the security parameter by $\kappa \in \mathbb {N}$ and $x\leftarrow X$ means that element x is chosen uniformly at random from 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. All algorithms run in probabilistic polynomial-time ($\mathsf {p.p.t.}$) unless stated otherwise. We denote concatenation by || and the set $\{1,\ldots ,n\}$ by [n]. We say $f(\kappa )$ is negligible, and write $f(\kappa )=\mathrm {negl}(\kappa )$, if for every positive polynomial $p(\kappa )$ there exists $\kappa _0\in \mathbb {N}$ such that for all $\kappa >\kappa _0$: $f(\kappa )< {1}/ {p(\kappa )}$.

2.1 Digital Signatures

A digital signature (DS) scheme is defined as follows.

Definition 1

(Digital signature scheme). A digital signature scheme $\varSigma$ consists of the $\mathsf {p.p.t.}$ algorithms $(\mathsf {KeyGen},\mathsf {Sign},\mathsf {Verif})$ where

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

• $\mathsf {Sign}(\mathsf {sk},m)$, on input signing key $\mathsf {sk}$ and message $m\in \mathcal {M}$, outputs a signature $\sigma$.

• $\mathsf {Verif}(\mathsf {vk},m,\sigma )$, on input verification key $\mathsf {vk}$, message $m\in \mathcal {M}$ and signature $\sigma$, outputs either 0 or 1.

Correctness. Signature scheme $\varSigma$ is correct if for all $\kappa \in \mathbb {N}$, for all $(\mathsf {sk}, \mathsf {vk})\leftarrow \mathsf {KeyGen}(1^\kappa )$, for all $m\in \mathcal {M}$, and $\sigma \leftarrow \mathsf {Sign}(\mathsf {sk}, m)$, we have $\mathsf {Verif}(\mathsf {vk}, m, \sigma ) = 1$.

2.2 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,¹ i.e., in Definition 1 we have $m=(a,p)\in \mathcal {U}\times \mathcal {P}$.

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

Definition 2

(Compromising pair of signatures  [19]). For a verification key $\mathsf {vk}$, a pair $(S_1, S_2)$ where $S_1=(a_1,p_1;\sigma _1)$ and $S_2=(a_2,p_2;\sigma _2)$, is compromising if

$$\begin{aligned} \mathsf {Verif}(\mathsf {vk},(a_1,p_1),\sigma _1)=1,\; \mathsf {Verif}(\mathsf {vk},(a_2,p_2),\sigma _2)=1,~~ a_1=a_2 \; \text {and} \; p_1\ne p_2. \end{aligned}$$

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 $\mathsf {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 $(\mathsf {sk},\mathsf {vk})\leftarrow \mathsf {KeyGen}(1^\kappa )$ it should be the case that $1\leftarrow \mathsf {Comp}_\mathsf {vk}(\mathsf {sk})$. If $\mathsf {Comp}_\mathsf {vk}(\cdot )=1$ is constant, we have nothing more than an ordinary signature without any prevention. The main requirement here is that producing $\mathsf {sk}'$ such that $\mathsf {Comp}_\mathsf {vk}(\mathsf {sk}')=1$ must be hard without a compromising pair of signed messages.

Fig. 1.

Game for key-extractability of DAPS.

Definition 3

(Key-extractability [19]). A DAPS scheme is key-extractable if there exists a $\mathsf {p.p.t.}$ algorithm $\mathsf {Ext}$ as follows:

• $\mathsf {Ext}(\mathsf {vk},S_1,S_2)$, on input a verification key $\mathsf {vk}$ and a compromising pair $(S_1,S_2)$, outputs a signing key $\mathsf {sk}'$,

such that $\Pr [\mathsf {KExt}^{\mathsf {Tr}/ \mathsf {nTr}}_{\mathsf {DAPS},\mathcal {A}}(\kappa )=1]= \mathrm {negl}(\kappa )$ for all $\mathsf {p.p.t.}$ adversaries $\mathcal {A}$, where experiment $\mathsf {KExt}^{\mathsf {Tr}/\mathsf {nTr}}_{\mathsf {DAPS},\mathcal {A}}(\kappa )$ is as described in Fig. 1.

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

Since DAPS schemes are a subclass of digital signatures, the standard existential unforgeability 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.

Definition 4

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

Fig. 2.

Game for EUF-CMA security of DAPS

Fig. 3.

Game for position-binding of a VC scheme

2.3 Vector Commitments

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

Definition 5

(Vector commitments [7]). A VC scheme is a tuple of $\mathsf {p.p.t.}$ algorithms $\mathsf {VC}=(\mathsf {Setup},\mathsf {Cmt},\mathsf {Open},\mathsf {Verif})$ where

• $\mathsf {Setup}(1^\kappa ,q)$, on input the security parameter $\kappa$ and the length q of committed vectors (with $q = poly(k)$), outputs public parameters $\mathsf {pp}$ (which defines the message space $\mathcal {M}$).

• $\mathsf {Cmt}_{\mathsf {pp}}(m_0,\ldots ,m_{q-1})$, on input a sequence of q messages $m_0,\ldots ,m_{q-1}\in \mathcal {M}$, outputs a commitment string C.

• $\mathsf {Open}_{\mathsf {pp}}(m_0,\ldots ,m_{q-1},m,i)$ produces a proof $\varLambda _i$ that m is the i-th committed message in the sequence $m_0,\ldots ,m_{q-1}$.

• $\mathsf {Verif}_{\mathsf {pp}}(C,m,i,\varLambda _i)$ outputs 1 if $\varLambda _i$ is a valid proof that C commits to a sequence $m_0,\ldots , m_{q-1}$ with $m=m_i$, and 0 otherwise

Definition 6

(Correctness of VC). A $\mathsf {VC}$ is correct if for all $\kappa \in \mathbb {N}$ and $q=\mathrm {poly}(\kappa )$, all $\mathsf {pp}\leftarrow \mathsf {Setup}(1^\kappa ,q)$ and all vectors $(m_0,\ldots ,m_{q-1})\in \mathcal {M}^q$, we have

$$\Pr \left[ \begin{array}{l} C\leftarrow \mathsf {Cmt}_{\mathsf {pp}}(m_0,\ldots ,m_{q-1})\\ \varLambda _i\leftarrow \mathsf {Open}_{\mathsf {pp}}(m_i,i) \end{array}\ :\ \mathsf {Verif}_{\mathsf {pp}}(C,m_i,i,\varLambda _i)=1\right] =1.$$

The security notion for a VC scheme is called position-binding and requires that for any $\mathsf {p.p.t.}$ adversary, given $\mathsf {pp}$, it should be infeasible to produce a commitment C and openings to two different messages for the same position.

Definition 7

(Position binding). A VC scheme $\mathsf {VC}$ is position-binding if for all $i\in \{0,\ldots ,q-1\}$ and $\mathsf {p.p.t.}$ adversary $\mathcal {A}$ we have $\Pr [\mathsf {PBind}_\mathsf {VC}^\mathcal {A}(\kappa )=1]=\mathrm {negl}(\kappa )$, where game $\mathsf {PBind}_\mathsf {VC}^\mathcal {A}(\kappa )$ 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 $\mathsf {Open}$ are both independent of q.

2.4 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.

Fig. 4.

Collision-resistance game for a DCH scheme

Definition 8

(DC hash function [6]). A DCH scheme $\mathcal {H}$ is a tuple of $\mathsf {p.p.t.}$ algorithms $\mathcal {H}=(\mathsf {KeyGen},\mathsf {TrChos},\mathsf {CHash},\mathsf {Coll})$ where

• $\mathsf {KeyGen}(1^\kappa )$, on input the security parameter $\kappa$, outputs a public key $\mathsf {pk}$ (which implicitly defines the message space $\mathcal {M}$) and private keys $\mathsf {tk}_0$ and $\mathsf {tk}_1$.

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

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

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

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

Definition 9

(Security of DCH). We require double-trapdoor chameleon hash functions to satisfy the following properties:

• Distribution of keys. The output of $\mathsf {TrChos}(1^\kappa ,i)$ is distributed like a public key $\mathsf {pk}$ and the i-th private key $\mathsf {tk}_i$ output by $\mathsf {KeyGen}(1^\kappa )$.

• Double-trapdoor collision-resistance (DTCR). Let $(\mathsf {pk},\mathsf {tk}_0,\mathsf {tk}_1)$ be output by $\mathsf {KeyGen}(1^\kappa )$. For all $i=0,1$, given $\mathsf {pk}$ and $\mathsf {tk}_i$ it is infeasible to find $\mathsf {tk}_{1-i}$. Formally, for all $\mathsf {p.p.t.}$ adversary $\mathcal {A}$, we have $\Pr [\mathsf {DTCR}^\mathcal {A}_{\mathsf {DCH}} (\kappa )=1] = \mathrm {negl}(\kappa )$, where game $\mathsf {DTCR}^\mathcal {A}_{\mathsf {DCH}}$ is defined in Fig. 4.

• Key-extractability (KE) (w.r.t. predicate $\mathsf {Comp}(\cdot )$). There exists a $\mathsf {p.p.t.}$ algorithm $\mathsf {Ext}$ as follows:

  • $\mathsf {Ext}(\mathsf {pk},S_1,S_2)$, on input the public key $\mathsf {pk}$ and a collision pair $(S_1,S_2)$, outputs a (single) secret key $\mathsf {tk}'$,

  such that $\Pr [\mathsf {KExt}^{\mathsf {Tr}/\mathsf {nTr}}_{\mathsf {DCH},\mathcal {A}}(\kappa )=1] = \mathrm {negl}(\kappa )$ for all $\mathsf {p.p.t.}$ adversaries $\mathcal {A}$, with game $\mathsf {KExt}^{\mathsf {Tr}/\mathsf {nTr}}_{\mathsf {DCH},\mathcal {A}}(\kappa )$ as defined in Fig. 5.

• Uniformity. For r chosen uniformly at random in $\mathcal {R}$, all messages m induce the same probability distribution on $\mathsf {CHash}_{\mathsf {pk}}(m,r)$. This implies that $\mathsf {CHash}_{\mathsf {pk}}(m,r)$ for randomly chosen r information-theoretically hides m. As for standard chameleon hash functions [15] 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'=\mathsf {Coll}(\mathsf {tk}_i,m,m',r)$ are identical (uniform) for $i = 0,1$, even when given $\mathsf {CHash}_\mathsf {pk}(m,r)$, m and $m'$.

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.

Remark 1 (On defining Key Extractability)

Our definitions above of Key Extractability implicitly assume that some appropriate predicate $\mathsf {Comp}$ is always associated with a DCH. This might seem surprising at first as, for DCH, $\mathsf {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 $\mathsf {DCH}$ to have an associated predicate $\mathsf {Comp}$, which lets us define Key Extractability for DAPS.

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

2.5 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 10

(NIZK proof system). A NIZK proof system $\varPi$ for the language L consists of three $\mathsf {p.p.t.}$ algorithms $(\mathsf {Setup},\mathsf {Prove}$, $\mathsf {Verif})$ where

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

• $\mathsf {Prove}(\mathsf {crs},x,w)$, takes the $\mathsf {crs}$, a statement x and a witness w as input and outputs a proof $\pi$.

• $\mathsf {Verif}(\mathsf {crs},x,\pi )$ takes the $\mathsf {crs}$, the statement x, and a proof $\pi$ as input and outputs either 0 or 1.

For a proof system $\varPi =(\mathsf {Setup},\mathsf {Prove},\mathsf {Verif})$, in addition to completeness and zero-knowledge we require simulation-sound extractability, which is a strengthening of knowledge soundness: even after the adversary has seen simulated proofs, from any valid (fresh) proof output by the adversary, a witness can be extracted.

Fig. 6.

Assigning addresses to leafs.

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_\epsilon$ 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. 6 for $q=3$). In what follows, $\mathsf {path}_{u\rightarrow w}$ denotes the ordered sequence of nodes connecting node u to node w. The root will be denoted by $\epsilon$. Note that each node u has a unique position in the tree which we denote by $\mathsf {pos}_u$; when u is the i-th node, from left-to-right, in the j-th level of the tree, we define $\mathsf {pos}_u=j||i$.

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 $\mathsf {VC}$ and for a double-trapdoor chameleon hash function $\mathsf {DCH}$. The private key is the corresponding trapdoor information. The public key also contains a value $C_\epsilon$ which is computed as follows. The signer first computes $\mathsf {CHash}$ on q random inputs to get the output values $m_0, \dots , m_{q-1}$. Next, she sets $C_\epsilon$ as a $\mathsf {VC}$ commitment to the vector $m_0,\dots ,m_{q-1}$. The value $C_\epsilon$ 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_\epsilon$. 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}=\mathsf {CHash}(p_h,r)$ where $p_h=p$ (for some randomness r) and, for $i\in \{0, \dots , {q-1}\}\setminus \{a_h\}$, $m_i=\mathsf {CHash}(\rho _i,r_i)$ for random $\rho _i,r_i$. Next the signer computes $p_{h-1}=\mathsf {Cmt}({\textit{\textbf{m}}})$ with ${\textit{\textbf{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 $\rho _j\ne p_j$ (i.e. for which a value $\mathsf {CHash}(\rho _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 $\mathsf {CHash}(\rho _j,r_j)=\mathsf {CHash}(p_j,r)$.

In Fig. 7 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.

Fig. 7.

Key generation: verification key.

Similarly, Fig. 8 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 $\mathsf {CHash}$. In Fig. 8 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 $\varLambda$ 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.

Signature procedure.

Formal Description of the Scheme. We are now ready to present a formal description of our scheme. Let $\mathsf {VC}=(\mathsf {VC}.\mathsf {Setup},\mathsf {Cmt},\mathsf {Open},\mathsf {VC}.\mathsf {Verif})$ be a vector commitment (VC) scheme and $\mathsf {DCH}=(\mathsf {DCH}.\mathsf {KeyGen},\mathsf {Trapdr},\mathsf {CHash},\mathsf {Coll})$ be a double-trapdoor chameleon hash (DCH) function with $\mathsf {Cmt}:\mathcal {M}^q\rightarrow \mathcal {O}_{\mathsf {vc}}$ and $\mathsf {CHash}:(\mathcal {P},\mathcal {R})\rightarrow \mathcal {O}_{\mathsf {DCH}}$. Let $H_1:\mathcal {O}_{\mathsf {vc}}\rightarrow \mathcal {P}$ and $H_2:\mathcal {O}_{\mathsf {DCH}}\rightarrow \mathcal {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 \mathcal {P}$ and address $a\in \mathcal {U}:=\{0, \ldots , q^h-1\}$. We use the label $\epsilon$ 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).

We use a pseudo-random function F to generate the random values $(\rho _{ji},r_{ji})$ as $\rho _{ji}=F_k(j||i,0)$ and $r_{ji}=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 $\mathsf {pos}_u=j||i$ denotes the unique position of node u in the tree. A complete description of the scheme is given in Fig. 9 and Fig. 10

Remark 2

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 [20]. 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

Fig. 9.

Our DAPS-VC-DCH scheme.

We prove the security of our construction via the following two theorems, first key-extractability (Definition 3), then unforgeability (Definition 4). Formally, we have the following theorem where we consider the KE property of our DAPS scheme w.r.t the same extractor of DCH scheme.

Theorem 1

If $\mathsf {VC}$ is position-binding, $\mathsf {DCH}$ is key-extractable and $H_1, H_2$ are collision-resistant, then our construction (Fig. 9) is key-extractable (w.r.t. the trusted setup for VC).

Proof Sketch. The general intuition of the proof 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 $\mathsf {Comp}$). We show that this can be used to break one of the underlying primitives.

Fig. 10.

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

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. We make this intuition formal in the full version.

Theorem 2

If $\mathsf {VC}$ is position-binding, $\mathsf {DCH}$ is a secure DCH scheme (Definition 9), F is pseudo-random, and $H_1$ and $H_2$ are collision-resistant, then our DAPS scheme is EUF-CMA secure.

Proof Sketch. The first step in the proof is to replace all PRF outputs by uniformly random values, which is indistinguishable by pseudo-randomness. The rest of the proof crucially relies on various properties of the DCH scheme. First note that instead of using $\mathsf {tk}_0$ as specified by the signing protocol, the game can choose $b{\mathop {\leftarrow }\limits ^{{}_R}}\{0,1\}$ and use $\mathsf {tk}_b$ when answering the adversary’s signing queries. By distribution of collisions (Definition 9), the game is distributed as the original game (with PRF values replaced by random).

Consider a forgery $\sigma ^*=(r^*_h,(r^*_{h-1},C^*_{h-1},\varLambda ^*_{h-1}),\ldots ,(r^*_{1},C^*_{1},\varLambda ^*_{1}),\varLambda ^*_\epsilon )$ 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 $\ell$ be the length of this prefix. Let $(r_{\ell +1},\,(r_{\ell },C_{\ell },\,\varLambda _{\ell }),\ldots ,(r_{1},\,C_{1},\,\varLambda _{1}),\varLambda _\epsilon )$ 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). We consider two cases:

• $(C^*_\ell ,\ldots ,C^*_1)\ne (C_\ell ,\ldots ,C_1)$: Let j be the smallest index so that $C^*_j\ne C_j$. If $p^*_j:=H_1(C_j^*) = H_1(C_j) =:p_j$ then we have found an $H_1$ collision (see Fig. 10 for the required computations/operations in this node). Else if $h^*_j:=\mathsf {CHash}(p_j^*,r_j^*) = \mathsf {CHash}(p_j,r_j)=:h_j$ then (since $p^*_j\ne p_j$), by key-extractability of $\mathsf {DCH}$ we can extract a trapdoor $\mathsf {tk}^*$. Else if $m^*_j:=H_2(h_j^*) = H_2(h_j) =: m_j$, then (since $h_j^*\ne h_j$) we have found an $H_2$ collision. Else we have $m^*_j\ne m_j$ and since $C^*_{j-1} = C_{j-1}$, this breaks position-binding of $\mathsf {VC}$.

• $(C^*_\ell ,\ldots ,C^*_1)=(C_\ell ,\ldots ,C_1)$: Let $(\rho _{\ell +1},r'_{\ell +1})$ be the values chosen for the $a^*_{\ell +1}$-th child of the node corresponding to $C_\ell$ when $C_\ell$ was first computed. Let $\rho ^*:= p^*$ if $\ell = h-1$; else let $\rho *:=H_1(C^*_{\ell +1})$. If $\rho ^* = \rho _{\ell +1}$ then we abort.    $(*)$

  If $h_j^*:=\mathsf {CHash}(\rho ^*,r_{\ell +1}^*) = \mathsf {CHash}(\rho _{\ell +1},r'_{\ell +1})=:h_j^*$ then (since $\rho ^* \ne \rho _{\ell +1}$) by key-extractability, we extract a trapdoor $\mathsf {tk}^*$. Otherwise, since $C_\ell ^*=C_\ell$, but $h_j^*\ne h_j$, we either found a collision for $H_2$ or we broke position-binding of $\mathsf {VC}$.

By uniformity of hashes (Definition 9) of the chameleon hash function $\mathsf {DCH}$, the adversary has no information on $\rho _{\ell +1}$, so the probability of aborting in line $(*)$ is negligible. Moreover, if we did not break CR of $H_1$ or $H_2$, or position-binding of $\mathsf {VC}$ or key-extractability of $\mathsf {DCH}$, then we have extracted a valid trapdoor $\mathsf {tk}^*$. Since the adversary obtains no information on the bit b (determining which trapdoor was used by the game), the probability that $\mathsf {tk}^*=\mathsf {tk}_{1-b}$ is $\frac{1}{2}$. The reduction can thus return $\mathsf {tk}^*$ and break double-trapdoor collision-resistance (Definition 9).

Finally, note that 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 $\mathsf {tk}_b$. The formal proof is given in the full version.

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), we might not trust a malicious signer to honestly generate its public key $\mathsf {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 [6] and is explicitly formalized in the full version of this paper. 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:\mathcal {M}^q\rightarrow \mathcal {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,\ldots ,m_{q-1},m,i)$ defined as $(m_0,\dots ,m_{i-1},m_{i+1},\dots ,m_{q-1})$ (Definition 5), which is position-binding by CR of H.

4 A DAPS Scheme Based on NIZK Proofs

We start with recalling the generic DAPS construction proposed by Derler et al. [11]. 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 [13] 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 [14]. 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:=\gamma \cdot p+\mathsf {sk}_\varSigma$ where p is the payload of the message, $\mathsf {sk}_\varSigma$ is a signing key for a digital signature scheme $\varSigma$, and $\gamma$ is derived from the address part a of the message via a pseudo-random function (PRF) F as $\gamma :=F(\mathsf {sk}_\mathsf {PRF},a)$. If the values $z,z'$ for a compromising pair $(a,p),(a,p')$ have been correctly computed then they reveal $\mathsf {sk}_\varSigma =(zp'-z'p)/(p'-p)$.

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

A DAPS signature on a message $m=(a,p)$ under a public key $\mathsf {pk}=(\mathsf {crs},\mathsf {vk}_\varSigma ,(\beta ,c))$ then consists of the value z together with a NIZK proof under $\mathsf {crs}$ that $(\mathsf {vk}_\varSigma ,\beta ,c,a,p,z)$ belongs to the following language:

$$\begin{aligned} L=\left\{ (\mathsf {vk}_\varSigma ,\beta ,c,a,p,z)~\left| ~\begin{array}{l}\exists \, (\mathsf {sk}_\varSigma ,\mathsf {sk}_\mathsf {PRF}): c=F(\mathsf {sk}_\mathsf {PRF},\beta )\\ \quad \wedge \;\mathsf {vk}_\varSigma =f(\mathsf {sk}_\varSigma )\,\wedge \,z=F(\mathsf {sk}_\mathsf {PRF},a)\cdot p+\mathsf {sk}_\varSigma \end{array}\right. \right\} . \end{aligned}$$

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 $\mathbb {G}_1$ and $\mathbb {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 [3] of Waters’ signature scheme [21] over asymmetric bilinear groups, which is secure under a variant of the computational Diffie-Hellman assumption, and the Naor-Reingold PRF [17], which is pseudo-random under DDH. Waters secret keys and Naor-Reingold PRF outputs are in $\mathbb {G}_1$.

In order to avoid additional assumptions on the PRF, we slightly modify the DAPS-DRS construction [11] (and call it DAPS-GS): to bind the signer to the value $\mathsf {sk}_\mathsf {PRF}$, we simply commitment to it in the public key using a commitment scheme $\mathcal {C}$. This lets us only rely on standard assumptions, while DRS had to assume that LowMC [1] is a fixed-value key-binding PRF.

In our variant DAPS-GS the language for the proof system is as follows:

$$ L=\left\{ (\mathsf {vk}_\varSigma ,\mathsf {pp}_\mathcal {C},C,a,p,z)~\left| ~\begin{array}{l}\exists \, (\mathsf {sk}_\varSigma ,\mathsf {sk}_\mathsf {PRF}): C=\mathsf {Cmt}(\mathsf {pp}_\mathcal {C},\mathsf {sk}_\mathsf {PRF})\\ \quad \wedge \;\mathsf {vk}_\varSigma =f(\mathsf {sk}_\varSigma )\, \wedge \,z=F(\mathsf {sk}_\mathsf {PRF},a)^p\cdot \mathsf {sk}_\varSigma \end{array}\right. \right\} $$

(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 Sect. 3, as shown in Table 1.