https://blog.cryptographyengineering.com/2023/08/21/some-rough-impressions-of-worldcoin/

Recently a reader wrote in and asked if I would look at Sam Altman’s Worldcoin, presumably to give thoughts on it from a privacy perspective. This was honestly the last thing I wanted to do, since life is short and this seemed like an obvious waste of it. Of course a project devoted to literally scanning your eyeballs was up to some bad things, duh.

However: the request got me curious. Against my better judgement, I decided to spend a few hours poking around Worldcoin’s documentation and code — in the hope of rooting out the obvious technical red flags that would lead to the true Bond-villain explanation of the whole thing. Because surely there had to be one. I mean: eyeball scanners. Right?

This post is my attempt to look at Worldcoin’s system from a privacy-skeptical point of view in order to understand how risky this project actually is. The risks I’m concerned about are twofold: (1) unintentional risks to users that could arise due to carelessness on Worldcoin’s part, and (2) “intentional” risks that could result from future business decisions (whether they are currently planned or not.)

For those who don’t love long blog posts, let me save you a bunch of time: I did not find as many red flags as I expected to. Indeed, while I’m still (slightly) leaning towards the idea that Worldcoin is the public face of some kind of moon-laser-esque evil plan, my confidence in that conclusion is lower than it was going in. I still don’t precisely understand what the point of Worldcoin is, but at least I’m somewhat more confident that it isn’t an obvious privacy disaster (although there are still some concerns.) Read on for the rest.

What is Worldcoin and why should I care?

Worldcoin is a new cryptocurrency funded by Sam Altman and run by Alex Blania. According to the project’s marketing material, the goal of the project is to service the “global unbanked“, which it will do by somehow turning itself into a form of universal basic income. While this doesn’t seem like much of a business plan, it’s pretty standard fare for a cryptocurrency project. Relatively few of these projects have serious business models, and it’s pretty common for projects to engage in behavior that amounts to “giving things away for free in the hope that it will drive adoption.”

What sets Worldcoin apart from other projects is that the free money comes with a surprising condition: in order to join the Worldcoin system and collect free tokens, users must hand over their eyeballs.

Ok, that’s obviously a bit dramatic. More prosaically: the novel technical contribution of Worldcoin is a proprietary biometric sensor called “the orb”, which allows the system to uniquely identify users by scanning their iris, which not-coincidentally is one of the most entropy-rich biometric features that humans possess. Worldcoin uses these scans to produce a record that they refer to as a “proof of personhood”, a credential that will, according to the project, have many unspecified applications in the future.

Whatever the long term applications for this technology may be, the project’s immediate goal is to enroll hundreds of millions of eyeballs into their system, using the iris scan to make sure that no user can sign up twice. A number of people have expressed concern about the potential security and privacy risks of this plan. Even more critically, people are skeptical that Worldcoin might eventually misuse or exploit this vast biometric database it’s building. Worldcoin has arguably made themselves more vulnerable to criticism by failing to articulate a realistic-sounding business case for its technology (admittedly, something that is common to many cryptocurrency projects.) The project has instead argued that their biometric database either won’t or can’t be abused — due to various privacy-preserving features they’ve embedded into it.

Worldcoin’s claims

Worldcoin makes a few important claims about their system. First, they insist that the iris scan has exactly one purpose: to identify duplicate users at signup. In other words, they only use it to keep the same user from enrolling multiple times (and thus collecting duplicate rewards.) They have claimed — though not particularly consistently, see further below! — that your iris itself will not serve as any kind of backup “secret key” for accessing wallet funds or financial services.

This is a pretty important claim! A system that uses iris codes only to recognize duplicate users will expose its users to relatively few direct threats. A system that uses biometrics to authorize financial transactions is potentially much more dangerous for users. TL;DR if iris scans can be used to steal money, the whole system is quite risky.

Second, Worldcoin claims that it will not store raw images of your actual iris — unless you ask them to. They will only store a derived value called an “iris code”:

The final claim that Worldcoin makes is that they will not tie your biometric to a substantial amount of personal or financial data, which could make their database useful for tracking. They do this by making the provision of personally identifiable information (PII) “optional” rather than mandatory. And further, they use technology to make it impossible for the company to tie blockchain transactions back to your iris record:

There are obviously still some caveats in here: notably the claim that you “do not need” any personal information does leave room for people to ‘voluntarily’ provide it. This could be a problem in settings where unsupervised Worldcoin contractors are collecting data in relatively poor communities. But overall at least Worldcoin seems to be trying.

Worldcoin in a technical nutshell

Worldcoin operates two different technologies. The first is a standard EVM-based cryptocurrency token (ERC20), which operates on the “Layer 2” Optimism blockchain. The company can create tokens according to a limited “inflation supply” model and then give them away to people. Mostly this part of the project isn’t very interesting (although there are some novel aspects to Worldcoin’s on-chain protocol that impact privacy: I’ll discuss those further below.)

The novel element of Worldcoin is its biometric-based “proof of personhood” identity verification tech. Worldcoin’s site handwaves a lot about future applications of the technology, many of them involving “AI.” For the moment this technology is used for one purpose: to ensure that each Worldcoin user has registered only once for its public currency airdrop. This assurance allows Worldcoin to provide free tokens to registered users, without worrying that the same person will receive multiple rewards.

To be registered into the system, users visit a Worldcoin orb scanning location, where they must verify their humanity to a real-life human operator. The orb contains tamper-resistant hardware that can scan one or both of the user’s eyes, while also performing various tests to ensure that the eyeballs belong to a living, breathing human. This sensor takes high-resolution iris images, which are then then processed internally within the the orb using an algorithm selected by Worldcoin. The output of this process is a sort of “digest value” called an iris code.

Iris codes operate like a fuzzy “hash” of an iris: critically, one iris code can be compared to another code, such that if the “distance” between the pair is small enough, the two codes can be considered to derive from the same iris. That means the coding must be robust to small errors caused by the scanning process, and even to small age-related changes within the users’ eyes. In theory the use of iris codes tamper-resistant hardware should mean that your raw iris scans are safe — the orb never needs to output them, it can simply output this (hopefully) much less valuable iris code.

(In practice, however, this is not quite true: Worldcoin allows users to opt in to “data custody“, which means that their raw iris scans will also be stored by the project. Worldcoin claims that these images will be encrypted, though using a key that the project holds. This custody is promoted as a way to enable future updates to the iris coding algorithm, without forcing users to re-scan their eyes at an orb. It is not clear how many users have opted in to this custody.)

Once the orb has scanned a user, the iris code is uploaded to a server operated by the Altman/Blania company Tools for Humanity. The code may or may not be attached to other personal user information that Worldcoin collects, such as phone numbers and email addresses (Worldcoin’s documents are slightly vague on this point, except for noting that this data is “optional.”) The server now compares the new code against its library of previously-registered iris codes. If the new code is sufficiently “distant” from all previous codes, the system will consider this user to be a unique first-time registered user. (The documents are also slightly vague about what happens if they’re already registered, see much further below.)

