Identification and signatures based on NP-hard problems of indefinite quadratic forms. (English) Zbl 1163.11027

Hartung, Rupert J.; Schnorr, Claus-Peter

J. Math. Cryptol. 2, No. 4, 327-341 (2008).

Some problems related to quadratic forms are proved NP-hard under probabilistic reductions. Any bilinear form \(f(X)=\sum_{1\leq i\leq j\leq n}a_{ij}X_iX_j\) with integer coefficients is represented by a symmetric matrix \(A\) such that \(f(X)=X^TAX\). Let us write in this review \(A=A_f\) and \(f=f_A\). two forms \(f,g\) are equivalent if \(A_g=T^TA_fT\) for some \(T\in\text{GL}(n)\), \(T\) with integer entries. In this case, it is written \(g=fT\). A form \(f\) represents an integer \(y\) if there exists an integer vector \(x\) such that \(f(x)=y\) and the representation is primitive if the entries of \(x\) have 1 as gcd.
The computational equivalence problem (CEP) consists in finding \(T\) such that \(g=fT\) given a pair \((f,g)\) of equivalent forms. The computational representation problem (CR) consists in finding a primitive representation \(x\) of an integer \(y\) (i.e. in solving in the integers the equation \(y=f(x)\)) given a form \(f\) and the integer \(y\) provided that such a representation does exist. The decisional bounded representation problem (DBR) is a variant of CR in which a bound \(c\) and the factorization of \(\det A_f\) are given as supplementary input and it is asked to decide the existence of primitive representations bounded by \(c\). The decisional bounded equivalence problem (DBE) is a similar variant of CEP.
It is proved in the paper that the restriction of DBR to indefinite primitive forms and \(n=3\), and the restriction to positive definite forms with \(n\geq 5\), are NP-hard under probabilistic reductions. Also it is proved that the restriction of DBE to indefinite forms in which some bounding conditions are posed on parts of the matrix \(A_f\) is NP-hard under probabilistic reductions.
The hardness of the above problems is used in order to build identification protocols. A prover should convince a verifier that he knows the solution \(T\) of a given instance \(\text{CEP}(f,g)\). The proposed protocol is correct and it is reasonably conjectured that the prover does not disclose the value of \(T\). The protocols involve the calculation of LLL-reductions of quadratic forms.

Reviewer: Guillermo Morales-Luna (Mexico)

MSC:

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

Keywords:

identification protocols; proof of knowledge; quadratic forms; NP-hardness; LLL-reduction

Software:

NTRUSign

References:

[1]	Ajtai M., Proceedings STOC pp 284– (1997)
[2]	DOI: 10.1006/jnth.1998.2221 · Zbl 0908.11012
[3]	DOI: 10.1112/S0024611502013898 · Zbl 1036.11009
[4]	DOI: 10.1007/BFb0052231
[5]	DOI: 10.1007/978-3-540-74456-6_31 · Zbl 1147.94316
[6]	DOI: 10.1007/3-540-36563-X_9
[7]	DOI: 10.1007/BFb0054868
[8]	DOI: 10.1016/0012-365X(95)00135-J · Zbl 0848.68041
[9]	DOI: 10.1007/BF01457454 · Zbl 0488.12001
[10]	DOI: 10.1145/1089023.1089027 · Zbl 1323.68301
[11]	DOI: 10.1016/0196-6774(80)90021-8 · Zbl 0473.68030
[12]	DOI: 10.1016/0022-0000(78)90044-2 · Zbl 0369.68030
[13]	Meyer A., Journal für Mathematik 108 pp 125– (1891)
[14]	DOI: 10.1007/11426639_13 · Zbl 1137.94353
[15]	DOI: 10.2307/2008059
[16]	DOI: 10.2307/2008059
[17]	DOI: 10.1109/TIT.1987.1057350 · Zbl 0636.94008
[18]	DOI: 10.1090/S0025-5718-05-01729-1 · Zbl 1078.11072
[19]	Zhuravlev V. G., St. Petersburg Mathematical Journal 8 pp 15– (1997)