## Complexity and Cryptography: An Introduction, Volume 13Cryptography plays a crucial role in many aspects of today's world, from internet banking and ecommerce to email and web-based business processes. Understanding the principles on which it is based is an important topic that requires a knowledge of both computational complexity and a range of topics in pure mathematics. This book provides that knowledge, combining an informal style with strong proofs of the key results to provide an accessible introduction. It includes many examples and exercises, and is based on a highly successful course developed and taught over many years. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

III | 1 |

IV | 2 |

V | 3 |

VI | 7 |

VII | 8 |

VIII | 10 |

IX | 16 |

X | 22 |

XLV | 145 |

XLVI | 147 |

XLVII | 150 |

XLVIII | 153 |

XLIX | 155 |

L | 158 |

LI | 161 |

LII | 164 |

XI | 30 |

XII | 33 |

XIII | 39 |

XIV | 43 |

XV | 45 |

XVI | 54 |

XVII | 56 |

XVIII | 60 |

XIX | 62 |

XX | 67 |

XXI | 71 |

XXII | 74 |

XXIII | 80 |

XXIV | 81 |

XXV | 83 |

XXVI | 86 |

XXVII | 92 |

XXVIII | 93 |

XXIX | 94 |

XXX | 99 |

XXXI | 101 |

XXXII | 102 |

XXXIII | 106 |

XXXIV | 111 |

XXXV | 113 |

XXXVI | 115 |

XXXVII | 118 |

XXXVIII | 119 |

XXXIX | 125 |

XL | 129 |

XLI | 132 |

XLII | 135 |

XLIII | 141 |

XLIV | 142 |

### Other editions - View all

### Common terms and phrases

3-colourable accepts Alice and Bob attack binary Bob's Boolean function chooses a random cipher circuit CLIQUE co-NP colours complexity computation consider cryptogram cryptography decision problem decryption defined denote Diffie-Hellman Elgamal encoding encryption Euclid's algorithm example Exercise exists factorisation feedback polynomial given graph G halting hard-core predicate hash function Hence input x e integer interactive proof system invert keystream length LFSR matrix mod q modn NP-complete one-time pad one-way function output P/poly pair Peggy permutation polynomial time algorithm Pr[A primality primitive root mod private key probabilistic algorithm probabilistic polynomial probability Proposition protocol prove pseudorandom PSPACE public key cryptosystem quadratic residue quadratic residue mod random bits read-write head recover the message result satisfying truth assignment secret key secret shares secure sends sequence signature scheme simply string strong one-way function Suppose tape Theorem trapdoor users vertices Victor zero