Adventures in Measure Theory - 2

I am following the Measure Theory series by D.H. Fremlin and blogging my notes here.

Borel Sets

To understand the definition of Borel Sets, we need to understand two things first:

Generating a $\sigma$-algebra

In order to understand what generating a $\sigma$-algebra means, we will start with a proof.

Let $\mathfrak S$ be a family of $\sigma$-algebras of subsets of a set $X$, i.e.,

\[\mathfrak S=\{\Sigma:\Sigma \text{ is a }\sigma\text{-algebra of subsets of }X\}.\]

So $\mathfrak S$ is basically a set of set of sets i.e. $\mathfrak S \subseteq \mathcal P(\mathcal PX)$. Then $\bigcap\mathfrak S$ is the intersection of all the $\sigma$-algebras in $\mathfrak S$. We want to prove that $\bigcap\mathfrak S$ is also a $\sigma$-algebra.

Proof.

  1. $\emptyset\in\Sigma$ for every $\Sigma\in\mathfrak S$, so $\emptyset\in\bigcap\mathfrak S$.
  2. If $E\in\bigcap\mathfrak S$ then $E\in\Sigma$ for every $\Sigma\in\mathfrak S$, so $X\setminus E\in\Sigma$ for every $\Sigma\in\mathfrak S$ and $X\setminus E\in\bigcap\mathfrak S$.
  3. Let $\langle E_n\rangle_{n\in\Bbb N}$ be any sequence in $\bigcap\mathfrak S$. Then for every $\Sigma\in\mathfrak S$, $\langle E_n\rangle_{n\in\Bbb N}$ is a sequence in $\Sigma$, so $\bigcup_{n\in\Bbb N}E_n\in\Sigma$; as $\Sigma$ is arbitrary, $\bigcup_{n\in\Bbb N}E_n\in\bigcap\mathfrak S$.

Now we can understand what generating a $\sigma$-algebra means: The $\sigma$-algebra generated by a set $\mathcal A$ is the smallest possible $\sigma$-algebra that contains $\mathcal A$. More precisely,

Let $\mathcal A$ be any family of subsets of $X$. Consider

\[\mathfrak S=\{\Sigma:\Sigma \text{ is a }\sigma\text{-algebra of subsets of }X \text{ and } \mathcal A\subseteq\Sigma\}\]

Then, the $\sigma$-algebra of subsets of $X$ generated by $\mathcal A$ is $\Sigma_{\mathcal A} = \bigcap\mathfrak S$. Let that sink in.

Another way of obtaining $\Sigma_{\mathcal A}$ from $\mathcal A$ could be: We start off with an empty set, say, $\Sigma_{\mathcal A’}$. We first add $\emptyset$ and every element of $\mathcal A$ to $\Sigma_{\mathcal A’}$. Then we add the complement of every element in $\Sigma_{\mathcal A’}$ to itself. Finally, we add the union of all sequences in $\Sigma_{\mathcal A’}$ to itself. Then the set $\Sigma_{\mathcal A’}$ is actually $\Sigma_{\mathcal A}$.

Examples

  • For any $X$, the $\sigma$-algebra of subsets of $X$ generated by $\emptyset$ is $\{\emptyset,X\}$.
  • The $\sigma$-algebra of subsets of $\Bbb N$ generated by $\{\{n\}:n\in\Bbb N\}$ is $\mathcal P\Bbb N$.

Open Sets

A set $S \subseteq \Bbb R$ is considered open if $\forall\,\, s\in S \,\,\exists\,\, \delta > 0$ such that $(s-\delta, s+\delta)\in S$.

Here’s a more general definition (with regards to the dimension of the Euclidean space): A set $S \subseteq \Bbb R^r;\,\, r \in \Bbb Z^+$ is considered open if $\forall\,\, s\in S \,\,\exists\,\, \delta > 0$ such that $\{t: ||(s-t)|| < \delta\}\subseteq S$ where $||(s-t)||$ denotes the Euclidean distance between $s$ and $t$ (i.e. all points within a distance $\delta$ from $s$ lie in $S$).

Borel Sets

