More Web Proxy on the site http://driver.im/

Article

New notions of security: achieving universal composability without trusted setup

Authors:

Manoj Prabhakaran,

Amit SahaiAuthors Info & Claims

STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing

Pages 242 - 251

https://doi.org/10.1145/1007352.1007394

Published: 13 June 2004 Publication History

Abstract

We propose a modification to the framework of Universally Composable (UC) security [3]. Our new notion involves comparing the real protocol execution with an ideal execution involving ideal functionalities (just as in UC-security), but allowing the environment and adversary access to some super-polynomial computational power. We argue the meaningfulness of the new notion, which in particular subsumes many of the traditional notions of security. We generalize the Universal Composition theorem of [3] to the new setting. Then under new computational assumptions, we realize secure multi-party computation (for static adversaries) without a common reference string or any other set-up assumptions, in the new framework. This is known to be impossible under the UC framework.

References

[1]

Boaz Barak. Constant-Round Coin-Tossing with a Man in the Middle or Realizing the Shared Random String Model. FOCS 2002: 345--355]]

Digital Library

[2]

Boaz Barak and Yehuda Lindell. Strict Polynomial-time in Simulation and Extraction. Electronic Colloquium on Computational Complexity (ECCC)(026): (2002)]]

[3]

Ran Canetti. Universally composable security: A new paradigm for cryptographic protocols. Electronic Colloquium on Computational Complexity (ECCC) (016): (2001) (Preliminary version in IEEE Symposium on Foundations of Computer Science, pages 136--145, 2001. )]]

Digital Library

[4]

Ran Canetti and Marc Fischlin. Universally composable commitments. In CRYPTO, pages 19--40, 2001.]]

Digital Library

[5]

Ran Canetti and Hugo Krawczyk. Universally Composable Notions of Key Exchange and Secure Channels. EUROCRYPT 2002: 337--351.]]

Digital Library

[6]

R. Canetti, E. Kushilevitz, and Y. Lindell. On the limitations of universally composable two-party computation without set-up assumptions. In EUROCRYPT, pages 68--86, 2003.]]

Digital Library

[7]

R. Canetti, Y. Lindell, R. Ostrovsky, and A. Sahai. Universally composable two-party and multi-party secure computation. In ACM Symposium on Theory of Computing, pages 494--503, 2002.]]

Digital Library

[8]

Ivan Damgard and Jens Groth. Non-interactive and reusable non-malleable commitment schemes. STOC 2003: 426--437]]

Digital Library

[9]

Giovanni Di Crescenzo, Yuval Ishai and Rafail Ostrovsky. Non-Interactive and Non-Malleable Commitment. STOC 1998: 141--150]]

Digital Library

[10]

Danny Dolev, Cynthia Dwork and Moni Naor. Nonmalleable Cryptography. SIAM J. Comput. 30(2): 391--437 (2000)]]

Digital Library

[11]

Cynthia Dwork, Moni Naor and Amit Sahai. Concurrent Zero-Knowledge. STOC 1998. 409--418]]

Digital Library

[12]

S. Goldwasser and Y. Lindell. Secure Computation without Agreement. DISC 2002: 17--32]]

Digital Library

[13]

Secure Multi-Party Computation. Manuscript. Preliminary version, 1998. Available from: http://www. wisdom. weizmann. ac. il/ oded/pp. html.]]

[14]

O. Goldreich and L. Levin. A Hard Predicate for All One-Way Functions. In 21st STOC, pages 25--32, 1989.]]

Digital Library

[15]

O. Goldreich, S. Micali and A. Wigderson. How to Play any Mental Game -- A Completeness Theorem for Protocols with Honest Majority. In 19th STOC, pages 218--229, 1987. For details see {13}.]]

Digital Library

[16]

Joe Kilian and Erez Petrank. Concurrent and resettable zero-knowledge in poly-logarithmic rounds. STOC 2001: 560--569.]]

Digital Library

[17]

Yehuda Lindell. Bounded-concurrent secure two-party computation without setup assumptions. STOC 2003. 683--692.]]

Digital Library

[18]

Yehuda Lindell. General composition and universal composability in secure multi-party computation. In IEEE Symposium on Foundations of Computer Science, pages 394--403, 2003.]]

Digital Library

[19]

Moni Naor. Bit Commitment using Pseudorandom Generators. Journal of Cryptology, 4(2):151--158, 1991.]]

[20]

Rafael Pass. Simulation in Quasi-Polynomial Time, and Its Application to Protocol Composition. EUROCRYPT 2003: 160--176.]]

Digital Library

[21]

Rafael Pass and Alon Rosen. Bounded-Concurrent Secure Two-Party Computation in a Constant Number of Rounds. FOCS 2003: 404--413.]]

Digital Library

[22]

B. Pfitzmann and M. Waidner. Composition and integrity preservation of secure reactive systems. In ACM Conference on Computer and Communications Security (CCS 2000), pp. 245 -- 254, 2000.]]

Digital Library

[23]

B. Pfitzmann and M. Waidner. A Model for Asynchronous Reactive Systems and its Application to Secure Message Transmission. In IEEE Symposium on Security and Privacy, 2001.]]

Digital Library

[24]

Manoj Prabhakaran, Alon Rosen and Amit Sahai. Concurrent Zero Knowledge with Logarithmic Round-Complexity. FOCS 2002: 366--375]]

Digital Library

[25]

Manoj Prabhakaran and Amit Sahai. New Notions of Security: Achieving Universal Composability without Trusted Setup. At the Cryptology ePrint Archive http://eprint. iacr. org/. 2004.]]

[26]

Manoj Prabhakaran and Amit Sahai. Revisiting Concurrency: Monitored Functionalities and Client-Server Computation. Manuscript under preparation.]]

