diff options
| -rw-r--r-- | content/know/category/cryptography.md | 9 | ||||
| -rw-r--r-- | content/know/category/quantum-information.md | 10 | ||||
| -rw-r--r-- | content/know/concept/bb84-protocol/index.pdc | 234 | ||||
| -rw-r--r-- | content/know/concept/diffie-hellman-key-exchange/index.pdc | 74 | ||||
| -rw-r--r-- | content/know/concept/lagrange-multiplier/index.pdc | 27 | ||||
| -rw-r--r-- | content/know/concept/no-cloning-theorem/index.pdc | 71 |
6 files changed, 421 insertions, 4 deletions
diff --git a/content/know/category/cryptography.md b/content/know/category/cryptography.md new file mode 100644 index 0000000..059b280 --- /dev/null +++ b/content/know/category/cryptography.md @@ -0,0 +1,9 @@ +--- +title: "Cryptography" +firstLetter: "C" +date: 2021-03-06T14:43:37+01:00 +draft: false +layout: "category" +--- + +This page will fill itself. diff --git a/content/know/category/quantum-information.md b/content/know/category/quantum-information.md new file mode 100644 index 0000000..f8f9916 --- /dev/null +++ b/content/know/category/quantum-information.md @@ -0,0 +1,10 @@ +--- +title: "Quantum information" +firstLetter: "Q" +date: 2021-03-06T14:43:52+01:00 +draft: false +layout: "category" +--- + +This page will fill itself. + diff --git a/content/know/concept/bb84-protocol/index.pdc b/content/know/concept/bb84-protocol/index.pdc new file mode 100644 index 0000000..9f7c7db --- /dev/null +++ b/content/know/concept/bb84-protocol/index.pdc @@ -0,0 +1,234 @@ +--- +title: "BB84 protocol" +firstLetter: "B" +publishDate: 2021-03-06 +categories: +- Quantum information +- Cryptography + +date: 2021-03-06T09:44:16+01:00 +draft: false +markup: pandoc +--- + +# BB84 protocol + +The **BB84** or **Bennett-Brassard 1984** protocol is +a *quantum key distribution* (QKD) protocol, +whose purpose is to securely transmit a string of random bits +over a quantum channel for later use as a one-time pad. +It is provably information-secure, thanks to the fact that +quantum channels cannot be eavesdropped without interfering with the signal. + +Alice wants to send a secret key to Bob. +Between them, they have one quantum channel and one classical channel. +Both channels may have eavesdroppers without compromising the security of the BB84 protocol, +as long as Alice and Bob authenticate all data sent over the classical channel. + +First, Alice securely generates a sequence of random (classical) bits. +Note that the BB84 protocol is only suitable for random (high-entropy) data, +because the later stages of the protocol involve revealing parts of the data +over the (insecure) classical channel. + +For each bit, Alice randomly chooses a qubit basis, +either $\{ \ket{0}, \ket{1} \}$ (eigenstates of the $z$-spin $\hat{\sigma}_z$) +or $\{ \ket{-}, \ket{+} \}$ (eigenstates of the $x$-spin $\hat{\sigma}_x$). +Using the basis she chose, she then transmits the bits to Bob over the quantum channel, +encoding them as follows: + +$$\begin{aligned} + 0 \:\:\rightarrow\:\: \ket{0} \:\mathrm{or}\: \ket{+} + \qquad \quad + 1 \:\:\rightarrow\:\: \ket{1} \:\mathrm{or}\: \ket{-} +\end{aligned}$$ + +Crucially, Bob has no idea which basis Alice used for any of the bits. +For every bit, he chooses $\hat{\sigma}_z$ or $\hat{\sigma}_x$ at random, +and makes a measurement of the qubit, yielding 0 or 1. +If he guessed the basis correctly, he gets the bit value intended by Alice, +but if he guessed incorrectly, he randomly gets 0 or 1 with a 50-50 probability: + +$$\begin{aligned} + | \braket{0}{+} |^2 = | \braket{0}{-} |^2 = | \braket{1}{+} |^2 = | \braket{1}{-} |^2 = \frac{1}{2} +\end{aligned}$$ + +After Alice has sent all her qubits, +the next step is **basis reconciliation**: +over the classical channel, Bob announces, for each bit, +which basis he chose, and Alice tells him if he was right or wrong. +Bob discards all bits where he guessed wrongly. +If their quantum channel did not have any noise or eavesdroppers, +Alice and Bob now have a perfectly correlated secret string of bits. + + +## Eavesdropper detection + +But what if there is actually an eavesdropper? +Consider a third party, Eve, who wants to intercept Alice' secret string. +The main advantage of using QKD compared to classical protocols +is that such an eavesdropper can be detected. + +Suppose that Eve is performing an *intercept-resend attack* +(not very effective, but simple), +where she listens on the quantum channel. +For each qubit received from Alice, Eve chooses +$\hat{\sigma}_z$ or $\hat{\sigma}_x$ at random and measures it. +She records her results and resends the qubits to Bob +using the basis she chose, which may or may not be what Alice intended. + +If Eve guesses Alice' basis correctly, her presence is not revealed, +and the protocol proceeds as normal. +However, if she guesses wrongly (which has a probability of 50%), +her bit value might be incorrect, and she will resend whatever she measured +to Bob encoded in the wrong basis. + +If we assume that Eve chose wrongly, +Bob might measure using Eve's basis, +which will yield a 50% error rate due to Eve's mistake. +Otherwise, Bob might measure using Alice' basis, +which will also yield a 50% error rate due to the disagreement with Eve. + +In the end, the probability is 0.5 that Eve chose correctly, +which, multiplied by the 0.5 error rate from Bob's choice, +will result in a 0.25 error rate due to Eve's presence. +To detect this, after basis reconciliation, +Bob reveals a part of his secret string as a sacrifice, +which allows Alice to estimate the error rate. +If the rate is too high, Eve is detected, and the protocol can be aborted, +although that is not mandatory. + +This was an intercept-resend attack. +There exist other attacks, but similar logic holds. +It has been proven by Shor and Preskill in 2000 +that as long as the error rate is below 11%, +the BB84 protocol is fully secure, i.e. there cannot be any eavesdroppers. + + +## Error correction + +In practice, even without Eve, quantum channels are imperfect, +and will introduce some errors in the qubits received by Bob. +Suppose that after basis reconciliation, +Alice and Bob have the strings +$\{a_1, ..., a_N\}$ and $\{b_1, ..., b_N\}$, respectively. +We define $p$ as the probability that Alice and Bob agree on the $n$th bit, +which we assume to be greater than 50%: + +$$\begin{aligned} + p = P(a_n = b_n) > \frac{1}{2} +\end{aligned}$$ + +Ideally, $p = 1$. To improve $p$, the following simple scheme can be used: +starting at $n = 1$, Alice and Bob reveal $A$ and $B$ over the classical channel, +where $\oplus$ is an XOR: + +$$\begin{aligned} + A = a_n \oplus a_{n+1} + \qquad \quad + B = b_n \oplus b_{n+1} +\end{aligned}$$ + +If $A = B$, then $a_{n+1}$ and $b_{n+1}$ are discarded to prevent +a listener on the classical channel from learning anything about the string. +If $A \neq B$, all of $a_n$, $b_n$, $a_{n+1}$ and $b_{n+1}$ are discarded, +and then Alice and Bob move on to $n = 3$, etc. + +Given that $A = B$, the probability that $a_n = b_n$, +which is what we want, is given by: + +$$\begin{aligned} + P(a_{n} = b_{n} | A = B) + &= \frac{P(a_{n} = b_{n} \land A = B)}{P(A = B)} + \\ + &= \frac{P(a_{n} = b_{n} \land a_{n+1} = b_{n+1})}{P(a_{n} = b_{n} \land a_{n+1} = b_{n+1}) + P(a_{n} \neq b_{n} \land a_{n+1} \neq b_{n+1})} + \\ + &= \frac{P(a_{n} = b_{n}) \: P(a_{n+1} = b_{n+1})}{P(a_{n} = b_{n}) \: P(a_{n+1} = b_{n+1}) + P(a_{n} \neq b_{n}) \: P(a_{n+1} \neq b_{n+1})} +\end{aligned}$$ + +We use the definition of $p$ to get the following inequality, +which can be verified by plotting: + +$$\begin{aligned} + P(a_{n} = b_{n} | A = B) + = \frac{p^2}{p^2 + (1 - p)^2} + > p +\end{aligned}$$ + +Alice and Bob can repeat this error correction scheme multiple times, +until their estimate of $p$ is satisfactory. +This involves discarding many bits, +so the length $N_\mathrm{new}$ of the string they end up with +after one iteration is given by: + +$$\begin{aligned} + N_\mathrm{new} + = \frac{1}{2} N_\mathrm{old} P(A = B) + = \frac{1}{2} N_\mathrm{old} \big( p^2 + (1 - p)^2 \big) +\end{aligned}$$ + +More efficient schemes exist, which do not consume so many bits. + + +## Privacy amplification + +Suppose that after the error correction step, $p = 1$, +so Alice and Bob fully agree on the random string. +However, in the meantime, Eve has been listening, +and has been doing a good job +building up her own string $\{e_1, ..., e_N\}$, +such that she knows more that 50% of the bits: + +$$\begin{aligned} + q = P(e_n = a_n) > \frac{1}{2} +\end{aligned}$$ + +**Privacy amplification** is an optional final step of the BB84 protocol +which aims to reduce Eve's $q$. +Alice and Bob use their existing strings to generate a new one +$\{a_1', ..., a_M'\}$: + +$$\begin{aligned} + a_1' + = a_1 \oplus a_2 = b_1 \oplus b_2 + \qquad + a_2' + = a_3 \oplus a_4 = b_3 \oplus b_4 + \qquad + \cdots +\end{aligned}$$ + +Note that this halves the string's length; +more efficient schemes exist, which consume less. + +To see why this improves Alice and Bob's privacy, +suppose that Eve is following along, +and creates a new string $\{e_1', ..., e_M'\}$ +where $e_m' = e_{2m - 1} \oplus e_{2m}$. +The probability that Eve's result agrees with +Alice and Bob's string is given by: + +$$\begin{aligned} + P(e_m' = a_m') + &= P(e_1 = a_1 \land e_2 = a_2) + P(e_1 \neq a_1 \land e_2 \neq a_2) + \\ + &= P(e_1 = a_1) \: P(e_2 = a_2) + P(e_1 \neq a_1) \: P(e_2 \neq a_2) +\end{aligned}$$ + +Recognizing $q$ 's definition, +we find the following inequality, +which can be verified by plotting: + +$$\begin{aligned} + P(e_m' = a_m') + = q^2 + (1 - q)^2 + < q +\end{aligned}$$ + +After repeating this step several times, $q$ will be close to 1/2, +which is the ideal value: for $q =$ 0.5, +Eve would only know 50% of the bits, +which is equivalent to her guessing at random. + + +## References +1. N. Brunner, *Quantum information theory: lecture notes*, 2019. diff --git a/content/know/concept/diffie-hellman-key-exchange/index.pdc b/content/know/concept/diffie-hellman-key-exchange/index.pdc new file mode 100644 index 0000000..c0af364 --- /dev/null +++ b/content/know/concept/diffie-hellman-key-exchange/index.pdc @@ -0,0 +1,74 @@ +--- +title: "Diffie-Hellman key exchange" +firstLetter: "D" +publishDate: 2021-03-06 +categories: +- Cryptography + +date: 2021-03-06T16:45:48+01:00 +draft: false +markup: pandoc +--- + +# Diffie-Hellman key exchange + +In cryptography, the **Diffie-Hellman key exchange** is a method +for two parties to securely agree on an encryption key, +when they can only communicate over an insecure channel. + +The fundamental assumption of the Diffie-Hellman scheme, +upon which its security rests, +is that the following function $f(n)$ is a **trapdoor function**, +which means that calculating $f$ is easy, +but its inverse $f^{-1}$ is extremely hard to find: + +$$\begin{aligned} + f(n) = g^n \bmod p +\end{aligned}$$ + +Where $n$ is a natural number, and $p$ is a prime. +The natural number $g$ is a so-called *primitive root modulo* $p$. +Importantly, $g$ and $p$ have been specifically chosen +such that $f(n)$ can take any value in $\{1, ..., p \!-\! 1\}$ +for $n$ in $\{0, ..., p \!-\! 2\}$. +The trapdoor assumption is that, given $g$, $p$ and $f(n)$, +there is no efficient algorithm to recover $n$. + +Suppose that Alice and Bob want to exchange encrypted data in the future, +so they need to agree on an encryption key to use. +However, they can only exchange messages with each other over +an insecure channel, which is being eavesdropped. + +After they publicly agree on the values of $g$ and $p$, +Alice and Bob each choose a secret number from $\{0, ..., p \!-\! 2\}$, respectively $a$ and $b$, +and then privately calculate $A$ and $B$ as follows: + +$$\begin{aligned} + A = g^a \bmod p + \qquad \quad + B = g^b \bmod p +\end{aligned}$$ + +Finally, they transmit these numbers $A$ and $B$ +to each other over the insecure connection, +and then each side calculates $k$, which is the desired secret key: + +$$\begin{aligned} + \boxed{ + k = A^b \bmod p = B^a \bmod p = g^{ab} \bmod p + } +\end{aligned}$$ + +The point is that $k$ includes both $a$ *and* $b$, +but each side only needs to know *either* $a$ *or* $b$. +And, due to the trapdoor assumption, +the eavesdropper knows $A$ and $B$, +but cannot recover $a$ or $b$. + +This assumption is just that: an assumption. +So far, nobody has been able to prove or disprove it +for classical computation. +However, for quantum computers, +it has already been *dis*proven! +In this case, another method must be used, +for example the [BB84 protocol](/know/concept/bb84-protocol/). diff --git a/content/know/concept/lagrange-multiplier/index.pdc b/content/know/concept/lagrange-multiplier/index.pdc index fffe85f..fc1319e 100644 --- a/content/know/concept/lagrange-multiplier/index.pdc +++ b/content/know/concept/lagrange-multiplier/index.pdc @@ -49,15 +49,14 @@ of all the partial derivatives. To help us solve this, we introduce a "dummy" parameter $\lambda$, the so-called **Lagrange multiplier**, -which need not be constant, and contruct a new function $L$ given by: $$\begin{aligned} L(x, y, z) = f(x, y, z) + \lambda \phi(x, y, z) \end{aligned}$$ -Clearly, $\dd{L} = \dd{f} + \lambda \dd{\phi} = 0$, -so now the problem is a single equation again: +At the extremum, $\dd{L} = \dd{f} + \lambda \dd{\phi} = 0$, +so now the problem is a "single" equation again: $$\begin{aligned} 0 = \dd{L} @@ -69,7 +68,21 @@ This choice represents satisfying the constraint, so now the remaining $\dd{x}$ and $\dd{y}$ are independent again, and we simply have to find the roots of $f_x + \lambda \phi_x$ and $f_y + \lambda \phi_y$. -This generalizes nicely to multiple constraints or more variables: +In effect, after introducing $\lambda$, +we have four unknowns $(x, y, z, \lambda)$, +but also four equations: + +$$\begin{aligned} + L_x = L_y = L_z = 0 + \qquad \quad + \phi = C +\end{aligned}$$ + +We are only really interested in the first three unknowns $(x, y, z)$, +so $\lambda$ is sometimes called the **undetermined multiplier**, +since it is just an algebraic helper whose value is irrelevant. + +This method generalizes nicely to multiple constraints or more variables: suppose that we want to find the extrema of $f(x_1, ..., x_N)$ subject to $M < N$ conditions: @@ -103,3 +116,9 @@ $$\begin{aligned} 0 = \dd{L} = \sum_{n = 1}^N \Big( f_{x_n} + \sum_{m = 1}^M \lambda_m \phi_{x_n} \Big) \dd{x_n} \end{aligned}$$ + + +## References +1. G.B. Arfken, H.J. Weber, + *Mathematical methods for physicists*, 6th edition, 2005, + Elsevier. diff --git a/content/know/concept/no-cloning-theorem/index.pdc b/content/know/concept/no-cloning-theorem/index.pdc new file mode 100644 index 0000000..e253464 --- /dev/null +++ b/content/know/concept/no-cloning-theorem/index.pdc @@ -0,0 +1,71 @@ +--- +title: "No-cloning theorem" +firstLetter: "N" +publishDate: 2021-03-06 +categories: +- Physics +- Quantum mechanics +- Quantum information + +date: 2021-03-06T09:45:32+01:00 +draft: false +markup: pandoc +--- + +# No-cloning theorem + +In quantum mechanics, the **no-cloning theorem** states +there is no general way to make copies of an arbitrary quantum state $\ket{\psi}$. +This has profound implications for quantum information. + +To prove this theorem, let us pretend that a machine exists +that can do just that: copy arbitrary quantum states. +Given an input $\ket{\psi}$ and a blank $\ket{?}$, +this machines turns $\ket{?}$ into $\ket{\psi}$: + +$$\begin{aligned} + \ket{\psi} \ket{?} + \:\:\longrightarrow\:\: + \ket{\psi} \ket{\psi} +\end{aligned}$$ + +We can use this device to make copies of the basis vectors $\ket{0}$ and $\ket{1}$: + +$$\begin{aligned} + \ket{0} \ket{?} + \:\:\longrightarrow\:\: + \ket{0} \ket{0} + \qquad \quad + \ket{1} \ket{?} + \:\:\longrightarrow\:\: + \ket{1} \ket{1} +\end{aligned}$$ + +If we feed this machine a superposition $\ket{\psi} = \alpha \ket{0} + \beta \ket{1}$, +we *want* the following behaviour: + +$$\begin{aligned} + \Big( \alpha \ket{0} + \beta \ket{1} \Big) \ket{?} + \:\:\longrightarrow\:\: + &\Big( \alpha \ket{0} + \beta \ket{1} \Big) \Big( \alpha \ket{0} + \beta \ket{1} \Big) + \\ + &= \Big( \alpha^2 \ket{0} \ket{0} + \alpha \beta \ket{0} \ket{1} + \alpha \beta \ket{1} \ket{0} + \beta^2 \ket{1} \ket{1} \Big) +\end{aligned}$$ + +Note the appearance of the cross terms with a factor of $\alpha \beta$. +The problem is that the fundamental linearity of quantum mechanics +dictates different behaviour: + +$$\begin{aligned} + \Big( \alpha \ket{0} + \beta \ket{1} \Big) \ket{?} + = \alpha \ket{0} \ket{?} + \beta \ket{1} \ket{?} + \:\:\longrightarrow\:\: + \alpha \ket{0} \ket{0} + \beta \ket{1} \ket{1} +\end{aligned}$$ + +This is clearly not the same as before: we have a contradiction, +which implies that such a general cloning machine cannot ever exist. + + +## References +1. N. Brunner, *Quantum information theory: lecture notes*, 2019. |