We study common randomness where two parties have access to i.i.d. samples from a known random source, and wish to generate a shared random key using limited (or no) communication with the largest possible probability of agreement. This problem is at the core of secret key generation in cryptography, with connections to communication under uncertainty and locality sensitive hashing. We take the approach of treating correlated sources as a critical resource, and ask whether common randomness can be generated resourceefficiently. We consider two notable sources in this setup arising from correlated bits and correlated Gaussians. We design the first explicit schemes that use only a polynomial number of samples (in the key length) so that the players can generate shared keys that agree with constant probability using optimal communication. The best previously known schemes were both nonconstructive and used an exponential number of samples. In the amortized setting, we characterize the largest achievable ratio of key length to communication in terms of the external and internal information costs, two wellstudied quantities in theoretical computer science. In the relaxed setting where the two parties merely wish to improve the correlation between the generated keys of length k, we show that theremore »
Bridging the Capacity Gap Between Interactive and OneWay Communication
We study the communication rate of coding schemes for interactive communication that transform any twoparty interactive protocol into a protocol that is robust to noise.
Recently, Haeupler [11] showed that if an ∊ > 0 fraction of transmissions are corrupted, adversarially or randomly, then it is possible to achieve a communication rate of Furthermore, Haeupler conjectured that this rate is optimal for general input protocols. This stands in contrast to the classical setting of oneway communication in which errorcorrecting codes are known to achieve an optimal communication rate of 1
In this work, we show that the quadratically smaller rate loss of the oneway setting can also be achieved in interactive coding schemes for a very natural class of input protocols. We introduce the notion of average message length, or the average number of bits a party sends before receiving a reply, as a natural parameter for measuring the level of interactivity in a protocol. Moreover, we show that any protocol with average message length ℓ = Ω(poly(1/∊)) can be simulated by a protocol with optimal communication rate 1  Θ(Η(∊)) over an oblivious adversarial channel with error fraction e. Furthermore, under the additional assumption of access to public shared randomness, the more »
 Publication Date:
 NSFPAR ID:
 10121526
 Journal Name:
 ACMSIAM Symposium on Discrete Algorithms
 Page Range or eLocationID:
 2123 to 2142
 Sponsoring Org:
 National Science Foundation
More Like this


null (Ed.)Zeroknowledge (ZK) proofs with an optimal memory footprint have attracted a lot of attention, because such protocols can easily prove very large computation with a small memory requirement. Such ZK protocol only needs O(M) memory for both parties, where M is the memory required to verify the statement in the clear. In this paper, we propose several new ZK protocols in this setting, which improve the concrete efficiency and, at the same time, enable sublinear amortized communication for circuits with some notion of relaxed uniformity. 1. In the circuitbased model, where the computation is represented as a circuit over a field, our ZK protocol achieves a communication complexity of 1 field element per nonlinear gate for any field size while keeping the computation very cheap. We implemented our protocol, which shows extremely high efficiency and affordability. Compared to the previous bestknown implementation, we achieve 6×–7× improvement in computation and 3×– 7× improvement in communication. When running on introlevel AWS instances, our protocol only needs one US dollar to prove one trillion AND gates (or 2.5 US dollars for one trillion multiplication gates over a 61bit field). 2. In the setting where part of the computation can be represented as amore »

This paper explores list decoding of convolutional and polar codes for short messages such as those found in the 5G physical broadcast channel. A cyclic redundancy check (CRC) is used to select a codeword from a list of likely codewords. One example in the 5G standard encodes a 32bit message with a 24bit CRC and a 512bit polar code with additional bits added by repetition to achieve a very low rate of 32/864. This paper shows that optimizing the CRC length improves the Eb/N0 performance of this polar code, where Eb/N0 is the ratio of the energy per data bit to the noise power spectral density. Furthermore, even better Eb/N0 performance is achieved by replacing the polar code with a tailbiting convolutional code (TBCC) with a distancespectrumoptimal (DSO) CRC. This paper identifies the optimal CRC length to minimize the frame error rate (FER) of a rate1/5 TBCC at a specific value of Eb/N0. We also show that this optimized TBCC/CRC can attain the same excellent Eb/N0 performance with the very low rate of 32/864 of the 5G polar code, where the low rate is achieved through repetition. We show that the proposed TBCC/CRC concatenated code outperforms the PBCH polar codemore »

Nissim, K. ; Waters, B. (Ed.)Recent new constructions of rate1 OT [Döttling, Garg, Ishai, Malavolta, Mour, and Ostrovsky, CRYPTO 2019] have brought this primitive under the spotlight and the techniques have led to new feasibility results for privateinformation retrieval, and homomorphic encryption for branching programs. The receiver communication of this construction consists of a quadratic (in the sender's input size) number of group elements for a single instance of rate1 OT. Recently [Garg, Hajiabadi, Ostrovsky, TCC 2020] improved the receiver communication to a linear number of group elements for a single stringOT. However, most applications of rate1 OT require executing it multiple times, resulting in large communication costs for the receiver. In this work, we introduce a new technique for amortizing the cost of multiple rate1 OTs. Specifically, based on standard pairing assumptions, we obtain a twomessage rate1 OT protocol for which the amortized cost per stringOT is asymptotically reduced to only four group elements. Our results lead to significant communication improvements in PSI and PIR, special cases of SFE for branching programs.  PIR: We obtain a rate1 PIR scheme with client communication cost of $O(\lambda\cdot\log N)$ group elements for security parameter $\lambda$ and database size $N$. Notably, after a onetime setup (or onemore »

We give the first communicationoptimal document exchange protocol. For any n and k
more »