Distribuição de dados

Na teoria da complexidade computacional [en], uma suposição de dificuldade computacional é a hipótese de que um problema específico não pode ser resolvido de forma eficiente (onde eficiência normalmente significa "em tempo polinomial"). Não se sabe como provar a dificuldade (incondicional) para essencialmente qualquer problema útil. Em vez disso, os cientistas da computação contam com reduções para relacionar formalmente a dificuldade de um problema novo ou complicado à uma suposição de dificuldade computacional sobre um problema que é mais bem compreendido.

As suposições de dificuldade computacional são de particular importância na criptografia. Um dos principais objetivos da criptografia é criar primitivas criptográficas [en] com segurança comprovada [en]. Em alguns casos, os protocolos criptográficos apresentam segurança teórica da informação; a chave (ou cifra) de uso único é um exemplo comum. No entanto, a segurança teórica da informação nem sempre pode ser alcançada; nesses casos, os criptógrafos recorrem à segurança computacional. Em termos gerais, isso significa que esses sistemas são seguros assumindo que quaisquer adversários são limitados computacionalmente, como todos os adversários são na prática.

As suposições de dificuldade computacional também são úteis para orientar projetistas de algoritmos: um algoritmo simples provavelmente não refutará uma suposição de dificuldade computacional bem estudada, como P ≠ NP.

Comparando suposições de dificuldade editar

Os cientistas da computação têm diferentes maneiras de avaliar quais suposições de dificuldade são mais confiáveis.

Força das suposições de dificuldade editar

Dizemos que a suposição   é mais forte do que a suposição   quando   implica   (e o inverso é falso ou desconhecido). Em outras palavras, mesmo que a suposição   fosse falsa, a suposição   ainda poderia ser verdadeira, e os protocolos criptográficos baseados na suposição   ainda podem ser seguros para uso. Assim, ao desenvolver protocolos criptográficos, se espera poder provar a segurança usando as suposições mais fracas possíveis.

Suposições de caso médio versus de pior caso editar

Uma suposição de caso médio diz que um problema específico é difícil na maioria das instâncias de alguma distribuição explícita, enquanto uma suposição de pior caso apenas diz que o problema é difícil em algumas instâncias. Para um determinado problema, a dificuldade de caso médio implica a dificuldade de pior caso, portanto, uma suposição de dificuldade de caso médio é mais forte do que uma suposição de dificuldade de pior caso para o mesmo problema. Além disso, mesmo para problemas incomparáveis, uma suposição como a hipótese de tempo exponencial é frequentemente considerada preferível a uma suposição de caso médio como a conjectura de clique oculto [en].[1] Observe, no entanto, que na maioria das aplicações criptográficas, saber que um problema tem alguma instância difícil (ou seja, um problema é difícil no pior caso) é inútil porque não nos fornece uma maneira de gerar instâncias difíceis.[2] Felizmente, muitas suposições de caso médio usadas em criptografia (incluindo RSA, logaritmo discreto e alguns problemas de rede) podem ser baseadas em suposições de pior caso por meio de reduções de pior caso a caso médio.[3]

Falseabilidade editar

Uma característica desejada de uma suposição de dificuldade computacional é a falseabilidade, ou seja, se a suposição fosse falsa, então seria possível a provar. Em particular, Naor (2003) introduziu uma noção formal de falseabilidade criptográfica.[4] Grosso modo, uma suposição de dificuldade computacional é considerada falseável se puder ser formulada em termos de um desafio: um protocolo interativo entre um adversário e um verificador eficiente, onde um adversário eficiente pode convencer o verificador a aceitar se e somente se a suposição for falsa.

Suposições comuns de dificuldade criptográfica editar

Existem muitas suposições de dificuldade criptográfica em uso. Esta é uma lista de algumas das mais comuns e de alguns protocolos criptográficos que os utilizam.

Fatoração de inteiros editar

 Ver artigo principal: Fatoração de inteiros

Dado um número composto  , e em particular aquele que é o produto de dois primos grandes  , o problema de fatoração de inteiros é encontrar   e   (mais geralmente, encontrar primos   de modo que  ). É um grande problema em aberto encontrar um algoritmo para fatoração de inteiros que execute em tempo polinomial no tamanho da representação ( ). A segurança de muitos protocolos criptográficos se baseia na suposição de que a fatoração de inteiros é difícil (ou seja, não pode ser resolvida em tempo polinomial). Os criptosistemas cuja segurança é equivalente a esta suposição incluem o criptosistema Rabin e o criptosistema Okamoto-Uchiyama [en]. Muitos outros criptosistemas dependem de suposições mais fortes, como RSA, problemas de residuosidade e ocultação de Phi.

