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

Elliptic Curves: The Basics

Working over the rationals (or more precisely any field with characteristic 0) an elliptic curve is a curve given the equation

such that the discriminant, which is 4A3 + 27B2, is non-zero. Equivalently, the polynomial on the right hand side has distinct roots, ensuring that the curve is non-singular. Though we restrict our attention to these non-singular curves we note that if the right hand side is a cubic polynomial, there are only two types of singular curves, corresponding to whether there is a double root (node) or triple root (cusp).

Source: Wolfram Mathworld

Point at Infinity

The point at infinity is an important point that always lies on an elliptic curve. For those who have studied algebraic geometry this is a familiar concept and comes from defining a projective closure of the equation defining the elliptic curve. However, informally it can be described as an idealised limiting point at the ‘end’ of each line.

If you imagine a vertical straight line, which intersects the elliptic curve at most two times.

The point at infinity is the point at which the two ends of this vertical line ‘meet’.

The reason that elliptic curves are amazing objects is because we can use geometry to make the points on the curve a group. Therefore we can use tools from algebraic number theory to study them.

Making Points on an Elliptic Curve into a Group

This is done using the chord and tangent process:

We denote the point at infinity on an elliptic curve E over Q as OE. E meets each line in 3 points, counted with multiplicity. Given two points on E, say P and Q, let R be the third point of intersection of PQ and E. Then P ⊕ Q is the third point of intersection of OER (vertical line through R) and E.

Source: jeremykun.com

If P = Q we take the tangent at P instead of the line PQ.

Then E with the group law on points defined above, denoted by (E, ⊕), is an abelian group:

  • The fact that is abelian is clear by construction
  • Identity: OE – this is why the point at infinity is such an important point and exists on all elliptic curves.
  • Inverses: Given a point P, let S be the point of intersection of the tangent at OE and E. Then let Q be the intersection of PS and E. Then the inverse of P is defined to be Q. Note that if OE is a point of inflection (point of multiplicity 3) then S = OE in the above.
  • Associativity: This is much harder to prove. It can be done by identifying (E, ⊕) with a subgroup of the Picard Group, which related to something called divisors.

Divisors are a tool for keeping track of poles and zeroes. For example, suppose a function g has a zero at a point P of order 3, and a pole at another point Q of order 2, and a pole at O of order 1 (note the number of zeroes and poles are equal, as they must be for a function). Then using divisors, we can say all this concisely as follows:

div g=3P−2Q−O

More precisely, we can define a divisor D to be a ‘formal sum’ of points on E (meaning that we write a sum of points using a + symbol but no actual operation is defined), say

Then the degree of a divisor is the sum of the coefficients.

This set of divisors forms a group, Div(E), generated by the points on E. Immediately we can identify a subgroup of Div(E), namely the divisors of degree zero denoted Div0(E).

We can also define an equivalence relation ~ on divisors: D1, D2 ∈ Div(E) are linearly equivalent, written D1 ~ D2, if exists an f such that div(f) = D1 – D2.

We can now introduce the Picard Group. It is a subgroup of Div(E), defined by quotienting out by this equivalence relation

A subgroup of the Picard group is given by

We’re now ready to go back to talking about elliptic curves. The point of this discussion is that we know (Pic0(E), +) is a group which has the associative property. Furthermore, we can show that we have a bijection between (E, ⊕) and (Pic0(E), +) that preserves the group structure i.e. we have an isomorphism of groups. So, using this isomorphism we can identify the two groups and deduce that (E, ⊕) is also associative.

Consequence

Say we started looking at points defined over Q (denoted by E(Q)). A natural question is to ask how we know that the addition or inverses of these points remains in Q?

We defined the group law by looking at the intersections of lines and curves. So, working through the algebra, we can get explicit equations for the addition of points and inverses. For example if we have an elliptic curve E over Q and a point P = (x,y) in E(Q), then -P = (x, -y).

These explicit equations are useful because they tell us that the points do indeed remain defined over Q. More precisely, we find that (E(Q), ⊕) is a subgroup of (E, ⊕):

  • The identity OE is in E(Q) by definition
  • (E(Q), ⊕) is closed under addition and has inverses by the explicit formulae
  • Associativity and commutativity is inherited from (E, ⊕).

