As some of you may know, a school and a workshop on Mathematics of Information-Theoretic Cryptography were held at the Lorentz Center in Leiden University this May. Organized by Ignacio Cascudo, Ronald Cramer, Venkatesan Guruswami, Yuval Ishai, Carles Padró and Chiaoping Xing, both events had several interesting talks covering a wide range of topics. In this blog post I will cover some of the highlights concerning information-theoretic tools and protocols for MPC that were presented during the workshop.
Multi-Linear Secret Sharing
Amos Beimel presented new results on Multi-Linear Secret sharing Schemes obtained in a joint work with Aner Ben-Efraim, Carles Padró and Ilya Tyomkin. Intuitively, such schemes can be viewed as a generalization of regular linear secret sharing schemes that works over secrets composed of an arbitrary number of field elements. In his talk, Amos showed that for every prime p multi-linear secret sharing schemes where the secret is composed of p field elements are more powerful than similar schemes where the secret is composed of less than p elements. This observation sheds light on the nature of such schemes and gives interesting insight on optimizing protocols and applications that use them as a building block. He also presented super-polynomial lower bounds on the share size of multi-linear secret sharing schemes, which were only known for linear schemes.
OT-based Secure Computation
Jesper Buus Nielsen described his new approach to secure two-party computation that appeared in Crypto 2012 in a joint work with Peter Sebastian Nordholt, Claudio Orlandi and Sai Sheshank Burra. He focused on the oblivious transfer (OT) extension protocol described in that paper that makes it possible to obtain many actively secure oblivious transfers for a pretty cheap price (O(1) evaluations of a hash function per OT). This protocol builds on the general approach to OT extension introduced by Yuval ishai et al. and yields more than a milion active secure OTs per second. Having explained his approach to secure two-party computation and its efficiency, Jesper discussed how having cheap access to such large quantities of OTs could help obtaining more efficient two-party computation. An interesting question posed by him is whether the IPS compiler could achieve the same (or even better than) efficiency of his Crypto’12 protocol with the right parameters and underlying codex.
Manoj Prabhakaran gave a very nice overview of classic and recent results on “cryptographic complexity”. He defined the cryptographic complexity of a (multi-party) function as the amortized number of “crypto gates” needed to securely evaluate the function. This can be viewed a formalization of the long standing question of what cryptographic primitives can be used as building blocks to obtain other primitives and specific functions. In fact, as Manoj pointed out in his talk, the cryptographic complexity of a certain function does not depend on the specific crypto gate used as building block as long as it is complete (for example, Oblivious Transfer). He went over recent results and state of the art techniques to obtain lower bounds on cryptographic complexity, touching different areas such as secure function evaluation and cryptography based on noisy resources. Building on the his general exposition of the subject, Manoj identified showing functions with super-linear cryptographic complexity (or even proofs of existence of such functions) as a main open problem in this field.
Functional Secret Sharing
Yvo Desmedt called the audience’s attention to Functional Secret Sharing, which allows a qualified set of parties to obtain a function evaluated on the secret and nothing else. This result appeared in the paper Computing Functions Of Shared Secrets by Yvo himself in collaboration with Amos Beimel, Mike Burmester and Eyal Kushilevitz. Yvo pointed out the similarity between this overlooked technique and current results on functional encryption. The paper presents basically two approaches: evaluating the function over the secret through private channels and through public broadcast channels. The scheme originally proposed is based on Shamir’s secret sharing scheme, naturally limiting the result to threshold access structures. Yvo remarked that there are still many open problems concerning functional secret sharing, such as generalizing the existing results to general access structures, obtaining more efficient schemes, considering other (possibly weaker) security definition and obtaining better results on the communication complexity of such schemes.
Broadcast Efficient MPC
Juan Garay presented his paper on Broadcast-Efficient Secure Multiparty Computation, which is a joint work with Clint Givens and Rafail Ostrovsky. In this paper, the broadcast channel is considered as an expensive resource, as it cannot be simulated if more than a third of the parties is corrupted. The main goal of the paper is to obtain protocols for MPC that minimize the use of the broadcast channel (or “broadcast complexity). The main result obtained towards this goal is a concrete protocol that only accesses the broadcast channel three times during a preprocessing phase and then never uses it anymore. This model fits well in situations where the parties are allowed to come together for an initial preprocessing phase where they have temporary access to a broadcast channel. Moreover, the protocol has a constant number of rounds. In its core are new constructions of verifiable secret sharing and pseudosignatures.
Crypto from Noisy Channels
Suhas Diggavi introduced a new model of noisy channel communication where all parties have access to an “erasure broadcast channel” and investigated what cryptographic primitives and protocols could be built on it. In contrast to Wyner’s classical wiretap channel, the model introduced by Suhas provides a single broadcast channel shared by all parties (including the adversary) where part of the messages transmitted are lost (erased). Consequently, all the honest parties and the adversary have exactly the same view of the information exchanged in the channel, requiring different techniques to obtain private message transmission and other primitives. Suhas shows that it is necessary to assume a (public) noiseless feedback channel between parties in order to obtain interesting cryptographic applications. Concretely he constructs key agreement and private message transmission solely from the physical noise properties of the channel and the feedback channel. There are still many open problems in this model, such as obtaining oblivious transfer, bit commitment and studying the capacity of this kind of channel for such cryptographic primitives.