Information theoretically secure multiparty computation (MPC) is a central primitive in modern cryptography.
It enables mutually distrusting parties to collaboratively perform computations on their combined data by ensuring that each party's data is kept private from the others.
This is achieved by designing communication protocols which allow the parties to collectively simulate an incorruptible trusted party, who privately receives inputs from the parties, computes the pre-agreed functionality, and delivers the outputs to the appropriate parties privately.
The subject of this dissertation is MPC when there is limited connectivity in the communication network available to the participants.
Our motivations and the progress we made in addressing them follows:
- In many practical scenarios, the parties may only have access to a communication network with limited connectivity, in that, not every pair of parties can communicate privately and reliably with each other.
We characterize the conditions under which a pair of parties can compute any functionality with information theoretic security in an incomplete network of reliable, private links.
Separate characterizations are obtained for honest-but-curious and malicious modes of corruption with security against general adversary structures.
- Many cryptographic tasks can be modelled as secure 2-party computation (2PC) using only one-directional communication.
Garg et al. (Crypto 15) initiated the study of non-interactive 2PC over noisy channels with one-way communication, namely when only one party speaks.
A major question left open by that work was the completeness of finite channels in this model of secure computation.
We show that bit-ROT (i.e., Randomized Oblivious Transfer) channel, which erases one of the two input bits uniformly at random, can compute any functionality with inverse polynomial security error (in the number of channel uses) in this model against a computationally unbounded adversary.
Further, assuming ideal obfuscation, realizable using tamper-proof hardware tokens, naturally occurring channels such as binary symmetric channel (BSC) and binary erasure channel (BEC) are complete in this sense with inverse polynomial security error against a computationally bounded adversary.
To complement this, we show that no channel with finite alphabet is complete in this model with negligible security error even against a computationally bounded adversary.
Finally, we characterize the channels that enable zero-knowledge proofs in this model; the previous result work had presented construction of zero-knowledge proofs using BEC/BSC channels.
- Studying secure computation with limited interaction tends to reveal new frontiers to approach the problem of complexity of several information theoretic primitives: a notoriously hard problem in cryptography.
We introduce a new primitive in information-theoretic cryptography, namely zero-communication reductions (ZCR), with varying levels of security, and relate it with several other important primitives.
Using these connections, we obtain new upper bounds and lower bounds for complexity of several cryptographic primitives.
- MPC provides a meaningful and robust definition of security that can be used for modelling security guarantees for existing models in network information theory.
Index coding is a well studied problem, in which a server wants to efficiently broadcast n messages intended for n users, each with access to a subset of these messages as side information.
We introduce a notion of privacy in index coding, where the receivers do not learn anything more than the message they want from the server and those they have as side information, and study various aspects of its transmission rate and secret consumption rate.
