Existe uma família conhecida de ações de grupo com um elemento designado
no conjunto em que está sendo atuado, onde é sabido como
amostra (essencialmente uniformemente) dos grupos, calcula as operações inversas,
calcula as operações do grupo e calcula as ações do grupo
e não existe um algoritmo quântico eficiente conhecido
para obter sucesso com probabilidade não desprezível em
dado como entrada o índice de uma ação de grupo e o resultado de
um elemento de grupo amostrado que atua no elemento designado,
encontra um elemento de grupo cuja ação no elemento designado é a segunda entrada
?
Tanto quanto sei, elas fornecem as únicas construções conhecidas de compromissos estatisticamente não-interativos, nos quais o conhecimento de um alçapão permite equívocos eficientes e indetectáveis, uma propriedade que é útil para protocolos de conhecimento zero e segurança adaptativa.
Qualquer família de homomorfismos de grupo unidirecional com as três primeiras propriedades (da terceira e quarta linhas deste post) pode ser convertida em algo assim, fazendo com que os domínios atuem nos codomains via , com os elementos de identidade como os elementos que se distinguem.
Uma versão restrita do esquema de compromisso de Pedersen pode ser obtida como um caso especial de aplicação da conversão acima ao homomorfismo exponencial do grupo, cuja via de mão única é equivalente à dureza do problema de logaritmo discreto, embora isso não seja difícil para algoritmos quânticos. (Consulte o algoritmo de Shor e a seção dessa página em logaritmo discreto.)