Problema RSA editar

 Ver artigo principal: Problema RSA

Dado um número composto  , expoente   e número , o problema RSA é encontrar  . O problema é considerado difícil, mas se torna fácil devido à fatoração de  . No criptosistema RSA,   é a chave pública,   é a criptografia da mensagem   e a fatoração de   é a chave secreta usada para descriptografia.

Problemas de residuosidade editar

Dado um número composto   e inteiros  , o problema de residuosidade é determinar se existe (alternativamente, encontre um)   tal que

 

Casos especiais importantes incluem o problema de residuosidade quadrática [en] e o problema de residuosidade composta de decisão [en]. Como no caso do RSA, este problema (e seus casos especiais) são considerados difíceis, mas se tornam fáceis devido à fatoração de . Alguns criptosistemas que dependem da dificuldade dos problemas de residuidade incluem:

  • Criptosistema Goldwasser–Micali [en] (problema de residuosidade quadrática)
  • Gerador Blum Blum Shub (problema de residuosidade quadrática)
  • Criptosistema Paillier [en] (problema de residuosidade composta de decisão)
  • Criptosistema Benaloh [en] (problema de maior residuosidade)
  • Criptosistema Naccache-Stern [en] (problema de maior residuosidade)

Suposição de ocultamento de Phi editar

Para um número composto  , não se sabe como calcular eficientemente sua função totiente de Euler  . A suposição de ocultação de Phi postula que é difícil calcular   e, além disso, mesmo computar quaisquer fatores primos de   é difícil. Essa suposição é usada no protocolo PIR Cachin–Micali–Stadler.[5]

Problema de logaritmo discreto (P.L.D.) editar

 Ver artigo principal: Logaritmo discreto

Dados os elementos   e   de um grupo  , o problema de logaritmo discreto pede um inteiro   tal que  . O problema de logaritmo discreto não é conhecido por ser comparável à fatoração de inteiros, mas suas complexidades computacionais estão intimamente relacionadas.

A maioria dos protocolos criptográficos relacionados ao problema de log discreto, na verdade, dependem da suposição de Diffie–Hellman [en] mais forte: determinados elementos de grupo  , onde   é um gerador e   são inteiros aleatórios, é difícil encontrar  . Exemplos de protocolos que usam essa suposição incluem a troca de chaves de Diffie–Hellman original, bem como a criptografia ElGamal (que depende da variante decisória de Diffie–Hellman [en] (D.D.H.) ainda mais forte).

Mapas multilineares editar

Um mapa multilinear é uma função   (onde   são grupos) tais que para qualquer   e  ,

 

Para aplicações criptográficas, gostaríamos de construir grupos   e um mapa   de modo que o mapa e as operações de grupo em   possam ser calculados de forma eficiente, mas o problema de logaritmo discreto em   ainda é difícil.[6] Algumas aplicações requerem suposições mais fortes, por exemplo, análogos multilineares das suposições de Diffie-Hellman.

Para o caso especial de  , mapas bilineares [en] com segurança confiável foram construídos usando emparelhamento Weil Weil pairing e emparelhamento Tate [en].[7] Para   muitas construções foram propostas nos últimos anos, mas muitas delas também foram quebradas e, atualmente, não há consenso sobre um candidato seguro.[8] Alguns criptosistemas que dependem de suposições de dificuldade multilinear incluem:

  • Esquema Boneh–Franklin [en] (bilinear Diffie–Hellman)
  • Boneh–Lynn–Shacham [en] (bilinear Diffie-Hellman)
  • Garg-Gentry-Halevi-Raykova-Sahai-Waters candidato para ofuscação indistinguível [en] e criptografia funcional [en] (quebra cabeças multilinear)[9]

Problemas de redes diagonais editar

O problema computacional mais fundamental nas redes diagonais é o problema de vetor mais curto [en] (P.V.M.C.): dada uma rede  , encontrar o menor vetor   diferente de zero. A maioria dos criptosistemas requer suposições mais fortes sobre as variantes do problema de vetor mais curto (P.V.M.C.), como o problema de vetores independentes mais curtos [en] (P.V.I.M.C.), o GapSVP [en][10] ou o Unique-SVP.[11]

