commit	89d8affe42e778993f3245b447c5165747c3c88f	[log] [tgz]
author	Kevin Graney <[email protected]>	Wed May 10 12:43:02 2023 -0400
committer	Kevin Graney <[email protected]>	Thu May 11 07:48:23 2023 -0400
tree	03f56d7cf2cd47e9d61363924e3c06ba0acc8d12
parent	dede29ddc66da173477b4d0891411c7b4b74bc5b [diff]

Import content from http://ag/22581896

Squashed commit of the following:

commit cb5cc5d4e837aa57c0155a78939a00f8858ddbdf
Author: Kevin Graney <[email protected]>
Date:   Tue May 9 14:41:20 2023 -0400

    Give Abseil visibility to anonymous-counting-tokens

commit ebb50c115dc0c14d67bcf7b268e573a932cecb67
Author: Kevin Graney <[email protected]>
Date:   Mon May 1 15:21:37 2023 -0400

    Update visibility again

commit e3ad3dbceb69fa961e47c6e1c2c52f1cfc6f5853
Author: Kevin Graney <[email protected]>
Date:   Mon May 1 11:14:02 2023 -0400

    Change visibility; add CFI for device builds

commit 4d9e0cc71238ed276d11b273fd5a78517e5d680a
Author: Kevin Graney <[email protected]>
Date:   Thu Apr 27 15:41:12 2023 -0400

    Add a TODO to support CFI

commit 4358e418a86e11ac83ffcc7b1d5d234a1c456b97
Author: Kevin Graney <[email protected]>
Date:   Thu Apr 27 14:58:42 2023 -0400

    Patch updates from google3

commit 4d706c63606e7a5e9b47a2e9de4d1a8f0b74506a
Merge: efa1236 e028e59
Author: Kevin Graney <[email protected]>
Date:   Thu Apr 27 11:28:46 2023 -0400

    Merge branch 'master' into android_3p2

    Add Karn's latest changes

commit efa12364a08be9293cb58781ac2bfa413fe72b8e
Author: Kevin Graney <[email protected]>
Date:   Wed Apr 26 11:20:31 2023 -0400

    Update visibility rules to match expected ACT dir

commit 70a58a8abea90d92c9fe1a957027f595c403de30
Author: Kevin Graney <[email protected]>
Date:   Wed Apr 19 13:13:34 2023 -0400

    Add sanitizers to libpjc compilation

commit e028e59420a9c36328705ed5064408de03d229a8
Author: Karn Seth <[email protected]>
Date:   Mon Apr 17 13:10:43 2023 -0400

    updates bb_oblivious_sig param combinations and dy_vrf params proof

commit 9e3c52095248f131461a716be4f59e8ae267d8f4
Author: Kevin Graney <[email protected]>
Date:   Tue Apr 11 19:38:36 2023 -0400

    Add TEST_MAPPING file

commit 6a04d8cf69c912ae72d5bb3e62d00a403cd9f50c
Author: Kevin Graney <[email protected]>
Date:   Mon Apr 10 23:50:49 2023 -0400

    More edits

commit b0dc1f512d9e1cabb697b99b14bc928e4e2e703a
Author: Kevin Graney <[email protected]>
Date:   Mon Apr 10 23:49:42 2023 -0400

    Add explicit version

commit ef0056eff7407e1c42c64216a9eba9c61734577b
Author: Kevin Graney <[email protected]>
Date:   Mon Apr 10 23:02:35 2023 -0400

    Start splitting up unit tests to prevent linker errors

commit 4df3ca23871bef011fb8aff624e794faf8400f32
Author: Kevin Graney <[email protected]>
Date:   Fri Apr 7 13:10:25 2023 -0400

    Add -Wno-unused-parameter

commit ef30c6900b326a551a6136e79a58ebac1b060040
Author: Kevin Graney <[email protected]>
Date:   Fri Apr 7 10:04:39 2023 -0400

    Split up unit tests

commit ff52a575179ed54878ca6e60fa7a77779782f61c
Author: Kevin Graney <[email protected]>
Date:   Fri Apr 7 08:44:47 2023 -0400

    Alphabetize abseil sources

commit 743ab3474664b8c83515dab8e7d71fff1d9b82d3
Author: Kevin Graney <[email protected]>
Date:   Fri Apr 7 08:43:15 2023 -0400

    Start separating out abseil unit tests

