Keywords

1 Introduction

Tamper-proof hardware has gained a lot of interest in the design of UC-secure [5] protocols. Many cryptographic tasks that are impossible in the plain model can be realized using tamper-proof hardware, e.g. Program Obfuscation [2]. It turns out that several flavors of tamper-proof hardware have different cryptographic strengths. On the one hand there are stateful tokens, which allow for very efficient and UC-secure oblivious transfer (OT) protocols even without computational assumptions [14, 15, 19]. On the other hand, resettable, or equivalently stateless, tokens are strictly weaker: it was shown that unconditional OT cannot be achieved with stateless tokens [18]. Nevertheless the distinction between both models is very relevant, because in real-world applications it is considered to be much more difficult to manufacture stateful tamper-proof tokens than stateless or resettable tokens. Removing the dependency on stateful hardware by an improved protocol design can greatly simplify the manufacturing process and also reduce the costs. This leads to the following question:

Is it possible to implement any UC-functionality using a single resettable tamper-proof hardware and assuming only one-way functions?

We answer this question affirmatively. We shall first motivate the setting. There are protocol compilers by Kilian [25] and Ishai et al. [23] basing general (UC-)secure multi-party computation (MPC) on OT without additional computational assumptions. Recent results in the area of efficient information-theoretically secure OT protocols include [14, 15]. Their results, however, are based on stateful tamper-proof hardware. Considering the above-mentioned impossibility result of Goyal et al. [18], who show that unconditionally secure OT with any number of resettable tokens is impossible, it becomes obvious that converting a protocol like [15] such that only resettable tokens are necessary cannot be achieved without further assumptions.

One of the weakest common assumptions in cryptography is the existence of one-way functions and it turns out that these suffice for our goal. It was previously known that one-way functions suffice for UC-secure OT with stateless tokens [19], but they need many tokens to obtain this result. For our solution, instead of adapting an OT protocol such that it uses a resettable token, we present two compilers that transform any protocol based on stateful tokens into a protocol based on resettable tokens. This allows for many improvements in previous protocols, because any statistically secure protocol using a single untrusted stateful token can be transformed into a computationally secure protocol using a single untrusted resettable token and one-way functions.

1.1 Our Contribution

We present two compilers that basically use the same technique to achieve resettability of the token: The sender has to authenticate the query that the receiver wants to input into the token. For the first compiler, we generalize and improve upon a technique that is implicit in [17], where resettability is obtained by having the sender sign every query the receiver will provide to the token. The second compiler is stated in the OT-hybrid model and makes no further assumptions.

In more detail, given a protocol where a stateful token is sent from the sender to the receiver, we extend the protocol as follows. For the first compiler, a key pair for a signature scheme is created by the sender. For each token invocation, the receiver commits to its input and sends the commitment to the sender. The sender signs the commitment and sends it back to the receiver. At this point, care must be taken not to introduce a channel between the sender and the token. Otherwise, the token and/or the sender party could gather complete information about the messages sent and received by the receiver party. This would make aborts possible that are correlated with the receivers secret input and thus cannot be simulated in the UC framework. Therefore, the receiver does not show any signature to the token, but instead provides a resettably-sound zero-knowledge argument of knowledge (rsZKAoK) of the commitment and the signature. Recent results by Chung et al. [9] and Bitansky and Paneth [3] show that such resettably-sound zero-knowledge arguments of knowledge can be based on the existence of one-way functions. This technique guarantees that any information generated by the sender during a protocol run remains oblivious to the token.

Additionally, we present a compiler that works in the OT-hybrid model (without any computational assumptions) and can, e.g., be used to implement many OT instances from few “seed OTs” and a resettable token. The raw version of this compiler uses one OT per bit sent from the receiver to the token, but by using Merkle trees (or sig-com trees [9] respectively; see Sect. 2.5), we can compress the number of bits to be authenticated. The main idea is that the sender only has to authenticate a single message of small size, namely the root of such a tree. To stay true to the goal of using only one-way functions, however, we cannot directly use a Merkle tree. Instead, we show how the sig-com scheme proposed by [9] can be applied to our scenario. The same compression technique applies to both our compilers, which also allows us to keep the amount of proofs for the rsZKAoK-based compiler at a minimum. For protocols that use more than one token, our compilers can be invoked successively, replacing all the stateful tokens by resettable tokens.

Our rsZKAoK-based compiler can be used to obtain several improvements on existing protocols concerning resettable hardware. We highlight the following contribution: The combination of the OT protocol by Döttling et al. [15] with our compiler yields a round-efficient OT protocol based on one-way functions and a single untrusted resettable token. This yields the first OT-protocol using a single resettable token and only symmetric computational assumptions. Prior to our result, the best known approach to obtain UC-secure OT with a single resettable token was to use the token to generate a common reference string [17] and use an efficient OT-protocol in the CRS-model, e.g. the protocol of Peikert et al. [30]. Implementing OT in the common reference string model, however, requires much stronger computational assumptions (e.g., doubly enhanced trapdoor permutations, number-theoretic or lattice assumptions). Alternatively, [19] presented a protocol for OT based on resettable hardware and one-way functions, but their construction needs polynomially many tokens. Thus the question of obtaining OT from a single resettable hardware token using only one-way functions was left open by prior works.

Döttling et al. [17] and Choi et al. [8] showed that, if only a single resettable token is issued, then even simple functionalities cannot be implemented only with black-box techniques. We circumvent this impossibility result by using resettably-sound zero-knowledge argument of knowledge, which are inherently non-black-box. Moreover, Goyal et al. [18] showed there exists no unconditionally secure protocol implementing OT using any number of resettable tokens. Thus, computational assumptions are necessary to implement OT using a single resettable token. Considering the computational assumptions and number of resettable tokens used, our compiler yields an optimal UC-secure OT-protocol.

1.2 Efficiency

The compilers require one round of interaction between the token issuer and the receiver per token message. With a few exceptions in the area of non-interactive computation [15, 17, 19], protocols based on tamper-proof hardware already require interaction between the sender and the receiver. Moreover, in the scenario of a single token, Döttling et al. [17] show that interaction is necessary to UC-realize any functionality based on resettable hardware. Thus the induced overhead is minimal with respect to communication, even more so since typically token-based protocols are constant round.

