Suppose you are a diplomat who has discovered some terrible news. There are 16 of the highest-level people in the government whom you can send a message to, and you want to pick out 5 of them, with at least 3 of them present when decrypting the message. For example - you don’t want the president to know, but you want the head of the military, and 4 heads of the legislature to get the message. With normal encryption, you can send the message to each person individually, but you can’t force a threshold limit for the number of people involved in decrypting the message. The idea behind threshold encryption is that you have a total of N people whose public keys are in a single block. Anyone can pick out L of them and create an encryption key using their public keys from the block. Then they can specify a threshold T and encrypt a message that gets sent to the L recipients. Each recipient does a partial decryption. This part can really be complicated - or forced to be really simple - depending on how the use case is implemented. For example, you could make the decryption operation happen on one computer, and all the people who are part of the quorum enter their pass phrase into that machine. Or you could have each person’s decryption sent to a single person in the list who combines them for the final decryption. Once all the threshold number of people have done their part, the final step of decrypting the message can happen. The mathematics behind threshold encryption is pretty dense. For details, look at NIST. I’ve implemented it in code as well, with a description of the math plus code here. What is interesting is the possible uses for threshold encryption. While understanding the math is useful, understanding the potential uses is a more interesting challenge. look at NIST. math plus code here For this algorithm, N is a power of 2. This is not critical because you can have a set of dummy users. But it does affect the overall size of the public key block of data. The number of people a message is encrypted to, “L” in the above description, is less than or equal to N. So, what happens at the limits? If L = N, then everyone on the list can be a “decryptor”. If T = 1, you get a “broadcast” system. One encrypted message gets sent to everyone, and each person can decrypt it on their own. For the math to work, T must be less than or equal to L. You can force everyone on the list to take part in the decryption by setting T = L. For the diplomat example, you’d send the message to 5 people and then say all 5 of them must be present to decrypt the message because the shock needs to be distributed. The entire algorithm is described using seven steps. The first step is the “setup,” which determines the level of security and the total number of users N that can be dealt with. If, at some later time, you want to add more users, you start here with 2N to create what is known as a “Common Reference String.” The CRS is a block of vectors and matrices with a size that depends on N. With the CRS created, each person creates a private key, which gets turned into a public key. I like the idea that private keys are never stored; they are always recreated with the hash of a pass phrase. By implementing the algorithm with elliptic curves, this is trivial. The full public key for each user consists of 4N points, so it is much larger than a standard public key algorithm. Picking out who gets a message is called the “preprocess” step. The sender chooses the L recipients, and the algorithm combines their public keys into an encryption key and a vector called an aggregation key. The encryption key depends on the users in list L. The aggregation key is a combination of the keys not in L with the keys that are in L. Those two keys can then be used in the next step. The encryption step uses several random numbers combined with the CRS and encryption key to hide a message. The message is a number, but any string can be converted to a valid number fairly easily because the numbers are so big. The example program I wrote has a 520-byte number. After thinking about how I wrote the program, I realized I could use the same hiding value on several sets of 520-byte blocks. So, there is no real limit to the size of a message one can hide. But it might be easier to use the 520 bytes as a key for a symmetric algorithm. Once everyone gets the encrypted message, they each use their private key to create a one-time public key. They each pick a random number to combine with the CRS data and their public key. In the algorithm, this is called “partial decryption”, but it is really just a combination of known parameters along with another random number to hide their private key. The aggregator of all the partial decryption values then does a “partial verify” step using the public key of each user along with the CRS data. This is not really essential, but it is never a bad idea to check things when you can. From an implementation perspective, it is an essential security check. When enough users have combined their partial decryption values, the message can be decrypted. This is where the math gets really messy. All the random numbers divide out, all the public keys combine, and an inverse matrix removes a set of secret numbers in the CRS. If you like math, it’s pretty cool. The math is based on point pairing over elliptic curves. At the present time, no algorithm is known that can undo the math (called the elliptic curve logarithm problem). Algorithms have been proposed that would work on a quantum computer with some 2^32 Toffoli gates. Once a single Toffoli gate has been constructed, Moore’s law of quantum computers can begin. If the doubling time is one year, then there are 32 years before 128-bit secure elliptic curves are cracked. If you need to hide things for 50 years, then maybe you want to worry about quantum computers breaking your message 40 years from now. But since the clock hasn’t started, it may well be 60 years before anyone can crack an elliptic curve algorithm from today. For most people, threshold encryption is perfectly secure and will be for another 30+ years. Especially if you only need to hide things for a few years. I’m confident there are many more uses for threshold encryption that I haven’t thought of. So, check it out and see what you can do.

What Is Threshold Encryption?

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

BBS Signatures Using Weil Pairings

102 Stories To Learn About Encryption

153 Stories To Learn About Cryptography

5 Books You Can Read to Boost Your Computer Science Knowledge

6 Not-so-obvious Tech Predictions

63 Stories To Learn About Quantum Computing

BBS Signatures Using Weil Pairings

102 Stories To Learn About Encryption

153 Stories To Learn About Cryptography

5 Books You Can Read to Boost Your Computer Science Knowledge

6 Not-so-obvious Tech Predictions

63 Stories To Learn About Quantum Computing

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps