## CryptoDB

### Madhu Sudan

#### Publications

**Year**

**Venue**

**Title**

2002

EPRINT

A Fuzzy Vault Scheme
Abstract

We describe a simple and novel cryptographic construction that we
refer to as a {\em fuzzy vault}. A player Alice may place a secret value $\kappa$ in a fuzzy vault and ``lock'' it using a set $A$ of elements from some public universe $U$. If Bob tries to ``unlock'' the vault using a set $B$ of similar length, he obtains $\kappa$ only if $B$ is close to $A$, i.e., only if $A$ and $B$ overlap substantially. In constrast to previous constructions of this flavor, ours possesses the useful feature of {\em order invariance}, meaning that the ordering of $A$ and $B$ is immaterial to the functioning of the vault. As we show, our scheme enjoys provable security against a computationally unbounded attacker.

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).

#### Coauthors

- Ran Canetti (1)
- Oded Goldreich (1)
- Ari Juels (1)
- Silvio Micali (1)
- Chris Peikert (1)
- Ronald L. Rivest (1)
- Dana Ron (1)
- Luca Trevisan (1)
- Salil P. Vadhan (1)
- Hoeteck Wee (1)
- David A. Wilson (1)