nach oben

Erschienen in:

2023 | OriginalPaper | Buchkapitel

Anonymous Permutation Routing

verfasst von : Paul Bunn, Eyal Kushilevitz, Rafail Ostrovsky

Erschienen in: Theory of Cryptography

Verlag: Springer Nature Switzerland

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

The Non-Interactive Anonymous Router (NIAR) model was introduced by Shi and Wu [SW21] as an alternative to conventional solutions to the anonymous routing problem, in which a set of senders wish to send messages to a set of receivers. In contrast to most known approaches to support anonymous routing (e.g. mix-nets, DC-nets, etc.), which rely on a network of routers communicating with users via interactive protocols, the NIAR model assumes a single router and is inherently non-interactive (after an initial setup phase). In addition to being non-interactive, the NIAR model is compelling due to the security it provides: instead of relying on the honesty of some subset of the routers, the NIAR model requires anonymity even if the router (as well as an arbitrary subset of senders/receivers) is corrupted by an honest-but-curious adversary.

In this paper, we present a protocol for the NIAR model that improves upon the results from [SW21] in two ways:

Improved computational efficiency (quadratic to near linear): Our protocol matches the communication complexity of [SW21] for each sender/receiver, while reducing the computational overhead for the router to polylog overhead instead of linear overhead.
Relaxation of assumptions: Security of the protocol in [SW21] relies on the Decisional Linear assumption in bilinear groups; while security for our protocol follows from the existence of any rate-1 oblivious transfer (OT) protocol (instantiations of which are known to exist under the DDH, QR and LWE assumptions [DGI+19, GHO20]).

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 Lower Bounds on Anonymous Whistleblowing

Nächstes Kapitel Non-Interactive Anonymous Router with Quasi-Linear Router Computation

Our limitation to HBC adversaries is only needed to ensure Correctness of our protocol - that receivers get the correct messages. We note that requiring HBC for correctness is unavoidable, as a malicious router can, for example, not forward any message (like in PIR and other related primitives). In terms of Security (privacy of the senders-receivers permutation): so long as the one-time Setup is performed properly, then security of our protocol will hold in the Malicious adversary setting.

Router computation is not explicitly measured in the protocol of [SW21], our analysis of their protocol yields \(O(N^2)\) computation load on the router: their Multi-Client Functional Encryption (MCFE) protocol is invoked N times by the router, with each invocation processing N ciphertexts.

The sender keys \(\{pk_i\}\) are associated with the receiver keys \(\{sk_i\}\) via the permutation \(\sigma \); namely, secret key \(sk_{\sigma (i)}\) can decrypt messages encrypted under \(pk_i\).

Trusted setup is required for establishing public/secret key pairs for encryption and for instantiating ideal functionality \(\varPi _{ORG}(G,\widehat{c},r,l,\varPi _{1{-}PIR})\).

A colored butterfly network can be viewed as c disjoint butterfly networks overlaid on top of one another. Alternatively, we can view a colored butterfly network as a single (connected) graph by adding an extra input level (with level index \(-1\)) on the far left, consisting of N input nodes. Then there are c edges emanating from each input node, connecting it to each of the c colored nodes in level 0 of the corresponding row.

In the special case of the (1+\(b)^{th}\) block, the first \(\log N\) levels of this block are a reflected butterfly network, and the last level of the block is the final “output” level of the entire network.

Notice \(a_\lambda = 2\) if \(\lambda \le N/2\).

