problema CDH y problema Square-DH

Mayoritaria.

Los dos problemas son en realidad más equivalentes en un modelo de brecha que en un modelo sin brecha.

Square-DH se reduce claramente a CDH de cualquier manera, pero CDH se reduce a dos llamadas a Square-DH (tienes 3, pero puedes usar $ (u-v) ^ 2 $ para hacer que sea 2). Esto está bien si el adversario de Square-DH siempre tiene la razón, pero quizás el adversario solo resuelva el problema de Square-DH con probabilidad $ \ epsilon $. La reducción no sabe si el adversario tuvo éxito, por lo que resuelve CDH con una probabilidad de solo $ \ epsilon ^ 2 $.

Si intentas resolver CDH varias veces, debes ejecutar el adversario Square-DH $ O (2 / \ epsilon) $ veces, y hacer $ O (\ epsilon ^ 2) $ conjeturas, que es algo suelto ... a menos que tenga un oráculo DDH, como en el modelo de brecha. En ese caso, puede filtrar los intentos incorrectos de Square-DH. Sin embargo, la reducción todavía no está perfectamente ajustada. Puede resolver el problema de CDH a tiempo $ t $ Square-DH llamadas con una probabilidad que es el primer pedido $ t ^ 2 \ epsilon ^ 2/2 $ cuando $ t < < 1 / \ epsilon $. Entonces, si su adversario es inexacto y no tiene mucho tiempo, todavía es una reducción suelta, pero si tiene $ \ aproximadamente 1 / \ epsilon $ tiempo, se vuelve más ajustado.

Sí , ha demostrado que estos dos problemas son equivalentes al mostrar las reducciones en ambas direcciones (que es la forma de resolverlos). Por cierto, este resultado es bien conocido, ya que el primer orden es de $ G $.