commit 960c9c5d3eabcb66f9596ebd1276af963a847b01
Author: Kevin Graney <[email protected]>
Date:   Wed Apr 5 23:53:01 2023 -0400

    Minor formatting

commit 99278f1502bf1a95567d0d4ab9093bd79f9109ca
Author: Kevin Graney <[email protected]>
Date:   Wed Apr 5 23:16:15 2023 -0400

    Add libpjc_crypto_test target

commit 8ffe7824c8eec67029c2cff49f6f959fbedc8c29
Author: Kevin Graney <[email protected]>
Date:   Wed Apr 5 21:24:58 2023 -0400

    Change from <> to "" include

commit c4915f258f6d60f57c8fdacfe58030d68b664729
Author: Kevin Graney <[email protected]>
Date:   Wed Apr 5 16:56:08 2023 -0400

    Add more files to compilation set

    Need to fix a few proto includes upstream

commit 12c5c82d53a87f3be8e84a780861c4e19b7d0ab6
Author: Kevin Graney <[email protected]>
Date:   Tue Apr 4 20:31:56 2023 -0400

    Add abseil source files and link to liblog

commit ccf10be3d9ac8106fa7afa372d42ba7281f3e65c
Author: Kevin Graney <[email protected]>
Date:   Mon Apr 3 17:06:02 2023 -0400

    Add include path for abseil

    This is still missing the library to link in

commit 0ac3897acefbc62ae245bcf3c29b80af7deb7efd
Author: Kevin Graney <[email protected]>
Date:   Mon Apr 3 15:59:32 2023 -0400

    Add a private copy of the latest LTS Abseil release

commit c610df0325afb6315ef004ec080c9cc431991c21
Author: Kevin Graney <[email protected]>
Date:   Fri Mar 31 12:23:15 2023 -0400

    Add metadata files for Android third-party

commit 8f055b2e9b4af2e68a65d7c2da67f43adf7eb8dc
Author: Karn Seth <[email protected]>
Date:   Mon Apr 3 11:02:49 2023 -0400

    updates dependencies, adds pedersen, cs, dy primitives

commit ff5af15595ffae1d2499118622f2933e000765bb
Author: Mihaela Ion <[email protected]>
Date:   Fri Nov 18 12:38:53 2022 -0500

    Adds a Java implementation of the EC Commutative Cipher

commit 8eafe59e2d5dda4b2f7e5b3498992d7b71fb45d1
Author: Karn Seth <[email protected]>
Date:   Wed Jul 20 16:25:23 2022 -0400

    updates grpc dep to 1.48.0

commit 505ba981d66c9e5e73e18cfa647b4685f74784cb
Author: Karn Seth <[email protected]>
Date:   Wed Sep 29 19:13:29 2021 +0000

    adds .bazelrc, pjc_deps and .gitignore

commit 5fb148f76a0a40462f4f97aaf858429478f6939b
Author: Karn Seth <[email protected]>
Date:   Tue Sep 28 20:22:27 2021 +0000

    modifies header guards, updates copyright notice

commit 2c8d9c3cd8843e7b0b30853242fbbab978bc333f
Author: Karn Seth <[email protected]>
Date:   Mon Sep 6 23:28:06 2021 +0000

    updates proto_util

commit b4d3de618b6dcf1c14265f5371d3e74151faf4ee
Author: Karn Seth <[email protected]>
Date:   Thu Sep 2 19:40:22 2021 +0000

    changes com_github_glog_glog to com_github_google_glog

commit 8bc01b3f0b41a8ee80acee9ad5ae2c45bbdaef88
Author: Karn Seth <[email protected]>
Date:   Fri Aug 6 23:53:19 2021 +0000

    removes unnecessary include

commit 163826c8ac35453cf2012f1ed0b0324970cae222
Author: Karn Seth <[email protected]>
Date:   Fri Aug 6 23:46:54 2021 +0000

    moves all source files to private_join_and_compute subfolder. Credit to efoxepstein

commit 76477f8d9f0cd773e7e827ad032062ab6e2efd6c
Author: Mihaela Ion <[email protected]>
Date:   Mon Aug 2 20:37:39 2021 +0200

    Updates util imports

commit 4d556ce53686440294f0661b371e483083e35abf
Author: Mihaela Ion <[email protected]>
Date:   Mon Aug 2 20:20:45 2021 +0200

    Removes unsupported proto option

