# Introduction

EllipticPIR is a Private Information Retrieval (PIR) implementation that scales and runs on GPUs.

## What is Private Information Retrievals (PIRs)?

[A private information retrieval](https://en.wikipedia.org/wiki/Private_information_retrieval) is a cryptographic building block which enables clients to retrieve data from a server without revealing any information about the query.

Suppose that you want to go to the nearest McDonald's. You will search it for finding the location on the Map, which will query to the map server with the text like "McDonald's New York". In that case the server will learn that you're going to go to one of the McDonald's located in New York city, which leaks your privacy.

With PIRs, you can search any keywords without disclosing any information about your query and in the above case the server learn nothing about your query.

## The difficulties with traditional PIRs

In principle, PIR implementations should traverse all the database elements and compute them to create an encrypted reply. Thus the server-side procedure requires huge amount of computational resources.

The traditional PIR implementations (like [SealPIR](https://github.com/microsoft/SealPIR)) does not support parallel computation of query and cannot be scaled with multi-core CPUs or many-core GPUs. In our implementation, the server side computation is highly parallelizable and can be run on any GPUs.

## What is EllipticPIR?

EllipticPIR is a new instantiation and an implementation of PIRs which is highly parallelizable and can run on GPUs.

The traditional PIR implementation (SealPIR) can reply to the query with \~1M database elements in 2 secs, whereas our implementation can reply with \~100M database elements in 2.6 secs using single consumer GPU, which is x77 faster! Please note that if we utilize multiple GPUs or use pro GPUs (like NVIDIA Tesla) our practical computation time easily can be faster than the above experiment.

In addition, SealPIR uses Learning With Errors (LWE) homomorphic encryption which is NOT widely battle-tested, but EllipticPIR only uses Elliptic Curve (EC)-ElGamal encryption (ElGamal encryption was invented in 1984) which is already technically matured well.

Thus our invention is highly practical and secure compared to the traditional ones.


# Why not Tor?

[Tor](https://www.torproject.org/) provides a proxy which anonymize your IP address from the server.

However it is rumored that NSA is try to controlling the Tor network. Tor's anonymization is achieved by relaying your encrypted packet through three or more relay servers. Unfortunately, if your entry (first) relay and exit (last) relay are operated by a single person or entity, that entity can track your packet. Tor is an excellent service, but it does not provide cryptographical nor mathematical security.

In addition, if you want to access to the private (authenticated) endpoints on the server, the server will learn who is accessing by your authorization token (like session keys). In this case Tor does not help privacy.

With EllipticPIR, you can query to the server in a cryptographically and mathematically secured way even if you are using some authentication. This characteristic cannot be achieved by Tor.


# EllipticPIR Cloud

The SaaS version of EllipticPIR

## Introduction

We provide a cloud service, "EllipticPIR Cloud" which you can put any data into the cloud and offers to the end-users for cryptographically privacy-preserving database server.

You can create any dataset with fixed byte-length, with any number of elements.

## Coming soon...


# Client Library (MIT)

We implemented the client-side library in C, C++ (bindings to C), Rust and TypeScript (JavaScript).

The code is publicly available at [GitHub](https://github.com/EllipticPIR/libepir).

Check the GitHub repo for documentation.


# Introduction

For non-engineers

## Math behind PIRs in 5min

The server sorts database elements in some way to coordinate a dataset. The client will send a query with an encrypted position of the elements and the server replies an encrypted data with the correct data.

The client sends an array of encrypted messages with zero or one. There is single "one" encrypted message which select the database elements to fetch. Since all messages are encrypted with client's private key, the server cannot distinguish which messages are zero or one.

The server will compute a multiplication with the data and encrypted messages, and then adds them up to compose an encrypted payload and send back to the client.

The client then decrypts the encrypted reply to retrieve the needed data.

```
(server's reply)
= d(1) * E(0) + .. + d(i-1) * E(0) + d(i) * E(1) + d(i+1) * E(0) + .. + dn * E(0)
= E(d(i))
```

## Multi-dimensional case

We intentionally limited ourselves to the one-dimensional case above, but in our implementation we use multi-dimensional PIR. For multi-dimensional PIR, the server arranges the database elements in a multi-dimensional cube (for 2d: squre, for 3d: cube, for 4d+: hypercube) and the client's query will be an array of arrays of encrypted messages. The reply will be an encrypted message with some another encrypted message of some another encrypted message... (repeated for the dimension used).

This looks too complicated but it is required for shorter reply. There are some trade-offs between the reply size and the computation time, the dimension is usually selected as two or three.


# Code Audit

Our client-side implementation is open-source and available to anyone at [GitHub](https://github.com/EllipticPIR). You can check the code reliability by yourself. It is licensed under the MIT License, you can integrate our client library without any permission.

The server-side implementation is closed-source currently thus our server may misbehave. However this does not lead any potential security defect because the query is encrypted by a client-side private key. Anything we can do on our server is to create a wrong reply. We cannot know anything from the query if the server-side implementation is malicious. This can be proven mathematically.


# EC-ElGamal Encryption

We use the EC-ElGamal encryption as a backing encryption because it is an additively homomorphic encryption.

We use the curve defined in Ed25519 for our implementation because this curve is well battle-tested and efficient.

The decrypted message of the EC-ElGamal encryption is the scalar multiplication between the original plaintext and the base point `G`. Thus we should solve the discrete logarithm problem (DLP) to retrieve the original plaintext.

The DLP is generally difficult to solve, but if we limit the message size in some range `n` (say `0-2^24`), we can solve the DLP by brute force. For this purpose we pre-generate `[O, G, 2G, ..]` array as the filename `mG.bin` for fast lookup for the solution. Pre-generation takes some time (`O(n)`) which is one-time, and if we utilize binary or interpolation search to the pre-generated points, we can efficiently solve the DLP with complexity `O(log(n))` for each decryption process.


# Query Composition

The database elements in EllipticPIR is arranged as a hypercube with dimension `d`. For instance, if `d = 3` and the number of database elements `n = 1,000,000`, the dataset is arrange as 3-d cube with `100 x 100 x 100` elements for each edge.

The query will select the position on that hypercube. For `d = 3` case, you should select the `x`, `y` and `z` coordinates of the hypercube in your query.

Once you determine the `(x, y, z)` tuble, next you should create an encrypted query.

You will **generate a private** key `sk` that can be ephemeral per query (you can reuse the private key for multiple queries, but there are no such requirement). **You don't have to submit your public key** to the server. There is no such API.

Then, create an array of EC-ElGamal encrypted message array for each coordinates. For `x`-coordinate, you will create an array of EC-ElGamal encrypted messages with the length equal to the element count on the `x`-edge of the hypercube. The encrypted array is

`[Enc(0), .., Enc(0), Enc(1), Enc(0), .., Enc(0)]`

where only the `x`-th message is one and zeros for non `x`-th.

This will continue to y, z, .. to reach to the dimension. Thus the final query is

`[`\
  `[Enc(0), .., Enc(0), Enc(1), Enc(0), .., Enc(0)],`\
  `..,`\
  `[Enc(0), .., Enc(0), Enc(1), Enc(0), .., Enc(0)]`\
`].`

The total number of encrypted messages will be `O(n^(1/d))`. This will be both the computational complexity of the query generation process and the outbound network traffic to the server.


# Reply Generation

To generate a server's reply, we take a multiply-and-add (inner product for 1d case, tensor product for 2+d case) between the query and the database elements stored on our database. This tensor product will be repeated for the dimension of a dataset to generate the final reply.


# Reply Decryption

The server reply is nested encrypted message with the depth equal to the dimension `d` of the dataset, the reply decryption process you need to decrypt the server's message for `d` times.

`decrypted = Dec(..Dec(reply)..)`

The decrypted will be the data you requested with some padding. The library automatically remove the padding and returns the desired result.


# Key Search

The naked PIR protocol only can specify the position of the database elements stored on the database. Thus if you are not sure about the position number of the data, you cannot retrieve the data in one query.

However if the database elements are sorted according to the some key set, you can execute a binary or interpolation search to the database with multiple requests to achieve key search essentially.

This enables you to do a key search for the database.

The worst number of queries sent to the server is `log2(n)`, but if you utilize interpolation search the number of queries are much shorter than the worst case for almost all real-world dataset.

We recommend interpolation search but the server may learn some knowledge from the number of requests sent to the server. In that case you can switch to binary search which has constant number of requests sent to the server. The latter case has perfect privacy by sacrificing efficiency, whereas the former case also will not leak big knowledge about the query and has more efficiency. We recommend interpolation search if you are not perfectionist.


# Why Reply Generation is O(n)

All PIR protocol requires `O(n)` computation without no exception where n is the number of database elements.

If the server-side computation is below `O(n)`, which means some database elements are not accessed in reply generation. Which leads the fact that those elements are not included in the reply and leaks knowledge. Thus it is mandatory to require `O(n)` computation complexity for all PIR protocols.

The computation in EllipticPIR is almost consumed by tensor product between encrypted query and data, and has `Θ(n)` of computational complexity which is optimal at least in a computational complexity context.

LWE (learning with errors) encryptions has relatively small computational footprint for homomorphic addition because addition in LWE encryption is just an addition of two polynomials. LWE ciphertext is high dimensional polynomial containing multiple plaintexts (vector). If we use LWE encrytion as our backend, it is required to rotate plaintext vector in a LWE ciphertext which consumes relatively high computational resources. Thus we concluded that simpler homomorphic encryption schemes like EC-ElGamal best fit for efficient parallelization.

We continue to research to find more efficient algorithm all time and there is a chance that we find a better way.


# Crypto Wallet Provider

Secure your wealth from the potential leakage of blockexplorer providers.

## Introduction

If you want to check the amount of crypto you're holding, your wallet will initiate an RPC call to a full node server (e.g. [Infura](https://www.infura.io/)) or API (blockexplorer) server with a query containing your crypto address. Thus the server will learn the connection between your IP address and your wallet address.

This will cause some security risks.

Since some machine located in your IP address has private key in some way, you will be a victim of targeted attacks. Hackers will try to penetrate into your local network and will steal your coins.

Your physical location roughly can be determined by your IP address. Someone may come to your physical address and try to [rob your coins with a five dollar wrench](https://cointelegraph.com/news/5-wrench-attacks-appear-to-be-on-the-rise-in-the-crypto-community). Your option is to endure until your death to protect your wealth or surrender all of your coins.

The happy news is that while your wallet endpoint server's access log is protected against hackers, the connection between the IP addresses and wallet addresses the server learned won't be leaked. However, Ledger, the one of the largest hardware wallet company, [reported they suffered a data breach in July, 2020](https://www.ledger.com/message-ledgers-ceo-data-leak). You need to trust wallet providers you use in some way. If you are a crypto nerd, why you can trust your wallet provider?

## Solution

To protect against the above situation, the crypto industry should shift not to collect the connection between IP addresses and wallet addresses, not in an operational way, but in a cryptographic security. Wallet providers can discard access logs to secure their customers, but how can you verify your wallet provider is doing so?

The ultimate solution is cryptographically secure way to access wallet providers. EllipticPIR is the answer. Wallet providers can offer a completely privacy-preserving endpoints to the customers using our implementation.

We have already built a sample implementation of a Bitcoin's UTXOs server using EllipticPIR. As we tested, it can reply to queries in 10 secs or so with single consumer GPU which is within practical limits. Please note that execution time can be shortened by offloading workload into multiple GPUs for better latency.


# Credit Scoring

Inquire users' credit scores to credit scoring services without letting know who you are registering.

Services typically financial services require to assess user's credit before registration. For that purpose it is common to use credit scoring services (CSS) such as [CIC](https://www.cic.co.jp/) and [JICC](https://www.jicc.co.jp/) in Japan.

However financial services need to inquire to the CSS with the user's name (e.g. Alice) they are registering, which will tell the CSS "we are going to register Alice as our customer".

If you are inquired by some loan shark (Yamikin, 闇金), you will have a chance to have a negative impact to your credit score.

If a CSS supports PIRs for their inquiry, there is no chance to learn the connection between you and financial services. This will improve privacy dramatically.


# + Add Your Service

We are seeking a practical usage of PIRs.

If you think your needs match we can provide, please [contact us](/help/contact) without hesitation!


# Contact

If you are interested in our product, please feel free to contact us.

```
info@janom.co.jp
```