NP-Hardness vs Cryptographic Hardness

To understand the gap between these two terms, we divide this blog into two parts. In first part, we discuss complexity theory, and in second part, we explore cryptographical perspective. 

Complexity Theory: 

For a better understanding of complexity theory, we refer readers to [1]

Language L: A language L is a set of strings defined over an alphabet set Σ.

Class P (polynomial time): A language L is in P if L is decidable in polynomial time by a deterministic Turing machine.

Example: Language = Reachability. Input: Graph G(V,E), and s,t ∊ V(G). Question: Does their exist a path from s to t ? 

The above Language is an example of Class P  (hint: can be easily solved by BFS/DFS algorithm). 

Class NP (non deterministic polynomial time): A language L ∊ NP if the certificate for L can be verified by a non-deterministic Turing machine in polynomial time.  

A certificate for a language L is an instance of the solution L.

Example: Language: Composite number. Input: An integer n ∊ Z+. Question: Does there exist a non-trivial factor d such that 1<d<n and d|n.

The above language is an example of Class NP. 

Class NP-Hardness:  A language L is NP-hard if there exist a polynomial time Turing reduction from every language L' in NP to L. 

Example: Minimum Hamiltonian path problem is NP-hard (for good introduction to Hamiltonian path we refer the readers to [2]). 

Class NP-Complete: A language L is NP-complete if 1) L ∊ NP, and 2) L ∊ NP-Hard.

Example: Hamiltonian path is an example of NP-Completeness. 

Open problem: Till date, it is unknown whether that P = NP or P≠NP ?

Cryptography Perspective: 

Cryptographic research often begins with P ≠ NP. 

Reason: When designing an encryption algorithm, we assume that no adversary can break the algorithm in polynomial time. Therefore, ensuring that breaking the scheme NP-hard is necessary starting point. 

Question: Is NP-Hardness alone sufficient? 

Answer: Probably not. 

Reason: Suppose breaking a certain encryption scheme is NP-Complete. Then, if P≠NP, this implies that this encryption scheme is hard to break in worse case. 

However, this does not rule out the possibility that the scheme may be easy to break in most cases. For instance, one could construct an encryption scheme for which the breaking problem is NP-complete, yet there exist an efficient breaking algorithm that succeeds 99% of the time. Thus, worse case hardness alone is inadequate for security; we require at least average case hardness. 

Cryptographic Hardness: A necessary condition for the existence of secure encryption scheme is the existence of languages in NP that are hard on average. 

Thus, the above analogy teaches us that an encryption scheme must be cryptographically hard. 

Question: Is average case hardness is sufficient for both encryption and decryption. 

Answer: Probably not for decryption. 

Reason: If decryption algorithm itself encounters hardness, then even a legitimate receiver would never be able to decrypt the message. 

Solution: To use such hard-on-the-average problem in cryptography, we must be able to generate hard instances together with auxiliary information that will enable us to solve these instances fast. 

(This auxiliary information is secret key, known only to legitimate user running the decryption algorithm, which enables decryption of the scheme in polynomial time). 


We thanks to..

[1] Michael R. Garey and Juris johnson, david S. Hartmanis. Computers and Intractability: A Guide to the Theory of NP-Completeness. Siam Review, 24(1):90, 1982.

[2] https://en.wikipedia.org/wiki/Hamiltonian_path

[3] Oded Goldreich. Foundations of Cryptography (Part- I).


Comments

Post a Comment

Popular posts from this blog

Elliptic Curve Cryptography (ECC) and ECDSA

Image
Elliptic Curve Cryptography (ECC) Elliptic curve (EC) was first introduced by Neal Kobiltz and Victor Miller in 1985. Elliptic curve is a non-singular curve that is operated on a finite field Zq (where q is the order of elliptic curve). EC consists of set of points that satisfies the following equation as follows.                                                                   Y 2 = X 3 + aX + b Where {X,Y,a,b} ∈ Zq, and 4a 3 + 27b 2 ≠ 0. Next, we discuss the encryption and decryption mechanism between two parties (Say α and γ ). Remark 1: Elements selected from party α is represented by capital letters whereas elements selected from party γ is represented by small letters. i) Key Generation: 1. Secret key: Each party α and γ selects secret keys S ∈ Zq and s ∈ Zq. 2. Public key: P ...
Read more

Fast Base Conversion and Its Application

Image
Fast Base Conversion (FBC) is a technique used to convert a number from one modulus space to another. For example, if we have 14 m o d     77 14 \mod 77  and want to convert it to x m o d     390 x \mod 390 , FBC is widely used. Mathematically, it can be represented as follows: Here, the above equation represents an integer x x  in modulus q q , and FBC converts this integer into the modulus space t t . The modulus q q  is the product of small coprime moduli (i.e., q = q 1 q 2 … q k q = q_1 q_2 \dots q_k ​ ), and x x  is an integer such that x ∈ [ 0 , q ) x \in [0, q) . We also note that q q  and t t  are coprime numbers. Here, we remark that it is not necessary for the above equation to produce the exact result for x x . Instead of x m o d     t x \mod t , it will provide x ′ m o d     t x' \mod t . Thus, the output of the above equation is as follows: FBC ( x , q , t )  =  x  +  A q  mod  t , where A ∈ [ 0 , k − 1 ] A \in [0,...
Read more