Witness-Hiding Proofs of Knowledge for Cable Locks
Chen-Da Liu Zhang, Ueli Maurer, Martin Raszyk, and Daniel Tschudi
We consider the general setting where users need to provide a secret code c to a verifying entity V in order to obtain access to a resource. More generally, the right to access the resource could, for example, be granted if one knows one of two codes c1 and c2. For privacy reasons, a party P may want to hide which of the two codes it knows and only prove that it knows at least one of them. For example, if the knowledge of a code corresponds to membership in a certain society, one may want to hide which society one belongs to. In cryptography, such a proof is called a witness-hiding proof of knowledge. How can P prove such a statement to V?
This paper is concerned with witness-hiding proofs of knowledge using simple mechanical tools. Specifically, we consider cable (or bicycle) locks, where the codes of the locks correspond to the secret codes. The above example of proving knowledge of either c1 or c2 in a witness-hiding fashion can be achieved simply as follows. When given the two locks closed and unlinked (by V), P presents the configuration of the two locks interlocked, which can be generated if and only if P knows at least one of the codes.
In the most general case with n codes c1,...,cn, the access right is characterized by a so-called knowledge structure K, a subset of the power set of {1,...,n}. Access is granted if a user knows the codes corresponding to any of the subsets of K. We present lock-based protocols for witness-hiding proofs of knowledge for any such monotone knowledge structure, and investigate the efficiency (i.e., in particular, the number of lock configurations that P must present) in several settings such as the availability of solid rings or the availability of multiple locks for a given code.
The topic of this paper is similar in spirit to other works, such as the picture hanging puzzles by Demaine et al., which explore connections between topology and real-world applications, where the motivation arises also, or even primarily, from mathematical curiosity.
BibTeX Citation
@inproceedings{LMRT17,
author = {Chen-Da Liu Zhang and Ueli Maurer and Martin Raszyk and Daniel Tschudi},
title = {Witness-Hiding Proofs of Knowledge for Cable Locks},
booktitle = {IEEE International Symposium on Information Theory (ISIT)},
pages = 953-957,
year = 2017,
month = 6,
}