Skip to main content

2018 | OriginalPaper | Buchkapitel

Leakage-Resilient Cryptography from Puncturable Primitives and Obfuscation

verfasst von : Yu Chen, Yuyu Wang, Hong-Sheng Zhou

Erschienen in: Advances in Cryptology – ASIACRYPT 2018

Verlag: Springer International Publishing

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

search-config
loading …

Abstract

In this work, we develop a framework for building leakage-resilient cryptosystems in the bounded leakage model from puncturable primitives and indistinguishability obfuscation (\(i\mathcal {O}\)). The major insight of our work is that various types of puncturable pseudorandom functions (PRFs) can achieve leakage resilience on an obfuscated street.
First, we build leakage-resilient weak PRFs from weak puncturable PRFs and \(i\mathcal {O}\), which readily imply leakage-resilient secret-key encryption. Then, we build leakage-resilient publicly evaluable PRFs (PEPRFs) from puncturable PEPRFs and \(i\mathcal {O}\), which readily imply leakage-resilient key encapsulation mechanism and thus public-key encryption. As a building block of independent interest, we realize puncturable PEPRFs from either newly introduced puncturable objects such as puncturable trapdoor functions and puncturable extractable hash proof systems or existing puncturable PRFs with \(i\mathcal {O}\). Finally, we construct the first leakage-resilient public-coin signature from selective puncturable PRFs, leakage-resilient one-way functions and \(i\mathcal {O}\). This settles the open problem posed by Boyle, Segev, and Wichs (Eurocrypt 2011).
By further assuming the existence of lossy functions, all the above constructions achieve optimal leakage rate of \(1 - o(1)\). Such a leakage rate is not known to be achievable for weak PRFs, PEPRFs and public-coin signatures before. This also resolves the open problem posed by Dachman-Soled, Gordon, Liu, O’Neill, and Zhou (PKC 2016, JOC 2018).

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!

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!

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!

Fußnoten
1
This is sometimes called second pre-image resistant functions.
 
2
Leftover hash lemma could be interpreted as a leakage-resilient fact, which stipulates \(\mathsf {ext}(x, s)\) is close to uniform even given a correlated value z, as long as s is a random seed chosen independently and x still has high min-entropy given leakage z.
 
3
Goldreich-Levin theorem can be interpreted as a leakage-resilient assumption, which states that if h is one-way then \(\mathsf {hc}(x)\) is pseudorandom even in the presence of h(x). Here \(\mathsf {hc}\) serves as a computational randomness extractor and h(x) could be viewed as leakage on x.
 
4
Following current conventions, we do not regard hash proof systems [CS02] as a general assumption.
 
5
A signature is secret-coin if its security breaks down when the randomness used in the signing procedure is revealed. On the contrary, a signature is public-coin if it stays secure even when the random coins used in the signing procedure are revealed (i.e., provided in-the-clear by the signature). In other words, public-coin signature is secure even when the entire random coins used for signing are leaked.
 
6
In selective security model, the adversary must declare the message \(m^*\) on which it will make a forgery before seeing the verification key, but then can adaptively make signing queries on messages distinct from \(m^*\).
 
7
In the case of our adaptively secure construction, a signature additionally contains a public coin of size \(\lambda ^c\) for any constant \(c < 1\).
 
8
Note that this dilemma does not occur in the case of encryption, since the argument in the final game is information-theoretic.
 
9
Without loss of generality, we assume that \(k(\{x^*\})\) includes the information of \(x^*\) in plain.
 
10
In a PEPRF, when the input x is not in \(L_{pk}\), its PRF value \(F_{sk}(x)\) may not be well defined and will be denoted by a distinguished symbol \(\bot \).
 
