Lower Bounds in the Hardware Token Model.
Shashank Agrawal, Prabhanjan Ananth, Vipul Goyal +2 more
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 to-kens, but we also study computational security with stateless tokens that have more complex functionality. Our results can be summarized as follows: • We show that 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). • We investigate the existence of non-adaptive protocols in the hardware token model. In a non-adaptive protocol, the queries to the tokens are fixed in advance as against an adaptive protocol in which the queries can depend on the answers from the previously queried tokens. In this work, we show that the existence of non-adaptive protocols in the hardware token model imply efficient (decomposable) randomized encodings. Since, efficient decomposable randomized encodings are believed to not exist for all efficient functions, this result can be interpreted as an evidence to the impossibility of non-adaptive protocols for efficiently
•Jan 1, 2013•0 citations