There is a vast body of work on implementing anonymous communication. In this paper, we study the possibility of using anonymous communication as a building block, and show that one can leverage on anonymity in a variety of cryptographic contexts. Our results go in two directions. middot Feasibility. We show that anonymous communication over insecure channels can be used to implement unconditionally secure point-to-point channels, broadcast, and general multi-party protocols that remain unconditionally secure as long as less than half of the players are maliciously corrupted. middot Efficiency. We show that anonymous channels can yield substantial efficiency improvements for several natural secure computation tasks. In particular, we present the first solution to the problem of private information retrieval (PIR) which can handle multiple users while being close to optimal with respect to both communication and computation
There is a vast body of work on implementing anonymous communication. In this paper, we study the possibility of using anonymous communication as a building block, and show that one can leverage on anonymity in a variety of cryptographic contexts. Our results go in two directions. middot Feasibility. We show that anonymous communication over insecure channels can be used to implement unconditionally secure point-to-point channels, broadcast, and general multi-party protocols that remain unconditionally secure as long as less than half of the players are maliciously corrupted. middot Efficiency. We show that anonymous channels can yield substantial efficiency improvements for several natural secure computation tasks. In particular, we present the first solution to the problem of private information retrieval (PIR) which can handle multiple users while being close to optimal with respect to both communication and computation
The thesis investigates a broad area of cryptography dealing with anonymity. We proposed a semi-formal model of anonymous channels (protocols for anonymous communication). Our model is able to capture many aspects of wide range of types of anonymous communication, however, we concentrate mostly on sender anonymity, receiver anonymity and relationship anonymity. These are the most basic types of anonymity and many others can be either derived from them or only slight modifications are required to include them into our model. Our model is based on protocol graphs (graphs describing communication patterns). Security properties are based on comparing these protocol graphs. If certain properties hold we can speak about anonymity achieved by a protocol. Our model also includes a novel idea of friends - participants who are allowed to know identity of some anonymous participant. Several anonymous channels together with their dining cryptographers based protocols are also presented in the thesis. These include protocols for the most basic anonymous channels (these are private bipartite channels) as well as for several complex channels. We also present information-theoretically secure protocols that make use of quantum resources. We were able to build a quantum protocol for an anonymous channel for which no classical protocol is known to exist (in the same cryptographic settings). Based on these anonymous channels and their protocols we also scratched surface of resource based reduction between cryptographic protocols. Because of complexity of all the areas of our research the thesis is written in semi-formal language. The main reason is flexibility and feasibility of working with the model. We use the well known language that is often used in IT security.
We focus on three different types of multi-party cryptographic protocols. The first is in the area of unconditionally secure signature schemes, the goal of which is to provide users the ability to electronically sign documents without the reliance on computational assumptions needed in traditional digital signatures. The second is on cooperative protocols in which users help each other maintain privacy while querying a database, called user-private information retrieval protocols. The third is concerned with the generalized Russian cards problem, in which two card players wish to communicate their hands to each other via public announcements without the third player learning the card deal. The latter two problems have close ties to the field of combinatorial designs, and properly fit within the field of combinatorial cryptography. All of these problems have a common thread, in that they are grounded in the information-theoretically secure or unconditionally secure setting.
While many scenarios of anonymous communication can be solved by various famous classical techniques including mix nets or dining cryptographers (DC), an abundant amount of anonymous tasks remains open. In this paper, we present a solution to one such task. Our protocol serves as a private communication channel for quantum messages while ensuring that both the sender and the receiver stay anonymous in a set of all parties. Our protocol is a continuation of our previous work on anonymous transmission of quantum information. The protocol does not require trusted parties, and is secure against an active adversary. It can also withstand denial of service attacks. The protocol exhibits an advantage of quantum resources over classical because no classical solution is known (in the same security settings). Entanglement swapping technique is used to create "symmetry" in the protocol, which makes it very transparent and easier to analyze. The security analysis we present is heavily based on our previous work on quantum anonymous communication. The task we implement is also a nice illustration of a cryptographic task where two parties in a multi-party protocol can be dishonest at the same time, but are not cooperating.
Security and privacy are of paramount importance in the modern information age. Secure multi-party computation and private information retrieval are canonical and representative problems in cryptography that capture the key challenges in understanding the fundamentals of security and privacy. In this dissertation, we use information theoretic tools to tackle these two classical cryptographic primitives. In the first part, we consider the secure multi-party computation problem, where multiple users, each holding an independent message, wish to compute a function on the messages without revealing any additional information. We present an efficient protocol in terms of randomness cost to securely compute a vector linear function. In the second part, we discuss the symmetric private information retrieval problem, where a user wishes to retrieve one message from a number of replicated databases while keeping the desired message index a secret from each individual database. Further, the user learns nothing about the other messages. We present an optimal protocol that achieves the minimum upload cost for symmetric private information retrieval, i.e., the queries sent from the user to the databases have the minimum number of bits.
There is a large body of work on using noisy communication channels for realizing different crypto-graphic tasks. In particular, it is known that secure message transmission can be achieved uncondition-ally using only one-way communication from the sender to the receiver. In contrast, known solutions for more general secure computation tasks inherently require interaction, even when the entire input originates from the sender. We initiate a general study of cryptographic protocols over noisy channels in a setting where only one party speaks. In this setting, we show that the landscape of what a channel is useful for is much richer. Concretely, we obtain the following results. • Relationships between channels. The binary erasure channel (BEC) and the binary symmetric channel (BSC), which are known to be securely reducible to each other in the interactive setting, turn out to be qualitatively different in the setting of one-way communication. In particular, a BEC cannot be implemented from a BSC, and while the erasure probability of a BEC can be manipulated in both directions, the crossover probability of a BSC can only be manipulated in one direction. • Zero-knowledge proofs and secure computation of deterministic functions. One-way commu-nication over BEC or BSC is sufficient for securely realizing any deterministic (possibly reactive) functionality which takes its inputs from a sender and delivers its outputs to a receiver. This pro-vides the first truly non-interactive solutions to the problem of zero-knowledge proofs. • Secure computation of randomized functions. One-way communication over BEC or BSC can-not be used for realizing general randomized functionalities which take input from a sender and deliver output to a receiver. On the other hand, one-way communication over other natural chan-nels, such as bursty erasure channels, can be used to realize such functionalities. This type of protocols can be used for distributing certified cryptographic keys without revealing the keys to the certification authority.
Historically, cryptography was created and used to deliver messages between people in such a way that only the intended receiver would be able to read them. The two persons communicating trusted each other, but not the rest of the world - for instance, not the message bearer. But what happens if we assume instead that even the receiver of a message may not be trusted by the sender, while both still have an interest in communicating? This problem is addressed by secure multi-party computation, that studies communication and shared computation between mutually distrusting parties. In a world where most of the communication happens over the Internet, and where an ever-increasing amount of computation is outsourced, for example to the cloud, multi-party computation is a subject of crucial importance. However, unconditionally secure multi-party protocols have never found practical application: the lack of realistic noisy channel models, that are required to achieve security against computationally unbounded adversaries, prevents implementation over real-world, standard communication protocols.\n\nIn this thesis, we study the properties and characteristics of noisy channels, and we introduce new models based on real-world error sources that have never been studied in this context, such as delays. On the contrary, previous works mostly focused on theoretical noisy channels that have little in common with the reality of network communication. We show that the models we propose are suitable for multi-party computation by building on each of them a protocol for oblivious transfer, a fundamental cryptographic primitive that implies any secure computation. Thanks to the realism of our noisy channels, we are able to provide the first working implementation of unconditionally secure oblivious transfer over both wired and wireless networks and different Internet protocols, which we test thoroughly in an extensive set of experiments. Our constructions are not only more realistic, but also more flexible, as they allow larger ranges of error probabilities. This will eventually open the way for the widespread use of unconditionally secure multi-party computation.