Diffie–Hellman problem (original) (raw)
The Diffie–Hellman problem (DHP) is a mathematical problem first proposed by Whitfield Diffie and Martin Hellman in the context of cryptography. The motivation for this problem is that many security systems use one-way functions: mathematical operations that are fast to compute, but hard to reverse. For example, they enable encrypting a message, but reversing the encryption is difficult. If solving the DHP were easy, these systems would be easily broken.
| Property | Value |
|---|---|
| dbo:abstract | The Diffie–Hellman problem (DHP) is a mathematical problem first proposed by Whitfield Diffie and Martin Hellman in the context of cryptography. The motivation for this problem is that many security systems use one-way functions: mathematical operations that are fast to compute, but hard to reverse. For example, they enable encrypting a message, but reversing the encryption is difficult. If solving the DHP were easy, these systems would be easily broken. (en) Le problème de Diffie-Hellman (abrégé DHP de l'anglais Diffie-Hellman problem) est un problème mathématique évoqué en premier par Whitfield Diffie et Martin Hellman en cryptologie. Le leitmotiv de ce problème est le fait que beaucoup de systèmes de sécurité utilisent des opérations mathématiques rapides à calculer, mais très difficiles, voire impossibles à l'échelle humaine, à inverser. Par exemple il est facile de calculer le hash d'un message avec les fonctions mathématiques de hachage, mais très difficile de revenir au message originel. Si la résolution du problème de Diffie-Hellman était facile, ces systèmes seraient faciles à corrompre. (fr) Na criptografia, para certos grupos, presume-se que o DHP é difícil, e isso é frequentemente chamado de suposição de Diffie-Hellman. O problema sobreviveu ao escrutínio por algumas décadas e nenhuma solução "fácil" foi divulgada ainda. A partir de 2006, o meio mais eficiente conhecido para resolver o DHP é resolver o problema do logaritmo discreto (DLP), que é encontrar x dados ge gx. Na verdade, um progresso significativo (por den Boer, Maurer, Wolf, Boneh e Lipton) foi feito no sentido de mostrar que em muitos grupos o DHP é quase tão difícil quanto o DLP. Não há prova até o momento de que o DHP ou o DLP sejam um problema difícil, exceto em grupos genéricos (por Nechaev e Shoup). Uma prova de que qualquer um dos problemas é difícil implica que P ≠ NP. (pt) |
| dbo:wikiPageExternalLink | http://eprint.iacr.org/2004/306 https://archive.org/details/3rdacmconference00asso https://archive.org/details/3rdacmconference00asso/page/31 https://www.di.ens.fr/~bresson/papers/BreChePoi02b.pdf |
| dbo:wikiPageID | 3237741 (xsd:integer) |
| dbo:wikiPageLength | 7339 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1101881731 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Multiplicative_group dbr:Ueli_Maurer_(cryptographer) dbr:Decisional_Diffie–Hellman_assumption dbr:Cryptography dbr:One-way_functions dbr:Elliptic_curve dbr:Generating_set_of_a_group dbc:Computational_hardness_assumptions dbr:Computational_Diffie–Hellman_assumption dbr:Pairing dbr:Whitfield_Diffie dbr:Lecture_Notes_in_Computer_Science dbr:Dan_Boneh dbr:Finite_field dbr:Diffie–Hellman_key_exchange dbr:Group_(mathematics) dbr:EUROCRYPT dbc:Finite_fields dbr:ElGamal_encryption dbr:Martin_Hellman dbr:Richard_J._Lipton dbr:Discrete_logarithm_problem dbr:CRYPTO |
| dbp:wikiPageUsesTemplate | dbt:Citation_style dbt:Cite_book dbt:Cite_journal dbt:Multiple_issues dbt:No_footnotes dbt:Refbegin dbt:Refend dbt:Computational_hardness_assumptions |
| dct:subject | dbc:Computational_hardness_assumptions dbc:Finite_fields |
| gold:hypernym | dbr:Problem |
| rdf:type | yago:WikicatAsymmetric-keyAlgorithms yago:WikicatComputationalHardnessAssumptions yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Communication100033020 yago:Event100029378 yago:Message106598915 yago:Postulate106753299 yago:Premise106753800 yago:Procedure101023820 yago:Proposition106750804 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity dbo:Disease yago:Rule105846932 yago:Statement106722453 |
| rdfs:comment | The Diffie–Hellman problem (DHP) is a mathematical problem first proposed by Whitfield Diffie and Martin Hellman in the context of cryptography. The motivation for this problem is that many security systems use one-way functions: mathematical operations that are fast to compute, but hard to reverse. For example, they enable encrypting a message, but reversing the encryption is difficult. If solving the DHP were easy, these systems would be easily broken. (en) Le problème de Diffie-Hellman (abrégé DHP de l'anglais Diffie-Hellman problem) est un problème mathématique évoqué en premier par Whitfield Diffie et Martin Hellman en cryptologie. Le leitmotiv de ce problème est le fait que beaucoup de systèmes de sécurité utilisent des opérations mathématiques rapides à calculer, mais très difficiles, voire impossibles à l'échelle humaine, à inverser. Par exemple il est facile de calculer le hash d'un message avec les fonctions mathématiques de hachage, mais très difficile de revenir au message originel. Si la résolution du problème de Diffie-Hellman était facile, ces systèmes seraient faciles à corrompre. (fr) Na criptografia, para certos grupos, presume-se que o DHP é difícil, e isso é frequentemente chamado de suposição de Diffie-Hellman. O problema sobreviveu ao escrutínio por algumas décadas e nenhuma solução "fácil" foi divulgada ainda. (pt) |
| rdfs:label | Diffie-Hellman-Problem (de) Diffie–Hellman problem (en) Problème de Diffie-Hellman (fr) Problema Diffie–Hellman (pt) |
| owl:sameAs | freebase:Diffie–Hellman problem wikidata:Diffie–Hellman problem dbpedia-de:Diffie–Hellman problem dbpedia-fa:Diffie–Hellman problem dbpedia-fr:Diffie–Hellman problem dbpedia-pt:Diffie–Hellman problem dbpedia-th:Diffie–Hellman problem https://global.dbpedia.org/id/4itrS |
| prov:wasDerivedFrom | wikipedia-en:Diffie–Hellman_problem?oldid=1101881731&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Diffie–Hellman_problem |
| is dbo:wikiPageRedirects of | dbr:Diffie-Hellman_problem dbr:Decision_Diffie–Hellman_problem dbr:Computational_Diffie-Hellman_problem dbr:Computational_Diffie–Hellman_problem dbr:Diffie-Hellman_assumption dbr:Diffie-Hellman_protocol dbr:Diffie-hellman_protocol dbr:Diffie_Hellman_problem |
| is dbo:wikiPageWikiLink of | dbr:XTR dbr:Algebraic_Eraser dbr:Decisional_Diffie–Hellman_assumption dbr:Index_of_cryptography_articles dbr:Proth_prime dbr:Elliptic-curve_Diffie–Hellman dbr:Computational_Diffie–Hellman_assumption dbr:DHP dbr:Lattice-based_cryptography dbr:Evi_Nemeth dbr:Diffie–Hellman_key_exchange dbr:Cheon,_Jung_Hee dbr:Integrated_Encryption_Scheme dbr:Diffie-Hellman_problem dbr:Naor–Reingold_pseudorandom_function dbr:Secure_channel dbr:Pairing-based_cryptography dbr:Decision_Diffie–Hellman_problem dbr:Computational_Diffie-Hellman_problem dbr:Computational_Diffie–Hellman_problem dbr:Diffie-Hellman_assumption dbr:Diffie-Hellman_protocol dbr:Diffie-hellman_protocol dbr:Diffie_Hellman_problem |
| is foaf:primaryTopic of | wikipedia-en:Diffie–Hellman_problem |