Identification and signatures based on NP-hard problems of indefinite quadratic forms

DOI10.1515/JMC.2008.015zbMath1163.11027MaRDI QIDQ3612243

Rupert J. Hartung, Claus Peter Schnorr

Publication date: 3 March 2009

Published in: Journal of Mathematical Cryptology (Search for Journal in Brave)

zbMATH Keywords

quadratic formsidentification protocolsNP-hardnessproof of knowledgeLLL-reduction

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Cryptography (94A60) Quadratic and bilinear Diophantine equations (11D09) General ternary and quaternary quadratic forms; forms of more than two variables (11E20) Class numbers, class groups, discriminants (11R29)

Related Items

An identification system based on the explicit isomorphism problem

Uses Software

• NTRUSign

Cites Work

• Factoring polynomials with rational coefficients
• NP-complete decision problems for binary quadratics
• Small solutions of the Legendre equation
• Lattice basis reduction for indefinite forms and an application
• Public Key Identification Based on the Equivalence of Quadratic Forms
• Hardness of approximating the shortest vector problem in lattices
• An efficient solution of the congruence<tex>x^2 + ky^2 = mpmod{n}</tex>
• Worst-case complexity bounds for algorithms in the theory of integral quadratic forms
• Small Solutions of Quadratic Diophantine Equations
• Solving quadratic equations using reduced unimodular quadratic forms
• Floating-Point LLL Revisited