To complete the enrollment process, users download Worldcoin’s wallet software to generate two different forms of credential:

1. A standard Ethereum wallet public and secret key, which is used to actually control funds in Worldcoin’s ERC20 contract.
2. A specialized digital commitment called an “identity credential”, which comes with its own matching secret key material.

Critically, none of this key material is derived from the user’s biometric scan. The (public) “identity commitment”, is uploaded to Tools for Humanity, where it is stored in the database along with the user’s iris code, while all of the secret key material is stored locally on the user’s phone. As a final step, Tools for Humanity exports the user’s identity commitment (but not the iris code data!) into a smart-contract-managed data structure that resides on Worldcoin’s blockchain.

Phew. Ok. Only one more thing.

As mentioned previously, the entire purpose of this iris scanning business is to allow users to perform assertions on their blockchain that “prove” they are unique human beings: the most obvious one being a request for airdropped tokens.

A very real concern with these assertions is that Worldcoin (aka Tools for Humanity) could monitor these on-chain transactions, and thus link the user’s wallet back to the unique biometric record it is associated with. This would instantly create a valuable source of linked biometric and financial data, which is one of the most obvious concerns about this type of system.

To their credit: Worldcoin seems to recognize that this is a problem. And their protocols address those concerns in two ways. First: they do not upload the user’s Ethereum wallet address to Tools for Humanity’s servers. This means that any financial transactions a user makes should not be trivially linkable to the user’s biometric credentials. (This obviously doesn’t make linkage impossible: transactions could be linked back to a user via public blockchain analysis at some later point.) But Worldcoin does try to avoid the obvious pitfall here.

This solves half the problem. However, to enable airdrops to a user’s wallet, Worldcoin must at some point link the user’s identity commitment to their wallet address. Implemented naively, this would seem to require a public blockchain transaction that would link a wallet address to an identity commitment — and hence (via the Tools for Humanity server) to the user’s biometric iris code. This would be quite bad!

Worldcoin avoids this issue in a clever way: their blockchain uses zero knowledge proofs to authorize the airdrop. Concretely, once an identity commitment has been placed on chain, the user can use their wallet to produce a privacy-preserving transaction that “proves” the following statement: “I know the secret key corresponding to a valid identity commitment on the chain, and I have not previously made a proof based on this commitment.” Most critically, this proof does not reveal which commitment the user is referencing. These protections make it relatively difficult for any outside party (including Tools for Humanity) to link this transaction back to a user’s identity and iris code.

Worldcoin conducts these transactions using a zero-knowledge proof system called Semaphore (developed by the Ethereum project, using an architecture quite similar to Zcash.) Although there are a fabulous number of different ways this could all go wrong in practice (more on this below), from an architectural perspective Worldcoin’s approach seems really nice. Critically, it should serve to prevent on-chain airdrop transactions from being directly linked to the biometric identifiers that Tools for Humanity records.

To summarize all of the above… if Worldcoin works as advertised, the following should be true after you’ve registered and used the system:

1. Tools for Humanity will have a copy of your iris code stored in its database.
2. Tools for Humanity may also have stored a copy of your raw iris scans, assuming you “opted in” to data custody. (This data will be encrypted under a key TfH knows.)
3. Tools for Humanity will store the mapping between each iris code and the corresponding “identity commitment”, which is essentially the public component of your ID credential.
4. Tools for Humanity may have bound the iris code to other PII they optionally collected, such as phone numbers and email addresses.
5. Tools for Humanity (and Worldcoin) should not know your wallet address.
6. All of your secret keys will be stored in your phone, and will not be backed up anywhere else.
7. If you conduct any transactions on the blockchain that reference the identity commitment, neither Worldcoin or TfH should be able to link these to your identity.
8. Finally (and critically): no biometric information (or biometric-derived information) will be sent to the blockchain or stored on your phone.

As you can see, this system appears to avoid some of the more obvious pitfalls of a biometric-based blockchain system: crucially, it does not upload raw biometric information to a volunteer-run blockchain. Moreover, iris scans are not used to derive key material or to enable spending of cryptocurrency (though more on this below.) The amount of data linked to your biometric credential is relatively minimal, and transactions on chain are not easily linked back to the credential.

This architecture rules out many threats that might lead to your eyeballs being stolen or otherwise needing to be replaced.

What about future uses of iris data?

As I mentioned earlier, a system that only uses iris codes to recognize duplicate users poses relatively few threats to users themselves. By contrast, a system that uses biometrics to authorize financial transactions could potentially be much more risky. To abuse a cliché: if iris scans can be used to steal money, then users might need to sleep with their eyes open closed.

While it seems that Worldcoin’s current architecture does not authorize transactions using biometric data, this does not mean the platform will behave this way forever. The existence of a biometric database could potentially create a kind of gravity that forces the company to put it to more dangerous use.

Let me be more specific.

The most famous UX problem in cryptocurrency is that cryptocurrency’s “defining” feature — self-custody of funds — is incredibly difficult to use. Users constantly lose their wallet secret keys, and with them access to all of their funds. This problem is endemic even with sophisticated first-world cryptocurrency adopters who have access to bank safety-deposit boxes and dedicated hardware wallets. It is obviously going to be an even more serious problem for a cryptocurrency that purports to be the global “universal basic income” for billions of people.

If Worldcoin is successful by its own standards — i.e., it becomes a billion-user cryptocurrency — it’s going to have to deal with the fact that many users are going to lose their wallet secrets. Those folks will want to re-authorize themselves to get those funds back. Unlike most cryptocurrencies, Worldcoin has the ultimate tool to make that possible:

At present the company cannot use biometrics to regain access to lose wallets, but they have many of the tools they need to get there. Concretely:

1. In principle, Tools for Humanity’s servers can re-bind an existing iris code to a new identity commitment. They can then send that new commitment to the chain using a special call in the smart contract.
2. While this could allow users to obtain a second airdrop (if Worldcoin/TfH choose to allow it), it would not (at present) allow a user to take control of an existing wallet.

Well wallet recovery is not enabled today, this could easily be changed in the future. It would require the project to either replace its ERC20 contract, or — more practically — to deploy a new form of smart contract wallet that allows users to “reset” ownership via an identity assertion. Worldcoin hasn’t done this, but it’s hard to see how they will withstand the pressure in the long term. (And see the white paper above.)

Another obvious concern is that Tools for Humanity could use its biometric database as a kind of “stone soup” to build a future (and more privacy-invasive) biometric database, which could then be deployed for applications that have nothing to do with cryptocurrency. For example, an obvious application would be to record and authorize credit for customers who lack government-issued ID. This is the kind of thing I can see Silicon Valley VC investors getting very excited over.

There is nothing, in principle, stopping the project from pivoting in this direction in the future. On the other hand, a reasonable counterpoint is that if Worldcoin really wanted to do this, they could just have done it from the get-go: enrolling lots of people into some weird privacy-friendly cryptocurrency seems like a bit of a distraction. But perhaps I am not being imaginative enough.

