Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Security Against Covert Adversaries: Efficient Protocols for Realistic Adversaries

  • Published:
Journal of Cryptology Aims and scope Submit manuscript

Abstract

In the setting of secure multiparty computation, a set of mutually distrustful parties wish to securely compute some joint function of their private inputs. The computation should be carried out in a secure way, meaning that no coalition of corrupted parties should be able to learn more than specified or somehow cause the result to be “incorrect.” Typically, corrupted parties are either assumed to be semi-honest (meaning that they follow the protocol specification) or malicious (meaning that they may deviate arbitrarily from the protocol). However, in many settings, the assumption regarding semi-honest behavior does not suffice and security in the presence of malicious adversaries is excessive and expensive to achieve.

In this paper, we introduce the notion ofcovert adversaries, which we believe faithfully models the adversarial behavior in many commercial, political, and social settings. Covert adversaries have the property that they may deviate arbitrarily from the protocol specification in an attempt to cheat, but do not wish to be “caught” doing so. We provide a definition of security for covert adversaries and show that it is possible to obtain highly efficient protocols that are secure against such adversaries. We stress that in our definition, we quantify over all (possibly malicious) adversaries and do not assume that the adversary behaves in any particular way. Rather, we guarantee that if an adversary deviates from the protocol in a way that would enable it to “cheat” (meaning that it can achieve something that is impossible in an ideal model where a trusted party is used to compute the function), then the honest parties are guaranteed to detect this cheating with good probability. We argue that this level of security is sufficient in many settings.

Article PDF

Similar content being viewed by others

Explore related subjects

Discover the latest articles and news from researchers in related subjects, suggested using machine learning.
Use our pre-submission checklist

Avoid common mistakes on your manuscript.

