— Here are the exact coordinates of each operative deployed in the combat zone.
— How much?
— That is too much.
— And a code that displays on screen the updated position of each and every enemy soldier.
Video games are a very serious business. They move a market worth many billions of euros worldwide and attract all kinds of criminals.
For example, in an online multiplayer video game, each device needs to know the position of all objects on the ground in order to render them correctly in 3D. In addition, it needs to know the positions of other players, to render them if they are in sight of the local player or not to render them if they are hidden behind walls or rocks. The server faces a classic dilemma: if it provides the positions of the players to the other players, they can cheat; but if it does not provide them, the game will not know when to show the hidden players.
Instead of providing exact coordinates, it would be ideal to be able to provide information on whether or not a target is in view of the local player, but without revealing its position. This was hardly possible until the invention of functional cryptography.
Functional Cryptography, A Step Beyond Conventional Public-Key Cryptography
Despite all its benefits and wonders, public key cryptography has some practical limitations:
- It provides all-or-nothing access to the encrypted data: either you decrypt the full plaintext, or you get no information about the plaintext at all.
- Once the data is encrypted with the public key, there is only one private key capable of decrypting it.
In 2011, D. Boneh, A. Sahai and B. Waters proposed to go beyond conventional asymmetric encryption with their functional cryptography: a new approach to public-key encryption in which different decryption keys allow access to functions on the data in clear. In other words, functional cryptography makes it possible to deliberately leak information about the encrypted data to specific users.
In a functional encryption scheme, a public key, pk, is generated. Any user can encrypt a secret message, m, with it, so that c = E(pk, m). And here comes the twist: instead of using a conventional decryption key, a master secret key, msk, is created, known only by a central authority. When this authority receives the description of a function, f, it derives from msk, a functional decryption key, dk [f], associated with f. Anyone using dk[f] to decrypt the encrypted data, c, will instead get the result of applying the function f to the data in clear, f(m), but no additional information about m. That is, D(dk[f], c) = f(m). Conventional public key cryptography is a particular case of functional cryptography where f is the identity function: f(m) = m.
Applications of Functional Encryption
A multitude of use cases can be devised for functional encryption, anywhere encrypted data is required to be operated on, but not seen:
- Spam filtering: A user does not trust his mail provider but wants it to clean up his spam messages. The user can implement a functional encryption system: he encrypts all his messages with pk and provides the server with a functional decryption key, dk[f], where f is a spam filtering function that returns 1 if a message m is spam and 0 otherwise. The server will use dk[f] to check if an encrypted message is spam, but without obtaining any additional information about the message itself.
- Database searches: a cloud service stores billions of encrypted images. The police want to find all images containing a suspect’s face. The server provides a functional decryption key that decrypts the images containing the target face but does not reveal anything about other images.
- Big data analytics: Consider a hospital that records its patients’ medical data and wants to make it available to the scientific community for research purposes. The hospital can delegate the encrypted storage of its sensitive patient data to a public cloud. It can then generate functional decryption keys that it distributes to researchers, enabling them to calculate different statistical functions on the data, without ever revealing individual patient records.
- Machine Learning on encrypted data: after training a classifier on a clear dataset, a functional decryption key associated with this classifier can be generated and used to classify a set of encrypted data, so that in the end only the classification result is revealed, without filtering anything about the data in the set.
- Access control: In a large organisation you want to share data between users according to different access policies. Each user can encrypt x = (P, m), where m is the data the user wants to share, and P is the access policy that describes how the user wants to share it. The functional decryption key dk[f] will check if the user’s credentials or attributes match the policy and reveal m only if they do. For example, policy P = (“ACCOUNTING” OR “IT”) AND “MAIN BUILDING” would return m to an accounting department or an IT department with an office in the organisation’s main building.
Differences Compared to Fully Homomorphic Encryption (FHE)
If you are familiar with the concept of the fully homomorphic encryption (FHE), you may have thought of it when reading about functional encryption. The difference between the two is crucial: fully homomorphic encryption (FHE) performs operations on the encrypted data and the result is still encrypted. To access the result of the computation on the encrypted data, decryption is needed, which can be inconvenient in certain use cases. The following schematic representation will help to visualise the difference between the two encryption schemas.
In the case of fully homomorphic encryption (FHE), the function f is computed on the encrypted data and the result is encrypted:
E(m1), E(m2), …, E(mn) –> E(f(m1, m2, …, mn))
Whereas with functional encryption, the result is directly accessible after the calculation of f:
E(m1), E(m2), …, E(mn) –> f(m1, m2, …, mn)
Another important difference is that in the case of FHE, anyone can perform the calculations on the encrypted data, so given the encrypted text of the result, there is no guarantee that the calculations have been performed correctly. FHE requires the use of zero-knowledge proof to verify that the correct function was evaluated. On the other hand, in functional cryptography, only the holder of the functional decryption key can perform the calculations, which provides greater guarantees of correctness.
Functional Encryption Security
There is a wide variety of functional encryption schemas, based on different and very complex mathematical tricks. To simplify a lot, a functional encryption is considered secure if an adversary cannot obtain more information about m than f(m). Even if n parties in possession of the keys dk[f1], dk[f2], …, dk[fn], agree to attack m in a collusion attack, they will not obtain more information than f1(m), f2(m), …, fn(m). The level of information about m revealed is fully controlled by whoever generates the functional decryption keys.
Super-Vitaminised And Super-Mineralised Public Key Cryptography for A Future in The Cloud
Functional encryption is still a very young discipline, which is receiving strong research momentum for its endless applications in cloud services and IoT. A particularly interesting application enhanced by the European FENTEC project is the possibility of moving the decision-making process based on end-to-end encrypted data from back-end systems to some gateways in complex networks, which is called local decision-making. Being capable of enabling gateways to perform such local decision-making is a big step forward in securing IoT and other highly decentralised networks that might want to implement end-to-end encryption, without losing too much decision-making capabilities at the gateway level.
If you want to try functional cryptography, you can do so thanks to several libraries published by the researchers of the FENTEC project. You can go directly to Github and start playing with CiFEr, a C implementation, and GoFE, implemented in Go. You can even try it out in your browser using WASM.
Functional encryption represents a further step towards a more powerful and versatile cryptography, capable of protecting users’ privacy in use cases that were previously unthinkable with conventional cryptography.