Top

Published in:

2021 | OriginalPaper | Chapter

Rate-1 Key-Dependent Message Security via Reusable Homomorphic Extractor Against Correlated-Source Attacks

Authors : Qiqi Lai, Feng-Hao Liu, Zhedong Wang

Published in: Public-Key Cryptography – PKC 2021

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this work, we first present general methods to construct information rate-1 PKE that is \(\mathsf {KDM}^{(n)}\)-secure with respect to block-affine functions for any unbounded polynomial n. To achieve this, we propose a new notion of extractor that satisfies reusability, homomorphic, and security against correlated-source attacks, and show how to use this extractor to improve the information rate of the \(\mathsf {KDM}\)-secure PKE of Brakerski et al. (Eurocrypt 18). Then, we show how to amplify \(\mathsf {KDM}\) security from block-affine function class into general bounded size circuits via a variant of the technique of Applebaum (Eurocrypt 11), achieving better efficiency. Furthermore, we show how to generalize these approaches to the IBE setting.

Additionally, our PKE and IBE schemes are also leakage resilient, with leakage rates \(1-o(1)\) against a slightly smaller yet still general class – block leakage functions. We can instantiate the required building blocks from \(\mathsf {LWE}\) or \(\mathsf {DDH}\).

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter Impossibility on Tamper-Resilient Cryptography with Uniqueness Properties

next chapter Two-Party Adaptor Signatures from Identification Schemes

Information rate is defined as the message-to-ciphertext ratio when one encrypts sufficiently long plaintexts.

When the secret key is stored in blocks, a block leakage function can leak individual blocks one after another, as long as the blocks still remain a block source.

The extractor can extract uniform string (up to statistical distance \(\varepsilon \)) for any source with min-entropy k.

Clearly, this notion cannot be achieved unconditionally, as an information-theoretic extractor requires (conditional) min-entropy from the source, which would be exhausted after a bounded number of extractions.

Clearly, this notion is stronger than the reusable extractor, which can be viewed as a special case where \(\mathfrak {g}_i\)’s are all the identity function. Thus, this notion is only possible under computational assumptions.

Here, t denotes the number of times the weak source being reused.

Just as described in full version, block leakage means that each block of source is leaked by an independent function and remain enough entropy conditioned on leakage against other blocks.

In [4], Applebaum leverages the abstract notion of randomized encoding to achieve \(\mathsf {KDM}\) amplification. Here, we directly amplify our scheme through using Garbled Circuits, which is a well-known instantiation of randomized encoding.

Adão, P., Bana, G., Herzog, J., Scedrov, A.: Soundness of formal encryption in the presence of key-cycles. In: di Vimercati, S.C., Syverson, P., Gollmann, D. (eds.) ESORICS 2005. LNCS, vol. 3679, pp. 374–396. Springer, Heidelberg (2005). https://doi.org/10.1007/11555827_22CrossRef

Alwen, J., Dodis, Y., Naor, M., Segev, S. Walfish, G., Wichs, D.: Public-key encryption in the bounded-retrieval model. In: Gilbert [17], pp. 113–134

Alwen, J., Krenn, S., Pietrzak, K., Wichs, D.: Learning with rounding, revisited. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 57–74. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_4CrossRef

Applebaum, B.: Key-dependent message security: generic amplification and completeness. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 527–546. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20465-4_29CrossRef

Applebaum, B., Cash, D., Peikert, C., Sahai, A.: Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In: Halevi [20], pp. 595–618

Banerjee, A., Peikert, C., Rosen, A.: Pseudorandom functions and lattices. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 719–737. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_42CrossRef

Barak, B., Haitner, I., Hofheinz, D., Ishai, Y. Bounded key-dependent message security. In: Gilbert [17], pp. 423–444

Black, J., Rogaway, P., Shrimpton, T.: Encryption-scheme security in the presence of key-dependent messages. In: Nyberg, K., Heys, H. (eds.) SAC 2002. LNCS, vol. 2595, pp. 62–75. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36492-7_6CrossRefMATH

Boneh, D., Halevi, S., Hamburg, M., Ostrovsky, R.: Circular-secure encryption from decision Diffie-Hellman. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 108–125. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85174-5_7CrossRef

