Cryptographic Hardness Assumptions

Ref. Chapter 8 INTRODUCTION TO MODERN CRYPTOGRAPHY by Jonathan Katz and Yehuda Lindellbar

Asymptotic Approach (Key-concepts)

This approach introduces an integer-valued security parameter (denoted by $n$) that parameterizes both cryptographic schemes as well as all involved parties (namely, the honest parties as well as the attacker). The security parameter is public.

The value $n$ is associated to the security since:

• we consider randomized (i.e., probabilistic) algorithms running in time polynomial in $n$ (PPT) efficient adversaries.
• we consider negligible probability small probabilities of success.

Remark: both these notions are asymptotic.

Informally, notions of security sound like: A scheme is secure if any PPT adversary succeeds in breaking the scheme with at most negligible probability.

Integer factorization and RSA

Factorization problem

The fundamental theorem of arithmetic states that every integer $n>1$ can be decomposed uniquely (up to permutation) as a product of prime factors. Namely, there exist unique $p_1<\dots<p_k$ prime integers and $e_1,\dots e_k\in\mathbb N^+$ such that $$ n= \prod_{j=1}^k p_j^{e_j}$$

CompQuest: Can we efficiently compute the set $\{(p_i,e_i)\}_{i=1}^k$?

CompQuest: Can we efficiently decide if a number is prime?

The notion of efficient strictly depends on the context! Here, we have a cryptographic perspective. Therefore, we read it as polynomially respect to the bitsize of $n$.

We address a "simpler" problem:

Problem F: Given a composite integer $N$, find $p,q>1$ such that $N=p\cdot q$.

Remark: in PF $p$ and $q$ are not necessarily primes!

Trial method for FP

We can use the definition.

from math import sqrt

def find_factor(n):
    if n>=2:
        for x in range(2,int(sqrt(n))+1):
            if n%x==0: return x
        print("%d is prime!" %n)

N=1093
print(N.bit_length())
find_factor(N) 

11
1093 is prime!

N=7338053
print(N.bit_length())
p=find_factor(N) 
print(p)

23
193

b=N//p
b*p==N

True

N=15850571424723771767 #64-bit
print(N.bit_length())
find_factor(N)

64

---------------------------------------------------------------------------
KeyboardInterrupt                         Traceback (most recent call last)
<ipython-input-5-45b5ca6864e5> in <module>
      1 N=15850571424723771767 #64-bit
      2 print(N.bit_length())
----> 3 find_factor(N)

<ipython-input-1-91c6419bfa9c> in find_factor(n)
      4     if n>=2:
      5         for x in range(2,int(sqrt(n))+1):
----> 6             if n%x==0: return x
      7         print("%d is prime!" %n)

KeyboardInterrupt: 

Exercise: compute the complexity of this algorithm.

A simple Experiment for FP

Let us consider an algorithm $\mathcal A$ and a parameter $n$.

Experiment WFP$_n(\mathcal A)$:

1. Choose uniformly at random $p,q>1$ two $n$-bit integers.
2. Compute $N=pq$.
3. $\mathcal A$ given $N$ computes $p',q'>1$.
4. Return 1 if $N=p'\cdot q'$, 0 otherwhise.

In order to say that PF is hard, we would like the following statement to be true:

"for every PPT algorithm $\mathcal A$ we have that $P[WFP_n(\mathcal A)=1]\leq negl(n)$"

However, 2 is factor with probability 0.75!

Factoring Assumption

To get an "hard problem" we consider $N=p\cdot q$ where $p,q$ are two distinct primes. Namely, let us consider $\mathtt{GenModulus}$ be a PT algorithm such that, given as input $1^n$, outputs a tuple $(N,p,q)$ such that: $N=pq$ and $p$,$q$ are $n$-bits primes.

Experiment $\mathtt{Fact}_{\mathcal A,\mathtt{GenModulus}}(n)$:

1. Generate $(N,p,q)$ by $\mathtt{GenModulus}(1^n)$.
2. $\mathcal A$ given $N$ computes $p',q'>1$.
3. Return 1 if $N=p'\cdot q'$, 0 otherwhise

Informally, the factorisation problem consists in computing a factor of a composite integer $N$ of unknown factorization.

Definition the factorization problem is hard relative to $\mathtt{GenModulus}$ if for all PPT algorithm $\mathcal A$ there exists a negligible function $negl$ such that: $$P[\mathtt{Fact}_{\mathcal A,\mathtt{GenModulus}}(n)=1] \leq negl(n).$$

Assumption (Factoring) there exists a $\mathtt{GenModulus}$ relative to which factorization problem is hard relatively to.

RSA

Historically, the most used and famous cryptosystem among those whose security is based relates to factoring is RSA. The RSA problem was introduced by Rivest, Shamir, and Adleman in 1978.

Exponentiation in $\mathbb Z^{*}_N$

Proposition: Let us consider a modulus $N$ and an integer $e > 2$ that is coprime with $\phi(N)$, i.e. $gcd(e,\phi(N))=1$. Then, the map $$\begin{matrix} f_e:& \mathbb Z^{*}_N& \rightarrow& \mathbb Z^{*}_N \\ &y&\rightarrow& [y^e \mod N] \end{matrix}$$ is bijective. Moreover, if $ d=[ e^{-1} \mod \phi(N)]$ then $f_d$ is the inverse of $f_e$.

Example: For $N=24$ compute the image of $f_3$, $f_5$ and if possible the inverse function.

from math import gcd

N=24
ZNs=[a for a in range(N) if gcd(a,N)==1 ]
print(ZNs)
phiN=len(ZNs) ##Do you know another method to compute phi(N)?
print(phiN)

[1, 5, 7, 11, 13, 17, 19, 23]
8

print(gcd(phiN,3)==1)
f3= lambda y : (y**3%N)
print({f3(a) for a in ZNs})

True
{1, 5, 7, 11, 13, 17, 19, 23}

print(3*3%phiN==1)
for a in ZNs:
    x=a,f3(f3(a))
    print( x, end=',')

True
(1, 1),(5, 5),(7, 7),(11, 11),(13, 13),(17, 17),(19, 19),(23, 23),

print(gcd(phiN,4)==1)
f4= lambda a : (a**4%N)
print({f4(a) for a in ZNs})

False
{1}

RSA Assumption

Let us consider a modulus $N$ and an integer $e > 2$ that is coprime with $\phi(N)$, i.e. $gcd(e,\phi(N))=1$. $f_e$ is invertible, so in the following for any $y\in \mathbb Z^*_N$ we denote $y^{1/e}=f_e^{-1}(y)$, and we call it the $e^{th}$ root of $y$.

Informally, the RSA problem consists in computing $y^{1/e}$ for a modulus $N$ of unknown factorization.

Let us consider $\mathtt{GenRSA}$ be a PPT algorithm such that, given as input $1^n$, outputs a tuple $(N,e,d)$ such that

• $N=pq$ where $p$,$q$ are unknown $n$-bits primes,
• $e>0$ such that $gcd(e,\phi(N))=1$,
• $d>0$ such that $ed=1 \mod \phi(N)$. The algorithm might fail with probability negligible in $n$.

Experiment $\mathtt{RSA-inv}_{\mathcal A,\mathtt{GenRSA}}(n)$:

1. Generate $(N,e,d)$ by $\mathtt{GenRSA}(1^n)$.
2. Choose uniformly at random $y \in\mathbb Z^{*}_N$.
3. $\mathcal A$ given $N,y,e$ outputs $x\in \mathbb Z^{*}_N$.
4. Return 1 if $x^e=y \mod N$, 0 otherwhise.

Definition the RSA problem is hard relative to $\mathtt{GenRSA}$ if for all PPT algorithm $\mathcal A$ there exists a negligible function $negl$ such that: $$P[\mathtt{RSA-inv}_{\mathcal A,\mathtt{GenRSA}}(n)=1] \leq negl(n).$$

Assumption (RSA) there exists a $\mathtt{GenRSA}$ relative to which the RSA problem is hard relatively to.

Remark: Computing $e^{th}$ roots modulo $N$ is easy if $d,\phi(N )$, or the factorization of $N$ is known. This is crucial in order to define the RSA public-key cryptosystem.

The Discrete-Logarithm and Diffie–Hellman Assumptions

Let us consider a cyclic group $G=<g>$ (we use multiplicative notation), recall $$G= \{g^k : k\in Z\}$$

Suppose $G$ has finite order $q$ then $$G= \{g^0, g^1,\dots, g^{q-1}\}$$ and for every $h\in G$ there exists unique $s\in \mathbb Z_q$ such that $h=g^s$.

In this case, we call $s$ the discrete logarithm of $h$ with respect to $g$ and we write $s=\log_g h$.

Problem DL: Given a cyclic group $G=<g>$ and $h\in G$ sampled uniformly at random, find $\log_g h$.

Mem: $(\mathbb Z_{N},+)$ is a cyclic group.

Example: compute $\log_1 21$ and $\log_5 21$ in $\mathbb Z_{24}$ ( Achtung! here we use additive notation)

N=24
g0=1
for k in range(24): print(k*g0%N, end=',') 
h= 21
s0=21
h== s0 * g0 % N

0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,

True

g=5
for k in range(24): print(k*g%N, end=',') 
h= 21
s= 9
h== s * g % N

0,5,10,15,20,1,6,11,16,21,2,7,12,17,22,3,8,13,18,23,4,9,14,19,

True

Discrete Logarithm Assumption

Informally, the discrete-logarithm assumption is simply the assumption that there exists a $G$ for which the discrete-logarithm problem is hard

Let us consider an algorithm $\mathcal A$ and a parameter $n$. Let

Experiment $\mathtt{DLog}_{\mathcal {A},\mathcal {G}}(n)$:

1. Run $\mathcal {G}(1^n)$ to get $(G,q,g)$ where $G=<g>$ is a cyclic group of order $q$ with $q$ a $n$-bit integers.
2. Choose uniformly at random $h \in G$.
3. $\mathcal A$ given $G,g,h,q$ outputs $s\in \mathbb Z_q$.
4. Return 1 if $s=\log_g h$, 0 otherwhise.