A related concern is that Worldcoin might somehow layer further PII onto their existing database, or find other ways to make this data more valuable — even if the on-chain data is unlinkable. Some reports indicate that Worldcoin employees do collect phone numbers and other personally-identifying information as part of the enrollment process. It’s really not clear why Worldcoin would collect this data if it doesn’t plan to use it somehow in the future.

As a final matter, there is a very real possibility that Worldcoin somehow has the best intentions — and yet will just screw up. Databases can be stolen. Zero-knowledge proofs are famously difficult to get right, and even small vulnerabilities can create a privacy leak. Worldcoin’s system almost certainly deploys various back-end servers to assist with proof generation (e.g., to obtain Merkle paths) and the logs of these servers could further undermine privacy. This will only get worse as Worldcoin proceeds to “decentralize” the World ID database, whatever that entails.

Conclusion

I came into this post with a great deal of skepticism about Worldcoin: I was 100% convinced that the project was an excuse to bootstrap a valuable biometric database that would be used e-commerce applications, and that Worldcoin would have built their system to maximize the opportunities for data collection.

After poking around the project a bit, I’m honestly still a little bit skeptical. I think Worldcoin is — at some level — an excuse to bootstrap a valuable biometric database for e-commerce applications. But I would say my confidence level is down to about 40%. And more critically, I’m pleasantly surprised by the amount of thought that Worldcoin has put into keep transaction data unlinked from its ID database.

No doubt there are still things that I’ve missed here, and perhaps others will chime in with some details and corrections. In the meantime, I still would not personally stick my eyeballs into the orb, but I can’t quite tell you how it would hurt.

https://blog.cryptographyengineering.com/2023/05/11/on-ashton-kutcher-and-secure-multi-party-computation/

Back in March I was fortunate to spend several days visiting Brussels, where I had a chance to attend a panel on “chat control“: the new content scanning regime being considered by the EU Commission. Among various requirements, this proposed legislation mandate that client-side scanning technology be incorporated into encrypted text messaging applications like Signal, WhatsApp and Apple’s iMessage. The scanning tech would examine private messages for certain types of illicit content, including child sexual abuse media (known as CSAM), along with a broad category of textual conversations that constitute “grooming behavior.”

I have many thoughts about the safety of the EU proposal, and you can read some of them here. (Or you’re interested in the policy itself, you can read this recent opinion by the EU’s Council’s Legal Service.) But although the EU proposal is the inspiration for today’s post, it’s not precisely what I want to talk about. Instead, I’d like to clear up some confusion I’ve noticed around the specific technologies that many have proposed to use for building these systems.

Also: I want to talk about Ashton Kutcher.

It turns out there were a few people visiting Brussels to talk about encryption this March. Only a few days before my own visit, Ashton Kutcher gave a major speech to EU Parliament members in support of the Commission’s content scanning proposal. (And yes, I’m talking about that Ashton Kutcher, the guy who played Steve Jobs and is also married to Mila Kunis.)

As unusual as this may sound, Kutcher has been very active in the technical debate around client-side scanning. He’s the co-founder of an organization called Thorn, which aims to develop cryptographic technology to enable CSAM scanning. In March he gave an impassioned speech to the EU Parliament urging the deployment of these technologies, and remarkably he didn’t just talk about the policy side of things. When asked how to balance user privacy against the needs of scanning, he even made a concrete technical proposal: to use fully-homomorphic encryption (FHE) as a means to evaluate encrypted messages.

Now let me take a breath here before my head explodes.

I promise I am not one of those researchers who believes only subject-matter experts should talk about cryptography. Really I’m not! I write this blog because I think cryptography is amazing and I want everyone talking about it all the time. Seeing mainstream celebrities toss around phrases like “homomorphic encryption” is literally a dream come true and I wish it happened every single day.

And yet, there are downsides to this as well.

I saw some of those last week. Terms like fully homomorphic encryption can be confusing and off-putting to nontechnical policymakers. When filtered through people who are not themselves experts in the technology, these ideas can produce the impression that crypto is magical pixie dust we can sprinkle on all the hard problems in the world. And oh how I wish that were true. But in the real world, cryptography is hard. Solving one problem often just makes new problems, or creates major new costs, or else shifts the risks and costs to other parts of the system.

So when people on various sides of the debate asked me whether fully-homomorphic encryption could really do what Kutcher said it would, I couldn’t give an easy five-word answer. The real answer is something like: (scream emoji) it’s very complicated. That’s a very unsatisfying thing to have to tell people. Out here in the real world the technical reality is eye-glazing and full of dragons.

Which brings me to this post.

What Kutcher is really proposing is that we to develop systems that perform privacy-preserving computation on encrypted data. He wants to use these systems to enable “private” scanning of your text messages and media attachments, with the promise that these systems will only detect the “bad” content while keeping your legitimate private data safe. This is a complicated and fraught area of computer science. In what goes below, I am going to discuss at a high and relatively non-technical level the concepts behind it: what we can do, what we can’t do, and how practical it all is.

In the process I’ll discuss the two most powerful techniques that we have developed to accomplish this task: namely, multi-party computation (MPC) and as an ingredient towards achieving the former) fully-homomorphic encryption (FHE). Then I’ll try to clear up the relationship between these two things, and explain the various tradeoffs that can make one better than the other for specific applications. Although these techniques can be used for so many things, throughout this post I’m going to focus on the specific application being considered in the EU: the use of privacy-preserving computation to conduct content scanning.

This post will not require any mathematics or much computer science, but it will require some patience. So find a comfortable chair and buckle in.

Computing on private data

Encryption is an ancient technology. Roughly speaking, it provides the ability to convert meaningful messages (and data) into a form that only you, and your intended recipient(s) can read. In the modern world this is done using public algorithms that everyone can look at, combined with secret keys that are held only by the intended recipients.

Modern encryption is really quite excellent. So as long as keys are kept safe, encrypted data can be sent over insecure networks or stored in risky locations like your phone. And while occasionally people find a flaw in an implementation of encryption, the underlying technology works very well.

But sometimes encryption can get in the way. The problem with encrypted data is that it’s, well, encrypted. When stored in this form, such data is virtually useless for practical purposes like performing calculations. Before you can compute on that data, you often need to first decrypt it and thus remove all the beautiful protections we get from encryption.

If your goal is to compute on multiple pieces of data that originate from different parties, the problem can become even more challenging. Who can we trust to do the computing? An obvious solution is to decrypt all that data and hand it to one very trustworthy person, who will presumably swear not to steal it or get hacked. Finding those parties can be quite challenging.

Fortunately for us all, the first academic cryptographers also happened to be computer scientists, and so this was exactly the sort of problem that excited them. Those researchers quickly devised a set of specific and general techniques designed to solve these problems, and also came up with a cool name for them: secure multi-party computation, or MPC for short.

MPC: secure private computation (in six eight ten paragraphs)

The setting of MPC is fairly simple: imagine that we have two (or more!) parties that each have some private data they don’t want to give to anyone else. Yet each of the parties is willing to provide their data as input to some specific computation, and are all willing to reveal the output of that computation — either to everyone involved, or perhaps just to some agreed subset of the parties.

