Cryptology ePrint Archive: Report 2002/093

A Fuzzy Vault Scheme

Ari Juels and Madhu Sudan

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.

Category / Keywords: cryptographic protocols /

Publication Info: A one page abstract of this paper appeared in _Proceedings of ISIT '02_.

Date: received 14 Jul 2002

Contact author: ajuels at rsasecurity com

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20020715:013631 (All versions of this report)

Short URL: ia.cr/2002/093

Discussion forum: Show discussion | Start new discussion