Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

On the Necessity of Rewinding in Secure Multiparty Computation

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNSC,volume 4392))

Included in the following conference series:

  • 2495Accesses

Abstract

We investigate whether security of multiparty computation in the information-theoretic setting implies their security under concurrent composition. We show that security in the stand-alone model proven using black-box simulators in the information-theoretic setting does not imply security under concurrent composition, not even security under 2-bounded concurrent self-composition with an inefficient simulator and fixed inputs. This in particular refutes recently made claims on the equivalence of security in the stand-alone model and concurrent composition for perfect and statistical security (STOC’06). Our result strongly relies on the question whether every rewinding simulator can be transformed into an equivalent, potentially inefficient non-rewinding (straight-line) simulator. We answer this question in the negative by giving a protocol that can be proven secure using a rewinding simulator, yet that is not secure for any non-rewinding simulator.

Similar content being viewed by others

Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

References

  1. Backes, M., Pfitzmann, B., Waidner, M.: Secure asynchronous reactive systems. IACR Cryptology ePrint Archive 2004/082 (Mar. 2004)

    Google Scholar 

  2. Beaver, D.: Secure multiparty protocols and zero knowledge proof systems tolerating a faulty minority. Journal of Cryptology 4(2), 75–122 (1991)

    Article MATH  Google Scholar 

  3. Canetti, R.: Security and composition of multiparty cryptographic protocols. Journal of Cryptology 3(1), 143–202 (2000)

    Article MathSciNet  Google Scholar 

  4. Canetti, R.: Universally composable security: A new paradigm for cryptographic protocols. In: Proc. 42nd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 136–145 (2001) Extended version in Cryptology ePrint Archive, Report 2000/67,http://eprint.iacr.org/

  5. Dodis, Y., Micali, S.: Parallel reducibility for information-theoretically secure computation. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 74–92. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  6. Goldreich, O.: Foundations of Cryptography – Volume 2 (Basic Applications). Cambridge University Press, Cambridge (May 2004), Previous version online available at,http://www.wisdom.weizmann.ac.il/~oded/frag.html

    Google Scholar 

  7. Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game – or – a completeness theorem for protocols with honest majority. In: Proc. 19th Annual ACM Symposium on Theory of Computing (STOC), pp. 218–229. ACM Press, New York (1987)

    Google Scholar 

  8. Goldwasser, S., Levin, L.: Fair computation of general functions in presence of immoral majority. In: Menezes, A.J., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 77–93. Springer, Heidelberg (1991)

    Google Scholar 

  9. Hofheinz, D., Müller-Quade, J., Unruh, D.: On the (im)possibility of extending coin toss. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 504–521. Springer, Heidelberg (2006), Full version online available at,http://eprint.iacr.org/2006/177

    Chapter  Google Scholar 

  10. Hofheinz, D., Unruh, D.: Comparing two notions of simulatability. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 86–103. Springer, Heidelberg (2005), Online available at,http://iaks-www.ira.uka.de/home/unruh/publications/hofheinz05comparing.html

    Google Scholar 

  11. Hofheinz, D., Unruh, D.: Simulatable security and polynomially bounded concurrent composition. In: IEEE Symposium on Security and Privacy, Proceedings of SSP ’06, pp. 169–182. IEEE Computer Society Press, Los Alamitos (2006), Full version online available at,http://eprint.iacr.org/2006/130.ps

    Google Scholar 

  12. Kushilevitz, E., Lindell, Y., Rabin, T.: Information-theoretically secure protocols and security under composition. In: 38th Annual ACM Symposium on Theory of Computing, Proceedings of STOC 2006, pp. 109–118. ACM Press, New York (2006), Online available at,http://www.cs.biu.ac.il/~lindell/abstracts/IT-composition_abs.html

    Chapter  Google Scholar 

  13. Lindell, Y.: Bounded-concurrent secure two-party computation without setup assumptions. In: 35th Annual ACM Symposium on Theory of Computing, Proceedings of STOC 2003, pp. 683–692. ACM Press, New York (2003)

    Google Scholar 

  14. Lindell, Y.: General composition and universal composability in secure multi-party computation. In: 44th Annual Symposium on Foundations of Computer Science, Proceedings of FOCS 2003, pp. 394–403. IEEE Computer Society Press, Los Alamitos (2003), Online available at,http://eprint.iacr.org/2003/141

    Chapter  Google Scholar 

  15. Lindell, Y.: Lower bounds for concurrent self composition. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 203–222. Springer, Heidelberg (2004)

    Google Scholar 

  16. Micali, S., Rogaway, P.: Secure computation. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 392–404. Springer, Heidelberg (1992)

    Google Scholar 

  17. Pfitzmann, B., Waidner, M.: Composition and integrity preservation of secure reactive systems. In: Proc. 7th ACM Conference on Computer and Communications Security, pp. 245–254. ACM, New York (2000), Extended version (with Matthias Schunter) IBM Research Report RZ 3206, May 2000,http://www.semper.org/sirene/publ/PfSW1_00ReactSimulIBM.ps.gz

    Chapter  Google Scholar 

  18. Pfitzmann, B., Waidner, M.: A model for asynchronous reactive systems and its application to secure message transmission. In: Proc. 22nd IEEE Symposium on Security & Privacy, pp. 184–200. IEEE, Los Alamitos (2004), Extended version of the model (with Michael Backes) IACR Cryptology ePrint Archive 2004/082,http://eprint.iacr.org/

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Saarland University, Saarbrücken, Germany

    Michael Backes & Dominique Unruh

  2. Universität Karlsruhe, Germany

    Jörn Müller-Quade

Authors
  1. Michael Backes

    You can also search for this author inPubMed Google Scholar

  2. Jörn Müller-Quade

    You can also search for this author inPubMed Google Scholar

  3. Dominique Unruh

    You can also search for this author inPubMed Google Scholar

Editor information

Salil P. Vadhan

Rights and permissions

Copyright information

© 2007 Springer Berlin Heidelberg

About this paper

Cite this paper

Backes, M., Müller-Quade, J., Unruh, D. (2007). On the Necessity of Rewinding in Secure Multiparty Computation. In: Vadhan, S.P. (eds) Theory of Cryptography. TCC 2007. Lecture Notes in Computer Science, vol 4392. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-70936-7_9

Download citation

Publish with us

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