Math and theory

Contents

Math

Branches in mathematics

Recall:

Hard problems and complexity

Hard problems in cryptography

Hidden supgroup problem

The hidden subgroup problem (HSP) is a topic of research in mathematics and theoretical computer science. The framework captures problems like factoring, discrete logarithm, graph isomorphism, and the shortest vector problem. This makes it especially important in the theory of quantum computing because Shor's quantum algorithm for factoring is essentially equivalent to the hidden subgroup problem for finite Abelian groups, while the other problems correspond to finite groups that are not Abelian.

Factorisation

Discrete Logarithm Problem

In any group G, powers bk can be defined for all integers k, and the discrete logarithm logb a is an integer k such that bk = a.

Diffie-Hellman

The Diffie–Hellman problem is related to the DLP. The DH problem is stated informally as follows: Given an element g and the values of gx and gy, what is the value of gxy?

Lattices

It is e.g. the basis of the lattice-based public-key encryption scheme, NTRU.

PQ - Post Quantum

Shor and Grover

ETSI

Techniques

Formal verification

Concepts

Models of computation and proof of security

Cryptographic schemes are usually based on complexity assumptions, which state that some problems, such as factorisation, cannot be solved in polynomial time. Schemes which can be proven secure using only complexity assumptions are said to be secure in the standard model.

Security proofs are notoriously difficult to achieve in the standard model, so in many proofs, cryptographic primitives are replaced by idealized versions. The most common example of this technique, known as the random oracle model, involves replacing a cryptographic hash function with a genuinely random function.

Another example is the generic group model where the adversary is given access to a randomly chosen encoding of a group, instead of the finite field or elliptic curve groups used in practice.

Standard model

Random oracle model

Cryptographic strength

The cryptographic strength is usually measured in bits, corresponding to an upper bound for operations needed for an attack against the signature algorithm. E.g. breaking a signature algorithm means, that given the public verification key and some signatures for some data, the attacker can create a signature for another document without the signature creation data. If the attack requires 2n operations, then the cryptographic strength is denoted by n.

Other ways to describe cryptographic strength

Semantic security can be informally defined as that an adversary cannot learn anything from a ciphertext more than from random data. Semantic security and resistance to Chosen Plaintext Attack (CPA) and Chosen Ciphertext Attack (CCA) are discussed by Boneh and Shoup in their Graduate Course.

S-box

S-boxes are typically used to provide the non-linearity in symmetric encryption. There are many ways to create a substition box, including the classical Substitution-Permutation Network (SPN). Can also be based on an Addition, Rotation, XOR (ARX) network.

Sponge function

A sponge function or sponge construction is any of a class of algorithms with finite internal state that take an input bit stream of any length and produce an output bit stream of any desired length.

Cryptanalysis

Other