Note: This in fact holds for any field K, not just Q, but we must be a bit more careful, as the elliptic curve may not be expressible in the nice form y2 = x3 + Ax + B so the formulae are a bit messier. The reason why this is important is that we often want to consider elliptic curves over finite fields, something I will explore in future posts.

M x

MATHS BITE: Stars and Bars

A common problem in combinatorics is when we are asked to count the number of ways to group identical objects, such as placing indistinguishable balls into labelled urns. Popularised by William Feller in his book on probability, the Stars and Bars methods aims to solve such problems.

Theorem

The number of ways to put n indistinguishable balls into k labelled urns is

Related image

Proof using Stars and Bars:

Represent n balls by n adjacent stars and consider inserting k – 1 bars between the starts to separate them into k groups.

For example, for n = 12 and k = 5 the following is a possible arrangement:

**|****||***|***

Here, urns 1, 2, 3, 4 and 5 are of size 2, 4, 0, 3 and 3 respectively.

There are a total of n + k – 1 positions, of which n are stars and k – 1  are bars. So, the number of ways to place n indistinguishable balls into k labeled urns in the same as the number of ways of choosing n positions (or k – 1 positions) amount n + k – 1 spaces, with all the remaining positions taken as bars (stars), i.e.

Related image

ways.

M x

MATHS BITE: Sierpinski Number

A Sierpinski number is an odd natural number k such that {\displaystyle k\times 2^{n}+1} is not prime for all natural numbers n. In 1960, Sierpinski proved that there are infinitely many odd integers k with this property, but failed to give an example. Numbers in such a set with odd k and k < 2^n are called Proth numbers.

78557, 271129, 271577, 322523, 327739, 482719, 575041, 603713, 903983, 934909,….

-List of some known Sierpinski Numbers

Sierpinski Problem

The Sierpinski problem asks what the smallest Sierpinski number is. In 1967, Sierpinski and Selfridge conjectured that 78557 is the smallest Sierpinski number. To show this is true, we need to show that all the odd numbers smaller than 78557 are not Sierpinski numbers, i.e. for every odd k below 78557 there is a positive interger n such that {\displaystyle k\times 2^{n}+1} is prime. There are only five numbers which have not been eliminated:

k = 21181, 22699, 24737, 55459, and 67607

Numberphile Video

Find out more here. M x

MATHS BITE: Wythoff’s Game

Wythoff’s game is a two-player mathematical strategy game. It is played with two piles of counters and goes as follows:

Players take turns to remove counters from one, or both piles (if they are removing stones from both piles, they must remove the same number of stones from each). The game ends when one person removes the last counter, or counters, thus winning.

It is name Wythoff’s game, as it was Dutch mathematician W. A. Wythoff that published a mathematical analysis of the game in 1907, although it was previously know in China as tsyan-shidzi (“choosing stones”).

Optimal Strategy?

Any position of the game can be described by a pair of integers (x,y) where x≤y. This describes the size of both piles in the position.

The strategy of the game involves cold and hot positions:

  • A cold position is one where the player whose turn it is to move will lose, even with his best move;
  • A hot position is one where the player whose turn it is to move will win with his best move.

Thus, the optimal strategy for a person in a hot position is to move to a cold position.

We can classify the positions as hot or cold recursively, using 3 simple rules:

  1. (0,0) is a cold position;
  2. Any position from which a cold position can be reached in a single move is a hot position;
  3. If every move leads to a hot position then the position is cold.

For example (taken from Wikipedia):

“all positions of the form (0, y) and (y, y) with y > 0 are hot, by rule 2. However, the position (1,2) is cold, because the only positions that can be reached from it, (0,1), (0,2), and (1,1), are all hot. The cold positions (x, y) with the smallest values of x and y are (0, 0), (1, 2), (3, 5), (4, 7),(6,10) and (8, 13).”

Connection with the Golden Ratio

Wythoff discovered that the cold positions can be determined using the Golden Ratio. Namely, if n is any natural number, then

Screen Shot 2017-11-05 at 5.54.53 PM.png