The main efficiency drawback is incurred by the use of non-black-box zero-knowledge. However, in current protocols [3, 9] the honest prover is not required to execute a universal argument, so that the efficiency is comparable to a general zero-knowledge protocol. With a zero-knowledge protocol tailored to the statements in our protocol the efficiency can be further improved.

1.3 Further Related Work

The model of tamper-proof hardware considered in this paper was introduced by Katz [24]. Further formalizations of different tamper-proof hardware tokens can be found in [17, 19]. Physically uncloneable functions (PUFs) [4, 28, 29] only allow for MPC if the PUFs are not malicious  [10, 33], but this is out of the scope of our work.

Resettability was first considered in the context of zero-knowledge protocols. The case of a resettable prover was analyzed by Canetti et al. [6] while the case of resettable verifiers was treated by Barak et al. [1] with several follow up works, e.g. [3, 9, 13]. Later, simultaneously resettable zero-knowledge protocols were presented [3, 12, 13]. These works made it possible to transform stateful into stateless protocols. Goyal and Sahai [21] present a compiler that transforms any semi-honest secure protocol into a resettably secure protocol using similar techniques to ours. They also show that general resettable MPC with honest majority is possible where all parties are resettable. Another compiler due to Goyal and Maji [20] allows to compile almost any semi-honest secure protocol into a fully resettable protocol. However, neither [21] nor [20] achieve UC-security.

While all of the above-mentioned works do not make use of tamper-proof hardware, Chandran et al. [7] present a protocol for general UC-secure MPC with resettable tokens, but they need to exchange several tokens and rely on strong cryptographic assumptions, namely enhanced trapdoor permutations. Goyal et al. [19] construct a protocol for UC-secure MPC assuming only one-way functions, but they also need polynomially many resettable tokens.

In the context of statistically UC-secure OT, Goyal et al. [19] present a protocol using several stateful tokens. The protocols of Döttling et al. [14, 15] improve upon this result by achieving UC-secure OT using only a single stateful token. In [18] it was shown that statistically secure OT is impossible with stateless tokens (unless parties can encapsulate tokens into each other), but statistical commitments are possible. Their commitment construction was improved by [11] to achieve UC-security. Given an upper bound on the number of resets, Döttling et al. [16] show that resettable tamper-proof hardware allows for unconditionally UC-secure OT. Another recent result by [8] implements UC-secure OT from CRHFs and two bidirectionally exchanged stateless tokens. Leaky tokens, which reveal additional information to malicious receivers, were considered in [2, 31], but this is again out of the scope of our work.

2 Preliminaries

In the following we denote by k a security parameter. We abbreviate probabilistic polynomial time by PPT. We use the standard notions of negligible functions, statistical indistinguishability and computational indistinguishability.

2.1 The UC-Framework

The Universal Composability (UC) framework was introduced by Canetti [5]. It differentiates between an ideal model and a real model. In the real model an adversary \(\mathcal {A}\) coordinates the behavior of all corrupted parties while the uncorrupted parties follow the protocol. An environment \(\mathcal {Z}\) representing an outside observer can read all messages and outputs of the protocol parties. The same setup also holds for the ideal model, but the adversary is replaced by a simulator \(\mathcal {S}\) that simulates the behavior of \(\mathcal {A}\), and all participating parties are replaced by dummy parties that only pass on any message that they receive. Security is proven by comparing a protocol \(\varPi \) in the real model with an ideal functionality \(\mathcal {F}\) in the ideal model. An ideal functionality is secure per definition and represents a trusted third party that provides a functionality. All communication between a protocol party and the ideal functionality is assumed to be authenticated. Tamper-proof hardware is also modeled as an ideal functionality, further details can be found in Sect. 3.

By \(\mathsf{Real}_{\varPi }^{\mathcal {A}}(\mathcal {Z})\) we denote the output of the environment \(\mathcal {Z}\) when interacting with the real model, by \(\mathsf{Ideal}_{\mathcal {F}}^{\mathcal {S}}(\mathcal {Z})\) we denote the output of \(\mathcal {Z}\) when interacting with the ideal model. A protocol is said to compose securely if for any environment \(\mathcal {Z}\), which is plugged to either the ideal model or the real model, the view is (computationally, statistically or perfectly) indistinguishable.

We assume static corruption (i.e. the adversary does not adaptively change corruption) and prove our results in this framework.

2.2 Signature Schemes

A signature scheme \(\mathsf{SIG}\) consists of three PPT algorithms KeyGen, Sign and Verify.

  • \(\mathsf{KeyGen}(1^k)\) generates a key pair consisting of a verification key \(\mathsf{vk}\) and a signature key \(\mathsf{sgk}\).

  • \(\mathsf{Sign}_{\mathsf{sgk}}(m)\) takes a message m and outputs a signature \(\sigma \) on this message.

  • \(\mathsf{Verify}_{\mathsf{vk}}(m, \sigma )\) takes as input a verification key \(\mathsf{vk}\), a message m and a presumed signature \(\sigma \) on this message. It outputs 1 if the signature is correct and 0 otherwise.

We will use existentially unforgeable (EUF-CMA secure) signatures and will briefly recall the security definition. The experiment creates a key pair \((\mathsf{sgk},\mathsf{vk})\). An adversary \(\mathcal {A}\) has access to a verification key \(\mathsf{vk}\) and a signing oracle \(\mathcal {O}^{\mathsf{Sign}_{\mathsf{sgk}}(\cdot )}\). The adversary can now query the oracle with messages and obtains signatures to these messages. If \(\mathcal {A}\) manages to create a signature \(\sigma ^{*}\) for an arbitrary message m without querying \(\mathcal {O}^{\mathsf{Sign}_{\mathsf{sgk}}(\cdot )}\) with m such that \(\mathsf{Verify}_{\mathsf{vk}}(m,\sigma ^{*}) = 1\) it wins the experiment.

