Title

Zero-knowledge proof of generalized compact knapsacks (or a novel identification/signature scheme)

RIS ID

15721

Publication Details

Qin, B., Wu, Q., Susilo, W., Mu, Y. & Wang, Y. (2006). Zero-knowledge proof of generalized compact knapsacks (or a novel identification/signature scheme). In L. Yang, H. Jin, J. Ma & T. Ungerer (Eds.), International Conference on Autonomic and Trusted Computing (pp. 531-540). Germany: Springer-Verlag.

Abstract

At FOCS 2002, a new generalized compact Knapsacks problem is introduced. It is shown that solving the generalized compact Knapsack problem on the average is at least as hard as the worst-case instance of various approximation problems over cyclic lattices. It is left as an open problem to construct a zero-knowledge proof of generalized compact Knapsack problem. In this paper, by investigating a new notion of one-way ensemble pair, we propose a generic construction of identification and achieve a signature with the Fiat-Shamir transformation. Following our generic construction, we implement a concrete scheme based on the random generalized compact Knapsack problem. Our scheme also implies the first efficient zero-knowledge proof of the generalized compact Knapsacks problem and results in a positive solution to the open problem at FOCS 2002.

Please refer to publisher version or contact your library.

Share

COinS
 

Link to publisher version (DOI)

http://dx.doi.org/10.1007/11839569_52