Paper 2014/555

General Statistically Secure Computation with Bounded-Resettable Hardware Tokens

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


Universally composable secure computation was assumed to require trusted setups, until it was realized that parties exchanging (untrusted) tamper-proof hardware tokens allow an alternative approach (Katz; EUROCRYPT 2007). This discovery initialized a line of research dealing with two different types of tokens. Using only a single stateful token, one can implement general statistically secure two-party computation (Döttling, Kraschewski, Müller-Quade; TCC 2011); though all security is lost if an adversarial token receiver manages to physically reset and rerun the token. Stateless tokens, which are secure by definition against any such resetting-attacks, however, do provably not suffice for arbitrary secure computations (Goyal, Ishai, Mahmoody, Sahai; CRYPTO 2010). We investigate the natural question of what is possible if an adversary can reset a token at most a bounded number of times (e.g., because each resetting attempt imposes a significant risk to trigger a self-destruction mechanism of the token). Somewhat surprisingly, our results come close to the known positive results with respect to non-resettable stateful tokens. In particular, we construct polynomially many instances of statistically secure and universally composable oblivious transfer, using only a constant number of tokens. Our techniques have some abstract similarities to previous solutions, which we grasp by defining a new security property for protocols that use oracle access. Additionally, we apply our techniques to zero-knowledge proofs and obtain a protocol that achieves the same properties as bounded-query zero-knowledge PCPs (Kilian, Petrank, Tardos; STOC 1997), even if a malicious prover may issue stateful PCP oracles.

Available format(s)
Cryptographic protocols
Publication info
Published by the IACR in TCC 2015
resettable tamper-proof hardwareuniversal composabilitystatistical securitycommitmentsoblivious transferzero-knowledge
Contact author(s)
kraschew @ ira uka de
2015-01-12: revised
2014-07-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nico Döttling and Daniel Kraschewski and Jörn Müller-Quade and Tobias Nilges},
      title = {General Statistically Secure Computation with Bounded-Resettable Hardware Tokens},
      howpublished = {Cryptology ePrint Archive, Paper 2014/555},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.