Alice, Bits, and Bob

Mark Simkin

Research output: Book/anthology/dissertation/reportPh.D. thesis


Cryptography is a diverse and rich field spanning across many disciplines of computer science.
In this thesis we make contributions to several very different areas of cryptography.

We present the first information-theoretically secure compiler that transforms any multiparty computation protocol that is secure against t(t+1) passive corruptions into one that is secure against t active corruptions.
The compiler is oblivious to the domain over which the computation is performed.
That is, if the underlying passively secure protocol works over rings, fields, or bits, then so does the actively secure one.

The second contribution in this thesis is in the domain of private set intersection.
More concretely, we look at the problem of threshold private set intersection, where two parties want to learn the intersection of their sets if and only if the intersection is larger than a given threshold.
If the sets differ by too much, then the protocol should not reveal any information about the set beyond the fact that they differ by too much.
We present the first protocol, whose communication complexity does not linearly depend on the set sizes, but only (up to polylog factors) on the maximum allowed symmetric set difference d.
Our first protocol is based on fully homomorphic encryption and has a communication complexity of O(d).
Our second protocol is based on additively homomorphic encryption and has a communication complexity of O(d^2).

Our third contribution is in the domain of leakage-resilient and non-malleable secret sharing.
In such schemes, the adversary can leak from or tamper with all shares.
In the case of leakage-resilience we would like to ensure that even given the leakage from each share the secret remains hidden.
In the case of non-malleability we would like to ensure that any secret that is reconstructed from the tampered shares is either identical or completely unrelated to the original one.
We present information-theoretic compilers that transforms any secret sharing scheme for any access structure into leakage-resilient or non-malleable versions thereof.
Original languageEnglish
Number of pages110
Publication statusPublished - 2020


Dive into the research topics of 'Alice, Bits, and Bob'. Together they form a unique fingerprint.

Cite this