Argumentos para a existência de funções unidirecionais

25

Li em vários artigos que se acredita amplamente na existência de funções de mão única . Alguém pode esclarecer por que esse é o caso? Que argumentos temos para apoiar a existência de funções unidirecionais?

Anônimo
fonte
1
Acho um tanto enganador que muitos trabalhos afirmam que a existência de funções unidirecionais é amplamente acreditada, pois até agora não temos nenhum argumento forte para sua existência. Escrever "a existência de funções unidirecionais é amplamente aceito como uma suposição plausível entre especialistas, consistente com a nossa experiência na prática e com o estado atual do conhecimento" é mais apropriado e imparcial.

Respostas:

22

Aqui está um argumento de que funções unidirecionais devem ser difíceis de inverter. Suponha que exista uma classe de problemas 3-SAT com soluções plantadas difíceis de resolver. Considere o seguinte mapa:

(x,r)s

onde x é qualquer cadeia de bits, r é uma cadeia de bits (você pode usá-los para propagar um gerador de números aleatórios ou pode pedir quantos bits aleatórios precisar) s é um problema k -SAT com x como uma solução plantada, em que o gerador de números aleatórios determina exatamente qual problema k -SAT você escolhe. Para inverter esta função unidirecional, é necessário resolver um problema k -SAT com uma solução plantada.

Este argumento mostra que a inversão de uma função unidirecional é tão difícil quanto resolver problemas de SAT com soluções plantadas. E como o k -SAT é um problema completo do NP, se você puder descobrir como construir instâncias rígidas com soluções plantadas para qualquer problema do NP, poderá plantar soluções nas fórmulas do k -SAT.kkk

Não foi provado que seja possível encontrar uma classe de problemas completos de NP com soluções plantadas que são tão difíceis quanto problemas arbitrários de NP completos (e mesmo que isso seja verdade, será incrivelmente difícil de provar) , mas as pessoas definitivamente sabem como plantar soluções nos problemas -SAT de maneiras que ninguém sabe como resolver no momento.k

ADICIONADO: Agora percebo que essa conexão já foi dada (em mais detalhes) em Abadi, Allender, Broder, Feigenbaum e Hemachandra ; eles apontam que funções unidirecionais podem fornecer instâncias rígidas resolvidas do SAT e vice-versa.

Colocando-o em uma linguagem mais informal, a inexistência de funções de mão única mostra que quebra-cabeças realmente difíceis não podem existir. Se existe um tipo de quebra-cabeça em que alguém pode criar um quebra-cabeça e sua solução algoritmicamente, também existe um algoritmo de tempo polinomial para encontrar uma solução para o quebra-cabeça. Isso parece muito contra-intuitivo para mim. Obviamente, uma lacuna polinomial poderia existir; pode ser que, se criar o quebra-cabeça tenha etapas, resolvê-lo possa levar O ( n 3 ) etapas. No entanto, minha intuição diz que deve haver uma lacuna superpolinomial. nO(n3)

Peter Shor
fonte
1
Não é esse o mesmo argumento que o de Sadeq, no sentido de que ambos dependem de alguns problemas que atualmente ninguém sabe como resolver, apesar de muito esforço?
Tsuyoshi Ito
2
@Sadeq: você pode fornecer ao algoritmo essencialmente todos os bits aleatórios necessários para esse argumento; você realmente não precisa de um PRG e, certamente, não de um criptograficamente forte.
Peter Shor
6
@ Tsuyoshi: Eu acho que gerar casos difíceis de problemas de NP com soluções plantadas é um pouco mais geral do que fatorar ou log discreto; por um lado, não se sabe que esteja no BQP.
Peter Shor
3
@ Tsuyoshi: Eu adoraria ver uma abordagem diferente; infelizmente, eu não tenho um. Mas o que isso significa é que quebra-cabeças realmente difíceis não podem existir; se existe um tipo de quebra-cabeça em que alguém pode criar um quebra-cabeça e sua solução algoritmicamente, também existe um algoritmo de tempo polinomial para resolver o quebra-cabeça. Isso parece muito contra-intuitivo para mim.
Peter Shor
4
@Tsuyoshi: Eu acho que o ponto de Peter é que não existem apenas dois ou três candidatos a OWFs; os candidatos são extremamente abundantes e quase triviais para serem apresentados. Por exemplo, se você observar o trabalho em torno da competição SHA-3 do NIST, parece "fácil" construir OWFs, e as pessoas se preocupam principalmente em projetar OWFs super rápidos que ainda atendem a uma noção muito rigorosa de segurança.
Timothy Chow
13

Darei uma resposta curta: a existência de problemas aparentemente difíceis, como FACTORING ou DISCRETE LOG, fez os teóricos acreditarem que a OWF existe. Em particular, eles tentaram por décadas (desde a década de 1970) encontrar algoritmos eficientes (tempo polinomial probabilístico) para esses problemas, mas nenhuma tentativa foi bem-sucedida. Esse raciocínio é muito semelhante ao motivo pelo qual a maioria dos pesquisadores acredita que P ≠ NP.

MS Dousti
fonte
O que eu não gosto nessa crença é que ambos os problemas estão no BQP; portanto, se eles são realmente computadores unidirecionais e quânticos se tornam práticos, a definição de função unidirecional deve ser alterada (para resistir à polimerização quântica). adversários em vez de aleatoriamente). Você conhece algum candidato para funções unidirecionais fortes nesse sentido? Existem candidatos do tipo de funções unidirecionais fortes que assumem Razborov-Rudich em seu teorema?
Diego de Estrada
1
Resposta à minha primeira pergunta: dx.doi.org/10.1016/j.tcs.2007.03.013
Diego de Estrada
3
Ou seja, não temos nenhum argumento para isso além de que ninguém quebrou esses problemas ainda. Esse é um argumento de uma semana. Na mesma linha, acreditaríamos na dureza de qualquer coisa que ainda não resolvemos. Poderíamos dizer que é amplamente acreditam que factoring não está na , mas eu não vi ninguém reclamando disso. Deve haver alguma outra razão para acreditar amplamente na existência de OWFs. Comparação com P vs NP não é justa. Existem muitos problemas naturais completos de NP equivalentes. DTIME(exp(n1/4))
Anônimo
10
Tem que haver um argumento melhor para o porquê de existirem funções unidirecionais do que conhecemos várias funções que ainda não sabemos como inverter. Vou ver se consigo encontrar um.
quer
1
@Anonymous: re: "amplamente acreditar [sic] que o factoring não está na ", você pode verificar as recentes melhorias na log discreto: eprint.iacr.org/ 2013/400 (seguindo eprint.iacr.org/2013/095 ). DTIME(exp(n1/4))
Joshua Grochow
-5

O argumento de Sasho se apóia no eterno problema de P = NP, para o qual atualmente não existe consenso.

No entanto, se seguirmos a análise de criptografia de C. Shannon do bloco único, desclassificada em 1947, ou seja: não há outro algoritmo de criptografia matematicamente seguro além do bloco único. Seu argumento é baseado na ideia de que, se tivermos uma sequência verdadeiramente aleatória dos números e para alguma sequência criptografar, s 1 , s 2 , s 3 , , s n , criptografamos da seguinte forma:r1,r2,r3,,rns1,s2,s3,,sn

f(ri,si)=risi=ci

Se a sequência for verdadeiramente aleatória, tentaremos calcular e o resultado seria, então, que todas as sequências são equiprováveis.f1(ri,si)

Poderíamos imitar o resultado de Shannon para funções de mão única.

A função é o mapa e a função inversa é o mapa f : Z / N ZZ / N Z × Z / N Z .f:Z/nZ×Z/nZZ/nZf:Z/nZZ/nZ×Z/nZ

O problema é que não sabemos se existem números verdadeiramente aleatórios, pois a pergunta é equivalente ao comentário de Einstein sobre "Deus não joga dados".

No entanto, para todos os fins, um gerador de números aleatórios baseado em um processo físico é considerado aleatório o suficiente pelos especialistas.

Dito isto, no momento em que estamos tentando reverter (ci,ri) , ou seja, os números aleatórios não são mais segredo, a reversão é trivial.

Além disso, essa função unidirecional não possui as boas propriedades da maioria das funções de hash criptograficamente seguras, como resistência à colisão. Além disso, temos a situação que . Isso significa que um mesmo valor s k é dividido em hash para dois valores diferentes. E f ( r i , s i ) = f ( r j , s j ) é comum.f(ri,sk)f(rj,sk)skf(ri,si)=f(rj,sj)

mathersjj1
fonte
5
O resultado de Shannon é sobre segurança teórica da informação (onde o adversário tem poder computacional ilimitado). Não é sobre isso que a pergunta está sendo feita. A pergunta é sobre funções unidirecionais com segurança computacional (onde o adversário é limitado a cálculos em tempo polinomial). Consequentemente, argumentos no estilo Shannon não dizem nada sobre a existência de funções unidirecionais seguras em termos computacionais.
DW
Leia a definição de função unidirecional .
Kaveh
Ker-I Ko define uma função unidirecional em relação ao problema P = NP e isomorfismo polinomial. Mais especificamente, se existirem funções unidirecionais, a conjectura de Cook sobre a completude do NP, ou seja, isomorfismo entre conjuntos completos do NP, não se sustenta. O interesse de colocar as coisas da perspectiva da entropia da informação é mostrar que a classe de isomorfismo de funções matematicamente definíveis é segura (irreversível) apenas se um conjunto aleatório puder ser definido. Não tenho certeza da contribuição de Shannon sobre intratabilidade e o uso da expressão "matematicamente seguro".
precisa saber é o seguinte
2
cstheory não é um fórum de discussão ou um blog pessoal, é um site de perguntas e respostas. Sua postagem não é uma resposta à pergunta sobre as funções unidirecionais (conforme definido no link). Verifique o tour e o centro de ajuda para obter explicações sobre o escopo da história.
Kaveh
-6

Seria tão fácil quanto sugerir, por exemplo, a função Seno?

Como para uma determinada entrada e saída, a entrada pode ser aumentada ou diminuída em 360 graus (ou 2 pi, se você estiver em radianos), é muitos para um, para que você nunca possa ter certeza de qual entrada teve?

Diga-me se eu entendi mal a pergunta.

Aaron Robson
fonte
4
Verifique a definição .
Kaveh #
3
Você está misturando dois conceitos: funções unidirecionais e funções invertíveis. Embora a função Seno seja invertível, não é uma maneira. Em particular, você sempre pode criar uma pré - imagem (com a precisão que desejar), mesmo que não seja a pré - imagem.
MS Dousti 7/11/11
Entendo, obrigado por explicar a distinção.
68568 Aaron Robson #