Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Bounded-concurrent secure multi-party computation with a dishonest majority
KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.
2004 (English)In: STOC '04 Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, Association for Computing Machinery (ACM), 2004, 232-241 p.Conference paper, Published paper (Refereed)
Abstract [en]

We show how to securely realize any multi-party functionality in a way that preserves security under an a-priori bounded number of concurrent executions, regardless of the number of corrupted parties. Previous protocols for the above task either rely on set-up assumptions such as a Common Reference String, or require an honest majority. Our constructions are in the plain model and rely on standard intractability assumptions (enhanced trapdoor permutations and collision resistant hash functions). Even though our main focus is on feasibility of concurrent multi-party computation we actually obtain a protocol using only a constant number of communication rounds. As a consequence our protocol yields the first construction of constant-round stand-alone secure multi-party computation with a dishonest majority, proven secure under standard (polynomial-time) hardness assumptions; previous solutions to this task either require logarithmic round-complexity, or subexponential hardness assumptions. The core of our protocol is a novel construction of (concurrently) simulation-sound zero-knowledge protocols, which might be of independent interest. Finally, we extend the framework constructed to give a protocol for secure multi-party (and thus two-party) computation for any number of corrupted parties, which remains secure even when arbitrary subsets of parties concurrently execute the protocol, possibly with interchangeable roles. As far as we know, for the case of two-party or multi-party protocols with a dishonest majority, this is the first positive result for any non-trivial functionality which achieves this property in the plain model.

Place, publisher, year, edition, pages
Association for Computing Machinery (ACM), 2004. 232-241 p.
Series
Conference Proceedings of the Annual ACM Symposium on Theory of Computing, ISSN 0734-9025
Keyword [en]
Concurrent composition, Constant-round protocols, Secure multi-party computation, Simulation-sound zero-knowledge
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-157173DOI: 10.1145/1007352.1007393Scopus ID: 2-s2.0-4544250511ISBN: 1-58113-852-0 (print)OAI: oai:DiVA.org:kth-157173DiVA: diva2:771778
Conference
The 36th Annual ACM Symposium on Theory of Computing; Chicago, IL; United States; 13 June 2004 through 15 June 2004
Note

QC 20141215

Available from: 2014-12-15 Created: 2014-12-08 Last updated: 2018-01-11Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Pass, Rafael
By organisation
Numerical Analysis and Computer Science, NADA
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 12 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf