Skip to main content
Erschienen in: Journal of Cryptology 3/2019

25.04.2018

Leakage Resilience from Program Obfuscation

verfasst von: Dana Dachman-Soled, S. Dov Gordon, Feng-Hao Liu, Adam O’Neill, Hong-Sheng Zhou

Erschienen in: Journal of Cryptology | Ausgabe 3/2019

Einloggen

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

search-config
loading …

Abstract

The literature on leakage-resilient cryptography contains various leakage models that provide different levels of security. In the bounded leakage model (Akavia et al.—TCC 2009), it is assumed that there is a fixed upper bound L on the number of bits the attacker may leak on the secret key in the entire lifetime of the scheme. Alternatively, in the continual leakage model (Brakerski et al.—FOCS 2010, Dodis et al.—FOCS 2010), the lifetime of a cryptographic scheme is divided into “time periods” between which the scheme’s secret key is updated. Furthermore, in its attack the adversary is allowed to obtain some bounded amount of leakage on the current secret key during each time period. In the continual leakage model, a challenging problem has been to provide security against leakage on key updates, that is, leakage that is a function of not only the current secret key but also the randomness used to update it. We propose a modular approach to overcome this problem based on program obfuscation. Namely, we present a compiler that transforms any public key encryption or signature scheme that achieves a slight strengthening of continual leakage resilience, which we call consecutive continual leakage resilience, to one that is continual leakage resilient with leakage on key updates, assuming indistinguishability obfuscation (Barak et al.—CRYPTO 2001, Garg et al.—FOCS 2013). Under stronger forms of obfuscation, the leakage rate tolerated by our compiled scheme is essentially as good as that of the starting scheme. Our compiler is derived by making a connection between the problems of leakage on key updates and so-called sender-deniable encryption (Canetti et al.—CRYPTO 1997), which was recently constructed based on indistinguishability obfuscation by Sahai and Waters (STOC 2014). In the bounded leakage model, we give an approach to constructing leakage-resilient public key encryption from program obfuscation based on the public key encryption scheme of Sahai and Waters (STOC 2014). In particular, we achieve leakage-resilient public key encryption tolerating L bits of leakage for any L from \({\mathsf {iO}} \) and one-way functions. We build on this to achieve leakage-resilient public key encryption with optimal leakage rate of \(1-o(1)\) based on stronger forms of obfuscation and collision-resistant hash functions. Such a leakage rate is not known to be achievable in a generic way based on public key encryption alone. We then develop additional techniques to construct public key encryption that is (consecutive) continual leakage resilient under appropriate assumptions, which we believe is of independent interest.

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

In the construction of Hazay et al. [35], the secret key of the constructed scheme consists of n secret keys of the underlying public key encryption scheme, where each underlying secret key is randomly selected from a set of size m and m is polynomial in security parameter. The total amount of leakage that can be tolerated is approximately \(n \log (m)\) bits. Thus, the leakage rate is \(\frac{n \log (m)}{n \cdot s} \in \varTheta (\frac{\log (m)}{s})\), where s denotes the length of the secret key of the underlying scheme.

 
2

Here “continual” refers to the fact that the total amount of leakage obtained by the adversary is unbounded. Additionally, the model is more accurately called the continual memory leakage model to contrast with schemes constructed under an assumption that “only computation leaks” [45].

 
3

To the best of our knowledge, no impossibility results are known for public-coin differing-inputs obfuscation. Indeed, the impossibility results of Garg et al. [30] do not apply to this setting. In either case, current constructions rely on multilinear maps, whose first candidate construction was given by [28].

 
4

We note that the techniques of [47] have been shown useful in adaptively secure two-party and multiparty computation [14, 18, 31] and “only computation leaks” (OCL) circuits without trusted hardware [19]. We note that this work precedes the work of [18].

 
5

Unlike the case of CLR without leakage on key updates, observe that any scheme that is CLR with leakage on key updates can leak at most \(1/2 \cdot |\mathsf{sk}|\)-bits per time period, since otherwise the adversary can recover an entire secret key. As a consequence, the optimal leakage rate for a scheme that is CLR with leakage on key updates is at most \(\frac{1/2 \cdot |\mathsf{sk}|}{|\mathsf{sk}| + |r_{up}|} < 1/2\), where \(|\mathsf{sk}|\) is the secret key length and \(|r_{up}|\) is the length of the randomness needed by the update algorithm.

 
6

Note that [12] also constructs such a signature scheme, but, as discussed below, such a signature scheme can in fact be generically obtained, and therefore, for simplicity we do not consider their direct construction here.

 
7

In the 2CLR model, the maximum amount of leakage is roughly \(1/2 \cdot |\mathsf{sk}| \), so the optimal rate is roughly \(\frac{1/2 \cdot |\mathsf{sk}|}{|\mathsf{sk}| + |\mathsf{sk}|} = 1/4\).

 
8

