nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

Deterministic Public-Key Encryption Under Continual Leakage

verfasst von : Venkata Koppula, Omkant Pandey, Yannis Rouselakis, Brent Waters

Erschienen in: Applied Cryptography and Network Security

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

Deterministic public-key encryption, introduced by Bellare, Boldyreva, and O’Neill (CRYPTO 2007), is an important technique for searchable encryption; it allows quick, logarithmic-time, search over encrypted data items. The technique is most effective in scenarios where frequent search queries are performed over a huge database of unpredictable data items. We initiate the study of deterministic public-key encryption (D-PKE) in the presence of leakage. We formulate appropriate security notions for leakage-resilient D-PKE, and present constructions that achieve them in the standard model. We work in the continual leakage model, where the secret-key is updated at regular intervals and an attacker can learn arbitrary but bounded leakage on the secret key during each time interval. We, however, do not consider leakage during the updates. Our main construction is based on the (standard) linear assumption in bilinear groups, tolerating up to \(0.5-o(1)\) fraction of arbitrary leakage. The leakage rate can be improved to \(1-o(1)\) by relying on the SXDH assumption.

At a technical level, we propose and construct a “continual leakage resilient” version of the all-but-one lossy trapdoor functions, introduced by Peikert and Waters (STOC 2008). Our formulation and construction of leakage-resilient lossy-TDFs is of independent general interest for leakage-resilient cryptography.

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 Offline Witness Encryption

Nächstes Kapitel Better Preprocessing for Secure Multiparty Computation

We note that in our model no leakage is allowed during update phase. However, the most general model allows leakage during the update phase as well.

Note that here it is important that distribution of m does not depend on \(h,\pi \). This is indeed the case since \((h,\pi )\) are part of the public-key and m is not allowed to depend on public-key in our setting.

For the PW construction, we will need to use n such ciphertexts, one for each diagonal entry; this can be handled using a hybrid argument.

We use the therms “matrix DDH assumption” and “linear assumption” interchangeably throughout the paper.

We can also consider more structured sets instead of \(\{0,1\}^{\mathrm {poly}(\lambda )}\). For example, a very intuitive and convenient choice is \(\mathcal {B}_\lambda =\mathbb {Z}_p^m\); i.e., the branches vectors in \(\mathbb {Z}_p^m\) for some \(m=\mathrm {poly}(n)\) and p is a prime of length \(\lambda \). However, too much structure in \(\mathcal {B}_\lambda \) should be avoided to ensure non-triviality and usefulness of the primitive.

We note that this formulation does ensure that \(\mathsf {Eval}(\mathsf {pp},b,\cdot )\) is indeed an injective function for all but a negligible fraction of \((\mathsf {pp},b)\) since inversion must almost always succeed for every given x.

We abuse the notation and continue to denote this modified game by \(\mathbf {Game}^\rho _A\).

We note that assuming such a \(\mathcal {G}\) is only for convenience and without loss of generality. Indeed, we can assume \(\mathcal {G}\) to be a part of the \(\mathsf {Setup}\) algorithm. Since the length of the generated prime p is independent of p and only depends on \(\lambda \), we can set \(\mathcal {B}_\lambda =\left( (\{0,1\}^{\lfloor \lg p\rfloor })^{\ell }\right) ^{n}\) which is independent of p and always a subset of \((\mathbb {Z}_p^\ell )^n\).

We remind the reader that uppercase letters, such as A, R, S, denote matrices of scalars (e.g., elements of \(\mathbb {Z}_p\)), whereas bold uppercase letters, such as \(\mathbf {A}\), denote matrices of vectors (e.g. elements of \(\mathbb {Z}_p^\ell \) or \(\mathbb {G}^\ell \)). Bold lowercase letter such as \(\mathbf {x}\) represent vectors with only scalar entries.

Recall that i-th row of \(\mathbf {A}'\mathbf {x}\) contains a vector in the span of the vectors in the i-th row of \(\mathbf {A}'\). See Sect. 2.

We will only focus on the single challenge setting; it is straightforward to extend our definition to deal with sequence of messages and get the corresponding notion CLR-PRIV-IND. However, our construction only satisfies the single message definition, and we do not know if our scheme can be shown to satisfy security for multiple messages.

W.l.o.g. we can assume s to be quite small if necessary. If the length requires a large string to describe the branch, we can use pseudorandom generators of sufficient stretch.

