Description
This thesis investigates the calculation of information leakage caused by an early-out
mechanism in secure multi-party computation schemes. As a model protocol, it uses
the privacy-preserving SAT-solving protocol ppSAT. This early-out optimization reveals
the number of rounds needed to solve a SAT problem, therefore leaking information
about the program’s control flow. In this setup, a semi-honest adversary knows its
own share of the SAT formula and tries to infer the other party’s share. The thesis
models this setting within the Quantitative Information Flow (QIF) framework in order
to measure the resulting information leakage.
This work first evaluates existing QIF tools and methods and shows their limitations
in solving the problem at hand. These drawbacks are mainly caused by scalability limits
and the structure of SAT solving. It then proposes a bin-masking solution tailored to
this setup, based on min-entropy leakage. Afterwards, a tool is presented for applying
the bin-masking method and optimizing it to improve runtime. Overall, the thesis
contributes a practical methodology, along with a tool, for analyzing leakage in the
ppSAT protocol.
|