A signature scheme \(\mathsf{SIG}\) is called EUF-CMA-secure if the probability that a PPT adversary wins the above specified experiment is negligible. EUF-CMA secure signature schemes can be constructed from one-way functions [27, 32].

2.3 Commitment Schemes

We will use 2-move commitment schemes in our compiler. In such a commitment-scheme, the receiver first chooses a key k, sends k to the sender of the commitment, who computes a commitment \(c = \textsf {com}_k(m;r)\) for a message m using randomness r and sends c to the receiver. The sender can unveil the commitment by sending (m, r) to the receiver, who checks if \(c = \textsf {com}_k(m;r)\) holds.

We will require such a commitment scheme to be statistically binding, which means that for a given commitment \(c = \textsf {com}_k(m;r)\), the unveil (m, r) is unique, except with negligible probability over the choice of k. Naor [26] constructs 2-move statistically binding commitment schemes using only pseudorandom generators, if one considers their first message from the receiver as the key. As the latter can be constructed from one-way functions [22], this yields a 2-move statistically binding commitment scheme based on one-way functions.

2.4 Resettably-Sound Zero-Knowledge Arguments of Knowledge

Due to the fact that our protocol runs in the resettable token model, we use resettably-sound zero-knowledge arguments of knowledge for our proofs. We give a definition for resettably-sound zero-knowledge arguments of knowledge.

Definition 1

A resettably-sound zero-knowledge argument of knowledge system for a language \(L \in \mathcal {NP}\) (with witness-relation \(\mathcal {R}_L\) and witness-set \(w_L(x) = \{ w : (x,w) \in R_L \}\)) consists of a pair of PPT-machines \((\mathsf{P},\mathsf{V})\), where the verifier \(\mathsf{V}\) is resettable, such that there exist two PPT-machines \(\mathsf{Sim}\) and \(\mathsf{Ext}\) and the following conditions hold.

  • Completeness. For every \((x,w) \in \mathcal {R}_L\) it holds that \(\Pr [ \langle \mathsf{P}(w), \mathsf{V} \rangle (x) = 1] = 1\).

  • Computational Soundness. For every \(x \notin L\) and every PPT-machine \(\mathsf{P}^*\) it holds that \(\Pr [ \langle \mathsf{P}^*, \mathsf{V} \rangle (x) = 1] < \mathsf{negl}(|x|)\).

  • Computational Zero-Knowledge. For every \((x,w) \in \mathcal {R}_L\) and every stateful or resettable PPT \(\mathsf{V}^{*}\) it holds that the distributions \(\mathsf{Real}= \{ \langle \mathsf{P}(w), \mathsf{V}^{*} \rangle (x) \}\) and \(\mathsf{Ideal}= \{ \mathsf{Sim}(x,\mathsf{V}^*) \}\) are computationally indistinguishable.

  • Proof of Knowledge. For every \(x \in L\) and every PPT-machine \(\mathsf{P}^*\) there exists a negligible \(\nu \) such that \(\Pr [\mathsf{Ext}(x,\mathsf{P}^*) \in w_{L}(x)] > \Pr [\langle \mathsf{P}^*, \mathsf{V} \rangle (x) = 1] - \nu \).

It will be convenient to rephrase the computational zero-knowledge property as follows. Given that a simulator \(\mathsf{Sim}\) exists with \(\{ \langle \mathsf{P}(w), \mathsf{V}^{*} \rangle (x) \} \approx _c \{ \mathsf{Sim}(x,\mathsf{V}^*) \}\), we can always construct a prover-simulator \(\mathsf{P}_\mathsf{Sim}\) such that it holds that \(\{ \langle \mathsf{P}(w), \mathsf{V}^{*} \rangle (x) \} \approx _c \{ \langle \mathsf{P}_\mathsf{Sim}(\mathsf{V}^*), \mathsf{V}^{*} \rangle (x) \}\). Such a prover-simulator can be constructed as follows. \(\mathsf{P}_\mathsf{Sim}\) first runs \(\mathsf{Sim}(x,\mathsf{V}^*)\) to obtain a simulated view of \(\mathsf{V}^*\). From this view it takes the prover-messages and uses these prover-messages in its own interaction with \(\mathsf{V}^*\). Thus it holds \(\{ \langle \mathsf{P}_\mathsf{Sim}(\mathsf{V}^*), \mathsf{V}^{*} \rangle (x) \} \approx _c \{ \mathsf{Sim}(x,\mathsf{V}^*) \}\) and we are done.

Recent constructions of rsZK arguments of knowledge are based on one-way functions [3, 9].

2.5 Sig-Com Schemes

As an alternative to collision resistant hash functions, Chung et al. [9] propose sig-com schemes. They show that such a scheme is compressing and has a collision resistance property similar to collision resistant hash functions, but requires only one-way functions. In comparison to hash functions, however, sig-com schemes require interaction between two parties: one party creates the signature and verification keys, and sends the verification key to the other party. The other party sends a commitment to its input and obtains a signature on the commitment, i.e. the party with the signature key acts as a signature oracle. This separation is due to the fact that if the party that holds the input for the sig-com tree also possesses the secret key to the signature scheme, the security of the signature scheme (and hence the collision resistance property) does no longer hold. The commitments to the input are necessary, because otherwise the sender could abort depending on the received message. The commit-then-sign step can be applied to create a tree analogous to Merkle trees.

Definition 2

([9]). Let \(\mathsf{SIG} = (\mathsf{Gen},\mathsf{Sign},\mathsf{Verify})\) be a strong length-n signature scheme and let \(\mathsf{com}\) be a non-interactive commitment scheme. Define \(\mathsf{SIG}^{\prime } = (\mathsf{Gen}^\prime ,\mathsf{Sign}^\prime ,\mathsf{Verify}^\prime )\) to be a triple of PPT machines defined as follows:

  • \(\mathsf{Gen}^\prime = \mathsf{Gen}\).

  • \(\mathsf{Sign}_{\mathsf{sgk}}^\prime (m)\): compute a commitment \(c = \mathsf{com}(m;r)\) using a uniformly selected r, and let \(\sigma = \mathsf{Sign}_\mathsf{sgk}(c)\); output \((\sigma ,r)\).

  • \(\mathsf{Verify}^\prime _{\mathsf{vk}}(m,\sigma ,r)\): output 1 iff \(\mathsf{Verify}_{\mathsf{vk}}(\mathsf{com}(m;r),\sigma ) = 1\).