The Borel sets of $\Bbb R$, are just the members of the $\sigma$-algebra of subsets of $\Bbb R$ generated by the family of open sets of $\Bbb R$; the $\sigma$-algebra itself is called the Borel $\sigma$-algebra.

In other words, we pick all the open sets in $\mathcal P\Bbb R$ and put them into a set, say, $\mathcal A$. Then using $\mathcal A$, we generate a $\sigma$-algebra $\Sigma_{\mathcal A}$ of the subsets of $\Bbb R$. The members of $\Sigma_{\mathcal A}$ are called Borel sets and $\Sigma_{\mathcal A}$ is called the Borel $\sigma$-algebra.

For a more general definition (with regards to the dimension of the Euclidean space), replace $\Bbb R$ with $\Bbb R^r;\,\,r\in\Bbb Z^+$ in the above two paragraphs.




Adventures in Measure Theory - 1

Today, I will start studying measure theory. I will be reading through the Measure Theory series by D.H. Fremlin and blogging my notes here.

Let’s jump straight into it!

“The business of pure mathematics is to express and extend the logical capacity of the human mind, and … the actual theorems we work through are merely vehicles for the ideas.” ~ D.H. Fremlin

Measure Space

A set in which some (not, as a rule, all) subsets may be assigned a measure.

  • What is a measure?
    Although measure is just a number that is assigned to a set, it can be interpreted as anything that determines the size, amount or degree of something. Area, mass, volume, temperature are just some examples. In general, a measure may be interpreted as anything additive, i.e., the measure of the union of two disjoint sets must be equal to the sum of their individual measures.

When studying any measure, a proper understanding of the class of sets which it measures is necessary. This is where $\sigma$-algebras come in. All measures in the standard theory (there are non-standard theories too?!) are defined on such collections.

$\sigma$-algebra of sets

[111A] Definition. Let $X$ be a set. A $\sigma$-algebra of subsets of $X$ (a.k.a $\sigma$-field) is a family $\Sigma$ of subsets of $X$ such that
(i) $\emptyset\in\Sigma$;
(ii) for every $E\in\Sigma$, its complement $X\setminus E$ in $X$ belongs to $\Sigma$;
(iii) for every sequence $\langle E_n\rangle_{n\in\Bbb N}$ in $\Sigma$, its union $\bigcup_{n\in\Bbb N}E_n$ belongs to $\Sigma$.

It is also obvious that for any $X$,

  • $\Sigma=\{\emptyset,X\}$ is the smallest $\sigma$-algebra of subsets of $X$; and,
  • $\mathcal{P}X$, the power set of $X$, is the largest $\sigma$-algebra of subsets of $X$.

Elementary properties of $\sigma$-algebras

[111D] If $\Sigma$ is a $\sigma$-algebra of subsets of $X$, then it has the following properties.

  • (a) $E\cup F\in\Sigma$ for all $E$, $F\in\Sigma$.
    Proof. if $E$, $F\in\Sigma$, set $E_0=E$, $E_n=F$ for $n\ge 1$; then $\langle E_n\rangle_{n\in\Bbb N}$ is a sequence in $\Sigma$ and $E\cup F=\bigcup_{n\in\Bbb N}E_n\in\Sigma$.

  • (b) $E\cap F\in\Sigma$ for all $E$, $F\in\Sigma$.
    Proof. By 111A (ii), $X\setminus E$ and $X\setminus F\in\Sigma$;
    by (a), $(X\setminus E)\cup(X\setminus F)\in\Sigma$;
    by (ii) again, $X\setminus((X\setminus E)\cup(X\setminus F))\in\Sigma$; but this is just $E\cap F$.

  • (c) $E\setminus F\in\Sigma$ for all $E$, $F\in\Sigma$.
    Proof. By 111A (ii), $X\setminus F\in\Sigma$;
    by (b), $E\cap(X\setminus F)\in\Sigma$; but this is just $E\setminus F$.

  • (d) Now suppose that $\langle E_n\rangle_{n\in\Bbb N}$ is a sequence in $\Sigma$, then, following the same logic as (b), we have

