Permutações unidirecionais sem alçapão

9

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ππ={πn}nNπnDn{tn}nNIn|tn|poly(n)I posso inverter desde que seja dado .πntn

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 :πD{0,1}D1nDn=0,1nDAc>0n

Pr[xD(1n):A(π(x))=x]<nc

(A probabilidade é assumida sobre os lançamentos internos de moeda de D e A .)

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 :πD A={An}nNc>0n

Pr[xD(1n):An(π(x))=x]<nc

(A probabilidade é assumida sobre os lançamentos internos de moeda de , já que é determinístico.)DA

MS Dousti
fonte
Parece que você deseja um OWP que permaneça unidirecional, mesmo quando recebe uma quantidade polinomial de conselhos. A propósito, geralmente não definimos famílias de OWPs assim - veja Goldreich Vol 1, defs 2.4.4 e 2.4.5.
David Cash
@ David: Sim, eu sei que não é a definição usual, mas senti que a definição formal (a que aparece no livro de Goldreich) é muito longa para esta discussão.
MS Dousti
@Sadeq: Justo, mas acho que a mudança nas definições será significativa aqui. Pelo que vale, tentei pensar em um tipo de segurança semelhante (sem alçapões) antes. Parecia que uma boa definição seria permitir que o processamento ilimitado do índice da família produzisse conselhos antes do experimento de inversão.
David Caixa
@ David: veja se a parte editada satisfaz a necessidade de mais formalização.
MS Dousti
11
@Sadeq: determinar se as permutações unidirecionais de alçapão são implícitas por permutações unidirecionais ou não (embora ainda não esteja claro o que este último significa, pois ambos poderiam existir) é um dos maiores problemas em aberto na teoria da criptografia . Impagliazzo e Rudich ( cseweb.ucsd.edu/~russell/secret.ps ) provaram que isso não pode ser alcançado usando técnicas de caixa preta, e as técnicas atuais não são conhecidas por contornar a separação.
Alon Rosen

Respostas:

7

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

Alon Rosen
fonte
+1, obrigado. David se esforçou muito em responder e sou muito grato a ele; mas esta é a resposta para o que eu tinha em mente.
MS Dousti
2
Eu pensei que a pergunta era: é (a) possível. Criptograficamente, se todo OWP tiver um alçapão, não será possível confiar em alguém que lhe oferece um OWP para não conhecer o alçapão. Obviamente, você pode pegar o OWP dele e compor com seu próprio OWP, para o qual apenas você conhece o alçapão, e obter um OWP para o qual nenhuma parte conhece o alçapão.
quer
11
@ Peter: Sim. Composição parece fazer o trabalho. Outra opção é usar a transferência inconsciente (que, se (a) é válida, é conhecida por existir - modulo algumas pequenas sutilezas). Usando o OT, os jogadores podem construir um protocolo de computação seguro de duas partes que permite que um deles aprenda f sem aprender o alçapão e o outro não aprenda nada. Mas sua solução é realmente mais simples.
Alon Rosen
7

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!)pgpπ(x)=gxmodpπ1p1

David Cash
fonte
+1. Obrigado pela resposta. Você está assumindo a dureza do registro discreto contra adversários não uniformes. Minha pergunta é: Supondo a mera existência de permutações de mão única, podemos construir uma que não tenha alçapão?
MS Dousti
@Sadeq: A existência de permutações unidirecionais não implica a dureza do log discreto desde P = NP?
Mohammad Alaggan
@Alaggan: Acho que não. Pode ser que exista permutações unidirecionais, mas alguém cria um algoritmo eficiente para inverter o log discreto.
MS Dousti
@Sadeq: Isso é se P = BQP! = NP.
Mohammad Alaggan
@Sadeq: Certo ou eu entendi errado?
Mohammad Alaggan