Cryptology ePrint Archive: Report 2004/220

On Oleshchuk's Public Key Cryptosystem

Heiko Stamer and Friedrich Otto

Abstract: This paper revisits a public key cryptosystem which is based on finite Church-Rosser string-rewriting systems. We consider some ideas for cryptanalysis and discuss issues concerning practical usage. It turns out that without changing crucial details of key generation this cryptosystem does not offer acceptable cryptographic security. We also provide the source code of our rudimentary implementation, if someone would like to use it for further cryptanalysis.

Category / Keywords: public-key cryptography / cryptanalysis, string-rewriting systems, Church-Rosser property, completion attack

Date: received 1 Sep 2004

Contact author: stamer at theory informatik uni-kassel de

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20040901:195600 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]