3
$\begingroup$

First of all, the Guillou-Quisquater digital signature scheme is:

Note everything is $\bmod n$. Message is denoted by $m$.

Private key: $s$

Public key: Hash function $H$, $e$, $L=s^e\bmod n$

To sign: Alice chooses random $r$. Computes $c=H(m||x)$ with $x=r^e\bmod n$; $y=r\cdot s^c\bmod n$; send Bob $x$ and $y$.

To verify: Bob computes $c=H(m||x)$ and accept if $y^e \equiv x\cdot L^c\pmod n$.

I'm wondering what the strongest known security of this is, in particular the question in the title. If not, what's the best research that's been done on this scheme?

I've scoured the internet for such a proof, but I can't find anything. I was also told by my supervisor that if I could find such a proof for El Gamal it might be easily adaptable, so that would also be much appreciated. Thanks!

$\endgroup$
  • 1
    $\begingroup$ What is "l" in your description of verification? $\:$ $\endgroup$ – user991 Feb 22 '13 at 6:51
  • $\begingroup$ Sorry, that's a lowercase L - same as the capital L in the public key. $\endgroup$ – Samuel Reid Feb 22 '13 at 21:33
  • $\begingroup$ Samuel, can you edit your question to fix any such typos? These details are important. You can click the little "edit" button at the bottom of your post to correct it. Thank you! $\endgroup$ – D.W. Feb 23 '13 at 7:19
  • $\begingroup$ The GQ signature scheme is hardly recognizable in the question. For a full exposition, see 11.4.2 in chapter 11 of the HAC. $\endgroup$ – fgrieu Feb 23 '13 at 10:27
  • $\begingroup$ @fgrieu I've seen that one too, but this is what my supervisor suggested we should use. I think there's several different schemes going by the name of "GQ signature scheme". $\endgroup$ – Samuel Reid Feb 23 '13 at 20:01
2
$\begingroup$

Guillo-Quisquater scheme uses the Fiat-Shamir trick to convert a proof of knowledge into a signature. There is a paper out there about the security of such schemes in the random oracle model here which seems to give what you want.

$\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.