Index

NC¹, see Nick's Class

(·), 310

π(·), 310

e^th roots assumption, 314

gcd(·,·), 310

1963 virus, 175

3DES, see symmetric cipher, 3DES

activity monitor, 186

adaptive attacks

chosen-ciphertext, 53, 80, 328, 340

chosen-message, 329, 343

chosen-plaintext, 327

AES, see symmetric cipher, AES

algorithmic combinatorics, 53

all-or-nothing disclosure, 137

ambivalent root, 166, 248, 256

Anderson Report, 190, 202

anonymous remailer, 45, 90

ANSI C, 232

ARDA, 77

assassination politics, 92, 93, 97

asymmetric cryptography, 39

asymmetric cryptosystem, 326

AT&T, 34

authentication systems, 35

battleprogs, 17

bias matching, heuristic, 60

biased coin, 52, 57

Big-O notation, 309

Binomial Theorem, 110

black-box cryptosystem, 231

Blowfish, see symmetric cipher, Blowfish

Blum integer, 330

busy-waiting, 53

call graph, 193

call-back function, 34

Capstone, 230

card shuffling, 71

Carmichael lambda function, 310

cascading encryptions, 290

CERT, 21, 348

certificate of recoverability, 227

certificate revocation list, see CRL

certification authority, 225, 227, 259, 292, 337

CFB, see cipher feed-back

chaotic air-turbulence, 54

checksum, 18, 30, 46, 135, 330

Chernoff bounds, 232

Chinese Remainder Theorem, 111, 331, 336

chosen-ciphertext attack, 327, 331

chosen-message attack, 329

chosen-plaintext attack, 327, 331

cipher feed-back, 46

ciphertext-only attack, 326

circularly linked list, 21, 100, 133

Clipper chip, 230, 286

Columbia University, 36

complete break, 328

composite key generation

honest, 231

SETUP attack on, 246

weak attacks on, 232

Computational Composite Residuosity assumption, 314, 315

conditional probability, 309

Confinement Problem, 214

congruence, 308

constant sum game, 150, 160

cookie-monster virus, 191

Core Wars, 295

correctness property, 120

Coupon Collector's Problem, 219

covert channel, 214

CRL, 200, 342, 348

cross-certified, 152, 153

cryptanalysis

definition of, 321

differential, 287

linear, 287

cryptanalyst, 321

cryptanalyzing adversary, 242

cryptocomputing, 114, 136, 142

cryptocounter, 103, 104, 111

based on additive group ₂, 111

ElGamal based, 105

Paillier based, 108, 111

cryptographer, 321

cryptography

definition of, 321

cryptolib, 34

cryptologist, 321

cryptology

definition of, 321

cryptotrojan, 77, 191, 238, 271, 281

cryptovirus, 43, 44, 48, 51, 78, 115, 191

cyberpunk, 6, 25

DARPA, 77, 144

database algorithm, 117, 119, 123, 127

database replication, 116

DCR, 108, 315, 348

DDH, 112, 318, 319, 337, 348

decision problem, 171

Den Zuk virus, 103

deniable encryption, 139

deniable password-snatching, 97, 132

denial-of-service, 40, 313, 348

DES, see symmetric cipher, DES

differential power analysis, 261, 288

Diffie-Hellman assumption, 318, 324

Diffie-Hellman key exchange, 213, 265, 266, 268, 271, 274, 278, 288, 289, 313, 318, 324, 337, 338

Diffie-Hellman triple, 318

digital certificate, 199, 227, 233, 334, 337, 342

digital signature algorithm, 280, 334

DSA, 217, 218, 222, 283, 345

ElGamal, 216, 223, 342

Pointcheval-Stern, 282, 318

Rabin, 331

RSA, 334

Schnorr, 284, 344

Digital Signature Standard, 345

discrete logarithm, 106, 143, 217, 235, 265, 280, 318, 324, 337, 343

discrete logarithm assumption, 318

disk-locking program, 30

distinguishing adversary, 242, 249

double-spending, 91

DSA, see digital signature algorithm, DSA

e-money, 91–94

EDE mode, 47, 48, 67

electronic voting, 96

ElGamal cryptosystem, see public key cryptosystem, ElGamal

Elk Cloner virus, 297

elliptic curve cryptosystems, 252

entropy extractor, 46, 52, 55

entropy sources

CPU crystal, 34, 53

free-running oscillators, 62

hard disk air-turbulence, 54

keyboard presses, 53

mouse timings, 53

radioactive emissions, 53

system time, 56

thermal noise, 62

Euclidean algorithm, see greatest common divisor

Euler's criterion, 217, 220, 311, 312, 315

Euler's totient function, 310, 333

existential forgery, 55, 328, 331, 335, 343

extended Euclidean, 310, 314, 330, 333, 338

Extended Riemann Hypothesis, 119

Extended Tiny Encryption Algorithm, see symmetric cipher, XTEA

factoring assumption, 313, 330

fair cryptosystem, 227

fault-tolerance, 167

Feistel cipher, 36

Fermat's Little Theorem

generalized form, 333

Fiat-Shamir heuristic, 125

FIPS, 66

FIPS-140, 76, 237, 291

FNP, 313

forward secrecy, 235–237, 265, 269, 349

friend-or-foe, 35

game theory, 149, 150

gcd, see greatest common divisor

generator, 311, 318, 324

finding an, 311

generic decryption, 180, 305

GNUmp, 34, 46

gnutella protocol, 94

greatest common divisor, 231, 234, 256, 282, 310, 314, 330–332, 342, 343

definition of, 308

halting problem, 27, 171, 350

Harmonic numbers, 72

hash function, 52, 54, 267, 319, 330, 340

collision intractability, 55, 340

extracting entropy with, 55

MD4, 55

MD5, 342

non-invertability, 55

SHA-1, 55, 122

hexadecimal, 350

homomorphism

additive, 111, 142

multiplicative, 142

honest-but-curious model, 104

honeypot, 10

hooks, see operating system, hooks

Huffman compression, 197

hybrid encryption, 45, 278

identity-based cryptosystem, 228

inoculation, 199

integrity checks, 17, 197

Intel hardware RNG, 62

inter-mix detour, 83

Internet Worm, 173, 297

interrupt addresses, 20

intractable, 313, 350

Israeli virus, 173

ITAR, 33, 350

Jacobi symbol, 39, 78, 213, 312, 335, 336

Karatsuba multiplication, 34, 192, 311

Kerchhoff's principle, 323

key escrow, 226

key-only attack, 329

kleptogram, 266

kleptogram, discrete-log, 265, 268, 275–277, 280–283

kleptographic attack, 80, 205, 219, 230, 277

known-message attack, 329

known-plaintext attack, 36, 326

Lagrange interpolation, 121

Las Vegas, 58, 76, 179, 246, 331, 351

Legendre symbol, 311, 315

logic bomb, 202, 351

Lucent Technologies, 54

lunch time attacks, 194

malleable ciphertext, 101, 104, 105, 351

MARS, see symmetric cipher, MARS

MD4, see hash function, MD4

memory-resident, 20

message indistinguishability, 79, 335

Millionaire problem, 144

minimal change algorithm, 73

minimal universal exponent, 311

MITM, 155, 159, 324, 337, 351, 353

mix network, 53, 80, 91, 94–96, 132, 133, 153, 158, 168, 212, 230

asynchronous, 81

sandwich attack, 83

synchronous, 81

mobile agent, 107, 122, 132, 142, 146

Monkey virus, 176

Monte Carlo, 67, 76, 239, 246, 331, 351

Montgomery reduction, 34, 311

MP3, 352

multipartite, 17

multiprecision library, 34, 75, 349, 352

Napster, 95

Neumann's unbiasing algorithm, 57, 71, 292

iterated, 59

Newton channel, see subliminal channel, Newton channel

Nick's Class, 145

Night City, 6

NIZK proof, 125, 227

non-zero sum game, 147, 149, 150, 160, 168

nonce, 138, 267, 276, 278, 352

NP, 313

Nullsoft, 94

number field sieve, 314

OAEP, 79, 80, 98, 135, 158, 352

One-half virus, 38

One-time pad, 36, 64, 159, 221

one-way function, 9, 18, 265, 275, 287, 289, 335, 344, 345

onion routing, 81, 352

OpenSSL, 52, 70, 75

operating system

hooks, 13

interrupt handler patch, 20

routines, 20

Paillier, see public key cryptosystem, Paillier

Pakistani Brain virus, 190

PAP, see pretty-awful-privacy

password-snatching, 2, 10, 31, 97, 115, 126, 135, 141, 203

patch, see operating system, interrupt handler patch

PBRM, see probabilistic bias removal method

PEAT toolkit, 183

perfect crime, 93, 94, 97

permutation generation, 71

personal information exchange, 233

PGP, see pretty-good-privacy

Phi-Hiding assumption, 117, 316

Phi-Sampling assumption, 119, 317

PIR, see private information retrieval

PKCS #12, see personal information exchange

PKI, 95, 152, 153, 158, 199, 225, 226, 288, 291, 336, 338

plaintext-aware, 341

Pohlig-Hellman, 224, 266, 318

Pollard's Rho, 224

polymorphic virus, 17, 36, 46, 175, 176, 184, 191, 298, 305

polynomially indistinguishable, 68, 139, 244, 250, 252, 271

Power Residue Hypothesis, 145

pretty-awful-privacy, 238, 245

pretty-good-privacy, 238

primality test, 191, 312, 332

deterministic, 118, 123, 232, 332

