We all know what Public-Key Cryptography is :). As opposed to symmetric cryptography where there is only one key, in PKC there are at least two keys: one for encryption and one for decryption. In more general sense, we have two (or more) keys, whose capabilities are different. One key is good for encryption only and one for decryption only, in contrast to symmetric cryptography where one key is good for everything.

RSA

The best-known Public-Key Cryptosystem is Rivest–Shamir–Adleman algorithm, or RSA for short. Its security is based on hardness of finding a modular logarithm. Speaking very briefly, we need to generate two (very large) numbers that are their respective inverses in a modular multiplicative group (that means, when they are multiplied modulo some big number, they give 1). Then we publish one of them as the public key.

(public_key * private_key) % modulus = 1

Anyone can encrypt a number by taking it to the power of the public key. (For exponentiation I use Python notation here.)

(cleartext ** public_key) % modulus = ciphertext

Then only the holder of the private key can decrypt the message.

(ciphertext ** private_key) % modulus = cleartext

This works, because finding an inverse in a multiplicative group is hard. However, generating two random numbers that are their respective inverses is easy.

ECDLP

Another approach to PKC utilizes so-called elliptic curves. An elliptic curve is a special mathematical structure that features addition and multiplication by scalar. Despite the name, they do not have much to do with actual curves, and they get their name because certain equations used to define them resemble equations used to plot an actual geometric elliptic curve. In fact, they can have a nice graphical interpretation. A good introduction with illustrations can be found in the article "Elliptic Curve Cryptography: a gentle introduction".

A discrete logarithm problem can be formulated in an elliptic curve structure too. The maths resembles RSA, but this time we do calculations in an elliptic curve and not in a modular multiplicative group. The security of this cryptosystem is better than RSA in smaller number of bits. This approach is called Elliptic Curve Discrete Logarithm Problem, or ECDLP for short.

Beyond basic PKC

So far we have learned about two PKCs, but their function is very basic: they can encrypt and decrypt data. Can we do more with PKCs beyond simple encryption? The answer is yes and many theoretical concepts have been designed.

Digital Signatures

The first creative application of PKCs can be digital signatures. We get it simply by replacing the roles of the public and the private key. We can encrypt data using our private key and publish them for anyone to decrypt. This proves that the message originates from the owner of the private key. Digital signature algorithms are well established, secure and are in common use.

Identity-Based Encryption

In traditional PKC the user has to generate their private and public key and then distribute the public key. Could we do it better? What if some public identifier of the user, for instance their phone number, email address or even postal address could be used as the public key? This cryptosystem assumes some central trusted key-generation facility that is able to verify the user's identity. First, we take the recipient's public identity (i.e. phone number). We download a special public key from the central key-generation facility and combine it with the phone number to get the encryption key. We use it to encrypt the message. Then we transmit the cipher to the recipient. When the recipient receives the encrypted message, he must decrypt it somehow. First he contacts the key-generation facility, identifying with his public identity. In the case of the phone number, he might be required to send a text message to the server. If the public identity used was email address, he might need to send an email. In any case, if the identity verification was successful, the key-generation facility responds with a decryption key. Then the recipient is able to decrypt the message.

This kind of cryptosystem could be used to implement "pay to email" or "pay to phone" features like those of PayPal or Revolut. The biggest challenge is obviously the need to trust the central key-generation facility, and also to rely on the accuracy of identity verification (think of phone stealing, password sniffing or even breaking the cryptography that secures the transmission channel). Nevertheless, it is better than no cryptography at all.

Attribute-Based Encryption

We could generalize Identity-Based Encryption further to use a set of recipient's attributes instead of just one public parameter. We could for instance require 4 attributes as a basis of the recipient's identification: his phone number, email address, Facebook profile and IP address. Then the verification does not have to be perfect: for instance we could require only 3 of the attributes to match and the fourth can be wrong.

This system has very similar applications to the Identity-Based Encryption, but allows us to implement several more functions, such as:

• securely sending a message to a recipient when our information about him is inaccurate (i.e. we are not sure what his email his and we know only his phone and Facebook)
• identifying a user based on more than one identity, aka multi-factor authentication
• partial resistance against losing some of the user's credentials (i.e. if the user loses password to his email or his phone is stolen, he could still be identified by his other attributes)
• combining several weaker identification protocols into a stronger one

and so on.

In the context of blockchain, Attribute-Based Encryption schemes could be used to implement very desired KYC checks without deploying new infrastructure. The existing user identification infrastructure, such as people's phone numbers, social media profiles or even bank account numbers could be used to identify a user without developing some new expensive system.

While there are not many practical implementations of ABE, I recently learned about the company Zeutro who are developing this technology. Their whitepaper is still in the queue of my things to read, so please wait a while until I give some insights :).

Functional Encryption

Functional Encryption is one step further in generalization of Public-Key Cryptography. It features two keys: encryption and decryption key. We encrypt and then decrypt some message. However when we will have done that, we will get a message transformed by some function.

Formally:

DECRYPT(ENCRYPT(message)) = F(message)

Recall the basic PKC protocol. We take the user's public key, we encrypt the message and we send it to the user. Then he can recover the message. With Functional Encryption he would get a modified message, and the modification is done by a function of our choice.

Both IBE and ABE could be implemented using Functional Encryption, if we had a working algorithm for that. But we could do much more.

Imagine we are making a service and we want to authenticate users based on a username and password. However, our users are clumsy and sometimes mistype their passwords. Now we want to authorize a user if he gave us a password with at most two typos. Quite a silly example, but serves to illustrate a concept. First we need to write a function (program) that calculates the Hamming distance of the provided text to the password in our database. Then we generate a pair of FE keys that perform the function: if the Hamming distance of the argument to the password is at most 2, return true. Otherwise, return false. We publish the public key. Then the user simply needs to encrypt the typed password and send it to the server. After decryption, we get the answer if the password was right, within bounds. Nothing more about the typed password is revealed. This way the user gets what he wants, that means he never shows us his password in cleartext. And we get what we want, that means we know if the provided password is close enough to the right one.

FE could be used for exactly that: to securely share part of our private data without revealing much more. Imagine possible applications:

• logging a user in without the server knowing which user logged in
• assigning the necessary access privileges without knowing who the user is
• verifying some user private information (i.e. age) based on government-issued data that we are able to validate, yet we do not learn anything more besides the necessary information
• calculating a person's credit score while not learning any of his private data.

Functional Encryption could give us benefits of absolute privacy and still let us enjoy most of services of current technology that requires us today to abandon all anonymity.

Conclusion

In the past decades cryptography allowed us in many aspects to move from human-level trust to electronic-level trust. It is often said that traditional services are trusted and modern services are trustless. While trust is good, much care must be taken who we trust. History showed that oftentimes people who we trust turn out to abuse their power. Cryptography could bring us better society, where honesty of many public services does not depend on the whim of somebody in power.

That is why I devoted myself to making blockchains, cryptographic algorithms and secure protocols.