The Discrete Logarithm Problem

The discrete logarithm problem is used in cryptography. Given values for a, b, and n (where n is a prime number), the function x = (a^b) mod n is easy to compute. For example, if a = 3, b = 4, and n = 17, then x = (3^4) mod 17 = 81 mod 17 = 81 mod 17 = 13. But if you have values for x, a, and n, the value of b is very difficult to compute when the values of x, a, and n are very large.

If you set a value for a and n, and then compute x iterating b from 1 to n-1, you will get each value from 1 to n in scrambled order — a permutation. For example, if a = 3 and n = 17, then:

b = 1, x = 3^1 % 17 = 3
b = 2, x = 3^2 % 17 = 9
b = 3, x = 3^3 % 17 = 27 % 17 = 10
b = 4, x = 3^4 % 17 = 81 % 17 = 13
. . .
b = 16, x = 3^16 % 17 = 43046721 % 17 = 1

In addition to the discrete logarithm problem, two other problems that are easy to compute but hard to “un-compute” are the integer factorization problem and the elliptic-curve problem. These types of problems are sometimes called trapdoor functions because one direction is easy and the other direction is difficult. Many public-key-private-key cryptographic algorithms rely on one of these three types of problems. (Symmetric key cryptography systems, where there’s just one key that encrypts and decrypts, don’t use these ideas).

Unfortunately, it has been proven that quantum computing can “un-compute” these three types of problems. This means that a huge amount of encrypted data will become readable by bad people. It’s not clear when quantum computing will become practical, but most experts guess it will happen in 10-15 years.

A big risk is that bad guys will start harvesting encrypted data and hold onto it for 10 years until quantum computing becaomes available, and then decrypt the old bank account information, hospital records, and so on. Ouch.

One viable solution is for companies to start encrypting their data with a combination of regular encryption, like RSA, plus one of the new post-quantum (PQ) encryption algorithms that have been designed to not be breakable by a quantum computer. These new PQ algorithms are still being studied. Examples include BIKE (Bit Flipping Key Encapsulation) and FrodoKEM (Frodo Key Encapsulation Method).

The increase in computing power since the earliest computers has been astonishing. Here are three early personal computers that were used in the 1980s. Left: The Radio Shack TRS-80. Center: The Apple IIe. Right: The Commodore 64, so-named because of its impressive for the time 64K RAM memory (with a blazing for-the-time 1.0 MHz speed). Amazing.

This entry was posted in Miscellaneous. Bookmark the permalink.

Leave a Reply

Please log in using one of these methods to post your comment: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s