Definition 3

([9]). Let \(\mathsf{SIG} = (\mathsf{Gen},\mathsf{Sign},\mathsf{Verify})\) be a strong length-n signature scheme, let \(\mathsf{com}\) be a non-interactive commitment scheme, and let \(\mathsf{SIG}^{\prime } = (\mathsf{Gen}^\prime ,\mathsf{Sign}^\prime ,\mathsf{Verify}^\prime )\) be the sig-com scheme corresponding to \(\mathsf{SIG}\) and \(\mathsf{com}\). Let \((\mathsf{sgk},\mathsf{vk})\) be a key pair of \(\mathsf{SIG}^\prime \), and s be a string of length \(2^d\). A sig-com tree for s w. r. t. \((\mathsf{sgk},\mathsf{vk})\) is a complete binary tree of depth d, defined as follows.

  • A leaf \(l_\gamma \) indexed by \(\gamma \in \{0,1\}^d\) is set as the bit at position \(\gamma \) in s.

  • An internal node \(l_\gamma \) indexed by \(\gamma \in \bigcup ^{d-1}_{i=0}\{0,1\}^i\) satisfies that there exists some \(r_\gamma \) such that \(\mathsf{Verify}^\prime _{\mathsf{vk}}((l_{\gamma _0},l_{\gamma _1}),l_\gamma ,r_\gamma ) = 1\). (By \(l_{\gamma _0},l_{\gamma _1}\) we denote the left and right child of an inner node \(l_\gamma \).)

Note that sig-com trees have a collision resistance property in the following sense: no adversary with oracle access to a signature oracle \(\mathsf{SIG}\) can output a root and a sequence of signatures for both 0 and 1 for any leaf \(\gamma \). This property stems from the binding property of the commitment and the unforgeability of the signature scheme.

3 Ideal Functionalities

In this section we define the ideal functionalities we will use later. Here we only consider the two-party case with a sender S and a receiver R. The following definition for a stateful wrapper functionality is based on [19, 24].

Functionality \(\mathcal {F}^{\mathrm {stateful}}_{\mathrm {wrap}}\) (parametrized by a security parameter k and a polynomial runtime bound \(p(\cdot )\)).

  • Create Upon receiving \((\mathtt {create}, \mathcal {P},p(\cdot ))\) from S, where \(\mathcal {P}\) is a Turing machine, send \(\mathtt {create}\) to R and store \(\mathcal {P}\).

  • Execute Upon receiving \((\mathtt {run}, w)\) from R, check if a \(\mathtt {create}\)-message has already been sent by S, if not output \(\bot \). Run \(\mathcal {P}(w)\) for at most p(k) steps, and let m be the output. Save the current state of \(\mathcal {P}\). Output m to R

We use the wrapper functionality for resettable functionalities as defined in [17].

Functionality \(\mathcal {F}^{\mathrm {resettable}}_{\mathrm {wrap}}\) (parametrized by a security parameter k and a polynomial runtime bound \(p(\cdot )\)).

  • Create Upon receiving \((\mathtt {create}, \mathcal {P},p(\cdot ))\) from S, where \(\mathcal {P}\) is a Turing machine, send \(\mathtt {create}\) to R and store \(\mathcal {P}\).

  • Execute Upon receiving \((\mathtt {run}, w)\) from R, check if a \(\mathtt {create}\)-message has already been sent by S, if not output \(\bot \). Run \(\mathcal {P}(w)\) for at most p(k) steps, and let m be the output. Save the current state of \(\mathcal {P}\). Output m to R

  • Reset (Adversarial Receiver only) Upon receiving \(\mathtt {reset}\) from \(\mathsf{R}\), reset the Turing machine \(\mathcal {P}\) to its initial state.

In the sequel, we will use the notation \(\mathcal {P}\) for programs (given as code, Turing-machine etc.) and \(\mathcal {T}\) for the instance of the wrapper-functionality \(\mathcal {F}^{\mathrm {resettable}}_{\mathrm {wrap}}\), resp. \(\mathcal {F}^{\mathrm {stateful}}_{\mathrm {wrap}}\), in which \(\mathcal {P}\) runs.

4 Compiler

In the following we present two compilers that allow to convert a protocol that makes a single call to a stateful token into a protocol that uses a resettable token.

We need to make some assumptions on the structure of the underlying stateful protocol \(\varPi _s\). W.l.o.g the protocol can be divided into the following phases.

  • A setup phase in which the sender sends a token program \(\mathsf{T}\) to \(\mathcal {F}^{\mathrm {stateful}}_{\mathrm {wrap}}\).

  • Communication between the sender and the receiver.

  • An invocation of the token by the receiver.

The token program from the setup phase will be used in the resettable protocol as well, albeit the setup phase will be extended by additional steps. Any interaction between the two parties of the protocol (not the communication with the token) will be left untouched.

The basic idea underlying our compilers is to let the sender authenticate the message for the token, while being oblivious of what the actual message to the token is. Instead of invoking the stateful token in the underlying protocol directly, we will additionally insert a communication step with the sender. Though the receiver can still perform reset-attacks, it will not be able to change its input after a reset.

We will assume that the input protocol \(\varPi _s\) has dummy-messages \(\mathtt {query}\) and \(\mathtt {ack}\), where an honest receiver sends the message \(\mathtt {query}\) to the sender before querying the token, and waits until the sender replies with \(\mathtt {ack}\) before proceeding. We do not require a corrupted receiver to send the \(\mathtt {query}\) message before querying the token. Therefore any protocol \(\varPi _s\) can be converted into this form, while preserving its security guarantees.

4.1 Protocol Using Resettably-Sound Zero-Knowledge

