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

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.


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


Full Text: DOI


[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)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.