\[\bigcap_{n\in\Bbb N}E_n = X\setminus\bigcup_{n\in\Bbb N}(X\setminus E_n) \in \Sigma\]

Countable Sets

A set $K$ is countable if there exists an injective function $f: K \to\Bbb N$.
Equivalent definition: A set $K$ is countable if either it is empty or there is a surjection from $\Bbb N$ onto $K$.

If $\Sigma$ is a $\sigma$-algebra of sets and $\langle E_k\rangle_{k\in K}$ is a family in $\Sigma$ indexed by $K$, then $\bigcup_{k\in K}E_k\in\Sigma$.

Proof. For if $n\mapsto k_n:\Bbb N\to K$ is a surjection, then $E’_n=E_{k_n}\in\Sigma\,\,\forall\,\, n\in\Bbb N$, and $\bigcup_{k\in K}E_k=\bigcup_{n\in\Bbb N}E’_n\in\Sigma$. This leaves out the case $K=\emptyset$; but in this case the natural interpretation of $\bigcup_{k\in K}E_k$ is

\[\{x:\exists\,\, k\in \emptyset,\,x\in E_k\}\]

which is itself $\emptyset$, and therefore belongs to $\Sigma$ by clause (i) of 111A.

Some properties of countable sets

  • (i) If $K$ is countable and $L \subseteq K$ then $L$ is countable.
    Proof. $K$ is countable, which means there exists an injective function $f:K \to \Bbb N$. Since $L \subseteq K$, $f$ is valid for all values in $L$.

  • (ii) The Cartesian Product $\Bbb N \times \Bbb N$ is countable.
    Proof. Consider the function $f(x, y) = 2^x 3^y$. This function is injective for all $(x, y) \in \Bbb N \times \Bbb N$ $[\because f(x_1, y_1) = f(x_2, y_2) \implies (x_1, y_1) = (x_2, y_2)]$.

  • (iii) If $K$ and $L$ are countable sets, then so is $K\times L$.
    Proof. $K$ and $L$ are countable sets, which means there exist injective functions $f:K\to\Bbb N$ and $g:L\to\Bbb N$. Consider a function $h:K\times L \to\Bbb N$ such that $h(k,l)=2^{f(k)} 3^{g(l)}$. Then $h$ is injective and hence $K\times L$ is a countable set.

  • (iv) If $K_1,K_2,\dots ,K_r$ are countable sets, so is $K_1\times K_2\times\dots K_r$.
    Proof. We will use induction on $r$ to prove this result.
    For $r=1$, the statement is trivial.
    Assume that the statement holds for $r=m$. If we are able to show that it also holds for $r=m+1$, then by the principle of mathematical induction, it will hold for all $r\in\Bbb N$.
    We have, $K_1\times K_2\times\dots K_m$ is a countable set. Let it be equal to $M$. There exists an injective function $f:M\to\Bbb N$.
    When $r=m+1$, it is given that $K_{m+1}$ is a countable set, i.e., there exists an injective function $g:K_{m+1} \to\Bbb N$. Now, consider a function $h:M\times K_{m+1}\to \Bbb N$ defined as $h(x, y) = 2^{f(x)} 3^{g(y)}$. It can be easily verified that this function is injective. Thus, $K_1\times K_2\times\dots K_{m+1}$ is a countable set.

Combining the idea of countable sets with 111D (d), we can say that,

  • If $\Sigma$ is a $\sigma$-algebra of sets, $K$ is a non-empty countable set, and $\langle E_k\rangle_{k\in K}$ is a family in $\Sigma$, then $\bigcap_{k\in K}E_k$ belongs to $\Sigma$.
    Proof. Since $K$ is a countable set, there exists a surjective function $f:\Bbb N\to K$. This means that, $\forall\,\,k\in K\,\,\exists\,\, n_k\in\Bbb N$. Thus, $\bigcap_{k\in K}E_k = \bigcap_{n\in\Bbb N}E_{n_k} \in \Sigma$.



Solving Cryptography Problems - 5

Here’s the first problem:

Using Shamir’s $(2, 4)$ secret sharing scheme with the parameter $p=17$, we get

\[D_1 = 12, D_4 = 3\]

