Introduction To Modern Cryptography
本文最后更新于 2022年11月21日 晚上
Introduction To Modern Cryptography 这本书英文原版的前两章笔记
Introduction To Modern Cryptography
Introduction and Classical Cryptography
Introduction
The Setting of PrivateKey Encryption

The syntax of encryption
 message space: M
 three algorithms:
 Gen
 key space: K
 Enc
 Dec
 Gen
 for every key k output by Gen and every message $m\in M$, it holds that $Dec_k(Enc_k(m))=m$.

Keys and Kerckhoff’s principle
The cipher method must not be required to be secret, and it must be able to fall into the hands of the enemy without inconvenience.
 It is significantly easier for the parties to maintain secrecy of a short key than to keep secret the algorithm they are using.
 it will be much easier for them to change a key than to replace an encryption scheme.
 for largescale deployment it is significantly easier for users to all rely the same encryption algorithm.
Historical Ciphers and Their Cryptanalysis

Caesar’s cipher: shift the letters of the alphabet
 ROT13 is still used nowadays, merely used to ensure the text is unintelligible.

Sufficient keyspace principle
Any secure encryption scheme must have a key space that is sufficiently large to make an exhaustivesearch attack infeasible.
 this is only true if the message space is larger than the key space.

The monoalphabetic substitution cipher
 attack relies on average letter frequencies
 $\sum_{i=0}^{25}p_i^2\approx0.065=\sum_{i=0}^{25}p_i\cdot q_{i+j}$

The Vigenere(polyalphabetic shift) cipher
 the character frequencies are “smoothed out”
 attack: tabulate the frequency of each ciphertext character for each stream; Kasiski’ method; index of coincidence method
Principles pf Modern Cryptography
Principle 1 , Formal Definitions

a threat model & a security goal

An example: secure encryption
 Wrong answers
 it should be impossible for an attack to recover the key.
 it should be impossible for an attack to recover the entire plaintext from the ciphertext.
 it should be impossible for an attacker to recover any character of the plaintext from the ciphertext.
 Right answer
 regardless of any information an attacker already has, a ciphertext should leak no additional information about the underlying plaintext.
 Wrong answers
Principle 2 , Precise Assumption
 Reasons
 mathematical proofs require this
 Validation of assumptions
 Comparison of schemes
 Understanding the necessary assumptions
Principle 3 , Proofs of Security
Perfectly Secret Encryption

Generating randomness:
 collect a “pool” of highentropy data
 process the data to yield a sequence of nearly independent and unbiased bits

rand() function in the C library is not cryptographically secure.
Definitions

perfectly secret
An encryption scheme with message space $M$ is perfectly secret if for every probability distribution over $M$, every message $m \in M$, and every ciphertext $c \in C$ for which $\Pr[C=c]>0$ :
$\Pr[M=mC=c]=\Pr[M=m]$

