On the Spinor Genus and the Distinguishing Lattice Isomorphism Problem

Cong Ling; Jingbo Liu; Andrew Mendelsohn

Paper 2024/1475

On the Spinor Genus and the Distinguishing Lattice Isomorphism Problem

Cong Ling, Imperial College London

Jingbo Liu, Texas A&M University – San Antonio

Andrew Mendelsohn, Imperial College London

Abstract

This paper addresses the spinor genus, a previously unrecognized classification of quadratic forms in the context of cryptography, related to the lattice isomorphism problem (LIP). The spinor genus lies between the genus and equivalence class, thus refining the concept of genus. We present algorithms to determine whether two quadratic forms belong to the same spinor genus. If they do not, it provides a negative answer to the distinguishing variant of LIP. However, these algorithms have very high complexity, and we show that the proportion of genera splitting into multiple spinor genera is vanishing (assuming rank ). For the special case of anisotropic integral binary forms () over number fields with class number 1, we offer an efficient quantum algorithm to test if two forms lie in the same spinor genus. Our algorithm does not apply to the HAWK protocol, which uses integral binary Hermitian forms over number fields with class number greater than 1.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published by the IACR in ASIACRYPT 2024
Keywords: quadratic forms lattice isomorphism problem spinor genus class group
Contact author(s): c ling @ imperial ac uk
jliu @ tamusa edu
am3518 @ ic ac uk
History: 2024-09-21: approved; 2024-09-20: received; See all versions
Short URL: https://ia.cr/2024/1475
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1475,
      author = {Cong Ling and Jingbo Liu and Andrew Mendelsohn},
      title = {On the Spinor Genus and the Distinguishing Lattice Isomorphism Problem},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1475},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1475}
}