Cryptology ePrint Archive: Report 2015/969

Zero-Knowledge Interactive Proof Systems for New Lattice Problems

Claude Crepéau and Raza Ali Kazmi

Abstract: In this work we introduce a new hard problem in lattices called Isometric Lattice Problem (ILP) and reduce Linear Code Equivalence over prime fields and Graph Isomorphism to this prob- lem. We also show that this problem has an (efficient prover) perfect zero-knowledge interactive proof; this is the only hard problem in lattices that is known to have this property (with respect to malicious verifiers). Under the assumption that the polynomial hierarchy does not collapse, we also show that ILP cannot be NP-complete. We finally introduce a variant of ILP over the rationals radicands and provide similar results for this new problem.

Category / Keywords: foundations / Zero-Knowledge, Interactive Proof Systems, Isometric Latties

Original Publication (in the same form): FIFTEENTH IMA INTERNATIONAL CONFERENCE ON CRYPTOGRAPHY AND CODING. 15th - 17th December 2015, St. Catherine's College, University of Oxford, UK

Date: received 8 Oct 2015

Contact author: raza-ali kazmi at mail mcgill ca

Available format(s): PDF | BibTeX Citation

Version: 20151009:210821 (All versions of this report)

Short URL: ia.cr/2015/969

Discussion forum: Show discussion | Start new discussion