module 7

Question 1

alternative definition of security for PRG

Answer 1

indistinguishability from random

Question 2

indistinguishability

Answer 2

informally: can adversary tell the difference between the output of experiment 1 and the output of experiment 2
formally: does there exist an efficient statistical test that distinguishes between the output of these experiments

Question 3

statistical test

Answer 3

an algorithm A that on input x E {0,1}^n:
outputs 0 when it thinks x is not random
outputs 1 when it thinks x is random

Question 4

advantage

Answer 4

captures how good a statistical test is at differentiating inputs

if advantage is close to 1:
– statistical test behaves differently when given pseudorandom inputs vs random inputs (so it’s good!)

if advantage is close to 0:
– statistical test behaves the same for both (so it is bad!)

Question 5

computational indistinguishability

Answer 5

Question 6

PRG security in terms of indistinguishability

Answer 6

Question 7

semantic security

Answer 7

perfect secrecy is too strong of a definition
– only OTP or its generalizations can satisfy it

SS is an analogue of perfect secrecy against PPT (probabilistic polynomial time) adversaries

definition: given the ciphertext of a message m, no PPT adversary can determine any information about m with probability non-negligibly higher than all PPT adversaries that only have access to m’s length

Question 8

semantic security is hard to work with, so instead we work with a definition of security that is equivalent to SS, but that is based on indistinguishability. This is called ____.

Answer 8

ciphertext indistinguishability against chosen plaintext attackers (IND-CPA)

Question 9

IND-CPA

Answer 9

assumes that the adversary:

• is computationally-bounded (weaker than perfect secrecy)
• picks the plaintexts to be encrypted

approach

• indistinguishability def requires 2 distributions from which to distinguish
• construct a challenger that will output from one of two distributions
• ask whether adversary can distinguish between the two

Question 10

IND-CPA Security Game

Answer 10

Question 11

How do we define if a cryptosystem is secure using the IND-CPA game?

Answer 11

Question 12

how do cryptographic reduction proofs work?

Answer 12

*useful to establish that if cryptographic object X is secure, then cryptographic object Y is also secure

typically work by contradiction

• assume Y is not secure. then show how the attack of Y can also break X
• since X is secure, attacker of Y cannot break Y (contradiction)

Question 13

properties of cryptographic hash functions

Answer 13

1. pre-image resistance
   given a digest y, it is computationally hard for a PPT adversary to find any x such that H(x) = y
2. second pre-image resistance
   give x1 it is computationally hard for a PPT adversary to find a different x2 (x1 != x2) such that H(x1) = H(x2)
3. collision resistance
   it is hard for a PPT adversary to find any two values x1, x2, (x1 != x2) such that H(x1) = H(x2)

Question 14

proof that collision resistance implies second pre-image resistance

Answer 14