| Home > Publications > Reports > Informatics (CW) |
CW 470
Liesje Demuynck and Bart De Decker
How to prove list membership in logarithmic time
Abstract
In this paper we propose a novel technique for proving in zero-knowledge that a committed value is on a public list. Our technique combines the concept of a hashtree with well-known zero-knowledge proofs of knowledge. The resulting proof protocol has a time complexity logarithmic in the size of the list. Its soundness property is guaranteed under the discrete logarithm assumption, while the prover's secret information is protected even in the face of a computational unbounded adversary. Applications of our technique can be found in membership revocation for group signature schemes, anonymous credential systems and identity escrow schemes.
report.pdf (206K) / mailto: L. Demuynck