nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Equational Security Proofs of Oblivious Transfer Protocols

verfasst von : Baiyu Li, Daniele Micciancio

Erschienen in: Public-Key Cryptography – PKC 2018

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We exemplify and evaluate the use of the equational framework of Micciancio and Tessaro (ITCS 2013) by analyzing a number of concrete Oblivious Transfer protocols: a classic OT transformation to increase the message size, and the recent (so called “simplest”) OT protocol in the random oracle model of Chou and Orlandi (Latincrypt 2015), together with some simple variants. Our analysis uncovers subtle timing bugs or shortcomings in both protocols, or the OT definition typically employed when using them. In the case of the OT length extension transformation, we show that the protocol can be formally proved secure using a revised OT definition and a simple protocol modification. In the case of the “simplest” OT protocol, we show that it cannot be proved secure according to either the original or revised OT definition, in the sense that for any candidate simulator (expressible in the equational framework) there is an environment that distinguishes the real from the ideal system.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel On Composable Security for Digital Signatures

Nächstes Kapitel Extending Oblivious Transfer with Low Communication via Key-Homomorphic PRFs

Rooted in computational complexity, the model is usually described as an arbitrary network of (dynamically generated) Turing machines that communicate by means of shared tapes, possibly under the direction of some scheduling process, also modeled as an interactive Turing machine.

This is analogous to the Turing machine, an excellent model to study computation in general but a rather inconvenient one when it comes to specifying actual algorithms.

Since each seed \(s_i\) is used only once, the secret key encryption scheme can be as simple as stretching \(s_i\) using a pseudorandom generator \({\mathcal G}\), and use the resulting string \({\mathcal G}(s_i)\) as a one-time pad to mask the message \(m_i\).

In general we should consider the Borel algebra on X when defining probability distributions on X. Here we simply use X instead since we work on finite sets and discrete probabilities.

In the asymptotic setting, cryptographic protocols are parameterized by a security parameter n. For notational simplicity, we consider this security parameter n as fixed throughout the paper.

This corresponds to a perfectly secure communication channel. More complex/realistic communication channels are discussed at the end of this section.

This can be modeled by letting qs and qr range over the set of sequences of queries \(Q^*\), partially ordered according to the prefix ordering relation.

Chou and Orlandi use additive notation to match their efficient implementation based on elliptical curve groups. Here we are not concerned with any specific implementation, but retain the additive notation to match [10] and facilitate the comparison with the original protocol description.

In fact, computational indistinguishability is enough, but it is easy to achieve perfect security.

Backes, M., Pfitzmann, B., Waidner, M.: The reactive simulatability (RSIM) framework for asynchronous systems. Inf. Comput. 205(12), 1685–1720 (2007)MathSciNetCrossRefMATH

Barak, B., Canetti, R., Nielsen, J.B., Pass, R.: Universally composable protocols with relaxed set-up assumptions. In: 45th Symposium on Foundations of Computer Science (FOCS 2004), 17–19 October 2004, Rome, Italy, Proceedings, pp. 186–195 (2004)

Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Proceedings of the 1st ACM Conference on Computer and Communications Security, CCS 1993, pp. 62–73. ACM, New York (1993)

Bellare, M., Rogaway, P.: The security of triple encryption and a framework for code-based game-playing proofs. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 409–426. Springer, Heidelberg (2006). https://doi.org/10.1007/11761679_25 CrossRef

Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: 2001 42nd IEEE Symposium on Foundations of Computer Science, Proceedings, pp. 136–145, October 2001

Canetti, R., Cohen, A., Lindell, Y.: A simpler variant of universally composable security for standard multiparty computation. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 3–22. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48000-7_1 CrossRef

Canetti, R., Dodis, Y., Pass, R., Walfish, S.: Universally composable security with global setup. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 61–85. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-70936-7_4 CrossRef

Canetti, R., Jain, A., Scafuro, A.: Practical UC security with a global random oracle. In: Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, CCS 2014, pp. 597–608. ACM, New York (2014)

Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable two-party and multi-party secure computation. In: Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing, STOC 2002, pp. 494–503. ACM, New York (2002)

10.

Chou, T., Orlandi, C.: The simplest protocol for oblivious transfer. In: Lauter, K., Rodríguez-Henríquez, F. (eds.) LATINCRYPT 2015. LNCS, vol. 9230, pp. 40–58. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-22174-8_3 CrossRef

