New patent: Auto-escrowable and auto-certifiable cryptosystems with fast key generation

[dmolnar]

On Fri, 15 Jun 2001, Robin Lee Powell wrote:

>
> So, anyone know if this is any good?

There was a paper on a similar topic in this year's ASIACRYPT from the
same authors. I have *not* reviewed the patent yet to see if the claimed
techniques are the same as that paper.

The paper seems to work; it's based on a cute technique involving what
they call "double-decker exponentiation." Instead of working with g^x, you
work with g1^(g2^x). They use this to perform what could be called "RSA in
the exponent" and leverage this to acheive the claimed signature-only
property. Double-decker exponentiation is interesting in its own right,
too.

One of the sections in their paper note that after too many signatures,
the scheme could leak a "shadow" public key. The signatures were needed to
solve a system of simultaneous equations; it made me wonder how a lattice
reduction algorithm would fare in practice. I apologize for being so
imprecise here, but the paper is at

http://link.springer-ny.com/link/service/series/0558/bibs/1976/19760097.htm

-David