Public key cryptography based on simple semirings
v Zusammenfassung vii Acknowledgements ix 1 Cryptography 1 1.1 Cryptosystems 2 1.1.1 Encryption schemes 2 1.1.2 Digital signatures 3 1.2 Perfect security: Shannon's theory of secrecy 5 1.2.1 Perfect security 5 1.2.2 Indistinguishability 6 1.3 Computational security 6 1.3.1 Principles of complexity theory 7 1.3.2 Efficient algorithms and cryptosystems 8 1.3.3 Public key cryptography 9 1.3.4 Notions of security 11 1.4 One way functions and trapdoor functions 14 1.5 Discrete logarithm based cyptosystems 17 1.5.1 Function problems 18 1.5.2 The discrete logarithm problem 19 1.5.3 The Diffie Hellman key agreement protocol 21 1.5.4 ElGamal encryption 23 1.5.5 Schnorr identification and signature 24 2 Cryptosystems based on semigroup actions 29 2.1 Semigroup actions 29 2.2 Semigroup action problems 32 2.2.1 Noncommutative semigroup actions 34 2.2.2 Problems in related semigroup actions 36 2.2.3 Two sided group actions 38 2.3 Cryptosystems 40 2.3.1 Semigroup action Diffie Hellman key agreement 42 2.3.2 Semigroup action ElGamal encryption 43 2.3.3 Identification protocols and digital signatures 45