Two remarks on the vectorization problem

Wouter Castryck; Natan Vander Meeren

Paper 2022/1366

Two remarks on the vectorization problem

Wouter Castryck

, KU Leuven

Natan Vander Meeren, KU Leuven

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 $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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: vectorization parallelization hidden shift
Contact author(s): wouter castryck @ gmail com
natan vander meeren @ gmail com
History: 2022-10-14: approved; 2022-10-11: received; See all versions
Short URL: https://ia.cr/2022/1366
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1366,
      author = {Wouter Castryck and Natan Vander Meeren},
      title = {Two remarks on the vectorization problem},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1366},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1366}},
      url = {https://eprint.iacr.org/2022/1366}
}