## CryptoDB

### Dana Ron

#### Publications

**Year**

**Venue**

**Title**

1999

EPRINT

Chinese Remaindering with Errors
Abstract

The Chinese Remainder Theorem states that a positive integer m is
uniquely specified by its remainder modulo k relatively prime integers
p_1,...,p_k, provided m < \prod_{i=1}^k p_i. Thus the residues of m
modulo relatively prime integers p_1 < p_2 < ... < p_n form a
redundant representation of m if m <= \prod_{i=1}^k p_i and k <
n. This suggests a number-theoretic construction of an
``error-correcting code'' that has been implicitly considered often in
the past. In this paper we provide a new algorithmic tool to go with
this error-correcting code: namely, a polynomial-time algorithm for
error-correction. Specifically, given n residues r_1,...,r_n and an
agreement parameter t, we find a list of all integers m <
\prod_{i=1}^k p_i such that (m mod p_i) = r_i for at least t values of
i in {1,...,n}, provided t = Omega(sqrt{kn (log p_n)/(log p_1)}). We
also give a simpler algorithm to decode from a smaller number of
errors, i.e., when t > n - (n-k)(log p_1)/(log p_1 + \log p_n). In
such a case there is a unique integer which has such agreement with
the sequence of residues.
One consequence of our result is that is a strengthening of the
relationship between average-case complexity of computing the
permanent and its worst-case complexity. Specifically we show that if
a polynomial time algorithm is able to guess the permanent of a random
n x n matrix on 2n-bit integers modulo a random n-bit prime with
inverse polynomial success rate, then #P=BPP. Previous results of
this nature typically worked over a fixed prime moduli or assumed very
small (though non-negligible) error probability (as opposed to small
but non-negligible success probability).

1997

EPRINT

A Probabilistic Error-Correcting Scheme
Abstract

In the course of research in Computational Learning Theory,
we found ourselves in need of an error-correcting encoding scheme for which
few bits in the codeword yield no information about the plain message.
Being unaware of a previous solution,
we came-up with the scheme presented here.
Since this scheme may be of interest to people working in Cryptography,
we thought it may be worthwhile to ``publish'' this part of our work
within the Cryptography community.
Clearly, a scheme as described above cannot be deterministic.
Thus, we introduce a probabilistic coding scheme which,
in addition to the standard coding theoretic requirements,
has the feature that any constant fraction
of the bits in the (randomized) codeword yields no information about
the message being encoded.
This coding scheme is also used to obtain efficient constructions for
the Wire-Tap Channel Problem.

#### Coauthors

- S. Decatur (1)
- Oded Goldreich (2)
- Madhu Sudan (1)