Outline. The compiler \(\mathcal {C}_{\text {ZK}}\) (cf. Fig. 1) alters the underlying protocol as follows. Before the execution of \(\varPi _s\) a signature key-pair \((\mathsf{sgk},\mathsf{vk})\) and a key k for a commitment scheme (cf. Sect. 2.3) are created by the sender and sent to the receiver. Then \(\varPi _s\) is carried out. When the token code of the underlying protocol is sent to the wrapper functionality, the sender chooses a seed s for a pseudorandom function and constructs a new token.

During token invocation of the original protocol, we enhance the communication of the token and the receiver as follows. Instead of just sending an input \(\mathsf{inp}\) to the token, the receiver first commits to its input \(\mathsf{inp}\) and sends the commitment to the sender. The sender then computes a signature \(\sigma \) on the commitment c and sends the signature to the receiver. Now the receiver checks if the signature is valid and queries the token with its input. Additionally, the receiver starts a resettably-sound zero-knowledge argument of knowledge to prove that it knows a signature on a commitment to the input. If the verifier accepts, the token outputs the output \(\mathsf{out}\) of the underlying functionality on input \(\mathsf{inp}\).

We stress that it is essential that the token cannot learn the signature \(\sigma \) on the commitment c, otherwise both token and sender have a covert channel by which they can communicate, which cannot be simulated. To eliminate this channel, we use a zero-knowledge proof which hides the signature from the token.

Fig. 1.
figure 1

Stateless compiler using resettably-sound zero-knowledge.

Full size image

Proof of Security. Corrupted Receiver. Let \(\mathcal {A}_{\mathsf{R}}\) be the dummy-adversary for a corrupted receiver for the protocol \(\varPi _r\). We will construct an adversary \(\mathcal {A}_\mathsf{R}^\prime \) (cf. Fig. 2) against the protocol \(\varPi _s\). \(\mathcal {A}_\mathsf{R}^\prime \) needs to simulate a resettable token to \(\mathcal {A}_\mathsf{R}\), while it has itself access to a non-resettable stateful token.

Fig. 2.
figure 2

Adversary-simulator \(\mathcal {A}_{\mathsf{R}}^\prime \) for \(\mathcal {C}_{\text {ZK}}\).

Full size image

Lemma 1

For every PPT-environment \(\mathcal {Z}\), it holds that the random variables \(\mathsf{Real}^{\mathcal {A}_{\mathsf{R}}}_{\varPi _{r}}(\mathcal {Z})\) and \(\mathsf{Real}^{\mathcal {A}_{\mathsf{R}}^\prime }_{\varPi _{s}}(\mathcal {Z})\) are computationally indistinguishable.

As \(\varPi _s\) is UC-secure, there exists a simulator \(\mathcal {S}_\mathsf{R}\) such that \(\mathsf{Real}^{\mathcal {A}_{\mathsf{R}}^\prime }_{\varPi _{s}}(\mathcal {Z}) \approx \mathsf{Ideal}_\mathcal {F}^{\mathcal {S}_\mathsf{R}}(\mathcal {Z})\). This yields the desired \(\mathsf{Real}^{\mathcal {A}_{\mathsf{R}}}_{\varPi _{r}}(\mathcal {Z}) \approx \mathsf{Ideal}_\mathcal {F}^{\mathcal {S}_\mathsf{R}}(\mathcal {Z})\).

Proof

Let \(\mathcal {Z}\) be a PPT environment. We will prove the indistinguishability of \(\mathsf{Real}^{\mathcal {A}_{\mathsf{R}}}_{\varPi _{r}}(\mathcal {Z})\) and \(\mathsf{Real}^{\mathcal {A}_{\mathsf{R}}^\prime }_{\varPi _{s}}(\mathcal {Z})\) by a series of indistinguishable hybrid experiments.

  • Hybrid \(\mathcal {H}_0\mathbf{.}\) Simulator \(\mathcal {S}_0\) simulates \(\mathsf{Real}^{\mathcal {A}_{\mathsf{R}}}_{\varPi _{r}}\).

  • Hybrid \(\mathcal {H}_1\mathbf{.}\) Identical to \(\mathcal {H}_0\), except that simulator \(\mathcal {S}_1\) replaces the pseudo"-random-function \(\mathsf{F}_s(\cdot )\) by a random-oracle \(\mathsf{H}\).

  • Hybrid \(\mathcal {H}_2\mathbf{.}\) Identical to \(\mathcal {H}_1\), except for the following. \(\mathcal {S}_2\) checks – after \(\mathsf{V}\) accepts – if a tuple \((\mathsf{inp}^\prime ,\mathsf{out}^\prime )\) has already been stored. If so and \(\mathsf{inp}^\prime \ne \mathsf{inp}\), it aborts. Moreover, if no such tuple exists it will store \((\mathsf{inp},\mathsf{out})\), where \(\mathsf{out}\) is the output of the token. From the view of \(\mathcal {Z}\), this is identical to \(\mathsf{Real}^{\mathcal {A}_{\mathsf{R}}^\prime }_{\varPi _{s}}\).

Computational indistinguishability of \(\mathcal {H}_0\) and \(\mathcal {H}_1\) follows straightforwardly by the pseudorandomness of the pseudorandom-function \(\mathsf{F}_s\). The interesting part is the computational indistinguishability of \(\mathcal {H}_1\) and \(\mathcal {H}_2\).

We claim that \(\mathcal {H}_1\) and \(\mathcal {H}_2\) are computationally indistinguishable, provided that the argument system \((\mathsf{P},\mathsf{V})\) fulfills the computational resettable soundness property, the commitment scheme \(\textsf {com}\) is statistically binding and the signature scheme \(\mathsf{SIG}\) is EUF-CMA secure.

Clearly, if \(\mathcal {S}_2\) does not abort after \(\mathsf{V}\) accepts, the views of \(\mathcal {Z}\) are identical in \(\mathcal {H}_1\) and \(\mathcal {H}_2\). We will thus show that this event happens at most with negligible probability, establishing indistinguishability of \(\mathcal {H}_1\) and \(\mathcal {H}_2\).

