MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
Question may or may not get a better answer at . – Qiaochu Yuan Feb 22 '13 at 21:42
It's been up there for a day and hasn't got much activity, so I thought I'd ask it here, too. – Samuel Reid Feb 22 '13 at 21:48

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.