Technically, we actually use pseudorandom value r, just as SW do. We omit this here to make the explanation a little more clear.

 
9

The description of the hash function is the seed. On input seed and source, the extractor outputs a distribution that is \({\epsilon }\) close to the uniform distribution if the source has min-entropy \(2\kappa \). Here we set \({\epsilon }\) to be some negligible. The hash function is chosen from a family of functions, and once chosen, it is a deterministic function.

 
10

Note: \(\mathsf {Rk}\) denotes rank. Here we use n as the dimension (different from [12] who used m) to avoid overloading notation.

 
11

We note that the statement of Occam’s Razor theorem in [40] is for the case of Boolean functions. However, the analysis can be easily extended to the non-Boolean case.

 
12

We note that the presented conditions only refer to single-message security, which is all that is needed in our applications. More generally they could provide the adversary many challenge encryptions (say, via appropriate encryption oracles).

 
Literatur
  1. M. Abe, M. Chase, B. David, M. Kohlweiss, R. Nishimaki, and M. Ohkubo. Constant-size structure-preserving signatures: Generic constructions and simple assumptions. In X. Wang and K. Sako, editors, ASIACRYPT 2012, vol. 7658 of LNCS (Springer, Berlin, 2012), pp. 4–24.
  2. A. Akavia, S. Goldwasser, and V. Vaikuntanathan. Simultaneous hardcore bits and cryptography against memory attacks. In O. Reingold, editor, TCC 2009, vol. 5444 of LNCS. (Springer, Berlin, 2009), , pp. 474–495.
  3. P. Ananth, D. Boneh, S. Garg, A. Sahai, M. Zhandry. Differing-inputs obfuscation and applications. Cryptology ePrint Archive, Report 2013/689, 2013. http://​eprint.​iacr.​org/​2013/​689.
  4. B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. P. Vadhan, and K. Yang. On the (im)possibility of obfuscating programs. In J. Kilian, editor, CRYPTO 2001, vol. 2139 of LNCS. (Springer, Berlin, 2001), pp. 1–18.
  5. B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. P. Vadhan, and K. Yang. On the (im)possibility of obfuscating programs. J. ACM, 59(2):6, 2012.MathSciNetView ArticleMATH
  6. A. Boldyreva, S. Fehr, and A. O’Neill. On notions of security for deterministic encryption, and efficient constructions without random oracles. In D. Wagner, editor, CRYPTO 2008, vol. 5157 of LNCS. (Springer, Berlin, 2008), pp. 335–359.
  7. D. Boneh, X. Boyen, and H. Shacham. Short group signatures. In M. Franklin, editor, CRYPTO 2004, volume 3152 of LNCS (Springer, Berlin, 2004), pp. 41–55.
  8. D. Boneh and B. Waters. Constrained pseudorandom functions and their applications. In K. Sako and P. Sarkar, editors, ASIACRYPT 2013, Part II, vol. 8270 of LNCS (Springer, Berlin, 2013), pp. 280–300.
  9. E. Boyle, K.-M. Chung, R. Pass. On extractability obfuscation. In Y. Lindell, editor, TCC 2014, vol. 8349 of LNCS (Springer, Berlin, 2014), pp. 52–73.
  10. E. Boyle, S. Goldwasser, and I. Ivan. Functional signatures and pseudorandom functions. In H. Krawczyk, editor, PKC 2014, vol. 8383 of LNCS (Springer, Berlin, 2014), pp. 501–519.
  11. E. Boyle, G. Segev, and D. Wichs. Fully leakage-resilient signatures. In K. G. Paterson, editor, EUROCRYPT 2011, vol. 6632 of LNCS (Springer, Berlin, 2011), pp. 89–108.
  12. Z. Brakerski, Y. T. Kalai, J. Katz, and V. Vaikuntanathan. Overcoming the hole in the bucket: Public-key cryptography resilient to continual memory leakage. In 51st FOCS, pp. 501–510. IEEE Computer Society Press, (2010).
  13. R. Canetti, C. Dwork, M. Naor, and R. Ostrovsky. Deniable encryption. In B. S. Kaliski Jr., editor, CRYPTO’97, volume 1294 of LNCS. (Springer, Berlin, 1997), pp. 90–104.
  14. R. Canetti, S. Goldwasser, and O. Poburinnaya. Adaptively secure two-party computation from indistinguishability obfuscation. In Y. Dodis and J. B. Nielsen, editors, TCC 2015, Part II, vol. 9015 of LNCS (Springer, Berlin, 2015), pp. 557–585.
  15. R. Canetti, H. Krawczyk, and J. B. Nielsen. Relaxing chosen-ciphertext security. In D. Boneh, editor, CRYPTO 2003, vol. 2729 of LNCS (Springer, Berlin, 2003), pp. 565–582.
  16. S. Chari, C. S. Jutla, J. R. Rao, and P. Rohatgi. Towards sound approaches to counteract power-analysis attacks. In M. J. Wiener, editor, CRYPTO’99, vol. 1666 of LNCS. (Springer, Berlin, 1999)
  17. M. Chase, M. Kohlweiss, A. Lysyanskaya, and S. Meiklejohn. Malleable proof systems and applications. In D. Pointcheval and T. Johansson, editors, EUROCRYPT 2012, vol. 7237 of LNCS (Springer, Berlin, 2012), pp. 281–300
  18. D. Dachman-Soled, J. Katz, and V. Rao. Adaptively secure, universally composable, multiparty computation in constant rounds. In Y. Dodis and J. B. Nielsen, editors, TCC 2015, Part II, vol. 9015 of LNCS (Springer, Berlin, 2015), pp. 586–613
  19. D. Dachman-Soled, F.-H. Liu, and H.-S. Zhou. Leakage-resilient circuits revisited - optimal number of computing components without leak-free hardware. In E. Oswald and M. Fischlin, editors, EUROCRYPT 2015, Part II, vol. 9057 of LNCS, (Springer, Berlin, 2015), pp. 131–158.
  20. A. De Santis, G. Di Crescenzo, R. Ostrovsky, G. Persiano, and A. Sahai. Robust non-interactive zero knowledge. In J. Kilian, editor, CRYPTO 2001, vol. 2139 of LNCS (Springer, Berlin, 2001), pp. 566–598
  21. Y. Dodis, K. Haralambiev, A. López-Alt, and D. Wichs. Cryptography against continuous memory attacks. In 51st FOCS, IEEE Computer Society Press, 2010, pp. 511–520.
  22. Y. Dodis, K. Haralambiev, A. López-Alt, and D. Wichs. Efficient public-key cryptography in the presence of key leakage. In M. Abe, editor, ASIACRYPT 2010, vol. 6477 of LNCS (Springer, Berlin, 2010), pp. 613–631.
  23. Y. Dodis, Y. T. Kalai, and S. Lovett. On cryptography with auxiliary input. In M. Mitzenmacher, editor, 41st ACM STOC (ACM Press, 2009), pp. 621–630.
  24. Y. Dodis, A. B. Lewko, B. Waters, and D. Wichs. Storing secrets on continually leaky devices. In R. Ostrovsky, editor, 52nd FOCS, pp. 688–697. IEEE Computer Society Press, 2011.
  25. Y. Dodis, R. Ostrovsky, L. Reyzin, and A. Smith. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. SIAM J. Comput., 38(1):97–139, 2008.MathSciNetView ArticleMATH
  26. Y. Dodis and A. Smith. Correcting errors without leaking partial information. In H. N. Gabow and R. Fagin, editors, 37th ACM STOC (ACM Press, 2005), pp. 654–663.
  27. S. Faust, T. Rabin, L. Reyzin, E. Tromer, and V. Vaikuntanathan. Protecting circuits from leakage: the computationally-bounded and noisy cases. In H. Gilbert, editor, EUROCRYPT 2010, vol. 6110 of LNCS (Springer, Berlin, 2010), pp. 135–156.
  28. S. Garg, C. Gentry, and S. Halevi. Candidate multilinear maps from ideal lattices. In T. Johansson and P. Q. Nguyen, editors, EUROCRYPT 2013, vol. 7881 of LNCS (Springer, Berlin, 2013), pp. 1–17.
  29. S. Garg, C. Gentry, S. Halevi, M. Raykova, A. Sahai, and B. Waters. Candidate indistinguishability obfuscation and functional encryption for all circuits. in 54th FOCS, pp. 40–49. IEEE Computer Society Press, 2013.
  30. S. Garg, C. Gentry, S. Halevi, and D. Wichs. On the implausibility of differing-inputs obfuscation and extractable witness encryption with auxiliary input. In J. A. Garay and R. Gennaro, editors, CRYPTO 2014, Part I, volume 8616 of LNCS, (Springer, Berlin, 2014), pp. 518–535.
  31. S. Garg and A. Polychroniadou. Two-round adaptively secure MPC from indistinguishability obfuscation. In Y. Dodis and J. B. Nielsen, editors, TCC 2015, Part II, vol. 9015 of LNCS (Springer, Berlin, 2015), pp. 614–637.
  32. O. Goldreich, S. Goldwasser, and S. Micali. How to construct random functions. J. ACM, 33(4):792–807, Aug. 1986.MathSciNetView ArticleMATH
  33. S. Goldwasser and G. N. Rothblum. On best-possible obfuscation. In S. P. Vadhan, editor, TCC 2007, volume 4392 of LNCS (Springer, Berlin 2007), pp. 194–213
  34. J. A. Halderman, S. D. Schoen, N. Heninger, W. Clarkson, W. Paul, J. A. Calandrino, A. J. Feldman, J. Appelbaum, and E. W. Felten. Lest we remember: Cold boot attacks on encryption keys, in USENIX Security Symposium, pp. 45–60 (2008)
  35. C. Hazay, A. López-Alt, H. Wee, and D. Wichs. Leakage-resilient cryptography from minimal assumptions. In T. Johansson and P. Q. Nguyen, editors, EUROCRYPT 2013, volume 7881 of LNCS, (Springer, Berlin, 2013), pp. 160–176.
  36. R. Impagliazzo, L. A. Levin, and M. Luby. Pseudo-random generation from one-way functions (extended abstracts). In 21st ACM STOC (ACM Press, 1989), pp. 12–24.
  37. Y. Ishai, O. Pandey, and A. Sahai. Public-coin differing-inputs obfuscation and its applications. In Y. Dodis and J. B. Nielsen, editors, TCC 2015, Part II, vol. 9015 of LNCS, (Springer, Berlin, 2015), pp. 668–697.
  38. J. Katz and Y. Lindell. Introduction to Modern Cryptography, Second Edition. CRC Press, 2014.MATH
  39. J. Katz and V. Vaikuntanathan. Signature schemes with bounded leakage resilience. In M. Matsui, editor, ASIACRYPT 2009, vol. 5912 of LNCS, (Springer, Berlin, 2009), pp. 703–720
  40. M. J. Kearns and U. V. Vazirani. An introduction to computational learning theory. Massachusetts Institute of Technology (1994)
  41. A. Kiayias, S. Papadopoulos, N. Triandopoulos, and T. Zacharias. Delegatable pseudorandom functions and applications. In A.-R. Sadeghi, V. D. Gligor, and M. Yung, editors, ACM CCS 13, (ACM Press, 2013), pp. 669–684.
  42. C.-J. Lee, C.-J. Lu, S.-C. Tsai, and W.-G. Tzeng. Extracting randomness from multiple independent sources. IEEE Transactions on Information Theory, 51(6):2224–2227, 2005.MathSciNetView ArticleMATH
  43. A. B. Lewko, M. Lewko, and B. Waters. How to leak on key updates. In L. Fortnow and S. P. Vadhan, editors, 43rd ACM STOC (ACM Press, 2011), pp. 725–734
  44. T. Malkin, I. Teranishi, Y. Vahlis, and M. Yung. Signatures resilient to continual leakage on memory and computation. In Y. Ishai, editor, TCC 2011, vol. 6597 of LNCS, (Springer, Berlin, 2011), pp. 89–106
  45. S. Micali and L. Reyzin. Physically observable cryptography (extended abstract). In M. Naor, editor, TCC 2004, vol. 2951 of LNCS (Springer, Berlin, 2004), pp. 278–296
  46. M. Naor and G. Segev. Public-key cryptosystems resilient to key leakage. In S. Halevi, editor, CRYPTO 2009, vol. 5677 of LNCS, (Springer, Berlin, 2009), pp. 18–35
  47. A. Sahai and B. Waters. How to use indistinguishability obfuscation: deniable encryption, and more. In D. B. Shmoys, editor, 46th ACM STOC (ACM Press, 2014), pp. 475–484
  48. B. Waters. Dual system encryption: Realizing fully secure IBE and HIBE under simple assumptions. In S. Halevi, editor, CRYPTO 2009, volume 5677 of LNCS, (Springer, Berlin, 2009), pp. 619–636
  49. B. Waters. CS 395T Special Topic: Obfuscation in Cryptography. 2014. http://​www.​cs.​utexas.​edu/​~bwaters/​classes/​CS395T-Fall-14/​outline.​html
  50. B. Waters. How to use in distinguishability obfuscation, in Visions of Cryptography, 2014. Talk slides available at http://​www.​cs.​utexas.​edu/​~bwaters/​presentations/​files/​how-to-use-IO.​ppt.
  51. D. Wichs. Cryptographic resilience to continual information leakage. Ph.D. Thesis, 2011. http://​www.​ccs.​neu.​edu/​home/​wichs/​thesis.​pdf
Metadaten
Titel
Leakage Resilience from Program Obfuscation
verfasst von
Dana Dachman-Soled
S. Dov Gordon
Feng-Hao Liu
Adam O’Neill
Hong-Sheng Zhou
Publikationsdatum
25.04.2018
Verlag
Springer US
Erschienen in
Journal of Cryptology / Ausgabe 3/2019
Print ISSN: 0933-2790
Elektronische ISSN: 1432-1378
DOI
https://doi.org/10.1007/s00145-018-9286-z

Weitere Artikel der Ausgabe 3/2019

Journal of Cryptology 3/2019 Zur Ausgabe