Cryptography Based on Quadratic Forms: Complexity Considerations

摘要

We study the computational problem Trafo of finding an integral equivalence transform between two given quadratic forms. This is motivated by a recent identification scheme based on this problem [10]. We prove that for indefinite forms over Z, its hardness is concentrated in dimensions 3 and 4. Moreover, over the field of rational numbers the complexity of Trafo is closely related to that of factoring. However, for definite forms over Z, as well as for forms over finite fields, the transformation problem is solvable in polynomial time.