Article

Handling Adaptive Compromise for Practical Encryption Schemes

Authors:

Nirvan TyagiAuthors Info & Claims

Advances in Cryptology – CRYPTO 2020: 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17–21, 2020, Proceedings, Part I

Pages 3 - 32

https://doi.org/10.1007/978-3-030-56784-2_1

Published: 17 August 2020 Publication History

Abstract

We provide a new definitional framework capturing the multi-user security of encryption schemes and pseudorandom functions in the face of adversaries that can adaptively compromise users’ keys. We provide a sequence of results establishing the security of practical symmetric encryption schemes under adaptive compromise in the random oracle or ideal cipher model. The bulk of analysis complexity for adaptive compromise security is relegated to the analysis of lower-level primitives such as pseudorandom functions.

We apply our framework to give proofs of security for the BurnBox system for privacy in the face of border searches and the in-use searchable symmetric encryption scheme due to Cash et al. In both cases, prior analyses had bugs that our framework helps avoid.

References

[1]

Asharov, G., Naor, M., Segev, G., Shahaf, I.: Searchable symmetric encryption: optimal locality in linear space via two-dimensional balanced allocations. In: Wichs, D., Mansour, Y. (eds.) 48th ACM STOC, Cambridge, MA, USA, 18–21 June 2016, pp. 1101–1114. ACM Press (2016)

[2]

Asharov G, Segev G, and Shahaf I Shacham H and Boldyreva A Tight tradeoffs in searchable symmetric encryption Advances in Cryptology – CRYPTO 2018 2018 Cham Springer 407-436

[3]

Barbosa M and Farshim P Shacham H and Boldyreva A Indifferentiable authenticated encryption Advances in Cryptology – CRYPTO 2018 2018 Cham Springer 187-220

[4]

Bellare M, Boldyreva A, and Micali S Preneel B Public-key encryption in a multi-user setting: security proofs and improvements Advances in Cryptology — EUROCRYPT 2000 2000 Heidelberg Springer 259-274

[5]

Bellare M, Canetti R, and Krawczyk H Koblitz N Keying hash functions for message authentication Advances in Cryptology — CRYPTO ’96 1996 Heidelberg Springer 1-15

[6]

Bellare, M., Desai, A., Jokipii, E., Rogaway, P.: A concrete security treatment of symmetric encryption. In: 38th FOCS, Miami Beach, Florida, 19–22 October 1997, pp. 394–403. IEEE Computer Society Press (1997)

[7]

Bellare M, Hofheinz D, and Yilek S Joux A Possibility and impossibility results for encryption and commitment secure under selective opening Advances in Cryptology - EUROCRYPT 2009 2009 Heidelberg Springer 1-35

[8]

Bellare M and Namprempre C Okamoto T Authenticated encryption: relations among notions and analysis of the generic composition paradigm Advances in Cryptology — ASIACRYPT 2000 2000 Heidelberg Springer 531-545

[9]

Bost, R.: : forward secure searchable encryption. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM CCS 2016, Vienna, Austria, 24–28 October 2016. ACM Press (2016)

[10]

Canetti, R., Feige, U., Goldreich, O., Naor, M.: Adaptively secure multi-party computation. In: 28th ACM STOC, Philadephia, PA, USA, 22–24 May 1996, pp. 639–648. ACM Press (1996)

[11]

Cash, D., Grubbs, P., Perry, J., Ristenpart, T.: Leakage-abuse attacks against searchable encryption. In: Ray, I., Li, N., Kruegel, C. (eds.) ACM CCS 2015, Denver, CO, USA, 12–16 October 2015, pp. 668–679. ACM Press (2015)

[12]

Cash, D., et al.: Dynamic searchable encryption in very-large databases: data structures and implementation. In: NDSS 2014, San Diego, CA, USA, 23–26 February 2014. The Internet Society (2014)

[13]

Cash D and Tessaro S Nguyen PQ and Oswald E The locality of searchable symmetric encryption Advances in Cryptology – EUROCRYPT 2014 2014 Heidelberg Springer 351-368

[14]

Coron J-S, Dodis Y, Malinaud C, and Puniya P Shoup V Merkle-Damgård revisited: how to construct a hash function Advances in Cryptology – CRYPTO 2005 2005 Heidelberg Springer 430-448

[15]

Curtmola, R., Garay, J.A., Kamara, S., Ostrovsky, R.: Searchable symmetric encryption: improved definitions and efficient constructions. In: Juels, A., Wright, R.N., De Capitani di Vimercati, S. (eds.) ACM CCS 2006, Alexandria, Virginia, USA, 30 October–3 November 2006, pp. 79–88. ACM Press (2006)