What is the shared secret $D$?

  • What is Shamir’s secret sharing scheme?
    I read Adi Shamir’s How to Share a Secret, and was able to get a decent understanding of the scheme he proposed.

    This is a scheme proposed for sharing secrets, not encrypting them. We basically divide our secret $D$ into $n$ parts, such that we only require $k$ parts to recover the secret. Even if an adversary is able to steal $k-1$ parts, they will not be able to read our secret. This is done by constructing a $(k-1)$ - degree polynomial $q(x)$ (so it will have $k$ coefficients) such that $q(0) = a_0 = D$ and $q(i) = D_i \,\forall\, i \in \{1, 2, \ldots , n\}$. Therefore, we can obtain the value of all the $k$ coefficients in the polynomial (and hence the secret $D$) only if we are able to write $k$ or more equations (that is, we must have at least $k$ of the $n$ $D_i$s). All these values are computed modulo a prime number $p$ that is chosen such that it is bigger than $n$.

Since $k=2$, our polynomial is linear:

\[q(x) = a_0 + a_1 x\]

where $a_0 = D$, the shared secret and $D_i \equiv q(i) \pmod {p}$. So we have,

\[D_1 = 12\equiv a_0 + a_1 \pmod {17}\\ D_4 = 3\equiv a_0 + 4a_1 \pmod {17}\]

Upon solving this system of equations, we get $D = a_0 = 15$ and $a_1 = 14$.

Here’s the last problem from my assignment:

Let $P = (9,7)$ be a point on the elliptic curve $y^2 \equiv x^3 + x + 1 \pmod{23}$. What is the point $2P$ on the elliptic curve?

These two videos (this one and this one) helped me understand the basic idea behind doubling a point on an elliptic curve.

The derivative of the curve will give us the slope of the tangent at a point:

\[\frac{dy}{dx} \equiv \frac{3x^2 + 1}{2y} \pmod{23}\]

At $(9,7)$, the slope of the tangent is $1$. The equation of the tangent at $(9,7)$ will be:

\[y = x - 2\]

Finding the point at which it intersects the elliptic curve,

\[(x-2)^2 \equiv x^3 + x + 1 \pmod{23}\\ \implies x^3 - x^2 + 5x - 3 \equiv 0 \pmod{23}\]

Here’s a quick python script I wrote that will help us find the real roots of the above cubic equation:

x = 0
roots = []
for _ in range(3):
    while (x**3 - x**2 + 5*x - 3) % 23 != 0: x+=1
    if x%23 not in roots: roots.append(x%23)
    x+=1
print(roots)

[6, 9]

We already know that the line $y=x-2$ is tangent to the elliptic curve at $(9,7)$. The other point at which it intersects the curve seems to be $(6, 4)$. The point that we are looking for is $2P$ which is the mirror image of this point about the x-axis i.e. $(6, -4)$ or $(6, 19)$.

These final two problems were especially interesting! I still need to read about these concepts in depth, however.

Anyways, the “solving a mystery” approach is really great. I was able to expose myself to a wide variety of cryptography concepts over the past five days without being bored for a single second thanks to it. I believe this approach is very similar to the Feynman technique for learning. I was able to identify gaps in my learning when I wrote them out like this, and then, with the help of the internet, fill those gaps. I believe that this approach can help me learn new programming concepts as well. You can probably expect blog posts to be more frequent than before.




Solving Cryptography Problems - 4

Here is today’s first problem:

Let the public key be $(y, p, g) = (64, 101, 2)$. The El Gamal Digital Signature of $11$ is $(r, s) = (8, s)$, where $s=$?

  • What is the El Gamal Signature Scheme?
    wikipedia: The ElGamal signature scheme is a digital signature scheme which is based on the difficulty of computing discrete logarithms. It was described by Taher Elgamal in 1985.

    my notes:

    1. Public / Private Keys:
      A triple $(y, p, g)$, where $p$ is a prime number, $g$ is a generator for $\mathbb{Z}_{p}^{*}$ and $y \equiv g^x \pmod p$ where x is the private Key.
    2. Signing:
      The signature of a message $m$ is a pair $(r, s)$. Since this is a probabilistic signature scheme, in order to generate such a pair, the signer begins by choosing a random number $k$ such that $0 \ne k \ne p-1$ and $\gcd (k, p-1) = 1$. Then,

      \[r \equiv g^{k} \pmod p \\ s \equiv (m - xr)\cdot k^{-1} \pmod{(p-1)}\]
    3. Verifying:
      Check that $g^{m} \equiv y^{r} r^{s} \pmod p$

    The equation for s in the Signing step was obtained as follows:

    \[g^m \equiv y^r r^s \pmod p \\ g^m \equiv g^{xr} g^{ks} \pmod p \\ g^m \equiv g^{xr + ks} \pmod p \\ m \equiv xr + ks \pmod{(p-1)} \\ s \equiv (m - xr) k^{-1} \pmod{(p-1)}\]

    The second-to-last step might be confusing. Since $g$ is a generator of $\mathbb{Z}_p^*$ and $p$ is a prime number, we have that

    \[g^z \equiv g^{z + (p-1)} \pmod p\]

    for any $z \in \mathbb{Z}$. In other words, the powers of $g$ are congruent modulo $p-1$.

For this problem, we need to find $s$. We already have the values of $m$,$r$ and $p$, which means we need the values of $x$ and $k$. Those can be found easily by examining these equations:

\[64 \equiv 2^{x} \pmod{101} \\ 8 \equiv 2^{k} \pmod{101}\]

It is clear that $x=6$ and $k=3$. We can now find $s$ as,

\[s \equiv (11 - 6 \cdot 8) \cdot 3^{-1} \equiv \frac{-37}{3} \equiv \frac{63}{3} \equiv 21 \pmod{100}\]

Therefore, $s=21$ is the solution to this problem.

Let’s move on to the next one:

The Hadamard gate is applied to the two qubits of a 2-qubit system in state

\[\frac{1}{2} (|00 \rangle + |01 \rangle + |10 \rangle + |11 \rangle).\]

What is the resulting state of the 2-qubit system?

My notes, this youtube video and this stackexchange answer allowed me to understand how we can apply a Hadamard gate to two qubits.

First, we can rewrite the given state of the 2-qubit system as:

\[\left(\frac{|0\rangle+|1\rangle}{\sqrt{2}}\right)\otimes\left(\frac{|0\rangle+|1\rangle}{\sqrt{2}}\right)\]

Now we will apply the Hadamard operation on each of these qubits,

\[H \left(\frac{|0\rangle+|1\rangle}{\sqrt{2}}\right) = \left(\frac{1}{\sqrt{2}} \begin{bmatrix}1 & 1\\1 & -1\end{bmatrix}\right) \left(\frac{1}{\sqrt{2}}\begin{bmatrix}1\\1\end{bmatrix}\right) = \begin{bmatrix}1\\0\end{bmatrix}\]

And finally take the tensor product of the output from the operation,

\[\begin{bmatrix}1\\0\end{bmatrix} \otimes \begin{bmatrix}1\\0\end{bmatrix} = \begin{bmatrix}1\\0\\0\\0\end{bmatrix}\]

which is equivalent to $\lvert 00\rangle$, the solution to this problem.

Even though I was able to solve this problem, I do not know anything about quantum computing. It seems like a very cool subject and I’d love to read and learn more about it. Until next time!




Solving Cryptography Problems - 3

Here’s the next problem:

The public key is $N=209$. What is the Rabin decryption of $80$?

  • What is Rabin decryption?
    wikipedia: The Rabin cryptosystem is an asymmetric cryptographic technique, whose security, like that of RSA, is related to the difficulty of integer factorization. However the Rabin cryptosystem has the advantage that it has been mathematically proven to be computationally secure against a chosen-plaintext attack as long as the attacker cannot efficiently factor integers, while there is no such proof known for RSA.

  • What is a chosen plaintext attack?
    wikipedia: A chosen-plaintext attack (CPA) is an attack model for cryptanalysis which presumes that the attacker can obtain the ciphertexts for arbitrary plaintexts. The goal of the attack is to gain information that reduces the security of the encryption scheme.

  • How does the Rabin Encryption scheme work?
    wikipedia: The keys for the Rabin cryptosystem are generated as follows:
    1. Choose two large distinct prime numbers $p$ and $q$ such that $p\equiv 3\bmod 4$ and $q\equiv 3\bmod 4$.
    2. Compute $n=pq$. Then $n$ is the public key and the pair $(p,q)$ is the private key.
  • Decryption
    Since 209 is not a large number, we can easily factorise it through trial and error:
i = 2
while 209 % i != 0: i+=1
print(i, 209/i)

11 19.0

Let $p=11$ and $q=19$. Now, following the procedure from wikipedia,

The message $m$ can be recovered from the ciphertext $80$ by taking its square root modulo $209$ as follows.

  1. Compute the square root of $c$ modulo $p$ and $q$:

    \[m_p = 80^{\frac{1}{4}(11+1)} \bmod{11} = 5 \\ m_q = 80^{\frac{1}{4}(19+1)} \bmod{19} = 17\]
  2. Using the extended Euclidean algorithm to find $y_p$ and $y_q$ such that

    \[y_p \cdot p + y_q \cdot q = 1\]
     def ExtEuclid (a,b):
     # returns a triple (d,s,t) such that d = gcd(a,b) and
     # d == a*s + b*t
     if b == 0: return (a,1,0)
     (d1, s1, t1) = ExtEuclid(b,a%b)
     d = d1
     s = t1
     t = s1 - int(a / b) * t1
     return (d,s,t)
    
     print('{} = 19*({}) + 11*({})'.format(*ExtEuclid(19,11)))
    

    1 = 19(-4) + 11(7)

    So we have $y_p = 7$ and $y_q = -4$.
    These two articles (this one and this one) were useful in understanding the algorithm.

  3. Using the Chinese remainder theorem to find the four square roots of $c$ modulo $n$: \(r_1 = (7 \cdot 11 \cdot 17 + (-4) \cdot 19 \cdot 5) \bmod 209 = 93\\ r_2 = 209 - 93 = 116\\ r_3 = (7 \cdot 11 \cdot 17 - (-4) \cdot 19 \cdot 5) \bmod 209 = 17\\ r_4 = 209 - 17 = 192\)

    One of these four values is the original plaintext $m$, although which of the four is the correct one cannot be determined without additional information.
    Of these four, $93$ is the only value that matches an option in my assignment, which means that it is the original plaintext in this case.

Further Reading / Questions:

Here’s the next one:

The public key is $N = 713$. What is the Rabin Digital Signature of $473$?

  • What is the Rabin Signature Scheme?
    From my class notes,
    Signature: $s = m^{1/2} \bmod n$ where $s$ is the signature
    Verification: $m = s^2 \bmod n$

Now I can think of two ways to solve this:

  • the one where we use pen and paper

    $x^2 \equiv 473 \bmod 713$
    $\implies x^2 \equiv 473 \bmod 23$ and $x^2 \equiv 473 \bmod 31$
    $\implies x^2 \equiv 13 \bmod 23$ and $x^2 \equiv 8 \bmod 31$
    $\implies x^2 \equiv 36 \bmod 23$ and $x^2 \equiv 225 \bmod 31$
    $\implies x \equiv \pm 6 \bmod 23$ and $x \equiv \pm 15 \bmod 31$

    We can then solve the four sets of equations using the Chinese Remainder theorem. These two videos (this one and this one) helped me in this approach.

  • the one where we use a brute force approach

      i = j = 1
      while j <= 4:
          while i**2 % 713 != 473: i+=1
          print(i)
          i+=1
          j+=1
    

Either way, the four roots we get are: $109$, $201$, $512$ and $604$.

Of these four, $201$ is the only one present in the given options in my assignment, so that is the solution to this problem.

Further Reading / Questions:

I clearly need to read more about Rabin’s cryptosystem, because the knowledge I have currently is not complete. I don’t want to make any commitments, except that if I encounter it again I’ll try to gain an in depth understanding of the cryptosystem and the problem solving techniques it involves (such as the Chinese remainder theorem).

Until next time!