commit 75e368656f29ba8c57766db0f660474345e21f5d
Author: Mihaela Ion <[email protected]>
Date:   Mon Aug 2 16:36:29 2021 +0200

    Fixes proto dependency

commit d363bd46049e24b2123de1d41656518cf6d4b52b
Author: Mihaela Ion <[email protected]>
Date:   Mon Aug 2 08:56:30 2021 +0200

    Fixes a BUILD rule name

commit 81249f1f7427a3e6c81551300d83689b6461f10a
Author: Mihaela Ion <[email protected]>
Date:   Mon Aug 2 08:32:18 2021 +0200

    Adds missing util BUILD rules

commit 4c0fea1906a575219a168b5da0e6dac0013b9205
Author: Mihaela Ion <[email protected]>
Date:   Wed Jul 28 08:34:43 2021 +0200

    Adds helper functions for processing files in parallel and reading and writing keys

commit e88d36aabcf301d904f035ec42f24dc50810ba7e
Merge: 2478023 fe6237a
Author: Kevin Yeo <[email protected]>
Date:   Thu Jul 22 14:43:30 2021 -0400

    Merge pull request #29 from efoxepstein/status-macros

    Improve util/status_macros.h with ifdef guards.

commit fe6237a65de5f3b3b1584f33eef34d9646a93dec
Author: Eli Fox-Epstein <[email protected]>
Date:   Thu Jul 22 18:36:51 2021 +0000

    Improve util/status_macros.h with ifdef guards.

    This also uses operator* instead of .value() to access the value of a
    StatusOr known to be OK as per guidance in https://abseil.io/tips/181.

commit 247802334ab523f9dc611fed872833f43d0c9f5a
Author: Mihaela Ion <[email protected]>
Date:   Wed Jul 21 19:00:40 2021 +0200

    Adds a helper function for writing multiple protos to file

commit 11cfedad51513688c421e86a77fe0e57399340f3
Author: Karn Seth <[email protected]>
Date:   Thu May 13 20:13:40 2021 +0000

    push internal changes

commit 89c8d0aae070b9c282043af419e47d7ef897f460
Author: Karn Seth <[email protected]>
Date:   Tue Feb 23 16:51:52 2021 +0000

    clean up headers etc

commit 217dbe13df5e3bdbafebe2f84efce21a3a33c4bb
Author: Karn Seth <[email protected]>
Date:   Thu Feb 11 18:18:59 2021 +0000

    adds shanks discrete log algorithm

commit 842f43b08cecba36f8e6c2d94d7467c3b7338397
Author: Karn Seth <[email protected]>
Date:   Thu Jan 14 16:06:54 2021 +0000

    adds hash_type to ec_point_util

commit 52c605f88b976d3ec386b09af0e72dec1e40d9a4
Author: Karn Seth <[email protected]>
Date:   Wed Jan 13 19:17:50 2021 +0000

    adds libraries for status testing, slight modifications to bignum

commit 884e999bde8f6c48e81c239eed95b7fcbaeb70ca
Author: Karn Seth <[email protected]>
Date:   Sun Jan 3 21:12:22 2021 +0000

    removes redundant files

commit 484a85c6302d3026ceb8643abff06490f2005de1
Author: Karn Seth <[email protected]>
Date:   Tue Dec 22 00:33:23 2020 +0000

    migrate commandlineflags to absl::flag

commit 458ea22489f7e0bca193af3b3049a035249d2e84
Merge: 99fbcf7 ee2c581
Author: karnseth <[email protected]>
Date:   Mon Dec 7 12:40:14 2020 -0500

    Merge pull request #20 from schoppmp/windows

    Fix build on Windows

commit ee2c581454fd895d9928fe27b7ba0d0ebfd8fda2
Author: Phillipp Schoppmann <[email protected]>
Date:   Wed Dec 2 10:16:17 2020 +0100

    Fix build on Windows

commit 99fbcf79c5aded3694973086651f535d08a645c5
Author: Karn Seth <[email protected]>
Date:   Mon Nov 30 15:29:42 2020 +0000

    incorporates absl::string_view where appropriate

commit aa2d68e68193547e88a120c667e173662abd7478
Author: Karn Seth <[email protected]>
Date:   Mon Nov 16 21:27:16 2020 +0000

    uses absl status and statusor

