3
$\begingroup$

The text below has been taken from the below paper Groth-Sahai Paper. The relevant part is highlighted in red. enter image description here

What does this group-dependent language mean in this context? From the definition of a language we know that it means a set of strings. In this case, what are all the strings forming the language?

$\endgroup$
4
$\begingroup$

You may be aware of the fact that zero-knowledge proofs for any language in $NP$ can be constructed if you have a zero-knowlege proof for any $NP$-complete language. Then you can reduce your original language to the $NP$-complete one in polynomial time and you are done (more precisely you reduce the instance and the corresponding witness). As the $NP$-complete language you could use 3-coloring or circuit satisfiability for instance. Although in theory such an approach is feasible, it is not practical for cryptographic protocols.

Group dependent language here means relations of elements and exponents in bilinear groups that can be expressed using all the equations illustrated in Figure 1 of the paper you linked to. Although this language is a more restricted language than "any language in $NP$", it is expressive enough for many interesting tasks that show up in cryptographic protocols to prove statements about ciphertexts, commitments and (structure-preserving) signatures for instance. The benefit is that it is practically efficient.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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