We consider the problem of Locally Decodable Codes against an adversary that is computationally bounded in terms of running time. Many times the computational limitations of the adversary help in designing better codes. In this paper we prove (using some standard crytographic assumptions) that in the case of constant query locally decodable codes the computational constraint does not make the adversary less powerful, unless both the sender and the receiver shares a secret key. We show, if either the receiver or the sender has a secret key (that is not known to the other) then designing LDCs against computationally bounded adversary is as hard as designing smooth codes unless some standard cryptographic assumptions are false.
We consider the problem of Locally Decodable Codes against an adversary that is computationally bounded in terms of running time. Many times the computational limitations of the adversary help in designing better codes. In this paper we prove (using some standard crytographic assumptions) that in the case of constant query locally decodable codes the computational constraint does not make the adversary less powerful, unless both the sender and the receiver shares a secret key. We show, if either the receiver or the sender has a secret key (that is not known to the other) then designing LDCs against computationally bounded adversary is as hard as designing smooth codes unless some standard cryptographic assumptions are false.
Locally Decodable Code (LDC) is a code that encodes a message in a way that one can decode any particular symbol of the message by reading only a constant number of locations, even if a constant fraction of the encoded message is adversarially corrupted. In this paper we present a new approach for the construction of LDCs. We show that if there exists an irreducible representation (ρ, V) of G and q elements g1, g2,..., gq in G such that there exists a linear combination of matrices ρ(gi) that is of rank one, then we can construct a q-query Locally Decodable Code C: V → F G. We show the potential of this approach by constructing constant query LDCs of subexponential length matching the parameters of the best known constructions. 1
A locally decodable code encodes n-bit strings x in m-bit codewords C(x), in such a way that one can recover any bit xi from a corrupted codeword by querying only a few bits of that word. We use a quantum argument to prove that LDCs with 2 classical queries need exponential length: m=2Ω(n). Previously this was known only for linear codes (Goldreich et al. 02). Our proof shows that a 2-query LDC can be decoded with only 1 quantum query, and then proves an exponential lower bound for such 1-query locally quantum-decodable codes. We also show that q quantum queries allow more succinct LDCs than the best known LDCs with q classical queries. Finally, we give new classical lower bounds and quantum upper bounds for the setting of private information retrieval. In particular, we exhibit a quantum 2 server PIR scheme with O(n3/10) qubits of communication, improving upon the O(n1/3) bits of communication of the best known classical 2-server PIR.
We introduce a keyless coding/cryptographic primitive that asks for two guarantees at once: the receiver is never fooled into accepting a message other than the one sent, and the adversary learns nothing about the message unless the receiver aborts. Neither the sender nor the receiver holds a secret key, and no computational hardness is assumed. The only restriction is on the adversary's online computation: the receiver aborts if nothing arrives by a fixed deadline, so the adversary must forward something before it, and her map in that window is computed by a circuit of size (or depth) at most p; before and after, she is unbounded. For every polynomial p we construct such an efficient quantum scheme, encoding k-bit messages into n=O(k) qubits with circuits of size poly(n,p). No classical scheme achieves this type of everlasting security, at any choice of parameters.
Our techniques also resolve open questions about universal tamper detection against families restricted in cardinality rather than in circuit size. We settle a question of Broadbent, Kapshikar and Rochette on relaxed tamper detection. As a corollary, we obtain the first efficient non-malleable code secure against global quantum tampering, with no split-state restriction, whereas the current constructions in the literature require the codeword to be split into non-communicating shares.
A locally decodable code encodes n-bit strings x in m-bit codewords C(x), in such a way that one can recover any bit xi from a corrupted codeword by querying only a few bits of that word. We use a quantum argument to prove that LDCs with 2 classical queries need exponential length: m=2Ω(n). Previously this was known only for linear codes (Goldreich et al. 02). Our proof shows that a 2-query LDC can be decoded with only 1 quantum query, and then proves an exponential lower bound for such 1-query locally quantum-decodable codes. We also show that q quantum queries allow more succinct LDCs than the best known LDCs with q classical queries. Finally, we give new classical lower bounds and quantum upper bounds for the setting of private information retrieval. In particular, we exhibit a quantum 2 server PIR scheme with O(n3/10) qubits of communication, improving upon the O(n1/3) bits of communication of the best known classical 2-server PIR.
We consider a communication problem where sender, say Alice, sends a message to receiver, say Bob, in the presence of an active adversary, James, who tampers Alice's transmission using a function from a known class of tampering functions. The goal is two-fold: First, the decoder should always decode Alice's message correctly in the absence of tampering. Second, when tampering occurs, the decoder should attempt to detect errors and, when that fails, limit the adversary's control over the decoding error outcome. In particular, the decoded message should be statistically independent of Alice's original message, making the coding scheme non-malleable (with respect to tampering). This setup is motivated by scenarios like tampered-proof sealed-bid auctions, where an adversary might attempt to alter the decoded bid to manipulate the outcome. In this work, we focus on binary non-malleable coding with input constraints, which limit the set of possible transmit vectors. We fully characterize the maximum throughput, or non-malleable capacity, for any given tampering family of bounded size (up to doubly-exponential in block length), extending the classic result for unconstrained inputs by Cheragchi and Guruswami (Trans. IT, 2016)
In the bounded-storage model for information-theoretically secure encryption and key-agreement one can prove the security of a cipher based on the sole assumption that the adversary's storage capacity is bounded, say by s bits, even if her computational power is unlimited. Assume that a random t-bit string R is either publicly available (e.g. the signal of a deep space radio source) or broadcast by one of the legitimate parties. If s < t, the adversary can store only partial information about R. The legitimate sender Alice and receiver Bob, sharing a short secret key K initially, can therefore potentially generate a very long n-bit one-time pad X with n jKj about which the adversary has essentially no information, thus at rst glance apparently contradicting Shannon's bound on the key size of a perfect cipher.