commit b040c117663747c7d0f3fae082a613ca8bf60943
Author: Karn Seth <[email protected]>
Date:   Tue May 12 13:35:01 2020 -0400

    adds missing BUILD rules, updates grpc deps version

commit 6daf1c5f48276c624e4275751992395341902c67
Author: Karn Seth <[email protected]>
Date:   Tue May 12 11:41:45 2020 -0400

    adds commutative elgamal and ec point util

commit 53ca1e2373512880a427adbfb58705827b8c55c6
Author: Karn Seth <[email protected]>
Date:   Mon Apr 27 13:17:31 2020 -0400

    changes default curve to NIST P-256

commit d9bd7fe9821f72640234cf447215c082d95f383a
Author: Karn Seth <[email protected]>
Date:   Mon Apr 27 13:11:30 2020 -0400

    syncs various refactoring changes

commit eaec47fa64619e9a6467630663c7af70a4eadfcc
Author: Karn Seth <>
Date:   Mon Apr 20 14:23:45 2020 -0400

    Removes workarounds from README

commit 391f0934e537e4399365865f1421c6b8f757b966
Merge: 4e1c4fd 646f563
Author: karnseth <[email protected]>
Date:   Mon Apr 20 12:33:05 2020 -0400

    Merge pull request #11 from schoppmp/fix-build

    Fix build with Bazel >= 2

commit 646f563e2092d40e39c5a0c80fd839f0a958095f
Author: Phillipp Schoppmann <[email protected]>
Date:   Mon Apr 20 15:12:29 2020 +0200

    Don't load grpc_test_only_deps

commit a5219c2470cef647bfdd5ecdd7051b8c770579b3
Author: Phillipp Schoppmann <[email protected]>
Date:   Mon Apr 20 15:04:34 2020 +0200

    Add comments in WORKSPACE

commit 975b14f07a071726840ee8c8bcddde61a62e6342
Author: Phillipp Schoppmann <[email protected]>
Date:   Fri Apr 17 10:27:38 2020 -0700

    Fix build with Bazel >= 2

commit 4e1c4fda242f11ccad9633abb06192fa36a4b94c
Author: mihaelaion-code <[email protected]>
Date:   Thu Nov 7 15:23:12 2019 +0100

    Added note to build with Bazel 0.28.1.

commit 375be83109e10b32441483dbd0f1ac493488d197
Author: Kevin Yeo <[email protected]>
Date:   Mon Aug 5 10:40:10 2019 -0400

    Update README.

commit 2506f959f6da14211527aab7c69508f2300e188b
Author: Kevin Yeo <[email protected]>
Date:   Mon Aug 5 09:43:55 2019 -0400

    Add SHA256 option for underlying hash function and refactor code.

commit 040ac897e8d3080fa57e550eb85239fb78728855
Merge: d03baa0 6fb131c
Author: mihaelaion-code <[email protected]>
Date:   Thu Jun 27 10:38:37 2019 +0200

    Merge pull request #1 from WalterHub/master

    Fixes typo in csv file name

commit 6fb131c86d3359b949e0de05c58fe38d80d63cae
Author: Walter Poupore <[email protected]>
Date:   Thu Jun 20 11:41:36 2019 -0700

    Fixes typo in csv file name

commit d03baa047de48c134bcfae8a16774752a73267bf
Author: mihaelaion-code <[email protected]>
Date:   Wed Jun 19 15:02:51 2019 +0200

    Update README.md

commit 5b8a532eeb81aa756e57e96de2c73a3fc907d294
Author: mihaelaion-code <[email protected]>
Date:   Wed Jun 19 14:40:52 2019 +0200

    Add files via upload

    Private Join and Compute code

Change-Id: I611f37b07fe38ef6c6eeeceffb9bf351659e0ac2

1609 files changed

tree: 03f56d7cf2cd47e9d61363924e3c06ba0acc8d12

README.md

Private Join and Compute

This project contains an implementation of the “Private Join and Compute” functionality. This functionality allows two users, each holding an input file, to privately compute the sum of associated values for records that have common identifiers.

In more detail, suppose a Server has a file containing the following identifiers:

Identifiers
Sam
Ada
Ruby
Brendan

And a Client has a file containing the following identifiers, paired with associated integer values:

Identifiers	Associated Values
Ruby	10
Ada	30
Alexander	5
Mika	35