Notice that if \(\mu _i = \mu _{i'}\), then \(\varPi '_{i,i',j}\) is identical to \(\varPi \) (for all paths \(\{\mathcal {P}_i\}\)) on all blocks through j (including block j).

Swapping paths is only necessary for the sake of making sure the paths link up/connect between blocks (since output node \(\mu _i\) and \(\mu _{i'}\) were swapped in block j). However, as was noted in the Aside note following Definition 20, the details of what \(\varPi '_{i,i',j}\) does beyond block j will be irrelevant for the context of Lemmas 22 and 25.

Notice that these parameter values all match those in the hypothesis of Corollary 19.

This information is also available indirectly from what \(\mathcal {C}\) gives to \(\mathcal {A}\) in Step 5 a below.

[AKS83]

Ajtai, M., Komlós, J., Szemerédi, E.: An o(n log n) sorting network. In: Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25–27 April 1983, pp. 1–9. ACM (1983)

[CGH+21]

Chase, M., Garg, S., Hajiabadi, M., Li, J., Miao, P.: Amortizing rate-1 OT and applications to PIR and PSI. In: Nissim, K., Waters, B. (eds.) TCC 2021. LNCS, vol. 13044, pp. 126–156. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-90456-2_5CrossRef

[CGKS95]

Chor, B., Kushilevitz, E., Goldreich, O., Sudan, M.: Private information retrieval. In: 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23–25 October 1995, pp. 41–50. IEEE Computer Society (1995)

[COS10]

Chandran, N., Ostrovsky, R., Skeith, W.E.: Public-key encryption with efficient amortized updates. In: Garay, J.A., De Prisco, R. (eds.) SCN 2010. LNCS, vol. 6280, pp. 17–35. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15317-4_2CrossRef

[DGI+19]

Döttling, N., Garg, S., Ishai, Y., Malavolta, G., Mour, T., Ostrovsky, R.: Trapdoor hash functions and their applications. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11694, pp. 3–32. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26954-8_1CrossRef

[FSSV22]

Fernando, R., Shi, E., Soni, P., Vanjani, N.: Non-interactive anonymous router with quasi-linear router computation. IACR Cryptology ePrint Archive, Paper 1395 (2022)

[GHO20]

Garg, S., Hajiabadi, M., Ostrovsky, R.: Efficient range-trapdoor functions and applications: rate-1 OT and more. In: Pass, R., Pietrzak, K. (eds.) TCC 2020. LNCS, vol. 12550, pp. 88–116. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64375-1_4CrossRef

[HOWW19]

Hamlin, A., Ostrovsky, R., Weiss, M., Wichs, D.: Private anonymous data access. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11477, pp. 244–273. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17656-3_9CrossRef

[IKOS04]

Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Batch codes and their applications. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 262–271. ACM (2004)

[IP07]

Ishai, Y., Paskin, A.: Evaluating branching programs on encrypted data. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 575–594. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-70936-7_31CrossRef

[KO97]

Kushilevitz, E., Ostrovsky, R.: Replication is NOT needed: SINGLE database, computationally-private information retrieval. In: 38th Annual Symposium on Foundations of Computer Science, FOCS 1997, 19–22 October 1997, pp. 364–373. IEEE Computer Society (1997)

[Lei84]

Leighton, F.T.: Tight bounds on the complexity of parallel sorting. In: Proceedings of the 16th Annual ACM Symposium on Theory of Computing, pp. 71–80. ACM (1984)

[LMW22]

Lin, W.-K., Mook, E., Wichs, D.: Doubly efficient private information retrieval and fully homomorphic RAM computation from ring LWE. IACR Cryptology ePrint Archive, Paper 1703 (2022)

[MS92]

Maggs, B.M., Sitaraman, R.K.: Simple algorithms for routing on butterfly networks with bounded queues (ext. abstract). In: 24th Annual ACM Symposium on Theory of Computing, pp. 150–161. ACM (1992)

[OS07]

Ostrovsky, R., Skeith, W.E.: A survey of single-database private information retrieval: techniques and applications. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 393–411. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-71677-8_26CrossRef

[SW21]

Shi, E., Wu, K.: Non-interactive anonymous router. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12698, pp. 489–520. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77883-5_17CrossRef

[Upf89]

Upfal, E.: An o(log N) deterministic packet routing scheme (preliminary version). In: Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pp. 241–250. ACM (1989)

Titel: Anonymous Permutation Routing
verfasst von: Paul Bunn
Eyal Kushilevitz
Rafail Ostrovsky
Verlag: Springer Nature Switzerland
Buch: Theory of Cryptography
Print ISBN: 978-3-031-48620-3

Electronic ISBN: 978-3-031-48621-0

Copyright-Jahr: 2023
DOI: https://doi.org/10.1007/978-3-031-48621-0_2

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