Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
From Indifferentiability to Constructive Cryptography (and Back) Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Composable Security in the Tamper-Proof Hardware Model Under Minimal Complexity

verfasst von : Carmit Hazay, Antigoni Polychroniadou, Muthuramakrishnan Venkitasubramaniam

Erschienen in: Theory of Cryptography

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

We put forth a new formulation of tamper-proof hardware in the Global Universal Composable (GUC) framework introduced by Canetti et al. in TCC 2007. Almost all of the previous works rely on the formulation by Katz in Eurocrypt 2007 and this formulation does not fully capture tokens in a concurrent setting. We address these shortcomings by relying on the GUC framework where we make the following contributions:
1.
We construct secure Two-Party Computation (2PC) protocols for general functionalities with optimal round complexity and computational assumptions using stateless tokens. More precisely, we show how to realize arbitrary functionalities in the two-party setting with GUC security in two rounds under the minimal assumption of One-Way Functions (OWFs). Moreover, our construction relies on the underlying function in a black-box way. As a corollary, we obtain feasibility of Multi-Party Computation (MPC) with GUC-security under the minimal assumption of OWFs. As an independent contribution, we identify an issue with a claim in a previous work by Goyal, Ishai, Sahai, Venkatesan and Wadia in TCC 2010 regarding the feasibility of UC-secure computation with stateless tokens assuming collision-resistant hash-functions (and the extension based only on one-way functions).
 
2.
We then construct a 3-round MPC protocol to securely realize arbitrary functionalities with GUC-security starting from any semi-honest secure MPC protocol. For this construction, we require the so-called one-many commit-and-prove primitive introduced in the original work of Canetti, Lindell, Ostrovsky and Sahai in STOC 2002 that is round-efficient and black-box in the underlying commitment. Using specially designed ?input-delayed? protocols we realize this primitive (with a 3-round protocol in our framework) using stateless tokens and one-way functions (where the underlying one-way function is used in a black-box way).
 

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 Binary AMD Circuits from Secure Multiparty Computation
Nächstes Kapitel Composable Adaptive Secure Protocols Without Setup Under Polytime Assumptions
Fußnoten
1
In private communication, the authors have acknowledged this flaw and are in the process of updating their result. We remark that we point out a flaw only in one particular result, namely, realizing the UC-secure oblivious transfer functionality based on CRHFs and stateless tokens.
 
2
Intuitively, this attack allows the recipient of the (only) message to repeatedly evaluate the function on different inputs for a fixed sender?s input.
 
3
Note that in the plain model, without trusted setup, Katz and Ostrovsky [43] showed that five rounds are necessary and sufficient for general 2PC functionalities. Garg et al. [28] revisit the lower bound of [43] and showed that four rounds are necessary and sufficient for realizing general 2PC functionalities in the simultaneous message exchange model where both parties can simultaneously exchange messages in each round.
 
4
We remark that the work of [17] considers multiple sessions of OT between a single pair of parties. However, they do not consider multiple sessions between multiple pairs of parties which is required to realize UC-security in the multiparty setting.
 
5
Informally, the only advantage that remains for the simulator is to see the code of the tokens created by the adversary. This essentially reduces to the case where tokens are sent only in one direction and is impossible due to a result of [17] when the code is treated as a black-box.
 
6
We remark here that the functionality does not explicitly store the \(\mathsf {PID}\) of the creator of the token. We made this choice since the simulator in the ideal world will create tokens for itself which will serve as a token created on behalf of an honest party.
 