References

  1. W. Aiello, Y. Ishai, O. Reingold, Priced oblivious transfer: how to sell digital goods, inEUROCRYPT 2001. LNCS, vol. 2045 (Springer, Berlin, 2001), pp. 119–135

    Chapter  Google Scholar 

  2. D. Beaver, Foundations of secure interactive computing, inCRYPTO’91. LNCS, vol. 576 (Springer, Berlin, 1991), pp. 377–391

    Google Scholar 

  3. M. Ben-Or, S. Goldwasser, A. Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, in 20th STOC (1988), pp. 1–10

  4. R. Canetti, Security and composition of multiparty cryptographic protocols.J. Cryptol.13(1), 143–202 (2000)

    Article MATH MathSciNet  Google Scholar 

  5. R. Canetti, R. Ostrovsky, Secure computation with honest-looking parties: what if nobody is truly honest?, in 31st STOC (1999), pp. 255–264

  6. D. Chaum, C. Crépeau, I. Damgard, Multi-party unconditionally secure protocols, in 20th STOC (1988), pp. 11–19

  7. N. Chandran, V. Goyal, R. Ostrovsky, A. Sahai, Covert multiparty computation, in 48th FOCS (2007)

  8. D. Dolev, H.R. Strong, Authenticated algorithms for byzantine agreement.SIAM J. Comput.12(4), 656–665 (1983)

    Article MATH MathSciNet  Google Scholar 

  9. S. Even, O. Goldreich, A. Lempel, A randomized protocol for signing contracts.Commun. ACM28(6), 637–647 (1985)

    Article MathSciNet  Google Scholar 

  10. M.K. Franklin, M. Yung, Communication complexity of secure computation, in 24th STOC (1992), pp. 699–710

  11. O. Goldreich,Basic Applications, Foundations of Cryptography, vol. 2 (Cambridge University Press, Cambridge, 2004)

    MATH  Google Scholar 

  12. O. Goldreich, Y. Lindell, Session-key generation using human passwords only.J. Cryptol.19(3), 241–340 (2006)

    Article MATH MathSciNet  Google Scholar 

  13. O. Goldreich, E. Petrank, Quantifying knowledge complexity.Comput. Complex.8(1), 50–98 (1999)

    Article MATH MathSciNet  Google Scholar 

  14. O. Goldreich, S. Micali, A. Wigderson, How to play any mental game—a completeness theorem for protocols with honest majority, in 19th STOC (1987), pp. 218–229

  15. S. Goldwasser, L. Levin, Fair computation of general functions in presence of immoral majority, inCRYPTO’90. LNCS, vol. 537 (Springer, Berlin, 1990), pp. 77–93

    Google Scholar 

  16. S. Goldwasser, Y. Lindell, Secure computation without agreement.J. Cryptol.18(3), 247–287 (2005)

    Article MATH MathSciNet  Google Scholar 

  17. S. Halevi, Y.T. Kalai, Smooth projective hashing and two-message oblivious transfer.Cryptology ePrint Archive, Report 2007/118 (2007)

  18. Y. Ishai, Personal Communication (2007)

  19. Y. Ishai, J. Kilian, K. Nissim, E. Petrank, Extending oblivious transfers efficiently, inCRYPTO 2003. LNCS, vol. 2729 (Springer, Berlin, 2003), pp. 145–161

    Google Scholar 

  20. S. Jarecki, V. Shmatikov, Efficient two-party secure computation on committed inputs, inEurocrypt ’07. LNCS, vol. 4515 (Springer, Berlin, 2007), pp. 97–114

    Chapter  Google Scholar 

  21. Y.T. Kalai, Smooth projective hashing and two-message oblivious transfer, inEUROCRYPT 2005. LNCS, vol. 3494 (Springer, Berlin, 2005), pp. 78–95

    Google Scholar 

  22. Y. Lindell, B. Pinkas, A proof of Yao’s protocol for secure two-party computation.Cryptology ePrint Archive, Report 2004/175, 2004.J. Cryptol., to appear

  23. Y. Lindell, B. Pinkas, An efficient protocol for secure two-party computation in the presence of malicious adversaries, inEUROCRYPT 2007. LNCS, vol. 4515 (Springer, Berlin, 2007), pp. 52–78

    Chapter  Google Scholar 

  24. D. Malkhi, N. Nisan, B. Pinkas, Y. Sella, Fairplay—a secure two-party computation system, in The 13th USENIX Security Symposium (2004), pp. 287–302

  25. S. Micali, P. Rogaway, Secure Computation. Unpublished manuscript, 1992, preliminary version inCRYPTO’91. LNCS, vol. 576 (Springer, Berlin, 1991), pp. 392–404

    Google Scholar 

  26. P. Paillier, Public-key cryptosystems based on composite degree residuosity classes, inEUROCRYPT ’99. LNCS, vol. 1592 (Springer, Berlin, 1999), pp. 223–238

    Google Scholar 

  27. C. Peikert, V. Vaikuntanathan, B. Waters, A framework for efficient and composable oblivious transfer, inCRYPTO 2008. LNCS, vol. 5157 (Springer, Berlin, 2008), pp. 554–571

    Chapter  Google Scholar 

  28. M. Rabin, How to exchange secrets by oblivious transfer. Tech. Memo TR-81, Aiken Computation Laboratory, Harvard U. (1981)

  29. L. von Ahn, N. Hopper, J. Langford, Covert two-party computation, in 37th STOC (2005), pp. 513–522

  30. A. Yao, How to generate and exchange secrets, in 27th FOCS (1986), pp. 162–167

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Bar-Ilan University, Ramat Gan, Israel

    Yonatan Aumann & Yehuda Lindell

Authors
  1. Yonatan Aumann

    You can also search for this author inPubMed Google Scholar

  2. Yehuda Lindell

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toYehuda Lindell.

Additional information

Communicated by Oded Goldreich

An extended abstract of this work appeared in the 4th Theory of Cryptography Conference. Work supported in part by an Infrastructures Grant from the Ministry of Science, Israel. The second author was also supported by The Israel Science Foundation (Grant No. 781/07).

Rights and permissions

About this article

Cite this article

Aumann, Y., Lindell, Y. Security Against Covert Adversaries: Efficient Protocols for Realistic Adversaries.J Cryptol23, 281–343 (2010). https://doi.org/10.1007/s00145-009-9040-7

Download citation

Keywords

Use our pre-submission checklist

Avoid common mistakes on your manuscript.

Advertisement

[8]ページ先頭
©2009-2025 Movatter.jp