This thesis discusses new results in two areas within cryptography; securely transmitting a message between two parties and securely computing a function on the inputs of multiple parties. For both of these areas we mainly consider perfectly secure protocols, which are protocols that have a zero error probability and that do not rely on any number-theoretical assumptions for their security or correctness.
For the first area, we in this thesis give an overview of all results on perfectly secure message transmission in the commonly used model and furthermore determine the exact achievable communication complexity under the weakest possible assumption in this model. For the second area, which is commonly referred to as secure multi-party computation, we introduce new techniques that allow to drastically reduce the required communication for perfectly secure multi-party computations and establish new connections with coding theory and algebraic geometry.
We study a new type of separations between quantum and classical communication complexity, separations that are obtained using quantum protocols where all parties are efficient , in the sense that they can be implemented by small quantum circuits, with oracle access to their inputs. Our main result qualitatively matches the strongest known separation between quantum and classical communication complexity Gavinsky (2016) and is obtained using a quantum protocol where all parties are efficient. More precisely, we give an explicit partial Boolean function f over inputs of length N , such that: f can be computed by a simultaneous-message quantum protocol with communication complexity polylog( N ) (where at the beginning of the protocol Alice and Bob also have polylog( N ) entangled EPR pairs). Any classical randomized protocol for f , with any number of rounds, has communication complexity at least
Ω~(N1/4) . All parties in the quantum protocol of Item (1) (Alice, Bob and the referee) can be implemented by quantum circuits of size polylog( N ) (where Alice and Bob have oracle access to their inputs). Items (1), (2) qualitatively match the strongest known separation between quantum and classical communication complexity, proved by Gavinsky (2016). Item (3) is new. (Our result is incomparable to the one of Gavinsky. While he obtained a quantitatively better lower bound of
Ω(N1/2) in the classical case, the referee in his quantum protocol is inefficient). Exponential separations of quantum and classical communication complexity have been studied in numerous previous works, but to the best of our knowledge the efficiency of the parties in the quantum protocol has not been addressed, and in most previous separations the quantum parties seem to be inefficient. The only separations that we know of that have efficient quantum parties are the recent separations that are based on lifting Göös et al. (2017), Chattopadhyay et al. (2019a). However, these separations seem to require quantum protocols with at least two rounds of communication, so they imply a separation of two-way quantum and classical communication complexity, but they do not give the stronger separations of simultaneous-message quantum communication complexity vs. two-way classical communication complexity (or even one-way quantum communication complexity vs. two-way classical communication complexity). Our proof technique is completely new, in the context of communication complexity, and is based on techniques from Raz & Tal (2019). Our function f is based on a lift of the forrelation problem, using xor as a gadget.
In this dissertation, we study the design of secure and efficient protocols for distributed linear algebra problems. All existing solutions to the problem are either inefficient in terms of round and communication complexity and/or provide security against very weak adversaries.
We design protocols for two different adversarial settings. (i) Computational: where the adversary's computational resources are bounded, but the adversary is allowed to corrupt all but one of the participants. (ii) Information theoretic: where the adversary is unconditionally powerful, but is only allowed to corrupt a third of the participants. The security in both cases is defined in the real world/ideal world simulation paradigm, where we assume that the adversary can behave arbitrarily malicious.
Our main constructions are O(s) round protocols with O(sn2+1/s) communication for testing singularity of a shared n x n matrix, for any positive integer s, in both adversarial settings. We then use and extend these constructions to design secure protocols for computing the rank of a shared matrix and solving shared linear systems with similar efficiency. Our protocols are almost optimal in terms of round and communication complexity, as they roughly match the efficiency of the best possible protocols for the case where security is not a concern.
We use a wide range of techniques from computer algebra to reduce the problem of securely deciding singularity to the problem of secure matrix multiplication. We then design new and efficient protocols for secure matrix multiplication in both adversarial environments. In the computational setting, and when there are only two parties, we apply cut-and-choose techniques to encrypted algebraic encodings of the inputs, outputs, and intermediate values in order to prevent malicious behavior. We achieve even better amortized efficiency when running multiple instances of the protocol, via use of share-packing techniques. When the number of parties is more that two, our construction relies on efficient instantiations of the inner and outer protocols in a recently introduced compiler by Ishai et al. [35]. In the information theoretic setting, our protocol takes advantage of a homomorphic commitment scheme to achieve the improved efficiency.