Paper 2013/827

Lower Bounds in the Hardware Token Model

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


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.

Available format(s)
Publication info
A major revision of an IACR publication in TCC 2014
Contact author(s)
sagrawl2 @ illinois edu
2014-01-12: revised
2013-12-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shashank Agrawal and Prabhanjan Ananth and Vipul Goyal and Manoj Prabhakaran and Alon Rosen},
      title = {Lower Bounds in the Hardware Token Model},
      howpublished = {Cryptology ePrint Archive, Paper 2013/827},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.