Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

From Stateful Hardware to Resettable Hardware Using Symmetric Assumptions

Nico Döttling, Daniel Kraschewski, Jörn Müller‐Quade, Tobias Nilges

Published Jan 1, 2015• 7 citations
Publisher

Abstract

Universally composable multi-party computation is impossible without setup assumptions. Motivated by the ubiquitous use of secure hardware in many real world security applications, Katz (EUROCRYPT 2007) proposed a model of tamper-proof hardware as a UC-setup assumption. An important aspect of this model is whether the hardware token is allowed to hold a state or not. Real world examples of tamper-proof hardware that can hold a state are expensive hardware security modules commonly used in mainframes. Stateless, or resettable hardware tokens model cheaper devices such as smartcards, where an adversarial user can cut off the power supply, thus resetting the card’s internal state. A natural question is how the stateful and the resettable hardware model compare in their cryptographic power, given that either the receiver or the sender of the token (and thus the token itself) might be malicious. In this work we show that any UC-functionality that can be implemented by a protocol using a single untrusted stateful hardware token can likewise be implemented using a single untrusted resettable hardware token, assuming only the existence of one-way functions. We present two compilers that transform UC-secure protocols in the stateful hardware model into UC-secure protocols in the resettable hardware model. The first compiler can be proven secure assuming merely the existence of one-way functions. However, it (necessarily) makes use of computationally rather expensive non-black-box techniques. We provide an alternative second compiler that replaces the expensive non-black-box component of the first compiler by few additional seed OTs. While this second compiler introduces the seed OTs as additional setup assumptions, it is computationally very efficient.

DOI
10.1007/978-3-319-26059-4_2

Related papers

Round-Optimal Token-Based Secure Computation.

Carmit Hazay, Antigoni Polychroniadou, Muthuramakrishnan Venkitasubramaniam

Secure computation in the presence of tamper-proof hardware tokens is proven under the assumption that the holder of the token is only given black-box access to the functionality of the token. Starting with the work of Goldreich and Ostrovsky [GO96], a long series of works studied tamper-proof hardware for realizing two-party functionalities in a variety of settings. In this work we focus our attention on two important complexity measures of stateless token-based secure computation: round complexity and hardness assumptions and present the following results in the two-party setting: • A round optimal generic secure protocol in the plain model assuming one-way functions, where the tokens are created by a single party. • A round optimal generic UC secure protocol assuming one-way functions. Our constructions are proven in the real/ideal paradigm with security in the presence of static malicious adversaries. As a side contribution, we identify a flaw in one of the feasibility results regarding UC secure protocols in the tamper proof model proved in the work of Goyal, Ishai, Sahai, Venkatesan and Wadia (TCC 2010) and correct history by attributing the work of Choi, Katz, Schroöder, Yerukhimovic and Zhou (TCC 2014) to establishing the (same) feasibility result.

•Jan 1, 2015•0 citations

New Constructions for UC Secure Computation using Tamper-proof Hardware.

Nishanth Chandran, Vipul Goyal, Amit Sahai

The Universal Composability framework was introduced by Canetti to study the security of protocols which are concurrently executed with other protocols in a network environment. Unfortunately it was shown that in the so called plain model, a large class of functionalities cannot be securely realized. These severe impossibility results motivated the study of other models involving some sort of setup assumptions, where general positive results can be obtained. Until recently, all the setup assumptions which were proposed required some trusted third party (or parties). Katz recently proposed using a physical setup to avoid such trusted setup assumptions. In his model, the physical setup phase includes the parties exchanging tamper proof hardware tokens implementing some functionality. The tamper proof hardware is modeled so as to assume that the receiver of the token can do nothing more than observe its input/output characteristics. It is further assumed that the sender knows the program code of the hardware token which it distributed. Based on the DDH assumption, Katz gave general positive results for universally composable multi-party computation tolerating any number of dishonest

•Jan 1, 2007•0 citations

Everlasting UC Commitments from Fully Malicious PUFs

Bernardo Magri, Giulio Malavolta, Dominique Schröder +1 more