A suposição de dificuldade de rede mais útil em criptografia é para o problema de aprendizado com erros (A.C.E.): amostras fornecidas para  , onde   para alguma função linear  , é fácil aprender   usando álgebra linear. No problema de aprendizado com erros (A.C.E.), a entrada para o algoritmo tem erros, ou seja, para cada par   com alguma pequena probabilidade. Se acredita que os erros tornam o problema intratável (para parâmetros apropriados); em particular, existem reduções conhecidas de pior caso a caso médio de variantes do problema de vetor mais curto.[12]

​​​Para computadores quânticos, os problemas de fatoração e logaritimo discreto são fáceis, mas os problemas de rede são considerados difíceis.[13] Isso torna alguns criptosistemas baseados em rede candidatos para criptografia pós-quântica.

Alguns criptosistemas que dependem da dificuldade dos problemas de rede incluem:

Suposições de dificuldade que não é criptográfica editar

Assim como suas aplicações criptográficas, as suposições de dificuldade são usadas na teoria da complexidade computacional [en] para fornecer evidências para afirmações matemáticas que são difíceis de provar incondicionalmente. Nessas aplicações, prova-se que a suposição de dificuldade implica alguma afirmação teórica da complexidade desejada, em vez de provar que a afirmação em si é verdadeira. A suposição mais conhecida desse tipo é a suposição de que P ≠ NP,[14] mas outras incluem a hipótese de tempo exponencial,[15] a conjectura clique plantado [en] e a conjectura de jogos únicos.[16]

Problemas difíceis de C editar

Muitos problemas computacionais de pior caso são conhecidos por serem difíceis ou mesmo completos para alguma classe de complexidade  , em particular difícil de NP (mas frequentemente também difícil de PSPACE [en], difícil de PPAD [en], etc.). Isso significa que eles são pelo menos tão difíceis quanto qualquer problema na classe  . Se um problema é  -difícil (com respeito às reduções de tempo polinomial), então não pode ser resolvido por um algoritmo de tempo polinomial, a menos que a suposição de dificuldade computacional   seja falsa.

Hipótese de tempo exponencial (H.T.E.) e variantes editar

 Ver artigo principal: Hipótese do tempo exponencial

A hipótese de tempo exponencial (eth) é um reforço da suposição de dificuldade  , que conjectura que não apenas o problema de satisfatibilidade booleana não tem um algoritmo de tempo polinomial, mas também requer tempo exponencial ( ).[17] Uma suposição ainda mais forte, conhecida como hipótese de tempo exponencial forte (H.T.E.F.) conjectura que SAT de   requer tempo  , onde  . Hipótese de tempo exponencial (H.T.E.), hipótese de tempo exponencial forte (H.T.E.F.) e pressupostos de dificuldade computacional relacionados permitem a dedução de resultados de complexidade refinados, por exemplo, resultados que distinguem o tempo polinomial e o tempo quase polinomial [en],[1] ou mesmo   versus  .[18] Essas suposições também são úteis na complexidade parametrizada.[19]

Suposições de dificuldade de caso médio editar

 Ver artigo principal: Complexidade de caso médio

Alguns problemas computacionais são considerados difíceis em média em uma distribuição particular de instâncias. Por exemplo, no problema do clique plantado [en], a entrada é um grafo aleatório amostrado, amostrando um grafo aleatório Erdős–Rényi e então "plantando" um clique   aleatório, ou seja, conectando nós   uniformemente aleatórios (onde  ), e o objetivo é encontrar o clique   plantado (que é, com alta probabilidade, único).[20] Outro exemplo importante é a hipótese de Feige, que é uma suposição de dificuldade computacional sobre instâncias aleatórias de SAT de 3 (amostradas para manter uma proporção específica de cláusulas para variáveis).[21] As suposições de dificuldade computacional de caso médio são úteis para provar a dificuldade de caso médio em aplicações como estatísticas, onde há uma distribuição natural sobre as entradas.[22] Além disso, a suposição de dificuldade do clique plantado também foi usada para distinguir entre a complexidade de tempo de pior caso polinomial e quase polinomial de outros problemas,[23] de forma semelhante à hipótese de tempo exponencial.

Jogos únicos editar

 Ver artigo principal: Conjectura de jogos únicos

