Trusted Setup with Isogeny-based Cryptography

Trusted parties are fundamental in seting up secure communication among parties. For instance, a trusted setup is needed when establishing a trusted relationship between users and certain public information in a public-key infrastructure (PKI) for public-key encryption and signature schemes.

The risk with placing trust on a third party can be seen when they misbehave, causing the security of the scheme to be compromised. For example, if the trusted certificate authority of a PKI is corrupted and issues certificates for users without verifying their identities, there is no longer a guarantee on the privacy and authenticity of the communication.

For the full blogpost, click here.

-M x

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

Maths Behind Bitcoin

Bitcoin is a “worldwide cryptocurrency and digital payment system” that works without a central repository or single administrator. This system is peer-to-peer meaning that each computer can act as a server for the others, which allows for transactions to take place between users directly without an intermediary (or central server).

Bitcoins are not stored centrally, but rather exist as records in the block chain, which is a “distributed ledger”. To own a bitcoin simply means to have the ability to transfer control of it to someone else by creating a record of the transfer in the block chain. This ability is granted by access to an ECDSA (Elliptic Curve Digital Signature Algorithm) private and public key pair. What does this mean?

Algorithms

An algorithm is a process to make calculations. They are like machines: data comes in, and the algorithm does some work, and data comes out. ECDSA is the algorithm that creates the Bitcoin key pairs. To create a new key pair the elliptic curve is plotted across a finite field.

Elliptic Curves

An elliptic curve is represented algebraically as an equation of the form:

 y2 = x3 + ax + b

Elliptic curves have useful properties, such as a non-vertical line intersecting two non-tangent points on the curve will always intersect a third point on the curve. Furthermore, if the non-vertical line intersects a point tangent to the curve it will intersect precisely one other point. Using these properties it is possible to define two operations:

  • Point Addition: P + Q = R is defined as the reflection through the x-axis of the third intersecting point R’ on a line that includes P and Q.

math behind bitcoin

  • Point Doubling: P + P = R is defined by finding the line tangent to the point being doubled and taking a reflection through the x-axis of the intersecting point R’ on the curve.

point doubling

Finite Fields

In relation to ECDSA, a finite field is a predefined range of positive numbers within which every calculation must fall. If a number is outside of this range, it will wrap around so that it does fall within this range.

In order to understand, consider taking the modulus operator. For example, mod 7: here the finite field is modulo 7 and all answers in this field lie in the range 0 – 6.

ECDSA

Bitcoin defines the formula for the curve and the parameters of the field so that every user has the same graph. The parameters include:

  • the equation used;
  • the prime modulo of the field;
  • base point that falls on the curve.

The order of the base point is not independent of the other parameters, and can be thought of graphically as “the number of times the point can be added to itself until its slope is infinite.” The base point is selected so that the order is a large prime number.

In the case of bitcoin:

Elliptic Curve Equation: y2 = x3 + 7

Prime Modulo: 2256 – 232 – 29 – 28 – 27 – 26 – 24 – 1 = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

Base Point: 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

Order: FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

Source: coindesk.com

In ECDSA the private key is chosen as a number between 1 and the order. Then the public key is given by:

public key = private key * base point

Practically, the computation of the public key is broken down into point doubling and point addition operations starting from the base point.

This shows that the maximum number of private keys possible is equal to the order. However, Bitcoin has an enormous field:

There are 10^82 atoms in the universe. If you made the entire Universe our finite field and you drew a giant elliptic curve through it, each “point” in the universe would about 300 square atoms. At that size, each cell in your body takes up the space of 1,150,000,000 Bitcoin key pairs.

– www.cryptocoinsnews.com

Bitcoin Addressess

A Bitcoin address is not a public key; it is an RIPEMD-160 hash of an SHA256 hash of a public key. SHA256 and RIPEMD-160 are also algorithms that, unlike ECDSA, generate a hash. I have taken an example from cryptocoinsnews to illustrate a simple example of a hash (SHA256 and RIPEMD-160 are much more complex):

Every letter has a value of its position in the alphabet: A = 1, B = 2, etc.
Our hash algorithm is this:

for i=0 to len(word):
h = h + (i + letter_value)

So for the word “ABC” using our hash would be:

Loop for ‘A’
h = 0 + (0 + 1)
Loop ‘B’
h = 1 + (1 + 2)
‘C’
h = 4 + (2 + 3)
h = 9

‘ABC’ hashes to 9.

How Bitcoin Actually Works

Your private key is kept secret. This key allows you to unlock funds that are owed to you in the Bitcoin block chain.

When making a transacting, it contains a script that has your private key’s signature and the matching public key. This is in order to prove that the public key provided matches the private key that was used to make the signature. If the public key hashes with the Bitcoin address in the unclaimed transaction, it can be spent.

Hope you enjoyed this basic explanation of Bitcoin! M x

New Books in Mathematics: January 2017

Beyond Infinity: An Expedition to the Outer Limits of Mathematics

514qAHoauGL.jpg

Release Date: 14/03/2017

In this book, musician, chef and mathematician Eugenia Cheng reveals the astonishing inner workings of infinity.

Whilst pondering why some numbers are uncountable or why infinity plus 1 is not the same as 1 plus infinity, Cheng takes the reader on a journey from “math at its most elemental to its loftiest abstractions”.

Using inventive, intuitive metaphors and head-scratching puzzles, Cheng draws beginners and enthusiasts into the heart of this mysterious, powerful concept to reveal fundamental truths about mathematics from the infinitely large down to the infinitely small.

“Beyond Infinity is witty, charming, and crystal clear. Eugenia Cheng’s enthusiasm and carefully chosen metaphors and analogies carry us effortlessly through the mathematical landscape of the infinite. A brilliant book!” ―Ian Stewart, author of Calculating the Cosmos

The Mathematics of Secrets: Cryptography from Caesar Ciphers to Digital Encryption

k10826.gif

Release Date: 07/02/2017

As a lover of cryptography, I am always keen on finding new books on this topic. The Mathematics of Secrets is unique in the way it is structured; instead of organising the events historically, Holden shows how mathematics underpins the ways that different codes and ciphers operate. However, only high school algebra is needed to understand and enjoy this book.

With many historical anecdotes and real world examples, from one of the simplest and historically well-known ciphers – the Caesar cipher – to modern day public-key ciphers, The Mathematics of Secrets uncovers the mathematics in the science of coded messages.

A Man for All Markets: From Las Vegas to Wall Street, How I Beat the Dealer and the Market

51fbd619ksl-_sx326_bo1204203200_Release Date: 24/01/2017

This book is based on the true story of Edward O. Thorp, a card-counting mathematics professor, who taught the world how to beat the dealer, and ushered in the era of quantitate finance we live in today.

Thorp tells the story of “what he did, how he did it, his passions and motivations, and the curiosity that has always driven him to disregard conventional wisdom and devise game-changing solutions to seemingly insoluble problems.”  A Man for All Markets is a great book for anybody interested in the more applied side of mathematics, and challenges readers to think logically about a seemingly irrational world.

“An amazing book by a true icon . . . Edward O. Thorp launched revolutions in Vegas and on Wall Street by turning math into magic, and here he weaves his own life lessons into a page-turner as hot as a deck full of aces. Loved it!”

Ben Mezrich, New York Times bestselling author of Bringing Down the House and The Accidental Billionaires

Read my last ‘New Books in Mathematics’ post here. M x

Choosing a Password

It has been argued that password systems are not a good way to authenticate. This is due to the fact that either they’re difficult to remember or they’re easy to remember, but therefore also easy to crack. So how do we choose a good password? XKCD posted this image suggesting a strategy for creating a password:

password_strength.png

This method is trying to eradicate to age old way of creating passwords that are, in fact, almost impossible for us to remember but relatively easy for a computer to crack.

The password suggested by XKCD (although now not a good password because everyone knows about it!) is practically resistant to the brute force approach, because, although it is composed of only lowercase letters, it is too long. Therefore, the method used to break this password would be the dictionary attack method. However, these words would probably not come up in a dictionary together as they aren’t usually associated to one another.

But what happens when this method (stringing together four words) becomes common practice? A method to combat this might be to look at the top 10,000 english words and try different combinations of these words until the password is found. Therefore, it is safest to always assume that the password cracker knows the method that you are using and so we must choose at least one uncommon word that is hard to guess, such as mirth, to include in the password. This will make it extremely difficult to crack.

M x

Modular Arithmetic, What’s the Point?

What is Modular Arithmetic?

Modular arithmetic, also known informally as ‘clock arithmetic’, is when numbers ‘wrap around’ upon reaching a fixed quantity – the modulus.

To illustrate this, consider a 12 hour clock divided into 12 hour periods.

Clock face numbered 1--24

When it is “13 o’clock” we say it is 1 o’ clock again, and “14 o’ clock” becomes 2 o’clock, etc. What we are saying essentially is that “13 = 1 + a multiple of 12” or alternatively “the remainder when you divide 13 by 12 is one”. To write this mathematically, we say 13 ≡ 1 mod 12 (13 is congruent to 1 modulo 12). 

More formally, for a positive integer n, two integers and are said to be congruent modulo n:

if a – b is an integer multiple of n.

Why is it useful?

Modular arithmetic is extremely useful in number theory; it can be used to find out information about the solutions of a specific equations, such as Diophantine equations.

For example, let us take the equations

  1. 3a + 5b = 8
  2. 3a + b = 2

If I apply mod 3 to these equations:

  1. 0 + 2b ≡ 2 mod 3, or b ≡ 1 mod 3
  2. 0 + b ≡ 2 mod 3, or b ≡ 2 mod 3

This is a contradiction, as there is no integer b that that can be 1 mod 3 AND 2 mod 3, hence there is no integer b that satisfies these equations.

Modular arithmetic is used in the video below as a tool to prove something about an equation:

Additionally, in cryptography, modular arithmetic underpins public key systems such as RSA.

The basic principle of RSA is the fact that it is practical to find three very large positive integers e, d and n such that for all m:

However, even if you know e, n or even m it is extremely difficult to find d. As d is essential for decryption, this ensures that the informations remains protected. Click here for more information on RSA.

Sources: 1 | 2 | 3

Have you come across modular arithmetic before? M x