10.

Brakerski, Z., Goldwasser, S.: Circular and leakage resilient public-key encryption under subgroup indistinguishability. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 1–20. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_1CrossRef

11.

Brakerski, Z., Goldwasser, S., Kalai, Y.T.: Black-box circular-secure encryption beyond affine functions. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 201–218. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19571-6_13CrossRef

12.

Brakerski, Z., Lombardi, A., Segev, G., Vaikuntanathan, V.: Anonymous IBE, leakage resilience and circular security from new assumptions. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10820, pp. 535–564. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78381-9_20CrossRef

13.

Camenisch, J., Lysyanskaya, A.: An efficient system for non-transferable anonymous credentials with optional anonymity revocation. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 93–118. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44987-6_7CrossRef

14.

Dodis, Y., Kalai, Y.T., Lovett, S.: On cryptography with auxiliary input. In: Mitzenmacher, M. (ed.) 41st ACM STOC, pp. 621–630. ACM Press, May/June (2009)

15.

Dodis, Y., Ostrovsky, R., Reyzin, L., Smith, A.D.: Fuzzy extractors: how to generate strong keys from biometrics and other noisy data. SIAM J. Comput. 38(1), 97–139 (2008)MathSciNetCrossRef

16.

Döttling, N.: Low noise LPN: KDM secure public key encryption and sample amplification. In: Katz, J. (ed.) PKC 2015. LNCS, vol. 9020, pp. 604–626. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46447-2_27CrossRefMATH

17.

Gilbert, H. (ed.): EUROCRYPT 2010, volume 6110 of LNCS. Springer, Heidelberg, May/June 2010

18.

Goldwasser, S., Micali, S.: Probabilistic encryption. J. Comput. Syst. Sci. 28(2), 270–299 (1984)MathSciNetCrossRef

19.

Goyal, V., Song, Y.: Correlated-source extractors and cryptography with correlated-random tapes. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11476, pp. 562–592. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17653-2_19CrossRef

20.

Halevi, S. (ed.): CRYPTO 2009. LNCS, vol. 5677. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03356-8CrossRefMATH

21.

Hazay, C., López-Alt, A., Wee, H., Wichs, D.: Leakage-resilient cryptography from minimal assumptions. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 160–176. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38348-9_10CrossRef

22.

Hofheinz, D., Unruh, D.: Towards key-dependent message security in the standard model. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 108–126. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78967-3_7CrossRefMATH

23.

Kitagawa, F., Tanaka, K.: Key dependent message security and receiver selective opening security for identity-based encryption. In: Abdalla, M., Dahab, R. (eds.) PKC 2018, Part I. LNCS, vol. 10769, pp. 32–61. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-76578-5_2CrossRef

24.

Laud, P., Corin, R.: Sound computational interpretation of formal encryption with composed keys. In: Lim, J.-I., Lee, D.-H. (eds.) ICISC 2003. LNCS, vol. 2971, pp. 55–66. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24691-6_5CrossRef

25.

Naor, M., Segev, G.: Public-key cryptosystems resilient to key leakage. In: Halevi [20], pp. 18–35

26.

Vadhan, S.P.: Pseudorandomness. Found. Trends® Theor. Comput. Sci. 7(1–3), 1–336 (2012)

27.

Wee, H.: KDM-security via homomorphic smooth projective hashing. In: Cheng, C.-M., Chung, K.-M., Persiano, G., Yang, B.-Y. (eds.) PKC 2016, Part II. LNCS, vol. 9615, pp. 159–179. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49387-8_7CrossRef

Title: Rate-1 Key-Dependent Message Security via Reusable Homomorphic Extractor Against Correlated-Source Attacks
Authors: Qiqi Lai
Feng-Hao Liu
Zhedong Wang
Publisher: Springer International Publishing
Book: Public-Key Cryptography – PKC 2021
Print ISBN: 978-3-030-75244-6

Electronic ISBN: 978-3-030-75245-3

Copyright Year: 2021
DOI: https://doi.org/10.1007/978-3-030-75245-3_16

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner