On Saturday, March 8, 2003, at 07:37 AM, Ben Laurie wrote:
Eric Cronin wrote:The Guillou-Quisquater (GQ) signature scheme seems to be popular in theory literature due to its efficiency compared to other signature algorithms. In the real world however, there does not seem to be much use of GQ... It's not is any of the common cryptographic libraries (OpenSSL, CryptLib, Cryptix) or in any standards or RFCs.
What literature? Not any I've read - OTOH, I probably don't read enough.
Papers from various theory conferences... It comes up most often in one-time signature/broadcast authentication, forward-secure signatures and e-cash (limited computing) papers, usually accompanied by some comment on it being one of the most efficient signatures.
My first question is if anyone knows if this is because there's some aspect of GQ that, when you actually go out and use it, makes it not as great as the theoretical discussion would make you think, or if its just a matter of "what we have now works well enough," and no one has pushed for getting GQ widely used. I'm guessing its the later given DSAs marginal foothold is only due to being legislated as a standard more or less.
The other questions that would be relevant are:
a) How much more efficient is it?
I don't know the answer to this one... Lacking any implementations to actually benchmark, all I have are some big-O space and time complexities as compared to RSA/DSA/ECDSA. This is why I was wondering if anyone had experience with it in the past.
b) Is it encumbered in any way (e.g. patents)?
Schneier is usually good about pointing out when algorithms covered under patents, and the section in Applied Crypto mentions no patents. Googling for it though turns up <http://patft.uspto.gov/netacgi/nph- Parser?Sect2=PTO1&Sect2=HITOFF&p=1&u=%2Fnetahtml%2Fsearch- bool.html&r=1&f=G&l=50&d=PALL&RefSrch=yes&Query=PN%2F5140634> I am definitely not a lawyer so I don't know what this implies.
Searching the mailing list archives I couldn't find any previous discussion of GQ in OpenSSL. Part of OpenSSL's mission is to provide "a full-strength general purpose cryptography library". Would GQ fall into this category if it were to be implemented as another EVP signature algorithm, or is the focus more on just providing already standardized algorithms than every un-patented crypto algorithm out there? The project I'm working on right now (forward-secure signatures) could really use a fast base signature, so I'm looking into implementing GQ for it. If people think this would be a useful thing to add into OpenSSL I can look into doing the implementation there instead of in my F-S Sig library.
Sounds interesting. Where can I find out more about GQ? What exactly do you mean by "forward-secure signatures"?
GQ Is covered briefly in both Schneier and Menezes, and also in its original paper:
Louis Claude Guillou and Jean-Jacques Quisquater. A "paradoxical"
indentity-based signature scheme resulting from zero-knowledge. In Advances in Cryptology--CRYPTO '88, volume 403 of Lecture Notes in Computer Science. Springer-Verlag, pages 216-231. (sorry, don't have an online reference... papers from the 80's are hard to find).
Forward-secure signatures are ones created with special public/private keys where one public key is associated with a non-reversable evolving private key, so that after a private key is compromised old signatures can still be verified and trusted. It's similar to using normal public/private keys with very short expiration times, except you don't then have to manage a ton of old expired public keys still needed for verification. <http://theory.lcs.mit.edu/~cis/pubs/reyzin/forwardsig-optimal.pdf> and <http://www.cs.ucsd.edu/~daniele/papers/MMM.html> are two recent F-S Sig papers (MMM is the one I have actually implemented, with IR being added soon for comparative purposes)
Thanks, Eric
______________________________________________________________________ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