[27]

Amit Sahai. Non-malleable Non-interactive Zero Knowledge and Adaptive Chosen Ciphertext Security. FOCS 1999: 543--553]]

Digital Library

[28]

Ransom Richardson and Joe Kilian. On the Concurrent Composition of Zero-Knowledge Proofs. EUROCRYPT 1999: 415--431]]

Digital Library

[29]

John Rompel. One-Way Functions are Necessary and Sufficient for Secure Signatures. STOC 1990: 387--394]]

Digital Library

Cited By

Dayanikli DLehmann A(2024)Provable Security Analysis of the Secure Remote Password Protocol2024 IEEE 37th Computer Security Foundations Symposium (CSF)10.1109/CSF61375.2024.00026(620-635)Online publication date: 8-Jul-2024
https://doi.org/10.1109/CSF61375.2024.00026
Bhushan KObbattu SPrabhakaran MRaghunath R(2024)R3PO: Reach-Restricted Reactive Program Obfuscation and Its ApplicationsPublic-Key Cryptography – PKC 202410.1007/978-3-031-57725-3_3(61-91)Online publication date: 14-Apr-2024
https://doi.org/10.1007/978-3-031-57725-3_3
Liang XPandey OYamakawa T(2023)A New Approach to Post-Quantum Non-Malleability2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00041(568-579)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00041
Show More Cited By

Index Terms

New notions of security: achieving universal composability without trusted setup
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

A unified framework for concurrent security: universal composability from stand-alone non-malleability
STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing

We present a unified framework for obtaining Universally Composable (UC) protocols by relying on stand-alone secure non-malleable commitments. Essentially all results on concurrent secure computation--both in relaxed models (e.g., quasi-polynomial time ...
Long-Term Security and Universal Composability

Algorithmic progress and future technological advances threaten today’s cryptographic protocols. This may allow adversaries to break a protocol retrospectively by breaking the underlying complexity assumptions long after the execution of the protocol. ...
A Universally Composable Group Key Exchange Protocol with Minimum Communication Effort
SCN '08: Proceedings of the 6th international conference on Security and Cryptography for Networks

The universal composability (UC) framework by Canetti [15] is a general-purpose framework for designing secure protocols. It ensures the security of UC-secure protocols under arbitrary compositions. As key exchange protocols (KEs) belong to the most ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing

June 2004

660 pages

ISBN:1581138520

DOI:10.1145/1007352

Program Chair:
László Babai
University of Chicago, Chicago, IL

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

STOC04

Sponsor:

STOC04: Symposium of Theory of Computing 2004

June 13 - 16, 2004

IL, Chicago, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

99
Total Citations
View Citations
663
Total Downloads

Downloads (Last 12 months)20
Downloads (Last 6 weeks)5

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dayanikli DLehmann A(2024)Provable Security Analysis of the Secure Remote Password Protocol2024 IEEE 37th Computer Security Foundations Symposium (CSF)10.1109/CSF61375.2024.00026(620-635)Online publication date: 8-Jul-2024
https://doi.org/10.1109/CSF61375.2024.00026
Bhushan KObbattu SPrabhakaran MRaghunath R(2024)R3PO: Reach-Restricted Reactive Program Obfuscation and Its ApplicationsPublic-Key Cryptography – PKC 202410.1007/978-3-031-57725-3_3(61-91)Online publication date: 14-Apr-2024
https://doi.org/10.1007/978-3-031-57725-3_3
Liang XPandey OYamakawa T(2023)A New Approach to Post-Quantum Non-Malleability2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00041(568-579)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00041
Berger RBroadnax BKlooß MMechler JMüller-Quade JOttenhues ARaiber M(2023)Composable Long-Term Security with RewindingTheory of Cryptography10.1007/978-3-031-48624-1_19(510-541)Online publication date: 29-Nov-2023
https://dl.acm.org/doi/10.1007/978-3-031-48624-1_19
Goyal VLiang XMalavolta G(2023)On Concurrent Multi-party Quantum ComputationAdvances in Cryptology – CRYPTO 202310.1007/978-3-031-38554-4_5(129-161)Online publication date: 20-Aug-2023
https://dl.acm.org/doi/10.1007/978-3-031-38554-4_5
Morgan APass R(2023)Concurrently Composable Non-interactive Secure ComputationAdvances in Cryptology – ASIACRYPT 202210.1007/978-3-031-22963-3_18(526-555)Online publication date: 25-Jan-2023
https://doi.org/10.1007/978-3-031-22963-3_18
Kim ALiang XPandey O(2022)A New Approach to Efficient Non-Malleable Zero-KnowledgeAdvances in Cryptology – CRYPTO 202210.1007/978-3-031-15985-5_14(389-418)Online publication date: 11-Oct-2022
https://doi.org/10.1007/978-3-031-15985-5_14
Broadbent AGharibian SZhou H(2021)Towards Quantum One-Time Memories from Stateless HardwareQuantum10.22331/q-2021-04-08-4295(429)Online publication date: 8-Apr-2021
https://doi.org/10.22331/q-2021-04-08-429
Broadnax BMechler JMüller-Quade J(2021)Environmentally Friendly Composable Multi-party Computation in the Plain Model from Standard (Timed) AssumptionsTheory of Cryptography10.1007/978-3-030-90459-3_25(750-781)Online publication date: 4-Nov-2021
https://doi.org/10.1007/978-3-030-90459-3_25
Hirt MLiu-Zhang CMaurer U(2021)Adaptive Security of Multi-party Protocols, RevisitedTheory of Cryptography10.1007/978-3-030-90459-3_23(686-716)Online publication date: 4-Nov-2021
https://doi.org/10.1007/978-3-030-90459-3_23
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents