Intro Flashcards
(47 cards)
1
Q
Definition of perfect security, shannon theorem and (t-epsilon) security
A
2
Q
Definition of computational security
A
3
Q
Definition of negligible function
A
4
Q
Definition of complexity
A
5
Q
Definition of polynomial time algo
A
6
Q
Cobham-Edmond thesis and extended thesis
A
7
Q
Definition of probabilistic algorithm
A
8
Q
Definition of probabilistic polynomial time algorithm
A
9
Q
Expected PPT algorithm
A
10
Q
Definition of group
A
11
Q
Definition of subgroup
A
12
Q
Definition of cyclic group
A
13
Q
Order of a group and order of the generator
A
14
Q
Lagrange Theorem about the order of a group
A
15
Q
Definition of ring
A
16
Q
Definition of field
A
17
Q
Homomorphism for a group and for a ring
A
18
Q
Equality mod n
A
19
Q
Ring of integers mod n
A
20
Q
Invertible number
A
21
Q
Multiplicative group of integers mod n
A
22
Q
Euler’s Theorem
A
23
Q
CRT
A
24
Q
Definition of finite field
A
25
Factoring assumption: definition, generation, experiment
26
RSA assumption: definition, generation, experiment
27
Relation between RSA and Factoring assumption, proof
28
DL assumption: definition, generation, experiment
29
Lemma: DL random self reduction and proof
30
DH assumption: definition, generation, experiment
31
Implications of DH assumption and proof
32
Definition of quadratic residue
33
Definition of Legendre symbol
34
Euler’s criterion
35
Jacobi symbol
36
What’s the difference relative to QR if p is prime or not?
numero radici e numero di elementi in QR e QNR
37
Quadratic Residuosity Problem, assumption and experiment
38
Implications between QR assumption and DCR assumption
39
Decisional Composite Residuosity Assumption
40
Perfect, statistical and computational indistinguishability, relationship and proofs
41
Assumptions with respect to indistinguishability
42
Exercise 1.
Provide an equivalent definition of the Decisional Diffie-Hellman Assumption by using an experiment that outputs 0 or 1.
b*xy + (1-b)*z
43
Exercise 3.
Prove that for the cyclic group (Zp,+) (p prime) with generator g (so g is an integer not divisible by p) the Discrete Logarithm Assumption is false.
ng e inverso g^-1
44
Exercise 4.
Can the following problem be solved in polynomial time? Given a prime p, a value x∈Z∗p−1 and y=gx mod p, where g←$Z∗p, find g.
x*x^-1
45
Exercise 5.
Provide a random self-reduction for the RSA Problem with fixed modulo N.
x^e^f
46
Exercise 6
Show that the DDH assumption for cyclic groups of even order is
false.
(Hint: notice that, when the order n is even, given (g, gx), then x is even ⇐⇒ xn
g2 =1)
check corretta parità di z
47
Exercise 7.
Consider a cyclic group G of prime order q (q odd) generated by g. Show that the following problems are poly-time equivalent:
* The CDH problem;
* Given g^α, compute g^α^2 (square problem SP).
