## CryptoDB

#### Publications

Year
Venue
Title
2008
EPRINT
A successful strategy was identified for any Verifier colluding with any Issuer to distinguish honest Provers issuing DAA signatures. An additional verification equation was introduced for a Prover to detect 'tagged' credentials that may be issued while Join protocol. This verification can be done by the Host and do not affect TPM in any way.
2008
EPRINT
A protocol is introduced to show an upper bound for rank of a square matrix
2008
EPRINT
A protocol is introduced to show $K$ copies of a pattern string are embedded is a host string. Commitments to both strings, and to offsets of copies of the pattern in the host is input of Verifier. Protocol does not leak useful information about strings, and is zero knowledge.
2008
EPRINT
A protocol is introduced to show knowledge of a codeword of Goppa code and Goppa polynomial. Protocol does not disclosure any useful information about the codeword and polynomial coefficients. A related protocol is introduced to show Hamming weight of an error is below a threshold. Protocol does not disclosure codeword and weight of the error. Verifier only uses commitments to codeword components and coefficients while testing validity of statements. Both protocols are honest verifier zero knowledge.
2008
EPRINT
A constant-round interactive argument is introduced to show existence of a Hamiltonian cycle in a directed graph. Graph is represented with a characteristic polynomial, top coefficient of a verification polynomial is tested to fit the cycle, soundness follows from Schwartz-Zippel lemma.
2006
EPRINT
Given the original set $X$ where $|X|=s$, a sketch $P$ is computed from $X$ and made public. From another set $Y$ where $|Y| = s$ and $P$, we can reconstruct $X$ if $|X\cap Y|\ge |s-t|$, where $t<s$ is some threshold. The sketch $P$ is secure if it does not reveal much information about $X$. A few constructions have been proposed, but they cannot handle multi-sets, that is, sets that may contain duplicate elements. We observe that the techniques in the set reconciliation protocol proposed by Minsky et al. (ISIT 2001) can be applied and give a secure sketch that supports multi-sets. If $X$ is a subset of an universe with $n$ elements, the running time of the encoding and decoding algorithms will be polynomial w.r.t. $s$ and $\log n$, and the entropy loss due to the sketch is less than $2t(1+\log n)$.

#### Coauthors

Ee-Chien Chang (1)
Qiming Li (1)
Vitaliy Sharapov (1)