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
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
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.
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
Abstract. The assumption of the availability of tamper-proof hardware tokens has been used extensively in the design of cryptographic primitives. For example, Katz (Eurocrypt 2007) suggests them as an alternative to other setup assumptions, towards achieving general UC-secure multi-party computation. On the other hand, a lot of recent research has focused on protecting security of various cryptographic primitives against physical attacks such as leakage and tampering. In this paper we put forward the notion of Built-in Tamper Resilience (BiTR) for cryptographic protocols, capturing the idea that the protocol that is encapsulated in a hardware token is designed in such a way so that tampering gives no advantage to an adversary. Our definition is within the UC model, and can be viewed as unifying and extending several prior related works. We provide a composition theorem for BiTR security of protocols, impossibility results, as well as several BiTR constructions for specific cryptographic protocols or tampering function classes. In particular, we achieve general UC-secure computation based on a hardware token that may be susceptible to affine tampering attacks. We also prove that two existing identification and signature schemes (by Schnorr and Okamoto, respecitively) are already BiTR against affine attacks (without requiring any modification or endcoding). We next observe that non-malleable codes can be used as state encodings to achieve the BiTR property, and show new positive results for deterministic non-malleable encodings for various classes of tampering functions. 1
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.
A desirable goal for cryptographic protocols is to guarantee security when the protocol is composed with other protocol instances. Universally Composable (UC) security provides this guarantee in a strong sense: A UC-secure protocol maintains its security properties even when composed concurrently with an unbounded number of instances of arbitrary protocols. However, many interesting cryptographic tasks are provably impossible to realize with UC security in the standard, “plain” model of computation. Impossibility holds even if ideally authenticated communication channels are provided. In contrast, it has been demonstrated that general secure computation can be obtained in a number of idealized models. Each one of these models represents a form of trust that is put in some of the system’s components. This survey examines and compares some of these trust models, both from the point of view of their sufficiency for building UC secure protocols, and from the point of view of their practical realizability. We start with the common reference string (CRS) model, and then describe several relaxations and alternatives including the Defective CRS model, the key registration models, the hardware token model, the global and augmented CRS models, and a timing assumption. Finally, we briefly touch upon trust models for obtaining authenticated communication.
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.