Week 7

Question 1

What is the ideal way to think about unpredictability that applies across cryptosystems?

Answer 1

Indistinguishability from Random

Question 2

What does Indistinguishability from Radnom mean?

Answer 2

The adversary should not be able to tell the difference between the output of a PRG, and the output of a truly random source of randomness.

Question 3

Explain the experiment for Indistinguishability from Random.

Answer 3

We have two boxes holding an n-bit string each.

One holds a string generated by a PRG using a seed sampled uniformly at random, one is a truly random string sampled uniformly at random from the set of all n-bit strings.

The truly random n-bit string comes from a set of 2ⁿ elements. The PRG produces a string from a smaller blue set which is a subset. It’s smaller because the PRG is deterministic and can’t produce any possible string.

Our adversary knows the function G() to produce the strings, so he wants to test it on all possible inputs to figure out all strings in the subset for the PRG so he can determine if some random string is in that set, or if it’s really a truly random string. BUT, he is computationally bounded and cannot calculate all of them.

So, indistinguishability basically asks if the adversary can determine if the string he is looking at is from the subset produced by the PRG, or from the complement (truly random).

Question 4

What is the output of a statistical test when determining if a string is random?

Answer 4

Statistical tests here are some algorithm A that predicts whether a string is generated by a PRG or truly random.

They output 0 if they think the n-bit string is NOT random, and 1 if they think the string IS random.

Question 5

What is an example of a statistical test for predicting whether a string is random or from a PRG?

Answer 5

A test that…

Outputs 1 IFF the absolute value of the number of 0’s - the number of 1’s is less than some value like 10 * sqrt(n).

This statistical test is useful because in general, we expecy that strings that are sampled uniformly will have roughly the same number of 0’s and 1’s. So, if a given output is very far away from that distribution, then the test will say that the string is not random.

See image for examples.

Question 6

What is the downside of statistical tests?

Answer 6

They are not always right. They can be arbitrarily wrong.

These tests are written and customized for a specific generator.

Question 7

How do we know if a statistical test is good? How do we measure goodness?

Answer 7

We measure goodness of a statistical test using the same advantage measurement from before.

Question 8

How do we define advantage mathematically?

Answer 8

The advantage of the PRG distinguishing game, when we use the specific statistical test A for this specific PRG G, we say the advantage is equal to, the absolute value of the difference of the probability that the statistical test predicts that the output is random - the probability that the statistical test predicts that a uniformly sampled random string is random.

If you have a statistical test that always says everything is random, this difference will be 0.

Question 9

How do we interpret the advantage we obtain from a given statistical test? When is it good? When is it bad?

Answer 9

If the advantage is close to 1, then the statistical test behaves differently when given pseudorandom input vs. random input. When the advantage is close to 1, we say it’s a GOOD statistical test.

When the advantage is close to 0, the test behaves basically the same for pseudorandom input as it does for truly random input. When the advantage is close to 0, we say that it’s a BAD statistical test.

Question 10

Worked out example of calculating and interpreting advantage.

Answer 10

Question 11

What is Computational Indistinguishability?

Answer 11

There are two types of indistinguishability. In statistical indistinguishability, the adversary can be computationally unbounded. He can run tests that take an arbitrary amount or time to run.

There is also computational indistinguishability in which we assume the adversary is computationally bounded and can only run statistical tests that run in polynomial time (even if it’s a crazy polynomial run time).

Question 12

How do we apply the concept of computational indistinguishability to two distributions P1 and P2 which are distributions over the set of n-bit strings?

Answer 12

We can then say that they are computationally indistinguishable if for every possible efficient statistical test, the probability that the statistical test can tell whether the input comes from P1 or P2 is going to be negligible.

The two distributions are computationally indistinguishable if there doesn’t exist a statistical test that is efficient and can distinguish the two. The advantage is negligible.

Question 13

How do we determine security in terms of indistinguishability for a PRG?

Answer 13

A PRG G is secure if the distribution that results from sampling k uniformly and then running G on (k) (creating a distribution since G() is a random variable) is indistinguishable from the uniform distribution {0,1}n.

So if the distribution that the PRG generates is indistinguishable from a uniform distribution by any efficient statistical test, then the PRG is secure. It’s as good as sampling uniformly from a uniform distribution.

Question 14

What is Next-Bit-Unpredictability?

Answer 14

It is equivalent to indistinguishability from random.

If you have an algorithm that can predict the next bit, you can use it to predict a statistical test that can then distinguish between the PRG string and a random string. You do this by using your predictor to try and predict the next bit in the output string. If your predictor is right, then you have high probability that the output is from a PRG, if you’re wrong, then maybe it’s from a truly random sample.

A hardwe wat to do this is to use a statistical test to build a bit predictor.

Question 15

What is Semantic Secrecy (SS)?

Answer 15

This is a notion of secrecy for modern Crypto Systems.

It means that given a ciphertext of a message m, no Probabilistic, Polynomial-time (PPT) Adversaries can determine any information about m with probabilityt non-negligible higher than all PPT adveraries that onlt have access to m’s length.

In other words, the adversary can’t learn anything other than the length of the message.

Question 16

What is IND-CPA?

Answer 16

It is a computational indistinguishability definition. We assume that the adversary is computationally competent. It means the adversary is allowed to choose the plaintext that is going to be encrypted and then he will need to distinguish from it.

We will assume the attacker can encrypt their own message and then try to tell which message was encrypted out of some random strings.

Question 17

How does the IND-CPA security game work?

Answer 17

1. The Challenger is an algorithm which outputs from one of the two distributions. We give the challenger an advantage which is that it is given a secret key sampled from the key space.
2. Both the adversary and the challenger know the encryption and decryption function, and the key space, message space, and cipher space.
3. The adversary then picks two messages he wants the challenger to encrypt from the message space (both of same length).
4. Then a coin is flipped with outcome b. If b is 0, the challenger encrypts M0, if b is 1, the challenger encrypts M1. It encrypts with the hidden key.
5. The encrypted message is then sent to the adversary. He must determine which of his messages was encrypted. If he guesses correctly, he wins.

Question 18

What is the use of the IND-CPA Security Game?

Answer 18

It is useful for capturing the advantage an adversary has by taking the probability that he is right minus 1/2.

The difference is his advantage.

Question 19

When do we say a cipher is Semantically Secure?

Answer 19

If for all efficient adversaries, the advantage that the adversary has in the IND-CPA game is negligible. If it’s negligible, we say the adversary really can’t distinguish.

Question 20

What is the style of proof we use to prove that if a PRG is secure, so is the Stream Cipher that uses it?

Answer 20

A reduction proof that works by contradiction, probing that if some cryptographic object X is secure, then another cryptographic object Y is also secure.

We assume that Y is not secure. Then we show how the attacker of Y can also break X with some repurposing of the strategy that broke Y. BUT, since X is securem the attacker of Y cannot break Y.

Question 21

What is a Hash Function?

Answer 21

A function that maps from an arbitrarily large set to a fixed-size set.

The size of the large set we start with is of size * and the fixed-size set is of size N.

Because we are mapping to a smaller set, there will inevitably be collisions (by the pigeonhole principle).

Question 22

What is the Preimage Resistance Property?

Answer 22

It means that given a hash digest y, it is computationally hard for a PPT adversary to find any x such that H(x) hashes to y.

Question 23

What is the Second Preimage Resistance Property?

Answer 23

Given one preimage x₁, it is computationally hard for a PPT adversary to find a different preimage x₂ that hashes to the same digest/image.

Question 24

What is the Collision Resistance Property?

Answer 24

Given that there are many collisions, it should be hard for a PPT adversary to find any two values x₁ and x₂ such that H(x₁) = H(x₂).

Question 25

State the proof that if a hash function is collision resistant, it is also second preimage resistant.

Answer 25

It is a proof by contradiction.

Assume that the hash function is collision resistant but not second-preimage resistant.

The attacker can choose an arbitrary m₁ and get the image. Then the attacker can take a second m₂ and get the same image as m₁. By definition of second pre-image, we have that H(m₁) = H(m₂). BUT, this would mean that the hash function is not collision resistant, which is a contradiction.

Question 26

Name one application of cryptographic hash functions.

Answer 26

One example is say you have a giant file or movie and you upload it to the cloud, but you keep a digest of it. You can then download the file later in the future and you can check that it wasn’t modified by checking the digest when you rehash the file once it was downloaded. This works because it is very difficult for there to be some other file that hashes to the same thing if the hash function is collision resistant. Someone can’t modify your video so that it still hashes to the same digest/image.