Resumindo: supondo que existam permutações de mão única , podemos construir uma que não tenha alçapão?
Mais informações:
Uma permutação unidirecional é uma permutação fácil de calcular, mas difícil de inverter (consulte o wiki da tag de função unidirecional para obter uma definição mais formal). Geralmente, consideramos famílias de permutação unidirecional, , em que cada é uma permutação unidirecional, atuando em um domínio finito . Uma permutação unidirecional de alçapão é definida como acima, exceto que existe um conjunto de alçapões e um algoritmo de inversão de politempo , de modo que para todos os , eπ = { π n } n ∈ N π n D n { t n } n ∈ N I n | t n | ≤ p o l y ( n ) I π n t n posso inverter desde que seja dado .
Conheço permutações unidirecionais que são geradas para que seja inviável encontrar o alçapão (ainda que o alçapão exista). Um exemplo, baseado na suposição de RSA, é dado aqui . A questão é,
Existem (famílias de) permutações de mão única que não possuem um alçapão (conjunto)?
Edit: (Mais formalização)
Suponha que exista alguma permutação unidirecional com o domínio (infinito) . Ou seja, existe um algoritmo probabilístico de tempo polinomial (que, na entrada , induz alguma distribuição sobre ), tal que para qualquer adversário em tempo polinomial , qualquer e todo número suficientemente grande :
(A probabilidade é assumida sobre os lançamentos internos de moeda de e .)
A questão é se podemos construir uma permutação unidirecional , para a qual existe um algoritmo probabilístico de tempo polinomial tal que, para qualquer família de circuitos de tamanho poligonal , qualquer e todo número suficientemente grande :
(A probabilidade é assumida sobre os lançamentos internos de moeda de , já que é determinístico.)
fonte
Respostas:
Considere os seguintes casos:
1) As permutações de mão única (OWP) existem, mas as permutações de alçapão (TDP) não existem (ou seja, estamos em uma variante do mundo " minicrip " de Impagliazzo ). Nesse caso, você apenas pega o OWP que é garantido que existe e você sabe que ele não tem um alçapão.
2) OWP e TDP existem. Aqui você tem duas opções:
(a) Todo OWP possui um algoritmo de geração de chave G que gera a descrição "pública" da função f junto com um alçapão amostrado t. Nesse caso, considere uma geração de chaves modificada que gera apenas f. Isso fornece um OWP e, além disso, é inviável encontrar t dado f (caso contrário, você tem uma maneira eficiente de inverter f). Isso também deve valer para uma variante não uniforme.
(b) Existe um OWP f tal que nenhum algoritmo G possa gerar f e t, de modo que t permita a inversão de f (x) para um x aleatório. Nesse caso, f é um OWP que não possui um alçapão.
Um dos comentários no segmento acima parece sugerir que você questiona se realmente a existência de OWP implica a existência de TDP. Isso foi mostrado para não conter construções / reduções de caixa preta erradas e é aberto em geral (veja meu comentário no tópico acima).
fonte
Não conheço construções a partir de suposições gerais, mas você pode obter um candidato plausível para uma "permutação unidirecional sem um alçapão", usando o módulo de log discreto a prime . Ou seja, seja um módulo raiz primitivo e defina . Então é uma permutação sobre os números inteiros entre e , e é geralmente aceite que é unidireccional. Para a parte "no trapdoor", suponho que você precise definir exatamente o que isso significa, mas até onde eu sei, não temos como configurar as coisas para permitir a inversão. (Se o fizéssemos, haveria todo tipo de aplicativos interessantes (positivos) em criptografia!)p g p π(x)=gxmodp π 1 p−1
fonte