(2026-03) Post-Quantum Anonymous Signatures from the Lattice Isomorphism Group Action
2026-03-03
Post-quantum assumptions may not rely on the difficulty of finding secret subgroups as many classical schemes did. Instead, several assumptions make use of more general group actions, with the belief that quantum algorithms are not helpful in this less structured setting. Famously, some isogeny constructions use the action of an ideal class group on elliptic curves, but equivalence problems in error-correcting codes and lattices also exhibit such structures.
Previous works hence presented anonymity-preserving constructions in a generic group action framework; however, they were not general enough to encompass the group action underlying the Lattice Isomorphism Problem (LIP), for which the acting group is infinite (in fact, not even compact) and non-commutative.
We bridge this gap by, from zero-knowledge proofs of OR statements, building generic blind signature and strong designated-verifier signature with non-delegability constructions from standard assumptions corresponding to a generalised group action inverse problem.