Cryptography: Theory and Practice:Index | Modern Cryptography: Theory and Practice

Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210 Pub Date: 03/17/95

Table of Contents

Index

abelian group, 4, 116, 184

accept, 385

access structure, 331

threshold, 332, 333

active adversary, 258

additive identity, 3

additive inverse, 3

adjoint matrix, 16

adversary

active, 258

passive, 258

Affine Cipher, 8, 8-12

cryptanalysis of, 26-27

affine function, 8

Affine-Hill Cipher, 41

algorithm

deterministic, 129

Las Vegas, 139, 171, 234

Monte Carlo, 129, 129

probabilistic, 129

associative property, 3

of cryptosystems, 66

authentication code, 304, 304-323

combinatorial bounds, 311-313

deception probability, 305, 306-313, 319-323

entropy bounds, 321-323

impersonation attack, 305, 306-308

orthogonal array characterization, 319-320

substitution attack, 305, 307-309

authentication matrix, 306

authentication rule, 305

authentication tag, 305

authorized subset, 331

minimal, 332

Autokey Cipher, 23, 23

basis, 332

Bayes’ Theorem, 45, 60, 135, 340, 341

binding, 399

binomial coefficient, 31

birthday paradox, 236

bit commitment scheme, 399, 398-401, 405-407

blob, 399

block cipher, 20

Blom Key Predistribution Scheme, 261, 260-263

Blum-Blum-Shub Generator, 371, 370-377, 379

Blum-Goldwasser Cryptosystem, 380, 379-382

boolean circuit, 333

fan-in, 333

fan-out, 333

monotone, 333

boolean formula, 333

conjunctive normal form, 337

disjunctive normal form, 334

Bos-Chaum Signature Scheme, 216, 215-217

Brickell Secret Sharing Scheme, 344, 343-348

Caesar Cipher, 4

certificate, 264

challenge, 385

challenge-and-response protocol, 217, 283, 385

Chaum-van Antwerpen Signature Scheme, 218, 217-223

Chaum-van Heijst-Pfitzmann hash function, 238, 238-241

Chinese remainder theorem, 122, 119-122, 142, 166, 380

Chor-Rivest Cryptosystem, 115

chosen ciphertext cryptanalysis, 25

chosen plaintext cryptanalysis, 25

cipher

block, 20

stream, 20, 20-24, 360

cipher block chaining mode, 83, 83, 267

cipher feedback mode, 83, 85

ciphertext, 1, 20, 378

ciphertext-only cryptanalysis, 25

closure, 332

closure property, 3

code, 194

distance of, 194

dual code, 194

generating matrix, 194

Goppa code, 195

Hamming code, 196

nearest neighbor decoding, 194

parity-check matrix, 194

syndrome, 194

syndrome decoding, 195

coin-flipping by telephone, 400

commutative cryptosystems, 66

commutative property, 3

complete graph, 346

complete multipartite graph, 346, 352, 353

completeness, 286, 386

Composites, 129, 130

computational security, 44

concave function, 56

strictly, 56

concealing, 399

conditional entropy, 59

conditional probability, 45

congruence, 3

conjunctive normal form boolean formula, 337

cryptanalysis, 6

chosen ciphertext, 25

chosen plaintext, 25

ciphertext-only, 25

known-plaintext, 25

cryptogram, 7

cryptosystem, 1

endomorphic, 64

idempotent, 66

iterated, 66

monoalphabetic, 12

polyalphabetic, 13

private-key, 114

probabilistic public-key, 378

product, 64, 64-67

public-key, 114

cyclic group, 123, 183, 187

Data Encryption Standard, 51, 70

description of, 70-78

differential cryptanalysis of, 89, 89-104

dual keys, 110

exhaustive key search, 82

expansion function, 71, 73

initial permutation, 70, 73

key schedule, 71, 75-78

modes of operation, 83, 83-86

S-boxes, 72, 73-75, 82