Abstract Everlasting security models the setting where hardness assumptions hold during the execution of a protocol but may get broken in the future. Due to the strength of this adversarial model, achieving any meaningful security guarantees for composable protocols is impossible without relying on hardware assumptions (Müller-Quade and Unruh, JoC’10). For this reason, a rich line of research has tried to leverage physical assumptions to construct well-known everlasting cryptographic primitives, such as commitment schemes. The only known everlastingly UC secure commitment scheme, due to Müller-Quade and Unruh (JoC’10), assumes honestly generated hardware tokens. The authors leave the possibility of constructing everlastingly UC secure commitments from malicious hardware tokens as an open problem. Goyal et al. (Crypto’10) constructs unconditionally UC-secure commitments and secure computation from malicious hardware tokens, with the caveat that the honest tokens must encapsulate other tokens. This extra restriction rules out interesting classes of hardware tokens, such as physically uncloneable functions (PUFs). In this work, we present the first construction of an everlastingly UC-secure commitment scheme in the fully malicious token modelwithout requiringhonest token encapsulation. Our scheme assumes the existence of PUFs and is secure in the common reference string model. We also show that our results are tight by giving an impossibility proof for everlasting UC-securecomputationfrom non-erasable tokens (such as PUFs), even with trusted setup.

Journal of Cryptology•Jul 1, 2022•6 citations

Weakening the Isolation Assumption of Tamper-proof Hardware Tokens

Rafael Dowsley, Jörn Müller‐Quade, Tobias Nilges

Recent results have shown the usefulness of tamper-proof hardware tokens as a setup assumption for building UC-secure two-party computation protocols, thus providing broad security guarantees and allowing the use of such protocols as buildings blocks in the modular design of complex cryptography protocols. All these works have in common that they assume the tokens to be completely isolated from their creator, but this is a strong assumption. In this work we investigate the feasibility of cryptographic protocols in the setting where the isolation of the hardware token is weakened. We consider two cases: (1) the token can relay messages to its creator, or (2) the creator can send messages to the token after it is sent to the receiver. We provide a detailed characterization for both settings, presenting both impossibilities and information-theoretically secure solutions.

arXiv:1502.03487•Feb 11, 2015•5 citations

Stateless Cryptographic Protocols

Vipul Goyal, Hemanta K. Maji

Secure computation protocols inherently involve multiple rounds of interaction among the parties where, typically a party has to keep a state about what has happened in the protocol so far and then wait for the other party to respond. We study if this is inherent. In particular, we study the possibility of designing cryptographic protocols where the parties can be completely stateless and compute the outgoing message by applying a single fixed function to the incoming message (independent of any state). The problem of designing stateless secure computation protocols can be reduced to the problem of designing protocols satisfying the notion of resettable computation introduced by Canetti, Goldreich, Goldwasser and Micali (FOCS'01) and widely studied thereafter. The current start of art in resettable computation allows for construction of protocols which provide security only when a single predetermined party is resettable [15]. An exception is for the case of the zero-knowledge functionality for which a protocol in which both parties are resettable was recently obtained by Deng, Goyal and Sahai (FOCS'09). The fundamental question left open in this sequence of works is, whether fully-resettable computation is possible, when: 1) An adversary can corrupt any number of parties, and 2) The adversary can reset any party to its original state during the execution of the protocol and can restart the protocol. In this paper, we resolve the above problem by constructing secure protocols realizing any efficiently computable multi-party functionality in the plain model under standard cryptographic assumptions. First, we construct a Fully-Resettable Simulation Sound Zero-Knowledge (ss-rs-rZK) protocol. Next, based on these ss-rs-rZK protocols, we show how to compile any semi-honest secure protocol into a protocol secure against fully resetting adversaries. Next, we study a seemingly unrelated open question: "Does there exist a functionality which, in the concurrent setting, is impossible to securely realize using BB simulation but can be realized using NBB simulation?". We resolve the above question in the affirmative by giving an example of such a (reactive) functionality. Somewhat surprisingly, this is done by making a connection to the existence of a fully resettable simulation sound zero-knowledge protocol.

Annual Symposium on Foundations of Computer Science•Oct 1, 2011•23 citations

Universally Composable Multiparty Computation with Partially Isolated Parties.

Ivan Damgård, Jesper Buus Nielsen, Daniel Wichs