Literatur
1.
Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography in \(NC^0\). In: FOCS, pp. 166?175 (2004)
2.
Barak, B., Canetti, R., Nielsen, J.B., Pass, R.: Universally composable protocols with relaxed set-up assumptions. In: FOCS, pp. 186?195 (2004)
3.
Barak, B., Sahai, A.: How to play almost any mental game over the net - concurrent composition via super-polynomial simulation. In: FOCS, pp. 543?552 (2005)
4.
Beaver, D.: Foundations of secure interactive computing. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 377?391. Springer, Heidelberg (1992). doi:10.​1007/​3-540-46766-1_​31
5.
Boureanu, I., Ohkubo, M., Vaudenay, S.: The limits of composable crypto with transferable setup devices. In: CCS, pp. 381?392 (2015)
6.
Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: FOCS, pp. 136?145 (2001)
7.
8.
9.
Canetti, R., Jain, A., Scafuro, A.: Practical UC security with a global random oracle. In: CCS, pp. 597?608 (2014)
10.
Canetti, R., Kushilevitz, E., Lindell, Y.: On the limitations of universally composable two-party computation without set-up assumptions. J. Cryptology 19(2), 135?167 (2006)MathSciNetCrossRefMATH
11.
Canetti, R., Lin, H., Pass, R.: Adaptive hardness and composable security in the plain model from standard assumptions. In: FOCS, pp. 541?550 (2010)
12.
Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable two-party and multi-party secure computation. In: STOC (2002)
13.
Canetti, R., Pass, R., Shelat, A.: Cryptography from sunspots: how to use an imperfect reference string. In: FOCS, pp. 249?259 (2007)
14.
15.
Chandran, N., Goyal, V., Sahai, A.: New constructions for UC secure computation using tamper-proof hardware. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 545?562. Springer, Heidelberg (2008). doi:10.​1007/​978-3-540-78967-3_​31 CrossRef
16.
Choi, S.G., Katz, J., Schröder, D., Yerukhimovich, A., Zhou, H.-S.: (Efficient) universally composable oblivious transfer using a minimal numberof stateless tokens. IACR Cryptology ePrint Archive, 2013:840 (2013)
17.
Choi, S.G., Katz, J., Schröder, D., Yerukhimovich, A., Zhou, H.-S.: (Efficient) universally composable oblivious transfer using a minimal number of stateless tokens. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 638?662. Springer, Heidelberg (2014). doi:10.​1007/​978-3-642-54242-8_​27 CrossRef
18.
Ciampi, M., Ostrovsky, R., Siniscalchi, L., Visconti, I.: Concurrent non-malleable commitments (and more) in 3 rounds. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9816, pp. 270?299. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-53015-3_​10 CrossRef
19.
Michele, C., Rafail, O., Luisa, S., Ivan, V.: On round-efficient non-malleable protocols. IACR Cryptology ePrint Archive, 2016:621 (2016)
20.
Ciampi, M., Persiano, G., Scafuro, A., Siniscalchi, L., Visconti, I.: Improved or-composition of sigma-protocols. In: TCC, pp. 112?141 (2016)
21.
Ciampi, M., Persiano, G., Scafuro, A., Siniscalchi, L., Visconti, I.: Online/Offline OR composition of sigma protocols. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 63?92. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-49896-5_​3 CrossRef
22.
Dachman-Soled, D., Malkin, T., Raykova, M., Venkitasubramaniam, M.: Adaptive and concurrent secure computation from new adaptive, non-malleable commitments. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part I. LNCS, vol. 8269, pp. 316?336. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-42033-7_​17 CrossRef
23.
Döttling, N., Kraschewski, D., Müller-Quade, J.: Unconditional and composable security using a single stateful tamper-proof hardware token. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 164?181. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-19571-6_​11 CrossRef
24.
Döttling, N., Kraschewski, D., Möller-Quade, J., Nilges, T.: From stateful hardware to resettable hardware using symmetric assumptions. In: ProvSec, pp. 23?42 (2015)
25.
Döttling, N., Kraschewski, D., Müller-Quade, J., Nilges, T.: General statistically secure computation with bounded-resettable hardware tokens. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015, Part I. LNCS, vol. 9014, pp. 319?344. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-46494-6_​14
26.
Döttling, N., Mie, T., Müller-Quade, J., Nilges, T.: Implementing resettable UC-functionalities with untrusted tamper-proof hardware-tokens. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 642?661. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-36594-2_​36 CrossRef
27.
Garg, S., Gentry, C., Halevi, S., Raykova, M.: Two-round secure MPC from indistinguishability obfuscation. In: TCC, pp. 74?94 (2014)
28.
Garg, S., Mukherjee, P., Pandey, O., Polychroniadou, A.: The exact round complexity of secure computation. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 448?476. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-49896-5_​16 CrossRef
29.
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: STOC, pp. 218?229 (1987)
30.
Goyal, V., Ishai, Y., Sahai, A., Venkatesan, R., Wadia, A.: Founding cryptography on tamper-proof hardware tokens. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 308?326. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-11799-2_​19 CrossRef
31.
Goyal, V., Lee, C.-K., Ostrovsky, R., Visconti, I.: Constructing non-malleable commitments: a black-box approach. In: FOCS, pp. 51?60 (2012)
32.
Goyal, V., Richelson, S., Rosen, A., Vald, M.: An algebraic approach to non-malleability. In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, 18?21 October 2014, pp. 41?50 (2014)
33.
Haitner, I., Hoch, J.J., Reingold, O., Segev, G.: Finding collisions in interactive protocols - tight lower bounds on the round and communication complexities of statistically hiding commitments. SIAM J. Comput. 44(1), 193?242 (2015)MathSciNetCrossRefMATH
34.
Carmit, H., Antigoni, P., Muthuramakrishnan, V.: Composable security in the tamper proof hardware model under minimal complexity. IACR Cryptology ePrint Archive 2015:887 (2015)
35.
Hazay, C., Venkitasubramaniam, M.: On black-box complexity ofuniversally composable security in the CRS model. In: ASIACRYPT, pp. 183?209 (2015)
36.
Hazay, C., Venkitasubramaniam, M.: On the power of secure two-party computation. In: Robshaw, M., Katz, J., Wooten, M.B. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 397?429. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-53008-5_​14 CrossRef
37.
Brett, H., Zahra, J., Rafail, O., Alessandra, S., Daniel, W.: Adaptively secure garbled circuits from one-way functions. IACR Cryptology ePrint Archive 2015:1250 (2015)
38.
Ishai, Y., Kushilevitz, E. Randomizing polynomials: a new representation with applications to round-efficient secure computation. In: FOCS, pp. 294?304 (2000)
39.
Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Zero-knowledge proofs from secure multiparty computation. SIAM J. Comput. 39(3), 1121?1152 (2009)MathSciNetCrossRefMATH
40.
41.
Kalai, Y.T., Lindell, Y., Prabhakaran, M.: Concurrent composition of secure protocols in the timing model. J. Cryptology 20(4), 431?492 (2007)MathSciNetCrossRefMATH
42.
43.
44.
Kilian, J.: Founding cryptography on oblivious transfer. In: STOC, pp. 20?31 (1988)
45.
Lapidot, D., Shamir, A.: Publicly verifiable non-interactive zero-knowledge proofs. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 353?365. Springer, Heidelberg (1991). doi:10.​1007/​3-540-38424-3_​26
46.
Lin, H., Pass, R., Venkitasubramaniam, M.: A unified framework for concurrent security: universal composability from stand-alone non-malleability. In: STOC, pp. 179?188 (2009)
47.
48.
Lindell, Y.: General composition and universal composability in secure multi-party computation. In: FOCS, pp. 394?403 (2003)
49.
Jeremias, M., Jörn, M.-Q., Tobias, N.: Universally composable (non-interactive) two-party computation from untrusted reusable hardware tokens. IACR Cryptology ePrint Archive 2016:615 (2016)
50.
51.
Moran, T., Segev, G.: David and Goliath commitments: UC computation for asymmetric parties using tamper-proof hardware. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 527?544. Springer, Heidelberg (2008). doi:10.​1007/​978-3-540-78967-3_​30 CrossRef
52.
53.
Nilges, T.: The Cryptographic Strength of Tamper-Proof Hardware. Ph.D. thesis, Karlsruhe Institute of Technology (2015)
54.
Ostrovsky, R., Richelson, S., Scafuro, A.: Round-optimal black-box two-party computation. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 339?358. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-48000-7_​17 CrossRef
55.
Pass, R.: Simulation in quasi-polynomial time, and its application to protocol composition. In: EUROCRYPT, pp. 160?176 (2003)
56.
57.
Prabhakaran, M., Sahai, A.: New notions of security: achieving universal composability without trusted setup. In: STOC, pp. 242?251 (2004)
58.
Yao, A.C.-C.: How to generate and exchange secrets (extended abstract). In: FOCS, pp. 162?167 (1986)
Metadaten
Titel
Composable Security in the Tamper-Proof Hardware Model Under Minimal Complexity
verfasst von
Carmit Hazay
Antigoni Polychroniadou
Muthuramakrishnan Venkitasubramaniam
Copyright-Jahr
2016
Verlag
Springer Berlin Heidelberg
Buch
Theory of Cryptography

Print ISBN: 978-3-662-53640-7

Electronic ISBN: 978-3-662-53641-4

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-662-53641-4_15