Let’s make this easier by using a concrete example.

Imagine a group of workers all know their own salaries, but don’t know anything about anyone else’s salary. Yet they wish to compute some statistics over their salary data: for example, the average of their salaries. These workers aren’t willing to share their own salary data with anyone else, but they are willing to submit it as one input in a large calculation under the strict condition that only the final result is ever revealed.

This might seem contrived to you, but it is in fact a real problem that some people have used MPC to solve.

An MPC protocol allows the workers to do this, without appointing a trusted central party or revealing their inputs (and intermediate calculations) to anyone else. At the conclusion of the protocol each party will learn only the result of the calculation:

MPC protocols typically provide strong provable guarantees about their properties. The details vary, but typically speaking: no party will learn anything about the other parties’ inputs. Indeed they won’t even learn any partial information that might be produced during the calculation. Even better, all parties can be assured that the result will be correct: as long as all parties submit valid inputs to the computation, none of them should be able to force the calculation to go awry.

Now obviously there are caveats.

In practice, using MPC is a bit like making a deal with a genie: you need to pay very careful attention to the fine print. Even when the cryptography works perfectly, this does not mean that computing your function is actually “safe.” In fact, it’s entirely possible to choose functions that when computed securely are still devastating to your privacy.

For example: imagine that I use an MPC protocol to compute an average salary between myself and exactly one other worker. This could be a very bad idea! Note that if the other worker is curious, then she can figure out how much I make. That is: the average of our two wages reveals enough information that she find my wage given knowledge of her own input. This (obvious) caveat applies to many other uses of MPC, even when the technology works perfectly.

This is not a criticism of MPC, just the observation that it’s a tool. In practice, MPC (or any other cryptographic technology) is not a privacy solution by itself, at least not in the sense of privacy that real-world human beings like to think about. It provides certain guarantees that may or may not be useful for providing privacy in the real world.

What does MPC have to do with client-side scanning?

We began this post by discussing client-side scanning for encrypted messaging apps. This is a perfect example of an application that fits the MPC (or two-party computation) use-case perfectly. That’s because in this setting we generally have multiple parties with secret data who want to perform some joint calculation on their inputs.

In this setting, the first party is typically a client (usually a person using an encrypted messaging app like WhatsApp or Signal), who possesses some private text message or perhaps a media file they wish to send to another user. Under proposed law in the EU, their app could be legally mandated to “scan” that image to see if it contains illegal content.

According to the EU Commission, this scanning can be done in a variety of ways. For example, the device could compare an images against a secret database of known illicit content (typically using a specialized perceptual hash function.) However, while the EU plan starts there, their plans also get much more ambitious: they also intend to look for textual conversations, possibly using machine learning (ML) models, that is, deep neural networks that will be trained to recognize illicit content. These models must be sophisticated enough to understand entirely new images, as well as to derive meaning from complex interactive human conversation. None of this is likely to be very simple.

Now most of this could be done using standard techniques on the client device, except for one major limitation. The challenge in this setting is that the provider doing the scanning usually wants to keep these hashes and/or models secret.

There are several reasons for this. The first reason is that knowledge of the scanning model (or database of illicit content) makes it relatively easy for bad actors to evade the model. In other words, with only modest transformations it’s possible to modify “bad” images so that they become invisible to ML scanners.

Knowledge of the model can also allow for the creation of “poisoned” imagery: these include apparently-benign images (e.g., a picture of a cat) that trigger false positives in the scanner. (Indeed this such “colliding” images have been developed for some hash-based CSAM scanning proposals.) More worryingly, in some cases the hashes and neural network models can be “reversed” to extract the imagery and textual content they were trained on: this has all kinds of horrifying implications, and could expose abuse victims to even more trauma.

So here the user doesn’t want to send its confidential data to the provider for scanning, and the provider doesn’t want to hand its confidential model parameters to the user (or even to expose them inside the user’s phone, where they might be stolen by reverse-engineers.) This is exactly the situation that MPC was designed to handle:

This makes everything very complicated. In fact, there has only been one real-world proposal for client-side CSAM scanning that has ever come (somewhat) close to deployment: that system was designed by Apple for a (now abandoned) client-side photo scanning plan. The Apple approach is cryptographically very ambitious: it uses neural-network based perceptual hashing, and otherwise exactly follows the architecture described above.

(If you’re interested in getting a sense of how complex this protocol is, here is a white paper describing how it works.)

Ok, so what kind of MPC protocols are available to us?

Multi-party computation is a broad category. It describes a class of protocols. In practice there are many different cryptographic techniques that allow us to realize it. Some of these (like the Apple protocol) were designed for specific applications, while others are capable of performing general-purpose computation.

I promised this post would not go into the weeds, but it’s worth pointing out that general MPC techniques typically make use of (some combination of) three different techniques: secret sharing, circuit garbling, and homomorphic encryption. Often, efficient modern systems will use a mixture of two or three of those techniques, just to make everything more confusing because they’re to maximize efficiency.

What is it that you need to know about these techniques? Here I’ll try, in a matter of a few sentences (that will draw me endless grief) to try to summarize the strengths and disadvantages of each technique.

Both secret sharing and garbling techniques share a common feature, which is that they require a great deal of data to be sent between the parties. In practice the amount of data sent between the parties will grow with (at least) the size of the inputs they’re computing on, but often will grow according to the complexity of the calculation they’re performing. For things like deep neural networks where both the data and calculation are huge, this generally results in fairly surprising amounts of data transfer.

This is generally not a problem on the general Internet, where data transfer is cheap. It can be quite a challenge when one of those parties is using a cellphone, however. That makes any scheme using these technologies subject to some very serious limitations.

Homomorphic encryption schemes take a different approach. These systems make use of specialized encryption schemes that are malleable. This means that encrypted data can be “modified” in useful ways without every decrypting it.

In a bit more detail: in these systems, a first party can encrypt its data under a public key that it generates. It can then send the encrypted data to a second party. This second party can then perform calculations on the ciphertext while it is still encrypted — adding and multiplying it together with other data (including data encrypted by the second party) to perform some calculation. Throughout this process all of the data remains encrypted. At the conclusion of this process, the second party will end up with a “modified” ciphertext that internally contains a final calculation result. To finish the transaction, the second party can send that ciphertext back to the first party, who can then decrypt it and obtain the output.

The major upshot of the pure-FHE technique is that it substantially reduces the amount of data that the two parties’ need to transmit between them, especially compared to the other MPC techniques. The downside of this approach is, well, there are several. One is that FHE calculations typically require vastly more computational effort (and hence time and carbon emissions) than the other techniques. Moreover, they may still require a great deal of data transfer — in part because the number of calculations that one can do on a given ciphertext is quite limited (and hence, calculations must either be simple or broken up into “phases”.)

In practice, cryptographers rarely commit to a single approach. They instead combine all these techniques in order to achieve an appropriate balance of data-transfer and computational effort. These “mixed systems” tend to have merely large amounts of data transfer and large amounts of computation, but are still amazingly efficient compared to the alternatives.

For an example of this, consider this very optimized two-party MPC scheme aimed at performing neural network classification. This scheme takes (from the client) a 32×32 image, and evaluates a tiny 7-layer neural network held by a server in order to perform classification. As you can see, evaluating the model even on a single image requires about 8 seconds of computation and 200 megabytes of bandwidth exchange, for each image being evaluated:

These numbers may seem quite high, but in fact they’re excellent. Previous systems used nearly an order of magnitude more time and bandwidth to do their work. Maybe there will be further improvements in the future! Even on a pure efficiency basis there is much work to be done.

What are the other risks of MPC in this setting?

The final point I would like to make is that secure MPC (or MPC built using FHE as a tool) is not itself enough to satisfy the requirements of a safe content scanning system. As I mentioned above, MPC systems merely evaluate some function on private data. The question of whether that function is safe is left largely to the system designer.

In the case of these content scanning systems, the safety of the resulting system really comes down to a question of whether the algorithms work well, particularly in settings where “bad guys” can find adversarial inputs that try to disrupt the system. It also requires new techniques to ensure that the system cannot be abused. That is: there must be guarantees within the computation to ensure that the provider (or a party who hacks the provider) cannot change the model parameters to allow them to access your private content.

This is a much longer conversation than I want to have in this post, because it fundamentally requires one to think about whether the entire system makes sense. For a much longer discussion on the risks, see this paper.

This was nice, but I would like to learn more about each of these technologies!

The purpose of this post was just to give the briefest explanation of the techniques that exist for performing all of these calculations. If you’re interested in knowing (a lot more!) about these technologies, take a look at this textbook by Evans, Kolesnikov and Rosulek. MPC is an exciting area, and one that is advancing every single (research) conference cycle.

https://blog.cryptographyengineering.com/2023/05/08/prfs-prps-and-other-fantastic-things/

A few weeks ago I ran into a conversation on Twitter about the weaknesses of applied cryptography textbooks, and how they tend to spend way too much time lecturing people about Feistel networks and the boring details of AES. Some of the folks in this conversation suggested that instead of these things, we should be digging into more fundamental topics like “what is a pseudorandom function.” (I’d link to the thread itself, but today’s Twitter is basically a forgetting machine.)

This particular point struck a chord with me. While I don’t grant the premise that Feistel networks are useless, it is true that pseudorandom functions, also known as PRFs, are awfully fundamental. Moreover: these are concepts that get way too little coverage in (non-theory) texts. Since that seems bad for aspiring practitioners, I figured I’d spend a little time trying to explain these concepts in an intuitive way — in the hopes that I can bring the useful parts to folks who aren’t being exposed to these ideas directly.

This is going to be a high-level post and hence it will skip all the useful formalism. It’s also a little wonky, so feel free to skip it if you don’t really care. Also: since I need to be contrary: I’m going to talk about Feistel networks anyway. That bit will come later.

What’s a PRF, and why should I care?

Pseudorandom functions (PRFs) and pseudorandom permutations (PRPs) are two of the most fundamental primitives in modern cryptography. If you’ve ever implemented any cryptography yourself, there’s an excellent chance you relied on an algorithm like AES, HMAC or ChaCha20 to implement either encryption or authentication. If you did this, then you probably relied on some security property you assumed those primitives to have. But what precisely is that security property you’re relying on?

We could re-imagine this security definition from scratch every time we look at a new cipher. Alternatively, we could start from a much smaller number of general mathematical objects that provide security properties that we can reason about, and try to compare those to the algorithms we actually use. The second approach has a major advantage: it’s very modular. That is, rather than re-design every single protocol each time we come up it with a new type of cipher, all we really need to do is to analyze it with the idealized mathematical objects. Then we can realize it using actual ciphers, which hopefully satisfy these well-known properties.

Two of the most common such objects are the pseudorandom function (PRF) and the pseudorandom permutation (PRP). At the highest level, these functions have two critical properties that are extremely important to cryptographers:

1. They are keyed functions: this means that they take in a secret key as well as some input value. (This distinguishes them from some hash functions.)
2. The output of a PRF (or PRP), when evaluated on some unique input, typically appears “random.” (But explaining this rough intuition precisely will require some finesse, see below.)

If a function actually can truly achieve those properties, we can use it to accomplish a variety of useful tasks. At the barest minimum, these properties let us accomplish message authentication (by building MACs), symmetric encryption by building stream ciphers, and key derivation (or “pluralization”) in which a single key is turned into many distinct keys. We can also use PRFs and PRPs to build other, more fundamental primitives such as pseudorandom number generators and modes of operation, which happen to be useful when encrypting things with block ciphers.

The how and why is a little complex, and that’s the part that will require all the explanation.

Random functions

There are many ideal primitives we’d love to be able to use in cryptography, but are thwarted from using due to the fact that they’re inefficient. One of the most useful of these is the random function.

Computer programmers tend to get confused about functions. This is mostly because programming language designers have convinced us that functions are the same thing as the subroutines (algorithms) that we use to compute them. In the purely mathematical sense, it’s much more useful to forget about algorithms, and instead think of functions as simply being a mapping from some set of input values (the domain) to some set of output values (the range).

If we must think about implementing functions, then for any function with a finite domain and range, there is always a simple way to implement it: simply draw up a giant (and yet still finite!) lookup table that contains the mapping from each input to the appropriate output value. Given such a table, you can always quickly realize an algorithm for evaluating it, simply by hard-coding the table into your software and performing a table lookup. (We obviously try not to do this when implementing software — indeed, most of applied computer science can be summarized as “finding ways to avoid using giant lookup tables”.)

A nice thing about the lookup table description of functions is that it helps us reason about concepts like the number of possible functions that can exist for a specific domain and range. Concretely: if a function has M distinct input values and N outputs, then the number of distinct functions sharing that profile is . This probably won’t scale very well for even modest values of M and N, but let’s put this aside for a moment. Given enough paper, we could imagine writing down each unique lookup table on a piece of paper: then we could stack those papers up and admire the minor ecological disaster we’d have just created.

Now let’s take this thought-experiment one step farther: imagine that we could walk out among those huge stacks of paper we’ll have just created, and somehow pick one of these unique lookup tables uniformly at random. If we could perform this trick routinely, the result would be a true “random function”, and it would make an excellent primitive to use for cryptography. We could use these random functions to build hash functions, stream ciphers and all sorts of other things that would make our lives much easier.

There are some problems with this thought experiment, however.

A big problem is that, for functions with non-trivial domain and range, there just isn’t enough paper in the world to enumerate every possible function. Even toy examples fall apart quickly. Consider a tiny hash function that takes in (and outputs) only 4-bit strings. This gives us M=16 inputs and N=16 outputs, and hence number of (distinct) mappings is $, or about 18 quintillion. It gets worse if you think about “useful” cryptographic functions, say those with the input/output profile of ChaCha20, which has 128-bit inputs and 512-bit outputs. There you’d need a whopping (giant) pieces of paper. Since there are only around atoms in the observable universe (according to literally the first Google search I ran on the topic), we would quickly run into shortages even if we were somehow able to inscribe each table onto a single atom.

Obviously this version of the thought experiment is pretty silly. After all: why bother to enumerate every possible function if we’re going to throw most of them away? It would be much more efficient if we could sample a single random function directly without all the overhead.

This also turns out to be fairly straightforward: we can write down a single lookup table with M rows (corresponding to all possible inputs); for each row, we can sample a random output from the set of N possible outputs. The resulting table will be M rows long and each row will contain bits of data.

While this seems like a huge improvement over the previous approach, it’s still not entirely kosher. Even a single lookup table is still going to huge — at least as large as the function’s entire domain. For example: if we wanted to sample a random function with the input/output profile of ChaCha20, the table would require enough paper to contain bits.

And no, we are not going to be able to compress this table! It should be obvious now that a random function generated this way is basically just a file full of random data. Since it has maximal entropy, compression simply won’t work.

The fact that random functions aren’t efficient for doing cryptography does not always stop cryptographers from pretending that we might use them, most famously as a way to model cryptographic hash functions in our security proofs. We have an entire paradigm called the random oracle model that makes exactly this assumption. Unfortunately, in reality we can’t actually use random functions to implement cryptographic functions — sampling them, evaluating them and distributing their code are all fundamentally infeasible operations. Instead we “instantiate” our schemes with an efficient hash algorithm like SHA3, and then we pray.

However, there is one important caveat. While we generally cannot sample and share large random functions in practice, we hope we can do something almost as interesting. That is, we can build functions that appear to be random: and we can do this in a very powerful cryptographic sense.

Pseudorandom functions

Random functions represent a single function drawn from a family of functions, namely the family that consists of every possible function that has the appropriate domain and range. As noted above, the cost of this decision is that such functions cannot be sampled, evaluated or distributed efficiently.

Pseudorandom functions share a similar story to random functions. That is, they represent a single function sampled from a family. What’s different in this case is that the pseudorandom function family is vastly smaller. A benefit of this tradeoff is that we can demand that the description of the function (and its family) be compact: pseudorandom function families must possess a relatively short description, and it must be possible to both sample and evaluate them efficiently: meaning, in polynomial time.

Compared to the set of all possible functions over a given domain and range, a pseudorandom function family is positively tiny. Let’s stick with the example of ChaCha20: as previously discussed, ChaCha has a 128-bit input, but it also takes in a 256-bit secret key. If we were to view ChaCha20 as a pseudorandom function family, then we could view it as a family of (likely) distinct functions, where each individual key value selects exactly one function from the family.

Now let’s be clear: is still a really big number! However: it is vastly smaller than , which is the total number of possible functions with ChaCha20’s input profile. Sampling a random 256-bit key and sharing it with to Bob is eminently feasible; indeed, your browser did something like this when you loaded this website. Sampling a “key” of bit-length is not.

This leaves us with an important question, however. Since ChaCha20’s key is vastly smaller than the description of a random function, and the algorithmic description of ChaCha20 is also much smaller than the description of even a single random function, is it possible for small-key function family like “ChaCha20” to be as good (for cryptographic purposes) as a true random function? And what does “good” even mean here?

And here is where we arrive at the importance of the term pseudorandom. Mirriam-Webster defines the prefix pseudo as “being apparently rather than actually as stated.” The Urban Dictionary is more colorful: it defines pseudo as “false; not real; fake replication; bootleg; tomfoolery“, and also strongly hints that pseudo may be shorthand for pseudoephedrine (note: it is not.)

Clearly if we can describe a function using a compact algorithmic description and a compact key, then it cannot be a true random function: it is therefore bootleg. However that doesn’t mean it’s entirely tomfoolery. What pseudorandom means, in a cryptographic sense, is that a function of this form will be indistinguishable from a truly random function — at least to an adversary who does not know which function we have chosen from the family, and who has a limited amount of computing power.

Let’s unpack this definition a bit!

Imagine that I create a black box that contains one of two possible items, chosen with equal probability. Item (1) is an instance of a single function sampled at random from a purported pseudorandom function family; item (2) is a true random function sampled from the set of all possible functions. Both functions have exactly the same input/output profile, meaning they take in inputs of the same length, and produce outputs of the same length (here we are excluding the key.)

Now imagine that I give you “oracle” access to this box. What this means is: you will be allowed to submit any input values you want, and the box will evaluate your input using whichever function it contains. You will only see the output. You can submit as many inputs as you want, using any strategy for choosing them that you desire: they simply have to be valid inputs, meaning that they’re within the domain of the function. We will further stipulate that you wil be computationally limited: that means you will only be able to compute for a limited (polynomial in the input/output size) number of timesteps. At the end of the day, your goal is to guess which type of function I’ve placed in the box.

We say that a family of functions is pseudorandom if for every possible efficient strategy (meaning, using any algorithm that runs in time polynomial in the key size), the “advantage” you will have in guessing what’s in the box is very tiny (at most negligible in, say, the size of the function’s key.)

A fundamental requirement of this definition is that the PRF’s key/seed (aka the selector that chooses which function to use) has to remain secret from the adversary. This is because the description of the PRF family is not secret (indeed, “all possible algorithms” necessarily has to include strategies that know this description, even if we don’t say this explicitly.) And pseudorandom functions cannot possibly be indistinguishable from random ones if the attacker can learn or guess the PRF’s secret key: this would allow the adversary to simply compute the function themselves and compare the results they get to the values that come out of the oracle (thus winning the experiment nearly 100% of the time.)

There’s a corollary to this observation: since the key length of the PRF is relatively short, the pseudorandomness guarantee can only be computational in nature. For example, imagine the key is 256 bits long: an attacker with unlimited computational resources could brute-force guess its way through all possible 256-bit keys and test each one against the results coming from the oracle. If the box truly contains a PRF, then with high probability she’ll eventually find a key that produces the same results as what comes out of the box; if the box contains a random function, then she probably won’t. To rule such attacks out of bounds we must assume that the adversary is not powerful enough to test a large fraction of the keyspace. (In practice this requirement is pretty reasonable, since brute forcing through an n-bit keyspace requires on the order of work, and we assume that there exist reasonable values of n for which no computing device exists that can succeed at this.)

So what can we do with pseudorandom functions?

As I mentioned above, pseudorandom functions are extremely useful for a number of basic cryptographic purposes. Let’s give a handful here.

Building stream ciphers. One of the simplest applications of a PRF is to use it to build an efficient stream cipher. Indeed, this is exactly what the ChaCha20 function is typically used for. Let us assume for the moment that ChaCha20 is a PRF family (I’ll come back to this assumption later.) Then we could select a random key and evaluate the function on a series of unique input values — the ChaCha20 documentation proposes to concatenate a 64-bit block number with a counter — and then concatenate the outputs of the function together to produce a keystream of bits. To encrypt a message we would simply exclusive-OR (XOR) this string of bits (called a “keystream”) with the message to be enciphered.

Why is this reasonable? The argument breaks down into three steps:

1. If we had generated the keystream using a perfect random number generator (and kept it secret, and never re-used the keystream) then the result would be a one-time pad, which is known to be perfectly secure.
2. And indeed, had we had been computing this output using a truly random function where each input was used exactly once, the result of this evaluation would indeed have been such a random string.
3. Of course we didn’t do this: we used a PRF. But here we can rely on the fact that our attackers cannot distinguish PRF output from that of a random function.

One can make the last argument the other way around, too. If our attacker is much better at “breaking” the stream cipher implemented with a PRF than they are at breaking one implemented with a random function, then they are implicitly “distinguishing” the two types of function with a substantial advantage — and this is precisely what the definition of a PRF says that an attacker cannot do!

Constructing MACs. A PRF with a sufficiently large range can also be used as a Message Authentication Code. Given a message M, the output of PRF(k, M) — the PRF evaluated on a secret key k and the message M — should itself be indistinguishable from the output of a random function. Since this output will effectively be a random string, this means that an attacker who has not previously seen a MAC on M should have a hard time guessing the appropriate MAC for a given message. (The “strength” of the MAC will be proportional to the output length of the PRF.)

Key derivation. Often in cryptography we have a single random key k and we need to turn this into several random-looking keys (k1, k2, etc.) This happens within protocols like TLS, which (at least in version 1.3) has an entire tree of keys that it derives from a single master secret. PRFs, it turns out, are an excellent for this task. To “diversify” a single key into multiple keys, one can simply evaluate the PRF at a series of distinct points (say, k1 = PRF(k, 1), k2 = PRF(k, 2), and so on), and the result is a set of keys that are indistinguishable from random; provided that the PRF does what it says it does.

There are, of course, many other applications for PRFs; but these are some pretty important ones.

Pseudorandom permutations

Up until now we’ve talked about pseudorandom functions (PRFs): these are functions that have output that is indistinguishable from a random function. A related concept is that of the pseudorandom permutation (PRP). Pseudorandom permutations share many of the essential properties of PRFs, with one crucial difference: these functions realize a permutation of their input space. That is: if we concentrate on a given function in the family (or, translating to practical terms, we fix one “key”) then each distinct input maps to a distinct output (and vice versa.)

A nice feature of permutations is that they are potentially invertible, which makes them a useful model for something we use very often in cryptography: block ciphers. These ciphers take in a key and a plaintext string, and output a ciphertext of the same length as the plaintext. Most critically, this ciphertext can be deciphered back to the original plaintext. Note that a standard (pseudo)random function doesn’t necessarily allow this: for example, a PRF instance F can map multiple inputs (A, B) such that F(A) = F(B), which makes it very hard to uniquely invert either output.

The definition of a pseudorandom permutation is very similar to that of a PRF: they must be indistinguishable from some idealized function — only in this case the ideal object is a random permutation. A random permutation is simply a function sampled uniformly from the set of all possible permutations over the domain and range. (Because really, why wouldn’t it be?)

There are two important mathematical features of PRPs that I should mention here:

PRPs are actually PRFs (to an extent.) A well-known result in cryptography, called the “PRP/PRF switching lemma” demonstrates that a PRP basically “is” a PRF. Put differently: a pseudorandom permutation placed into an oracle can be computationally indistinguishable from an oracle that contains a pseudorandom function (with the same domain and range), provided the range of the function is large enough and the attacker doesn’t make too many queries.

The intuition behind this result is fairly straightforward. If we consider this from the perspective of an attacker interacting with some function in an oracle, the only difference between a random permutation and a random function is that the former will never produce any collisions — distinct inputs that produce the same output — while the latter may (occasionally) do so.

From the adversary’s perspective, therefore, the ability to distinguish whether the oracle contains a random permutation or a random function devolves to querying the oracle to see if one can observe such a collision. Clearly if it sees even one collision of the form F(A) = F(B), then it’s not dealing with a permutation. But it may take many queries for the attacker to find such a collision in a PRF, or to be confident one should already have occurred (and hence it is probably interacting with a PRP.)

In general the ability to distinguish the two is a function of the number of queries the attacker is allowed to make, as well as the size of the function’s range. After a single query, the probability of a collision (on a random function) is zero: hence the attacker has no certainty at all. After two queries, the probability is equal to 1/N where N is the number of possible outputs. As the attacker makes more queries this probability increases. Following the birthday argument the expected probability reaches p=0.5 after about queries. For functions like AES, which has output size , this will occur around queries.

PRFs can be used to build PRPs. The above result shows us that PRPs are usually good enough to serve as PRFs “without modification.” What if one has a PRF and wishes to build a PRP from it? This can also be done, but it requires more work. The standard technique was proposed by Luby and Rackoff and it involves building a Feistel network, where each “round function” in the PRP is built using a pseudorandom function. (See the picture at right.) This is a bit more involved than I want to get in this post, so please just take away the notion that the existence of one of these objects implies the existence of the other.

Why do I care about any of this?

I mean, you don’t have to. However: I find that many people just getting into cryptography tend to get very involved in the deep details of particular constructions (ciphers and elliptic curves being one source of rabbit-holing) and take much longer to learn about useful analysis tools like PRFs and PRPs.

Once you understand how PRPs and PRFs work, it’s much easier to think about protocols like block cipher modes of operation, or MAC constructions, or anything that involves deriving multiple keys.

Take a simple example, the CBC mode of operation: this is a “classical” mode of operation used in many block ciphers. I don’t recommend that you use it (there are better modes) but it’s actually a very good teaching example. CBC encryption requires the sender to first select a random string called an Initialization Vector, then to chop up their message into equal-size blocks. Encryption looks something like this:

If we’re willing to assume that the block cipher is a PRP, then analyzing the security of this construction shouldn’t be terribly hard. Provided the block size of the cipher is large enough, we can first use the PRP/PRF switching lemma to argue that show that a PRP is (computationally) indistinguishable from a random function. To think about the security of CBC-mode encryption, therefore, we can (mathematically) replace our block cipher with a random function of the appropriate domain and range. Now the question is whether CBC-mode is secure when realized with a random function.

So if we replace the block cipher with a random function, how does the argument work?

Well, a nice way to realize a random function (oracle) is to imagine that the function is being sampled “lazily.” This means instead of sampling an entire random function in one go, we can instead imagine an “oracle” that builds the function one query at a time. The oracle works as follows: anytime some party queries the oracle, the oracle checks to see if the input value has been queried before. If it has, it outputs the value it gave you previously. Otherwise it samples a new (uniformly random) output string using the RNG, and writes the input/output values down for later checks.

Now here is how we can use this oracle to argue the security of CBC mode. Imagine that an encryptor is using CBC mode to encrypt some secret message, but instead of a block cipher they are using our “random function” oracle above. The encryption of a message will look like this:

1. To encrypt a message, the encryptor will first choose a uniformly-random Initialization Vector (IV).
2. She will then XOR that IV with the first block of the message, producing a uniformly-distributed string.
3. Then she’ll query our random function oracle to obtain the “encryption” of this string. Provided the oracle hasn’t seen this input before, it will sample and output a uniformly random output string. That string will form the first block of ciphertext.
4. Then the encryptor will take that ciphertext block and treat it as the “IV” for the next message block, and will repeat steps (2-4) over and over again.

