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