Public Key Revolution

Tweet

A New Direction in Cryptography

Recall that the private-key cryptography allows two users who share a secret to establish a “secure channel” which is a way to communicate with both secrecy and integrity. But the problem is that the need to share this secret key incurs several drawbacks.

1. The key-distribution problem:
   • How do users share a key in the first place?
2. The key-management problem:
   • Imagine N people, where each pair of them need to communicate securely. Each user must store / manage N-1 secret keys. There are O(N²) keys overall in the system.
3. Lack of support of “open systems”
   • When two users, who have no prior relationship, want to communicate securely.
   • This is not far-fetched, for example customer sending credit card data to merchant, or sending an email to a colleague.

“Classical” private key cryptography offers no solution to the problem mentioned above. A paper by Diffie-Hellman in 1976 that promised a new direction in cryptography.

---

---

Key Exchange Protocols

The key idea is that some problems exhibit asymmetry, i.e. it is easy to compute, but hard to invert, such as factoring. It is possible to use this asymmetry to enable two parties to agree on a shared secret key, using public discussion without having access to a secure channel. The protocols that achieve this are called Key Exchange Protocol. The steps are like this:

1. Two users interact back and forth in a sequence of rounds. The sequence of messages that the parties have exchanged by a transcript.
2. Each of the two parties should be able to generate a bit string of length n, that is a key. i.e. k ∈ {0,1}n.
3. They can use that key coupled with private key cryptography to setup a secure channel between them.

The security property that we are seeking is that:

1. From an attacker’s point of view:
   • Entire transcript can be observed by the attacker.
   • Being unable to compute the key given the transcript.
   • The shared key k should be indistinguishable from a complete uniform key.
2. From either of the parties’ point of view:
   • Given their local computation, and the transcript, they can compute the key k that the other party will compute also.

Formally, fix a key-exchange protocol Π and an attacker (passive eavesdropper) A. We can define the following experiment KE_A,Π(n):

1. Honest parties run Π using security parameter n, resulting in a transcript trans and shared key k of length n.
2. Choose a uniform bit b. If b = 0, set k' = k; if b = 1, choose uniform k' ∈ {0,1}n.
3. Give trans and k' to A, which outputs a bit b'.
4. Experiment evaluates to 1 (A succeeds) if b' = b.

The key exchange protocol Π is secure (against passive eavesdropping) if for all probabilisitic polynomial time attacker A, it holds that:

Pr[ KEA,Π(n) = 1 ] ≤ 1/2 + negligible(n)

NOTE: being unable to compute the key given the transcript (the Computational Diffie-Hellman problem) is a weak guarantee. But the indistinguishability of the shared key from uniform (the Decisional Diffie-Hellman problem) is a much stronger guarantee, which is exactly what is needed if the parties are going to use the shared key in a private key encryption scheme or in a message authentication code to ensure their future communication.

Also, the level of security against passive eavesdropper is not sufficient. In practice we want Authenticated Key Exchange, where not only are parties able toe generate a shared key, but also that the parties should both know each other’s identity, in particular who they’ve shared the key with. Modern key exchange protocols do provide this stronger notion of security.

---

---

Diffie-Hellman Key Exchange

Diffie-Hellman key exchange protocol is based on the Diffie-Hellman problem. Recall the problem, we have a group generation algorithm ? (script G), which on input a security parameter n, outputs a description of a cyclic group G of prime order q with generator g of that group. The length of q is n bits. The size of the group G will be roughly 2ⁿ, meaning there’re roughly 2ⁿ elements in the group.

The Decisional Diffie-Hellman (DDH) problem is the following: given elements g^x and g^y, where x and y are uniform exponents in the range of [0, q-1], to distinguish the group element g^xy from a completely uniform and independent group element (chosen uniformly) from the group G. The hardness of the DDH problem implies the hardness of the discrete logarithm problem, which is computing x from g^x and y from g^y.

In practice, the G, q, and g are standardized. So al parties in the world whoever what to run this protocol will simply know already what those parameters are, and they wouldn’t have to be generated as part of the protocol every time.

Eavesdropper sees the transcript, which includes the group G, the order q, the generator g, and elements g^x and g^y. But the shared key k = gxy, which can not be seen by the eavesdropper. Note computing the key k from the transcript is exactly the Computational Diffie-Hellman (CDH) problem, which is a weak guarantee. Distinguishing k from a uniform group elements is a stronger and what we need, which is exactly the Decisional Diffie-Hellman (DDH) problem. This implies if the DDH problem is hard relative to the generation algorithm ?, then this is a secure key-exchange protocol.

Map Group Element to Key

There is one more subtlety, we want our key exchange protocol to give us a uniform (looking) key k ∈ {0,1}n. However in the Diffie-Hellman protocol, we end up with a uniform looking group element k ∈ G, which may not have length equal to n, or may not be a uniform string. And in general, it is not clear how you would use a group element, random or not, as a key for encryption, say 128-bit AES.

The solution is rather simple: use a key derivation mechanism: set k’ = H(k), where k is the shared secret information (a group element), k' is a n-bit string, H is a suitable hash function. For H, you need stronger properties than just collision resistance.

---

---

Public-Key Setting

In 1976, Diffie and Hellman also introduced the “public-key setting”, in contrast to the private-key setting, one party generates a pair of keys: a public key pk and a private key sk.

Public key	Widely disseminated. Anybody who wants to communicate with this party is able to access the public key.
Private key	Kept secret by the party who generates these pair of keys. Used only by this party.

In contrast to the private key setting, here we have an asymmetry, which is in the keys used by various entities. There are usually two ways that the owner of a public key can distribute the public key:

1. Store the public key in a public repository, from where others can download later.
2. Send the public key directly over an open channel to the others.

Then others can use that public key for any subsequent communication. Notice in both ways, the public keys are potentially available to anyone. In particular we here have an assumption that attackers are passive during key distribution phase, we don’t assume that the attacker will actively interfere.

In the public-key setting, we have two primitives, that are corresponding to the counterparts in the private-key setting, achieving the same goals:

Public-key setting	Private-key setting	Security goals
Public-key encryption	Private-key encryption	Secrecy
Digital signature schemes	Message authentication codes	Integrity

Public Key Cryptography Addresses Drawbacks

How does the Public Key Cryptography address the drawbacks of Private Key Cryptography?

1. Key distribution problem
   • Public keys can be distributed over public (but authenticated) channels.
2. Key management problem
   • Every party generates their own pair of public and private keys.
   • In a system with N users, there are only N private keys and N public keys.
   • Each user stores 1 private key (of its own) and N-1 public keys (of others).
   • Public keys could be stored in a central directory.
3. Open systems problem
   • Parties with no prior relationship are able to find each other’s public keys and use them to communicate.

But Private Key Cryptography is still valuable. It is more suitable for certain applications, for example: disk encryption. Moreover Public Key Cryptography is roughly 2-3 orders of magnitude slower than Private Key Cryptography. If private key cryptography is an option, use it. Private key cryptography is used in the public key setting for efficiency considerations.

---

---

My Certificate

For more on Public Key Revolution, please refer to the wonderful course here https://www.coursera.org/learn/cryptography

My #90 course certificate from Coursera

---

Related Quick Recap

Factoring, RSA, Discrete-Logarithm and Diffie-Hellman

---

I am Kesler Zhu, thank you for visiting my website. Check out more course reviews at https://KZHU.ai

Don't forget to sign up newsletter, don't miss any chance to learn.

Or share what you've learned with friends!

Tweet