Since the commitment-scheme \(\textsf {com}\) is statistically binding, the event that there exist distinct \((\mathsf{inp}_1,r_1)\) and \((\mathsf{inp}_2,r_2)\) with \(\textsf {com}_k(\mathsf {inp}_1;r_1) = \textsf {com}_k(\mathsf {inp}_2;r_2)\) has only negligible probability (over the choice of k). We can thus assume that each commitment c has a unique unveil \((\mathsf {inp},r)\).

Assume now that the probability that \(\mathcal {S}_2\) aborts after \(\mathsf {V}\) accepts is non-negligible. We distinguish two cases:

  1. 1.

    The probability \(\epsilon \) that \(\mathcal {A}_\mathsf {R}\) successfully proves a false statement in one of the invocations of \((\mathsf {P},\mathsf {V})\) is non-negligible.

  2. 2.

    The probability \(\epsilon \) that \(\mathcal {A}_\mathsf {R}\) successfully proves a false statement in one of the invocations of \((\mathsf {P},\mathsf {V})\) is negligible.

In the first case, we can construct a corrupted prover \(\mathsf {P}^*\) that breaks the soundness property of the argument-system \(\mathsf {P},\mathsf {V}\). \(\mathsf {P}^*\) simulates \(\mathcal {S}_1\) faithfully until the argument-system \((\mathsf {P},\mathsf {V})\) is started. Then, \(\mathsf {P}^*\) announces the statement \((\mathsf{vk},\mathsf {inp})\) and forwards all messages sent by \(\mathcal {A}_{\mathsf {R}}\) to his own verifier \(\mathsf {V}\) and vice versa. Clearly, from \(\mathcal {A}_{\mathsf {R}}\)’s (and thus \(\mathcal {Z}\)’s) view, \(\mathcal {S}_1\) and \(\mathsf {P}^*\)’s simulation are identically distributed. Thus, \(\mathsf {P}^*\)’s chance of successfully proving a false statement is at least \(\epsilon \), contradicting the soundness property of \((\mathsf {P},\mathsf {V})\).

In the second case, we will argue that \(\mathcal {A}_{\mathsf {R}}\) must be able to successfully forge a signature \(\sigma \) for a message c, contradicting the EUF-CMA security of \(\mathsf {SIG}\). We will therefore construct an adversary \(\mathcal {B}\) that breaks the EUF-CMA security of \(\mathsf {SIG}\) with non-negligible probability, leading to the desired contradiction. Let \(\mathsf {Ext}\) be a knowledge-extractor for the argument-of-knowledge system \((\mathsf {P},\mathsf {V})\). \(\mathcal {B}\) simulates \(\mathcal {S}_2\) faithfully except for the following. Instead of generating \((\mathsf{sgk},\mathsf{vk})\) itself, it will use \(\mathsf{vk}\) provided by the EUF-CMA experiment. \(\mathcal {B}\) uses \(\mathcal {A}_{\mathsf {R}}\) and \(\mathcal {Z}\) to construct a malicious prover \(\mathsf {P}^*\), which simply consists in continuing the computation of \(\mathcal {A}_{\mathsf {R}}\) and \(\mathcal {Z}\) until the argument-system terminates. \(\mathcal {B}\) now runs the extractor \(\mathsf {Ext}\) on \(\mathsf {P}^*\) and obtains a witness \((\sigma ^*,c^*,r^*)\) for a statement \((\mathsf{vk},\mathsf {inp}^*)\). If it holds \(\mathsf {Verify}_\mathsf{vk}(c^*,\sigma ^*) = 1\), then \(\mathcal {B}\) outputs the forge \((c^*,\sigma ^*)\). Otherwise it outputs \(\bot \).

Clearly, from the view of \(\mathcal {Z}\), both \(\mathcal {S}_2\) and \(\mathcal {B}\)’s simulation are identically distributed. Since we assume that \(\mathcal {S}_2\) aborts with non-negligible probability and \(\mathsf {P}^*\) proves a true statement, except with negligible probability, the extractor \(\mathsf {Ext}\) returns a witness \((\sigma ^*,c^*,r^*)\) with non-negligible probability. As we conditioned on the event that \(\mathcal {S}_2\) aborts and the commitment \(c^*\) has a unique unveil, it must hold that \((c^*,\sigma ^*)\) is, with non-negligible probability, a valid forge. This however contradicts the EUF-CMA security of \(\mathsf {SIG}\), which concludes the proof.    \(\square \)

Corrupted Sender. We move on to prove the security against a corrupted sender by stating a simulator (cf. Fig. 3).

Fig. 3.
figure 3

Adversary-simulator \(\mathcal {A}_{\mathsf {S}}^\prime \) for \(\mathcal {C}_{\text {ZK}}\).

Full size image

Lemma 2

For every PPT-environment \(\mathcal {Z}\), it holds that the random variables \(\mathsf {Real}^{\mathcal {A}_{\mathsf {S}}}_{\varPi _{r}}(\mathcal {Z})\) and \(\mathsf {Real}^{\mathcal {A}_{\mathsf {S}}^\prime }_{\varPi _{s}}(\mathcal {Z})\) are computationally indistinguishable.

Again, as \(\varPi _s\) is UC-secure, there exists a simulator \(\mathcal {S}_\mathsf {S}\) such that \(\mathsf {Real}^{\mathcal {A}_{\mathsf {S}}^\prime }_{\varPi _{s}}(\mathcal {Z}) \approx \mathsf {Ideal}_\mathcal {F}^{\mathcal {S}_\mathsf {S}}(\mathcal {Z})\), which yields the desired \(\mathsf {Real}^{\mathcal {A}_{\mathsf {S}}}_{\varPi _{r}}(\mathcal {Z}) \approx \mathsf {Ideal}_\mathcal {F}^{\mathcal {S}_\mathsf {S}}(\mathcal {Z})\)

Proof

