Prerequisites

You are currently browsing the archive for the Prerequisites category.

Download pdf here: Elliptic Curve Groups

1. Introduction and motivation

The sempiternel question of how to gain and maintain power has haunted the minds of humanity’s brightest and darkest since the dawn of civilization. Be it physical (e.g., military) or economical (e.g., wealth), power’s very existence relied in part on access to information. Asymmetric information that is. Numerous are history’s examples that demonstrate how entities that knew what others didn’t and that were able to act on it, benefited from an unfair advantage. The quest for sustainable power motivates the protection of one’s proprietary information and the attempt at breaching that of the others.

Although significant in its own right, the pursuit of power is not the only motivator to conceal information. Privacy, in so far as the individual’s well-being is concerned, is another. In that respect, two areas stand out. The first is concerned with the unique nature of a human persona. As a matter of observation, and at the risk of irritating adherents of monism, the attributes of a human personality are so varied. Each attribute exists on a wide spectrum, making it unlikely that any two individuals have the same profile so to speak. The privacy spectrum is no exception, and while some live their lives as an open book, others might not even be comfortable sharing their half title page. The second area is concerned with the safety of a certain subset of individuals, e.g., whistle-blowers. They may hold sensitive information destined to be shared with a specific party. Should this information fall in the wrong hands, it could jeopardize the safety of the source.

It is therefore reasonable to assume that not every piece of information is meant to be common knowledge. One could certainly debate the merits of such a claim and in the process, revisit the very foundation of power, privacy and safety. The fact remains however, that information can be a source of influence, discomfort, and danger. One way of protecting specific content and limiting its access to intended parties only, is through the use of encryption and decryption algorithms.

Read the rest of this entry »

Tags: , , , , , , ,

Download pdf here: Groups and Finite Fields

1. Introduction

Group, field and elliptic curve theories make a regular appearance in the study of crypto-assets including but not limited to cryptocurrencies. For example, the security strength of a number of crypto-specific primitives relies on the math of elliptic curve groups over finite fields. These groups constitute a robust infrastructure to generate adequate public keys from private ones.

Groups and fields are foundational pillars of modern algebra. While in elementary algebra we rely on common arithmetic operations (e.g., addition and multiplication of real numbers), in modern algebra we raise further the level of abstraction. In particular, we introduce more general counterparts to real number addition and multiplication and define them over more general sets. An important objective is to study the common properties of all sets on which a fixed number of operations are defined. These operations tend to be interrelated in some definite way (e.g., distributivity of multiplication over addition).

In this post, we provide a concise (but by no means comprehensive) introduction to group and finite-field theory at the level needed to better appreciate the mathematical foundation of crypto assets. In a subequent post we build on this material to introduce elliptic curve groups defined over finite fields. The interested reader could consult e.g., [1] for a deeper dive on the theory of finite fields and its applications.

Read the rest of this entry »

Tags: ,

1. Introduction

We divide this post into 6 sections. Section 2 is a qualitative description of digital signature schemes. Section 3 motivates the introduction of hash functions along with some of their desired properties. Section 4 describes a hypothetical ideal random function known as a Random Oracle. Section 5 briefly introduces the notion of Probabilistic Turing Machines that will be needed when studying the security of digital signature schemes. Sections 6 and 7 describe 2 pillars introduced by Poitncheval & Stern to prove the resilience of some digital signature schemes against a forgery attack in the Random Oracle model. In particular, Setion 6 describes a reduction model to facilitate the security analysis of signature schemes. Section 7 states and proves an important lemma known as the splitting lemma.

There is one caveat: I assume that the reader is familiar with basic probability theory, modulo arithmetic, as well as some group theoretic concepts including the notions of cyclic groups and finite fields. A concise introduction to group and field theory can be found in this post. For a more detailed treatment, the reader can refer to e.g., [3].

Read the rest of this entry »

Tags: , , , , , , , , , ,