11.

Crépeau, C., van de Graaf, J., Tapp, A.: Committed oblivious transfer and private multi-party computation. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 110–123. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-44750-4_9 CrossRef

12.

Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. Commun. ACM 28(6), 637–647 (1985)MathSciNetCrossRefMATH

13.

Genç, Z.A., Iovino, V., Rial, A.: “The simplest protocol for oblivious transfer” revisited. IACR Cryptology ePrint Archive 2017, 370 (2017). http://eprint.iacr.org/2017/370

14.

Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game. In: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC 1987, pp. 218–229. ACM, New York (1987)

15.

Gunter, C.A., Scott, D.S.: Semantic domains. In: Handbook of theoretical computer science, vol. b, pp. 633–674. MIT Press, Cambridge (1990)

16.

Hofheinz, D., Shoup, V.: GNUC: a new universal composability framework. J. Cryptol. 28(3), 423–508 (2015)MathSciNetCrossRefMATH

17.

Hofheinz, D., Unruh, D., Müller-Quade, J.: Polynomial runtime and composability. J. Cryptol. 26(3), 375–441 (2013)MathSciNetCrossRefMATH

18.

Ishai, Y., Prabhakaran, M., Sahai, A.: Founding cryptography on oblivious transfer – efficiently. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 572–591. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85174-5_32 CrossRef

19.

Katz, J., Maurer, U., Tackmann, B., Zikas, V.: Universally composable synchronous computation. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 477–498. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36594-2_27 CrossRef

20.

Kilian, J.: Founding crytpography on oblivious transfer. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC 1988, pp. 20–31. ACM, New York (1988)

21.

Küsters, R.: Simulation-based security with inexhaustible interactive turing machines. In: Computer Security Foundations Workshop, CSFW-19 2006, pp. 309–320. IEEE Computer Society (2006)

22.

Küsters, R., Tuengerthal, M.: The IITM model: a simple and expressive model for universal composability. IACR Cryptology ePrint Archive 2013, 25 (2013). http://eprint.iacr.org/2013/025

23.

Lindell, Y., Pinkas, B.: Secure two-party computation via cut-and-choose oblivious transfer. J. Cryptol. 25(4), 680–722 (2011)MathSciNetCrossRefMATH

24.

Maurer, U.: Constructive cryptography – a new paradigm for security definitions and proofs. In: Mödersheim, S., Palamidessi, C. (eds.) TOSCA 2011. LNCS, vol. 6993, pp. 33–56. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-27375-9_3 CrossRef

25.

Maurer, U., Renner, R.: Abstract cryptography. In: Innovations in Computer Science - ICS 2010, Proceedings. Tsinghua University, Beijing, China, 7–9 January 2011, pp. 1–21 (2011)

26.

Micciancio, D., Tessaro, S.: An equational approach to secure multi-party computation. In: Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, ITCS 2013, pp. 355–372. ACM, New York (2013)

27.

Rabin, M.O.: How to exchange secrets with oblivious transfer, Technical report, TR-81 edn. Harvard University, Aiken Computation Lab (1981)

28.

Scott, D.S.: Domains for denotational semantics. In: Nielsen, M., Schmidt, E.M. (eds.) ICALP 1982. LNCS, vol. 140, pp. 577–610. Springer, Heidelberg (1982). https://doi.org/10.1007/BFb0012801 CrossRef

29.

Stoltenberg-Hansen, V., Lindström, I., Griffor, E.R.: Mathematical Theory of Domains. Cambridge University Press, New York (1994)CrossRefMATH

30.

Wikström, D.: Simplified universal composability framework. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9562, pp. 566–595. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49096-9_24 CrossRef

31.

Winskel, G.: The Formal Semantics of Programming Languages: An Introduction. MIT Press, Cambridge (1993)MATH

32.

Yao, A.C.: How to generate and exchange secrets (extended abstract). In: Foundations of Computer Science, Proceedings of FOCS 1986, pp. 162–167. IEEE Computer Society (1986)

Titel: Equational Security Proofs of Oblivious Transfer Protocols
verfasst von: Baiyu Li
Daniele Micciancio
Verlag: Springer International Publishing
Buch: Public-Key Cryptography – PKC 2018
Print ISBN: 978-3-319-76577-8

Electronic ISBN: 978-3-319-76578-5

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-76578-5_18

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner