New Blog Features!

I’m happy to announce that I have two new features on my new blog:

  • You can now subscribe! Use the link either in the header or at the bottom of each post. Once you subscribe, you will be updated by email when a new post is up.
  • You can share on Facebook, Twitter etc. using the red button on the bottom right of each post. Currently, this doesn’t work on Firefox, but it does work on Chrome!

The next step is getting a comment box at the end of each post! M x

MOVED BLOG

Just a quick post to let you all know that have decided to shift my blog onto GitHub: mariascrs.github.io. This way I can integrate Latex easily into my posts! I still haven’t figured out how to get a subscribe feature on the website but don’t worry, I will continue to post links to my new blog posts on this blog so you can still be notified when I post!

I have just posted a new post on ‘Isogenies for Cryptography’ so let me know what you think. – M

Post Quantum Cryptography – The Basics

Post-quantum cryptography aims to find schemes that can withstand an attack from a quantum computer. This is becoming an increasingly important field of research as the development of quantum computers intensifies and current cryptography schemes relying on the difficulty of factorisation can be broken in polynomial time by these quantum computers. So, researchers have tried to find other ‘hard’ problems in mathematics (take exponential time to solve) that can be exploited to create classical crypto schemes that withstand attack of quantum computers (at least for now).

In general post-quantum schemes require more resources compared to traditional cryptography, in particular Elliptic Curve cryptography; security against quantum computer attacks come at a cost. There are four different families of post-quantum schemes that are considered to be the best candidates, and in this blog post I will briefly discuss each of them.

Code-Based Cryptography

Traditionally, error-correction codes are used to detect and correct bit errors when messages are transmitted over an unreliable channel. The code can be chosen to fulfil the requirements of the channel; in particular the number t of correctable bit errors can be determined.

Decoding arbitrary codes is computationally hard and can be infeasible depending on the code parameters. However, there are specific codes for which efficient decoding algorithms are known. So in practice only such codes are used that have efficient decoding algorithms.

The main security assumption of code-based cryptography is the difficulty of decoding a random linear code. Even with quantum computers, only exponential-time algorithms are known.

The first code-based public key crypto system was proposed by McEliece in 1978 and has not been fundamentally broken since, however the main problem with this is the size of the keys: it requires key sizes of about 4MB in order to achieve post-quantum security. Niederreiter introduced a scheme that gave some improvements to the encryption and decryption cost and required smaller keys.

There have been many attempts to reduce key sizes by using different codes that have some redundant structure in the public key. But this structure has led to efficient classical attacks on the crypto-systems. 

There are also signature schemes, hash functions and random number generators based on code-based cryptography. 

Lattice-Based Cryptography

The underlying ‘hard’ problem is the shortest vector problem (SVP): a basis of a vector space V and a norm N are given for a lattice L and one must find the shortest non-zero vector in V, as measured by N, in L. It is believed that the SVP is computationally hard even for quantum computers.

NTRUEncrypt is a commercial public key encryption scheme based on lattices. Public key sizes of about 1.5kB to 2kB are required in order to achieve the desired security. Note that these are the requirements based on the algorithms that have (up to today) been developed to solve the SVP. These restrictions are called ‘parameters’.

Closely related is the signature scheme NTRUSign. However, the security of this is not yet well understood and so there are no recommendations for these signature schemes for post-quantum security.

There are also key exchange protocols that are built on lattice-based cryptography, such as NewHope that has been experimentally adopted by Google. NewHope is not symmetric and needs two rounds of agreement (unlike the Diffie-Hellman Key Exchange). Also, it does not include authentication, so this needs to be achieved by other means.

By switching to post-quantum key exchange now, an attacker in the future does not learn encryption kets even if he breaks long-term authentication keys. Therefore, combining a post-quantum key exchange with a classical authentication scheme provides a cost effective long-term secure authenticated key exchange for the interim period until all cryptographic primitives have been transitioned to post-quantum secure schemes.

Hash-based Cryptography

Hash functions are one-way functions tha tmap bit strings of an arbitrary length to relatively short, fixed length bit strings called hash values. There are three required properties:

  • Pre-image resistance: must be hard to compute a pre-image of a hash value i.e. a bit string that once hashed results in a given hash value.
  • Second pre-image resistance: given a bit string, it must be hard to find a different bit string that has the same hash value.
  • Collision resistance: it must be hard to find two arbitrary bit strings that have the same hash value.

