Expand knowledge base

4 files changed, 402 insertions, 4 deletions

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.