This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.
author: burton rosenberg
created: 26 oct 2019
update: 27 oct 2019
If mathematics is a body of knowledge, then logic is its illness. –burt
Mathematics is congenitally incapable of embarrassment. –burt
Notation, and the numbers for definitions, theorems and constructions from the 2nd edition of Katz and Lindell, Introduction to Modern Cryptography.
PRIVATE KEY
PrivKCCA (Def 3.33)
|
| a maleable encryption
|
PrivKLR-cpa (Def 3.23)
|
| no gap: ⊢ Thm 3.24
|
PrivKCPA (Def 3.22)
|
| gap: E_k(m) = [r,m+E_k(r),E_k(~r)] ?
| Query E_k(~r) = [r',~r+E_k(~r),E_k(r)],
| use E_k(r) to go back to previous
| note: attack must be adaptive
|
PrivKmult (Def 3.19)
|
| gap: ⊢ Thm 3.21 (stateless and deterministic)
|
PrivKeav (Def 3.8)
|
| pseudorandom function
|
Perfect secrecy
ex: Vernon Cipher
PUBLIC KEY
PPT Gen, Enc and Dec such that:
Gen(1n) ⇒ (pk,sk)
Enc(pk,m) ⇒ c
Dec(sk,c) ⇒ m
* Correctness:
Pr[ { (pk,sk)⇐Gen | Dec∘Enc is the identity } ] > 1 - negl(n)
* Dec can be deterministic
PubKCCA
|
| E_pk(m) = [E_pk(r),r+m]
|
PubKLR-cpa
|
| no gap
|
PubKCPA
|
| no gap
|
PubKmult
|
| no gap
|
PubKeav
|
*****
|
Perfect secrecy
not possible
try Gen until (pk,sk) appears
KEM/DEM KEM DEM
by Cons. 11.10
PubKCCA KEMCCA ⟺ PrivKCCA ⊢ Thm 11.14
| | |
| | |
| | |
PubKCPA KEMCPA ⟺ PrivKeav ⊢ Thm 11.12
Digital Signature
PPT Gen, Sign and Vrfy such that:
Gen(1n) ⇒ (pk,sk)
Sign(sk,m) ⇒ σ
Vrfy(pk,m,σ) a predicate
* Correctness:
Pr[ { (pk,sk) ⇐ Gen(n) | Vrfy(pk,m,Sign(sk,m)) } ] > 1 - negli(n)
* Vrfy can be deterministic.
Sig-forgeA,π(n)
author: burton rosenberg
created: 26 oct 2019
update: 27 oct 2019