0
$\begingroup$

In the Groth-Sahai proof system, the authors mention (section 1.2) that one of the reasons behind the inefficiency of previous NIZK proof systems is their reliance on the hidden-bits model. Then, they state that other previous work avoided this by using bilinear pairings (but still used a reduction to CSAT, which is not the focus of their proposal.) Thus, I understand that, in their system, they follow the bilinear pairing approach to avoid the inefficiency stemming from the hidden-bits model.

Then, in the description of their framework (section 5), they use a Common Reference String (CRS) that includes some carefully chosen group elements and mappings. Among these mappings, there is $\iota_1,p_1,\iota_2,p_2,\iota_t,p_t$, where the $\iota$'s allow moving from the "witness domain" to the "commitment domain" and the $p$'s the other way around. The security of their proposal relies on the hardness of applying the $p$ mappings without an appropriate trapdoor.

Now, my doubt is: How is this avoiding the hidden-bits model? I mean, there is a predefined CRS with public information, which is later used by a prover to "hide" information from a verifier, since the verifier cannot apply the inverse mappings (the $p$'s). Which is precisely the hidden-bits model if I'm not mistaken.

Is it just that, with the statement in section 1.2, they rather meant that they create an "efficient version" of the hidden-bits model? Have I just got something messed up?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

The hidden bits model is an abstraction of the CRS where the prover is able to reveal some random bits and not others (and where these are guaranteed to be uniformly distributed). The Groth-Sahai approach indeed uses a trapdoor in the CRS but its not the same as the hidden bits approach since the trapdoor is used in a different way (in the hidden bits model the trapdoors are the preimages of each block which enable revealing the bits).

Improve this answer
$\endgroup$
2
  • $\begingroup$ I see. So, the inefficiency of the hidden-bits model is due to this need of revealing the chosen bits and the associated process (I'm following Proof of Theorem 1 in Katz's lecture notes, based on your response). In Groth-Sahai, there is no need to reveal these bits, and the trapdoor is used for simulation purposes (I'm almost guessing here, but that is another question...) Thanks, Professor! $\endgroup$
    – Ginswich
    Commented May 30, 2018 at 15:13
  • 1
    $\begingroup$ The efficiency and inefficiency is an orthogonal issue. I explained why its not the hidden bits model, since the trapdoor is used in a different way. Regarding inefficiency, indeed, the hidden bits model is extremely inefficient in practice since all you can do is open bits and to get a reasonable NIZK from this you need an incredibly massive CRS. $\endgroup$
    – Yehuda Lindell
    Commented May 31, 2018 at 5:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.