Let \(\mathcal {Z}\) be a PPT environment. We will prove the indistinguishability of \(\mathsf {Real}^{\mathcal {A}_{\mathsf {S}}}_{\varPi _{r}}(\mathcal {Z})\) and \(\mathsf {Real}^{\mathcal {A}_{\mathsf {S}}^\prime }_{\varPi _{s}}(\mathcal {Z})\) by a series of indistinguishable hybrid experiments.

  • Hybrid \(\mathcal {H}_0\) . Simulator \(\mathcal {S}_0\) simulates \(\mathsf {Real}^{\mathcal {A}_{\mathsf {S}}}_{\varPi _{r}}\).

  • Hybrid \(\mathcal {H}_1\) . Identical to \(\mathcal {H}_0\), except that during invocation of the token, \(\mathsf {R}\) does not setup and run a prover \(\mathsf {P}\) with input \((\mathsf{vk},\mathsf {inp})\) and witness-input \((\sigma ,c,r)\), but instead runs the prover-simulator \(\mathsf {P}_\mathsf {Sim}\) with input \((\mathsf{vk},\mathsf {inp})\) and witness-input \(\mathsf {V}^*\), where \(\mathsf {V}^*\) is a corrupted verifier that is constructed from \(\mathsf {T}^*\).

  • Hybrid \(\mathcal {H}_2\) . Identical to \(\mathcal {H}_1\), except that the commitment c sent to \(\mathcal {A}_\mathsf {S}\) is computed by \(c = \textsf {com}_k(0;r)\) instead of \(c = \textsf {com}_k(\mathsf {inp};r)\). From the view of \(\mathcal {Z}\), this is identical to \(\mathsf {Real}^{\mathcal {A}_{\mathsf {S}}^\prime }_{\varPi _{s}}\).

Indistinguishability of the hybrids \(\mathcal {H}_0\) and \(\mathcal {H}_1\) follows directly from the computational zero-knowledge property of the system \((\mathsf {P},\mathsf {V})\). Since the commitment scheme \(\textsf {com}\) is computationally binding, the hybrids \(\mathcal {H}_1\) and \(\mathcal {H}_2\) are computationally indistinguishable from the view of \(\mathcal {Z}\) as well. This can be established by a simple hybrid-argument, where a \(\mathcal {Z}\) distinguishing the two experiments can be used to break the hiding-property of \(\textsf {com}\).   \(\square \)

Remark 1

The above compiler can easily be extended to allow for multiple messages. Then, in each step of the token invocation the token receiver has to query the sender on a commitment and provide a proof to the token, that this commitment was signed by the sender. For each message, a counter is added such that the receiver cannot query the token “out-of-sync”. If the token is reset, its counter will not match the counter of the sender and thus the token will abort.

4.2 Protocol Using UC-Secure Seed-OTs

Outline. The compiler \(\mathcal {C}_{\text {OT}}\) depicted in Fig. 4 adds a step to the underlying protocol \(\varPi _s\), which authenticates the token input. This time, the authentication is done by using UC-secure OTs. Before the execution of \(\varPi _s\), the token sender creates two random strings \((s^i_0,s^i_1)\) for every bit of the message \(\mathsf {inp}\) that the receiver will input into the token. Let \(\mathsf {inp}(i)\) denote the i-th bit of \(\mathsf {inp}\). During the setup, the receiver obtains one of these random strings, namely \(s^i_{\mathsf {inp}(i)}\), for each of his input bits. Since the receiver does not learn any \(s^i_{1-\mathsf {inp}(i)}\), he is bitwise committed to his input, while the sender does not learn anything about it.

All random values \(((s^1_0,s^1_1),\ldots ,(s^k_0,s^k_1))\) that the sender created are stored in the token functionality. When the token is invoked on input \((\mathsf {inp},(s^1_{j_1},\ldots ,s^k_{j_k}))\), the tokens checks that these values are consistent with the random values of the OTs. If that is the case, the token will evaluate the underlying token functionality on \(\mathsf {inp}\) and forward the output \(\mathsf {out}\).

Fig. 4.
figure 4

Stateless compiler using k seed-OTs.

Full size image

Proof of Security. Please note that the security reduction is information-theoretic, but depending on the realization of \(\mathcal {F}\), the protocol might still only be computationally secure.

Corrupted Receiver. Let \(\mathcal {A}_{\mathsf {R}}\) be the dummy-adversary for a corrupted sender for the protocol \(\varPi _r\). We will construct an adversary \(\mathcal {A}_{\mathsf {R}}^\prime \) against the protocol \(\varPi _s\) (cf. Fig. 5).

Lemma 3

For every (PPT-)environment \(\mathcal {Z}\), it holds that the random variables \(\mathsf {Real}^{\mathcal {A}_{\mathsf {R}}}_{\varPi _{r}}(\mathcal {Z})\) and \(\mathsf {Real}^{\mathcal {A}_{\mathsf {R}}^\prime }_{\varPi _{s}}(\mathcal {Z})\) are indistinguishable.

Proof

The only difference between \(\mathsf {Real}^{\mathcal {A}_{\mathsf {R}}}_{\varPi _{r}}(\mathcal {Z})\) and \(\mathsf {Real}^{\mathcal {A}_{\mathsf {R}}^\prime }_{\varPi _{s}}(\mathcal {Z})\) is the abort of \(\mathcal {A}_{\mathsf {R}}^\prime \) in case \(\mathsf {inp}^\prime \ne \mathsf {inp}\). For this event to happen, \(\mathcal {A}_{\mathsf {R}}\) has to guess a string \(s^i_j\in S\) of length \(\lambda \) for any \(i\in \{1,\ldots ,k\},j\in \{0,1\}\). The probability for this event is obviously negligible in the security parameter \(\lambda \).   \(\square \)

Since the protocol \(\varPi _s\) is UC-secure, there exists a simulator \(\mathsf {S}_{\mathsf {R}}\) such that \(\mathsf {Real}^{\mathcal {A}_{\mathsf {R}}^\prime }_{\varPi _{s}}(\mathcal {Z}) \approx \mathsf {Ideal}^{\mathcal {S}_{\mathsf {R}}}_{\mathcal {F}}(\mathcal {Z})\). Thus, \(\mathsf {Real}^{\mathcal {A}_{\mathsf {R}}}_{\varPi _{r}}(\mathcal {Z})\approx \mathsf {Ideal}^{\mathcal {S}_{\mathsf {R}}}_{\mathcal {F}}(\mathcal {Z})\) follows from the above lemma.

