MATHEMATICS

Views and branches

Views

Branches of abstract algebra

High level

Overview

Associations

Universities

Mathematics Subject Classification

Notation

General

When g is a generator of a group G, < g > refers to the subgroup generated by g.

When specifying a security parameters such as k, it is customary that 1k refers to a bitstring of lenght k (and not to the exponent).

A map is often specified by an 'accent circonflexe', the 'little roof': ê.

A random selection is sometimes indicated by the use of the dollarsign, $.

Exponentiation: Affine:

Integers

The word integer comes from the Latin integer meaning "whole" or (literally) "untouched", from in ("not") plus tangere ("to touch"). The use of the letter Z to denote the set of integers comes from the German word Zahlen ("numbers") and has been attributed to David Hilbert.

The symbol Z is often annotated to denote various sets, with varying usage amongst different authors: Z+, Z+ or Z> for the positive integers.

Some authors use Z* for non-zero integers, while others use it for non-negative integers, or for {–1, 1} (the group of units of Z.

Additionally, Zp is used to denote either the set of integers modulo p (i.e., the set of congruence classes of integers), or the set of p-adic integers.

Nigel Smart

Book 'Cryptography Made Simple':

Fields and cardinality

Identification and authentication

Cryptographers often refer to the demonstration of identity as identification. The reason is the paper 'How to prove yourself: Practical solutions to identification and signature problems' by Fiat and Shamir in Andrew M. Odlyzko, editor, Advances in Cryptology - CRYPTO ’86, Santa Barbara, California, USA, 1986. Computer scientists prefer to call this authentication. In the field of biometric recognition, identification is the 1:n match for subjects that are not collaborative.

Preneel suggests to always specify whether you mean entity or data authentication.

Problem hardness and complexity

P, NP, NP-complete, NP-hard

A language L is in NP if for every word x in the language there exists a witness w which is of length polynomial in the length of x and given the witness and the word you can verify language-membership in polynomial time.

Note that you only need said witness (sometimes also called certificate) need only exist for words that actually are in the language, i.e. you don't need to be able to construct them for negative instances and constructing them is allowed to take super-polynomial time.

P for Polynomial time

NP for Non-deterministic Polynomial time

IP - Interactive Proof = PSPACE

The class IP (interactive polynomial time) is the class of problems solvable by an interactive proof system. It is equal to the class PSPACE.

The result was established in a series of papers The concept of an interactive proof system (IPS) was introduced by Shafi Goldwasser, Silvio Micali, and Charles Rackoff in 1985. An IPS consists of two machines, a prover, P, which presents a proof that a given string n is a member of some language, and a verifier, V, that checks that the presented proof is correct.

The prover is assumed to be infinite in computation and storage, while the verifier is a probabilistic polynomial-time machine with access to a random bit string whose length is polynomial on the size of n. These two machines exchange a polynomial number, p(n), of messages and once the interaction is completed, the verifier must decide whether or not n is in the language, with only a 1/3 chance of error. (So any language in Bounded-error Probabilistic Polynomial time (BPP) is in IP, since then the verifier could simply ignore the prover and make the decision on its own.)

Bounded-error probabilistic polynomial time (BPP) is the class of decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability bounded by 1/3 for all instances. BPP is one of the largest practical classes of problems, meaning most problems of interest in BPP have efficient probabilistic algorithms that can be run quickly on real modern machines. BPP also contains P, the class of problems solvable in polynomial time with a deterministic machine, since a deterministic machine is a special case of a probabilistic machine.

Computational complexity

Time complexity (i.e. running time)

To express the running time of an algorithm one can use a combination of two ideas. Suppose an algorithm, running on an input of size n takes 6n2+100n+300 machine instructions. This expression is a polynomial with n as variable (indeterminate). The 6n2 squared term becomes larger than the remaining terms, 100n+300 once n becomes large enough, 20 in this case. The running time of this algorithm is specified as n2 dropping the coefficient 6 and the remaining terms 100n+300.

The less significant terms and the constant coefficients are dropped to focus on the important part of an algorithm's running time—its rate of growth—without getting mired in details. This is called 'asymptotic notation', of which there are the following forms. The complexity class NEXPTIME (sometimes called NEXP) is the set of decision problems that can be solved by a non-deterministic Turing machine using time 2nO(1).

Circuit complexity

Lattices complexity

Learning With Errors complexity

Based on the idea of representing secret information as a set of equations with errors. LWE is a way to hide the value of a secret by introducing noise to it. It refers to the computational problem of inferring a linear n-ary function f over a finite ring from given samples yi = f(xi) some of which may be erroneous.

Famous solved problems

Proofs

Basics

Soundness and completeness

In mathematical logic, logical systems are sound if and only if every formula that can be proved in the system is logically valid with respect to the semantics of the system. The converse of soundness is known as completeness. A formal system is called complete with respect to a particular property if every formula having the property can be derived using that system, i.e. is one of its theorems; otherwise the system is said to be incomplete.

Interactive Proofs

In 'A paradoxial solution to the signature problem' Goldwasser, Micali and Rivest specify that the standard definition of interactive proofs require An interactive proof system (IPS) is an abstract machine that models computation as the exchange of messages between two parties: a prover and a verifier. The parties interact by exchanging messages in order to ascertain whether a given string belongs to a language or not.

The prover possesses unlimited computational resources but cannot be trusted, while the verifier has bounded computation power but is assumed to be always honest. Messages are sent between the verifier and prover until the verifier has an answer to the problem and has 'convinced' itself that it is correct. Classes of interactive proofs are:

Probabilistically Checkable Proofs (PCP)

The PCP theorem (also known as the PCP characterization theorem) states that every decision problem in the NP complexity class has probabilistically checkable proofs (proofs that can be checked by a randomized algorithm) of constant query complexity and logarithmic randomness complexity (uses a logarithmic number of random bits).

The PCP theorem says that for some universal constant K, for every n, any mathematical proof for a statement of length n can be rewritten as a different proof of length poly(n) that is formally verifiable with 99% accuracy by a randomized algorithm that inspects only K letters of that proof.

Used a.o. in SNARKS.

Arithmetic

Counting, log, exp, ...

Arithmetic is the study of the properties of the traditional operations on numbers—addition, subtraction, multiplication, division, exponentiation, and extraction of roots. In the 19th century, Italian mathematician Giuseppe Peano formalized arithmetic with his Peano axioms, which are important to the field of mathematical logic today.

Logarithm and exponentiation

Logarithm is the inverse function to exponentiation. The logarithm of a number x to the base b is the exponent to which b must be raised, to produce x.

For example, since 1000 = 10**3, the logarithm base 10 of 1000 is 3, or log10 (1000) = 3.

The logarithm of x to base b is denoted as logb(x), or without the explicit base, log x, when no confusion is possible, or when the base does not matter such as in big O notation.

The logarithm base 10 is called the decimal or common logarithm and is commonly used in science and engineering. The natural logarithm has the number e ≈ 2.718 as its base; its use is widespread in mathematics and physics, because of its very simple derivative. The binary logarithm uses base 2 and is frequently used in computer science.

Logarithms were introduced by John Napier in 1614 as a means of simplifying calculations. They were rapidly adopted by navigators, scientists, engineers, surveyors and others to perform high-accuracy computations more easily. Using logarithm tables, tedious multi-digit multiplication steps can be replaced by table look-ups and simpler addition. This is possible because the logarithm of a product is the sum of the logarithms of the factors:

Modular arithmethic

The integers modulo a prime are a finite field.

Basics

p-adic numbers

Calculus

Basics

Calculus is the study of continuous change, in the same way that geometry is the study of shape, and algebra is the study of generalizations of arithmetic operations. Differentiation has applications in nearly all quantitative disciplines. In physics, See Integration

Process calculus

Linear algebra

Basics

Linear algebra concerns and their representations in vector spaces and through matrices.

Linear equations

And solving them, see

Vectors and vector spaces

A vector space (also called a linear space) is a set whose elements (vectors), may be added together and multiplied by numbers called scalars. Scalars are often real numbers, but can be complex numbers or, more generally, elements of any field.

The operations of vector addition and scalar multiplication must satisfy certain requirements, called vector axioms. The terms real vector space and complex vector space are often used to specify the nature of the scalars: real coordinate space or complex coordinate space.

Vector basics

A vector is a term that refers colloquially to some quantities that cannot be expressed by a single number (a scalar), or to elements of some vector spaces.

Historically, vectors were introduced in geometry and physics (typically in mechanics) for quantities that have both a magnitude and a direction, such as displacements, forces and velocity. Such quantities are represented by geometric vectors in the same way as distances, masses and time are represented by real numbers.

The term vector is also used, in some contexts, for tuples, which are finite sequences of numbers of a fixed length.

Vector spaces basics

A vector space (also called a linear space) is a set whose elements, often called vectors, may be added together and multiplied ("scaled") by numbers called scalars.

Both geometric vectors and tuples can be added and scaled, and these vector operations led to the concept of a vector space, which is a set equipped with a vector addition and a scalar multiplication that satisfy some axioms generalizing the main properties of operations on the above sorts of vectors. Many vector spaces are considered in mathematics, such as extension field, polynomial rings, algebras and function spaces. The term vector is generally not used for elements of these vectors spaces, and is generally reserved for geometric vectors, tuples, and elements of unspecified vector spaces (for example, when discussing general properties of vector spaces).

Dot product

The dot product or scalar product is an algebraic operation that takes two equal-length sequences of numbers (usually coordinate vectors), and returns a single number.

Dot product illustration

The dot product of two vectors a = [a1 , a2 , ⋯ , an] and b = [b1 , b2, ⋯ , bn] specified with respect to an orthonormal basis, is defined as: a.b = a1b1 + a2b2 + ⋯ + anbn

For instance, in three-dimensional space, the dot product of vectors [ 1, 3, −5] and [ 4, −2, −1] is: [ 1, 3, −5] ⋅ [ 4, − 2, −1] = (1 × 4) + (3 × −2) + (−5 × −1) = 4−6+5 = 3

Linear maps

A prototypical example that gives linear maps their name is a function f : R → R : x ↦ cx of which the graph is a line through the origin

Bilinear forms

The Weil pairing is a pairing (bilinear form, though with multiplicative notation) on the points of order dividing n of an elliptic curve E, taking values in nth roots of unity. The dot product (scalar product) on Rn is an example of a bilinear form.

Bilinear map

A bilinear map is a function combining elements of two vector spaces to yield an element of a third vector space, and is linear in each of its arguments. Matrix multiplication is an example.

Abstract algebra

Algebra is the study of variables and the rules for manipulating these variables in formulas; it is a unifying thread of almost all of mathematics. Many areas of mathematics belong to algebra, some having "algebra" in their name, such as commutative algebra, and some not, such as Galois theory.

Algebra began with computations similar to those of arithmetic, with letters standing for numbers. This allowed proofs of properties that are true no matter which numbers are involved. For example, in the quadratic equation ax^{2}+bx+c=0, where a, b, c can be any numbers whatsoever (except that a cannot be 0 and the quadratic formula can be used to quickly and easily find the values of the unknown quantity x which satisfy the equation. That is to say, to find all the solutions of the equation.

Polynomials

A polynomial is an expression of the form a0+a1x+...+anxn. The ai are called coefficients (typically real or complex numbers). The x is a variable, substituting an arbitrary number for it a well defined number is obtained.

Lagrange interpolation

The Lagrange interpolating polynomial is the unique polynomial of lowest degree that interpolates a given set of data.

Lagrange normal basis

Lagrange theorem on how frequently a polynomial over the integers evaluates to a multiple of a fixed prime

  • Lagrange theorem - Wikipedia

    • Polynomials over rings and fields

    A polynomial of ring R is a polynomial where the coefficients are element of R, and x is a symbol not belonging to R, called the indeterminate over R.

    Addition and product for polynomials over R is defined, and the set of polynomials over R forms a ring, called the polynomial ring over R, R[x]. The highest exponent of n is called the degree of the polynomial.

    The prime elements of the ring F[x] are called irreducible polynomials. Polynomials of postive degree can be uniquely factorised. An element of a field F is called a root of the polynomial if its value is zero.

    Sets and cosets

    Magmas

    Basics

    A magma, binar, or groupoid consists of a set equipped with a single binary operation that must be closed by definition. No other properties are imposed.

    Groups

    Basics

    Relevant for cryptography (Ben Lynn's thesis): Using representation theory group elements can be represented as linear transformations of vector spaces.

    Features of a single group

    Features of sets of groups

    Bilinear groups (i.e. groups where bilinear maps, or pairings, can be found)

    From Groth16: 'We will work over bilinear groups (p, G1, G2 , GT, e, g, h) with the following properties: More:

    Isogeny groups (i.e. a morphism that is surjective and has a finite kernel)

    An isogeny is a morphism of algebraic groups (also known as group varieties) that is surjective and has a finite kernel.

    If the groups are abelian varieties, then any morphism f : A → B of the underlying algebraic varieties which is surjective with finite fibres is automatically an isogeny, provided that f(1A) = 1B. Such an isogeny f then provides a group homomorphism between the groups of k-valued points of A and B, for any field k over which f is defined.

    The terms "isogeny" and "isogenous" come from the Greek word ισογενη-ς, meaning "equal in kind or nature". The term "isogeny" was introduced by Weil; before this, the term "isomorphism" was somewhat confusingly used for what is now called an isogeny.

    Rings

    Basics

    Examples

    The four common rings:

    Characteristics of a ring

    The characteristic of a ring R is defined to be the smallest number of times one must use the ring's multiplicative identity (1) in a sum to get the additive identity (0). If this sum never reaches the additive identity the ring is said to have characteristic zero.

    Ideal of a ring (subset of its elements)

    An ideal of a ring R is a special subset of its elements. Ideals generalise certain subsets of the integers, such as the even numbers or the multiples of 3. Addition and subtraction of even numbers preserves evenness, and multiplying an even number by any integer (even or odd) results in an even number; these closure and absorption properties are the defining properties of an ideal. An ideal can be used to construct a quotient ring in a way similar to how, in group theory, a normal subgroup can be used to construct a quotient group. Illustrations:

    Principal ideal of a ring (subset of its elements)

    In ring theory, a principal ideal is an ideal I in a ring R that is generated by a single element a of R through multiplication by every element of R . Note: the term also has another, similar meaning in order theory.

    Divisability of a ring, divisors, left and right divisors

    The notion of a divisor arose within the arithmetic of whole numbers. With the development of abstract rings, of which the integers are the archetype, the original notion of divisor found a natural extension.

    Divisibility is a useful concept for the analysis of the structure of commutative rings because of its relationship with the ideal structure of such rings.

    Let R be a ring, and let a and b be elements of R. When R is commutative, the notions of left divisor, right divisor, and two-sided divisor coincide, so one says simply that a is a divisor of b, or that b is a multiple of a, and one writes a ∣ b.

    Zero divisors (in a ring or a semi-group with zero element)

    A zero divisor is a non-zero element such that the product with some non-zero element is zero (weird name choice). An element a is called a left (right) divisor of zero if ab=0 (ba=0) for at least one b≠0.

    The only zero divisor of the ring Z of integers is 0.

    Polynomial rings

    A polynomial ring is a ring formed from the set of polynomials in one or more indeterminates (also called variables) with coefficients in another ring, often a field.

    Often, the term "polynomial ring" refers implicitly to the special case of a polynomial ring in one indeterminate over a field. The importance of such polynomial rings relies on the high number of properties that they have in common with the ring of the integers.

    The polynomial ring, K[X], in X over a field (or, more generally, a commutative ring) K can be defined in several equivalent ways. One of them is to define K[X] as the set of expressions, called polynomials in X.

    Univariate polynomial rings - single variable (indeterminate)

    The polynomial ring, K[X], in X over a commutative ring (or over a field) K can be defined as the set of expressions, called polynomials in X, of the form p = p0 + p1 X + p2 X2 + ⋯ + pm-1Xm−1 + pmXm, where p0, p1, p2, the coefficients of p, are elements of K, pm ≠ 0 if m > 0, and X, X2, …, are symbols, which are considered as "powers" of X, and follow the usual rules of exponentiation for any nonnegative integers k and l. The symbol X is called an indeterminate or variable.

    Fields

    Basics

    It can be observed that while composites of the form m.n do not lead to fields, e.g. Z(15) is not a field. But numbers such as pk (which could potentially also be called composites of the form p.p) do lead to fields. F(p^k) is a field.

    Definition:

    Notation

    N. Smart's book 'Cryptography Made Simple':

    Selective fields

    Creation of finite fields

    Lidl and Niederreiter describe three ways to represent elements of finite fields: Also: see https://www.doc.ic.ac.uk/~mrh/330tutor/ch04s02.html

    One way to construct a finite field Fpk with k >1 is using the polynomial basis. The field is constructed as a set of pk polynomials along with two polynomial operations.

    Polynomials are specified as f(x) = p = p0 + p1 x + p2 x2 + ⋯ + p m-1 xm−1 + pmxm,

    The highest exponent of x is the degree of the polynomial.

    In a polynomial, p0, p1, ... are called coefficients. If the coefficients are taken from a field F, then we say it is a polynomial over F.

    Polynomials over field GF(p)

    With polynomials over field GF(p), you can add and multiply polynomials just like you have always done but the coefficients need to be reduced modulo p.

    We can add, subtract polynomials by combining the terms in the polynomials with the same powers. We can multiply and divide (in which case there might be a remainder).

    If a polynomial is divisible only by itself and constants, then we call this polynomial irreducible. Irreducible polynomials have properties similar to prime numbers.

    Similar to integers, you can do modular arithmetic with polynomials over a field. Now the operands and modulus are polynomials. Always remember there are two moduli involved: a polynomial modulus and an integer modulus. You need to reduce the result from the polynomial operations by modulo the polynomial modulus and then reduce the coefficients modulo the integer modulus.

    Let f(x) and g(x) be two polynomials over a field F, of degrees n and m respectively, then there is a unique polynomial r(x) of degree smaller than m and another unique polynomial h(x), both over F, such that f(x) = h(x)*g(x)+r(x). The polynomial r(x) is called the remainder of f(x) modulo g(x). For polynomials a(x), b(x) and g(x) which are over the same field, we say a(x) is congruent to b(x) modulo g(x) written a(x) ≡ b(x) mod g(x), if m(x) divides a(x)-b(x).

    Polynomials over field GF(pm)

    If the modulus g(x) is an irreducible polynomial of degree m over GF(p), then the finite field GF(pm) can be constructed by the set of polynomials over GF(p) whose degree is at most m-1, where addition and multiplication are done modulo g(x).

    For example, the finite field GF(32) can be constructed as the set of polynomials whose degrees are at most 1, with addition and multiplication done modulo the irreducible polynomial x2+1 (you can also choose another modulus, as long as it is irreducible and has degree 2).

    Polynomials over field GF(2m)

    Finite fields of order 2m are called binary fields or characteristic-two finite fields. They are of special interest because they are particularly efficient for implementation in hardware, or on a binary computer. The elements of GF(2m) are binary polynomials, i.e. polynomials whose coefficients are either 0 or 1.

    Order of a field (number of its elements)

    The order (or size) of a finite field is its number of elements. The order of a finite field is always a prime or a power of a prime (Why? Birkhoff and Mac Lane 1996).

    Fields of prime order, Fp

    If the field is called Fq but q is simply a prime, then any field with q elements is isomorphic to the integers mod q. Addition and multiplication are defined just as in the integers, except you always take the remainder by q after you add or multiply.

    Fields of prime power order, Fpk = Fq

    See https://www.johndcook.com/blog/2022/09/21/field-of-order-9/ Multiplication in a field of 9 elements (9 = 32)is not simply multiplication mod 9. You need an irreducible polynome as well.

    Arithmetic in prime power fields: In a finite field of order q, the polynomial Xq − X has all q elements of the finite field as roots. The non-zero elements of a finite field form a multiplicative group. This group is cyclic, so all non-zero elements can be expressed as powers of a single element called a primitive element of the field. (In general there will be several primitive elements for a given field.)

    When and why to use prime fields versus prime power fields seems to be an implementation issue.

    Characteristic of a field (number of time the multiplicative identity must be added to the the additive identity)

    The expression 'characteristics' carries over from the rings. Recall that the characteristic of a ring R is defined to be the smallest number of times one must use the ring's multiplicative identity (1) in a sum to get the additive identity (0).

    The characteristic of any field is either 0 or a prime number. A field of non-zero characteristic is called a field of finite, positive or prime characteristic. The characteristic of any field with positive characteristic must be prime. Sidebar: roots of a finite field ...

    Fields of prime characteristic

    The finite field GF(p n) has characteristic p.

    There exist infinite fields of prime characteristic. For example, the field of all rational functions over Z/pZ, the algebraic closure of Z/pZ or the field of formal Laurent series Z/pZ.

    The size of any finite ring of prime characteristic p is a power of p. Since in that case it contains Z/pZ it is also a vector space over that field, and from linear algebra we know that the sizes of finite vector spaces over finite fields are a power of the size of the field. This also shows that the size of any finite vector space is a prime power.

    Normal basis of a field

    A normal basis is a special kind of basis for Galois extensions of finite degree, characterised as forming a single orbit for the Galois group. The normal basis theorem states that any finite Galois extension of fields has a normal basis. In algebraic number theory, the study of the more refined question of the existence of a normal integral basis is part of Galois module theory. See https://en.wikipedia.org/wiki/Normal_basis

    Fields and polynomials

    Extension fields and subfields

    A field extension is a pair of fields K ⊆ L such that the operations of K are those of L restricted to K. In this case, L is an extension field of K and K is a subfield of L. For example, under the usual notions of addition and multiplication See

    Splitting fields

    The splitting field of a polynomial is the smallest field containing all roots of that polynomial. Otherwise said, a splitting field of a polynomial with coefficients in a field is the smallest field extension of that field over which the polynomial splits, i.e., decomposes into linear factors.

    Any finite field GF(q), where q=pn, is the splitting field of the polynomial xq−x over the prime subfield GF(p) ⊂ GF(q).

    Cyclotomic fields

    A cyclotomic field is a number field obtained by adjoining a complex root of unity to Q, the field of rational numbers.

    Cyclotomic fields played a crucial role in the development of modern algebra and number theory because of their relation with Fermat's Last Theorem. It was in the process of his investigations of the arithmetic of these fields (for prime n) – and more precisely, because of the failure of unique factorization in their rings of integers – that Ernst Kummer first introduced the concept of an ideal number and proved his celebrated congruences.

    Fields of p-adic numbers

    P-adic numbers

    The p-adic number system for any prime number p extends the ordinary arithmetic of the rational numbers in a different way from the extension of the rational number system to the real and complex number systems. The extension is achieved by an alternative interpretation of the concept of "closeness" or absolute value.

    In particular, two p-adic numbers are considered to be close when their difference is divisible by a high power of p: the higher the power, the closer they are.

    This property enables p-adic numbers to encode congruence information in a way that turns out to have powerful applications in number theory – including, for example, in the famous proof of Fermat's Last Theorem by Andrew Wiles. The p-adic integers are the p-adic numbers with a nonnegative valuation. A p-adic integer can be represented as a sequence x = ( x1 mod ⁡p, x2 mod p2, x3 mod ⁡ p3 , … ) of residues xe mod pe for each integer e, satisfying the compatibility relations xj ≡ xj (mod ⁡pi ) for i < j.

    Every integer is a p-adic integer (including zero, since 0 < ∞. The rational numbers of the form n/d pk with d coprime with p and k ≥ 0 are also p-adic integers (because d has an inverse mod pe for every e).

    P-adic numbers ring and field

    The p-adic integers form a commutative ring, denoted Zp (difference in notation with regular Zp?) that has the following properties. The last property provides a definition of the p-adic numbers that is equivalent to the above one: the field of the p-adic numbers is the field of fractions of the completion of the localization of the integers at the prime ideal generated by p.

    Applications of finite fields

    Popular fields in cryptography: Definition of a finite field of characteristic 2:

    The difficulty of the discrete logarithm problem in finite fields or in elliptic curves is the basis of several widely used protocols, such as the Diffie–Hellman protocol.

    Finite fields are used by many error correction codes, such as Reed–Solomon error correction code or BCH code. The finite field almost always has characteristic of 2, since computer data is stored in binary. For example, a byte of data can be interpreted as an element of GF(28).

    Roots

    Roots

    Quadratic residues, Legendre and Jacobi symbols

    QR

    For an introduction refer to the HAC Section 3.4. There is a significant difference finding QRs modulo a prime (randomised algorithm exists) versus a composite (if the factors are unknown, this is the Quadratic Residuity Problem). Finding a square root of a number modulo a large composite n is equivalent to factoring (which is widely believed to be a hard problem), hence has been used for constructing cryptographic schemes such as the Rabin cryptosystem and the oblivious transfer.

    The quadratic residuosity problem is the basis for the Goldwasser-Micali cryptosystem.

    Legendre - prime p and integer a

    Jacobi - [composite] integer n and integer a

    Elliptic curve

    See Lynn's Ph.D. thesis.

    Basics

    An elliptic curve is a smooth, projective, algebraic curve of genus one (one 'hole), on which there is a specified point O.

    An elliptic curve is defined over a field K and describes points in K x K, the Cartesian product of K with itself. If the field's characteristic is different from 2 and 3, then the curve can be described as a plane algebraic curve which consists of solutions (x, y) for y2 = x3 + a x + b for some coefficients a and b in K. Introductions:

    EC's embedding degree

    See 'Constructing Elliptic Curves with Prescribed Embedding Degrees' - Barreto, Lynn, Scott.

    Pairing-based cryptosystems depend on the existence of groups where the Decision Diffie-Hellman problem is easy to solve, but the Computational Diffie-Hellman problem is hard. Such is the case of elliptic curve groups whose embedding degree is large enough to maintain a good security level, but small enough for arithmetic operations to be feasible. However, the embedding degree for most elliptic curves is enormous, and the few previously known suitable elliptic curves have embedding degree k less or equal to 6.

    A subgroup G of (the group of points of) an elliptic curve E(Fq ) is said to have embedding degree or security multiplier k if the subgroup order r divides qk − 1, but does not divide qi − 1 for all 0 < i < k. The Tate pairing [3,9,11] (or the Weil pairing [15,18,25]) maps the discrete logarithm in G to the discrete logarithm in Fqk , and this is the basis for the Frey-Ruck attack [10]. An important open problem in pairing-based cryptography [5,6,12,14,22,23,27,29] is to build curves containing a subgroup with embedding degree k that is at once big enough to prevent the Frey-Ruck attack, but small enough that the Tate pairing is efficiently computable, which in turn means that arithmetic in Fqk is feasible. The embedding degree is known to be usually enormous [2,19], and for a long time, the only elliptic curves known to admit subgroups with reasonable k were supersingular curves, particularly over F3m where k = 6 [18]. Such curves are constructed over fields of low characteristic, making them more susceptible to discrete logarithm algorithms [24].

    Weierstrass equation

    This is a traditional way to specify an EC as y2= x3+ ax + b, in which form the curve always contains exactly one point at infinity.

    While this is commonly referred to as the Weierstrass equation, it is a simplification of the full form, which is specified as follows.

    Source: https://www.lmfdb.org/knowledge/show/ec.weierstrass_coeffs

    A Weierstrass equation or Weierstrass model over a field k is a plane curve E of the form y2 + a1 x y + a3 y = x3 + a2 x2 + a4 x + a6, with a1, a2, a3, a4, a5, a6 in k. The Weierstrass coefficients of this model E are the five coefficients ai. These are often displayed as a list [a_1, a_2, a_3, a_4, a_6]. It is common not to distinguish between the affine curve defined by a Weierstrass equation and its projective closure, which contains exactly one additional point at infinity, [0:1:0]. A Weierstrass model is smooth if and only if its discriminant is nonzero. In this case, the plane curve E together with the point at infinity as base point, define an elliptic curve defined over k.

    Singularity

    Curves can be singular, non-singular (cryptocurves), supersingular. Given the equation y2 = x3 + a x + b , the discriminant of the cubic in x is 4a3 + 27b2. Background:

    Hyperelliptic

    Lynn: no implementations of PBC on hyperelliptic curves.

    Embedding degree

    Embedding degree k is ...

    Well-known theorems

    Hasse, on the number of points on an EC (called the trace of Frobenius). t = qk + 1 - #E (Fqk).

    Weil.

    Ways of specifying ECs

    There are many ways of specifying an EC. Then there's the question whether a curve is suitable for cryptography. Useful curves include:

    EC pairings

    Refer also to pairing-based crypto.

    See 'On the Selection of Pairing-Friendly Groups', Barreto, Lynn & Scott at https://link.springer.com/chapter/10.1007/978-3-540-24654-1_2 .

    NIST: a pairing is a function that maps a pair of points on an elliptic curve into a finite field.

    It does not work like first choose the groups and then find a bilinear map, but the other way round. All you can do is choose groups and function and then check IF your construction fulfills the definitions of pairings. Some basic properties have to "fit" (e.g. the orders of the groups need to be compatible).

    Being able to create pairings on just any groups of your liking, would be a major algebraic breakthrough.

    Weil pairing

    Specification

    Kaliska's Ph.D. thesis (Appendix 1) contains a clear description of the Weil pairing. Also Lynn's Ph.D. thesis.

    Calculation

    In 1985 Miller found the MACSYMA algorithm for the calculation of the Weil pairing (described in Section 4.1), and wrote it up as a note which has never been published, though widely distributed and cited. Burt Kaliski devotes a chapter to this algorithm in his Ph.D. thesis - Appendix 1, B and was the first to implement it.

    Using the Weil pairing to reduce the DLP to subexponential

    Was used by Menezes, Okamoto and Vanstone ('MOV', A. J. Menezes, T. Okamoto and S. A. Vanstone, Reducing elliptic curve logarithms to logarithms in a finite field, IEEE Trans. Inf. Theory, 39, No. 5 (1993) 1639{1646) to attack the ECDLP on certain elliptic curves.

    Their method reduces the EC logarithm problem in a curve E over a finite field Fq to the discrete logarithm problem in a suitable extension field Fgk of Fg. This is achieved by establishing an isomorphism between <P>, the subgroup of E generated by P, and the subgroup of nth roots of unity in Fqk, where n denotes the order of P. The isomorphism is given by the Weil pairing.

    Since the index-calculus methods for computing logarithms in a finite field have running times that are subexponential, the reduction is useful for the purpose of computing elliptic curve logarithms provided that k is small.

    Tate pairing

    Specification

    Was introduced to cryptography by Frey and Rueck (G. Frey and H.-G. Rueck, A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves, Math. Comp., 62, No.206 (1994) 865{874}) in their extension of the work of Menezes, Okamoto and Vanstone.

    Other pairings

    TBD

    Isogenous EC

    See https://gkorpal.github.io/quantum/isogeny. Isogeny-based cryptography is a kind of elliptic-curve cryptography, whose security relies on (various incarnations of) the problem of finding an explicit isogeny between two given isogenous supersingular elliptic curves over a finite field Fq.

    However, given an elliptic curve E in Weierstrass form over a finite field Fq and a point P on E of order n, one can compute a cyclic separable isogeny of degree n using Velu’s formulas in SageMath (implemented by D. Shumow in 2009).

    Currently, quantum computers do not seem to make the isogeny-finding problem substantially easier. This contrasts with the standard discrete-logarithm based elliptic-curve cryptography which is not quantum-safe due to polynomial-time quantum algorithm by P. W. Shor from 1997.

    See https://www.mariascrs.com/posts.html. SIDH, SIKE (NIST PQ).

    Representation theory

    Studies abstract algebraic structures by representing their elements as linear transformations of vector spaces, and studies modules over these abstract algebraic structures. A representation makes an abstract algebraic object more concrete by describing its elements by matrices and their algebraic operations (for example, matrix addition, matrix multiplication). The theory of matrices and linear operators is well-understood, so representations of more abstract objects in terms of familiar linear algebra objects helps glean properties and sometimes simplify calculations on more abstract theories.

    The algebraic objects amenable to such a description include groups, associative algebras and Lie algebras. The most prominent of these (and historically the first) is the representation theory of groups, in which elements of a group are represented by invertible matrices such that the group operation is matrix multiplication. https://en.wikipedia.org/wiki/Representation_theory

    Logic

    Reasoning

    Intro and overview

    Set theory and Z

    Intro

    The formal specification notation Z is based on Zermelo-Fraenkel set theory and first order predicate logic. It has been developed by the Programming Research Group at the Oxford University Computing Laboratory and elsewhere since the late 1970s, inspired by Jean-Raymond Abrial's seminal work. Z is now defined by the ISO/IEC 13568 standard and is public domain.

    Z tools

    Tools

    Overview

    Alloy

    Alloy = logic + language + analysis, where Focused on software engineering

    Proof assistants

    Isabelle (Cambridge/Muenchen)

    Coq (INRIA)

    Coq is a formal proof management system. It provides a formal language to write mathematical definitions, executable algorithms and theorems together with an environment for semi-interactive development of machine-checked proofs. Typical applications include the certification of properties of programming languages (e.g. the CompCert compiler certification project, the Verified Software Toolchain for verification of C programs, or the Iris framework for concurrent separation logic), the formalization of mathematics (e.g. the full formalization of the Feit-Thompson theorem, or homotopy type theory), and teaching.

    Finite State Machines

    Proposition logic, SAT, SMT

    In mathematical logic, satisfiability and validity are elementary concepts of semantics.

    SAT

    SAT refers to the propositional (or boolean) satisfiability problem.

    SMT

    Satisfiability Modulo Theories (SMT) is an area of automated deduction that studies methods for checking the satisfiability of first-order formulas with respect to some logical theory T of interest. It differs from general automated deduction in that the background theory T need not be finitely or even first-order axiomatizable, and specialized inference methods are used for each theory.

    FOL and predicate logic

    Basics

    Prolog

    KIF

    Subjective logic

    Deontic logic

    Other

    Number theory

    Primes

    Graphs

    Intro

    Graph in ZK

    Transformations

    DSP - FFT - wavelets - compression

    Matrices

    Information and computation

    Tools

    NIST

    Python/SageMath

    Refer to LTK-SageMath.

    Regex

    sed

    Mathworld - Matworks - Matlab

    Other

    Humour

    When a statistician passes the airport security check, they discover a bomb in his bag. He explains. "Statistics shows that the probability of a bomb being on an airplane is 1/1000. However, the chance that there are two bombs at one plane is 1/1000000. So, I am much safer..."

    The same statistician later drowned in a river with an average depth of 30 cm.