Literatur
[BGI+12]
Zurück zum Zitat Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S.P., Yang, K.: On the (im)possibility of obfuscating programs. J. ACM 59(2), 6 (2012)MathSciNetCrossRef Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S.P., Yang, K.: On the (im)possibility of obfuscating programs. J. ACM 59(2), 6 (2012)MathSciNetCrossRef
[BKKV10]
Zurück zum Zitat Brakerski, Z., Kalai, Y.T., Katz, J., Vaikuntanathan, V.: Overcoming the hole in the bucket: public-key cryptography resilient to continual memory leakage. In: FOCS, pp. 501–510 (2010) Brakerski, Z., Kalai, Y.T., Katz, J., Vaikuntanathan, V.: Overcoming the hole in the bucket: public-key cryptography resilient to continual memory leakage. In: FOCS, pp. 501–510 (2010)
[CDRW10]
Zurück zum Zitat Chow, S.S.M., Dodis, Y., Rouselakis, Y., Waters, B.: Practical leakage-resilient identity-based encryption from simple assumptions. In: ACM CCS, pp. 152–161 (2010) Chow, S.S.M., Dodis, Y., Rouselakis, Y., Waters, B.: Practical leakage-resilient identity-based encryption from simple assumptions. In: ACM CCS, pp. 152–161 (2010)
[DGL+16]
[DHLAW10]
Zurück zum Zitat Dodis, Y., Haralambiev, K., López-Alt, A., Wichs, D.: Cryptography against continuous memory attacks. In: FOCS, pp. 511–520 (2010) Dodis, Y., Haralambiev, K., López-Alt, A., Wichs, D.: Cryptography against continuous memory attacks. In: FOCS, pp. 511–520 (2010)
[DKL09]
Zurück zum Zitat Dodis, Y., Kalai, Y.T., Lovett, S.: On cryptography with auxiliary input. In: STOC, pp. 621–630 (2009) Dodis, Y., Kalai, Y.T., Lovett, S.: On cryptography with auxiliary input. In: STOC, pp. 621–630 (2009)
[GGH+13]
Zurück zum Zitat Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: FOCS, pp. 40–49 (2013) Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: FOCS, pp. 40–49 (2013)
[GGHW14]
[GGM86]
[GKPV10]
Zurück zum Zitat Goldwasser, S., Kalai, Y.T., Peikert, C., Vaikuntanathan, V.: Robustness of the learning with errors assumption. In: ICS, pp. 230–240 (2010) Goldwasser, S., Kalai, Y.T., Peikert, C., Vaikuntanathan, V.: Robustness of the learning with errors assumption. In: ICS, pp. 230–240 (2010)
[GM84]
[HSH+08]
Zurück zum Zitat Alex Halderman, J., et al.: Lest we remember: cold boot attacks on encryption keys. In: USENIX Security Symposium, pp. 45–60 (2008) Alex Halderman, J., et al.: Lest we remember: cold boot attacks on encryption keys. In: USENIX Security Symposium, pp. 45–60 (2008)
[KPTZ13]
Zurück zum Zitat Kiayias, A., Papadopoulos, S., Triandopoulos, N., Zacharias, T.: Delegatable pseudorandom functions and applications. In: ACM CCS, pp. 669–684 (2013) Kiayias, A., Papadopoulos, S., Triandopoulos, N., Zacharias, T.: Delegatable pseudorandom functions and applications. In: ACM CCS, pp. 669–684 (2013)
[LLW11]
Zurück zum Zitat Lewko, A.B., Lewko, M., Waters, B.: How to leak on key updates. In: STOC, pp. 725–734 (2011) Lewko, A.B., Lewko, M., Waters, B.: How to leak on key updates. In: STOC, pp. 725–734 (2011)
[PW08]
Zurück zum Zitat Peikert, C., Waters, B.: Lossy trapdoor functions and their applications. In: STOC, pp. 187–196 (2008) Peikert, C., Waters, B.: Lossy trapdoor functions and their applications. In: STOC, pp. 187–196 (2008)
[Reg05]
Zurück zum Zitat Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC, pp. 84–93 (2005) Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC, pp. 84–93 (2005)
[RW14]
Zurück zum Zitat Ramchen, K., Waters, B.: Fully secure and fast signing from obfuscation. In: ACM CCS, pp. 659–673 (2014) Ramchen, K., Waters, B.: Fully secure and fast signing from obfuscation. In: ACM CCS, pp. 659–673 (2014)
[SW14]
Zurück zum Zitat Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: STOC, pp. 475–484 (2014) Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: STOC, pp. 475–484 (2014)
[Wic13]
Zurück zum Zitat Wichs, D.: Barriers in cryptography with weak, correlated and leaky sources. In: Innovations in Theoretical Computer Science, ITCS, pp. 111–126 (2013) Wichs, D.: Barriers in cryptography with weak, correlated and leaky sources. In: Innovations in Theoretical Computer Science, ITCS, pp. 111–126 (2013)
Metadaten
Titel
Leakage-Resilient Cryptography from Puncturable Primitives and Obfuscation
verfasst von
Yu Chen
Yuyu Wang
Hong-Sheng Zhou
Copyright-Jahr
2018
DOI
https://doi.org/10.1007/978-3-030-03329-3_20

Premium Partner