Right now the Client sends all of the Galois Keys to the server for oblivious expansion. This may not always be necessary. We should consider only sending what's necessary. See this comment on PR6.

Description

To complete the PSI integration, we need to support cardinality requests.

For a batch request, we need to return the number of elements that are in the database.
For that, we can simply assign 1 as database values to every queried index, and return the encrypted sum.

Currently, relinearization keys are not required, though the client will always send them. We need to figure out when relinearization keys are required and enforce that in the server. We could also add that to the PIRParameters so that the server can specify when relinearization keys must be given with a request.

Description

The current PSI implementation supports 2 operations:

• Get intersection elements.
• Get Intersection size.

In order to finish the PSI integration, we need:

• Batch queries. #22
• Support for strings in the database. #21
• Support for sparse databases.#24
• Support for database buckets #27
• Support for cardinality requests. #23

On completion, it should be straightforward to integrate PIR in https://github.com/OpenMined/PSI

The current PSI flow:

1. Setup phase

The server encrypts all its elements x under a commutative encryption scheme, computing H(x)^s where s is its secret key. The encrypted elements are then inserted in a Bloom filter, which is sent to the client encoded as JSON. The message has the following form:

{
  "num_hash_functions": <int>,
  "bits": <string>
}

Here, bits is a Base64-encoded string.

2. Client request

The client encrypts all their elements x using the commutative encryption scheme, computing H(x)^c, where c is the client's secret key. The encoded elements are sent to the server as a JSON array of Base64 strings, together with a boolean reveal_intersection that indicates whether the client wants to learn the elements in the intersection or only its size.

{
  "reveal_intersection": <bool>,
  "encrypted_elements": [ Base64(H(x_1)^c), Base64(H(x_2)^c), ... ]
}

3. Server response

For each encrypted element H(x)^c received from the client, the server encrypts it again under the commutative encryption scheme with its secret key s, computing (H(x)^c)^s = H(x)^(cs). The result is sent back to the client as a JSON array of strings:

{
  "encrypted_elements": [ Base64(H(x_1)^c), Base64(H(x_2)^c), ... ]
}

If reveal_intersection is false, the array is sorted to hide the order of entries from the client.

4. Client computes intersection

The client decrypts each element received from the server's response using its secret key c, computing (H(x)^(cs))^(1/c) = H(x)^s. It then checks if each element is present in the Bloom filter, and reports the number of matches as the intersection size.

Description

I'm new to cryptography and want to use PIR to do some experiments, but I can't find a tutorial on how to use this library.

Type of Test

• Unit test (e.g. checking a loop, method, or function is working as intended)
• Integration test (e.g. checking if a certain group or set of functionality is working as intended)
• Regression test (e.g. checking if by adding or removing a module of code allows other systems to continue to function as intended)
• Stress test (e.g. checking to see how well a system performs under various situations, including heavy usage)
• Performance test (e.g. checking to see how efficient a system is as performing the intended task)
• Other...

Expected Behavior

A clear and concise description of what you expected to happen. Do you intend to reach a certain percentage of test coverage for this file, feature, or codebase?

Additional Context

Add any other context about the tests here.

Question

How to get the modified version of SealPIR that described in the paper "Communication–Computation Trade-offs in PIR" from this project.

Further Information

Is this project implementation of modified version of SealPIR ?

Screenshots

If applicable, add screenshots to help explain your question.

System Information

• OS: [e.g. iOS]
• OS Version: [e.g. 22]
• Language Version: [e.g. Python 3.7, Node 10.18.1]
• Package Manager Version: [e.g. Conda 4.6.1, NPM 6.14.1]

Additional Context

Add any other context about the problem here.

If the database contains zero values, these cause exceptions to be thrown in the Server. We should probably at least check for zero values and warn in that case, if not actually handle them properly.

After PR6, we'll introduce Galois Keys into the Payload, but not in the serialization. We need to add that to the serialization.

What is the minimum version required for the dependencies such as bazel, gcc and clang? Please specify that in the README.

Is there support for large responses in this codebase? I'm referring to responses larger than one ciphertext. As far as I try, I get an error as soon as the size of the response, i.e. ITEM_SIZE, exceeds the size of one ciphertext.

Question

Describe your question in ONE SENTENCE.
Is this project implementation of MulPIR？

Further Information

Describe your question in greater length here.

Screenshots

If applicable, add screenshots to help explain your question.