Such permutations are known.

Akavia, A., Goldwasser, S., Vaikuntanathan, V.: Simultaneous hardcore bits and cryptography against memory attacks. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 474–495. Springer, Heidelberg (2009)CrossRef

Alwen, J., Dodis, Y., Naor, M., Segev, G., Walfish, S., Wichs, D.: Public-key encryption in the bounded-retrieval model. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 113–134. Springer, Heidelberg (2010)CrossRef

Ananth, P., Goyal, V., Pandey, O.: Interactive proofs under continual memory leakage. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part II. LNCS, vol. 8617, pp. 164–182. Springer, Heidelberg (2014)CrossRef

Anderson, R.J., Kuhn, M.G.: Low cost attacks on tamper resistant devices. In: Christianson, B., Crispo, B., Lomas, M., Roe, M. (eds.) Security Protocols. LNCS, pp. 125–136. Springer, Heidelberg (1997)

Bellare, M., Boldyreva, A., O’Neill, A.: Deterministic and efficiently searchable encryption. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 535–552. Springer, Heidelberg (2007)CrossRef

Bellare, M., Fischlin, M., O’Neill, A., Ristenpart, T.: Deterministic encryption: definitional equivalences and constructions without random oracles. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 360–378. Springer, Heidelberg (2008)CrossRef

Bellare, M., Kiltz, E., Peikert, C., Waters, B.: Identity-based (lossy) trapdoor functions and applications. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 228–245. Springer, Heidelberg (2012)CrossRef

Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Proceedings of the 1st Annual ACM Conference on Computer and Communications Security. pp. 62–73 (1993)

Boldyreva, A., Fehr, S., O’Neill, A.: On notions of security for deterministic encryption, and efficient constructions without random oracles. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 335–359. Springer, Heidelberg (2008)CrossRef

10.

Boneh, D., Boyen, X., Shacham, H.: Short group signatures. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 41–55. Springer, Heidelberg (2004)CrossRef

11.

Boyle, E., Goldwasser, S., Jain, A., Kalai, Y.T.: Multiparty computation secure against continual memory leakage. In: STOC. pp. 1235–1254 (2012)

12.

Boyle, E., Segev, G., Wichs, D.: Fully leakage-resilient signatures. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 89–108. Springer, Heidelberg (2011)CrossRef

13.

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)

14.

Brakerski, Z., Segev, G.: Better security for deterministic public-key encryption: the auxiliary-input setting. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 543–560. Springer, Heidelberg (2011)CrossRef

15.

Chow, S.S.M., Dodis, Y., Rouselakis, Y., Waters, B.: Practical leakage-resilient identity-based encryption from simple assumptions. In: ACM Conference on Computer and Communications Security. pp. 152–161 (2010)

16.

Dodis, Y., Haralambiev, K., López-Alt, A., Wichs, D.: Cryptography against continuous memory attacks. In: FOCS. pp. 511–520 (2010)

17.

Dodis, Y., Kalai, Y.T., Lovett, S.: On cryptography with auxiliary input. In: STOC. pp. 621–630 (2009)

18.

Dodis, Y., Smith, A.: Correcting errors without leaking partial information. In: STOC 2005. pp. 654–663 (2005)

19.

Dziembowski, S., Pietrzak, K.: Leakage-resilient cryptography. In: FOCS. pp. 293–302 (2008)

20.

Faust, S., Rabin, T., Reyzin, L., Tromer, E., Vaikuntanathan, V.: Protecting circuits from leakage: the computationally-bounded and noisy cases. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 135–156. Springer, Heidelberg (2010)CrossRef

21.

Freeman, D.M., Goldreich, O., Kiltz, E., Rosen, A., Segev, G.: More constructions of lossy and correlation-secure trapdoor functions. In: Proceedings of the 13th International Conference on Practice and Theory in Public Key Cryptography. pp. 279–295 (2010)

22.

Fuller, B., O’Neill, A., Reyzin, L.: A unified approach to deterministic encryption: new constructions and a connection to computational entropy. In: Cramer, R. (ed.) Theory of Cryptography. Lecture Notes in Computer Science, vol. 7194, pp. 582–599. Springer, Heidelberg (2012). Cryptology ePrint Archive, Report 2012/005CrossRef

23.

Garg, S., Jain, A., Sahai, A.: Leakage-resilient zero knowledge. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 297–315. Springer, Heidelberg (2011)CrossRef

