Some questions about performance of APSI

[qwerfdg]

Hi! I am trying to use APSI framework and have read relevant papers. And I'm confused about the time consuming of each part of the algorithm.

1. It seems that most of the time spent is concentrated in "generating bin bundle caches". Does the algorithm only calculate polynomials and insert them into the cuckoo hash here? As far as I am concerned, the public key encryption required by OPRF and homomorphic multiplication are expensive in cryptography. Why does polynomial calculation cost the most instead of OPRF carrying out by sender or homomorphic multiplication online?
2. Compared to "unlabeled model", "generating bin bundle caches" cost more in "labeled model". Perhaps it is that "Partial Item Collisions". Is there any more reason for this problem?

[kimlaine]

Here is some explanation:

1. It's true that the "preprocessing" phase (inserting data into the SenderDB) is generally the most time-consuming part. Our thinking in designing this was that this computation only needs to be done once, because it's updateable: adding or removing items from SenderDB can be done without having to re-process the whole thing. It's slow because to insert just one single item we need to perform multiple searches for its components from the different BinBundles to see where we have room to insert. The are some obvious faster ways to do this insertion, but they result in less dense packing of the data, and therefore have an impact on the online running time and communication, which we hope to avoid.
2. Labeled mode insertion is much slower because it requires interpolation polynomials to be computed, which is much more expensive than computing coefficients of the symmetric polynomials that are used as the "matching" polynomials.

[qwerfdg]

OK, I see. Thanks a lot!