Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.