Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
On the Security of the Algebraic Eraser Tag Authentication Protocol Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Deterministic Public-Key Encryption Under Continual Leakage

Authors : Venkata Koppula, Omkant Pandey, Yannis Rouselakis, Brent  Waters

Published in: Applied Cryptography and Network Security

Publisher: Springer International Publishing

Log in

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

search-config
loading …

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.

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 Offline Witness Encryption
next chapter Better Preprocessing for Secure Multiparty Computation
Footnotes
1
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.
 
2
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.
 
3
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.
 
4
We use the therms “matrix DDH assumption” and “linear assumption” interchangeably throughout the paper.
 
5
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.
 
6
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.
 
7
We abuse the notation and continue to denote this modified game by \(\mathbf {Game}^\rho _A\).
 
8
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\).
 
9
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.
 
10
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.
 
11
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.
 
12
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.
 
13
Such permutations are known.
 
Literature
1.
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
2.
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
3.
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
4.
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)
5.
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
6.
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
7.
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
8.
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)
9.
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.
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
Metadata
Title
Deterministic Public-Key Encryption Under Continual Leakage
Authors
Venkata Koppula
Omkant Pandey
Yannis Rouselakis
Brent  Waters
Copyright Year
2016
Book
Applied Cryptography and Network Security

Print ISBN: 978-3-319-39554-8

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

Copyright Year: 2016

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

Premium Partner

    Image Credits