O problema de cobertura de rótulo exclusivo é um problema de satisfação de restrição, onde cada restrição   envolve duas variáveis  , e para cada valor de   há um valor único de   que satisfaz  . Determinar se todas as restrições podem ser satisfeitas é fácil, mas a conjectura de jogos únicos (C.J.U.) postula que determinar se quase todas as restrições (fração  , para qualquer constante  ) podem ser satisfeitas ou quase nenhuma delas (fração  ) podem ser satisfeitas é difícil de NP'.[16] Os problemas de aproximação são frequentemente conhecidos como difíceis de NP assumindo conjectura de jogos únicos (C.J.U.); tais problemas são chamados de difícil de jogos únicos (J.U.). Em particular, assumindo conjectura de jogos únicos (C.J.U.), há um algoritmo de programação semidefinida [en] que atinge garantias de aproximação ótimas para muitos problemas importantes.[24]

Expansão de conjunto pequeno editar

Intimamente relacionado ao problema de cobertura de rótulo único está o problema de expansão de conjunto pequeno (E.C.P.): Dado um gráfico  , encontrar um conjunto pequeno de vértices (de tamanho  ) cuja expansão de borda [en] é mínima. Se sabe que, se a expansão de conjunto pequeno é difícil de estimar, o mesmo ocorre com a cobertura de rótulo único. Consequentemente, a hipótese de expansão de conjunto pequeno, que postula que a expansão de conjunto pequeno é difícil de se aproximar, é uma suposição mais forte (mas intimamente relacionada) do que a conjectura de jogo único.[25] Alguns problemas de aproximação são conhecidos por serem difíceis de expansão de conjunto pequeno (E.C.P.)[26] (ou seja, pelo menos tão difíceis quanto aproximar a expansão de conjunto pequeno).

A conjectura 3SUM editar

Dado um conjunto de   números, o problema 3SUM pergunta se existe um trio de números cuja soma é zero. Há um algoritmo de tempo quadrático para 3SUM, e foi conjecturado que nenhum algoritmo pode resolver 3SUM em "tempo verdadeiramente subquadrático": a conjectura 3SUM é a suposição de dificuldade computacional de que não há algoritmos de tempo   para 3SUM (para qualquer constante  ). Esta conjectura é útil para provar limites inferiores quase quadráticos para vários problemas, principalmente de geometria computacional.[27]

Ver também editar

  • Nível de segurança [en]