Definition the discrete logarithm problem is hard relative to $\mathcal{G}$ if for all PPT algorithm $\mathcal A$ there exists a negligible function $negl$ such that: $$P[\mathtt{DLog}_{\mathcal A,\mathcal {G}}(n)=1] \leq negl(n).$$

Assumption (DL) there exists a $\mathcal{G}$ relative to which the discrete logarithm problem is hard relatively to.

Diffie–Hellman Assumptions

Diffie–Hellman assumptions are strictly related to DL but not equivalent (as factoring and RSA!)

Definition Given a group $G$ and a generator $g\in G$. Consider two elements $h_1,h_2\in G$ such that $s_1= \log_g h_1$ and $s_2= \log_g h_2$, we denote $$\mathtt{DH}_g(h_1,h_2)=g^{s_1\cdot s_2 }=h_1^{s_2}=h_2^{s_1}$$

Problem CDH The computational Diffie-Hellmann problem consists in computing $\mathtt{DH}_g(h_1,h_2)$ for $h_1,h_2$ sample uniformly at random from $G$.

Problem DDH The decisional Diffie-Hellmann problem consists in deciding whether an element $h'$ is of the form $\mathtt{DH}_g(h_1,h_2)$ for $h_1,h_2$, sample uniformly at random from $G$, or was chosen uniformlyat random from $G$.

Informally, the DDH problem is to distinguish $\mathtt{DH}_g(h_1,h_2)=g^{s_1\cdot s_2 }$ from a uniform group element when $h_1 , h_2$ are uniform. Namely, given uniform $h_1 , h_2$ and a third group element $h_0$, the problem is to decide whether $h_0 = \mathtt{DH}_g(h_1,h_2)$ or whether $h_0$ was chosen uniformly from $G$.

Definition the DDH problem is hard relative to $\mathcal{G}$ if for all PPT algorithm $\mathcal A$ there exists a negligible function $negl$ such that: $$|P[{\mathcal A}(G,q,g,g^x,g^y,g^z)=1]-P[{\mathcal A}(G,q,g,g^x,g^y,g^{xy})=1]| \leq negl(n),$$ where in each case the probabilities are taken over the experiment in which $\mathcal G(1^n)$ outputs $(G,q,g)$ and subsequently $x,y,z \in \mathbb Z_q$ are chosen.

Remark: if the DL problem is easy relative to some G, then the CDH problem is too. Similarly, if the CDH problem is easy relative to G then so is the DDH problem. But we don't know if the converse is true.

Selecting $\mathcal G$:

• if the order $q$ of the group has small prime factors, DDH is easy.
• decisional Diffie–Hellman problem should be hard in prime-order groups.
• prime-order groups are cyclic. Moreover, it is straightforward to get a generator.
• DL is hardest in prime order groups.

Discrete Log in $\mathbb Z^{*}_p$

Theorem: If $p$ is a prime, then $\mathbb Z_p^*$ is a cyclic group of order $p-1$.

Example: $\mathbb Z_{11}^*$

from math import gcd
p=11
Zps=[a for a in range(p) if gcd(a,p)==1 ]
print(Zps)
g=2
Gg=[g**k%p for k in range(p-1)] 
print(Gg) ## is 2 a generator? 
g=7
Gg=[g**k%p for k in range(p-1)] 
print(Gg) ## is 7 a generator?    

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 2, 4, 8, 5, 10, 9, 7, 3, 6]
[1, 7, 5, 2, 3, 10, 4, 6, 9, 8]

g=5
Gg=[g**k%p for k in range(p-1)] 
print(Gg) ## is 5 a generator? 
g=1
Gg=[g**k%p for k in range(p-1)] 
print(Gg) ## is 1 a generator? 
g=10
Gg=[g**k%p for k in range(p-1)] 
print(Gg) ## is 10 a generator?

[1, 5, 3, 4, 9, 1, 5, 3, 4, 9]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 10, 1, 10, 1, 10, 1, 10, 1, 10]

CompQuest: Can we efficiently compute the DL in $\mathbb Z_p^*$?

Groups of order $p$ prime are groups in which the DL problem is believed to be hard.

In general we could use as $\mathcal G$ analgorithm that chooses a uniform $n$-bit prime $p$, and outputs a representation of $\mathbb Z_p^*$, $q = p -1$ along with a generator $g$.

However, for $p > 3$, $\mathbb Z_p^*$ does not have prime order!! (Can you quickly tell why?) Therefore, $\mathbb Z_p^*$ is not a good choice for the cryptographic applications based on the DDH/DL assumption.

Nevertheless, we can solve this by working of subgroups of prime order of $\mathbb Z_p^*$.

Theorem: Suppose $p-1=rq$ and $p,q$ prime.Then, $G=\{[h^r \mod p] | h \in\mathbb Z_p^* \}$ is a subgroup of order $q$.

This implies that we can generate a subgroup of $\mathbb Z_p^*$ of prime order!

In practice, standardized values (e.g., see NIST, keylenght) for $p, q$, and a generator $g$ are used.

CompQuest: Can we efficiently sample a prime of given size?

Exercise: compute the complexity of this algorithm.