Paper 2015/439

On Concurrently Secure Computation in the Multiple Ideal Query Model

Vipul Goyal and Abhishek Jain

Abstract

The multiple ideal query (MIQ) model was introduced by Goyal, Jain and Ostrovsky [Crypto'10] as a relaxed notion of security which allows one to construct concurrently secure protocols in the plain model. The main question relevant to the MIQ model is how many queries must we allow to the ideal world adversary? The importance of the above question stems from the fact that if the answer is positive, then it would enable meaningful security guarantees in many application scenarios, as well as, lead to resolution of long standing open questions such as fully concurrent password based key exchange in the plain model. In this work, we continue the study of the MIQ model and prove severe lower bounds on the number of ideal queries per session. Following are our main results: 1) There exists a two-party functionality that cannot be securely realized in the MIQ model with only a constant number of ideal queries per session. 2) There exists a two-party functionality that cannot be securely realized in the MIQ model by any constant round protocol, with any polynomial number of ideal queries per session. Both of these results are unconditional and even rule out protocols proven secure using a non-black-box simulator. We in fact prove a more general theorem which allows for trade-off between round complexity and the number of ideal queries per session. We obtain our negative results in the following two steps: 1) We first prove our results with respect to black-box simulation, i.e., we only rule out simulators that make black-box use of the adversary. 2) Next, we give a technique to compile our negative results w.r.t. black-box simulation into full impossibility results (ruling out non-black-box simulation as well) in the MIQ model. Interestingly, our compiler uses ideas from the work on obfuscation using tamper-proof hardware, even though our setting does not involve any hardware tokens.

Note: Full version of the Eurocrpt 2013 paper.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in EUROCRYPT 2013
Keywords
secure computationconcurrent security
Contact author(s)
abhishek @ cs jhu edu
History
2015-05-08: received
Short URL
https://ia.cr/2015/439
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/439,
      author = {Vipul Goyal and Abhishek Jain},
      title = {On Concurrently Secure Computation in the Multiple Ideal Query Model},
      howpublished = {Cryptology ePrint Archive, Paper 2015/439},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/439}},
      url = {https://eprint.iacr.org/2015/439}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.