Paper 2016/737

Zero Knowledge Authentication Protocols With Algebraic Geometry Techniques

Edgar González, Guillermo Morales-Luna, and Feliú D. Sagols

Abstract

Several cryptographic methods have been developed based on the difficulty to determine the set of solutions of a polynomial system over a given field. We build a polynomial ideal whose algebraic set is related to the set of isomorphisms between two graphs. The problem {\sc isomorphism}, posed in the context of Graph Theory, has been extensively used in zero knowledge authentication protocols. Thus, any cryptographic method based on {\sc isomorphism} can be translated into an equivalent method based on the problem of finding rational points in algebraic sets associated to polynomial ideals.