Cryptology ePrint Archive: Report 2014/555

General Statistically Secure Computation with Bounded-Resettable Hardware Tokens

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

Abstract: 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.

Category / Keywords: cryptographic protocols / resettable tamper-proof hardware, universal composability, statistical security, commitments, oblivious transfer, zero-knowledge

Date: received 16 Jul 2014, last revised 16 Jul 2014

Contact author: kraschew at ira uka de

Available format(s): PDF | BibTeX Citation

Version: 20140718:123139 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]