Communications in Cryptology IACR CiC

Bayesian Leakage Analysis

A Framework for Analyzing Leakage in Cryptography

Authors

Zachary Espiritu, Seny Kamara, Tarik Moataz
Zachary Espiritu ORCID
MongoDB, New York, United States
zachary dot espiritu at mongodb dot com
Seny Kamara ORCID
MongoDB, New York, United States
Brown University, Providence, United States
seny dot kamara at mongodb dot com
Tarik Moataz ORCID
MongoDB, New York, United States
tarik dot moataz at mongodb dot com

Abstract

We introduce a framework based on Bayesian statistical inference for analyzing leakage in cryptography and its vulnerability to inference attacks. Our framework naturally integrates auxiliary information, defines a notion of adversarial advantage, and provides information-theoretic measures that capture the security of leakage patterns against both full and functional recovery attacks.

We present two main theorems that bound the advantage of powerful inference techniques: the maximum a posteriori (MAP), the maximum likelihood estimate (MLE) and the MAP test. Specifically, we show that the advantage of these methods is exponentially bounded by new entropy measures that capture the susceptibility of leakage patterns to inference.

To demonstrate the applicability of our framework, we design and implement an automated leakage attack engine, Bayle, which leverages a novel inference algorithm that efficiently computes MAP estimates for a large class of i.i.d. leakage models. These models include query equality leakage, the combination of query equality and volume leakage, and leakage patterns arising from naive conjunctions.

References