Prime Number Theorem, 123, 232, 310

Prisoner's Dilemma, 149, 150

Prisoner's Problem, 215, 284

privacy property, 120

private information retrieval, 113, 115, 120, 131, 136, 141

computationally secure, 116

Phi-Hiding scheme, 117, 315, 317

Trojan, 132

unconditionally secure, 116

PRNG, see pseudorandom generator

probabilistic bias removal method, 239, 246

proof of work, 165

pseudonym, 96, 162

pseudorandom function, 234–236

pseudorandom generator, 52, 66–68, 76, 138, 236, 238, 275

ANSI X9.17, 66, 78

BBS, 64, 67, 236

pseudosquare, 136, 312, 336, 348

public key cryptosystem, 325

Cramer-Shoup, 279, 318, 340

ElGamal, 134, 277, 338

Goldwasser-Micali, 229, 315, 335

Paillier, 108, 312, 314, 315

Rabin, 213, 229, 246, 248, 249, 313, 330

RSA, 39, 78, 79, 136, 143, 224, 229, 244, 256, 312, 314, 332

quadratic residuosity assumption, 112, 136, 315, 336

quadratic sieve, 313

quasi-random, 52

query generator, 117, 118, 123, 126

questionable encryption, 102, 134, 138

Rabin-Miller algorithm, 52, 332

race condition, 181

random function, 125, 166, 267, 320

random oracle, 124, 221, 245, 255, 272, 273, 275, 283, 284, 319

assumption, 122, 282

model, 79, 230, 249, 266, 270, 274, 343

random self-reducible, 145

ranking algorithm, 73

reduction argument, 67, 249, 252, 270, 272, 274, 314, 318, 338

reference monitor, 190

relative primality, 216, 250, 333, 353

repeated XOR encryption, 36

residues, 319

higher order, 128, 145, 315

quadratic, 67, 248, 311, 315, 319, 331, 336, 340

response retriever, 117, 120, 124, 127

revocable anonymity, 93

Rivest-Shamir-Adleman cryptosystem, see public key cryptosystem, RSA

rootkit, 203, 354

rotational delay, 54

rotational latency, 54

RSA assumption, 314

safe prime, 195, 340

salami slicing attack, 202

Salt II treaty, 212, 213, 218

Santha-Vazirani algorithm, 62, 64

scanner, 174, 177

secret sharing, 159

secretly embedded trapdoor with universal protection, see SETUP

secure multiparty computation, 144

SecurID, 100

security by obscurity, 98, 215, 291

security kernel, 190

security parameter, 118, 122, 252

selective forgery, 328

semantic security, 49, 79, 101, 315, 336, 340

semaphore, 181

SETUP, 191, 229, 243, 249, 256–258, 261, 263, 265, 268, 276, 283, 288

definition of, 243

SHA-1, see hash function, SHA-1

shadow public key, 225

side channel analysis, 80, 256, 261

Skipjack, see symmetric cipher, Skip-jack

smart card, 219

smooth integer, 144, 223, 286, 318, 354

snake oil, 290, 354

Solovay-Strassen algorithm, 312

sprawl, 6

square-and-multiply, 311

stealth virus, 175, 190

steganography, 96, 101, 133, 215

subliminal channel, 101, 133, 211, 214, 216, 241, 243, 259, 262, 281, 287

card marking using residues, 222

ElGamal signature, 216

history of, 212

impact on research, 226

Legendre channel, 217, 284

Newton channel, 223, 286

Oracle channel, 220, 221

product of primes, 224, 262

sum-of-products method, 130

symmetric cipher, 192, 323

3DES, 30

AES, 67, 322

Black-Rugose, 287

Blowfish, 287, 323

DES, 66

MARS, 287

Monkey, 287

RC4, 323

Skipjack, 286

TEA, 35, 46

Twofish, 323

XTEA, 36

SysBeep virus, 303

tamper-resistance, 219, 230, 276

TEA, see symmetric cipher, TEA

terminate-and-stay resident, 7, 203, 355

threat model, 80, 326

tick, 34

timing attacks, 261, 288

Tiny Encryption Algorithm, see symmetric cipher, TEA

tractable, 112, 248, 317, 354

Tremor virus, 176

Trotter-Johnson algorithm, 73, 179

truerand, 34, 46, 53

tunneling, 188

Twofish, see symmetric cipher, Twofish

unbiasing, 52, 208, 292

uniform sampling, 52, 68

universal gate, 143

universal re-encryption, 84, 153

unranking algorithm, 73, 179

vector addition chains, 34, 311

verifiable encryption, 227

Vernam cipher, 36, 64, 155, 221

worm, 52, 69, 71, 85, 142, 147, 173, 296–298

XEROX PARC, 85

XTEA, see symmetric cipher, XTEA

zero-sum game, 150, 160

ZKIP, 35, 100, 125