time-memory tradeoff, 86, 86-89

dealer, 326

deception probability, 305

decision problem, 129, 190

decomposition construction, 354, 355, 353-357

decryption rule, 1, 21, 378

determinant, 16

deterministic algorithm, 129

differential cryptanalysis, 89

characteristic, 98

filtering operation, 101

input x-or, 89

output x-or, 89

right pair, 100

wrong pair, 100

Diffie-Hellman Key Exchange, 270, 270-271

Diffie-Hellman Key Predistribution Scheme, 265, 263-267

Diffie-Hellman problem, 266, 265-267, 275

Digital Signature Standard, 205, 211, 209-213

digram, 25

disavowal protocol, 217

Discrete Logarithm Generator, 383

Discrete Logarithm problem, 162, 163, 164-177, 206, 207, 210, 238, 263, 266, 276, 287, 290, 362, 397, 400, 406

bit security of, 172-177, 400

elliptic curve, 187

generalized, 177, 177-180

in Galois fields, 183

index calculus method, 170-172

ith Bit problem, 173

Pohlig-Hellman algorithm, 169, 166-170

Shanks’ algorithm, 165, 165-166

disjunctive normal form boolean formula, 334

distinguishable probability distributions, 364

distinguisher, 364

distribution rule, 338

distributive property, 4

electronic codebook mode, 83, 83

ElGamal Cryptosystem, 115, 163, 162-164, 266-267

elliptic curve, 187-190

generalized, 178, 177-178

ElGamal Signature Scheme, 205, 205-209

elliptic curve, 183, 183-187

point at infinity, 183

Elliptic Curve Cryptosystem, 115, 187-190

encryption matrix, 47

encryption rule, 1, 21, 378

endomorphic cryptosystem, 64

entropy, 52, 51-52

conditional, 59

of a natural language, 61

of a secret sharing scheme, 349-352

of authentication code, 321-323

properties of, 56-59, 349

Euclidean algorithm, 116-120, 140, 179, 181

extended, 117, 119

running time of, 128

Euler phi-function, 9

Euler pseudo-prime, 132

Euler’s criterion, 130, 131, 173

exclusive-or, 21

exhaustive key search, 6, 13

of DES, 82

factor base, 171

factoring, 150-156

factor base, 153

number field sieve, 155

p - 1 algorithm, 151, 151-152

quadratic sieve, 154

trial division, 150

fan-in, 333

fan-out, 333

Fermat’s theorem, 122, 137

Fibonacci number, 128

field, 10, 181

forging algorithm, 390

for Graph 3-colorability, 405

for Graph Isomorphism, 391, 394

Galois field, 180-183

Girault Key Agreement Scheme, 278, 276-279

Goldwasser-Micali Cryptosystem, 379, 378-379, 399

graph, 346

complete, 346

complete multipartite, 346, 352, 353

induced subgraph, 352

isomorphic, 386

proper 3-coloring, 401

Graph 3-colorability, 401

Graph 3-colorability Interactive Proof System, 402, 400-404, 406-407

Graph Isomorphism, 386

Graph Isomorphism Interactive Proof System, 389, 388-395

Graph Non-isomorphism, 386

Graph Non-isomorphism Interactive Proof System, 387, 386-388, 395-396

group, 4

abelian, 4, 116, 184

cyclic, 123, 183, 187

order of element in, 122

Guillou-Quisquater Identification Scheme, 296, 295-299

identity-based, 300

Hamming distance, 194

hash function, 203, 232, 232-254

birthday attack, 236-237

collision-free, 233-236

constructed from a cryptosystem, 246

extending, 241-246

one-way, 234

strongly collision-free, 233

weakly collision-free, 233

Hill Cipher, 13-17, 18

cryptanalysis of, 36-37

Huffman encoding, 53-56

Huffman’s algorithm, 55

ideal decomposition, 353

