nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

A Quantum-Proof Non-malleable Extractor

With Application to Privacy Amplification Against Active Quantum Adversaries

verfasst von : Divesh Aggarwal, Kai-Min Chung, Han-Hsuan Lin, Thomas Vidick

Erschienen in: Advances in Cryptology – EUROCRYPT 2019

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

In privacy amplification, two mutually trusted parties aim to amplify the secrecy of an initial shared secret X in order to establish a shared private key K by exchanging messages over an insecure communication channel. If the channel is authenticated the task can be solved in a single round of communication using a strong randomness extractor; choosing a quantum-proof extractor allows one to establish security against quantum adversaries.

In the case that the channel is not authenticated, this simple solution is no longer secure. Nevertheless, Dodis and Wichs (STOC’09) showed that the problem can be solved in two rounds of communication using a non-malleable extractor, a stronger pseudo-random construction than a strong extractor.

We give the first construction of a non-malleable extractor that is secure against quantum adversaries. The extractor is based on a construction by Li (FOCS’12), and is able to extract from source of min-entropy rates larger than 1 / 2. Combining this construction with a quantum-proof variant of the reduction of Dodis and Wichs, due to Cohen and Vidick (unpublished) we obtain the first privacy amplification protocol secure against active quantum adversaries.

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 Quantum Circuits for the CSIDH: Optimizing Quantum Evaluation of Isogenies

Nächstes Kapitel A Note on the Communication Complexity of Multiparty Computation in the Correlated Randomness Model

Nur mit Berechtigung zugänglich

QKD relies on an authenticated channel at other stages of the protocol, and here we only address the privacy amplification part: indeed, PA plays an important role in multiple other cryptographic protocols, and it is a fundamental task that it is useful to address first.

This description is a little different from Li’s description since he was working with a field of size \(2^n\), but we find it more convenient to work with a prime field.

The correspondence between security of quantum-proof strong extractors and communication problems has been used repeatedly before, see e.g. [21, 22].

When restricted to \(\mathbb {F}_2\), our standard XOR lemma is very similar to Lemma 10 of [22], although the result from [22] provides a tighter bound in this case. [22] provides a bound of \(p^{2t}\epsilon ^2\), while ours scales as \(p^t \epsilon \), a quadratic loss. However our result applies to \(\mathbb {F}_p\), while it is unclear whether the proof of [22] generalizes to \(p>2\). [22] obtains the result by Fourier analysis.

The term “quantum collision probability” is ours.

Compared to [27, Lemma 3.15], we have \(m=1\) and \(n=t\).

It is not necessary for the definition to specify exactly how the protocols are formulated; informally, each player’s actions is described by a sequence of efficient algorithms that compute the player’s next message, given the past interaction.

Aggarwal, D., Chung, K.-M., Lin, H.-H., Vidick, T.: A quantum-proof non-malleable extractor, with application to privacy amplification against active quantum adversaries. arXiv preprint arXiv:1710.00557 (2017)

Aggarwal, D., Dodis, Y., Jafargholi, Z., Miles, E., Reyzin, L.: Amplifying privacy in privacy amplification. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. Part II. LNCS, vol. 8617, pp. 183–198. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44381-1_11CrossRefMATH

Aggarwal, D., Hosseini, K., Lovett, S.: Affine-malleable extractors, spectrum doubling, and application to privacy amplification. In: 2016 IEEE International Symposium on Information Theory (ISIT), pp. 2913–2917. IEEE (2016)

Bennett, C.H., Brassard, G., Crépeau, C., Maurer, U.M.: Generalized privacy amplification. IEEE Trans. Inf. Theory 41(6), 1915–1923 (1995)MathSciNetCrossRef

Bennett, C.H., Brassard, G., Robert, J.-M.: Privacy amplification by public discussion. SIAM J. Comput. 17(2), 210–229 (1988)MathSciNetCrossRef

Bhatia, R.: Matrix Analysis. Graduate Texts in Mathematics. Springer, Heidelberg (1997). https://doi.org/10.1007/978-1-4612-0653-8CrossRefMATH

Bouman, N.J., Fehr, S.: Secure authentication from a weak key, without leaking information. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 246–265. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20465-4_15CrossRef

Chandran, N., Kanukurthi, B., Ostrovsky, R., Reyzin, L.: Privacy amplification with asymptotically optimal entropy loss. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5–8 June 2010, pp. 785–794 (2010)

Chattopadhyay, E., Goyal, V., Li, X.: Non-malleable extractors and codes, with their many tampered extensions. arXiv preprint arXiv:1505.00107 (2015)

10.

Chung, K.-M., Li, X., Wu, X.: Multi-source randomness extractors against quantum side information, and their applications (2014)

11.

Cleve, R., van Dam, W., Nielsen, M., Tapp, A.: Quantum entanglement and the communication complexity of the inner product function. In: Williams, C.P. (ed.) QCQC 1998. LNCS, vol. 1509, pp. 61–74. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-49208-9_4CrossRefMATH

12.

Cohen, G.: Non-malleable extractors - new tools and improved constructions. Electron. Colloq. Comput. Complex. (ECCC) 22, 183 (2015)

13.

