nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Topology-Hiding Computation for Networks with Unknown Delays

verfasst von : Rio LaVigne, Chen-Da Liu-Zhang, Ueli Maurer, Tal Moran, Marta Mularczyk, Daniel Tschudi

Erschienen in: Public-Key Cryptography – PKC 2020

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

Topology-Hiding Computation (THC) allows a set of parties to securely compute a function over an incomplete network without revealing information on the network topology. Since its introduction in TCC’15 by Moran et al., the research on THC has focused on reducing the communication complexity, allowing larger graph classes, and tolerating stronger corruption types.

All of these results consider a fully synchronous model with a known upper bound on the maximal delay of all communication channels. Unfortunately, in any realistic setting this bound has to be extremely large, which makes all fully synchronous protocols inefficient. In the literature on multi-party computation, this is solved by considering the fully asynchronous model. However, THC is unachievable in this model (and even hard to define), leaving even the definition of a meaningful model as an open problem.

The contributions of this paper are threefold. First, we introduce a meaningful model of unknown and random communication delays for which THC is both definable and achievable. The probability distributions of the delays can be arbitrary for each channel, but one needs to make the (necessary) assumption that the delays are independent. The existing fully-synchronous THC protocols do not work in this setting and would, in particular, leak information about the topology. Second, in the model with trusted stateless hardware boxes introduced at Eurocrypt’18 by Ball et al., we present a THC protocol that works for any graph class. Third, we explore what is achievable in the standard model without trusted hardware and present a THC protocol for specific graph types (cycles and trees) secure under the DDH assumption. The speed of all protocols scales with the actual (unknown) delay times, in contrast to all previously known THC protocols whose speed is determined by the assumed upper bound on the network delay.

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 Threshold Schemes from Isogeny Assumptions

Nächstes Kapitel Sublinear-Round Byzantine Agreement Under Corrupt Majority

Nur mit Berechtigung zugänglich

Our second protocol works for any graphs, as long as we agree to reveal a spanning tree: the parties know which of their edges are on the tree and execute the protocol, ignoring other edges. See also [AM17].

The difference here is that a token typically needs to be passed around during the protocol and the parties can embed their own programs in it, whereas a secure hardware box is used only by one party and is initialized with the correct program.

In fact, our hardware-based protocol does not use this information, and our protocols for cycles and trees only need upper bounds on the expected values of the delays. This bound can be easily established, e.g. by probing the connection.

Its functionality does not matter and is left undefined on encryptions of 1.

If the parties do not send at every round, the topology would leak. Intuitively, when a party \(P_i\) sends the initial message to its right neighbor \(P_j\), the right neighbor of \(P_j\) learns how big the delay from \(P_i\) to \(P_j\) was. We can extend this to larger neighborhood, eventually revealing information about relative positions of corrupted parties.

Note that delays between rounds are independent, but not within the round. This means we need to send copies of the message over multiple rounds for this strategy to work.

Note that the round length \(R\) is a parameter of the protocol, so we allow the adversary to provide it.

In practice, this is not an unrealistic assumption. It would be enough, for example, if each party was given a very rough upper bound on the time it takes to flood the network and traverse all edges of the graph (for instance, a constant number proportional to the sum of delays on all edges). This is still faster than assuming worst-case upper bounds on the delays along edges, as one would need to do to adapt a fully synchronous protocol.

Intuitively, a functionality is well-formed if its code does not depend on the ID’s of the corrupted parties. We refer to [CLOS02] for a detailed description.

In PKCR of [ALM17], computing \(\texttt {pk} _1 \circledast \texttt {pk} _2\) does not require the secret key. Moreover, PKCR requires perfect correctness.

In [ALM17] the rerandomization algorithm is given the public key as input. We also note that they require public keys to be re-randomizable, while we do not need this property.

