Zero-Knowledge Interactive Proof Systems for New Lattice Problems

Claude Crepéau; Raza Ali Kazmi

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-Knowledge Interactive Proof Systems Isometric Latties
Contact author(s): raza-ali kazmi @ mail mcgill ca
History: 2015-10-09: received
Short URL: https://ia.cr/2015/969
License: CC BY

BibTeX

@misc{cryptoeprint:2015/969,
      author = {Claude Crepéau and Raza Ali Kazmi},
      title = {Zero-Knowledge Interactive Proof Systems for New Lattice Problems},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/969},
      year = {2015},
      url = {https://eprint.iacr.org/2015/969}
}