Randomness extractors and error correcting codes are fundamental objects in computer science. Recently, there have been several natural generalizations of these objects, in the context and study of tamper resilient cryptography. These are seeded non-malleable extractors, introduced in [DW09]; seedless non-malleable extractors, introduced in [CG14b]; and non-malleable codes, introduced in [DPW10]. However, explicit constructions of non-malleable extractors appear to be hard, and the known constructions are far behind their non-tampered counterparts. In this paper we make progress towards solving the above problems. Our contributions are as follows. (1) We construct an explicit seeded non-malleable extractor for min-entropy @math . This dramatically improves all previous results and gives a simpler 2-round privacy amplification protocol with optimal entropy loss, matching the best known result in [Li15b]. (2) We construct the first explicit non-malleable two-source extractor for min-entropy @math , with output size @math and error @math . (3) We initiate the study of two natural generalizations of seedless non-malleable extractors and non-malleable codes, where the sources or the codeword may be tampered many times. We construct the first explicit non-malleable two-source extractor with tampering degree @math up to @math , which works for min-entropy @math , with output size @math and error @math . We show that we can efficiently sample uniformly from any pre-image. By the connection in [CG14b], we also obtain the first explicit non-malleable codes with tampering degree @math up to @math , relative rate @math , and error @math .
Here, while one can still design protocols for an active adversary, the major goal is to design a protocol that uses as few number of interactions as possible, and output a uniform random string @math that has length as close to @math as possible (the difference is called ). When the entropy rate of @math is large, i.e., bigger than @math , there exist protocols that take only one round (e.g., @cite_39 , @cite_36 ). However these protocols all have very large entropy loss. On the other hand, @cite_12 showed that when the entropy rate of @math is smaller than @math , then no one round protocol exists; furthermore the length of @math has to be at least @math smaller than @math . Thus, the natural goal is to design a two-round protocol with such optimal entropy loss. There has been a lot of effort along this line @cite_39 , @cite_36 , @cite_12 , @cite_42 , @cite_40 , @cite_5 , @cite_28 , @cite_38 , @cite_52 , @cite_27 . However, all protocols before the work of @cite_28 either need to use @math rounds, or need to incur an entropy loss of @math .
@cite_38 @cite_36 @cite_28 @cite_42 @cite_52 @cite_39 @cite_40 @cite_27 @cite_5 @cite_12
2066209652 2140805804 2039605106 2102879646
In this paper we examine the problem of sending an n-bit data item from a client to a server across an asymmetric communication channel. We demonstrate that there are scenarios in which a high-speed link from the server to the client can be used to greatly reduce the number of bits sent from the client to the server across a slower link. In particular, we assume that the data item is drawn from a probability distribution D that is known to the server but not to the client. We present several protocols in which the expected number of bits transmitted by the server and client are O(n) and O(H(D)+1), respectively, where H(D) is the binary entropy of D (and can range from 0 to n). These protocols are within a small constant factor of optimal in terms of the number of bits sent by the client. The expected number of rounds of communication between the server and client in the simplest of our protocols is O(H(D)). We also give a protocol for which the expected number of rounds is only O(1), but which requires more computational effort on the part of the server. A third technique provides a tradeoff between the computational effort and the number of rounds. These protocols are complemented by several lower bounds and impossibility results. We prove that all of our protocols are existentially optimal in terms of the number of bits sent by the server, i.e., there are distributions for which the total number of bits exchanged has to be at least n. In addition, we show that there is no protocol that is optimal for every distribution (as opposed to just existentially optimal) in terms of bits sent by the server. We demonstrate this by proving that it is undecidable to compute (even approximately), for an arbitrary distribution D, the expected number of bits that must be exchanged by the server and client on the distribution D. We study the question of basing symmetric key cryptography on weak secrets. In this setting, Alice and Bob share an n-bit secret W, which might not be uniformly random, but the adversary has at least k bits of uncertainty about it (formalized using conditional min-entropy). Since standard symmetric-key primitives require uniformly random secret keys, we would like to construct an authenticated key agreement protocol in which Alice and Bob use W to agree on a nearly uniform key R, by communicating over a public channel controlled by an active adversary Eve. We study this question in the information theoretic setting where the attacker is computationally unbounded. We show that single-round (i.e. one message) protocols do not work when k ≤ n 2, and require poor parameters even when n 2 On the other hand, for arbitrary values of k, we design a communication efficient two-round (challenge-response) protocol extracting nearly k random bits. This dramatically improves the previous construction of Renner and Wolf [32], which requires Θ(λ + log(n)) rounds where λ is the security parameter. Our solution takes a new approach by studying and constructing "non-malleable" seeded randomness extractors -- if an attacker sees a random seed X and comes up with an arbitrarily related seed X', then we bound the relationship between R= Ext(W;X) and R' = Ext(W;X'). We also extend our two-round key agreement protocol to the "fuzzy" setting, where Alice and Bob share "close" (but not equal) secrets WA and WB, and to the Bounded Retrieval Model (BRM) where the size of the secret W is huge. Assume we have a network of three or more players, each player in possession of some private input. The players want to compute some function of these private inputs, but in a way which protects the privacy of each participant's contribution. Not all of the players can be trusted to do as they are instructed. The resources the players are given to accomplish their goal are communication--the ability to privately send messages to one another, or to broadcast messages to the community as a whole--and local computation. Many insightful protocols have been proposed for solving this problem of multiparty secure function evaluation. Building on Yao's protocol for the case of two players (Ya86), Goldreich, Micali and Wigderson (GMW87) offered the first general protocol for this problem, and they provided the paradigm on which a large body of successive work was based. Despite enormous progress, research on secure function evaluation has suffered from some serious shortcomings. First, though many protocols have been devised for solving the problem, what, exactly, these protocols accomplish has not been fully understood. In fact, no rigorously specified and generally accepted definitions have been proposed in this field. Second, protocols for multiparty secure function evaluation could be extremely inefficient, the main cause being that they required an unbounded (and usually large) number of communication rounds. We address both of these points, carefully crafting definitions which satisfactorily deal with the myriad of issues lurking here, and offering a new protocol for multiparty secure function evaluation--one which categorically improves the complexity requirements for this task. The new protocol completely divorces the computational complexity of the function being collaboratively computed from the round complexity of the protocol that evaluates it. Using this approach, we show that a rigorously-specified and extremely strong notion of secure function evaluation can be achieved by a protocol which requires only a fixed constant number of rounds of interaction. This result assumes only the existence of a one-way function and that the majority of the participants to the protocol behave correctly. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.) We revisit the classic problem of spreading a piece of information in a group of @math n fully connected processors. By suitably adding a small dose of randomness to the protocol of Gasieniec and Pelc (Parallel Comput 22:903---912, 1996), we derive for the first time protocols that (i) use a linear number of messages, (ii) are correct even when an arbitrary number of adversarially chosen processors does not participate in the process, and (iii) with high probability have the asymptotically optimal runtime of @math O(logn) when at least an arbitrarily small constant fraction of the processors are working. In addition, our protocols do not require that the system is synchronized nor that all processors are simultaneously woken up at time zero, they are fully based on push-operations, and they do not need an a priori estimate on the number of failed nodes. Our protocols thus overcome the typical disadvantages of the two known approaches, algorithms based on random gossip (typically needing a large number of messages due to their unorganized nature) and algorithms based on fair workload splitting (which are either not time-efficient or require intricate preprocessing steps plus synchronization).