Math theory and cryptology

Contents

Math

See also local info:

Complexity

EC based crypto

ECDSA. EdDSA.

Pairings based crypto

Intro

Refer also to math on EC and math on EC pairings.

Recall that ECC is used for key agreement, digital signatures, pseudo-random generators and other tasks. Indirectly, it can be used for encryption by combining the key agreement with a symmetric encryption scheme.

NIST: a pairing is a function that maps a pair of points on an elliptic curve into a finite field. Their unique properties have enabled many new cryptographic protocols that had not previously been feasible.

Identity-based encryption (IBE) is a pairing-based scheme that uses some form of a person (or entity’s) identification to generate a public key. An IBE scheme allows a sender to encrypt a message without needing a receiver’s public key to have been certified and distributed for subsequent use. Such a scenario is quite useful if the pre-distribution of public keys is impractical. There are other identity-based cryptosystems (including signature schemes), key establishment schemes, functional and attribute-based encryption, and privacy-enhancing techniques, such as the use of anonymous credentials based on pairings.

Local files: If the embedding degree k is small, then there is the possibility that the known subexponential-time index-calculus algorithms for solving the DLP in Fqk are faster than Pollard’s rho method for solving the ECDLP in P. This is indeed the case for all supersingular curves since k ∈ {1, 2, 3, 4, 6} for these curves. However, one can expect that k ≈ n for most elliptic curves (and this was proven to be the case for elliptic curves of prime order over prime fields, and thus for most elliptic curves the ECDLP is not vulnerable to the Weil and Tate pairing attacks.

Ben-Sasson:

PQ - Post Quantum

The main families of PQ algorithms include:

Shor and Grover

NIST

ETSI

Other

Tools

Formal verification

Concepts

Models of computation and proof of security

See also local files:

The standard model

Random oracle model

Oracle model

According to Goldreich (P, NP and NP-Completeness, Section 1.3.6), an oracle machine is a turing machine that is augmented such that it may pose questions to the outside. One can ask the oracle turing machine a question. As a result, the machine will send a query q to an oracle f, outside of the machine. The oracle responds to the query with f(q). The oracle turing machine then returns this response.

An oracle machine is a turing machine with an additional tape, called the oracle tape, and two special states, oracle invocation and oracle spoke. For details see Goldreich. One can envisage an oracle for any type of function. For example an RSA oracle is used by Bellare et al. in The One-More-RSA-Inversion Problems and the Security of Chaum's Blind Signature Scheme' . They specify Hence to invert RSA at point y means to compute x = RSA-1N,e(y). They then study the setting where both a legitimate user and an adversary have access to an RSA oracle, i.e. one can provide y to the oracle and get back SA-1N,e(y). However, the oracle does not disclose d. They then propose a security property as follows:

Random oracle model in security

Signatures without random oracles

Gennaro et al. describe such a system in 'Secure hash-and-sign signatures without the random oracle' (1999). The security is based on the Strong RSA assumption, which is specified as follows. Given an RSA modulus N and s ∈ Z*N, it is difficult to construct a non-trivial pair (c, s1/c) where c ∈ Z*N.

Boneh and Boyen describe such a system in 'Short Signatures Without Random Oracles' (2004). The security is based on an assumption they call the Strong Diffie-Hellman assumption (SDH). The SDH may be viewed as the DL analogue of the Strong RSA assumption.

Boneh and Boyen describe a variant in 'Short Signatures Without Random Oracles and the SDH Assumption in Bilinear Groups' (2014).

Semantic and non-malleable security

Goldwasser and Micali. A semantically secure cryptosystem is one where only negligible information about the plaintext can be feasibly extracted from the ciphertext. Specifically, any probabilistic, polynomial-time algorithm (PPTA) that is given the ciphertext of a certain message m (taken from any distribution of messages), and the message's length, cannot determine any partial information on the message with probability non-negligibly higher than all other PPTA's that only have access to the message length (and not the ciphertext).

This concept is the computational complexity analogue to Shannon's concept of perfect secrecy. Perfect secrecy means that the ciphertext reveals no information at all about the plaintext, whereas semantic security implies that any information revealed cannot be feasibly extracted.

Dolev. Non-malleable is an extension of semantically secure. Given the ciphertext it must be impossible to generate a different ciphertext so that the respective plaintexts are related. Semantically secure encryption algorithms include Goldwasser-Micali, ElGamal and Paillier. These schemes are considered provably secure, as their semantic security can be reduced to solving some hard mathematical problem (e.g., Decisional Diffie-Hellman or the Quadratic Residuosity Problem). Other, semantically insecure algorithms such as RSA, can be made semantically secure (under stronger assumptions) through the use of random encryption padding schemes such as Optimal Asymmetric Encryption Padding (OAEP).

Other security models

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.

Alternatively, a security factor, often referred to as k is also used. Oddly enough, it is sometimes used as 1k.

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.

Cryptanalysis

Illustrations

Specific stuff

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.