When you first learn cryptography, you might be introduced to the familiar RSA encryption scheme, a public-key cryptosystem used for secure encryption. However, as elegant as the mathematics of this simple scheme can be, a deeper look shows that RSA’s basic function cannot be considered entirely secure in a modern context.

Securing Communication

The ideas behind the RSA scheme are indeed used in modern systems but as just one piece in a complex jigsaw puzzle. We combine the RSA primitive with other security jigsaw pieces, such as elliptic curve-based protocols, message authentication codes and symmetric ciphers, into a larger cryptographic picture. For example, the transport layer security (TLS) protocol (used by your browser) is designed to enable secure web browsing. It is based on public key cryptography, but the public key is used for authentication and not encryption. Usually, the public key is one based on the RSA algorithm. Thus, we do not use RSA in its original guise as an encryption algorithm. One can see already how what appeared to be a simple model starts to appear more like just one piece of a bigger composite picture.

In a system such as TLS, we can identify three players: The sender (Alice), the receiver (Bob) and an adversary (Eve) who is sitting between them and trying to access the information they are exchanging. However, this model doesn’t take into consideration other factors, for example, that there might be more than one Alice or Bob and that some of them could be controlled by Eves. It is this extra complexity (that Alice could indeed be a malicious Eve) that creates the need for a complex jigsaw of cryptographic algorithms and which makes the classical textbook use of the RSA algorithm insecure.

Securing Computation

If such a complex puzzle can arise from a simple cryptographic application such as communication security, it is not surprising that things also get complex when one considers trying to secure data during computation. There are several cryptography techniques that can be used, with fully homomorphic encryption (FHE) enabling data procession without decryption. Naively, one can apply FHE to securing computation in much the same way as one can apply RSA naively to securing communication. it is common (even for seasoned cryptographers) to think they can approach FHE in the same way that the naive undergraduate approaches encryption via RSA. But as we saw above, this is not how basic encryption schemes should be approached when building complex protocols.

With FHE, we now have four entities: An encryptor (Alice), a decryptor (Bob), someone doing the FHE computation (Charlie) as well as an adversary (Eve). It may seem like a simple scenario, but things are more complicated than they appear since from Alice’s perspective, both Bob and Charlie could actually be adversarial, and from Bob’s perspective, both Alice and Charlie can be adversarial, and so on. When we add additional Alices, Bobs and Charlies into the mix, things can become very complex very quickly. Luckily, cryptographers already have a notion of what such a protocol is trying to accomplish, one that should be used to look at FHE: It is a multi-party computation (MPC) protocol.

Just as TLS requires additional cryptographic components (elliptic curve-based protocols, message authentication codes and symmetric ciphers), as well as the basic RSA primitive, to make a secure protocol, we need more than just FHE to create a secure computation protocol. So, what other puzzle pieces are needed to create our jigsaw?

Additional Puzzle Pieces

Zero-Knowledge Proofs: As well as FHE, we need an additional primitive called a zero-knowledge proof. This is because Alice (the data encryptor) could be adversarial. She could try to create badly formed ciphertexts. Alice needs to prove to all other parties that every ciphertext is validly created and that she knows the underlying message. She needs to do this of course without revealing the underlying message (hence the need for zero-knowledge proofs). This stops Alice from mounting attacks such as copying another Alice’s input as her own (which can result in data leakage), creating ciphertexts that result in the computation not succeeding, or giving the incorrect output to Bob. We cannot stop Alice from lying about her input, but we can stop Alice from purposely disrupting the computation.

Threshold Cryptography: With a single Bob, one is limited in the usefulness of any protocol for secure computation. FHE usually has a single secret key. Anyone with this key can decrypt anything. Thus, if we have a single Bob, then that Bob can also decrypt all of the messages, and in particular, Alice’s input. Hence, even having a single Bob can cause security problems. Using threshold cryptography, we can split the FHE secret key into parts and give them to multiple Bobs. This not only makes our protocol more useful (in situations where different parties obtain output), but it also prevents the single point of failure of having a single secret key held by a single entity, Bob.

Verifiable Computation: Charlie, who we recall is actually doing the computation, could compute a different function than that which Alice and Bob think he is. This is a security concern as Alice trusts Charlie not to compute a function that directly reveals her data. Bob is expecting a specific function to be computed upon which he may base further business decisions. Thus, it is vital that the other parties know that Charlie is indeed doing the correct operations. This problem is solved by requiring Charlie to use a form of verifiable computation. The simplest way of doing this is to have multiple Charlies, each of which duplicates the homomorphic computation, with Bob taking the majority output as the final encrypted output. More complex forms of verifiable computation require (simpler) forms of the zero-knowledge proofs we mentioned earlier to be applied.

Summary

FHE should not be seen as a simple encryption algorithm with special properties ready for simplistic deployment, just as textbook RSA should not be seen as a simple encryption algorithm ready for immediate deployment. FHE needs to be viewed within a protocol that provides a cryptographic service. Thus, one needs to combine FHE with other cryptographic primitives and ideas, and one needs to think holistically about the entire system’s security.