| Computational Diffie-hellman Assumption |
Article Index for Computational |
Website Links For Computational |
Information AboutComputational Diffie-hellman Assumption |
| CATEGORIES ABOUT COMPUTATIONAL DIFFIE-HELLMAN ASSUMPTION | |
| asymmetric-key cryptosystems | |
|
Consider a cyclic group of order . The CDH assumption states that, given : for a randomly-chosen generator and random :, it is Computationally Intractable to compute the value :. The security of many Cryptosystem s is based on the CDH assumption, including notably the Diffie-Hellman key agreement scheme. Also, the confidentiality of ElGamal Encryption is equivalent to the CDH assumption (though the Semantic Security of the scheme is based on the Decisional Diffie-Hellman Assumption ). The CDH assumption is related to the Discrete Logarithm Assumption , which holds that computing the Discrete Logarithm of a value base a generator is hard. If taking discrete logs in were easy, then the CDH assumption would be false: given :, one could efficiently compute in the following way:
It is an open problem to determine whether the discrete log assumption is equivalent to CDH, though in certain special cases this can be shown to be the case. The CDH assumption is also related to the Decisional Diffie-Hellman Assumption (DDH), which holds that it is hard to distinguish tuples of the form from random tuples. If computing from were easy, then one could detect DDH tuples trivially. It is believed that CDH is a weaker assumption than DDH: there are groups for which detecting DDH tuples is easy, but solving CDH problems is believed to be hard. SEE ALSO REFERENCES #Variations of the Diffie-Hellman Problem ( pdf file ) #Towards the Equivalence of Breaking the Diffie-Hellman Protocol and Computing Discrete Logarithms ( pdf file ) |
|
|