Cryptography and Network Security

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 ...

Digital Signature (DS):  Before the advent of computer communication, handwritten signature were commonly used as a promising tool for validating proposals.  With the rise of computer communication, handwritten signature were gradually replaced by digital signatures.  Thus, the interplay between encryption and signature methods was enabled by their digitalization and the introduction of computational complexity as a basic for security.  Loosely speaking, a scheme for unforgeable signature requires that 1. each user can efficiently generate their own signature on documents of their choice,  2. each user can efficiently verify whether a given string is valid signature of another user on a specific document, and 3. no one can efficiently produce the signature of another user on documents that the users did not sign.  Message Authentication (MA): First, consider a scenario where an adversary is monitoring the channel and may alter the message sent transmitted t...