skip to main content
10.1145/1007352.1007395acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
Article

Completeness in two-party secure computation: a computational view

Published: 13 June 2004 Publication History

Abstract

A Secure Function Evaluation (SFE) of a two-variable function f(·,·) is a protocol that allows two parties with inputs x and y to evaluate f(x,y) in a manner where neither party learns "more than is necessary". A rich body of work deals with the study of completeness for secure two-party computation. A function f is complete for SFE if a protocol for securely evaluating f allows the secure evaluation of all (efficiently computable) functions. The questions investigated are which functions are complete for SFE, which functions have SFE protocols unconditionally and whether there are functions that are neither complete nor have efficient SFE protocols.The previous study of these questions was mainly conducted from an Information Theoretic point of view and provided strong answers in the form of combinatorial properties. However, we show that there are major differences between the information theoretic and computational settings. In particular, we show functions that are considered as having SFE unconditionally by the combinatorial criteria but are actually complete in the computational setting. We initiate the fully computational study of these fundamental questions. Somewhat surprisingly, we manage to provide an almost full characterization of the complete functions in this model as well. More precisely, we present a computational criterion (called computational row non-transitivity) for a function f to be complete for the asymmetric case. Furthermore, we show a matching criterion called computational row transitivity for f to have a simple SFE (based on no additional assumptions). This criterion is close to the negation of the computational row non-transitivity and thus we essentially characterize all "nice" functions as either complete or having SFE unconditionally.

References

[1]
A. Beimel, T. Malkin, and S. Micali. The all-or-nothing nature of two-party secure computation. In CRYPTO '99, volume 1666, pages 80--97. Springer, 1999.]]
[2]
M. Bellare and S. Micali. Non-interactive oblivious transfer and applications. In CRYPTO '89, volume 435, pages 547--557. Springer, 1989.]]
[3]
M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In 20th STOC, pages 1--10, 1988.]]
[4]
R. Canetti. Security and composition of multiparty cryptographic protocols. Journal of Cryptology, 13(1):143--202, 2000.]]
[5]
B. Chor and E. Kushilevitz. A zero-one law for boolean privacy. SIAM Journal on Disc. Math., 4(1):36--47, 1991. preliminary version in STOC 89.]]
[6]
C. Crepeau. Equivalence between two flavours of oblivious transfers. In CRYPTO '87, volume 293, pages 350--354. Springer-Verlag, 1987.]]
[7]
I. Damgard, J. Kilian, and L. Salvail. On the (im)possibility of basing oblivious transfer and bit commitment on weakened security assumptions. In Eurocrypt '99, volume 1592, pages 56--73, 1999.]]
[8]
S. Even, O. Goldreich, and A. Lempel. A randomized protocol for signing contracts. Communications of the ACM, 28(6):637--647, 1985.]]
[9]
M. Fitzi, J. A. Garay, U. M. Maurer, and R. Ostrovsky:. Minimal complete primitives for secure multi-party computation. In CRYPTO '01, volume 2139, pages 80--100. Springer, 2001.]]
[10]
Y. Gertner, S. Kannan, T. Malkin, O. Reingold, and M. Viswanathan. The relationship between public key encryption and oblivious transfer. In 41st FOCS, pages 325--335, 2000.]]
[11]
O. Goldreich. Foundations of Cryptography. Cambridge University Press, 2001.]]
[12]
O. Goldreich. Foundations of cryptography - volume 2. Working Draft, available at www. wisdom. weizmann. ac. il/oded/foc-vol2. html, 2004.]]
[13]
O. Goldreich and L. A. Levin. A hard-core predicate for all one-way functions. In 21st STOC, pages 25--32, 1989.]]
[14]
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.]]
[15]
O. Goldreich, S. Micali, and A. Wigderson. Proofs that yield nothing but their validity, or all languages in np have zero-knowledge proof systems. Journal of the ACM, 38:691--729, 1 1991.]]
[16]
O. Goldreich, N. Nisan, and A. Wigderson. On Yao's XOR-lemma. In ECCC (50), volume 2, 1995.]]
[17]
D. Harnik, M. Naor, O. Reingold, and A. Rosen. Completeness in two-party secure computation - a computational view. ECCC, TR03-060, 2003.]]
[18]
R. Impagliazzo. A personal view of average-case complexity. In 10th Annual Structure in Complexity Theory Conference, pages 134--147. IEEE Computer Society Press, 1995.]]
[19]
R. Impagliazzo and M. Luby. One-way functions are essential for complexity based cryptography. In 30th FOCS, pages 230--235, 1989.]]
[20]
R. Impagliazzo and S. Rudich. Limits on the provable consequences of one-way permutations. In 21st STOC, pages 44--61, 1989.]]
[21]
J. Kilian. Founding cryptography on oblivious transfer. In 20th STOC, pages 20--31, 1988.]]
[22]
J. Kilian. A general completeness theorem for two-party games. In 23rd STOC, pages 553--560, 1991.]]
[23]
J. Kilian. More general completeness theorems for secure two-party computation. In 32nd STOC, pages 316--324, 2000.]]
[24]
J. Kilian, E. Kushilevitz, S. Micali, and R. Ostrovsky. Reducibility and completeness in private computations. SIAM Journal of Computing, 28(4):1189--1208, 2000.]]
[25]
E. Kushilevitz. Privacy and communication complexity. SIAM Journal on Disc. Math., 5(2):273--284, 1992. preliminary version in FOCS 89.]]
[26]
E. Kushilevitz, S. Micali, and R. Ostrovsky. Reducibility and completeness in multi-party private computations. In 35th FOCS, pages 478--489, 1994.]]
[27]
M. Naor and B. Pinkas. Efficient oblivious transfer protocols. In SIAM Symposium on Discrete Algorithms (SODA 2001), pages 448--457, 2001.]]
[28]
R. Ostrovsky and A. Wigderson. One-way fuctions are essential for non-trivial zero-knowledge. In Second Israel Symposium on Theory of Computing Systems, ISTCS 93, Proceedings. IEEE Computer Society, pages 3--17, 1993.]]
[29]
M. O. Rabin. How to exchange secrets by oblivious transfer. TR-81, Harvard, 1981.]]
[30]
A. C. Yao. Theory and application of trapdoor functions. In 23rd FOCS, pages 80--91, 1982.]]
[31]
A. C. Yao. How to generate and exchange secrets. In 27th FOCS, pages 162--167, 1986.]]