[ACM+20]
Mário S Alvim, Konstantinos Chatzikokolakis, Annabelle McIver, Carroll Morgan, Catuscia Palamidessi, and Geoffrey Smith. The Science of Quantitative Information Flow. Springer 2020. DOI: 10.1007/978-3-319-96131-6
[APP+21]
Ghous Amjad, Sarvar Patel, Giuseppe Persiano, Kevin Yeo, and Moti Yung. Dynamic Volume-Hiding Encrypted Multi-Maps with Applications to Searchable Encryption. Proceedings of Privacy Enhancing Technologies, 2023:417–436, 2021. DOI: 10.56553/popets-2023-0025
[BB20]
Matthew S. Brennan and Guy Bresler. Reducibility and Statistical-Computational Gaps from Secret Leakage. In Jacob D. Abernethy and Shivani Agarwal, editors, Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria], volume 125 of Proceedings of Machine Learning Research, pages 648–847. 2020. PMLR.
[BBH18]
Matthew S. Brennan, Guy Bresler, and Wasim Huleihel. Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018, volume 75 of Proceedings of Machine Learning Research, pages 48–166. 2018. PMLR.
[BBH+21]
Matthew S. Brennan, Guy Bresler, Samuel B. Hopkins, Jerry Li, and Tselil Schramm. Statistical Query Algorithms and Low Degree Tests Are Almost Equivalent. In Mikhail Belkin and Samory Kpotufe, editors, Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pages 774. 2021. PMLR.
[BBMM18]
Marshall Ball, Elette Boyle, Tal Malkin, and Tal Moran. Exploring the Boundaries of Topology-Hiding Computation. In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018 Proceedings, Part III, volume 10822 of Lecture Notes in Computer Science, pages 294–325. 2018. Springer. DOI: 10.1007/978-3-319-78372-7_10
[BGI+01]
Boaz Barak, Oded Goldreich, Rusell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, and Ke Yang. On the (Im)possibility of Obfuscating Programs. In Joe Kilian, editor, Advances in Cryptology — CRYPTO 2001, pages 1–18, Berlin, Heidelberg. 2001. Springer Berlin Heidelberg. DOI: 10.1007/3-540-44647-8_1
[BGW24]
Alexandra Boldyreva, Zichen Gui, and Bogdan Warinschi. Understanding Leakage in Searchable Encryption: a Quantitative Approach. Proc. Priv. Enhancing Technol., 2024(4):503–524, 2024. DOI: 10.56553/POPETS-2024-0127
[BHK+19]
Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh K. Kothari, Ankur Moitra, and Aaron Potechin. A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. SIAM Journal on Computing, 48(2):687-735, 2019. DOI: 10.1137/17M1138236
[BKM20]
Laura Blackstone, Seny Kamara, and Tarik Moataz. Revisiting Leakage Abuse Attacks. In Network and Distributed System Security Symposium (NDSS '20). 2020. DOI: 10.14722/ndss.2020.23103
[BKMN24]
Amine Bahi, Seny Kamara, Tarik Moataz, and Guevara Noubir. Subliminal Encrypted Multi-Maps and Black-Box Leakage Absorption. Cryptology ePrint Archive, Paper 2024/1708. 2024.
[CGKO06]
Reza Curtmola, Juan Garay, Seny Kamara, and Rafail Ostrovsky. Searchable symmetric encryption: improved definitions and efficient constructions. In Proceedings of the 13th ACM Conference on Computer and Communications Security, pages 79–88, New York, NY, USA. 2006. Association for Computing Machinery. DOI: 10.1145/1180405.1180417
[CGKS95]
B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan. Private information retrieval. In Proceedings of IEEE 36th Annual Foundations of Computer Science, pages 41-50. 1995. DOI: 10.1109/SFCS.1995.492461
[CGPR15]
David Cash, Paul Grubbs, Jason Perry, and Thomas Ristenpart. Leakage-Abuse Attacks Against Searchable Encryption. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pages 668–679, New York, NY, USA. 2015. Association for Computing Machinery. DOI: 10.1145/2810103.2813700
[Cha81]
David L. Chaum. Untraceable electronic mail, return addresses, and digital pseudonyms. Commun. ACM, 24(2):84–90, February 1981. DOI: 10.1145/358549.358563
[CJJ+14]
David Cash, Joseph Jaeger, Stanislaw Jarecki, Charanjit Jutla, Hugo Krawczyk, Marcel Rosu, and Michael Steiner. Dynamic Searchable Encryption in Very-Large Databases: Data Structures and Implementation. In Network and Distributed System Security Symposium (NDSS '14). 2014. DOI: 10.14722/ndss.2014.23264
[CK10]
Melissa Chase and Seny Kamara. Structured Encryption and Controlled Disclosure. In Masayuki Abe, editor, Advances in Cryptology - ASIACRYPT 2010, pages 577–594, Berlin, Heidelberg. 2010. Springer Berlin Heidelberg. DOI: 10.1007/978-3-642-17373-8_33
[Den82]
Dorothy Denning. Cryptography and data security, volume 112. Addison-Wesley 1982.
[DLHP23]
Marc Damie, Jean-Benoist Leger, Florian Hahn, and Andreas Peter. The statistical nature of leakage in SSE schemes and its role in passive attacks. Cryptology ePrint Archive, Paper 2023/1883. 2023.
[DMNS06]
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating Noise to Sensitivity in Private Data Analysis. In Shai Halevi and Tal Rabin, editors, Theory of Cryptography, pages 265–284, Berlin, Heidelberg. 2006. Springer Berlin Heidelberg. DOI: 10.1007/11681878_14
[EGKQ24]
Zachary Espiritu, Marilyn George, Seny Kamara, and Lucy Qin. Synq: Public Policy Analytics Over Encrypted Data. In IEEE Symposium on Security and Privacy (SP), pages 146-165. 2024. DOI: 10.1109/SP54263.2024.00085
[EKM25]
Zachary Espiritu, Seny Kamara, and Tarik Moataz. Bayle (Artifact for “Bayesian Leakage Analysis”). April 2025.
[FIM+06]
Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim, Martin J. Strauss, and Rebecca N. Wright. Secure multiparty computation of approximations. ACM Trans. Algorithms, 2(3):435–472, July 2006. DOI: 10.1145/1159892.1159900
[FVK+15]
Ben A. Fisch, Binh Vo, Fernando Krell, Abishek Kumarasubramanian, Vladimir Kolesnikov, Tal Malkin, and Steven M. Bellovin. Malicious-Client Security in Blind Seer: A Scalable Private DBMS. In 2015 IEEE Symposium on Security and Privacy, pages 395-410. 2015. DOI: 10.1109/SP.2015.31
[GKM21]
Marilyn George, Seny Kamara, and Tarik Moataz. Structured Encryption and Dynamic Leakage Suppression. In Advances in Cryptology – EUROCRYPT 2021: 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17–21, 2021, Proceedings, Part III, pages 370–396, Berlin, Heidelberg. 2021. Springer-Verlag. DOI: 10.1007/978-3-030-77883-5_13
[GLMP18]
Paul Grubbs, Marie-Sarah Lacharité, Brice Minaud, and Kenneth G. Paterson. Pump up the Volume: Practical Database Reconstruction from Volume Leakage on Range Queries. In David Lie, Mohammad Mannan, Michael Backes, and XiaoFeng Wang, editors, Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS 2018, Toronto, ON, Canada, October 15-19, 2018, pages 315–331. 2018. ACM. DOI: 10.1145/3243734.3243864
[GLMP19]
Paul Grubbs, Marie-Sarah Lacharité, Brice Minaud, and Kenneth G. Paterson. Learning to Reconstruct: Statistical Learning Theory and Encrypted Database Attacks. In 2019 IEEE Symposium on Security and Privacy, SP 2019, San Francisco, CA, USA, May 19-23, 2019, pages 1067–1083. 2019. IEEE. DOI: 10.1109/SP.2019.00030
[GM82]
Shafi Goldwasser and Silvio Micali. Probabilistic encryption & how to play mental poker keeping secret all partial information. In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, pages 365–377, New York, NY, USA. 1982. Association for Computing Machinery. DOI: 10.1145/800070.802212
[GMW87]
O. Goldreich, S. Micali, and A. Wigderson. How to play ANY mental game. In ACM Symposium on the Theory of Computation (STOC '87), pages 218–229. 1987. ACM. DOI: 10.1145/28395.28420
[GO96]
Oded Goldreich and Rafail Ostrovsky. Software protection and simulation on oblivious RAMs. J. ACM, 43(3):431–473, May 1996. DOI: 10.1145/233551.233553
[GPT23]
Zichen Gui, Kenneth G. Paterson, and Tianxin Tang. Security analysis of MongoDB queryable encryption. 2023.
[Gra92]
James W. Gray. Toward a Mathematical Foundation for Information Flow Security. J. Comput. Secur., 1(3–4):255–294, May 1992. DOI: 10.1109/RISP.1991.130769
[GRR19]
Adam Groce, Peter Rindal, and Mike Rosulek. Cheaper Private Set Intersection via Differentially Private Leakage. Proc. Priv. Enhancing Technol., 2019(3):6–25, 2019. DOI: 10.2478/POPETS-2019-0034
[Has70]
W K Hastings. Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57(1):97–109, 1970. DOI: 10.2307/2334940
[HKE12]
Yan Huang, Jonathan Katz, and David Evans. Quid-Pro-Quo-tocols: Strengthening Semi-honest Protocols with Dual Execution. In 2012 IEEE Symposium on Security and Privacy, pages 272-284. 2012. DOI: 10.1109/SP.2012.43
[Hop18]
Sam Hopkins. Statistical Inference and the Sum of Squares Method. PhD thesis, Cornell University, 2018.
[IKK12]
M. Saiful Islam, M. Kuzu, and M. Kantarcioglu. Access Pattern disclosure on Searchable Encryption: Ramification, Attack and Mitigation. In Network and Distributed System Security Symposium (NDSS '12). 2012.
[JGJS99]
Michael I Jordan, Zoubin Ghahramani, Tommi S Jaakkola, and Lawrence K Saul. An introduction to variational methods for graphical models. Machine learning, 37(2):183–233, 1999. DOI: 10.1023/A:1007665907178
[JJK+13]
Stanislaw Jarecki, Charanjit Jutla, Hugo Krawczyk, Marcel Rosu, and Michael Steiner. Outsourced symmetric private information retrieval. In Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security, pages 875–888, New York, NY, USA. 2013. Association for Computing Machinery. DOI: 10.1145/2508859.2516730
[JPS21]
Mireya Jurado, Catuscia Palamidessi, and Geoffrey Smith. A Formal Information-Theoretic Leakage Analysis of Order-Revealing Encryption. In 2021 IEEE 34th Computer Security Foundations Symposium (CSF), pages 1-16. 2021. DOI: 10.1109/CSF51468.2021.00046
[JS19]
Mireya Jurado and Geoffrey Smith. Quantifying Information Leakage of Deterministic Encryption. In Proceedings of the 2019 ACM SIGSAC Conference on Cloud Computing Security Workshop, pages 129–139, New York, NY, USA. 2019. Association for Computing Machinery. DOI: 10.1145/3338466.3358915
[Kea98]
Michael Kearns. Efficient noise-tolerant learning from statistical queries. J. ACM, 45(6):983–1006, November 1998. DOI: 10.1145/293347.293351
[Kel02]
John Kelsey. Compression and Information Leakage of Plaintext. In Joan Daemen and Vincent Rijmen, editors, Fast Software Encryption, pages 263–276, Berlin, Heidelberg. 2002. Springer Berlin Heidelberg. DOI: 10.1007/3-540-45661-9_21
[KF09]
Daphne Koller and Nir Friedman. Probabilistic Graphical Models: Principles and Techniques - Adaptive Computation and Machine Learning. The MIT Press, Cambridge, MA 2009.
[KKNO16]
Georgios Kellaris, George Kollios, Kobbi Nissim, and Adam O'Neill. Generic Attacks on Secure Outsourced Databases. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 1329–1340, New York, NY, USA. 2016. Association for Computing Machinery. DOI: 10.1145/2976749.2978386
[KM18]
Seny Kamara and Tarik Moataz. SQL on Structurally-Encrypted Databases. In Advances in Cryptology – ASIACRYPT 2018: 24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, QLD, Australia, December 2–6, 2018, Proceedings, Part I, pages 149–180, Berlin, Heidelberg. 2018. Springer-Verlag. DOI: 10.1007/978-3-030-03326-2_6
[KM19]
Seny Kamara and Tarik Moataz. Computationally Volume-Hiding Structured Encryption. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2019, pages 183–213, Cham. 2019. Springer International Publishing. DOI: 10.1007/978-3-030-17656-3_7
[KMO18]
Seny Kamara, Tarik Moataz, and Olya Ohrimenko. Structured Encryption and Leakage Suppression. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology – CRYPTO 2018, pages 339–370, Cham. 2018. Springer International Publishing. DOI: 10.1007/978-3-319-96884-1_12
[KMPP22]
Evgenios M. Kornaropoulos, Nathaniel Moyer, Charalampos Papamanthou, and Alexandros Psomas. Leakage Inversion. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. November 2022. ACM. DOI: 10.1145/3548606.3560593
[KMPQ21]
Seny Kamara, Tarik Moataz, Andrew Park, and Lucy Qin. A Decentralized and Encrypted National Gun Registry. In 2021 IEEE Symposium on Security and Privacy (SP), pages 1520-1537. 2021. DOI: 10.1109/SP40001.2021.00072
[KMRR15]
Vladimir Kolesnikov, Payman Mohassel, Ben Riva, and Mike Rosulek. Richer Efficiency/Security Trade-offs in 2PC. In Yevgeniy Dodis and Jesper Buus Nielsen, editors, Theory of Cryptography - 12th Theory of Cryptography Conference, TCC 2015, Warsaw, Poland, March 23-25, 2015, Proceedings, Part I, volume 9014 of Lecture Notes in Computer Science, pages 229–259. 2015. Springer. DOI: 10.1007/978-3-662-46494-6_11
[KMZZ20]
Seny Kamara, Tarik Moataz, Stan Zdonik, and Zheguang Zhao. OPX: An Optimal Relational Database Encryption Scheme. Technical report, IACR ePrint Cryptography Archive. 2020.
[KPR11]
Seny Kamara, Charalampos Papamanthou, and Tom Roeder. CS2: A Searchable Cryptographic Cloud Storage System. Technical report number MSR-TR-2011-58, May 2011.
[KPT20]
Evgenios M. Kornaropoulos, Charalampos Papamanthou, and Roberto Tamassia. The State of the Uniform: Attacks on Encrypted Databases Beyond the Uniform Query Distribution. In 2020 IEEE Symposium on Security and Privacy (SP), pages 1223-1240. 2020. DOI: 10.1109/SP40000.2020.00029
[KPT21]
Evgenios M. Kornaropoulos, Charalampos Papamanthou, and Roberto Tamassia. Response-Hiding Encrypted Ranges: Revisiting Security via Parametrized Leakage-Abuse Attacks. In 2021 IEEE Symposium on Security and Privacy (SP), pages 1502-1519. 2021. DOI: 10.1109/SP40001.2021.00044
[Las01]
Jean B. Lasserre. Global Optimization with Polynomials and the Problem of Moments. SIAM Journal on Optimization, 11(3):796-817, 2001. DOI: 10.1137/S1052623400366802
[LMP17]
Marie-Sarah Lacharité, Brice Minaud, and Kenneth G. Paterson. Improved Reconstruction Attacks on Encrypted Data Using Range Query Leakage. IACR Cryptology ePrint Archive, 2017:701, 2017.
[LMP18]
Marie-Sarah Lacharité, Brice Minaud, and Kenneth G. Paterson. Improved Reconstruction Attacks on Encrypted Data Using Range Query Leakage. In 2018 IEEE Symposium on Security and Privacy (SP), pages 297-314. 2018. DOI: 10.1109/SP.2018.00002
[LS18]
S. L. Lauritzen and D. J. Spiegelhalter. Local Computations with Probabilities on Graphical Structures and Their Application to Expert Systems. Journal of the Royal Statistical Society: Series B (Methodological), 50(2):157-194, December 2018. DOI: 10.1111/j.2517-6161.1988.tb01721.x
[MF06]
P. Mohassel and M. Franklin. Efficiency Tradeoffs for Malicious Two-Party Computation. In Conference on Theory and Practice of Public-Key Cryptography (PKC '06), volume 3958 of Lecture Notes in Computer Science, pages 458-473. 2006. Springer. DOI: 10.1007/11745853_30
[MRR+53]
N Metropolis, A W Rosenbluth, M N Rosenbluth, A H Teller, and E Teller. Equation of state calculations by fast computing machines. The journal of chemical physics, 21(6):1087–1092, 1953. DOI: 10.1063/1.1699114
[NKW15]
M. Naveed, S. Kamara, and C. V. Wright. Inference Attacks on Property-Preserving Encrypted Databases. In ACM Conference on Computer and Communications Security (CCS), pages 644–655. 2015. ACM. DOI: 10.1145/2810103.2813651
[Par03]
Pablo A. Parrilo. Semidefinite Programming Relaxations for Semialgebraic Problems. Mathematical Programming, 95(1):1–33, 2003. DOI: 10.1007/s10107-003-0387-5
[Pea88]
Judea Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA 1988. DOI: 10.1016/C2009-0-27609-4
[PKV+14]
Vasilis Pappas, Fernando Krell, Binh Vo, Vladimir Kolesnikov, Tal Malkin, Seung Geol Choi, Wesley George, Angelos Keromytis, and Steve Bellovin. Blind Seer: A Scalable Private DBMS. In 2014 IEEE Symposium on Security and Privacy, pages 359-374. 2014. DOI: 10.1109/SP.2014.30
[PPYY19]
Sarvar Patel, Giuseppe Persiano, Kevin Yeo, and Moti Yung. Mitigating Leakage in Secure Cloud-Hosted Data Structures: Volume-Hiding for Multi-Maps via Hashing. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, CCS 2019, London, UK, November 11-15, 2019, pages 79–93. 2019. ACM. DOI: 10.1145/3319535.3354213
[PRZB11]
Raluca Ada Popa, Catherine M. S. Redfield, Nickolai Zeldovich, and Hari Balakrishnan. CryptDB: protecting confidentiality with encrypted query processing. In Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles, pages 85–100, New York, NY, USA. 2011. Association for Computing Machinery. DOI: 10.1145/2043556.2043566
[RC04]
Christian P Robert and George Casella. Monte Carlo Statistical Methods. Springer, New York, NY, USA 2004. DOI: 10.1007/978-1-4757-4145-2
[SDT98]
M. S. Stanković, B. M. Danković, and S. B. Trićković. Some Inequalities Involving Harmonic Numbers. In G. V. Milovanović, editor, Recent Progress in Inequalities, volume 430 of Mathematics and Its Applications. Springer, Dordrecht 1998. DOI: 10.1007/978-94-015-9086-0_33
[Sha49]
C. E. Shannon. Communication theory of secrecy systems. The Bell System Technical Journal, 28(4):656-715, 1949. DOI: 10.1002/j.1538-7305.1949.tb00928.x
[SW14]
Amit Sahai and Brent Waters. How to use indistinguishability obfuscation: deniable encryption, and more. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, pages 475–484, New York, NY, USA. 2014. Association for Computing Machinery. DOI: 10.1145/2591796.2591825
[Val84]
Leslie G. Valiant. A theory of the learnable. Commun. ACM, 27(11):1134–1142, November 1984. DOI: 10.1145/1968.1972
[WBMM07]
Charles V. Wright, Lucas Ballard, Fabian Monrose, and Gerald M. Masson. Language Identification of Encrypted VoIP Traffic: Alejandra y Roberto or Alice and Bob?. In 16th USENIX Security Symposium (USENIX Security 07), Boston, MA. August 2007. USENIX Association.
[WP17]
Charles V. Wright and David Pouliot. Early Detection and Analysis of Leakage Abuse Vulnerabilities. IACR Cryptol. ePrint Arch., 2017.
[Yao82]
Andrew C. Yao. Protocols for secure computations. In 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), pages 160–164. 1982. DOI: 10.1109/SFCS.1982.38
[ZKMZ21]
Zheguang Zhao, Seny Kamara, Tarik Moataz, and Stan Zdonik. Encrypted Databases: From Theory to Systems. In Conference on Innovative Data Systems Research (CIDR '21). 2021.

PDFPDF Open access

History
Submitted: 2025-01-14
Accepted: 2025-03-11
Published: 2025-04-08
How to cite

Zachary Espiritu, Seny Kamara, and Tarik Moataz, Bayesian Leakage Analysis. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/a36c0lmol.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.