数据安全与密码学基础 Cheatsheet & Homework

Reference & Analysis#

Cheatsheet#

我最后尝试画一个知识树

Crypto fundation#

Secure Multi-Party Computation#

Shannon/Perfect Privacy#

One Time pad#

One-way function#

PRG#

PRFs#

PRP#

密码学作业#

第一次作业 One Time Pad & OWF & PRG#

Question 1: A Flawed One-Time Pad#

Description
Consider a variant of the one-time pad with message space $\{0, 1\}^n$ , where $n$ is an odd integer, and the secret key space is restricted to all $n$ -bit strings with an even number of 1’s. Construct an efficient adversary that compromises perfect secrecy.

Answer:

Let the key set be denoted by $K$ : $|K|=\sum _{i=0}^{n-1}\binom{n}{i}=2^{n-1}$

For any $m_1$ with an odd number of 1’s and any $m_2$ with an even number of 1’s, since $n$ is odd, we have

\Pr_{sk}[m_1 \oplus sk = c] = \begin{cases} \frac{1}{2^{n-1}} & \text{if } \text{pop\_count}(c) \not\equiv 0 \mod 2\\ 0 & \text{if } \text{pop\_count}(c) \equiv 0 \mod 2 \end{cases}

Similarly,

\Pr_{sk}[m_2 \oplus sk = c] = \begin{cases} \frac{1}{2^{n-1}} & \text{if } \text{pop\_count}(c) \equiv 0 \mod 2\\ 0 & \text{if } \text{pop\_count}(c) \not\equiv 0 \mod 2 \end{cases}

Thus, an adversary can determine the parity (odd or even) of the number of 1’s in the original message by examining the ciphertext $c$ . This additional information compromises perfect secrecy.

Idea:

The original One-Time Pad encryption and decryption processes are defined as follows:

M = \{0,1\}^n = K \\ \text{Gen}(\cdot) \to sk, sk \overset{\$}{\leftarrow} K\\ \text{Enc}(sk, m) = sk \oplus m \\ \text{Dec}(sk, c) = sk \oplus c

Under the condition that $sk$ is uniformly random, the probability of encrypting $m_1$ and $m_2$ to the same ciphertext $c$ is equal, i.e.,

\Pr_{sk}[m_1 \oplus sk = c] = \Pr_{sk}[m_2 \oplus sk = c]

However, the modification to the definition of $K$ leads to the issue where

\Pr_{sk}[m_1 \oplus sk = c] \neq \Pr_{sk}[m_2 \oplus sk = c] \text{ if } \text{pop\_count}(m_1) \not\equiv \text{pop\_count}(m_2) \mod 2

Question 2: One Way Functions vs Pseudorandom Generators#

2.1#

Description
Let $G$ be a PRG that maps $n$ bits to $2n$ bits, prove that $G$ is a (strong) one-way function.

Solution:

The definition of a PRG is that for any algorithm $A$ , the probability that $A$ can distinguish between the output of $G:\{0,1\}^n\to \{0,1\}^{l(n)}$ (in this problem, $l(n)=2n$ ) on a random input and a truly random string is negligible. Formally,

|\Pr_{s \leftarrow \{0,1\}^n, r \leftarrow G(s)}[\mathcal A(r)=1]-\Pr_{r \xleftarrow{\mathbb{R}}\{0,1\}^{l(n)}}[\mathcal A(r)=1]| \leq \mathtt{negl}(n)

If $G$ is not a one-way function, there exists an efficient algorithm $\mathcal A$ that can invert $G$ .

Idea:

Assume $G \in \text{PRG}[\{0,1\}^n \to \{0,1\}^{2n}]$ is not a one-way function, then there exists $\mathcal A_0$ such that

\Pr_{x}[f(\mathcal A_0(G(x))=G(x)] \geqslant \frac{1}{\text{poly}(n)}

( $G$ here is essentially the function $f$ in the definition).

In this scenario, consider

\mathcal A':\{0,1\}^{2n}\to \{0,1\} \mid \mathcal A'(r)=[G(\mathcal A_0(r))=r]

Then,

\Pr_{s \leftarrow \{0,1\}^n, r \leftarrow G(s)}[\mathcal A'(r)=1] = \Pr_{s\leftarrow \{0,1\}^n}[G(\mathcal A_0(G(s)))=G(s)] \geqslant \frac{1}{\text{poly}(n)}

and

\Pr_{r \xleftarrow{\mathbb{R}}\{0,1\}^{2n}}[\mathcal A'(r)=1] \leq \Pr_{r\xleftarrow{\mathbb R}\{0,1\}^{2n}}[\exists s\in \{0,1\}^n,G(s)=r] = \frac{2^n}{2^{2n}} = \frac{1}{2^n}

Thus,

\left|\Pr_{s \leftarrow \{0,1\}^n, r \leftarrow G(s)}[\mathcal A'(r)=1]-\Pr_{r \xleftarrow{\mathbb{R}}\{0,1\}^{2n}}[\mathcal A'(r)=1]\right| \geq \left|\frac{1}{\text{poly}(n)}-\frac{1}{2^n}\right| \geq \frac{1}{\text{poly'}(n)}

Since $\frac{1}{\text{poly'}(n)} \neq \mathtt{negl}(n)$ , this contradicts the initial assumption. Therefore, $G$ is a one-way function.

2.2#

Description
Given that $F$ is a one-way function, construct a function $G$ such that:
$G$ is a one-way function.
$G$ is not a pseudorandom generator (PRG).

Solution:

Directly provide the construction: Let

F:\{0,1\}^n\to \{0,1\}^{l(n)}

Construct

G:\{0,1\}^n\to \{0,1\}^{l(n)+1} \mid G(r)=\text{concat}(F(r),\{\mathtt{1}\})

Here, $\text{concat}$ denotes the sequential concatenation of two binary sequences. In other words, $G$ appends a $1$ to the end of $F$ ‘s output.

Proof for OWF:

Since $F$ satisfies

\forall \mathcal A:\{0,1\}^{l(n)}\to \{0,1\}^n, \Pr_{x \xleftarrow{\mathbb R}{} \{0,1\}^{n} }[F(\mathcal A(F(x)))=F(x)] \leqslant \mathtt{negl}(x)

If $G$ is not OWF, then there exists $\mathcal A_0:\{0,1\}^{l(n)+1}\to \{0,1\}^n,\text{poly}(\cdot)$ such that

\Pr_{x \xleftarrow{\mathbb R}{} \{0,1\}^n}[G(\mathcal A_0(G(x)))=G(x)] \geqslant \frac{1}{\text{poly}(n)}

Then we construct $\mathcal A'_0:{0,1}^{l(n)}\to {0,1}^{n} \mid \mathcal {A}'_0(r)=\mathcal A_0(\text{concat}(r,{\mathtt{1}}))$

$\mathcal A_0'$ satisfies

\Pr_{x \xleftarrow{\mathbb R}{} \{0,1\}^n}[F(\mathcal A_0'(F(x)))=F(x)] \geqslant \frac{1}{\text{poly}(n)}

This contradicts the fact that $F$ is an OWF.

Proof for not PRG:

Construct

\mathcal A'':\{0,1\}^{l(n)+1}\to \{0,1\} \mid \begin{cases}1 & r_{l(n)+1}=1\\ 0 & r_{l(n)+1}=0\end{cases}

Then

|\Pr_{s \leftarrow \{0,1\}^n, r \leftarrow G(s)}[\mathcal A(r)=1]-\Pr_{r \xleftarrow{\mathbb{R}}\{0,1\}^{l(n)+1}}[\mathcal A(r)=1]| = 1-\frac{1}{2} = \frac{1}{2}

Clearly, this contradicts the requirement for the PRG definition of being negligible.

In summary, the constructed $G$ is a One-Way Function but not a PRG.br