Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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


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.