search

microsoft / APSI

APSI is a C++ library for Asymmetric (unlabeled or labeled) Private Set Intersection.
MIT License
185 stars 42 forks source link

senderDB size related #48

Closed kexuedaishu closed 1 year ago

kexuedaishu commented 1 year ago

Everything with this project seems to be designed carefully and achieve good online performance, except that the size of senderDB is quite large when label is long. I understand that the encrypted labels and multiple of them are saved, but is there a way to compress the senderDB size for the sake of storage? Maybe compression techniques will not affect online performance as well.

jtakeshi-nd commented 1 year ago

In the paper (https://dl.acm.org/doi/pdf/10.1145/3460120.3484760), the authors note that their HElib implementation is the one they use to focus more on improving communication overhead. This is because SEAL's plaintext parameter selection is much more rigid than in HElib or other libraries, and is not amenable to choosing parameters friendly to the optimization of low-depth exponentiation via Frobenius automorphisms. Thus, the SEAL implementation doesn't focus as much on communication overhead, but is primarily for making comparisons with related work.

kimlaine commented 1 year ago

The only way really to compress the SenderDB is by using the SenderDB::strip function. This removes all unnecessary data structures, but prevents the SenderDB from being modified any further (adding, deleting, or changing items/labels). If you do this and ensure there are no changes to the SenderDB, then you can probably also set the label encryption nonce to be 0 bytes, which will reduce the size a little.