Since by definition it is not computationally feasible to compute the inverse of a hash function it is not known how to construct public-key encryption schemes using hash functions. However, it is possible to construct signature schemes, where in general the required signature size increases if more signatures for the same public key are needed.

Hash-based signature schemes have been around for a long time and so the estimates of the required parameters to achieve post-quantum security are very reliable.

Multivariate Cryptography

This is based on the difficulty of the MQ-problem: solving multivariate quadratic systems of equations over finite fields is NP hard (no efficient algorithm for solving random multivariate polynomial systems). The difficulty depends on the size of the underlying field, the number of variables and the degree of the system. If the number of equations and variables is sufficiently large then even quadratic equations over a the field with two elements are hard to solve.

For constructing an asymmetric public-key scheme, the public-key itself is a set of multivariate quadratic polynomial and the private key often is the knowledge of a trapdoor that allows to efficiently solve the multivariate system. The construction of the scheme allows the use of systems with more variables than equations, so there may be more that one solution. Any of these solutions is a valid signature.

The confidence in multivariate systems is quite high however a relatively large public key is required. Attempts to reduce key sizes by using few variables over larger fields, but the security of such systems is not well understood. The second approach is to use sparse systems in order to compress the public key, but this often leads to a loss in security. 

For public key encryption, we need the resulting equation system to only have one solution and so we must have an over-defined system i.e. the public key must have more polynomials than variables. Currently there are not many multivariate public-key encryption schemes that are considered secure. 

Multivariate cryptography can also be used for pseudo random-number generators, cryptographic hash functions and symmetric encryption, e.g. the symmetric block gopher QUAD.

What about Elliptic-Curve Cryptography?

I have talked about elliptic curve cryptography in previous blog posts, so why isn’t this mentioned?

Due to the novelty of these cryptographic schemes there is not great confidence in them yet. So they are not currently consensually considered as candidates for post-quantum public-key encryption. 


This is the first installation in my series about post-quantum cryptography. Anything you want me to talk about in particular? M x

Is the COVID-19 Tracing App secure?

There has been a lot of talk about the COVID-19 tracing app that has been recently released. The simple premise is that the app will use Bluetooth signals to log on when smartphone owners are close to each other, so if someone develops COVID-19 symptoms, an alert can be sent to other users they may have infected. However, countries and organisation developing the apps have opted for two different types of systems to achieve this: centralised systems or decentralised systems. First, I will what these are in general.

Centralised Systems

Centralised systems rely on a single server as a core distribution centre in the communication with end users. From a functional perspective they often imply that each entity involved in the software stream has a specific, distinct role. For example, when streaming a movie on Netflix, Netflix’s central server provides the video; the user consumes it. However, this also means that if the central server is compromised, the entire network is.

Decentralised Systems

Decentralised systems eliminate the need for a central entity and rely on multiple servers or end-user devices to cooperate and undertake a given task. Each of these entities is tasked with a similar role. These systems are not a novel concept and in fact there are a vast array of places in which it has been implemented, such as blockchain technology. Most decentralised systems that preserve privacy focus on ensuring either the confidentiality and anonymity of personal data (such as ‘TOR’) or user control over your personal data (such as the MIT project ‘Enigma’).

In context of COVID-19 Tracing Apps

Centralised contact-tracing apps store a user’s Bluetooth ID in a central database as well as the Bluetooth IDs of phones they have come into contact with (and any other data that’s being collected), enabling better visibility of data by health services or governments.

Decentralised contact-tracing apps only stop a user’s Bluetooth ID (and any other data being collected) in a central database and contact-tracing is done at the phone level, without sharing the information centrally. This allows for stronger data privacy.

Source: BBC News

There is a key trade-off between these two approaches: do we want to maximise data availability to health services or do we want to protect privacy of individuals? Furthermore, should it be up to individual governments or companies to make this choice? This is especially important as these two systems don’t interact well with each other, meaning that the fact that various countries are opting for different systems may prove disastrous for allowing tracing across borders and so quarantine rules may have to stay in place even with the introduction of the app.

UK App – Apple and Google are involved?

NHS officials initially decided to build a centralised system, but the NHS could not get the same accuracy as if it was using Apple and Google’s software. The second version of England’s app uses Apple and Google’s technology and opts for the decentralised approach.

The ecosystems of Apple and Google are fundamental to the NHS app. The app uses the Apple and Google system to conduct the Bluetooth contact tracing. This is achieved through an API and require some of the latest versions of the Android and iOS operating systems to run. The companies have favoured the method that puts people’s privacy at the forefront in order to stop the technology from being used maliciously.


What are your thoughts on the COVID-19 tracing app? M x

4: An Example

In this blog post I will show you how you can use the tools developed in parts 1, 2 and 3 to solve a problem in number theory.

Determine all the integer solutions of the equations x2 − 3y2 = m for m = −1 and 13.

Noting that x2 − 3y2 = (x – √3y)(x + √3), first we find the fundamental unit, e = a + b√3, of the number field Q(√3):

For b = 1, 3b2 + 1 = 4 = 2and so a = 2. Hence the fundamental unit is e = 2 +√3.

First we note that the norm of an element in Q(√d) is:

N(a + b√d) = a2 − db2

We will use the following three facts:

  1. N(x + √3y) = x2 − 3y2 = m.
  2. If we have a unit u, then N(a) = N(ua) for some a in Q(√d), as N(u) = 1 and N(ua) = N(u)N(a) (i.e. norm is multiplicative).
  3. In the last post, we saw how the units in the ring of algebraic integers of L is of the form:

Screenshot 2019-10-13 at 10.01.15 PM.png

Thus, multiplying x + √3y by a unit is equal to multiplying x + √3y by a power of the fundamental unit e.

So how do we solve this equation? First, by fact 1 we have to do find the element of Q(√3) that has norm +m or -m (there will be one such element for each, up to multiplication by a unit). Using fact 1 and 2, we deduce all the solutions to the equation are given by (x, y) such that:

  • N(e) = – 1, N(x + √3y) = -m: en(x + √3y) for n a natural number.
  • N(e) = – 1, N(x + √3y) = m: e2n(x + √3y) for n a natural number.
  • N(e) = 1, N(x + √3y) = m: en(x + √3y) for n a natural number.

m = -1

Noting that for any element a,|N(a)| = 1 if and only if a is a unit. Hence as the solutions are given by (x, y) where N(x + √3y) = -1, we must have that x + √3y is a unit. But,

Screenshot 2019-10-13 at 10.01.15 PM.pngso all units have norm 1, and thus there are NO integer solutions to this equation.

 m = 13

We need to find (x, y) such that N(x + √3y) = x2 − 3y2 = 13 (because N(e) = 1).

  • When y = 1, x2 = 14, so x is not an integer.
  • When y = 2, x2 = 25, so x = 5.

Hence we get that all solutions are of the form:

en(5 + 2√3), for n a natural number and e = 2 +√3, fundamental unit


This is the last post of this series! Next I’ll be delving into Galois Theory. M x

 

3: Dirichlet’s Unit Theorem

Last time, I discussed Dedekind’s Criterion. In this post I aim to introduce Dirichlet’s Unit Theorem.

Let L be a number field (finite extension of the field of rational numbers).

We will define a complex embedding of L as being a field homomorphism:

Screenshot 2019-10-12 at 6.49.21 PM.png

Then a real embedding of L  is similarly defined as being a field homomorphism:

Screenshot 2019-10-12 at 6.49.57 PM.png

We note that the complex embeddings can be given in pairs:

Screenshot 2019-10-12 at 6.51.38 PM.png

where we obtain one embedding by taking the complex conjugate of the other embedding in the pair.

Hence, given a number field L, we can label its real embeddings as

Screenshot 2019-10-12 at 6.57.45 PM.png

and its complex embeddings as

Screenshot 2019-10-12 at 6.58.36 PM.png

Noting that the degree, n, of the field extension L/Q (where Q is the field of rational numbers) is equal to the total number of embeddings and hence we deduce that n = 2s + r. The fact that there is this equivalence is non-trivial, so don’t worry if you don’t immediately see why this is! In order to prove this we must use tools from Galois Theory, such as something called the ‘Tower Law’, and therefore I will emit the proof from this blog post.


Let me know if you’re interested in seeing Galois Theory related posts in the future!


Letting Screenshot 2019-10-12 at 7.01.18 PM.png be the units in the ring of algebraic integers of L we are now ready to state Dirichlet’s Unit Theorem.

Dirichlet’s Unit Theorem

Screenshot 2019-10-12 at 7.04.57 PM.png

The proof of this is rather complicated and involves defining a map, whose kernel is this finite cyclic group, which takes Screenshot 2019-10-12 at 7.01.18 PM.png into a lattice. Considering lattices are involved in the proof, you can start to see where the isomorphism with the integers comes from.

Why is this useful?

Take the case where r = 0 and s = 1, i.e. L is an imaginary quadratic number field:

Screenshot 2019-10-12 at 7.11.23 PM.png

As r + s – 1 = 0, we get that Screenshot 2019-10-12 at 7.01.18 PM.png is a finite group. By explicitly defining the isomorphism we can deduce that the finite cyclic group is simply {+/- 1}, and Screenshot 2019-10-12 at 7.01.18 PM.png is generated by one element – the fundamental unit, i.e.

Screenshot 2019-10-12 at 7.17.07 PM.png

I’ve purposefully skipped a lot of the details as what is important is the result. The proof requires a bit of magic and is not terribly enlightening. However, the result is extremely important – using this, for the case of imaginary quadratic fields, we can completely specify Screenshot 2019-10-12 at 7.01.18 PM.png, provided we find the fundamental unit.

Finding the Fundamental Unit

It turns out that finding the fundamental unit in this case is extremely straightforwards. There are various different cases.

  • If d = 2, 3 (mod 4) we characterise the fundamental unit u in the following way: let b be the least positive integer such that db2 + 1 or db2 – 1 is of the form a2 for some natural number a. Then:

Screenshot 2019-10-12 at 7.25.39 PM.png

  • If d = 1 (mod 4) and d is not equal to 5: let b be the least positive integer such that db2 + 4 or db2 – 4 is of the form a2 for some natural number a. Then:

Screenshot 2019-10-12 at 7.27.40 PM.png

  • If d = 5: 

Screenshot 2019-10-12 at 7.28.33 PM.png

(If you would like the proof as to WHY this is true, leave me a comment below and I’ll be happy to make a post!)

Example: d = 2

Then 𝑏 = 1 works since 2 − 1 = 1so 1 + √2 is a fundamental unit.


In order to get a lot of the symbols I had to LaTex some of the sections so sorry if the formatting is a little off! Next time we will start solving some equations using algebra!

M x

2: Dedekind’s Criterion

In episode 1, I introduced the idea of prime ideals. Today we will extend this idea and prove a really important result in algebraic number theory: Dedekind’s Criterion.

We will use the following fact:

If P, contained in O, is a non-zero prime ideal, then there is a unique prime number p such that pP.

For those who are more advanced, this is because the ideal generated by p, namely (p), is the kernel of

Screen Shot 2019-09-17 at 11.12.53 AM.png

Then P|pOand N(P) = pfor some f > 0.

The proof of Dedekind’s Criterion uses a lot of Group Theory and therefore I will not prove it for you. However, it is a really useful tool in algebraic number theory and so I will state it and show how it can be used to factor ideals (remember that in episode 1 we showed that this factorisation is unique).

Before stating the theorem, let me define a few things:

  • Let 𝛼 ∈ Othen Screen Shot 2019-09-17 at 11.39.55 AM.png(𝛼) = { x + 𝛼y | x, y ∈ Screen Shot 2019-09-17 at 11.39.55 AM.png}
  • Let 𝐿/𝐾 be a field extension and let 𝛼 ∈ 𝐿 be algebraic over 𝐾 (i.e. there is a polynomial p with coefficients in such that p(𝛼)=0). We call the minimal polynomial of 𝛼 over 𝐾 the monic polynomial 𝑓 with coefficients in K of the least degree such that f(𝛼) = 0.
  • Say we have a polynomial p(x) = anx+ an-1xn-1 … + a1x1 + a0  with coefficients in K. Then its reduction mod p is defined as p(x) = anx+ … + a0 where ai  ≡ ai (mod p).
  • In episode 1 we defined the degree of a field extension L/K. We denote this as [L:K].
  • Z/pZ is the additive group of the integers mod p. For p prime, this is a finite field. We usually denote this as Fp.

Okay, now we’re ready for the theorem!

Theorem: Dedekind’s Criterion

Let 𝛼 ∈ Obe such that 𝐿 = Q(𝛼). Let 𝑓(x), with integer coefficients, be its minimal polynomial and let 𝑝 be a prime integer such that 𝑝 does not divide the degree [O∶ Z[𝛼]]. Let 𝑓(x) be its reduction mod p and factor

Screen Shot 2019-09-17 at 12.02.55 PM.png

where g1(x), … , gr(x F𝑝 [x] are distinct monic irreducible polynomials. Let gi(x) ∈ Z[x] be any polynomial with gi(x) (mod 𝑝) = gi(x), and define

Screen Shot 2019-09-17 at 12.11.25 PM.png

an ideal of OL. Let f= deg gi(x).

Then p1 ,…, pare disjoint prime ideals of OL and

Screen Shot 2019-09-17 at 12.14.55 PM.png

If you don’t quite understand the theorem, don’t worry! The first time I read this I was really confused as well. I think the more examples you see and the more you use it the easier it becomes to understand. Because of this, I will give you an example next.

Example

Let L = Screen Shot 2019-09-17 at 11.39.55 AM.png(√−11) and p = 5. We will use the following result:

Let d ∈ Z be square-free and not equal to 0 or 1. Let L = Screen Shot 2019-09-17 at 11.39.55 AM.png(√d). Then 

Screen Shot 2019-09-17 at 12.20.18 PM.png

As – 11 = 1 (mod 4), OLScreen Shot 2019-09-17 at 12.22.14 PM.png. Then, [OL: Z[√−11]] = 2 and so we can apply Dedekind’s criterion to 𝛼 = √−11 for p = 5. Then the minimal polynomial is f(x) = x+ 11, so 𝑓(x) = f(x) (mod 5) = x+ 1 = (x+2)(x+3) F5 [x].

Therefore by Dedekind’s Criterion, 5OL= P·where

P = (5, √−11 + 2) and Q = (5, √ −11 + 3)

and P, Q are distinct prime ideals in OL. So we have found how 5 splits in Screen Shot 2019-09-17 at 11.39.55 AM.png(√−11).


In the next episode I will talk about Dirichlet’s Unit Theorem and then we will be ready to solve some problems in Number Theory!

M x

I’m back!

After a long year of university filled with lots of ups and downs, I am finally back! I decided to take a year out of blog post writing to focus on my final year as an maths undergraduate. A year later, I have finished my final exams and found out that I did well enough to get a spot in the masters program! Feeling refreshed and filled with one more year of maths to share, I am ready to start writing regular posts again.

Thank you for staying subscribed despite my lack of output this year and hopefully see you in many more posts to come!

M x

MATHS BITE: Pinwheel Tiling

Pinwheel tiling is a type non-periodic tiling that was defined by American mathematician Charles Radin based on a construction by John Conway. They are the first known non-periodic tilings where the tiles appear in infinitely many orientations.

Conway Tessellation

Given a right angle triangle T with side lengths 1, 2 and {\sqrt {5}}, Conway noticed that we can divide it into five copies of its image by the dilation of factor 1/{\sqrt  {5}}

Source: Wikipedia

By rescaling, translating and rotating, we can iterate this to obtain and infinite increasing sequence of growing triangles. If we take the union of these triangles, we obtain T. It is this increasing sequence of triangles that defines the Conway tiling.

We observe that the triangles appear in infinitely many orientations. (This is because arctan(1/2) and arctan(2), two angles in the triangles, are both not proportionate to \pi ). Extraordinarily, despite this all the vertices have rational coordinates!

Tiling

Based on this tessellation, Radin defined a tiling:

Source: Wikipedia

Architecture

Federation Square, a building complex in Melbourne, Australia has this pinwheel tiling.

Federation Square - Melbourne, Australia

File:Federation-square-sandstone-facade.jpg

M x