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:
TinyKeys: A New Approach to Efficient Multi-Party Computation Kapitel lesen Erstes Kapitel lesen

2018 | OriginalPaper | Buchkapitel

An Optimal Distributed Discrete Log Protocol with Applications to Homomorphic Secret Sharing

verfasst von : Itai Dinur, Nathan Keller, Ohad Klein

Erschienen in: Advances in Cryptology – CRYPTO 2018

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

The distributed discrete logarithm (DDL) problem was introduced by Boyle et al. at CRYPTO 2016. A protocol solving this problem was the main tool used in the share conversion procedure of their homomorphic secret sharing (HSS) scheme which allows non-interactive evaluation of branching programs among two parties over shares of secret inputs.
Let g be a generator of a multiplicative group \(\mathbb {G}\). Given a random group element \(g^{x}\) and an unknown integer \(b \in [-M,M]\) for a small M, two parties A and B (that cannot communicate) successfully solve DDL if \(A(g^{x}) - B(g^{x+b}) = b\). Otherwise, the parties err. In the DDL protocol of Boyle et al., A and B run in time T and have error probability that is roughly linear in M/T. Since it has a significant impact on the HSS scheme’s performance, a major open problem raised by Boyle et al. was to reduce the error probability as a function of T.
In this paper we devise a new DDL protocol that substantially reduces the error probability to \(O(M \cdot T^{-2})\). Our new protocol improves the asymptotic evaluation time complexity of the HSS scheme by Boyle et al. on branching programs of size S from \(O(S^2)\) to \(O(S^{3/2})\). We further show that our protocol is optimal up to a constant factor for all relevant cryptographic group families, unless one can solve the discrete logarithm problem in a short interval of length R in time \(o(\sqrt{R})\).
Our DDL protocol is based on a new type of random walk that is composed of several iterations in which the expected step length gradually increases. We believe that this random walk is of independent interest and will find additional applications.

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 Cryptanalyses of Branching Program Obfuscations over GGH13 Multilinear Map from the NTRU Problem
Nächstes Kapitel Must the Communication Graph of MPC Protocols be an Expander?
Fußnoten
1
In all algorithms presented in this paper, the bulk of computation involves performing group operations, hence this is a reasonable complexity measure. Alternatively, the parameter T may bound the complexity of A, B in some reasonable computational model.
 
2
We note that in the applications of [4‐6], the distribution of \(b \in [-M,M]\) is arbitrary. However (as we show in Lemma 13), our choice to define and analyze DDL for the uniform distribution of \(b \in [-M,M]\) is technically justified since the uniform distribution is the hardest for DDL: algorithms for A, B that solve DDL with an error probability \(\delta \) for the uniform distribution, also solve DDL with with an error probability \(O(\delta )\) for any distribution of \(b \in [-M,M]\).
 
3
The function \(\phi \) (and additional pseudo-random functions defined in this paper) can be implemented by a keyed MAC, where the key is pre-distributed to A and B. Thus, our probabilistic calculations should be formally taken over the choice of the key. They should include an error term that accounts for the distinguishing advantage of an efficient adversary (A or B in our case) that attempts to distinguish the PRF from a truly random permutation. However, for an appropriately chosen PRF, the distinguishing advantage is negligible and we ignore it for the sake of simplicity.
 
4
Our analysis assumes that \(\psi _{L-1}\) is a truly random function and our probabilistic calculations are taken over the choice of \(\psi _{L-1}\).
 
5
We assume that the algorithm uses a table containing the pre-computed values \(g,g^2,\ldots ,g^{L-1}\). Otherwise, it has to compute \(g^{z_{i+1}}\) on-the-fly in Step 10, which results in a multiplicative penalty of \(O(\log (T))\) on the number of group operations. Of course, it is also possible to obtain a time-memory tradeoff here.
 
6
We assume in our analysis that during the application of the whole protocol by a single party, each function \(\phi ,\psi _{L-1}\) is not evaluated twice on the same input. These constrains are satisfied since \(|\mathbb {G}| = N\) is much larger than T (e.g., \(|\mathbb {G}|>cT^2\) for a sufficiently large constant c).
 