is a cold position (where we use the floor function and φ is the Golden Ratio).

To read more, click here.

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

How to Solve It

In 1945, Hungarian mathematician George Pólya wrote an extremely successful book called How to Solve It, which sold over one million copies and has been translated into 17 languages. In this book, Pólya identifies the four basic principles of problem solving.

1. Understand the Problem

Firstly, you must understand the problem you are tackling.  Although this may seem like common sense, it is often overlooked; the amount of times I’ve been staring at a problem for hours because I haven’t fully understood what it is asking! Consider asking the following questions:

  • What is the unknown? What are the data? What is the condition?
  • What are you asked to find or show?
  • Can you restate the problem in your own words?
  • Do you understand all the words used in stating the problem?

For some areas in maths, such as mechanics, drawing a labelled figure can often be extremely helpful to visualise what is going on.

Resultado de imagem para free body diagram
Example of Diagram


2. Devise a Plan

There are many different suitable ways to solve a problem, as mentioned by Pólya. However, it is important to choose an appropriate strategy, which is a skill learnt by solving many problems. Some strategies include:

  • Guess and check
  • Use symmetry
  • Consider special cases
  • Solve an equation or use a formula
  • Look for a pattern
  • Solve a simpler problem
  • Work backwards
  • Eliminate possibilities

When choosing a strategy, it may help to consider whether you have solved a related problem already or whether you can think of a familiar problem that has the same or similar unknown.


3. Carry out the Plan

Once you have devised the plan, this step is simple if you already have the necessary skills, often only required care and patience -try to avoid silly mistakes!

Persist with the plan that you have chosen, only discarding it after multiple failed attempts. Then, return to step 2.

4. Look back

Pólya highlights how a lot can be gained from looking back and reflecting on the work you have done, asking yourself what worked and what didn’t. This way you can implement strategies that were successful for future problems that are similar.


Read more here.

M x

MATHS BITE: The Kolakoski Sequence

The Kolakoski sequence is an infinite sequence of symbols {1,2} that is its own “run-length encoding“. It is named after mathematician Willian Kolakoski who described it in 1965, but further research shows that it was first discussed by Rufus Oldenburger in 1939.

This self-describing sequence consists of blocks of single and double 1s and 2s. Each block contains digits that are different from the digit in the preceding block.

To construct the sequence, start with 1. This means that the next block is of length 1. So we require that the next block is 2, giving the sequence 1, 2. Continuing this infinitely gives us the Kolakoski sequence: 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, etc.

M x

Diophantine Approximation: Liouville’s Theorem

Diophantine approximation deals with the approximation of real numbers by rational numbers.

Liouville’s Theorem

In the 1840’s Liouville obtained the first lower bound for the approximation of algebraic numbers:

Let α ∈ R be an irrational algebraic number satisfying f(α) = 0 with non-zero irreducible (cannot be reduced) f ∈ Z[x] of degree d. Then there is a non-zero constant C such that for every fraction p/q

Screen Shot 2016-12-11 at 10.35.05 AM.png

Proof

The proof utilises the mean value theorem. By this theorem, given p/q, there is a real ξ between α and p/q such that

Screen Shot 2016-12-11 at 10.35.08 AM.png

Since f has integer coefficients and is of degree d, the value of f(p/q) is a rational number with denominator at worst q^d. Since f is irreducible, f(p/q) cannot be equal to 0. Thus

Screen Shot 2016-12-11 at 10.40.22 AM.png

and so

Screen Shot 2016-12-11 at 10.40.58 AM.png

A corollary of this result is that numbers that are well approximable by rational numbers, i.e. in for every d ≥ 1 and positive constant C, there is a rational p/q such that

Screen Shot 2016-12-11 at 10.43.32 AM.png

are transcendental.

Example

Letscreen-shot-2016-12-11-at-10-45-22-am

β is a real, transcendental number.

This is because there is a rational approximation

Screen Shot 2016-12-11 at 10.46.43 AM.png

with

screen-shot-2016-12-11-at-10-47-21-am

Analysing this inequality, the ratio

screen-shot-2016-12-11-at-10-48-30-am

is unbounded as N → +∞, and so β is well approximable by rationals.

M x