[16]

Dodis Y, Ristenpart T, Steinberger J, and Tessaro S Safavi-Naini R and Canetti R To hash or not to hash again? (In)differentiability results for H² and HMAC Advances in Cryptology – CRYPTO 2012 2012 Heidelberg Springer 348-366

[17]

Etemad M, Küpçü A, Papamanthou C, and Evans D Efficient dynamic searchable encryption with forward privacy PoPETs 2018 2018 1 5-20

[18]

Fischlin M, Lehmann A, Ristenpart T, Shrimpton T, Stam M, and Tessaro S Abe M Random Oracles with(out) programmability Advances in Cryptology - ASIACRYPT 2010 2010 Heidelberg Springer 303-320

[19]

Goldwasser S and Micali S Probabilistic encryption J. Comput. Syst. Sci. 1984 28 2 270-299

[20]

Hahn, F., Kerschbaum, F.: Searchable encryption with secure and efficient updates. In: Ahn, G.-J., Yung, M., Li, N. (eds.) ACM CCS 2014, Scottsdale, AZ, USA, 3–7 November 2014, pp. 310–320. ACM Press (2014)

[21]

Hu, S., Cai, C., Wang, Q., Wang, C., Luo, X., Ren, K.: Searching an encrypted cloud meets blockchain: a decentralized, reliable and fair realization. In: IEEE INFOCOM 2018 - IEEE Conference on Computer Communications, pp. 792–800, April 2018

[22]

Islam, M.S., Kuzu, M., Kantarcioglu, M.: Access pattern disclosure on searchable encryption: ramification, attack and mitigation. In: NDSS 2012, San Diego, CA, USA, 5–8 February 2012. The Internet Society (2012)

[23]

Jaeger, J., Tyagi, N.: Handling adaptive compromise for practical encryption schemes. Cryptology ePrint Archive, Report 2020/765 (2020). http://eprint.iacr.org/2020/765

[24]

Jarecki S, Krawczyk H, and Xu J Nielsen JB and Rijmen V OPAQUE: an asymmetric PAKE protocol secure against pre-computation attacks Advances in Cryptology – EUROCRYPT 2018 2018 Cham Springer 456-486

[25]

Kamara S and Papamanthou C Sadeghi A-R Parallel and dynamic searchable symmetric encryption Financial Cryptography and Data Security 2013 Heidelberg Springer 258-274

[26]

Kamara, S., Papamanthou, C., Roeder, T.: Dynamic searchable symmetric encryption. In: Yu, T., Danezis, G., Gligor, V.D. (eds.) ACM CCS 2012, Raleigh, NC, USA, 16–18 October 2012, pp. 965–976. ACM Press (2012)

[27]

Kim, K.S., Kim, M., Lee, D., Park, J.H., Kim, W.-H.: Forward secure dynamic searchable symmetric encryption with efficient updates. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 2017, Dallas, TX, USA, 31 October–2 November 2017, pp. 1449–1463. ACM Press (2017)

[28]

Li, J., et al.: Searchable symmetric encryption with forward search privacy. IEEE Trans. Dependable Secure Comput., 1 (2019, early access). https://ieeexplore.ieee.org/document/8621026

[29]

Liu, Q., Tian, Y., Wu, J., Peng, T., Wang, G.: Enabling verifiable and dynamic ranked search over outsourced data. IEEE Trans. Services Comput., 1 (2019, early access). https://ieeexplore.ieee.org/document/8734776

[30]

Maurer U, Renner R, and Holenstein C Naor M Indifferentiability, impossibility results on reductions, and applications to the random Oracle methodology Theory of Cryptography 2004 Heidelberg Springer 21-39

[31]

Nielsen JB Yung M Separating random Oracle proofs from complexity theoretic proofs: the non-committing encryption case Advances in Cryptology — CRYPTO 2002 2002 Heidelberg Springer 111-126

[32]

Rogaway P and Shrimpton T Vaudenay S A provable-security treatment of the key-wrap problem Advances in Cryptology - EUROCRYPT 2006 2006 Heidelberg Springer 373-390

[33]

Tyagi, N., Mughees, M.H., Ristenpart, T., Miers, I.: BurnBox: self-revocable encryption in a world of compelled access. In: Enck, W., Felt, A.P. (eds.) USENIX Security 2018, Baltimore, MD, USA, 15–17 August 2018, pp. 445–461. USENIX Association (2018)

[34]

Zuo C, Sun S-F, Liu JK, Shao J, and Pieprzyk J Lopez J, Zhou J, and Soriano M Dynamic searchable symmetric encryption schemes supporting range queries with forward (and backward) security Computer Security 2018 Cham Springer 228-246

