Identification and signatures based on NP-hard problems of indefinite quadratic forms
Rupert J. Hartung, Claus-Peter Schnorr · Journal of Mathematical Cryptology · 2008
Abstract We prove NP -hardness of equivalence and representation problems of quadratic forms under probabilistic reductions, in particular for indefinite, ternary quadratic forms with integer coefficients. We present identifications and signatures based on these hard problems. The bit complexity of signature generation and verification is quadratic using integers of bit length 150.