CryptoDB
Chinese Remaindering with Errors
| Authors: | |
|---|---|
| Download: | |
| 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). |
BibTeX
@misc{eprint-1999-11324,
title={Chinese Remaindering with Errors},
booktitle={IACR Eprint archive},
keywords={Algorithms, Error correcting codes, List decoding, Number theory, Lattice reduction.},
url={http://eprint.iacr.org/1999/002},
note={Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive. madhu@theory.lcs.mit.edu 10500 received Feb 8th, 1999. Also appears as ECCC TR98-062.},
author={Oded Goldreich and Dana Ron and Madhu Sudan},
year=1999
}