Referências

  1. a b Braverman, Mark; Ko, Young Kun; Weinstein, Omri (2015). «Approximating the best Nash equilibrium in  -time breaks the Exponential time hypothesis». Symposium on discrete algorithms (S.O.D.A.) (em inglês). Sociedade para a matemática aplicada e industrial. pp. 970–982. ISBN 978-1-61197-374-7. doi:10.1137/1.9781611973730.66 
  2. J. Katz e Y. Lindell, Introduction to modern cryptography (Chapman and Hall/CRC Cryptography and network security series) (em inglês), Chapman and Hall/CRC, 2007.
  3. Goldwasser, Shafi; Kalai, Yael Tauman (2016). «Cryptographic assumptions: A position paper». Theory of cryptography conference (T.C.C.) 2016 (em inglês). Springer. pp. 505–522. doi:10.1007/978-3-662-49096-9_21  
  4. Naor, Moni (2003). «On cryptographic assumptions and challenges». In: Boneh, Dan. Advances in cryptology – CRYPTO 2003: 23rd annual international cryptology conference, Santa Barbara, California, USA, August 17–21, 2003, Proceedings. Lecture notes in computer science (em inglês). 2729. Berlim: Springer. pp. 96–109. MR 2093188. doi:10.1007/978-3-540-45146-4_6  
  5. Cachin, Christian; Micali, Silvio; Stadler, Markus (1999). «Computationally private information retrieval with polylogarithmic communication». In: Stern, Jacques. Advances in cryptology — EUROCRYPT '99. Col: Lecture notes in computer science (em inglês). 1592. [S.l.]: Springer. pp. 402–414. ISBN 978-3-540-65889-4. doi:10.1007/3-540-48910-X_28 
  6. Boneh, Dan; Silverberg, Alice (2002). «Applications of multilinear forms to cryptography». Cryptology ePrint archive (em inglês) 
  7. Dutta, Ratna; Barua, Rana; Sarkar, Palash (2004). «Pairing-based cryptographic protocols : A survey». Cryptology ePrint archive (em inglês) 
  8. Albrecht, Martin R. «Are graded encoding scheme broken yet?» (em inglês). Consultado em 22 de março de 2018 
  9. Garg, Sanjam; Gentry, Craig; Halevi, Shai; Raykova, Mariana; Sahai, Amit; Waters, Brent (2016). «Candidate indistinguishability obfuscation and functional encryption for all circuits» (PDF). Sociedade de matemática industrial e aplicada (S.I.A.M.). S.I.A.M. journal on computing (em inglês). 45 (3): 882–929. doi:10.1137/14095772X 
  10. Peikert, Chris (2009). «Public-key cryptosystems from the worst-case shortest vector problem: extended abstract». Proceedings on 41st annual A.C.M. symposium on theory of computing (S.T.O.C.) (em inglês). pp. 333–342. doi:10.1145/1536414.1536461 
  11. Ajtai, Miklós; Dwork, Cynthia (1997). «A public-key cryptosystem with worst-case/average-case equivalence». Proceedings on 29th annual A.C.M. Symposium on Theory of Computing (S.T.O.C.) (em inglês). pp. 284–293. doi:10.1145/258533.258604 
  12. Regev, Oded (2010). «The learning with errors problem (invited survey)». Conference on computational complexity (C.C.C.) 2010 (em inglês). pp. 191–204. doi:10.1109/CCC.2010.26 
  13. Peikert, Chris (2016). «A decade of lattice cryptography». Foundations and trends in theoretical computer science (em inglês). 10 (4): 283–424. doi:10.1561/0400000074 
  14. Fortnow, Lance (2009). «The status of the P versus NP problem» (PDF). Communications of the ACM (em inglês). 52 (9): 78–86. doi:10.1145/1562164.1562186. Arquivado do original (PDF) em 24 de fevereiro de 2011 
  15. Woeginger, Gerhard (2003). «Exact algorithms for NP-hard problems: A survey». Combinatorial optimization — Eureka, you shrink! (em inglês). 2570. [S.l.]: Springer-Verlag. pp. 185–207. doi:10.1007/3-540-36478-1_17 
  16. a b Khot, Subhash (2010). «On the Unique games conjecture». Proc. 25th I.E.E.E. conference on Computational complexity (PDF) (em inglês). pp. 99–121. doi:10.1109/CCC.2010.19 
  17. Impagliazzo, Russell; Paturi, Ramamohan (1999). «The complexity of k-SAT». Proc. 14th I.E.E.E. conference on computational complexity (em inglês). pp. 237–240. doi:10.1109/CCC.1999.766282 
  18. Abboud, Amir; Vassilevska-Williams, Virginia; Weimann, Oren (2014). «Consequences of faster alignment of sequences». Automata, languages, and programming - 41st International colloquium, I.C.A.L.P. 2014 (em inglês). pp. 39–51. doi:10.1007/978-3-662-43948-7_4 
  19. Lokshtanov, Daniel; Marx, Daniel; Saurabh, Saket (2011). «Lower bounds based on the Exponential time hypothesis». Bulletin of the E.A.T.C.S. (em inglês). 105: 41–72 
  20. Arora, Sanjeev; Barak, Boaz (2009). Computational complexity: A modern approach (em inglês). [S.l.]: Cambridge University Press. pp. 362–363. ISBN 9780521424264 
  21. Feige, Uriel (2002). «Relations between average case complexity and approximation complexity». Proceedings on 34th annual A.C.M. symposium on theory of computing (S.T.O.C.) (em inglês). pp. 534–543. doi:10.1145/509907.509985 
  22. Berthet, Quentin; Rigollet, Philippe (2013). «Complexity theoretic lower bounds for sparse principal component detection». C.O.L.T. 2013 (em inglês). pp. 1046–1066 
  23. Hazan, Elad; Krauthgamer, Robert (2011). «How hard is it to approximate the best Nash equilibrium?». S.I.A.M. journal on computing (em inglês). 40 (1): 79–91. CiteSeerX 10.1.1.139.7326 . doi:10.1137/090766991 
  24. Raghavendra, Prasad (2008). «Optimal algorithms and inapproximability results for every C.S.P.?». 40th annual A.C.M. symposium on theory of computing (S.T.O.C.) 2008 (em inglês). pp. 245–254. doi:10.1145/1374376.1374414 
  25. Raghavendra, Prasad; Steurer, David (2010). «Graph expansion and the Unique games conjecture». 42nd annual A.C.M. symposium on theory of computing (S.T.O.C.) 2010 (em inglês). pp. 755–764. doi:10.1145/1806689.1806792 
  26. Wu, Yu; Austrin, Per; Pitassi, Toniann; Liu, David (2014). «Inapproximability of Treewidth and related problems». Journal of artificial intelligence research (em inglês). 49: 569–600. doi:10.1613/jair.4030  
  27. Vassilevska Williams, Virginia (2018). «On some fine-grained questions in algorithms and complexity». I.C.M. 2018 (PDF) (em inglês)