Cited By

Jaeger JStracovsky R(2024)Dictators? Friends? Forgers.Advances in Cryptology – ASIACRYPT 202410.1007/978-981-96-0888-1_4(105-137)Online publication date: 10-Dec-2024
https://dl.acm.org/doi/10.1007/978-981-96-0888-1_4
Katz JRosenberg M(2024)LATKE: A Framework for Constructing Identity-Binding PAKEsAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68379-4_7(218-250)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68379-4_7
Badertscher CCiampi MKiayias A(2023)Agile Cryptography: A Universally Composable ApproachTheory of Cryptography10.1007/978-3-031-48624-1_18(480-509)Online publication date: 29-Nov-2023
https://dl.acm.org/doi/10.1007/978-3-031-48624-1_18
Show More Cited By

Recommendations

Practical convertible authenticated encryption schemes using self-certified public keys

A convertible authenticated encryption scheme allows a designated receiver to recover and verify a message simultaneously, during which the recipient can prove the dishonesty of the sender to any third party if the sender repudiates her signature later. ...
Revocable hierarchical identity-based encryption with adaptive security
Abstract
Hierarchical identity-based encryption (HIBE) can be extended to revocable HIBE (RHIBE) if a private key of a user can be revoked when the private key is revealed or expired. Previously, many selectively secure RHIBE schemes were ...
Generic constructions of secure-channel free searchable encryption with adaptive security

For searching keywords against encrypted data, public key encryption scheme with keyword search PEKS, and its extension secure-channel free PEKS SCF-PEKS, has been proposed. In this paper, we extend the security of SCF-PEKS, calling it adaptive SCF-PEKS,...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Advances in Cryptology – CRYPTO 2020: 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17–21, 2020, Proceedings, Part I

Aug 2020

882 pages

ISBN:978-3-030-56783-5

DOI:10.1007/978-3-030-56784-2

Editors:
Daniele Micciancio
UC San Diego, La Jolla, CA, USA
,
Thomas Ristenpart
Cornell Tech, New York, NY, USA

© International Association for Cryptologic Research 2020.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 17 August 2020

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Jaeger JStracovsky R(2024)Dictators? Friends? Forgers.Advances in Cryptology – ASIACRYPT 202410.1007/978-981-96-0888-1_4(105-137)Online publication date: 10-Dec-2024
https://dl.acm.org/doi/10.1007/978-981-96-0888-1_4
Katz JRosenberg M(2024)LATKE: A Framework for Constructing Identity-Binding PAKEsAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68379-4_7(218-250)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68379-4_7
Badertscher CCiampi MKiayias A(2023)Agile Cryptography: A Universally Composable ApproachTheory of Cryptography10.1007/978-3-031-48624-1_18(480-509)Online publication date: 29-Nov-2023
https://dl.acm.org/doi/10.1007/978-3-031-48624-1_18
Jaeger J(2023)Let Attackers Program Ideal Models: Modularity and Composability for Adaptive CompromiseAdvances in Cryptology – EUROCRYPT 202310.1007/978-3-031-30620-4_4(101-131)Online publication date: 23-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-30620-4_4
Len JGrubbs PRistenpart T(2022)Authenticated Encryption with Key IdentificationAdvances in Cryptology – ASIACRYPT 202210.1007/978-3-031-22969-5_7(181-209)Online publication date: 5-Dec-2022
https://dl.acm.org/doi/10.1007/978-3-031-22969-5_7
Backendal MGünther FPaterson K(2022)Puncturable Key Wrapping and Its ApplicationsAdvances in Cryptology – ASIACRYPT 202210.1007/978-3-031-22966-4_22(651-681)Online publication date: 5-Dec-2022
https://dl.acm.org/doi/10.1007/978-3-031-22966-4_22
Tyagi NCeli SRistenpart TSullivan NTessaro SWood C(2022)A Fast and Simple Partially Oblivious PRF, with ApplicationsAdvances in Cryptology – EUROCRYPT 202210.1007/978-3-031-07085-3_23(674-705)Online publication date: 30-May-2022
https://dl.acm.org/doi/10.1007/978-3-031-07085-3_23
Cash DNg RRivkin A(2021)Improved Structured Encryption for SQL Databases via Hybrid IndexingApplied Cryptography and Network Security10.1007/978-3-030-78375-4_19(480-510)Online publication date: 21-Jun-2021
https://dl.acm.org/doi/10.1007/978-3-030-78375-4_19

View Options

View options

Figures

Tables

Media

View Table of Conten