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.
- Pairing-based tutorial - Cryptimeleon Paderborn University
- Pairing-based crypto - NIST
- NIST summarised the landscape in the report 'Report on Pairing-based Cryptography' in 2012, published in the NIST Journal of Research in 2015.
- Mentions as seminal work:
- Boneh and Franklin’s identity-based encryption scheme
- Boneh, Lynn, and Schacham’s short signature scheme, and
- Joux’s one round tripartite key exchange.
- Pairing-based crypto - Wikipedia
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:
- Let G1 and G2 be two cyclic groups of order r. We denote elements of G1, G2 via calligraphic letters such as P, Q.
- We write G1 and G2 in additive notation.
- Let P1 be a generator of G1 , i.e., G1 = {αP1} with α ∈ Fr (finite field F). α is also viewed as an integer, hence αP1 is well-defined.
- Let P2 be a generator for G2.
- A pairing is an efficient map e : G1 × G2 → GT, where GT is also a cyclic group of order r (which we write in multiplicative notation), satisfying the following properties:
- bilinearity: for every nonzero elements α, β ∈ Fr , it holds that e(αP1, βP2 ) = e(P1 , P2)αβ
- non-degeneracy: e(P1, P2) is not the identity in GT
PQ - Post Quantum
The main families of PQ algorithms include:
- code-based e.g. McEliece, Rollo,
- isogeny-based e.g. SIKE,
- hash-based e.g. Merkle Hash-trees
- lattice-based e.g. NTRU, LWE, RLWE,
- multivariate-based e.g. Rainbow, LUOV.
Shor and Grover
- Shor's algorithm - a polynomial-time quantum computer algorithm for integer factorization - Wikipedia
- Grover's algorithm - a quantum algorithm that finds with high probability the unique input to a black box function that produces a particular output value - Wikipedia
NIST
- NIST PQ - Wikipedia
- NIST PQ project
- NIST PQ selected algorithms 2022
- CRYSTALS - 'Cryptographic Suite for Algebraic Lattices' - both algorithms are based on hard problems over module lattices, are designed to withstand attacks by large quantum computers
- Crystals-KyberR: an IND-CCA2-secure key-encapsulation mechanism (KEM) - Public-key Encryption and Key-establishment Algorithms
- Crystals-Dilithium, a strongly EUF-CMA-secure digital signature algorithm.
- Background: Module lattices can be thought of as lattices that lie between the ones used in the definitions of the LWE problem, and those used for the Ring-LWE problem. If the ring underlying the module has a sufficiently high degree (like 256), then these lattices inherit all the efficiency of the ones used in the Ring-LWE problem, and additionally have the following advantages, when used in our cryptographic algorithms:
- The only operations required for Kyber and Dilithium for all security levels are variants of Keccak, additions/multiplications in Zq for a fixed q, and the NTT (number theoretic transform) for the ring Zq[X]/(X256+1). This means that increasing/decreasing the security level involves virtually no re-implementation of the schemes in software or hardware. Changing a few parameters is all that one needs to convert an optimized implementation for one security level into an optimized implementation for a different one.
- The lattices used in Kyber and Dilithium have less algebraic structure than those used for Ring-LWE and are closer to the unstructured lattices used in LWE. It is therefore conceivable that if algebraic attacks against Ring-LWE appear (there are none that we are aware of at this point), then they may be less effective against schemes like Kyber and Dilithium.
- FALCON DSA - Fast Fourier Lattice-based Compact Signatures over NTRU
- Based on the theoretical framework of Gentry, Peikert and Vaikuntanathan for lattice-based signature schemes. We instantiate that framework over NTRU lattices, with a trapdoor sampler called "fast Fourier sampling". The underlying hard problem is the short integer solution problem (SIS) over NTRU lattices, for which no efficient solving algorithm is currently known in the general case, even with the help of quantum computers.
- SPHINCS+ DSA
- Stateless hash-based signature scheme, which advances the SPHINCS signature scheme
ETSI
Other
- SageMath - a computer algebra system with features covering many aspects of mathematics, including algebra, combinatorics, graph theory, numerical analysis, number theory, calculus and statistics
- Mission: Creating a viable free open source alternative to Magma, Maple, Mathematica and Matlab.
- Free open-source mathematics software building on NumPy, SciPy, matplotlib, Sympy, Maxima, GAP, FLINT, R and more.
- Access through a common, Python-based language or directly via interfaces or wrappers.
- DE - TU Darmstadt - Lindner - links to Jalgebra
- Project Everest - Microsoft, INREA, CMU
- aims to build and deploy a verified HTTPS stack
- formally verified implementation of components in HTTPS ecosystem, including TLS and
AES, SHA2 and X25519 (DH function on Curve25519)
- Everest consists of:
- F*- a verification language for effectful programs
- By default F* only verifies the input code, it does not execute it.
To execute F* code one needs to extract it to OCaml or F# and then compile it using the OCaml or F# compiler
- miTLS, reference implementation of the TLS protocol in F*
- KreMLin, a compiler from a subset of F* to C
- HACL*, a verified library of cryptographic primitives written in F*
- Vale, a domain-specific language for verified cryptographic primitives in assembly
- EverCrypt, a verified crypto provider that combines HACL* and Vale via an agile, multi-platform,
self-configuring cryptographic API
- EverParse, a library and tool to automatically generate verified parsers and serializers for binary data formats
- => When combined together, the projects above generate a mixture of C and assembly code that implements TLS 1.3, with proofs of safety, correctness, security and various forms of side-channel resistance
Concepts
Models of computation and proof of security
See also local files:
The standard model
- The Standard model - N. Smart: 'corresponds more or less to the real world' - Wikipedia
- The model of computation in which the adversary is only limited by the amount of time and computational power available.
- This is challenged by PQ computing.
- Interpretation of Wikipedia:
- Cryptographic schemes are usually based on complexity assumptions, which state that some problems cannot be solved in polynomial time.
- Schemes that 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 thereof is the random oracle model, this involves replacing a cryptographic hash function with a genuinely random function. See below.
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.
- Oracle machine - Wikipedia
- An Oracle machine can be conceived as a Turing machine connected to an oracle. The oracle, in this context, is an entity capable of solving some problem, which for example may be a decision problem or a function problem. The problem does not have to be computable; the oracle is not assumed to be a Turing machine or computer program. The oracle is simply a "black box" that is able to produce a solution for any instance of a given computational problem:
- A decision problem is represented as a set A of natural numbers (or strings). An instance of the problem is an arbitrary natural number (or string). The solution to the instance is "YES" if the number (string) is in the set, and "NO" otherwise.
- A function problem is represented by a function f from natural numbers (or strings) to natural numbers (or strings). An instance of the problem is an input x for f. The solution is the value f(x).
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
- the RSA function as RSAN,e(x) = xe mod N, with e as encryption exponent,
- the inverse RSA function as RSA-1N,e(x) = yd mod N, with d as decryption exponent.
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:
- the adversary is given some random target points y1, ..., y1,
- the adversary wins if the number of these points whose RSA-inverse it manages to compute exceeds the number calls made to the oracle (that is, it computes 'one more RSA-inverse')
Random oracle model in security
- The Random Oracle model (in cryptography) - Wikipedia
- A random oracle is an oracle (a theoretical black box) that responds to every unique query with a (truly) random response chosen uniformly from its output domain.
If a query is repeated, it responds the same way every time that a query is submitted.
- A system that is proven secure when every hash function is replaced by a random oracle is described as being secure in the random oracle model, as opposed to secure in the standard model of cryptography.
- Random Oracles are practical - M. Bellare and P. Rogaway - 1993
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
- 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.
- The TTP model, where a TTP is to to perform some task without cheating. E.g. the PKI model requires a CA which if it were dishonest, could produce fake certificates and use them to forge signatures, or mount a man in the middle attack to read encrypted messages.
- The common random string model, where it is assumed that all parties have access to some string chosen uniformly at random, and its generalization, the common reference string model, where a string is chosen according to some other probability distribution. These models are often used for non-interactive zero-knowledge proofs (NIZK). In some applications, such as the Dolev–Dwork–Naor encryption scheme,it makes sense for a particular party to generate the common reference string, while in other applications, the common reference string must be generated by a trusted third party. Collectively, these models are referred to as models with special setup assumptions.
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
- Cryptanalysis and attacks - Wikipedia
- Amount of information available to the attacker (further to Kerckhoffs' principle)
- Ciphertext-only: the cryptanalyst has access only to a collection of ciphertexts or codetexts.
- Known-plaintext: the attacker has a set of ciphertexts to which they know the corresponding plaintext.
- Chosen-plaintext (CPA): the attacker can obtain the ciphertexts corresponding to an arbitrary set of plaintexts of their own choosing.
- Adaptive chosen-plaintext: like a chosen-plaintext attack, except the attacker can choose subsequent plaintexts based on information learned from previous encryptions, similarly to the Adaptive chosen ciphertext attack.
- Related-key attack: Like a chosen-plaintext attack, except the attacker can obtain ciphertexts encrypted under two different keys. The keys are unknown, but the relationship between them is known; for example, two keys that differ in the one bit.
- Chosen-ciphertext (CCA): the attacker can obtain the plaintexts corresponding to an arbitrary set of ciphertexts of their own choosing. Boneh's IBE from the Weil Pairing refers to CCA as the standard acceptable notion of security for a public key encryption scheme.
- Computational resources required
- Time – the number of computation steps (e.g., test encryptions) which must be performed - see a href="LW0200MATHEMATICS#timecomplexity_anchor">mathematics section
- Memory – the amount of storage required to perform the attack.
- Data – the quantity and type of plaintexts and ciphertexts required for a particular approach.
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.