IACR News item: 14 October 2022
Wouter Castryck, Natan Vander Meeren
ePrint Report
We share two small but general observations on the vectorization problem for group actions, which appear to have been missed by the existing literature. The first observation is pre-quantum: explicit examples show that, for classical adversaries, the vectorization problem cannot in general be reduced to the parallelization problem. The second observation is post-quantum: by combining a method for solving systems of linear disequations due to Ivanyos with a Kuperberg-style sieve, one can solve the hidden shift problem, and therefore the vectorization problem, for any finite abelian $2^tp^k$-torsion group in polynomial time and using mostly classical work; here $t, k$ are any fixed non-negative integers and $p$ is any fixed prime number.
Additional news items may be found on the IACR news page.