ideal secret sharing scheme, 343, 344, 346-348

idempotent cryptosystem, 66

identification scheme, 282-300

converted to signature scheme, 300

identity-based, 299, 299

identity matrix, 14

impersonation, 305

implicit key authentication, 276, 278

independent random variables, 45

index of coincidence, 31

mutual, 33

indistinguishable probability distributions, 363-370, 378, 404

induced subgraph, 352

information rate, 342

monotone circuit construction, 343

injective function, 2

interactive argument

perfect zero-knowledge, 407

zero-knowledge, 406, 405-407

interactive proof, 385, 385-397

computational zero-knowledge, 398, 404, 400-404

perfect zero-knowledge, 393, 388-397

perfect zero-knowledge for Vic, 391

zero-knowledge, 385

intruder-in-the-middle attack, 271, 305

inverse matrix, 15

inverse permutation, 7

isomorphic graphs, 386

iterated cryptosystem, 66

Jacobi symbol, 132, 132-134, 370, 379

Jensen’s Inequality, 56, 63, 316

joint probability, 45

Kasiski test, 31

Kerberos, 268, 267-270

key lifetime, 268

session key, 267

timestamp, 268

Kerckhoff’s principle, 24

key, 1, 20, 203, 305, 326, 378

key agreement, 258

authenticated, 271

key confirmation, 269

key distribution, 258

on-line, 259

key equivocation, 59

key freshness, 267

key predistribution, 259, 260-267

key server, 259

keystream, 20

keystream alphabet, 21

keystream generator, 21

keyword, 12

known-plaintext cryptanalysis, 25

Lagrange interpolation formula, 329, 329-330

Lagrange’s theorem, 122

Lamé’s theorem, 128

Lamport Signature Scheme, 213, 213-215

Las Vegas algorithm, 139, 171, 234

Legendre symbol, 131, 131-132

Linear Congruential Generator, 360, 360

linear feedback shift register, 22, 360, 362

linear recurrence, 21

linear transformation, 14

m-gram Substitution Cipher, 68

matrix product, 14

McEliece Cryptosystem, 115, 196, 193-198

MD4 Hash Function, 248, 247-250

MD5 Hash Function, 247, 250

memoryless source, 53

Menezes-Vanstone Cryptosystem, 189, 188-190

Merkle-Hellman Cryptosystem, 115, 193, 190-193

message, 203, 305

message authentication code, 86, 304

message digest, 232

Miller-Rabin algorithm, 129, 130, 137, 136-138

error probability of, 138

mod operator, 3

modular exponentiation, 127

square-and-multiply algorithm, 127, 127, 131

modular multiplication, 126

modular reduction, 3

modulus, 3

monoalphabetic cryptosystem, 12

monotone circuit, 333

monotone circuit construction, 333, 335

information rate, 343

monotone property, 332

Monte Carlo algorithm, 129, 129, 374

error probability of, 129

no-biased, 129

unbiased, 374, 374-377

yes-biased, 129

MTI Key Agreement Protocol, 274, 273-276

Multiplicative Cipher, 65, 65

multiplicative identity, 4

multiplicative inverse, 10

mutual index of coincidence, 33

next bit predictor, 365-370

NP-complete problem, 44, 191, 193, 400, 404

Okamoto Identification Scheme, 291, 290-295

One-time Pad, 50, 50

one-way function, 116, 213, 234

trapdoor, 116

oracle, 139

orthogonal array, 314, 313-320

bounds, 315-318

constructions, 318-319

output feedback mode, 83, 85, 362

passive adversary, 258

perfect secrecy, 48, 44-51

perfect secret sharing scheme, 332, 339, 349

periodic stream cipher, 21

permutation, 2

Permutation Cipher, 18, 17-20

permutation matrix, 19

plaintext, 1, 20, 378

polyalphabetic cryptosystem, 13

polynomial

congruence of, 180

degree of, 180

division, 180

