You are looking at a specific version 20151009:210821 of this paper. See the latest version.

Paper 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. FIFTEENTH IMA INTERNATIONAL CONFERENCE ON CRYPTOGRAPHY AND CODING. 15th - 17th December 2015, St. Catherine's College, University of Oxford, UK
Keywords
Zero-KnowledgeInteractive Proof SystemsIsometric Latties
Contact author(s)
raza-ali kazmi @ mail mcgill ca
History
2015-10-09: received
Short URL
https://ia.cr/2015/969
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.