Cryptology ePrint Archive: Report 2013/827

Lower Bounds in the Hardware Token Model

Shashank Agrawal and Prabhanjan Ananth and Vipul Goyal and Manoj Prabhakaran and Alon Rosen

Abstract: We study the complexity of secure computation in the tamper-proof hardware token model. Our main focus is on non-interactive unconditional two-party computation using bit-OT tokens, but we also study computational security with stateless tokens that have more complex functionality. Our results can be summarized as follows:

- There exists a class of functions such that the number of bit-OT tokens required to securely implement them is at least the size of the sender's input. The same applies for receiver's input size (with a different class of functionalities).

- Non-adaptive protocols in the hardware token model imply efficient (decomposable) randomized encodings. This can be interpreted as evidence to the impossibility of non-adaptive protocols for a large class of functions.

- There exists a functionality for which there is no protocol in the stateless hardware token model accessing the tokens at most a constant number of times, even when the adversary is computationally bounded.

En route to proving our results, we make interesting connections between the hardware token model and well studied notions such as OT hybrid model, randomized encodings, and obfuscation.

Category / Keywords: foundations /

Original Publication (with major differences): IACR-TCC-2014

Date: received 5 Dec 2013, last revised 12 Jan 2014

Contact author: sagrawl2 at illinois edu

Available format(s): PDF | BibTeX Citation

Version: 20140112:074937 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]