Public Key Identification Based on the Equivalence of Quadratic Forms
Public Key Identification Based on the Equivalence of Quadratic Forms
复制标题
基于二次形式等价性的公钥识别
DOI：
10.1007/978-3-540-74456-6_31
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
C. Schnorr
中科院分区：
文献类型：
--
作者：
R. Hartung;C. Schnorr
在随机约简下，证明了二次型的计算等价问题是NP-难的，特别是对于不定的、具有整数系数的三元二次型。这一结果取决于科恩-列斯特拉关于类号的启发式的一个变体。我们的识别方案证明了等价变换的知识。
The computational equivalence problem for quadratic forms is shown to be NP-hard under randomized reductions, in particular for indefinite, ternary quadratic forms with integer coefficients. This result is conditional on a variant of the Cohen-Lenstra heuristics on class numbers. Our identification scheme proves knowledge of an equivalence transform.