an equivalent formulation of perfect secrecy
For every $m,m\in M$, and every $c\in C$, $\Pr[Enc_K(m)=c]=\Pr[Enc_K(m')=c]$.

The adversarial indistinguishability experiment $PrivK^{eav}_{A,\Pi}$
 The adversary $\mathcal{A}$ outputs a pair of messages $m_0,m_1\in M$.
 A key $k$ is generated using Gen, and a uniform bit $b\in \left\{0,1\right\}$ is chosen. Ciphertext $c \leftarrow Enc_k(m_b)$ is computed and given to $\mathcal{A}$. We refer to $c$ as the challenge ciphertext.
 $\mathcal{A}$ outputs a bit $b'$.
 The output of the experiment is defined to be 1 if $b'=b$, and 0 otherwise. We write $PrivK^{eav}_{\mathcal{A},\Pi}=1$ if the output of the experiment us 1 and in this case we say that $A$ succeeds.

Perfectly indistinguishable
Encryption scheme $\Pi=(Gen,Enc,Dec)$ with message space $M$ is perfectly indistinguishable if for every $\mathcal{A}$ it holds that $\Pr[PrivK_{\mathcal{A},\Pi}^{eav}=1]=\frac{1}{2}$

Encryption scheme $\Pi$ is perfectly secret if and only if it is perfectly indistinguishable.
The OneTime Pad
 The onetime pad encryption scheme is perfectly secret.
 The key is as long as the message.
 The same key can be used only once.
Limitations of Perfect Secrecy
 If (Gen, Enc, Dec) is a perfectly secret encryption scheme with message space $M$ and key space $K$, then $K ≥ M$.
Shannon‘s Theorem*

Shannon’s theorem
Let (Gen,Enc,Dec) be an encryption scheme with message space $M$, for which $M=K=C$. The scheme is perfectly secret if and only if:
 Every key $k\in K$ is chosen with equal probability $1/K$ by algorithm Gen.
 For every $m\in M$ and every $c\in C$, there exists a unique key $k\in K$ such that $Enc_k(m)$ outputs c.
※：The theorem only applies` when $M=K=C$
PrivateKey (Symmetric) Cryptography
PrivateKey Encryption
Computational Security
 Computational security incorporates two relaxations relative to information theoretic notions of security
 Security is only guaranteed against efficient adversaries that run for some
feasible amount of time.  Adversaries can potentially succeed with some very small probability.
 Security is only guaranteed against efficient adversaries that run for some
The Concrete Approach
 A scheme is $(t,\varepsilon)$secure if any adversary running for time at most t succeeds in breaking the scheme with probability at most $\varepsilon$.
The Asymptotic Approach

A scheme is secure if any ppt adversary succeeds in breaking the scheme with at most negligible probability.

A function f from the natural numbers to the nonnegative real numbers is negligible if for every positive polynomial $p$ there is an $N$ such that for all integers $n>N$ it holds that $f(n)<\frac{1}{p(n)}$.
 $negl_1$ and $negl_2$ are negligible functions. Then,
 $negl_3(n)=negl_1(n)+negl_2(n)$ is negligible.
 $negl_4(n)=p(n)\cdot negl_1(n)$ is negligible.
 $negl_1$ and $negl_2$ are negligible functions. Then,
Necessity of the Relaxations
 If we wish to encrypt many messages using a single short key, security can only be achieved if we limit the running time of the adversary.
Defining Computationally Secure Encryption
 A privatekey encryption scheme is a tuple of probabilistic polynomialtime algorithm (Gen, Enc, Dec) such that:
 The Gen takes as input $1^n$ and outputs a key $k$; we write $k\leftarrow Gen(1^n)$. We assume without loss of generality that any key $k$ output by $Gen(1^n)$ satisfies $k\geq n$.
 The Enc takes as input a key $k$ and a plaintext message $m\in\left\{0,1\right\}^*$, and output a ciphertext $c$. Since Enc may be randomized, we write this as $c\leftarrow Enc_k(m)$.
 The Dec take as input a key $k$ and a ciphertext $c$, and outputs a message $m$ or an error. We assume that Dec is deterministic, and so write $m:=Dec_k(c)$. We denote a generic error by the symbol $\perp$ .
The adversarial indistinguishability experiment
 The adversary $\mathcal{A}$ is given input $1^n$, and outputs a pair of messages $m_0,m_1$ with $m_0=m_1$.
 A key $k$ is generated by running $Gen(1^n)$, and a uniform bit $b\in\left\{0,1\right\}$ is chosen. Ciphertext $c\leftarrow Enc_k(m_b)$ is computed and given to $A$. We refer to $c$ as the challenge ciphertext.
 $A$ outputs a bit $b'$
 The output of the experiment is defined to be 1 if $b'=b$, and 0 otherwise. If $PrivK^{eav}_{A,\Pi}(n)=1$, we say $\mathcal{A}$ succeeds.
Indistinguishable encryption in the presence of an eavesdropper/EAVsecure
 Definition 1: For all probabilistic polynomialtime adversaries $\mathcal{A}$ there is a negligible function $negl$ such that, for all $n$, $\Pr[PrivK_{\mathcal{A},\Pi}^{eav}(n)=1]\leq\frac{1}{2}+negl(n)$.
 Definition 2: For all PPT adversaries $\mathcal{A}$ there is a negligible $negl$ such that $\Pr[out_{\mathcal{A}}(PrivK_{\mathcal{A},\Pi}^{eav}(n,0))=1]\Pr[out_{\mathcal{A}}(PrivK_{\mathcal{A},\Pi}^{eav}(n,1))=1]\leq negl(n)$
Encryption and Plaintext Length
 Sometimes leaking the plaintext length is problematic
 Simple numeric/text data
 Autosuggestions
 Database searches
 Compressed data
Semantic Security*

A privatekey encryption scheme (Enc, Dec) is semantically secure in the presence of an eavesdropper if for every PPT algorithm $\mathcal{A}$ there exists a PPT algorithm $\mathcal{A}^{\prime}$ such that for any PPT algorithm Samp and polynomialtime computable functions $f$ and $h,$ the following is negligible:
$\left\operatorname{Pr}\left[\mathcal{A}\left(1^{n}, \operatorname{Enc}_{k}(m), h(m)\right)=f(m)\right]\operatorname{Pr}\left[\mathcal{A}^{\prime}\left(1^{n},m, h(m)\right)=f(m)\right]\right$
where the first probability is taken over uniform $k \in\{0,1\}^{n}, m$ output by
$\operatorname{Samp}\left(1^{n}\right),$ the randomness of $\mathcal{A},$ and the randomness of Enc, and the second probability is taken over $m$ output by $\operatorname{Samp}\left(1^{n}\right)$ and the randomness of $\mathcal{A}^{\prime}$. 
A privatekey encryption scheme has indistinguishable encryptions in the presence of an eavesdropper if and only if it is semantically secure in the presence of an eavesdropper.
Constructing Secure Encryption Schemes
Pseudorandom Generators and Stream Ciphers
 For any efficient statistical test D, the probability that D returns 1 when given the output of the pseudorandom generator should be close to the probability that D returns 1 when given a uniform string of the same length.
 Pseudorandomness is computational relaxation of true randomness.
 Considering only polynomialtime observers,a pseudorandom string is just as good as a uniform string.
 Let $l$ be a polynomial and let $G$ be a deterministic polynomialtime algorithm such that for any $n$ and any input $s\in\left\{0,1\right\}^n$ , the result $G(s)$ is a string of length $l(n)$. We say that $G$ is a pseudorandom generator if the following conditions hold:
 (Expansion:) For every $n$ it holds that $l(n)>n$
 (Pseudorandomness:) For any PPT algorithm $D$, there is a negligible function $negl$ such that $\Pr[D(G(s))=1]\Pr[D(r)=1]\leq negl(n)$, where the first probability is taken over uniform choice of $s\in\left\{0,1\right\}^n$ and the randomness of $D$, and the second probability is taken over uniform choice of $r\in\left\{0,1\right\}^{l(n)}$ and the randomness of $D$.
 We call $l$ the expansion of $G$.
 Stream Ciphers: (Init, GetBits)
 Init
 Input: seed $s$, optional initialization vector $IV$
 Output: initial state $st_0$
 GetBits
 Input: state $st_i$
 output： a block of several bits $y$, updated state $st_{i+1}$
Proofs by Reduction

A security reduction is a particular type of mathematical proof that some cryptographic primitive or protocol is secure, in the sense that it is “at least as difficult to break” as some other problem believed to be hard.

A proof that some cryptographic construction $\Pi$ is secure proceeds via the following steps:
 Fix some efficient adversary $\mathcal A$ attacking $\Pi$. Denote the $\mathcal A$ 's success probability by $\varepsilon(n)$.
 Construct an efficient algorithm $\mathcal A'$, called the “reduction”, that attempts to solve problem $X$ using $\mathcal A$ as a subroutine. And $\mathcal A'$ knows noting about how $\mathcal A$ works and only knows $\mathcal A$ is expecting to attack $\Pi$. So, given some input instance $x$ of $X$ , $\mathcal A'$ will simulate for $\mathcal A$ an instance of $\Pi$ such that:
 (a) As far as $\mathcal A$ can tell, it is interacting with $\Pi$. That is, the view of $\mathcal A$ when run as a subroutine by $\mathcal A'$ should be distributed identically to the view of $A$ when it interacts with $\Pi$ itself.
 (b) If $\mathcal A$ succeeds in “breaking” the instance of $\Pi$ that is being simulated by $\mathcal A'$, this should allow $\mathcal A'$, this should allow $\mathcal A'$ to solve the instance $x$ is was given, at least with inverse polynomial probability $1/p(n)$
 Taken together, (a) and (b) imply that $\mathcal A'$ solves $X$ with probability $\varepsilon(n)/p(n)$, if $\varepsilon(n)$ is not negligible. Moreover, if $\mathcal A$ is efficient then we obtain an efficient algorithm $\mathcal A'$ solving $X$ with nonnegligible probability, contradicting the initial assumption.
 Given our assumption regarding $X$, we conclude that no efficient adversary $\mathcal A$ can succeed in breaking $\Pi$ with nonnegligible probability. Stated differently , $\Pi$ is computationally secures.
An instance for Reduction $\mathcal A'$——Distinguisher D
 D is given as input a string $\omega\in\left\{0,1\right\}^{l(n)}$.
 Run $\mathcal A(1^n)$ to obtain a pair of messages $m_0,m_1\in\left\{0,1\right\}^{l(n)}$
 Choose a uniform bit $b\in\left\{0,1\right\}$. Set $c:=\omega \oplus m_b$
 Give $c$ to $\mathcal A$ and obtain output $b'$, Output 1 if $b'=b$, and 0 otherwise.
Stronger Security Notions
Security for Multiple Encryptions
The multiplemessage eavesdropping experiment $Priv_{\mathcal A,\Pi}^{mult}(n)$
 The adversary $\mathcal A$ is given input $1^n$, and outputs a pair of equallength lists of messages $M_0=(m_{0,1},\dots,m_{0,t})$ and $M_1=(m_{1,1},\dots,m_{1,t})$, with $m_{0,i}=m_{1,i}$ for all $i$.
 A key $k$ is generated by running $Gen(1^n)$, and a uniform bit $b\in \left\{0,1\right\}$ is chosen. For all $i$, the ciphertext $c_i\leftarrow Enc_{k}(m_{b,i})$ is computed and the list $C=(c_1,\dots,c_t)$ is given to $\mathcal A$
 $\mathcal A$ outputs a bit $b'$
 The output of the experiment is defined to be 1 if $b=b'$, and 0 otherwise.
Indistinguishable multiple encryptions in the presence of an eavesdropper
 For all probabilistic polynomialtime adversaries there is a negligible function $negl$ such that $\Pr[Priv_{\mathcal A,\Pi}^{mult}(n)]\leq\frac{1}{2}+negl(n)$.
※：There is a privatekey encryption scheme that has indistinguishable encryption in the presence of an eavesdropper, but not indistinguishable multiple encryption in the presence of an eavesdropper. For example: the encryption scheme is deterministic.
ChosenPlaintext Attacks and CPASecurity
 encryption oracle: a “black box” that encrypts messages of $\mathcal A$’s choice using a key $k$ that is unknown to $\mathcal A$. $\mathcal A$ can interact with the oracle as many times ad it likes and query the reply of the oracle.
The CPA indistinguishability experiment $PrivK_{\mathcal A,\Pi}^{cpa}(n)$

A key $k$ is generated by running $Gen(1^n)$.

The adversary $\mathcal A$ is given input $1^n$ and oracle access to $Enc_k(·)$, and outputs a pair of messages $m_0, m_1$ of the same length.

A uniform bit $b\in\left\{0, 1\right\}$ is chosen, and then a ciphertext $c \leftarrow Enc_k(m_b)$ is computed and given to $\mathcal A$.

The adversary continues to have oracle access to $Enc_k(·)$, and outputs a bit $b'$.

The output of the experiment is defined to be 1 if $b' = b$, and 0 otherwise. In the former case, we say that $\mathcal A$ succeeds.
CPAsecure

For all probabilistic polynomialtime adversaries $\mathcal A$ there is a negligible function $negl$ such that $\Pr[Priv_{\mathcal A,\Pi}^{cpa}(n)]\leq\frac{1}{2}+negl(n)$.

Any privatekey encryption scheme that is CPAsecure is also CPAsecure for multiple encryptions.
Constructing CPASecure Encryption Schemes

Pseudorandom function: Let $F: \left\{0,1\right\}^*\times\left\{0,1\right\}^*\rightarrow \left\{0,1\right\}^*$be an efficient, lengthpreserving, keyed function. $F$ is a pseudorandom function if for all probabilistic polynomialtime distinguishers $D$, there is a negligible function $negl$ such that: $\Pr[D^{F_K(\cdot)}(1^n)=1]\Pr[D^{f(\cdot)}(1^n)=1]\leq negl(n)$.
 size: $Func_n=2^{n*2^n}$