Cohen, G., Raz, R., Segev, G.: Non-malleable extractors with short seeds and applications to privacy amplification. In: 2012 IEEE 27th Annual Conference on Computational Complexity (CCC), pp. 298–308. IEEE (2012)

14.

Cohen, G., Vidick, T.: Privacy amplification against active quantum adversaries (2016)

15.

De, A., Portmann, C., Vidick, T., Renner, R.: Trevisan’s extractor in the presence of quantum side information. SIAM J. Comput. 41(4), 915–940 (2012)MathSciNetCrossRef

16.

Dodis, Y., Kanukurthi, B., Katz, J., Reyzin, L., Smith, A.: Robust fuzzy extractors and authenticated key agreement from close secrets. IEEE Trans. Inf. Theory 58(9), 6207–6222 (2012)MathSciNetCrossRef

17.

Dodis, Y., Li, X., Wooley, T.D., Zuckerman, D.: Privacy amplification and nonmalleable extractors via character sums. SIAM J. Comput. 43(2), 800–830 (2014)MathSciNetCrossRef

18.

Dziembowski, S., Pietrzak, K.: Leakage-resilient cryptography. In: 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 293–302. IEEE (2008)

19.

Dodis, Y., Wichs, D.: Non-malleable extractors and symmetric key cryptography from weak secrets. In: Mitzenmacher, M (ed.) Proceedings of the 41st Annual ACM Symposium on Theory of Computing, Bethesda, MD, USA, pp. 601–610. ACM (2009)

20.

Dodis, Y., Yu, Y.: Overcoming weak expectations. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 1–22. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36594-2_1CrossRef

21.

Gavinsky, D., Kempe, J., Kerenidis, I., Raz, R., De Wolf, R.: Exponential separations for one-way quantum communication complexity, with applications to cryptography. In: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, pp. 516–525. ACM (2007)

22.

Kasher, R., Kempe, J.: Two-source extractors secure against quantum adversaries. Theory Comput. 8(1), 461–486 (2012)MathSciNetCrossRef

23.

Koenig, R., Renner, R., Schaffner, C.: The operational meaning of min-and max-entropy. IEEE Trans. Inf. Theory 55(9), 4337–4347 (2009)MathSciNetCrossRef

24.

Lee, C.-J., Lu, C.-J., Tsai, S.-C., Tzeng, W.-G.: Extracting randomness from multiple independent sources. IEEE Trans. Inf. Theory 51(6), 2224–2227 (2005)MathSciNetCrossRef

25.

Li, X.: Design extractors, non-malleable condensers and privacy amplification. In: Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, 19–22 May 2012, pp. 837–854 (2012)

26.

Li, X.: Non-malleable condensers for arbitrary min-entropy, and almost optimal protocols for privacy amplification. CoRR, abs/1211.0651 (2012)

27.

Li, X.: Non-malleable extractors, two-source extractors and privacy amplification. In: FOCS, pp. 688–697 (2012)

28.

Li, X.: Non-malleable condensers for arbitrary min-entropy, and almost optimal protocols for privacy amplification. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. Part I. LNCS, vol. 9014, pp. 502–531. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46494-6_21CrossRef

29.

Li, X.: Improved non-malleable extractors, non-malleable codes and independent source extractors. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, 19–23 June 2017, pp. 1144–1156 (2017)

30.

Maurer, U.: Conditionally-perfect secrecy and a provably-secure randomized cipher. J. Cryptol. 5(1), 53–66 (1992)MathSciNetCrossRef

31.

Maurer, U., Wolf, S.: Privacy amplification secure against active adversaries. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 307–321. Springer, Heidelberg (1997). https://doi.org/10.1007/BFb0052244CrossRef

32.

Nayak, A., Salzman, J.: Limits on the ability of quantum states to convey classical messages. J. ACM (JACM) 53(1), 184–206 (2006)MathSciNetCrossRef

33.

Nisan, N., Zuckerman, D.: Randomness is linear in space. J. Comput. Syst. Sci. 52(1), 43–53 (1996)MathSciNetCrossRef

34.

Renner, R., König, R.: Universally composable privacy amplification against quantum adversaries. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 407–425. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-30576-7_22CrossRef

35.

Renner, R., Wolf, S.: Unconditional authenticity and privacy from an arbitrarily weak secret. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 78–95. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45146-4_5CrossRef

36.

Tomamichel, M., Schaffner, C., Smith, A.D., Renner, R.: Leftover hashing against quantum side information. IEEE Trans. Inf. Theory 57(8), 5524–5535 (2011)MathSciNetCrossRef

37.

Vitanov, A., Dupuis, F., Tomamichel, M., Renner, R.: Chain rules for smooth min-and max-entropies. IEEE Trans. Inf. Theory 59(5), 2603–2612 (2013)MathSciNetCrossRef

Titel: A Quantum-Proof Non-malleable Extractor
verfasst von: Divesh Aggarwal
Kai-Min Chung
Han-Hsuan Lin
Thomas Vidick
Verlag: Springer International Publishing
Buch: Advances in Cryptology – EUROCRYPT 2019
Print ISBN: 978-3-030-17655-6

Electronic ISBN: 978-3-030-17656-3

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-17656-3_16

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"