I am learning Groth-Sahai NIZK proof system for Bilinear groups. While going through the literature, I am getting confused on how the proof system is related to Subspace Decision, SXDH or DLIN assumptions. In the proof system, what I understood is to prove the ownership of solution of a set of equations, e.g. Quadratic/Pairing Product etc. Then how does it relate to various hardness assumptions?
$\begingroup$
$\endgroup$
6
-
2$\begingroup$ They show that violating the zero-knowledge property is at least as hard as $\hspace{1.67 in}$ violating those hardness assumptions. $\:$ $\endgroup$– user991Aug 24, 2014 at 6:19
-
$\begingroup$ My understanding is that being able to distinguish between instances of Subspace Decision, SXDH or DLIN assumptions with non-negligible probability corresponds to be able to distinguish between Hiding and Binding keys. But, what does it get translated to further? $\endgroup$– sherlockAug 24, 2014 at 6:31
-
$\begingroup$ Real executions use Binding keys and the Simulator uses Hiding keys. $\;$ $\endgroup$– user991Aug 24, 2014 at 6:33
-
3$\begingroup$ site.uottawa.ca/~lucia/courses/4105-10/CIRCUITSATisNPhard.pdf $\;$ $\endgroup$– user991Aug 24, 2014 at 6:46
-
2$\begingroup$ Groth-Sahai is more of a "template" that you can implement for different groups and assumptions. DLIN, SXDH and subgroup decision are three example implementations given in the original paper. $\endgroup$– user2552Jul 27, 2015 at 14:54
|
Show 1 more comment