Zero-Knowledge Interactive Proof Systems for New Lattice Problems

Autor:	Raza Ali Kazmi, Claude Crépeau
Rok vydání:	2015
Předmět:	Discrete mathematics Algebra Polynomial hierarchy Rational number Lattice problem Lattice (order) Zero-knowledge proof Graph isomorphism Gas meter prover Linear code Mathematics
Zdroj:	Cryptography and Coding ISBN: 9783319272382 IMA Int. Conf.
DOI:	10.1007/978-3-319-27239-9_9
Popis:	In this work we introduce a new hard problem in lattices called Isometric Lattice ProblemILP and reduce Linear Code Equivalence over prime fields and Graph Isomorphism to this problem. 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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::c7ff9c7a2c751c02f4c3aed3b7142066 https://doi.org/10.1007/978-3-319-27239-9_9 Zobrazit plný text záznamu