24.

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

25.

Goldwasser, S., Rothblum, G.N.: How to compute in the presence of leakage. In: FOCS. pp. 31–40 (2012)

26.

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)CrossRef

27.

Hemenway, B., Libert, B., Ostrovsky, R., Vergnaud, D.: Lossy encryption: constructions from general assumptions and efficient selective opening chosen ciphertext security. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 70–88. Springer, Heidelberg (2011)CrossRef

28.

Hofheinz, D.: All-but-many lossy trapdoor functions. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 209–227. Springer, Heidelberg (2012)CrossRef

29.

Ishai, Y., Sahai, A., Wagner, D.: Private circuits: securing hardware against probing attacks. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 463–481. Springer, Heidelberg (2003)CrossRef

30.

Kocher, P.C.: Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 104–113. Springer, Heidelberg (1996)

31.

Lewko, A.B., Lewko, M., Waters, B.: How to leak on key updates. In: STOC (2011)

32.

Lewko, A., Rouselakis, Y., Waters, B.: Achieving leakage resilience through dual system encryption. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 70–88. Springer, Heidelberg (2011)CrossRef

33.

Lewko, A.B., Waters, B.: On the insecurity of parallel repetition for leakage resilience. In: FOCS. pp. 521–530 (2010)

34.

Micali, S., Reyzin, L.: Physically observable cryptography. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 278–296. Springer, Heidelberg (2004)CrossRef

35.

Mironov, I., Pandey, O., Reingold, O., Segev, G.: Incremental deterministic public-key encryption. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 628–644. Springer, Heidelberg (2012)CrossRef

36.

Naor, M., Segev, G.: Public-key cryptosystems resilient to key leakage. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 18–35. Springer, Heidelberg (2009)CrossRef

37.

O’Neill, A.: Deterministic public-key encryption revisited. Eprint Report 2010/533 (2010)

38.

Osvik, D.A., Shamir, A., Tromer, E.: Cache attacks and countermeasures: the case of AES. In: Pointcheval, D. (ed.) CT-RSA 2006. LNCS, vol. 3860, pp. 1–20. Springer, Heidelberg (2006)CrossRef

39.

Pandey, O.: Achieving constant round leakage-resilient zero-knowledge. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 146–166. Springer, Heidelberg (2014)CrossRef

40.

Peikert, C., Waters, B.: Lossy trapdoor functions and their applications. In: STOC. pp. 187–196 (2008)

41.

Popa, R.A., Redfield, C.M.S., Zeldovich, N., Balakrishnan, H.: Cryptdb: protecting confidentiality with encrypted query processing. In: SOSP. pp. 85–100 (2011)

42.

Popa, R.A., Redfield, C.M.S., Zeldovich, N., Balakrishnan, H.: Cryptdb: processing queries on an encrypted database. Commun. ACM 55(9), 103–111 (2012)CrossRef

43.

Qin, B., Liu, S., Chen, K., Charlemagne, M.: Leakage-resilient lossy trapdoor functions and public-key encryption. In: AsiaPKC (2013)

44.

Quisquater, Jean-Jacques, Samyde, David: Electromagnetic analysis (EMA): measures and counter-measures for smart cards. In: Attali, S., Jensen, T. (eds.) E-smart 2001. LNCS, vol. 2140, pp. 200–210. Springer, Heidelberg (2001)CrossRef

45.

Raghunathan, A., Segev, G., Vadhan, S.: Deterministic public-key encryption for adaptively chosen plaintext distributions. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 93–110. Springer, Heidelberg (2013)CrossRef

46.

Renauld, M., Standaert, F.-X., Veyrat-Charvillon, N., Kamel, D., Flandre, D.: A formal study of power variability issues and side-channel attacks for nanoscale devices. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 109–128. Springer, Heidelberg (2011)CrossRef

47.

Wee, H.: Dual projective hashing and its applications — lossy trapdoor functions and more. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 246–262. Springer, Heidelberg (2012)CrossRef

Titel: Deterministic Public-Key Encryption Under Continual Leakage
verfasst von: Venkata Koppula
Omkant Pandey
Yannis Rouselakis
Brent Waters
Verlag: Springer International Publishing
Buch: Applied Cryptography and Network Security
Print ISBN: 978-3-319-39554-8

Electronic ISBN: 978-3-319-39555-5

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-319-39555-5_17

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"