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.
I'd note that HAC says it is less efficient than Feige-Fiat-Shamir, though whether that is any use to you is another question.
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.
That sure looks like a patent to me - does it cover the algorithm you are thinking of (on the face of it, it sounds like it)?
So, although that's not necessarily a barrier to implementation, it may be a barrier to use. That would depend on their licensing terms.
However, looking at the bibliography in HAC, it seems the method _may_ have been presented at EUROCRYPT '88 - which would make the patent (filed in '91) invalid almost everywhere except the US. That would need verification, of course.
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).
Springer-Verlag are assholes about that - but I have the proceedings anyway.
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.
Cool! I need this for Keyman (http://keyman.aldigital.co.uk).
<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)
What's the status of MMM, patent-wise? What licence are you using?
Cheers,
Ben.
-- http://www.apache-ssl.org/ben.html http://www.thebunker.net/
"There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit." - Robert Woodruff
______________________________________________________________________ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