Then the Private Join and Compute functionality would allow the Client to learn that the input files had 2 identifiers in common, and that the associated values summed to 40. It does this without revealing which specific identifiers were in common (Ada and Ruby in the example above), or revealing anything additional about the other identifiers in the two parties' data set.

Private Join and Compute is a variant of the well-studied Private Set Intersection functionality. We sometimes also refer to Private Join and Compute as Private Intersection-Sum.

How to run the protocol

In order to run Private Join and Compute, you need to install Bazel, if you don't have it already. Follow the instructions for your platform on the Bazel website.

You also need to install Git, if you don't have it already. Follow the instructions for your platform on the Git website.

Once you've installed Bazel and Git, open a Terminal and clone the Private Join and Compute repository into a local folder:

git clone https://github.com/google/private-join-and-compute.git

Navigate into the private-join-and-compute folder you just created, and build the Private Join and Compute library and dependencies using Bazel:

cd private-join-and-compute
bazel build //private_join_and_compute:all

(All the following instructions must be run from inside the private-join-and-compute folder.)

Next, generate some dummy data to run the protocol on:

bazel-bin/private_join_and_compute/generate_dummy_data --server_data_file=/tmp/dummy_server_data.csv \
--client_data_file=/tmp/dummy_client_data.csv

This will create dummy data for the server and client at the specified locations. You can look at the files in /tmp/dummy_server_data.csv and /tmp/dummy_client_data.csv to see the dummy data that was generated. You can also change the size of the dummy data generated using additional flags. For example:

bazel-bin/private_join_and_compute/generate_dummy_data \
--server_data_file=/tmp/dummy_server_data.csv \
--client_data_file=/tmp/dummy_client_data.csv --server_data_size=1000 \
--client_data_size=1000 --intersection_size=200 --max_associated_value=100

Once you've generated dummy data, you can start the server as follows:

bazel-bin/private_join_and_compute/server --server_data_file=/tmp/dummy_server_data.csv

The server will load data from the specified file, and wait for a connection from the client.

Once the server is running, you can start a client to connect to the server. Create a new terminal and navigate to the private-join-and-compute folder. Once there, run the following command to start the client:

bazel-bin/private_join_and_compute/client --client_data_file=/tmp/dummy_client_data.csv

The client will connect to the server and execute the steps of the protocol sequentially. At the end of the protocol, the client will output the Intersection Size (the number of identifiers in common) and the Intersection Sum (the sum of associated values). If the protocol was successful, both the server and client will shut down.

Caveats

Several caveats should be carefully considered before using Private Join and Compute.

Security Model

Our protocol has security against honest-but-curious adversaries. This means that as long as both participants follow the protocol honestly, neither will learn more than the size of the intersection and the intersection-sum. However, if a participant deviates from the protocol, it is possible they could learn more than the prescribed information. For example, they could learn the specific identifiers in the intersection. If the underlying data is sensitive, we recommend performing a careful risk analysis before using Private Join and Compute, to ensure that neither party has an incentive to deviate from the protocol. The protocol can also be supplemented with external enforcement such as code audits to ensure that no party deviates from the protocol.

Maliciously Chosen Inputs

We note that our protocol does not authenticate that parties use “real” input, nor does it prevent them from arbitrarily changing their input. We suggest careful analysis of whether any party has an incentive to lie about their inputs. This risk can also be mitigated by external enforcement such as code audits.

Leakage from the Intersection-Sum.

While the Private Join and Compute functionality is supposed to reveal only the intersection-size and intersection-sum, it is possible that the intersection-sum itself could reveal something about which identifiers were in common.

For example, if an identifier has a very unique associated integer values, then it may be easy to detect if that identifier was in the intersection simply by looking at the intersection-sum. One way this could happen is if one of the identifiers has a very large associated value compared to all other identifiers. In that case, if the intersection-sum is large, one could reasonably infer that that identifier was in the intersection. To mitigate this, we suggest scrubbing inputs to remove identifiers with “outlier” values.

Another way that the intersection-sum may leak which identifiers are in the intersection is if the intersection is too small. This could make it easier to guess which combination of identifiers could be in the intersection in order to yield a particular intersection-sum. To mitigate this, one could abort the protocol if the intersection-size is below a certain threshold, or to add noise to the output of the protocol.

(Note that these mitigations are not currently implemented in this open-source library.)

Disclaimers

This is not an officially supported Google product. The software is provided as-is without any guarantees or warranties, express or implied.