Fig. 5.
figure 5

Adversary-simulator \(\mathcal {A}_{\mathsf {R}}^\prime \) for \(\mathcal {C}_{\text {OT}}\).

Full size image

Corrupted Sender. Let \(\mathcal {A}_{\mathsf {S}}\) be the dummy-adversary for a corrupted sender for the protocol \(\varPi _r\). We will construct an adversary \(\mathcal {A}_{\mathsf {S}}^\prime \) against the protocol \(\varPi _s\) (cf. Fig. 6).

Fig. 6.
figure 6

Adversary-simulator \(\mathcal {A}_{\mathsf {S}}^\prime \) for \(\mathcal {C}_{\text {OT}}\).

Full size image

Lemma 4

For every (PPT-)environment \(\mathcal {Z}\), it holds that the random variables \(\mathsf {Real}^{\mathcal {A}_{\mathsf {S}}}_{\varPi _{r}}(\mathcal {Z})\) and \(\mathsf {Real}^{\mathcal {A}_{\mathsf {S}}^\prime }_{\varPi _{s}}(\mathcal {Z})\) are indistinguishable.

5 Optimizations

Recall that the compiler \(\mathcal {C}_{\text {ZK}}\) can straightforwardly be extended to allow for multiple messages between token and receiver. However, this would lead to an inefficient zero-knowledge proof for each message. Also, it seems difficult to change the compiler \(\mathcal {C}_{\text {OT}}\) such that it allows for more than a single message due to the fixed amount of seed-OTs.

In case that the receiver has non-adaptive queries for the token, these problems can be overcome. By non-adaptive queries, we mean that the i-th token query does not depend on the \((i-1)\)-th query. A very simple solution is to just concatenate all messages into a single message and have the sender authenticate this message. However, this needs quite a lot of seed-OTs and also the amount of data that has to be sent to the sender is very large.

A more refined solution to the problem is the following. Instead of using the normal token input as the message that shall be authenticated by the sender, the receiver computes a Merkle tree with all non-adative messages in the leaves. Then, the sender authenticates the root of the Merkle tree, and the receiver only has to use the compiler for the root message. From there on, for each of the initial non-adaptive messages he sends the path through the tree and the corresponding message to the token, which can verify that the path is consistent with the root.

This improvement leads to a single message of small size during the authentication step of \(\mathcal {C}_{\text {ZK}}\) and \(\mathcal {C}_{\text {OT}}\) respectively. This construction has one drawback: the Merkle tree relies on collision resistant hash functions. Considering our initial goal to achieve a compiler using only one-way functions, we replace the Merkle tree with the recent construction of sig-com trees [9].

We will briefly sketch how sig-com trees can be used in our scenario. Additionally to the normal setup, the token sender creates a key pair \((\mathsf {vk}_h,\mathsf {sk}_h)\) and extends the token functionality as follows. Upon receiving \((\mathtt {sign},x)\) the token returns \(\mathsf {Sign}_{\mathsf {sk}_h}(x)\), basically implementing a signature oracle. Further, upon receiving \((\mathtt {check},\mathsf {path})\), the token checks that \(\mathsf {path}\) constitutes a valid path given the root of a sig-com tree. The verification key \(\mathsf {vk}_h\) is given to the token receiver. The rest of the compiler is carried out as described above. During the protocol run, instead of directly giving the non-adaptive messages to the sender, the receiver first uses the resettable token to create a signature tree and verifies each obtained signature with \(\mathsf {vk}_h\). Since all inputs are committed to in advance of the oracle calls, the token does not learn the inputs. Then the rest of the protocol proceeds normally: The sender authenticates the root of the sig-com tree, and the receiver has to present a path through the sig-com tree for each of the non-adaptive messages.

Simulation of this enhancement against a corrupted sender is quite simple. Since the commitments on the receiver inputs are never opened (but only used in zero-knowledge arguments of knowledge), the simulator can still just pick all-zero inputs, then use the token to create a corresponding sig-com tree, and proceed as before. Our indistinguishability proofs for the original compilers just carry over; otherwise the commitments on the receiver inputs would not be hiding. If the receiver is corrupted, the binding property of the commitments on his inputs and the collision resistance of the sig-com tree guarantee that the token can still be queried only with messages that were authenticated by the sender. It follows again that our indistinguishability proofs for the original compilers just carry over.

6 Implications

In this section we will briefly discuss the implications of applying our compiler to existing protocols. We want to focus on UC-secure oblivious transfer protocols. Previous constructions based on resettable tokens were either dependent on the fact that several hardware tokens had to be exchanged [8] or made use of stronger computational assumptions [7]. In fact, it was shown that, using only black-box techniques, OT can only be achieved by exchanging two tokens [8] or by sending a large amount of tokens in one direction [7, 19].

The only known solution using a single resettable hardware token can be constructed by using the recent work of [17] (which makes inherent use of non-black-box techniques). They create a CRS with a single resettable token and by plugging in an efficient OT protocol in the CRS model, e.g. [30], an OT protocol using a single resettable token can be obtained. OT protocols in the CRS model, however, cannot be based on one-way functions and thus stronger cryptographic assumptions are needed. In the context of stateful tokens, very efficient constructions are known, e.g. [15]. By plugging the protocol of Döttling et al. [14, 15] into one of our compilers, we obtain the most efficient OT-protocol based on resettable hardware to date (the protocol of [14, 15] only gives an a priori fixed amount of OTs). The compiler \(\mathcal {C}_{\text {ZK}}\) uses non-black-box techniques, so the above-mentioned impossibility result does not hold. We can further improve the efficiency of this protocol by performing random OTs with non-adaptive token inputs. This allows us to use the optimization from Sect. 5, thereby making only a single call to the sender. Additionally, the compiler \(\mathcal {C}_{\text {OT}}\) allows to extend a fixed amount of UC-OTs (the seed-OTs of the compiler) to a (fixed but independent) number of UC-OTs by using the protocol of [14, 15].