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

Authors

Bo Qin, University of Wollongong
Qianhong Wu, University of WollongongFollow
Willy Susilo, University of WollongongFollow
Yi Mu, University of WollongongFollow
Yumin Wang, Xidian University

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.