module 8 Flashcards
What is a multiplicative cyclic group?
- a set with an identity element and closed under multiplication
- a set where all elements are generated by a single element (the generator)
The discrete log assumption is that when p is a large prime, it is very hard to determine k given only G, p, g, and h. What do we mean by very hard?
We do not know any algorithm capable of computing discrete logs in polynomial time (in the size of the group)
Explain the concrete generator from Blum-Micala
Let p be a very large prime and g be a generator of the group. We have this group; the group of integers mod p in the multiplicative subgroup. We’re going to sample the seed of the PRG by just sampling an element uniformly from this group.
One thing to point out about those multiplicative cyclic groups is that if the exponent is chosen uniformly at random, then observe that the generator has equal probability of generating any value in the set or in the group. If the exponent is sampled uniformly at random, then so is the element that we’re picking. So is the corresponding element that we’re generating. That’s going to be the key intuition for why the Blum-Micali PRG is correct.
The way it works is that it basically goes from zero to whatever position you’re asking for. It basically takes the generator of the group and it raises it to x_i. So x_i is going to be initially x_0, so which is the seed mod p, and remember the seed is uniform, is chosen uniformly, which means this g^x_i mod p is going to be uniform in all the elements in the group. Which means this x_i plus 1 is going to be uniformly at random from the elements in the group. You’re going to repeat this operation position times. Once you’re done, what you’re going to say is if the value that you got after doing this position times is less than or equal to p minus 1/2, then return one, otherwise return zero. You’re going to return one bit, which is either one or zero. The idea is that because the output of doing this g^xi is going to be uniformly random if the exponent is uniformly random, and we’re doing this a bunch of times, then the final result x_pos has equal probability of being 1, or 2, or 3, or 4, or 5, or 6, or 7, or p/2 or p minus 1/2, it has equal probability to be any element in the group. Therefore, you have equal probability of getting a one or a zero. What Blum-Micali show, and I’m not going to go into this in this video because its way outside the scope of this video, is that if the discrete logarithm problem is hard, so if the assumption holds, then this pseudorandom generator then I’m showing you here, is secure. In the sense that an adversary won’t be able to predict the next bit with non-negligible probability or none negligible advantage.
What is a random oracle?
on a given input, RO outputs a uniformly random value
it is deterministic with respect to a given input y1=RO(x1) y2=RO(x2) if y1 = y2 then we know that x1=x2 --> y1=y2
Why does pre-image resistance not imply random output?
(pre-image resistance: given y, hard to find any x such that H(x) = y)
so we might think that if we cannot determine what preimage produced y, then it must be produced uniformly at random
not the case!
proof strategy:
• assume pre-image resistance implies output is uniformly random
• suppose you have a pre-image resistant hash function H
• define another hash function H’(x) = first bit of x || H(x)
• claim: if H is preimage resistant, then so is H’ (try to prove this claim)
• we can’t! the output of H’ depends on x, so it is not uniformly random
Does collision resistance imply random output?
No. Use proof of contradiction.
What is a pseudorandom function?
a PRF is defined over (K, X, Y)
f: K x X –> Y
such that there exists an efficient algorithm to evaluate F(k,x)
What do we mean when we say that a PRF is a “family” of functions indexed by key?
How do we define a PRF to be secure?
A PRF F is secure if a random function from the PRF family is computationally indistinguishable from random function from X to Y (random oracle)
How do we define a PRF to be secure?
A PRF F is secure if a random function from the PRF family is computationally indistinguishable from random function from X to Y (random oracle)
Explain the PRF Security game
a PRF is secure if for all PPT A:
Adv_PRF{A,F} <= neglibible
why is the block cipher in ECB mode not semantically secure?
the big problem is that a PRP is deterministic.
this means that a block cipher in ECB mode is not semantically secure because we have the same two plaintexts then we will get the same ciphertext. in semantic security we should not be able to tell which plaintext you encrypted.
