Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
Zero-Knowledge Proof of Generalized Compact Knapsacks (or A Novel Identification/Signature Scheme)
verfasst von : Bo Qin, Qianhong Wu, Willy Susilo, Yi Mu, Yumin Wang
Erschienen in: Autonomic and Trusted Computing
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.