Paper 2015/559

Concurrent Secure Computation with Optimal Query Complexity

Ran Canetti, Vipul Goyal, and Abhishek Jain


The multiple ideal query (MIQ) model [Goyal, Jain, and Ostrovsky, Crypto'10] offers a relaxed notion of security for concurrent secure computation, where the simulator is allowed to query the ideal functionality multiple times per session (as opposed to just once in the standard definition). The model provides a quantitative measure for the degradation in security under concurrent self-composition, where the degradation is measured by the number of ideal queries. However, to date, all known MIQ-secure protocols guarantee only an overall average bound on the number of queries per session throughout the execution, thus allowing the adversary to potentially fully compromise some sessions of its choice. Furthermore, [Goyal and Jain, Eurocrypt'13] rule out protocols where the simulator makes only an adversary-independent constant number of ideal queries per session. We show the first MIQ-secure protocol with worst-case per-session guarantee. Specifically, we show a protocol for any functionality that matches the [GJ13] bound: The simulator makes only a constant number of ideal queries in every session. The constant depends on the adversary but is independent of the security parameter. As an immediate corollary of our main result, we obtain the first password authenticated key exchange (PAKE) protocol for the fully concurrent, multiple password setting in the standard model with no set-up assumptions.

Available format(s)
Publication info
A major revision of an IACR publication in CRYPTO 2015
secure computationconcurrent security
Contact author(s)
abhishek @ cs jhu edu
2015-06-17: received
Short URL
Creative Commons Attribution


      author = {Ran Canetti and Vipul Goyal and Abhishek Jain},
      title = {Concurrent Secure Computation with Optimal Query Complexity},
      howpublished = {Cryptology ePrint Archive, Paper 2015/559},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.