Notice that as long as the oracle never gets called on the same input value twice, the output of this encryption process will be a series of uniformly-random bits that have nothing to do with the input message. So CBC ciphertexts will be very secure! The only remaining thing to do is to consider the probability that the encryptor does query the same input value twice. Fortunately, using a little bit of probability, we can show that since (1) each input is uniformly distributed, then (2) the probability of such an input-collision is quite low.

(In practice this probability works out to be a function of the block size and the number of plaintext blocks enciphered. This analysis is why cryptographers generally prefer ciphers with large block sizes, and why we place official limits on the number of blocks you’re allowed to encipher with modes like CBC before you change the key. To see more of the gory details, look at this paper.)

You can repeat a similar analysis for many other protocols that use keyed PRF/PRP type functions.

What if the PRP/PRF key isn’t secret?

One of the biggest restrictions on the PRF concept is the notion that these functions are only secure when the secret key (AKA, the choice of which “function” to use from the family) is kept secret from the adversary. We already discussed why this is critical: in the PRF (resp. PRP) security game, an attacker who learns the key can instantly “distinguish” a pseudorandom function from a random one. In other words, knowledge of the secret key explodes the entire concept of pseudorandomness. Hence from a mathematical perspective, the security properties of a PRF are somewhere between non-existent and undefined in this setting.

But that’s not very satisfying, and this kind of non-intuitive behavior only makes people ask more questions. They come back wondering: what actually happens when you learn the secret key for a PRF? Does it explode or collapse into some kind of mathematical singularity? How does a function go from “indistinguishable from random” to “completely broken” based on learning a small amount of data?

And then, inevitably, they’ll try to build things like hash functions using PRFs.

The former questions are mainly interesting to cryptographic philosophers. However the latter question is practically relevant, since people are constantly trying to do things like build hash functions out of block ciphers. (NB: this is not actually a crazy idea. It’s simply not possible to do it based solely on the assumption that these functions are pseudorandom.)

So what happens to a PRF when you learn its key?

One tempting answer to this question draws from the following (tempting, but incorrect) line of reasoning: PRFs must somehow produce statistically-“random looking” output all the time, whether you know the key or not. Therefore, the argument goes, the PRF is effectively as good as random even after one learns the key.

This intuition is backed up by the following thought-experiment:

1. Imagine that at time (A) I do not know the key for a PRF, but I query an oracle on a series of well-defined inputs (say, the numbers 1, 2, …, q for some integer q that is polynomial in the key length.)
2. Clearly at this point, the outputs of the PRF must be indistinguishable from those of a true random function. More concretely, any statistical “randomness test” I run on those outputs should “succeed”, i.e., tell me that they look pretty random.

   (Putting this differently: if any test reliably “fails” on the output of the PRF oracle, but “succeeds” on the output of a true random function, then you’ve just built a test that lets you distinguish the PRF from a random function — and this means the function was never a PRF in the first place! And your “PRF” will now disappear in a puff of logic.)

3. Now imagine that at time (B) — after I’ve obtained the oracle outputs — someone hands me the secret key for the PRF inside the oracle. Do the outputs somehow “stop” being random? Will the NIST test suite suddenly start failing?

The simple answer to the last question is “obviously no.” Any public statistical test you could have performed on the original outputs will still continue to pass, even after you learn the secret key. What has changed in this instance is that you can now devise new non-public statistical tests that are based on your knowledge of the secret key. For example, you might test to see if the values are outputs of the PRF (on input the secret key), which of course they would be.

So far this doesn’t seem so awful.

Where things get deeply unpleasant is if the secret key is known to the attacker at the time it queries the oracle. Then the PRF can behave in ways that deviate massively from the expected behavior of a random function. For example, consider a function called “Katy-Perry-PRF” that generally behaves like a normal PRF most of the time, but that spews out Katy Perry lyrics when queried on specific (rare) inputs.

Provided that these rare inputs are hard for any attacker to find — meaning, the attacker will find them only with negligible probability — then Katy-Perry-PRF will be a perfectly lovely PRF. (More concretely, we might imagine that the total number of possible input values is exponential in the key length, and the set of “Katy-Perry-producing” input values forms a negligible fraction of this set, distributed pseudorandomly within it, to boot.) We can also imagine that the identity of these Katy-Perry-producing inputs is listed in the secret key, which a normal PRF adversary will not have.

Clearly a standard attacker (without the secret key) is unlikely to find any inputs that produce Katy Perry lyrics. Yet an attacker who knows the secret key can easily obtain the entire output of Katy Perry’s catalog: this attacker will simply look through the secret key to find the appropriate inputs, and then query them all one at a time. The behavior of the Katy-Perry function on these inputs is clearly very different from what we’d expect from a random function and yet here is a function that still satisfies the definition of a PRF.

Now obviously Katy-Perry-PRF is a silly and contrived example. Who actually cares if your PRF outputs Katy Perry lyrics? But similar examples can be used to produce PRFs that enable easy “collisions”, which is generally a bad thing when one is trying to build things like hash functions. This is why the construction of such functions needs stronger assumptions, such as the assumption that the block cipher is actually a random function.

Finally: how do we build PRFs?

So far I’ve been using the ChaCha function as an example of something we’d really like to imagine is a PRF. But the fact of the matter is that nobody knows how to actually prove this. Most of the practical functions we use like PRFs, which include ChaCha, HMAC-SHAx, and many other ciphers, are constructed from a handful of simple mathematical operations such as rotations, XORs, and additions. The result is then analyzed by very smart people to see if they can break it. If someone finds a flaw in the function, we stop using it.

This is theoretically less-than-elegant. Instead, it would be nice to have constructions we clearly know are PRFs. Unfortunately the world is not quite that friendly to cryptography.

From a theoretical perspective, we know that PRFs can be constructed from pseudorandom generators (PRGs). We further know that PRGs can in turn be constructed from one-way functions (OWFs). The existence of the latter functions is one of the most basic assumptions we make in cryptography, which is a good way of saying we have no idea if they exist but we are hopeful. Indeed, this is the foundation of what’s called the “standard model.” But in practice the existence of OWFs remains a stubbornly open problem, bound tightly to the P/NP problem.

If that isn’t entirely satisfying to you, you might also like to know that we can also build (relatively) efficient PRFs based on the assumed hardness of a number of stronger mathematical assumptions, including things like the Decisional Diffie-Hellman assumption and various assumptions in lattices. Such things are nice mainly because they let us build cool things like oblivious PRFs.

Phew!

This has been a long piece, on that I’m glad to have gotten off my plate. I hope it will be helpful to a few people who are just starting out in cryptography and are itching to learn more. If you are one of these people and you plan to keep going, I urge you to take a look at a cryptography textbook like Katz/Lindell’s excellent textbook, or Goldreich’s (more theoretical) Foundations of Cryptography.

Top photo by Flickr user Dave DeSandro, used under CC license.