Cryptographic Hardness Assumptions

Also Known As...

• hardness problems
• computational hardness assumption
• 1 Way Function
• Trapdoor Function

• a certain problem $P$ that is hard to efficiently (in $O(Poly)$) compute, but easy to verify given a precomputed solution
• a mathematical operation which is computationally easy to compute, but hard to reverse

Strength of Hardness Assumptions

• if A is stronger than B, then A implies B (the converse is false or not known)
• i.e. if A is found to be false, B can still be true

Use Weakest Possible Assumption for Cryptography

• when designing a cryptographic protocol, one wants to use the weakest possible assumptions

Discrete Log Problem (DLP)

Not Post Quantum Safe

DLP is considered to be non-Post Quantum Safe

undefined`

(Computational) Diffie-Hellman Assumption (CDH)

• stronger than DLP
• given group elements $g,g^a,g^b$, it is hard to find $g^{ab}$
  • $g$ is a generator, $a$ and $b$ are random integers
• used in Diffie-Hellman Key Exchange

Decisional Diffie-Hellman Assumption (DDH)

• stronger than CDH
  • if computing $g^{ab}$ from $g,g^a,g^b$ was easy, then one could solve DDH problem trivially
• used in ElGamal Encryption (Cryptosystem)

Elliptic Curve Discrete Logarithm Problem (ECDLP)

• used in Elliptic Curve Diffie-Hellman Key Exchange (ECDH)
• relies on the hardness of finding the scalar multiple $k$, where $Q=kP$ and both $Q$ and $P$ are points on the elliptic curve defined over a finite field $P$

Pairing Based / Decisional Diffie-Helman (DDH) Assumption

• assumption in a cyclic group $G$ with generator $g$ states that, given $g^a$ and $g^b$ for $a,b$ chosen uniformly and independently from $|G|$ , the value $g^{ab}$ is computationally indistinguishable from a random group element
• Pairing Security

Integer Factorization Problem

Not Post Quantum Safe

DLP is considered to be non Post Quantum Safe

• instance of Hidden Subgroup Problem (HSP)
• given $n$ where $n=p\cdot q$, $p$ and $q$ are large primes, find $p$ and $q$
  • to find by brute force, use Number Field Sieve (NFS) Algorithm
• relies on hardness of factoring large numbers

RSA Problem

• Given $c$, $e$, $n$, where $c=m^e(modn)$, find $m$
• problem is conjectured to be hard, but is easy given factorization of $n$
• RSA Encryption (Cryptosystem)

Lattice Problems

Post Quantum Safe

Some Lattice Problems are considered to be Post Quantum Cryptography (Post Quantum Safe)

Shortest Vector Problem (SVP)

undefined

Closest Vector Problem (CVP)

undefined

Learning With Errors Problems (LWE)

• might be more appropriately named “approximate linear algebra modulo q”
• the problem is basically to solve systems of linear equations where the equations are only approximately true, and instead of solving for rational or real numbers, we’re solving for integers modulo q
• Given a number of approximate equations of the form:
  • $y=a_1{x}_1+...+a_n{x}_n+ϵ$
  • solve for $a_1,...,a_n\in \mathbb{Z}/q\mathbb{Z}$ where each $ϵ$ is small

Ring Learning With Errors (RLWE)

Search Variant

• let Q be a big value
• let ring $R_{Q,N}:=\frac{Z_Q}{(X^N+1)}$
  • polynomials in $R_{Q,N}$ have coefficients in $Z_Q$ and degree $<N$
• let $S$ be secret polynomial $\in R_{Q,N}$ with coefficients from ternary distribution $\{-1,0,1\}$
• sample $A\in R_{Q,N}$ and sample error $E\in R_{Q,N}$ with coefficients from gaussian distribution
• given tuple:

$$(B=-A\ast S+E,A)$$

• finding $S$ is hard

NTRU

GGH