  Recent results of Kaplan et al., building on previous work by Kuwakado and
Morii, have shown that a wide variety of classically-secure symmetric-key
cryptosystems can be completely broken by quantum chosen-plaintext attacks
(qCPA). In such an attack, the quantum adversary has the ability to query the
cryptographic functionality in superposition. The vulnerable cryptosystems
include the Even-Mansour block cipher, the three-round Feistel network, the
Encrypted-CBC-MAC, and many others. In this work, we study simple algebraic
adaptations of such schemes that replace $(\mathbb Z/2)^n$ addition with
operations over alternate finite groups--such as $\mathbb Z/{2^n}$--and provide
evidence that these adaptations are qCPA-secure. These adaptations furthermore
retain the classical security properties (and basic structural features)
enjoyed by the original schemes.
  We establish security by treating the (quantum) hardness of the well-studied
Hidden Shift problem as a basic cryptographic assumption. We observe that this
problem has a number of attractive features in this cryptographic context,
including random self-reducibility, hardness amplification, and--in many cases
of interest--a reduction from the "search version" to the "decisional version."
We then establish, under this assumption, the qCPA-security of several such
Hidden Shift adaptations of symmetric-key constructions. We show that a Hidden
Shift version of the Even-Mansour block cipher yields a quantum-secure
pseudorandom function, and that a Hidden Shift version of the Encrypted CBC-MAC
yields a collision-resistant hash function. Finally, we observe that such
adaptations frustrate the direct Simon's algorithm-based attacks in more
general circumstances, e.g., Feistel networks and slide attacks.
