General notions about cryptography

Question 1

Symmetric vs Asymmetric Cryptography

Answer 1

Symmetric Ke = Kd

Asymmetric Ke is public and Kd is private

Question 2

Authentication and verification

Answer 2

Athentication  : 
massage => (message ,tag)
ka in K 
Verification 
message = > {message , ⊥}
kv in K 
Symmetric cryptography : 
kv = ka and the tag called mac
Asymmetric crypto 
ka is private and kv is public , tag is called signature

Question 3

perfect screcy :

Answer 3

perfect secrecy :

Pr[Enc(m1)=c] = Pr[Enc(m2)=c]

If |
K| = |
C| = |
P| then the system provides perfect secrecy iff
(1) every key is used with equal probability 1/|
K|, and
(2) for every x
∈ P and y
∈
C, there exists a unique key k
∈
K such that e
k(x) = y

Question 4

perfect secrecy

Answer 4

perfect secrecy => H(k) >= H(M) and key must not be reused
perfect secrecy requires that no info about the message leaked
in practice, a small probability of leaking is allowed

Question 5

Explain computational security

Answer 5

A schema is (t, ϵ )-secure if the adversary manages to break it in t time with probability ϵ
A scheme is (t,ϵ) -kbit secure and log2 t − log2 ϵ(t) ≥ s.

for example the Exhaustive search :
ϵ(t) = t / |k| => key is size of K space
it means S = log2(t / |k|)-bit secure

Question 6

Explain computational security

Answer 6

A schema is (t, ϵ )-secure if the adversary manages to break it in t time with probability ϵ
A scheme is (t,ϵ) -kbit secure and log2 t − log2 ϵ(t) ≥ s.

for example the Exhaustive search :
ϵ(t) = t / |k| => key is size of K space
it means S = log2(t / |k|)-bit secure

according to keckchoff principle : the algorithm should be public and key secret

Question 7

Taxonomy of attacks for Encryption scheme

Answer 7

Exhaustive search : 
goal : recovering the key 
Online Complexity: one pair (cipher text, plain text)
offline complexity : t = | k |
probability success : 1

Question 8

problem with deterministic encryption and solution

Answer 8

the problem with deterministic encryption is that we may fall in a situation where two ciphertexts are similar with the same Key K:
Solution : Nonce : (asymmetric crypto)
Randomized encryption schema

Question 9

IN-CCA secure (chosen cipher text and plain text )

Answer 9

A scheme E = (Gen, Enc, Dec) is IND-CCA-secure if no adversary can win the following game for more than a negligible advantage.
Challenger generates a key (pair) k ← Gen() Adversary queries Enck with plaintexts of his choice and Deck with ciphertexts of his choice
Adversary chooses two plaintexts m0, m1 ∈ M with |m0| = |m1|
Challenger randomly chooses b ←R {0, 1}, encrypts mb and sends c = Enck (mb) to the adversary

Adversary queries Enck with plaintexts of his choice and Deck with ciphertexts of his choice except c

Adversary guesses b ′ which plaintext was encrypted

Adversary wins if b ′ = b (Advantage: ϵ = Pr[win] − 1 2

IND-CCA :
Symmetric: ENCk + DEC;
asymetric : DECk

Question 10

IND-CPA secure (Chosen plain text)

Answer 10

A scheme E = (Gen, Enc, Dec) is IND-CPA-secure if no adversary can win the following game for more than a negligible advantage.
Challenger generates a key (pair) k ← Gen() Adversary queries Enck with plaintexts of his choice Adversary chooses two plaintexts m0, m1 ∈ M with |m0| = |m1|

Challenger randomly chooses b ←R {0, 1}, encrypts mb and sends c = Enck (mb) to the adversary

Adversary queries Enck with plaintexts of his choice

Adversary guesses b ′ which plaintext was encrypted

Adversary wins if b ′ = b (Advantage: ϵ = Pr[win] − 1 2 .)

IND-CPA :
Symmetric: Enck
asymmetric : -

Question 11

Security schema

Answer 11

(t ,d,Є)-scure if adversity with runing time T having access to D data manages to break the ciphey with Є probability

Question 12

Taxanomy of attacks on Authentication schema

Answer 12

Universal forgery attack :
d: submit random time (message, tag) at the complexity of d 
no offline message needed 
probability of success  Є is d/ 2^n 
for n bits