McFIL: Model Counting Functionality-Inherent Leakage
Preprint
Abstract
Protecting the confidentiality of private data and using it for useful collaboration have long been at odds. Modern cryptography is bridging this gap through rapid growth in secure protocols such as multi-party computation, fully-homomorphic encryption, and zero-knowledge proofs. However, even with provable indistinguishability or zero-knowledgeness, confidentiality loss from leakage inherent to the functionality may partially or even completely compromise secret values without ever falsifying proofs of security. In this work, we describe McFIL, an algorithmic approach and accompanying software implementation which automatically quantifies intrinsic leakage for a given functionality. Extending and generalizing the Chosen-Ciphertext attack framework of Beck et al. with a practical heuristic, our approach not only quantifies but maximizes functionality-inherent leakage using Maximum Model Counting within a SAT solver. As a result, McFIL automatically derives approximately-optimal adversary inputs that, when used in secure protocols, maximize information leakage of private values.Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- BIRD: Engineering an Efficient CNF-XOR SAT Solver and Its Applications to Approximate Model CountingProceedings of the AAAI Conference on Artificial Intelligence, 2019
- Enforcing Ideal-World Leakage Bounds in Real-World Secret Sharing MPC Frameworks2018
- Distribution-Aware Sampling and Weighted Model Counting for SATProceedings of the AAAI Conference on Artificial Intelligence, 2014
- Dynamic enforcement of knowledge-based security policies using probabilistic abstract interpretationJournal of Computer Security, 2013
- PP is as Hard as the Polynomial-Time HierarchySIAM Journal on Computing, 1991
- The polynomial-time hierarchyTheoretical Computer Science, 1976