Two remarks on the vectorization problem

W Castryck, N Vander Meeren - International Conference on Cryptology in …, 2022 - Springer
International Conference on Cryptology in India, 2022Springer
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 …
Abstract
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 -torsion group in polynomial time and predominantly relying on classical work; here tk are any fixed non-negative integers and p is any fixed prime number.
Springer
Showing the best result for this search. See all results