irreducible, 181

modular reduction of, 181

polynomial equivalence, 126

prefix-free encoding, 54

previous bit predictor, 373

primality testing, 129-138

prime, 9

Prime number theorem, 129, 135

primitive element, 123

principal square root, 373, 379

private-key cryptosystem, 114

probabilistic algorithm, 129

probabilistic encryption, 377-382

probabilistic public-key cryptosystem, 378

probability, 45

conditional, 45

joint, 45

product cryptosystem, 64, 64-67

proof of forgery algorithm, 224

proof of knowledge, 285

proper 3-coloring, 401

protocol failure, 156, 158, 208

prover, 385

pseudo-random bit generator, 359, 359-377

pseudo-square, 370

public-key cryptosystem, 114

probabilistic, 378

quadratic non-residue, 130

Quadratic Non-residues Interactive Proof System, 408

quadratic reciprocity, 132

quadratic residue, 130

Quadratic Residues, 130, 130, 371, 370-371, 374, 375, 377, 396, 399, 406

Quadratic Residues Interactive Proof System, 396, 396-397

Rabin Cryptosystem, 147, 145-150

security of, 149-150

rank, 226

redundancy of a natural language, 61

reject, 385

relative shift, 33

relatively prime, 9

replay attack, 269

response, 385

ring, 4, 180

round, 385

RSA Cryptosystem, 114, 124, 124

attacks on, 138-145

bit security of, 144-145

implementation of, 125-128

RSA Generator, 362, 362-363

RSA Signature Scheme, 203, 204

Schnorr Identification Scheme, 286, 284-289, 295

Schnorr Signature Scheme, 301

search problem, 190

secret sharing scheme, 326-357

decomposition construction, 353-357

ideal, 343, 344, 346-348

information rate, 342, 341-343, 349-355

monotone circuit construction, 333-338

threshold scheme, 326-331

Secure Hash Standard, 247, 250-252

security parameter, 284, 378

seed, 359

self-certifying public key, 276

session key, 259

Shamir Threshold Scheme, 327, 327-330, 343, 346

share, 326

Shift Cipher, 4, 3-7

Shrinking Generator, 362

signature, 203

signature scheme, 203, 202-229

constructed from identification

scheme, 300

fail-stop, 224-229

one-time, 213-217, 228

undeniable, 217-223

signing algorithm, 203

simulator, 390

Solovay-Strassen algorithm, 133, 129-136

error probability, 136, 134-136

soundness, 288, 386

source state, 304

Sperner property, 215

spurious keys, 61, 59-64

expected number of, 63

square-and-multiply algorithm, 127, 127, 131

Station-to-station Protocol, 272, 271-273

Stirling’s formula, 68, 216

stream cipher, 20, 20-24, 360

cryptanalysis of, 37

synchronous, 21, 85

Subgroup Membership, 397

Subgroup Membership Interactive Proof System, 398

Subset Sum problem, 190, 190-191

modular transformation, 192

superincreasing, 191

substitution, 305

Substitution Cipher, 7, 7, 7-8

cryptanalysis of, 27-31

m-gram, 68

synchronous stream cipher, 21, 85

threshold scheme, 326, 326-331

timestamping, 252-254

transcript, 390

Transposition Cipher, 17

trapdoor, 116

trigram, 25

trusted authority, 258

unconditional security, 45

unicity distance, 63, 59-64

van Heyst-Pedersen Signature Scheme, 225, 224-229

Vandermonde matrix, 329

determinant of, 329

verification algorithm, 203

verifier, 385

Vernam One-time Pad, 50, 50

Vigenere Cipher, 12, 12-13, 40

cryptanalysis of, 31-36

zero-knowledge interactive argument, 406, 405-407

perfect, 407

zero-knowledge interactive proof, 385

computational, 398, 404, 400-404

perfect, 393, 388-397

perfect, for Vic, 391

Table of Contents