System Information

• OS: [e.g. iOS]
• OS Version: [e.g. 22]
• Language Version: [e.g. Python 3.7, Node 10.18.1]
• Package Manager Version: [e.g. Conda 4.6.1, NPM 6.14.1]

Additional Context

Add any other context about the problem here.

Description

In order to complete the PSI integration, we need to support sparse databases.

The database would receive as setup arguments an ordered map, uint64_t -> T.
One approach could be to create a vector full of zeros, and mark only the keys from the sparse map.

Description

There are two warnings during compilations.

How to Reproduce

1. bazel build -c opt //pir/cpp/...

Expected Behavior

No warning

Screenshots

NA

System Information

• OS: macOS
• OS Version: 10.15

Additional Context

pir/cpp/utils.h:33:21: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
   33 |   for (int i = 1; i < sizeof(n) * 8; i = i << 1) {
      |                   ~~^~~~~~~~~~~~~~~

and

pir/cpp/server_test.cpp:122:16: warning: unused variable 'desired_index' [-Wunused-variable]
  122 |   const size_t desired_index = 7;
      |                ^~~~~~~~~~~~~

To be able to send a request for arbitrary DB sizes, we need to support sending more than 1 CT as the selection vector and do the oblivious expansion on it. As of PR6 we only support 1 CT.

Description

To complete the PSI integration, we need support for multiple values in a single request.

Hi, I have a question to ask, this PIR library is not implemented in terms of network communication, right? Including the library of our community PSI is also not implemented?

Description

When I run "bazel build -c opt //pir/cpp/..." to compile, something goes wrong.

Expected Behavior

compiling success

Screenshots

System Information

• OS: centos
• OS Version: 7
• GCC version: gcc version 11.2.1 20220127 (Red Hat 11.2.1-9) (GCC)
• Bazel version:
  Build label: 1.2.1
  Build target: bazel-out/k8-opt/bin/src/main/java/com/google/devtools/build/lib/bazel/BazelServer_deploy.jar
  Build time: Tue Nov 26 00:00:00 2019 (1574726400)
  Build timestamp: 1574726400
  Build timestamp as int: 1574726400

As we've discussed via Slack, the PSI team is going towards Protocol Buffers for serialization to better cross-language support (i.e. rather than depending on C++ first and then exporting serialization to other languages). We should update PIR to match, which means changing the existing json serialization to Protocol Buffers.

I've actually already implemented some of this in my own repo when I was experimenting with SealPIR. See the rpc branch.

Feature Description

For a variety of use cases, we need to be able to support bucketing. Bucketing is when one or more elements of a database exist in one address. All it really is, is a particular DB layout that changes what would be a sparse database into a packed database. For example, let's say there are 2^18 items, each 128 bits long, uniformly distributed. Storing these items in their native format would require a sparse database with 128-bit addresses, or something like cuckoo hashing. Another approach is to use 2^16 buckets, with on average 4 items per bucket. The first 16-bits of the item is used as the bucket address, and then the remaining bits are stored within the bucket.

Is your feature request related to a problem?

This is needed to efficiently support PSI (and PSI-CA) over sparse databases.

Description

In order to complete the PSI integration, we need to support string values in the database class.

We need to encode the strings in seal::Plaintext objects.

The server will need to send the client PIRParameters. We should make this a protocol buffer like the request and response. We can also use the PB as an internal representation to reduce duplication.

Hey Bogden, figured we could use the tools in github rather than Slack so that we can't search this afterwards. Compiling the starting point on Mac produces this error:

ld: library not found for -lrt

Looks like the rt library isn't available on Mac, but also isn't needed. I just commented that line out of the build file and then everything worked. Not sure what the right answer is, but there's got to be a way in Bazel to only include rt if it's needed.

Based on this readme template, we should improve our readmes across all OpenMined projects.

Please consult the following document for our desired best practices.

Where?

Should probably be in the top level readme file

Who?

Users of the library

What?

Top level PIR parameters and important encryption parameters, like database sizing, poly_mod_degree, plain mod bit size, etc. Should include what they do and how to chose them.

Additional Context

Need to include some info about SEAL, but should probably point to their documentation instead of reproducing it.

Description

A clear and concise description of what you want to improve.

Are you interested in working on this improvement yourself?

• Yes, I am.
• No, I am not.
• No, but I think @XxXperson would be interested.

Additional Context

Add any other context or screenshots.