Cited By

View all
  • (2018)k-Skyband query answering with differential privacy1Journal of Computer Security10.3233/JCS-17110126:5(647-676)Online publication date: 9-Aug-2018
  • (2018)Completeness for Symmetric Two-Party FunctionalitiesJournal of Cryptology10.1007/s00145-017-9267-731:3(671-697)Online publication date: 1-Jul-2018
  • (2017)Differentially Private K-Skyband Query Answering Through Adaptive Spatial DecompositionData and Applications Security and Privacy XXXI10.1007/978-3-319-61176-1_8(142-163)Online publication date: 22-Jun-2017
  • Show More Cited By

Index Terms

  1. Completeness in two-party secure computation: a computational view

    Recommendations

    Comments

    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
    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.

    Check for updates

    Author Tags

    1. completeness
    2. oblivious tansfer
    3. secure computation

    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
    57th Annual ACM Symposium on Theory of Computing (STOC 2025)
    June 23 - 27, 2025
    Prague , Czech Republic

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)4
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 17 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2018)k-Skyband query answering with differential privacy1Journal of Computer Security10.3233/JCS-17110126:5(647-676)Online publication date: 9-Aug-2018
    • (2018)Completeness for Symmetric Two-Party FunctionalitiesJournal of Cryptology10.1007/s00145-017-9267-731:3(671-697)Online publication date: 1-Jul-2018
    • (2017)Differentially Private K-Skyband Query Answering Through Adaptive Spatial DecompositionData and Applications Security and Privacy XXXI10.1007/978-3-319-61176-1_8(142-163)Online publication date: 22-Jun-2017
    • (2016)Privacy-Preserving Two-Party Skyline Queries Over Horizontally Partitioned DataInformation Security Theory and Practice10.1007/978-3-319-45931-8_12(187-203)Online publication date: 17-Sep-2016
    • (2012)Completeness for symmetric two-party functionalities - revisitedProceedings of the 18th international conference on The Theory and Application of Cryptology and Information Security10.1007/978-3-642-34961-4_9(116-133)Online publication date: 2-Dec-2012
    • (2010)A Variant of Naor-Pinkas Oblivious Transfer for More Efficient AuthenticationAdvanced Computer Science and Information Technology10.1007/978-3-642-13346-6_4(32-38)Online publication date: 2010
    • (2007)How many oblivious transfers are needed for secure multiparty computation?Proceedings of the 27th annual international cryptology conference on Advances in cryptology10.5555/1777777.1777801(284-302)Online publication date: 19-Aug-2007
    • (2007)How Many Oblivious Transfers Are Needed for Secure Multiparty Computation?Advances in Cryptology - CRYPTO 200710.1007/978-3-540-74143-5_16(284-302)Online publication date: 2007
    • (2007)Oblivious-Transfer AmplificationProceedings of the 26th annual international conference on Advances in Cryptology10.1007/978-3-540-72540-4_32(555-572)Online publication date: 20-May-2007

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media