Skip to main content

How it works

The Blyss bucket service is a key-value store with private retrievals. Clients can use the Blyss SDK to create buckets, write data to them, and make private retrievals from them.

In this document, we'll explain what private retrieval is, and how the Blyss service makes it possible at a high level. For a more complete explanation, including the underlying mathematics, check out this blog post.

Goal: private retrieval​

The security guarantee of a private retrieval is that no entity, not even the Blyss bucket service itself, can determine the key being retrieved. The security model assumes from the start that the Blyss bucket service, and all other entities outside of the client's device, are completely untrusted.

Remote, untrustedLocal, trustedUser deviceOpen source SDKSDKBucket service

Private retrievals were essentially impossible until recently. Data stores like Amazon S3, Firebase, or Redis cannot offer private retrievals - they must know the item being retrieved so that they can fetch it from memory or disk. The only way to perform private retrievals from these services is to download the entire database.

Blyss uses advancements in state-of-the-art cryptography to build the first generally available key-value store with private retrievals.

Tool: homomorphic encryption​

The cryptography that powers Blyss is called "homomorphic encryption". First, some history: homomorphic encryption was a 'holy grail' for academic cryptographers for over 20 years, until it was finally constructed for the first time by Craig Gentry in 2009. Early schemes were comically slow: it could take hours to encrypt small amounts of data. Thanks to hard work from a large set of academic cryptographers, homomorphic encryption has finally become fast enough in the last two years.

What kind of encryption could so fascinate people that they spend decades working to build it? Well, basically, homomorphic encryption lets you perform computation on encrypted data. This is really unique: normally, when you encrypt something, it gets totally garbled. If you tried to perform computation on normally encrypted data, you would get meaningless garbage.

Client homomorphically encrypts its image.Server applies the sepia filter, without seeing the image!Client decrypts and gets the filtered image.

With homomorphic encryption, everything still gets garbled, but you can do strange and wonderful new things. For example, if you homomorphically encrypt an image, and send the encrypted image to an untrusted server, the server can apply filters (e.g. 'sepia' or 'background blur') directly to the encrypted image. Everything stays encrypted the whole time - the server never gets to see the original or filtered image - but you get back an encrypted version of the filtered image. It's almost like the sever has a blindfold on, and is able to 'do its job' without learning any inputs or outputs. This is totally impossible with normal encryption, and opens up a whole new world of services and applications that can serve end users without learning their sensitve data.

info

Homomorphic encryption is an emerging technology, and is still in the process of being standardized. The underlying cryptographic assumptions are well-founded and have been extensively analyzed as a byproduct of efforts to standardize post-quantum cryptography, but it is not yet available in libraries like OpenSSL and OS's.

Private retrievals using homomorphic encryption​

So, how does Blyss actually use homomorphic encryption to enable private retrievals? Here's a high-level summary:

Client homomorphically encrypts 0’s and 1’s.Server multiplies encryptions by the database, and adds up the results.Client decrypts and gets the desired item.0“alpha”0“omega”1“beta”“beta”

  1. The client homomorphically encrypts a large vector of 0's and 1's. The vector has encrypted 0's in almost every entry, except that it has '1' in the entry corresponding to the item we are trying to retrieve. The client sends this large vector of encrypted 0's and 1's as the query.

    info

    The client uploads a series of encrypted 0's and 1's, but the server cannot tell which are 0, and which are 1; each encryption is unique random-looking.

  2. The server computes a dot-product between the data in the bucket and the query. Specifically, it multiplies each item in the bucket by the corresponding encrypted 0 or 1 in the query, and then adds up all the results. All the non-desired items will get multiplied by zero, so we're left with only the client's desired item. Thanks to the special properties of homomorphic encryption, all of this happens without the server learning anything about which item the client wanted!

  3. The server sends back this final encryption, and the client decrypts it, getting the item that it wanted.

Basically, we can "select" an item from the bucket using 0's and 1's, and homomorphic encryption lets the server do that while "blindfolded" - without learning which value was 1. This is an abridged version of what is happening under the hood: Blyss uses cutting-edge schemes that compress the query significantly and structure the database as many-dimensional. The underlying cryptographic schemes are peer-reviewed and were presented at IEEE S&P 2022.

SDK​

To perform a private retrieval, you need to homomorphically encrypt 0's and 1's. Since homomorphic encryption is not (yet) a part of standard cryptography toolkits like OpenSSL, we distribute an open-source SDK that provides this functionality. Our implementation of all cryptography is written in Rust, with basic side-channel mitigations. As this space matures, we hope to encourage multiple open-source implementations of a common private retrieval protocol. The SDK is versioned, open source, and has reproducible builds, mitigating the potential for a malicious actor to inject compromised SDK code into the software supply chain.