Intro Flashcards
Definition of perfect security, shannon theorem and (t-epsilon) security
Definition of computational security
Definition of negligible function
Definition of complexity
Definition of polynomial time algo
Cobham-Edmond thesis and extended thesis
Definition of probabilistic algorithm
Definition of probabilistic polynomial time algorithm
Expected PPT algorithm
Definition of group
Definition of subgroup
Definition of cyclic group
Order of a group and order of the generator
Lagrange Theorem about the order of a group
Definition of ring
Definition of field
Homomorphism for a group and for a ring
Equality mod n
Ring of integers mod n
Invertible number
Multiplicative group of integers mod n
Euler’s Theorem
CRT
Definition of finite field
Factoring assumption: definition, generation, experiment
RSA assumption: definition, generation, experiment
Relation between RSA and Factoring assumption, proof
DL assumption: definition, generation, experiment
Lemma: DL random self reduction and proof
DH assumption: definition, generation, experiment
Implications of DH assumption and proof
Definition of quadratic residue
Definition of Legendre symbol
Euler’s criterion
Jacobi symbol
What’s the difference relative to QR if p is prime or not?
numero radici e numero di elementi in QR e QNR
Quadratic Residuosity Problem, assumption and experiment
Implications between QR assumption and DCR assumption
Decisional Composite Residuosity Assumption
Perfect, statistical and computational indistinguishability, relationship and proofs
Assumptions with respect to indistinguishability
Exercise 1.
Provide an equivalent definition of the Decisional Diffie-Hellman Assumption by using an experiment that outputs 0 or 1.
bxy + (1-b)z
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
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
Exercise 5.
Provide a random self-reduction for the RSA Problem with fixed modulo N.
x^e^f
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
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).
