Cryptology ePrint Archive: Report 2015/559
Concurrent Secure Computation with Optimal Query Complexity
Ran Canetti and Vipul Goyal and Abhishek Jain
Abstract: 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.
Category / Keywords: foundations / secure computation, concurrent security
Original Publication (with major differences): IACR-CRYPTO-2015
Date: received 5 Jun 2015
Contact author: abhishek at cs jhu edu
Available format(s): PDF | BibTeX Citation
Version: 20150617:000444 (All versions of this report)
Short URL: ia.cr/2015/559
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]