The Rise and Fall of a Public Key Cryptosystem
I came upon my algorithms for signature, and later encryption,
in prime order subgroups of Zn* by chance, while I was thinking
of another idea. When I could not break them myself I showed them
to a few people and then submitted them for publication. The
paper describing them was accepted for the ICICS'97 conference
in Beijing. Then things started to go wrong.
First Problem
I presented the algorithms in a seminar at Queen's University,
Canada, in September 1997. When I returned to Australia, Henk
Meijer informed me that he had found that it was easy to
find the private key from the public key, due to the structure
of the public key.
It was not too difficult to overcome this problem, by altering
the algorithm to work in a small (non-prime order) subgroup of
Zn*. This reduced the efficiency but still made the
computational requirements attractive. It was in any case too
late to withdraw my paper from the ICICS'97 conference, so I
went ahead and presented it, explaining the problem and how to
fix it.
Second Problem
After the ICICS'97 conference the algorithm got wider
exposure. It was not long before I heard from Markus Michels
at UBS in Switzerland that he and his colleague Markus Stadler
had found an attack on the signature scheme that exploited
the algorithm in a clever way. Markus also pointed out that
a similar algorithm to mine had been published by deJonge and Chaum
back at Crypto'86.
Before I really was able to even appreciate the attack I was
also contacted by Hung-Min Sun of Chaoyang University of Technology,
Taiwan, who had independently found what was essentially the
identical attack. Quickly I had to admit that the signature
scheme was broken. At that stage the encryption algorithm was
still intact and it was my hope to fix up the signature algorithm
(for example by making it probabilistic like the encryption
algorithm) and prove the whole idea secure.
Final Demise
Wenbo Mao, of Hewlett-Packard Labs, UK, had taken an interest
in my algorithms for some time. In March 1998 Wenbo completely
broke the whole idea of my algorithms, by showing that the
public information is sufficient to decrypt messages, or to generate
signatures. The only way to fix the algorithms would make them
much less efficient than existing schemes.
A
paper by Wenbo describing the attack is available from the P1363
web site. An expanded version of this paper will be presented at
Asiacrypt'98, and includes attacks on other algorithms too.
I am grateful to all the researchers who took an interest in
my algorithms. I have learnt a lot from the `rise and fall' of
the idea, and hope others may also gain some insight from the
papers that have described the problems.
Last modified: 20th August 1998