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

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

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!)