- Hard problems and complexity
- Hidden subgroup problem
- Hidden Field Equations problem
- Factorisation
- Discrete Logarithm
- Discrete Logarithm applied to signatures
- Discrete Logarithm in EC groups
- Discrete Logarithm equivalence proofs
- Diffie-Hellman
- Decisional DH
- Computational DH
- Static DH
- Bilenair DH
- Hash DH
- External and Gap DH
- q-Strong DH
- General DH
- Decision Linear assumption (DLIN)
- Knowledge (extractability) assumptions
- Lattices
- LWE

- Local MATH - hardness
- Computational complexity theory - Wikipedia

- HSP - Wikipedia

- a public key cryptosystem, introduced at Eurocrypt 1996 and proposed by (in French) Jacques Patarin following the idea of the Matsumoto and Imai system, and
- digital signature schemes, e.g. Quartz and Sflash.

- HFE - Wikipedia

- NFS, role of Legendre and Jacobi
- New approaches from PQ such as Shor

- Miller-Rabin probabilistic primality test
- Is of historical significance in the search for a polynomial-time deterministic primality test. Its probabilistic variant remains widely used in practice, as one of the simplest and fastest tests known.
- Miller discovered the test in 1976. His version of the test is deterministic, but its correctness relies on the unproven extended Riemann hypothesis.
- Michael O. Rabin modified it to obtain an unconditional probabilistic algorithm in 1980.

- HFE - introducing the strong RSA assumption

- Strong RSA assumption - Wikipedia

- Discrete logarithm - Wikipedia

- ElGamal (1985)
- DSA (1991)
- Schnorr
- Nyberg-Rueppel (allowing message recovery)

**Decisional**Diffie-Hellman Problem: given g, g^{x}, g^{y}, g^{z}, determine if xy = z.- Decisional DH - Wikipedia
- The DDH assumption states that, given g
^{a}and g^{b}for uniformly and independently chosen a, b in Zq, the value g^{ab}"looks like" a random element in G.

- The DDH assumption is related to the discrete log assumption. If it were possible to efficiently compute discrete logs in G, then the DDH assumption would not hold in G.
- When using a protocol whose security depends on the DDH assumption, it is important that the protocol is implemented using groups where DDH is believed to hold. DDH does not hold e.g. in the multiplicative group Z
_{p}^{∗}where p is prime, nor in elliptic curves over GF(p) with small embedding degree.

**Computational**Diffie-Hellman Problem. Given g, g^{x}, g^{y}, compute g^{xy}.- Computational DH - Wikipedia
- The CDH assumption states that, given g
^{a}and g^{b}for a randomly chosen generator g and random a, b in { 0 , … , q − 1 } it is computationally intractable to compute the value g^{xy}.

**Static**Diffie-Hellman problem (SDHP) is the special case of the classic Diffie-Hellman problem where one of the public keys is fixed. See https://eprint.iacr.org/2004/306 where it is established that the SDHP is almost as hard as the associated discrete logarithm problem.

- Decision Linear Assumption (DLIN) - Wikipedia - related to bilinear DH

- Hash DH - Wikipedia - HDH

- External and gap DH - Wikipedia
- The external Diffie–Hellman (XDH) assumption is used in ECC.
- XDH implies the existence of two distinct groups ⟨G1, G2⟩ with the following properties:
- The discrete logarithm problem (DLP), the computational Diffie–Hellman problem (CDH), and the computational co-Diffie–Hellman problem are all intractable in G1 and G2.
- There exists an efficiently computable bilinear map (pairing) e ( ⋅ , ⋅ ) : G1 × G2 → GT
- The decisional Diffie–Hellman problem (DDH) is intractable in G1.
- In certain EC subgroups, the existence of an efficiently-computable bilinear map (pairing) can allow for practical solutions to the DDH problem. These groups, referred to as
**gap Diffie–Hellman**(GDH) groups, facilitate a variety of cryptographic protocols, including tri-partite key exchange, identity based encryption, and secret handshakes. - BLS - Boneh–Lynn–Shacham - Wikipedia
*'Short signatures from the Weil pairing'*- uses gap DH - Works in a 'gap group', a group in which CDH problem is intractable but DDH problem can be efficiently solved. Non-degenerate, efficiently computable, bilinear pairings permit such groups.
- Let e : G × G → G
_{T}be a non-degenerate, efficiently computable, bilinear pairing where G, G_{T}are groups of prime order, r. Let g be a generator of G. - Consider an instance of the CDH problem, g, g
^{x}, g^{y}. Intuitively, the pairing function e does not help us compute g^{xy}, the solution to the CDH problem. It is conjectured that this instance of the CDH problem is intractable. **Given g**^{z}, we may check if g^{z}= g^{xy}without knowledge of x, y, and z, by testing whether e(g^{x}, g^{y}) = e(g, g^{z}) holds.- By using the bilinear property x+y+z times, we see that if e(g
^{x}, g^{y}) = e(g, g)^{xy}= e (g, g)^{z}= e(g , g^{z}), then, since G_{T}is a prime order group, xy = z. - The signature scheme is provably secure (the scheme is existentially unforgeable under adaptive chosen-message attacks) assuming both the existence of random oracles and the intractability of the computational Diffie–Hellman problem in a gap Diffie–Hellman group.
- Boneh and Franklin describe a generic method for converting any Identity-Based Encryption scheme into a signature scheme in
*'Identity-based encryption from the Weil pairing.*SIAM J. Comput., 32(3):586–615, 2003.'

- Boneh-Boyen
*Short Signatures Without Random Oracles*- IACR 2004 - Tanaka on q-Strong DH 2010
- Boneh-Boyen
*Short Signatures Without Random Oracles and the SDH Assumption in Bilinear Groups*- Stanford 2014

- Lattice - Wikipedia
- Lattice problems
*Shortest Vector Problem (SVP), gapSVP, Closest Vector Problem (CVP), ...*- Wikipedia - Lattice-based_cryptography - Wikipedia

- Lattice - Wikipedia
- Lattice problems
*Shortest Vector Problem (SVP), gapSVP, Closest Vector Problem (CVP), ...*- Wikipedia - Lattice-based_cryptography - Wikipedia

- LWE - Wikipedia