Abstract. It is well known that universally composable multiparty computation cannot, in general, be achieved in the standard model without setup assumptions when the adversary can corrupt an arbitrary number of players. One way to get around this problem is by having a trusted third party generate some global setup such as a common reference string (CRS) or a public key infrastructure (PKI). The recent work of Katz shows that we may instead rely on physical assumptions, and in particular tamper-proof hardware tokens. In this paper, we consider a similar but strictly weaker physical assumption. We assume that a player (Alice) can partially isolate another player (Bob) for a brief portion of the computation and prevent Bob from communicating more than some limited number of bits with the environment. For example, isolation might be achieved by asking Bob to put his functionality on a tamper-proof hardware token and assuming that Alice can prevent this token from communicating to the outside world. Alternatively, Alice may interact with Bob directly but in a special office which she administers and where there are no high-bandwidth communication channels to the outside world. We show that, under standard cryptographic assumptions, such physical setup can be used to UC-realize any two party and multiparty computation in the presence of an active and adaptive adversary corrupting any number of players. We also consider an alternative scenario, in which there are some trusted third parties but

•Jan 1, 2007•4 citations
Universally composable multi-party computation is impossible without setup assumptions. Motivated by the ubiquitous use of secure hardware in many real world security applications, Katz (EUROCRYPT 2007) proposed a model of tamper-proof hardware as a UC-setup assumption. An important aspect of this model is whether the hardware token is allowed to hold a state or not. Real world examples of tamper-proof hardware that can hold a state are expensive hardware security modules commonly used in mainframes. Stateless, or resettable hardware tokens model cheaper devices such as smartcards, where an adversarial user can cut off the power supply, thus resetting the card’s internal state. A natural question is how the stateful and the resettable hardware model compare in their cryptographic power, given that either the receiver or the sender of the token (and thus the token itself) might be malicious. In this work we show that any UC-functionality that can be implemented by a protocol using a single untrusted stateful hardware token can likewise be implemented using a single untrusted resettable hardware token, assuming only the existence of one-way functions. We present two compilers that transform UC-secure protocols in the stateful hardware model into UC-secure protocols in the resettable hardware model. The first compiler can be proven secure assuming merely the existence of one-way functions. However, it (necessarily) makes use of computationally rather expensive non-black-box techniques. We provide an alternative second compiler that replaces the expensive non-black-box component of the first compiler by few additional seed OTs. While this second compiler introduces the seed OTs as additional setup assumptions, it is computationally very efficient.
Secure computation in the presence of tamper-proof hardware tokens is proven under the assumption that the holder of the token is only given black-box access to the functionality of the token. Starting with the work of Goldreich and Ostrovsky [GO96], a long series of works studied tamper-proof hardware for realizing two-party functionalities in a variety of settings. In this work we focus our attention on two important complexity measures of stateless token-based secure computation: round complexity and hardness assumptions and present the following results in the two-party setting: • A round optimal generic secure protocol in the plain model assuming one-way functions, where the tokens are created by a single party. • A round optimal generic UC secure protocol assuming one-way functions. Our constructions are proven in the real/ideal paradigm with security in the presence of static malicious adversaries. As a side contribution, we identify a flaw in one of the feasibility results regarding UC secure protocols in the tamper proof model proved in the work of Goyal, Ishai, Sahai, Venkatesan and Wadia (TCC 2010) and correct history by attributing the work of Choi, Katz, Schroöder, Yerukhimovic and Zhou (TCC 2014) to establishing the (same) feasibility result.
The Universal Composability framework was introduced by Canetti to study the security of protocols which are concurrently executed with other protocols in a network environment. Unfortunately it was shown that in the so called plain model, a large class of functionalities cannot be securely realized. These severe impossibility results motivated the study of other models involving some sort of setup assumptions, where general positive results can be obtained. Until recently, all the setup assumptions which were proposed required some trusted third party (or parties). Katz recently proposed using a physical setup to avoid such trusted setup assumptions. In his model, the physical setup phase includes the parties exchanging tamper proof hardware tokens implementing some functionality. The tamper proof hardware is modeled so as to assume that the receiver of the token can do nothing more than observe its input/output characteristics. It is further assumed that the sender knows the program code of the hardware token which it distributed. Based on the DDH assumption, Katz gave general positive results for universally composable multi-party computation tolerating any number of dishonest
Abstract Everlasting security models the setting where hardness assumptions hold during the execution of a protocol but may get broken in the future. Due to the strength of this adversarial model, achieving any meaningful security guarantees for composable protocols is impossible without relying on hardware assumptions (Müller-Quade and Unruh, JoC’10). For this reason, a rich line of research has tried to leverage physical assumptions to construct well-known everlasting cryptographic primitives, such as commitment schemes. The only known everlastingly UC secure commitment scheme, due to Müller-Quade and Unruh (JoC’10), assumes honestly generated hardware tokens. The authors leave the possibility of constructing everlastingly UC secure commitments from malicious hardware tokens as an open problem. Goyal et al. (Crypto’10) constructs unconditionally UC-secure commitments and secure computation from malicious hardware tokens, with the caveat that the honest tokens must encapsulate other tokens. This extra restriction rules out interesting classes of hardware tokens, such as physically uncloneable functions (PUFs). In this work, we present the first construction of an everlastingly UC-secure commitment scheme in the fully malicious token modelwithout requiringhonest token encapsulation. Our scheme assumes the existence of PUFs and is secure in the common reference string model. We also show that our results are tight by giving an impossibility proof for everlasting UC-securecomputationfrom non-erasable tokens (such as PUFs), even with trusted setup.
Recent results have shown the usefulness of tamper-proof hardware tokens as a setup assumption for building UC-secure two-party computation protocols, thus providing broad security guarantees and allowing the use of such protocols as buildings blocks in the modular design of complex cryptography protocols. All these works have in common that they assume the tokens to be completely isolated from their creator, but this is a strong assumption. In this work we investigate the feasibility of cryptographic protocols in the setting where the isolation of the hardware token is weakened. We consider two cases: (1) the token can relay messages to its creator, or (2) the creator can send messages to the token after it is sent to the receiver. We provide a detailed characterization for both settings, presenting both impossibilities and information-theoretically secure solutions.
Secure computation protocols inherently involve multiple rounds of interaction among the parties where, typically a party has to keep a state about what has happened in the protocol so far and then wait for the other party to respond. We study if this is inherent. In particular, we study the possibility of designing cryptographic protocols where the parties can be completely stateless and compute the outgoing message by applying a single fixed function to the incoming message (independent of any state). The problem of designing stateless secure computation protocols can be reduced to the problem of designing protocols satisfying the notion of resettable computation introduced by Canetti, Goldreich, Goldwasser and Micali (FOCS'01) and widely studied thereafter. The current start of art in resettable computation allows for construction of protocols which provide security only when a single predetermined party is resettable [15]. An exception is for the case of the zero-knowledge functionality for which a protocol in which both parties are resettable was recently obtained by Deng, Goyal and Sahai (FOCS'09). The fundamental question left open in this sequence of works is, whether fully-resettable computation is possible, when: 1) An adversary can corrupt any number of parties, and 2) The adversary can reset any party to its original state during the execution of the protocol and can restart the protocol. In this paper, we resolve the above problem by constructing secure protocols realizing any efficiently computable multi-party functionality in the plain model under standard cryptographic assumptions. First, we construct a Fully-Resettable Simulation Sound Zero-Knowledge (ss-rs-rZK) protocol. Next, based on these ss-rs-rZK protocols, we show how to compile any semi-honest secure protocol into a protocol secure against fully resetting adversaries. Next, we study a seemingly unrelated open question: "Does there exist a functionality which, in the concurrent setting, is impossible to securely realize using BB simulation but can be realized using NBB simulation?". We resolve the above question in the affirmative by giving an example of such a (reactive) functionality. Somewhat surprisingly, this is done by making a connection to the existence of a fully resettable simulation sound zero-knowledge protocol.
Abstract. It is well known that universally composable multiparty computation cannot, in general, be achieved in the standard model without setup assumptions when the adversary can corrupt an arbitrary number of players. One way to get around this problem is by having a trusted third party generate some global setup such as a common reference string (CRS) or a public key infrastructure (PKI). The recent work of Katz shows that we may instead rely on physical assumptions, and in particular tamper-proof hardware tokens. In this paper, we consider a similar but strictly weaker physical assumption. We assume that a player (Alice) can partially isolate another player (Bob) for a brief portion of the computation and prevent Bob from communicating more than some limited number of bits with the environment. For example, isolation might be achieved by asking Bob to put his functionality on a tamper-proof hardware token and assuming that Alice can prevent this token from communicating to the outside world. Alternatively, Alice may interact with Bob directly but in a special office which she administers and where there are no high-bandwidth communication channels to the outside world. We show that, under standard cryptographic assumptions, such physical setup can be used to UC-realize any two party and multiparty computation in the presence of an active and adaptive adversary corrupting any number of players. We also consider an alternative scenario, in which there are some trusted third parties but