Akavia, Adi, LaVigne, Rio, Moran, Tal: Topology-Hiding Computation on All Graphs. In: Katz, Jonathan, Shacham, Hovav (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 447–467. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_15CrossRef

Akavia, Adi, Moran, Tal: Topology-Hiding Computation Beyond Logarithmic Diameter. In: Coron, Jean-Sébastien, Nielsen, Jesper Buus (eds.) EUROCRYPT 2017. LNCS, vol. 10212, pp. 609–637. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56617-7_21CrossRef

Bellare, Mihir, Boldyreva, Alexandra, Desai, Anand, Pointcheval, David: Key-Privacy in Public-Key Encryption. In: Boyd, Colin (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 566–582. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45682-1_33CrossRefMATH

Marshall Ball, Elette Boyle, Tal Malkin, and Tal Moran. Exploring the boundaries of topology-hiding computation. In Eurocrypt’18, 2018

Michael Ben-Or, Ran Canetti, and Oded Goldreich. Asynchronous secure computation. In 25th ACM STOC, pages 52–61. ACM Press, May 1993

Ran Canetti. Universally composable security: A new paradigm for cryptographic protocols. In 42nd FOCS, pages 136–145. IEEE Computer Society Press, October 2001

Cohen, Ran, Coretti, Sandro, Garay, Juan, Zikas, Vassilis: Probabilistic Termination and Composability of Cryptographic Protocols. In: Robshaw, Matthew, Katz, Jonathan (eds.) CRYPTO 2016. LNCS, vol. 9816, pp. 240–269. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53015-3_9CrossRef

Nishanth Chandran, Vipul Goyal, and Amit Sahai. New constructions for uc secure computation using tamper-proof hardware. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 545–562. Springer, 2008

Seung Geol Choi, Jonathan Katz, Dominique Schröder, Arkady Yerukhimovich, and Hong-Sheng Zhou. (efficient) universally composable oblivious transfer using a minimal number of stateless tokens. In Theory of Cryptography Conference, pages 638–662. Springer, 2014

Ran Canetti, Yehuda Lindell, Rafail Ostrovsky, and Amit Sahai. Universally composable two-party and multi-party secure computation. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 494–503. ACM, 2002

Chiesa, Alessandro, Tromer, Eran: Proof-carrying data and hearsay arguments from signature cards. ICS 10, 310–331 (2010)

Damgård, Ivan, Ishai, Yuval: Constant-Round Multiparty Computation Using a Black-Box Pseudorandom Generator. In: Shoup, Victor (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 378–394. Springer, Heidelberg (2005). https://doi.org/10.1007/11535218_23CrossRef

Fleury, M.: Deux problèmes de géométrie de situation. Journal de mathématiques élémentaires 2, 257–261 (1883)

H Fleischner. X. 1 algorithms for eulerian trails. Eulerian Graphs and Related Topics: Part 1 (Annals of Discrete Mathematics), 2(50):1–13, 1991

Vipul Goyal, Yuval Ishai, Amit Sahai, Ramarathnam Venkatesan, and Akshay Wadia. Founding cryptography on tamper-proof hardware tokens. In Theory of Cryptography Conference, pages 308–326. Springer, 2010

Hinkelmann, Markus, Jakoby, Andreas: Communications in unknown networks: Preserving the secret of topology. Theoretical Computer Science 384(2–3), 184–200 (2007)MathSciNetCrossRef

Dennis Hofheinz, Jörn Müller-Quade, and Dominique Unruh. Universally composable zero-knowledge arguments and commitments from signature cards. In 5th Central European Conference on Cryptology, 2005

Hirt, Martin, Maurer, Ueli, Tschudi, Daniel, Zikas, Vassilis: Network-Hiding Communication and Applications to Multi-party Protocols. In: Robshaw, Matthew, Katz, Jonathan (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 335–365. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53008-5_12CrossRef

Katz, Jonathan, Maurer, Ueli, Tackmann, Björn, Zikas, Vassilis: Universally Composable Synchronous Computation. In: Sahai, Amit (ed.) TCC 2013. LNCS, vol. 7785, pp. 477–498. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36594-2_27CrossRef

Rio Lavigne, Chen-Da Liu-Zhang, Ueli Maurer, Tal Moran, Marta Mularczyk, and Daniel Tschudi. Topology-hiding computation beyond semi-honest adversaries. In Theory of Cryptography Conference, to appear, 2018

Rio LaVigne, Chen-Da Liu-Zhang, Ueli Maurer, Tal Moran, Marta Mularczyk, and Daniel Tschudi. Topology-hiding computation for networks with unknown delays. Cryptology ePrint Archive, Report 2019/1211, 2019. https://eprint.iacr.org/2019/1211

Lindell, Yehuda, Pinkas, Benny, Smart, Nigel P., Yanai, Avishay: Efficient Constant Round Multi-party Computation Combining BMR and SPDZ. In: Gennaro, Rosario, Robshaw, Matthew (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 319–338. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48000-7_16CrossRef

SAM Makki. A distributed algorithm for constructing an eulerian tour. In Performance, Computing, and Communications Conference, 1997. IPCCC 1997, IEEE International, pages 94–100. IEEE, 1997

Moran, Tal, Orlov, Ilan, Richelson, Silas: Topology-Hiding Computation. In: Dodis, Yevgeniy, Nielsen, Jesper Buus (eds.) TCC 2015. LNCS, vol. 9014, pp. 159–181. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46494-6_8CrossRef

Titel: Topology-Hiding Computation for Networks with Unknown Delays
verfasst von: Rio LaVigne
Chen-Da Liu-Zhang
Ueli Maurer
Tal Moran
Marta Mularczyk
Daniel Tschudi
Verlag: Springer International Publishing
Buch: Public-Key Cryptography – PKC 2020
Print ISBN: 978-3-030-45387-9

Electronic ISBN: 978-3-030-45388-6

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-45388-6_8

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"