7
We note that according to the proof of Theorem 1 (given in the extended version of this paper), I can be taken to be any value between \(\log \log (T)+\omega (1)\) and \(o(\sqrt{\log (T)})\), without a significant effect on the provable performance of the algorithm. On the other hand, according to Table 1, I seems to grow more sharply. However, the restriction of \(I = o(\sqrt{\log (T)})\) is merely an artifact of the proof and the optimal value of I could be asymptotically larger. Furthermore, the sharp increase of the values of I in Table 1 could be attributed to low-order terms that have a more noticeable effect for small T values.
 
8
We consider only uniform algorithms that can be applied to families of groups (such as elliptic curve groups) and not non-uniform algorithms that are specialized to a specific group \(\mathbb {G}\). Indeed, in the non-uniform model, there exist algorithms that solve DLI in an interval of length R in time \(o(\sqrt{R})\) for any specific group (see, e.g., [2]).
 
9
More accurately, it is \(O(\delta )\), as \(\delta \) is the average error probability in the interval \([-1,1]\).
 
10
It is also possible to prove a similar bound in case the interval \([M_1,M_2]\) is not symmetric around the origin.
 
11
Alternatively, x could be in any fixed interval of length R. The exact interval is not important as one can easily reduce the problem in a given interval to any other interval.
 
12
Our actual proof is slightly more general than outlined here and uses the notion of query chains.
 
13
Our proof relaxes this strong condition, and requires that it holds unless a low-probability event (called a collision) occurs.
 
Literatur
1.
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In: Simon [19], pp. 1–10 (1988)
2.
3.
4.
Boyle, E., Couteau, G., Gilboa, N., Ishai, Y., Orrù, M.: Homomorphic secret sharing: optimizations and applications. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, Dallas, TX, USA, 30 October–03 November 2017, pp. 2105–2122. ACM (2017)
5.
6.
7.
Boyle, E., Gilboa, N., Ishai, Y., Lin, H., Tessaro, S.: Foundations of homomorphic secret sharing. In: Karlin, A.R. (ed.) 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, Cambridge, MA, USA, 11–14 January 2018. LIPIcs, vol. 94, pp. 21:1–21:21. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018)
8.
Chaum, D., Crépeau, C., Damgård, I.: Multiparty unconditionally secure protocols (extended abstract). In: Simon [19], pp. 11–19 (1988)
9.
Chor, B., Kushilevitz, E., Goldreich, O., Sudan, M.: Private information retrieval. J. ACM 45(6), 965–981 (1998)MathSciNetCrossRef
10.
11.
Galbraith, S.D., Pollard, J.M., Ruprai, R.S.: Computing discrete logarithms in an interval. Math. Comput. 82(282), 1181–1195 (2013)MathSciNetCrossRef
12.
Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Mitzenmacher, M. (ed.) Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, 31 May–2 June 2009, pp. 169–178. ACM (2009)
13.
Gordon, D.M.: Discrete logarithms in GF(P) using the number field sieve. SIAM J. Discret. Math. 6(1), 124–138 (1993)MathSciNetCrossRef
14.
15.
Pollard, J.M.: Monte Carlo methods for index computation \(({\rm mod}\ p)\). Math. Comput. 32(143), 918–924 (1978)MATH
16.
17.
Rivest, R.L., Adleman, L., Dertouzos, M.L.: On data banks and privacy homomorphisms. In: Foundations of Secure Computation, pp. 169–179 (1978)
18.
19.
Simon, J. (ed.): Proceedings of the 20th Annual ACM Symposium on Theory of Computing, Chicago, Illinois, USA, 2–4 May 1988. ACM (1988)
20.
Yao, A.C.: Protocols for secure computations (extended abstract). In: 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3–5 November 1982, pp. 160–164. IEEE Computer Society (1982)
Metadaten
Titel
An Optimal Distributed Discrete Log Protocol with Applications to Homomorphic Secret Sharing
verfasst von
Itai Dinur
Nathan Keller
Ohad Klein
Copyright-Jahr
2018
Buch
Advances in Cryptology – CRYPTO 2018

Print ISBN: 978-3-319-96877-3

Electronic ISBN: 978-3-319-96878-0

Copyright-Jahr: 2018

DOI
https://doi.org/10.1007/978-3-319-96878-0_8