Is there a candidate for a post-quantum one-way group action?

Question

Is there a known family of group actions with a designated element
in the set that is being acted on, where it is known how to efficiently

$\:$ sample (essentially uniformly) from the groups, compute the inverse operations,
$\:$ compute the group operations, and compute the group actions

and there is no known efficient quantum algorithm
for succeeding with non-negligible probability in

$\:$ given as inputs the index of a group action and the result of
$\:$ a sampled group element acting on the designated element,
$\:$ find a group element whose action on the designated element is the second input

?


As far as I am aware, those provide the only known constructions of non-interactive statistically hiding commitments in which knowledge of a trapdoor enables efficient and undetectable equivocation, a property that is useful for zero knowledge protocols and adaptive security.

Any family of one-way group homomorphisms with the first three properties (from the third and fourth lines of this post) can be converted into such a thing by having the domains act on the codomains via $\: \langle a,b\rangle \mapsto h(a)\cdot b \:$, $\:$ with the identity elements as the distinguished elements.

A restricted version of the Pedersen commitment scheme can be obtained as a special case of applying the above conversion to the group exponential homomorphism, whose one-wayness is equivalent to the hardness of the discrete logarithm problem, although that is not hard for quantum algorithms. (See Shor's algorithm and that page's section on discrete logarithm.)

Answer 1

Yes, there is an old proposal for this due to Couveignes, which was independently rediscovered by Rostovtsev and Stolbunov.

In both cases, the set of elliptic curves with some common endomorphism ring $\mathcal O$ is acted on by the ideal class group of $\mathcal O$. The secret key is essentially a description of an isogeny via its kernel ideal, and the action of a group element $[\mathfrak a]$ takes a curve $E$ to the codomain of said isogeny: $$ ([\mathfrak a], E) \longmapsto E/\mathfrak a = E/\bigcap_{\alpha\in\mathfrak a}\ker\alpha \text. $$ There is a nice graph-walking interpretation of this action, which is described (for instance) in Section 14.1 of Luca De Feo's lecture notes. _{^{(They also contain more of the background necessary to understand this construction!)}}

While it is possible to invert the group action by solving an instance of the hidden-shift problem, giving rise to a subexponential quantum attack, the system remains unbroken for reasonably big parameter sizes. A much bigger problem is that these schemes are painfully slow in practice: Even after considerable optimization effort, one computation of the group action still takes minutes.

The performance issue has been tackled by a recent proposal called CSIDH by switching to supersingular elliptic curves, which drastically improves efficiency while keeping essentially the same underlying structure. It is still slow relative to comparable pre-quantum schemes, as well as incomparable post-quantum schemes, but may have a place in a post-quantum world due to its unique features.