APSI: C++ library for Asymmetric PSI

September 21, 2026 · View on GitHub

Introduction
- (Unlabeled) PSI and Labeled PSI
- Sender and Receiver
How APSI Works
Using APSI
Building APSI
Command-Line Interface (CLI)
Acknowledgments
Contributing

Introduction

(Unlabeled) PSI and Labeled PSI

Private Set Intersection (PSI) refers to a functionality where two parties, each holding a private set of items, can check which items they have in common without revealing anything else to each other. Upper bounds on the sizes of the sets are assumed to be public information and are not protected.

The APSI (Asymmetric PSI) library provides a PSI functionality for asymmetric set sizes based on the protocol described in eprint.iacr.org/2021/1116. For example, in many cases one party may hold a large dataset of millions of records, and the other party wishes to find out whether a single particular record or a small number of records appear in the dataset. We refer to this as APSI in unlabeled mode.

In many cases, however, the querier wishes to also retrieve some information per each record that matched. This can be viewed as a key-value store with a privacy preserving batched query capability. We use the terminology item and label to refer to the key and the value in such a key-value store, and call this APSI in labeled mode.

Note: Unless labeled mode is actually needed, it will be much more efficient (in both communication and computation) to use the unlabeled mode.

Sender and Receiver

We use the terminology sender and receiver to denote the two parties in the APSI protocol: a sender sends the result to the receiver. For example, in a common use case where a server hosts a look-up table that multiple clients can query with encrypted records. In this case the server acts as the sender, and the clients act as (independent) receivers.

How APSI Works

Homomorphic Encryption

APSI uses a relatively new encryption technology called homomorphic encryption that allows computations to be performed directly on encrypted data. Results of such computations remain encrypted and can be only decrypted by the owner of the secret key. There are many homomorphic encryption schemes with different properties; APSI uses the BFV encryption scheme implemented in the Microsoft SEAL library.

Computation on Encrypted Data

Microsoft SEAL enables computation representable with arithmetic circuits (e.g., additions and multiplications modulo a prime number) with limited depths rather than arbitrary computation on encrypted data. These computations can be done in a batched manner, where a single Microsoft SEAL ciphertext encrypts a large vector of values, and computations are done simultaneously and independently on every value in the vector; batching is crucial for APSI to achieve good performance.

Noise Budget

The capacity of computation that can be done on encrypted data is tracked by noise budget that each ciphertext carries. A freshly encrypted ciphertext has a certain amount of noise budget which is then consumed by computations – particularly multiplications. A ciphertext can no longer be decrypted correctly once its noise budget is fully consumed. To support computations of larger multiplicative depths, it is necessary to start with a larger initial noise budget, which can be done through appropriate changes to the encryption parameters.

Encryption Parameters

Homomorphic encryption schemes, such as BFV, are difficult to configure for optimal performance. APSI requires the user to explicitly provide the Microsoft SEAL encryption parameters. So we need to describe them here briefly. For much more details, we refer the reader to the examples in the Microsoft SEAL repository. We describe three important encryption parameters that the user should be familiar with.

plain_modulus is the easiest to understand. It must be a prime number congruent to 1 modulo 2 * poly_modulus_degree and defines the finite field datatype that the BFV scheme encrypts. For example, if plain_modulus is 65537 – a 17-bit prime – then the scheme encrypts integers modulo 65537, and computations on encrypted data preserves integer arithmetic modulo 65537. A larger plain_modulus leads to faster noise budget consumption. It is recommended to design computation with as small a plain_modulus as possible.

poly_modulus_degree is a positive power-of-two integer that determines how many integers modulo plain_modulus can be encoded into a single Microsoft SEAL plaintext; typical values are 2048, 4096, 8192, and 16384. It is now easy for the reader to appreciate the value of batching: computation of thousands of values can be done at the cost of one computation on encrypted data. poly_modulus_degree also affects the security level of the encryption scheme: if other parameters remain the same, a bigger poly_modulus_degree is more secure.

coeff_modulus is a set of prime numbers that determine the noise budget of a freshly encrypted ciphertext. In Microsoft SEAL the coeff_modulus primes are rarely given explicitly by values but instead by bit counts – the library can create them. In APSI it is beneficial to have as few primes in coeff_modulus as possible; using 2 – 8 primes is probably reasonable. A single prime is enough only when the receiver sends every power the sender needs, so that the sender never relinearizes; the smallest parameter sets in parameters/ do exactly that. The individual primes can be up to 60 bits. The noise budget depends linearly on the total bit count of the primes. coeff_modulus also affects the security level of the encryption scheme: if other parameters remain the same, a bigger total bit count is less secure. Thus, to obtain more computing capability, i.e., more noise budget, one needs to increase the total bit count of the coeff_modulus, and consequently may have to increase poly_modulus_degree for security. This will subsequently have an impact on the batching capability, so the computation itself may now change.

Fortunately, Microsoft SEAL prevents the user from accidentally setting insecure parameters. It checks that, for the given poly_modulus_degree, the total coeff_modulus bit count does not exceed the following bounds:

poly_modulus_degree	max coeff_modulus bit count
1024	27
2048	54
4096	109
8192	218
16384	438
32768	881

In APSI, the user will need to explicitly provide the coeff_modulus prime bit counts, so the table above will be of great help in avoiding unnecessary exceptions being thrown by Microsoft SEAL.

Theory

Naive Idea

The basic idea of APSI is as follows. Suppose the sender holds a set {Y_i} of items – each an integer modulo plain_modulus – and the receiver holds a single item X – also an integer modulo plain_modulus.

Note on notation: This section uses X for the receiver's (query) item and {Y_i} for the sender's set. This is transposed relative to the paper, where X denotes the sender's (larger) set and Y the receiver's set. Only the choice of letters differs; the protocol is identical.

The receiver can choose a secret key, encrypts X to obtain a ciphertext Q = Enc(X), and sends it over to the sender. The sender can now evaluate the matching polynomial M(x) = (x - Y_0)(x - Y_1)...(x - Y_n) at x = Q. Here the values Y_i are unencrypted data held by the sender. Due to the capabilities of homomorphic encryption, M(Q) will hold an encryption of (X - Y_0)(X-Y_1)...(X-Y_n) which is zero if X matches one of the sender's items and non-zero otherwise. The sender who performs computation on X – encrypted data – will not be able to know this result due to the secret key being held only by the receiver.

One problem with the above is that the computation has an enormously high multiplicative depth. It is not uncommon for the sender to have millions or even hundreds of millions of items. This would require a very high initial noise budget and subsequently very large encryption parameters with an impossibly large computational overhead.

Lowering the Depth

The first step towards making this naive idea practical is to figure out ways of lowering the multiplicative depth of the computation. First, notice that the sender can split up its set into S equally sized parts and evaluate the matching polynomial independently on each of the parts, producing S results {M_i(Q)}. All of these results must be sent back to the receiver, so the sender-to-receiver communication has increased by a factor of S. Nevertheless, this turns out to be a really valuable trick in helping reduce the size of the encryption parameters.

The second step is to use batching in Microsoft SEAL. Per each of the S parts described above, the sender can further split its set into poly_modulus_degree many equally sized parts, and the receiver can batch-encrypt its item into a single batched query ciphertext Q = Enc([ X, X, ..., X ]). Now, the sender can evaluate vectorized versions of the matching polynomials on Q, improving the computational complexity by a factor of poly_modulus_degree and significantly reducing the multiplicative depth.

The third step is to have the receiver compute higher powers of its query, encrypt those separately, and send them all to the sender. Suppose the matching polynomials that the sender hopes to evaluate have degree d. Then, the sender will need ciphertexts encrypting all powers of the receiver's query, up to power d. Although the sender can always compute Q^2, ..., Q^d from a given Q, the computation can have high multiplicative depth even with the improvements described above. Instead, suppose the receiver precomputes certain powers of its query, encrypts them, and sends them to the sender in addition to Q. If the powers are chosen appropriately, the sender can compute all remaining necessary powers of Q with a much lower depth circuit. The receiver-to-sender communication cost increases by a factor of how many powers were sent. It is almost always beneficial to use this trick to reduce the multiplicative depth of the matching polynomials, and subsequently the size of the encryption parameters.

Cuckoo Hashing

The above techniques scale poorly when the receiver has more items. Indeed, it would seem that the query needs to be repeated once per receiver's item, so if the receiver holds 10,000 items, the communicational and computational cost would massively increase.

There is a well-known technique for fixing this issue. We use a hashing technique called cuckoo hashing, as implemented in the Kuku library. Cuckoo hashing uses multiple hash functions (usually 2 – 4) to achieve very high packing rates for a hash table with a bin size of 1. Instead of batch-encrypting its single item X into a query Q by repeating it into each batching slot, the receiver uses cuckoo hashing to insert multiple items {X_i} into a hash table of size poly_modulus_degree (the batch size) and bin size 1. The cuckoo hash table is then encrypted to form a query Q, and is sent to the sender.

The sender uses all the different cuckoo hash functions to hash its items {Y_i} into a large hash table with arbitrarily sized bins; notably, it does not use cuckoo hashing. In fact, it inserts each item multiple times – once per each cuckoo hash function. This is necessary, because the sender cannot know which of the hash functions the receiver's cuckoo hashing process ended up using for each item. If the number of cuckoo hash functions is H, then clearly this effectively increases the sender's set size by a factor of H. After hashing its items the sender breaks down its hash table into parts as described above in Lowering the Depth, and proceeds as before upon receiving Q.

The benefit is enormous. Cuckoo hashing allows dense packing of the receiver's items into a single query Q. For example, the receiver may be able to fit thousands of query items {X_i} into a single query Q, and the sender can perform the matching for all of these query items simultaneously, at the cost of increasing the sender's dataset size by a small factor H.

Large Items

Recall how each item had to be represented as an integer modulo plain_modulus. Unfortunately, plain_modulus has usually 16 – 30 bits and always less than 60 bits in Microsoft SEAL. Larger plain_modulus also causes larger noise budget consumption, lowering capability of computing on encrypted data. On the other hand, we may need to support arbitrary length items. For example, an item may be an entire document, an email address, a street address, or a driver's license number. Two tricks make this possible.

The first trick is to apply a hash function to all items on both the sender's and receiver's side, so that they have a capped standard length. We hash to 128 bits and truncate the hash to a shorter length (large enough to be collision-resistant) as necessary. The shortest item length we support (after truncation) is 80 bits, which is still far above the practical sizes of plain_modulus.

The second trick is to break up each item into multiple parts and encode them separately into consecutive batching slots. Namely, if plain_modulus is a B-bit prime, then we write only B - 1 bits of an item into a batching slot and the next B - 1 bits into the next slot. One downside is that a batched plaintext/ciphertext now only holds a fraction of poly_modulus_degree items. For example, if plain_modulus is a 21-bit prime, then 4 slots could encode an item of length 80, and the query ciphertext Q (and its powers) can encrypt up to poly_modulus_degree / 4 of the receiver's items. The receiver now queries substantially fewer items than before. The solution is to decouple the cuckoo hash table size from the poly_modulus_degree and simply use two or more ciphertexts to encrypt {X_i} (and their powers).

OPRF

Unfortunately, the above approach reveals more than whether there is a match:

It allows the receiver to learn if parts of its query matched;
The result of the matching polynomial reveals information about the sender's data, even when there is no match. These are significant issues and unacceptable.

The solution is to use an Oblivious Pseudo-Random Function, or OPRF for short. An OPRF can be thought of as a keyed hash function OPRF(s, -) that only the sender knows; here s denotes the sender's key. Further, the receiver can obtain OPRF(s, X) without learning the function OPRF(s, -) or the key s, and without the sender learning X.

The way to do this is simple. The receiver hashes its item X to an elliptic curve point A in some cryptographically secure elliptic curve. Next, the receiver chooses a secret number r, computes the point B = rA, and sends it to the sender. The sender uses its secret s to compute C = sB, and sends it to back to the receiver. Upon receiving C, the receiver computes the inverse r^(-1) modulo the order of the elliptic curve, and further computes r^(-1) C = r^(-1) srA = sA. The receiver then extracts the OPRF hash value OPRF(s, X) from this point, for example by hashing its x-coordinate to an appropriate domain.

The sender knows s, so it can simply replace its items {Y_i} with {OPRF(s, Y_i)}. The receiver needs to communicate with the sender to obtain {OPRF(s, X_i)}; once the receiver has received these values, the protocol can proceed as described above. With OPRF, the problem of the receiver learning whether parts of its query matched goes away. Since all the items are hashed with a hash function known only by the sender, the receiver will benefit nothing from learning parts of the sender's hashed items. In fact, the sender's dataset is not private information and could in principle be sent in full to the receiver. Homomorphic encryption only protects the receiver's data.

There is one further detail that must be mentioned here. We choose OPRF(s, -) to have a 256-bit output and denote its first 128 bits by ItemHash(s, -). Instead of {OPRF(s, X_i)} we use {ItemHash(s, X_i)} as the items; the reason will be given later in Label Encryption.

Paterson-Stockmeyer

In some cases it is beneficial for the sender to use the Paterson-Stockmeyer algorithm instead for evaluating the matching and label polynomials. Consider a simple example where the matching polynomial happens to be

M(x) = 1 + 2x + 3x^2 + 4x^3 + 5x^4 + 6x^5 + 7x^6 + 8x^7 + 9x^8 + 10x^9 + 11x^10 + 12x^11 + 13x^12 + 14x^13 + 15x^14.

To evaluate M(Q) for an encrypted query Q=Enc(X), the sender must first compute all encrypted powers of X up to X^14 from some number of source powers the receiver sends to the sender (see Lowering the Depth). Next, the encrypted powers of X are multiplied with the encrypted coefficients of M and the results are added together. It is important to note that the first step (computing all powers) involves a lot of ciphertext-ciphertext multiplications, while the second step (multiply with coefficients and adding) involves only ciphertext-plaintext multiplications, which are much faster than ciphertext-ciphertext multiplications. If the sender splits it dataset into S equal parts (see Lowering the Depth), then the powers need to be computed only once and can be used repeatedly for each of the S parts.

Now consider the following approach, which is a special case of the Paterson-Stockmeyer algorithm. The polynomial M(x) can be alternatively written as:

M(x) =     (1 + 2x + 3x^2 + 4x^3) +
        x^4(5 + 6x + 7x^2 + 8x^3) +
        x^8(9 + 10x + 11x^2 + 12x^3) +
       x^12(13 + 14x + 15x^2 + 0x^3).

To evaluate M(Q), the sender needs to compute all encrypted powers of X up to X^3, and also X^4, X^8, and X^12: a total of 6 powers, as opposed to the 14 powers needed above. Next the sender needs to evaluate the four degree-3 polynomials by computing ciphertext-plaintext multiplications with the appropriate powers and adding up the terms. Then it needs to multiply the degree-3 polynomial results obtained above with appropriate powers of X^4 (either X^4, X^8, or X^12) and add up the results. One difference to the earlier approach is the number of ciphertext-ciphertext multiplications: in the first approach the number is 14 minus the number of precomputed powers the receiver sent; in the second approach it is 6 minor the number of precomputed powers the receiver sent. Another key difference is that the number of costly ciphertext-ciphertext multiplications is now proportional to S.

We decided to group the terms above into degree-3 polynomials, but we could have chosen to use either lower or higher degree polynomials instead. Different choices result in different communication-computation trade-offs. We refer to the degree of these inner polynomials as the (Paterson-Stockmeyer) low-degree. As is obvious from above, the sender must also compute powers of low-degree + 1 of the query; we call low-degree + 1 the (Paterson-Stockmeyer) high-degree.

The user may want to ensure that the multiplicative depth of computing the inner polynomials – taking into account an additional level from multiplying by the plaintext coefficients – matches the multiplicative depth of computing the powers of high-degree. This way the last multiplication will be depth-optimal.

False Positives

In some cases the protocol may result in a false positive match. For example, suppose an item is split into P parts, each B - 1 bits long, as in Large Items. In some parameterizations, the sender's hash table bin size K may be so large that the probability of a particular item part being present in a corresponding bin, purely by random chance instead of true match, is rather large. If P is small, the probability of each of the receiver's item's parts being discovered in the corresponding sender's hash table bins becomes non-negligible. If the receiver submits thousands of items per each query, and the protocol is executed many times, a false positive may become a common occurrence.

There are multiple ways of preventing this from happening. The negative logarithm of the false-positive probability for a single receiver's item, against a single bin bundle, is approximately P(B - 1 - log2(K)). Thus, one can reduce the false-positive probability by increasing the plain_modulus and the number of item parts P, or reducing the sender's bin size K.

Reducing K helps less than that formula suggests: a location holding more than K items spills into a further bin bundle, and a match in any of them is reported, so halving K roughly doubles the bundles a query is tested against and nets about P - 1 bits rather than P. See False Positives under PSIParams for the figure a deployment should use.

Practice

We now begin to illustrate how the Theory is implemented in APSI. Our discussion only considers the unlabeled mode; the labeled mode is not very different, and we will discuss it later. For simplicity, we assume that the OPRF step has already been performed, and consider the simplified case where the receiver needs only a single ciphertext (and its powers) to encrypt the query. This could happen, for example, if poly_modulus_degree is 16, each item uses 2 batching slots, and the cuckoo hash table size is 8; these numbers are too small to work in reality, but are helpful to illustrate the concepts. Suppose the receiver wants to perform a query for a vector of items as follows.

Receiver's query vector

[ item92  ]
[ item14  |
[ item79  ]
[ item3   ]
[ item401 ]

After cuckoo hashing, the receiver's view is as follows. The entire vector of size 16 becomes a single Microsoft SEAL ciphertext.

Receiver's cuckoo hash table

[ item79-part1  ]
[ item79-part2  ]
[ empty         ]
[ empty         ]
[ item14-part1  ]
[ item14-part2  ]
[ item92-part1  ]
[ item92-part2  ]  ==>  query-ctxt
[ item401-part1 ]
[ item401-part2 ]
[ empty         ]
[ empty         ]
[ empty         ]
[ empty         ]
[ item3-part1   ]
[ item3-part2   ]

The sender creates one big hash table and then breaks it into several independent bin bundles. The matching polynomials for each bin bundle are evaluated independently on query-ctxt; this is the first idea presented in Lowering the Depth. For simplicity, we ignore the fact that the sender must use all of the cuckoo hash functions to insert each item.

Sender's big hash table

[ item416-part1 | item12-part1  ][ item71-part1  | item611-part1 ]
[ item416-part2 | item12-part2  ][ item71-part2  | item611-part2 ]
[ item125-part1 | item9-part1   ][ item512-part1 | empty         ]
[ item125-part2 | item9-part2   ][ item512-part2 | empty         ]
[ item500-part1 | item277-part1 ][ item14-part1  | item320-part1 ]
[ item500-part2 | item277-part2 ][ item14-part2  | item320-part2 ]
[ item92-part1  | empty         ][ empty         | empty         ]
[ item92-part2  | empty         ][ empty         | empty         ]
[ item498-part1 | item403-part1 ][ item88-part1  | item5-part1   ]
[ item498-part2 | item403-part2 ][ item88-part2  | item5-part2   ]
[ item216-part1 | empty         ][ empty         | empty         ]
[ item216-part2 | empty         ][ empty         | empty         ]
[ item315-part1 | item491-part1 ][ item262-part1 | empty         ]
[ item315-part2 | item491-part2 ][ item262-part1 | empty         ]
[ item100-part1 | item37-part1  ][ item90-part1  | item3-part1   ]
[ item100-part2 | item37-part2  ][ item90-part2  | item3-part2   ]

\-------------------------------/\-------------------------------/
           Bin bundle 1                     Bin bundle 2

The sender's table is created by first starting with a single bin bundle. Imagine first item416 is inserted and it happens to land in the very first bin of the hash table. Next suppose we add item500, item125, item12, item9, and finally item512 into the bins as shown in the diagram.

APSI allows to specify how many items the sender can fit (horizontally) into each bin bundle. For the sake of this example, we shall assume that this value is 2, but in reality it would be larger.

Once more room is needed, a new bin bundle is created. The sender started with only Bin bundle 1, but item512 would land in the same bin as item125 and item9, which is already full according to our bound of 2. Hence, APSI creates Bin bundle 2 and inserts item512 into it. Next, item277 is inserted into Bin bundle 1 since there is still room for it. In the end, we may end up with dozens or hundreds of bin bundles, and some of the last bin bundles to be added may be left with many empty locations.

For the matching, the encrypted query query-ctxt is matched – in encrypted form – against both Bin bundle 1 and Bin bundle 2, producing results result-ctxt-1 and result-ctxt-2 which are sent back to the receiver. The receiver decrypts the results and finds a result as follows.

Receiver decrypting the result

                    [ item79-no-match  ]                            [ item79-no-match  ]
                    [ empty            ]                            [ empty            ]
                    [ item14-no-match  ]                            [ item14-match     ]
result-ctxt-1  ==>  [ item92-match     ]        result-ctxt-2  ==>  [ item92-no-match  ]
                    [ item401-no-match ]                            [ item401-no-match ]
                    [ empty            ]                            [ empty            ]
                    [ empty            ]                            [ empty            ]
                    [ item3-no-match   ]                            [ item3-match      ]

APSI computes the logical OR of the match values for each result ciphertext and orders the results according to the order of the items appearing in the original query producing, for example, a result vector as follows. The order of the items in the query is arbitrary and irrelevant.

Receiver's query vector      Receiver's result vector

[ item92  ]                  [ match    ]
[ item14  ]                  [ match    ]
[ item79  ]                  [ no-match ]
[ item3   ]                  [ match    ]
[ item401 ]                  [ no-match ]

The receiver, in this case, concludes that item92, item14, and item3 are all present in the sender's database, whereas the other items are not.

A few important details are omitted from the description above. First, the original items on either side are never inserted directly into the APSI protocol, but instead their OPRF hashes are used.

Second, the sender needs to insert each item multiple times, once using each of the cuckoo hash functions. For example, if three cuckoo hash functions are used, the sender would insert, e.g., Hash1(item92), Hash2(item92), and Hash3(item92). The receiver, on the other hand, has inserted only Hash?(item92), where Hash? is one of the three hash functions; in any case, the match will be discovered. Thus, our diagram above is misleading: we should have used names like item92-hash1-part1.

Third, as explained in Large Items, in many cases the receiver's query consists of multiple ciphertexts – not just one like above. For example, suppose we use a cuckoo hash table of size 32, instead of size 8. Now a single plaintext cannot encode the receiver's query anymore. Instead, the query is broken into 4 ciphertexts, each encoding a contiguous chunk of the bigger cuckoo hash table.

Receiver's cuckoo hash table

[ item79-part1  ]
[ item79-part2  ]
[ empty         ]
[ empty         ]
[ item14-part1  ]
[ item14-part2  ]
[ item92-part1  ]
[ item92-part2  ]  ==>  query-ctxt0
[ item401-part1 ]
[ item401-part2 ]
[ empty         ]
[ empty         ]
[ empty         ]
[ empty         ]
[ item3-part1   ]
[ item3-part2   ]

[ ...           ]  ==>  query-ctxt1

[ ...           ]  ==>  query-ctxt2

[ ...           ]  ==>  query-ctxt3

A similar breakdown takes place on the sender's side, creating a jagged array of bin bundles. Here is an example of what the sender's view could be.

                +------------++------------++------------+
                |            ||            ||            |
Bundle index 0  | Bin bundle || Bin bundle || Bin bundle |
                |            ||            ||            |
                +------------++------------++------------+
                +------------++------------+
                |            ||            |
Bundle index 1  | Bin bundle || Bin bundle |
                |            ||            |
                +------------++------------+
                +------------++------------++------------++------------+
                |            ||            ||            ||            |
Bundle index 2  | Bin bundle || Bin bundle || Bin bundle || Bin bundle |
                |            ||            ||            ||            |
                +------------++------------++------------++------------+
                +------------++------------++------------+
                |            ||            ||            |
Bundle index 3  | Bin bundle || Bin bundle || Bin bundle |
                |            ||            ||            |
                +------------++------------++------------+

When the sender receives query-ctxt0, it must compute the matching for each bin bundle at bundle index 0. Similarly, query-ctxt1 must be matched against each bin bundle at bundle index 1, and so on. The number of result ciphertexts obtained by the receiver will be equal to the total number of bin bundles held by the sender; the client cannot know this number in advance.

Labeled Mode

Basic Idea

The labeled mode is not too different but requires some extra explanation. The receiver, in addition to learning whether its query items are in the sender's set, will learn data the sender has associated to these items. One can think of this as a key-value store with privacy-preserving querying.

To understand how the labeled mode works, recall from Basic Idea how the matching polynomial M(x) outputs either an encryption of zero or an encryption of a non-zero value when being evaluated at the receiver's encrypted item Q. In the labeled mode, the sender creates another polynomial L(x), the label interpolation polynomial, that has the following property: if {(Y_i, V_i)} denotes the sender's set of item-label pairs, then L(Y_i) = V_i. Upon receiving Q, the sender computes the ciphertext pair (M(Q), L(Q)) and returns them to the receiver. The receiver decrypts the pair and checks whether the first value decrypts to zero. If it does, the second value decrypts to the corresponding label.

Large Labels

One immediate issue is that all encrypted computations happen modulo the plain_modulus, but the sender's labels might be much longer than that. This was a problem for the items, and was resolved in Large Items by hashing the items first to a bounded size (80 – 128 bits) and then using a sequence of batching slots to encode the items. This solution works to some extent for labels as well. Namely, the labels can be broken into parts similarly to how the items are, and for each part we can form a label interpolation polynomial that outputs that part of the label when evaluated at the corresponding part of the item.

This is not yet a fulfilling solution, because our items do not have a fixed size and are fairly short anyway (up to 128 bits). Labels that are longer than the items can be broken into multiple parts each of the length of the item. For each part we can construct a separate label interpolation polynomial, evaluate them all at the encrypted query, and return each encrypted result to the receiver. The receiver decrypts the results and concatenates them to recover the label for those items that were matched.

Label Encryption

There is a serious issue with the above approach that must be resolved. Recall how we used OPRF to prevent partial (or full) leakage of the sender's items to the receiver: given an item Y, the matching polynomial is not actually computed for Y itself, but rather for ItemHash(s, Y), which denoted the first 128 bits of the item's OPRF value OPRF(s, Y). This means that the label interpolation polynomial L should actually have the property that L(ItemHash(s, Y_i)) = V_i for each of the sender's items Y_i. However, if the receiver can guess a part of some ItemHash(s, Y_i) it can use it to query for the corresponding part of the label for that item, which is unacceptable since the receiver does not actually know the item Y_i.

To solve this issue, the sender uses a symmetric encryption function Enc(<input>, <key>, <nonce>) to encrypt the labels V_i using keys derived from OPRF(s, Y_i). Specifically, as the encryption key LabelKey(s, Y_i) for the label V_i corresponding to an item Y_i we use the remaining 128 bits of the 256-bit output of OPRF(s, Y_i), so the label we must communicate to the receiver becomes Enc(V_i, LabelKey(s, Y_i), nonce).

There is still a bit of a problem, because the receiver must somehow know the nonce as well. One option is to use a constant or empty nonce. In this case extreme care must be taken, because if an adversary can learn encryptions of two different labels for the same item with the same OPRF key s, then they may be able to learn information about the labels. This can happen, because APSI supports updating labels for items. Another option is to use a long randomly generated nonce – different for each encryption – which the receiver must somehow learn. APSI achieves this by randomly sampling a nonce, concatenating it with the encryption of V_i, and using the concatenation for the interpolation polynomial L. In other words, the sender samples a random nonce for each item Y_i and computes the label interpolation polynomial L such that L(ItemHash(s, Y_i)) = nonce | Enc(V_i, LabelKey(s, Y_i), nonce).

The receiver benefits nothing from learning parts (or all) of the encrypted label unless it also knows the original item. Furthermore, even if the receiver manages to obtain nonce | Enc(V_i, LabelKey(s, Y_i), nonce) by guessing ItemHash(s, Y_i), and in an offline attack enumerates all possible items Y_i (or later learns Y_i through other means), it still cannot obtain the label because LabelKey(s, Y_i) is derived from OPRF(s, Y_i) – not just from Y_i. Of course at this later point the sender may decide to serve a normal query to the receiver for Y_i, in which case the receiver will learn V_i, as it is supposed to.

APSI allows the sender to specify the nonce size in bytes. The default nonce size is set to 16 bytes, but expert users who fully understand the issue may want to use smaller values to achieve improved performance. A nonce size of zero is permitted and makes label encryption deterministic, which saves the nonce bytes on every item. It is safe only for a SenderDB whose labels are never rewritten: encrypting a label for the same item a second time – by updating it, or by removing the item and reinserting it – reproduces the same keystream, and the two ciphertexts together reveal the two labels. The SenderDB constructor warns whenever the nonce is shorter than the default, and warns specifically when it is zero.

Partial Item Collisions

There is one last subtle issue that must be addressed. Recall from Practice how the sender constructs a large hash table and breaks it into a jagged array of bin bundles. In the labeled mode each bin bundle holds not only the item parts in it, but also the corresponding label parts, and the label interpolation polynomials, as described above. The interpolation polynomials are not created for the entire label at a time, but for each part separately, although the encryption is applied to the full item before decomposing it into parts.

Now consider what happens when – by chance – item416-part1 and item12-part1 (as in Practice) are the same. If the corresponding label parts label416-part1 and label12-part1 are different, it will be impossible to create a label interpolation polynomial L, as it cannot output both label416-part1 and label12-part1 on the corresponding item part.

This issue is resolved by checking that label parts do not already appear in the same locations before inserting an item into a bin bundle. If any of them does, the item simply cannot be inserted into that bin bundle, and a new bin bundle for the same bundle index must be created. Note that the problem exists only in the labeled mode and can lead to worse packing rate (items_inserted / theoretical_max) than in unlabeled mode, where no such limitation exists.

Trust Model

APSI is a confidentiality protocol, not an integrity protocol, and the difference matters for how it must be deployed. What the protocol protects is described in OPRF and Label Encryption above. What it does not provide is any assurance about where a response came from. Nothing in a response binds it to the sender – there is no MAC, no signature, and no shared secret between the two parties beyond the OPRF itself.

The practical consequence is that any party able to write to the receiver's connection can make it report an arbitrary set of matches, using nothing but the publicly known PSIParams. A BFV ciphertext whose own coefficients are small decrypts to zero under every key, and a zero result is what APSI reads as a match, so such a forgery needs no key material, no observed traffic, and no involvement from the real sender. The receiver cannot detect it by inspection either: a forged response can match a genuine one on every property the receiver is able to measure.

Deployments must therefore run APSI over a channel that authenticates the sender. The network::ZMQChannel implementations used by the example applications provide no authentication and no encryption; embedders needing either should supply their own transport through network::StreamChannel, which is transport-agnostic by design.

Two further limitations follow from the same root. Labels carry no integrity protection: the label ciphertext is a keystream XOR with no authentication tag, so a party on the connection can apply a chosen difference to a delivered label without detection. And an authenticated channel makes the sender identified, not honest: a sender remains authoritative for its own data and can always answer as though its database contained any item it likes.

One case makes transport encryption matter as much as authentication, and is the reason APSI builds Microsoft SEAL with its no-throw-tran feature rather than letting SEAL reject the ciphertext outright. A label result is produced by evaluating an interpolation polynomial, and when every occupied bin in a bundle holds a single item that polynomial has degree zero. The result is then a constant that the sender cannot blind, because rerandomizing it would require the receiver's public encryption key, which the protocol never transmits. Such a ciphertext is transparent: its plaintext can be read off the wire without the receiver's secret key. What that exposes is the EncryptedLabel described in Label Encryption rather than the label itself, so an eavesdropper who does not already know the item still cannot recover the label, and the matching result is unaffected because its leading coefficient is monic and so never degenerates. A deployment serving labels should nonetheless choose a transport that encrypts as well as authenticates.

What a Peer Can Learn

These two exposures are properties of the protocol rather than of the transport, so an authenticated channel bounds them only by bounding who may query.

An OPRF request is exactly oprf_query_size bytes per item, so its length reveals the receiver's exact item count. Padding a query set up to a fixed bucket size hides this; APSI does not do so automatically.

A peer allowed to query repeatedly can extract the sender's data. The sender holds no key with which to check that the encrypted query powers it receives are consistent, and must evaluate whatever it is given, so a peer supplying chosen values obtains an evaluation oracle for the matching and label polynomials; enough queries recover their coefficients. The sender's item set is non-secret, but in the labeled mode the labels are not, so a deployment serving labels must treat the right to query as a privilege and limit its volume per peer. APSI enforces no such limit itself: it has no notion of a peer identity to attribute queries to, and the routing identifier on a ZeroMQ connection is chosen by the peer and is not authenticated.

Using APSI

Receiver

The apsi::receiver::Receiver class implements all necessary functions to create and send parameter, OPRF, and PSI or labeled PSI queries (depending on the sender), and process any responses received. Most of the member functions are static, but a few (related to creating and processing the query itself) require an instance of the class to be created. All functions and types are in the apsi namespace, so we omit apsi:: from all names below. For simplicity, we also use Receiver to denote apsi::receiver::Receiver.

This same text appears in the receiver.h header file.

Receiver includes functionality to request protocol parameters (PSIParams object) from a sender. This is needed when the receiver does not know what parameters it is supposed to use with a specific sender. In other cases the receiver would know the parameters ahead of time, and can skip this step. In any case, once the receiver has an appropriate PSIParams object, an Receiver can be instantiated. The Receiver constructor automatically creates Microsoft SEAL public and private keys. The public keys are sent to the sender along with every query request, and the private keys are held internally by the Receiver object for decrypting query responses. Receiver::request_query draws a new key pair for each query it sends, so two queries made through it never carry the same public keys and a sender cannot recognize them as coming from one receiver. A caller using the advanced API instead is responsible for calling Receiver::reset_keys between queries, at a point where no query is still in flight: the result of a query in flight is encrypted under the key that rotating would discard.

The class includes two versions of an API to perform the necessary operations. The "simple" API consists of three functions: Receiver::RequestParams, Receiver::RequestOPRF, and Receiver::request_query. However, these functions only support network::NetworkChannel, such as network::ZMQReceiverChannel, for the communication. Other channels, such as network::StreamChannel, are only supported by the "advanced" API.

Each of the three takes an optional trailing std::chrono::milliseconds timeout, defaulting to Receiver::default_receive_timeout (thirty minutes). The timeout bounds how long the sender may stay silent, not how long the query may take: every message received restarts the clock, so a sender that is slow but responsive is never cut off, however large its database. Passing std::chrono::milliseconds::zero() waits indefinitely, which is appropriate only against a sender you trust. All three throw std::runtime_error if that deadline passes, or if the channel receives a message it cannot use.

The advanced API requires many more steps. The full process is as follows:

(optional) Receiver::CreateParamsRequest must be used to create a parameter request. The request must be sent to the sender on a channel with network::Channel::send. The sender must respond to the request and the response must be received on the channel with network::Channel::receive_response. The received Response object must be converted to the right type (ParamsResponse) with the to_params_response function. This function will return nullptr if the received response was not of the right type. A PSIParams object can be extracted from the response.
A Receiver object must be created from a PSIParams object. The PSIParams must match what the sender uses.
Receiver::CreateOPRFReceiver must be used to process the input vector of items and return an associated oprf::OPRFReceiver object. Next, Receiver::CreateOPRFRequest must be used to create an OPRF request from the oprf::OPRFReceiver, which can subsequently be sent to the sender with network::Channel::send. The sender must respond to the request and the response must be received on the channel with network::Channel::receive_response. The received Response object must be converted to the right type (OPRFResponse) with the to_oprf_response function. This function will return nullptr if the received response was not of the right type. Finally, Receiver::ExtractHashes must be called with the OPRFResponse and the oprf::OPRFReceiver object. This function returns std::pair<std::vector<HashedItem>, LabelKeyVector>, containing the OPRF hashed items and the label encryption keys. The LabelKeyVector is an alias for std::vector<LabelKey, apsi::util::wiping_allocator<LabelKey>>; the custom allocator wipes the underlying buffer with apsi::util::secure_zero before freeing it, so per-item label keys do not linger in heap memory after a query completes. Both vectors in this pair must be kept for the next steps.
Receiver::create_query (non-static member function) must then be used to create the query itself. The function returns std::pair<Request, IndexTranslationTable>, where the Request object contains the query itself to be send to the sender, and the IndexTranslationTable is an object associated to this query describing how the internal data structures of the query maps to the vector of OPRF hashed items given to Receiver::create_query. The IndexTranslationTable is needed later to process the responses from the sender. The Request object must be sent to the sender with network::Channel::send. The received Response object must be converted to the right type (QueryResponse) with the to_query_response function. This function will return nullptr if the received response was not of the right type. The QueryResponse contains only one important piece of data: the number of ResultPart objects the receiver should expect to receive from the sender in the next step.
network::Channel::receive_result must be called repeatedly to receive all ResultParts. For each received ResultPart, Receiver::process_result_part must be called to find a std::vector<MatchRecord> representing the match data associated to that ResultPart. Alternatively, one can first retrieve all ResultParts, collect them into a std::vector<ResultPart>, and use Receiver::process_result to find the complete result – just like what the simple API returns. Both Receiver::process_result_part and Receiver::process_result require the IndexTranslationTable and the LabelKeyVector objects created in the previous steps.

Note that the advanced API gives you the receive loop, and with it the responsibility the simple API handles on your behalf. network::Channel::receive_response and network::Channel::receive_result return nullptr for two different reasons: nothing has arrived yet, or a message arrived and was rejected. Only the second records a failure, so network::Channel::receive_failed is what tells them apart. A loop that simply retries on nullptr will wait forever once a malformed message has been consumed, because the data it is waiting for no longer exists. For the same reason such a loop needs a deadline of its own: a sender that accepts a request and then falls silent will otherwise hold the calling thread indefinitely. The simple API does both of these for you, bounded by its timeout argument.

Which of those two reasons can occur depends on the channel. A network::NetworkChannel such as network::ZMQReceiverChannel returns control within a bounded interval whether or not a message arrived, so both reasons are live and a caller-side deadline is effective. network::StreamChannel instead blocks inside the underlying stream's own read and returns only when that read does, so it has no "nothing has arrived yet" return – but for the same reason a deadline checked between receive calls cannot bound a network::StreamChannel that is blocked on a silent peer. Bounding that case requires a stream that does not block indefinitely.

Request, Response, and ResultPart

The Request type is defined in requests.h as an alias for std::unique_ptr<network::SenderOperation>, where network::SenderOperation is a purely virtual class representing either a parameter request (network::SenderOperationParms), an OPRF request (network::SenderOperationOPRF), or a PSI or labeled PSI query request (network::SenderOperationQuery). The types ParamsRequest, OPRFRequest, and QueryRequest are similar aliases to unique pointers of these derived types. The functions to_params_request, to_oprf_request, and to_query_request convert a Request into the specific kind of request, returning nullptr if the Request was not of the right type. Conversely, the to_request function converts a ParamsRequest, OPRFRequest, or QueryRequest into a Request object.

Similarly, the Response type is defined in responses.h as an alias for std::unique_ptr<network::SenderOperationResponse>, along with related type aliases ParamsResponse, OPRFResponse, and QueryResponse, and corresponding conversion functions to_params_response, to_oprf_response, to_query_response, and to_response.

Finally, the ResultPart type is defined in responses.h as an alias for std::unique_ptr<network::ResultPackage>, where network::ResultPackage contains an encrypted result to a query request. Since the query is evaluated independently per each bin bundle (recall Practice), the results for each bin bundle are sent back to the receiver as separate ResultPart objects. The receiver must collect all these together to find the final result, as was described above in Receiver.

The important thing about Request, Response, and ResultPart is that these are the object handled by the network::Channel class member functions send, receive_operation, receive_response, and receive_result (see channel.h). A custom network::Channel must tolerate concurrent calls, because a sender sends result packages from several tasks at once and a receiver receives them on several threads at once; the channels shipped with APSI serialize their sends and receives internally, and a replacement for the sender's result-package send callback must do the same.

Sender

The Sender class implements all necessary functions to process and respond to parameter, OPRF, and PSI or labeled PSI queries (depending on the sender). Unlike the Receiver class, Sender also takes care of actually sending data back to the receiver. Sender is a static class and cannot be instantiated.

All functions and types are in the apsi namespace, so we omit apsi:: from all names below. For simplicity, we also use Sender to denote apsi::sender::Sender, and SenderDB to denote apsi::sender::SenderDB.

This same text appears in the sender.h header file.

Just like Receiver, there are two ways of using Sender. The "simple" approach supports network::ZMQSenderChannel and is implemented in the ZMQSenderDispatcher class in zmq/sender_dispatcher.h. The ZMQSenderDispatcher provides a very fast way of deploying an APSI Sender: it automatically binds to a ZeroMQ socket, starts listening to requests, and acts on them as appropriate.

The advanced Sender API consisting of three functions: RunParams, RunOPRF, and RunQuery. Of these, RunParams and RunOPRF take the request object (ParamsRequest or OPRFRequest) as input. RunQuery requires the QueryRequest to be "unpacked" into a Query object first.

The full process for the sender is as follows:

Create a PSIParams object that is appropriate for the kinds of queries the sender is expecting to serve. Create a SenderDB object from the PSIParams. The SenderDB constructor optionally accepts an existing oprf::OPRFKey object and samples a random one otherwise. It is recommended to construct the SenderDB directly into a std::shared_ptr, as the Query constructor (see below) expects it to be passed as a std::shared_ptr<SenderDB>.
The sender's data must be loaded into the SenderDB with SenderDB::set_data. More data can always be added later with SenderDB::insert_or_assign, or removed with SenderDB::remove, as long as the SenderDB has not been stripped (see SenderDB::strip).
(optional) Receive a parameter request with network::Channel::receive_operation. The received Request object must be converted to the right type (ParamsRequest) with the to_params_request function. This function will return nullptr if the received request was not of the right type. Once the request has been obtained, the RunParams function can be called with the ParamsRequest, the SenderDB, the network::Channel, and optionally a lambda function that implements custom logic for sending the ParamsResponse object on the channel.
Receive an OPRF request with network::Channel::receive_operation. The received Request object must be converted to the right type (OPRFRequest) with the to_oprf_request function. This function will return nullptr if the received request was not of the right type. Once the request has been obtained, the RunOPRF function can be called with the OPRFRequest, the oprf::OPRFKey, the network::Channel, and optionally a lambda function that implements custom logic for sending the OPRFResponse object on the channel.
Receive a query request with network::Channel::receive_operation. The received Request object must be converted to the right type (QueryRequest) with the to_query_request function. This function will return nullptr if the received request was not of the right type. Once the request has been obtained, a Query object must be created from it. The constructor of the Query class verifies that the QueryRequest is valid for the given SenderDB, and if it is not the constructor still returns successfully but the Query is marked as invalid (Query::is_valid() returns false) and cannot be used in the next step. Once a valid Query object is created, the RunQuery function can be used to perform the query and respond on the given channel. Optionally, two lambda functions can be given to RunQuery to provide custom logic for sending the QueryResponse and the ResultPart objects on the channel.

SenderDB

For simplicity, we use SenderDB to denote apsi::sender::SenderDB.

This same text appears in the sender_db.h header file.

A SenderDB maintains an in-memory representation of the sender's set of items and labels (in labeled mode). These items are not simply copied into the SenderDB data structures, but also preprocessed heavily to allow for faster online computation time. Since inserting a large number of new items into a SenderDB can take time, it is not recommended to recreate the SenderDB when the database changes a little bit. Instead, the class supports fast update and deletion operations that should be preferred: SenderDB::insert_or_assign and SenderDB::remove.

The SenderDB constructor allows the label byte count to be specified; unlabeled mode is activated by setting the label byte count to zero. It is possible to optionally specify the size of the nonce used in encrypting the labels, but this is best left to its default value unless the user is absolutely sure of what they are doing.

The SenderDB requires substantially more memory than the raw data would. Part of that memory can automatically be compressed when it is not in use; this feature is enabled by default, and can be disabled when constructing the SenderDB. The downside of in-memory compression is a performance reduction from decompressing parts of the data when they are used, and recompressing them if they are updated.

An update and a query cannot overlap. SenderDB::insert_or_assign and SenderDB::remove hold a writer lock for the whole of their work, including the OPRF hashing they begin with, while answering a query holds a reader lock for as long as the answer takes. An embedder that updates a SenderDB while it serves queries therefore stalls every query for the duration of the update, which for a large batch is not brief. Where that matters, build the new state separately and direct later queries at it, or update while the sender is not serving.

In many cases the SenderDB does not need to be modified after having been constructed, or loaded from disk. The function SenderDB::strip can be called to remove all data that is not strictly needed to serve query requests. A SenderDB that has been stripped cannot be modified, cannot be checked for the presence of specific items, and labels cannot be retrieved from it. A stripped SenderDB can be serialized and deserialized.

PSIParams

The apsi::PSIParams class encapsulates parameters for the PSI or labeled PSI protocol. These parameters are important to set correctly to ensure correct behavior and good performance. All of the concepts behind these parameters have come up in How APSI Works, which we urge the reader to review unless it is absolutely clear to them.

If a parameter set works for specific sender and receiver sets, then it will still run correctly for a smaller or larger sender's set (with asymptotic linear scaling in communication and computation complexity), both in the unlabeled and labeled mode with arbitrary length labels. A larger sender's set does, however, raise the false-positive probability, because more items per location mean more bin bundles to match against; the bound each file in parameters/ meets is tied to the set sizes its name gives. Use sender::SenderDB::log2_fpp to find the figure for the database you actually built. A parameter set does not necessarily work for a larger receiver's set at all.

For simplicity, we use PSIParams to denote apsi::PSIParams.

A PSIParams object contains four kinds of parameters, encapsulated in sub-structs: PSIParams::SEALParams, PSIParams::ItemParams, PSIParams::TableParams, and PSIParams::QueryParams. We shall discuss each separately.

Choosing a Parameter Set

Start with parameters/ rather than with the sub-structs below. Choose one whose first two numbers are at least your sender's set size and your query size, since they are upper bounds. An optional third number is the label byte count, and a trailing -com or -cmp says whether the set is tuned to spend less on communication or on computation. Then build your SenderDB and read sender::SenderDB::log2_fpp(query_item_count) for the query size you actually expect, because the false-positive bound a file meets is tied to the sizes its name gives and a larger sender's set weakens it.

Tune only if no shipped set fits. The parameters are not independent, so the order matters – each step below is constrained by the ones above it, and choosing in a different order means discovering the constraints through exceptions:

poly_modulus_degree, felts_per_item and plain_modulus together. They fix the item length, which must land in [80, 128] bits, and they are what the false-positive probability is made of.
table_size and max_items_per_bin. table_size must be a multiple of floor(poly_modulus_degree / felts_per_item), and max_items_per_bin decides both how much of the false-positive budget each bin bundle spends and how many bin bundles a full location needs.
ps_low_degree and query_powers, as Query Powers describes. These fix the multiplicative depth of the sender's computation.
coeff_modulus_bits last, because the depth chosen in step 3 is what it has to support.

The couplings worth keeping in front of you:

Quantity	Constraint
`felts_per_item * floor(log2(plain_modulus))`	must be between 80 and 128
`table_size`	must be a multiple of `floor(poly_modulus_degree / felts_per_item)`
`ps_low_degree`	at most `max_items_per_bin`; 0 disables Paterson-Stockmeyer
`query_powers`	must contain 1, not 0, nothing above `max_items_per_bin`; anything above `ps_low_degree` must be a multiple of `ps_low_degree + 1`
`coeff_modulus` total bit count	must respect the Microsoft SEAL security bound for the degree, tabulated in Encryption Parameters
each `coeff_modulus` prime	at most 60 bits
number of `coeff_modulus` primes	at most `PSIParams::coeff_modulus_size_max`, which is 12

A parameter set that passes the constructor can still be wrong in three ways that only show up when you run it.

It can return false positives more often than you expect, which sender::SenderDB::log2_fpp tells you in advance; and it can run out of noise budget, which shows up as wrong results rather than as an error. Build a SenderDB whose bins are full – roughly table_size * max_items_per_bin / hash_func_count items, since the sender places each item once per hash function – run a query, and read the "Matching result noise budget" and "Label result noise budget" lines that APSI logs at debug level. Measuring with fewer items than that reports a budget that is too high, because a bin bundle that is not full evaluates a lower-degree polynomial and keeps more of it. A few bits left is what the shipped sets aim for; zero means the parameters are already producing wrong answers, and one or two means a different sender's set may.

Third, table_size can be too small for the number of items the receiver means to query. The receiver places its items in a cuckoo hash table of that size, and Receiver::create_query throws when they do not fit.

Whether a given set fits is a property of the items themselves, so a failure carries information about the receiver's set, and the receiver cannot help acting on it: it either abandons the query or retries and sends one later than it otherwise would. The margin is therefore a privacy parameter and not a performance one, and the shipped sets are sized for it: table_size is at least 1.6 times the receiver's item count, about 62% occupancy, at which the probability of a failure is around $2^{-40}$ . The granularity of the first constraint above is why several sets sit well above that ratio rather than at it.

The failure probability is governed by occupancy rather than by the absolute size, and climbs steeply with it: by 90% it is close to even odds. A parameter set of your own should be sized against the largest query it will ever carry rather than a typical one, since the occupancy that decides the matter is the worst case rather than the average.

A failure is not permanent for a given set of items, which bounds the damage without removing the reason for the margin. The hash functions are seeded identically on every call, so an item's candidate locations never change, but the walk that evicts and re-places items in search of a consistent assignment is not, and calling Receiver::create_query again on the same items may succeed.

SEALParams

PSIParams::SEALParams wraps a Microsoft SEAL seal::EncryptionParameters object, with the scheme always set to seal::scheme_type::bfv. Encryption Parameters covers what these mean; the Microsoft SEAL examples cover them in depth. plain_modulus also drives the false-positive probability, as False Positives describes.

Two things about coeff_modulus are specific to how APSI uses Microsoft SEAL, and neither is visible from the SEAL examples alone.

The last prime is the special prime Microsoft SEAL reserves for key switching, which APSI performs whenever the sender relinearizes after multiplying two ciphertexts together while computing query powers. It carries no message, so it is tempting to make it small and spend the bits on the others. The noise key switching adds grows with the ratio of the largest ordinary prime to this one, so shrinking it too far costs more noise than the extra bits buy: a set can go from comfortable to producing wrong answers on this change alone, with every other parameter untouched. How far is too far depends on how many times the sender relinearizes, which is decided by query_powers and ps_low_degree, so there is no single safe ratio – a gap that a shallow set tolerates can exhaust a deep one.

The first prime is the one the response is left in. BinBundle::eval switches the result down the modulus chain to that prime and then clears the low-order bits that carry no information, so the sender-to-receiver communication is governed by the width of the first prime and by how many of its bits are cleared, and not by the rest of the chain. The two pull against each other – a wider first prime leaves more to clear – and what survives compression depends on where the remainder falls relative to a byte boundary, so the response size is not monotone in the width and is worth measuring rather than predicting. The receiver-to-sender communication, by contrast, grows with the total across the whole chain.

The number of primes, rather than their sizes, is what the sender's computation scales with: each is a separate residue that every multiplication and transform has to touch. Use as few as the depth from step 3 above allows.

ItemParams

The PSIParams::ItemParams struct contains only one member variable: a 32-bit integer felts_per_item. This number was described in Large Items; it specifies how many Microsoft SEAL batching slots should represent each item, and hence influences the item length. It has a significant impact on the false-positive probability, as described in False-Positives.

The item length (in bits) is a product of felts_per_item and floor(log_2(plain_modulus)). The PSIParams constructor will verify that the item length is bounded between 80 and 128 bits, and will throw an exception otherwise.

felts_per_item must be at least 2 and can be at most 32. Most realistic parameterizations use some number between 4 and 8.

TableParams

The PSIParams::TableParams struct contains parameters describing the receiver's cuckoo hash table and the sender's data structure. It holds three member variables:

table_size denotes the size of the receiver's cuckoo hash table. The hash table size must be a positive multiple of the number of items that can fit into a Microsoft SEAL plaintext. The total number of item parts that fit in a plaintext is given by the poly_modulus_degree parameter, so the total number of (complete) items is floor(poly_modulus_degree / felts_per_item).
max_items_per_bin denotes how many items fit into each row of the sender's bin bundles. It cannot be zero.
hash_func_count denotes the number of hash functions used for cuckoo hashing. It must be at least 1 and at most 8. While setting hash_func_count to 1 means essentially disabling cuckoo hashing, it can improve performance in cases where the receiver is known to have only a single item (set membership).

QueryParams

The PSIParams::QueryParams struct contains two parameters: a std::uint32_t called ps_low_degree, and a std::set<std::uint32_t> called query_powers. ps_low_degree determines the Paterson-Stockmeyer low degree, as was discussed in Paterson-Stockmeyer. If set to zero, the Paterson-Stockmeyer algorithm is not used. query_powers defines which encrypted powers of the query the receiver sends to the sender, as was discussed in Lowering the Depth. This is one of the most complex parameters to set, which is why we have dedicated an entire subsection below for describing how to choose it.

ps_low_degree can be any number between 0 and max_items_per_bin, although values 1 and max_items_per_bin are meaningless to use. query_powers must contain 1, cannot contain 0, and cannot contain values larger than max_items_per_bin. Any value in query_powers larger than ps_low_degree must be a multiple of ps_low_degree + 1.

PSIParams Constructor

To construct a PSIParams object, one needs to provide the constructor with a valid PSIParams::SEALParams, PSIParams::ItemParams, PSIParams::TableParams, and PSIParams::QueryParams. The constructor will perform the following validations on the parameters, in order, and will throw an exception (with a descriptive message) if any of them fails:

PSIParams::TableParams::table_size is verified to be non-zero.
PSIParams::TableParams::max_items_per_bin is verified to be non-zero.
PSIParams::TableParams::hash_func_count is verified to be at least 1 and at most 8.
PSIParams::ItemParams::felts_per_item is verified to be at least 2 and at most 32.
PSIParams::QueryParams::ps_low_degree is verified to not exceed max_items_per_bin.
PSIParams::QueryParams::query_powers is verified to not contain 0, to contain 1, and to not contain values larger than max_items_per_bin. Any value larger than ps_low_degree is verified to be divisible by ps_low_degree + 1.
PSIParams::SEALParams are verified to be valid and to support Microsoft SEAL batching. Specifically, the parameters must have a plain_modulus that is prime and congruent to 1 modulo 2 * poly_modulus_degree. Microsoft SEAL contains functions in seal::CoeffModulus and seal::PlainModulus classes (see modulus.h) to choose appropriate coeff_modulus and plain_modulus primes.
The item bit count is computed as the product of felts_per_item and floor(log_2(plain_modulus)), and is verified to be at least 80 and at most 128.
The number of items fitting vertically in a bin bundle is computed as floor(poly_modulus_degree / felts_per_item). This number is verified to be non-zero.
table_size is verified to be a multiple of floor(poly_modulus_degree / felts_per_item).

If all of these checks pass, the PSIParams object is successfully created and is valid for use in APSI.

Loading from JSON

A PSIParams object can be most conveniently created from a JSON string with the PSIParams::Load method. The format of the JSON string is as in the following example:

{
    "table_params": {
        "hash_func_count": 3,
        "table_size": 6552,
        "max_items_per_bin": 20
    },
    "item_params": {
        "felts_per_item": 5
    },
    "query_params": {
        "ps_low_degree": 0,
        "query_powers": [ 1, 2, 5, 8, 9, 10 ]
    },
    "seal_params": {
        "plain_modulus": 147457,
        "poly_modulus_degree": 4096,
        "coeff_modulus_bits": [ 48, 32, 24 ]
    }
}

This is parameters/256K-4096-cmp.json verbatim. PSIParams::Load adds the power 1 to query_powers if the file leaves it out, which the PSIParams constructor does not do – it rejects a query_powers without it. Write it out, as every file in parameters/ does, and the file means the same thing through either route. The Microsoft SEAL plain_modulus parameter can be set to a specific prime, like in the example above in the seal_params section, or can be expressed as a desired number of bits for the prime, in which case the library will sample a prime of appropriate form. In such a case, the seal_params section would appear as follows:

    ...
    "seal_params": {
        "plain_modulus_bits": 24,
        "poly_modulus_degree": 4096,
        "coeff_modulus_bits": [ 49, 40, 20 ]
    }
    ...

APSI uses only the width of this prime, so every prime of a given width describes the same items and carries the same false-positive probability. The noise budget does depend on the value: the smaller the prime, the more budget is left, and plain_modulus_bits asks Microsoft SEAL for the largest prime of the width. An explicit prime therefore fixes both, and fixes them identically for anything else that reads the file, which is what the sets in parameters/ do.

The parameters/ subdirectory holds ready-made sets; Choosing a Parameter Set explains how their names read and how to pick one.

False Positives

Poorly chosen parameters can have a significant false-positive probability: even if the receiver queries an item that is not in the sender's set, the protocol may return a false positive response. Depending on the scenario, this may or may not be a problem.

A false positive does not require a whole item to collide. Recall from Practice that an item is split into felts_per_item field elements, each held in its own bin with its own matching polynomial, and that the receiver reports a match only when all of them evaluate to zero. Those zeros need not come from the same stored item: the first field element may collide with one item, the second with another, and so on. That is what makes the probability per item roughly (max_items_per_bin / 2^item_bit_count_per_felt) raised to the power felts_per_item, which is what PSIParams::log2_fpp_per_bin_bundle returns the base-2 logarithm of.

Two further factors apply, and both make the true probability larger.

First, a sender location holding more items than max_items_per_bin spills into additional bin bundles at the same bundle index. Each has its own matching polynomial, and the receiver reports a match from any of them, so the probability is multiplied by the number of bin bundles at the busiest index. PSIParams::log2_fpp_per_bin_bundle cannot know this, since PSIParams does not know how large the sender's set is; sender::SenderDB::log2_fpp does. Prefer it wherever a SenderDB exists.

Second, the probability is per item queried, so a query of many items is likelier to contain a false positive than a query of one.

sender::SenderDB::log2_fpp takes the number of items a query carries and returns the base-2 logarithm of the probability that such a query returns at least one false positive, counting both of these factors. Pass 1 for the probability per item. Both factors are union bounds, so the result is an upper estimate rather than an exact figure. A deployment expecting queries of 1024 items should check sender_db.log2_fpp(1024) directly rather than adding 10 to anything by hand. The parameter sets in parameters/ are chosen so that this total stays below -40 at the sender and receiver set sizes their file names indicate, assuming the OPRF spreads items evenly enough for the load estimate behind the bin bundle count to hold.

Query Powers

query_powers is the set of powers of the query that the receiver encrypts and sends. The sender needs every power up to max_items_per_bin to evaluate its matching polynomials, and derives the ones it was not sent by multiplying ciphertexts together. Each power sent costs communication; each power derived costs multiplicative depth, and depth is what forces larger encryption parameters. pd_tool reports the depth a candidate set produces, so alternatives can be compared without running a query.

It is unfortunately difficult to find good choices for the query_powers parameter in PSIParams. This is related to the so-called global postage-stamp problem in combinatorial number theory (see Challis and Robinson (2010)). In short, the global postage-stamp problem can be stated as follows:

For given positive integers h and k, determine a set of k integers { a_i | 1 = a_1 < a_2 < ... < a_k }, such that

any positive integer up to n can be realized as a sum of at most h of the a_i (possibly with repetition), and
n is as large as possible.

For example, if h = 2 and k = 3, then { 1, 3, 4 } provides a solution for n = 8. This is easy to verify:

Value	First summand	Second summand
1	1	N/A
2	1	1
3	3	N/A
4	4	N/A
5	1	4
6	3	3
7	3	4
8	4	4

For a larger example, if h = 3 and k = 3, then { 1, 4, 5 } provides a solution for n = 15. Simply start from 1 and write each number, in order, a sum of two of the previous numbers, in a way that minimizes the total number of summands:

Value	First summand	Second summand	Total # of summands
1	1	N/A	1
2	1	1	2
3	1	2	3
4	4	N/A	1
5	5	N/A	1
6	1	5	2
7	2	5	3
8	4	4	2
9	4	5	2
10	5	5	2
11	5	6	3
12	4	8	3
13	5	8	3
14	4	10	3
15	5	10	3

The choice of { 1, 4, 5 } is optimal in the sense that there is no set {a_i} of size 3 (k = 3) that allows for n >= 16 without at least 4 total summands (h = 4).

The above table can now immediately be represented as a directed graph with each value (integers 1 through 15) labeling the nodes and the is-a-summand-of relationship represented by directed edges. In this case { 1, 4, 5 } will appear as sink nodes.

Now, recall from Practice how bin bundle rows can hold only a predetermined number of items. For this example, suppose that number was 15. Then, once the sender receives a query ciphertext from the receiver, it must compute – in encrypted form – all powers of the query up to 15. Computing these powers will require a circuit of multiplicative depth 4. Evaluating the matching polynomials will further require an additional multiplication (by the coefficients), so in the end the encrypted computation will have multiplicative depth 5: this requires large encryption parameters. Instead, the receiver can precompute the 4th and the 5th powers of the query, encrypt them, and send them to the sender in addition to the query itself (1st power). Now the sender can use the graph to compute all powers of the query in an efficient manner with only a depth 2 circuit. The coefficient multiplications will increase the depth of the full computation to 3, but this is considerably better than 5, and will allow for much smaller encryption parameters to be used. The downside is, of course, that the communication from the receiver to the sender is now three times larger than if only the query itself was sent. Still, the reduction in the size of the parameters is typically immensely beneficial, and using appropriate source powers will be the key to good performance.

We recommend using the tables in Challis and Robinson (2010) to determine good source powers. For example, suppose the bin bundle rows are desired to hold at least 70 items. Then, looking at the tables in Challis and Robinson (2010), we find the following possibly good source powers:

Multiplicative depth	Source powers	Highest power
1 (h = 2)	1, 3, 4, 9, 11, 16, 20, 25, 27, 32, 33, 35, 36 (k = 13)	72
2 (h = 3)	1, 4, 5, 15, 18, 27, 34 (k = 7)	70
2 (h = 4)	1, 3, 11, 15, 32 (k = 5)	70
3 (h = 5)	1, 4, 12, 21 (or 1, 5, 12, 28) (k = 4)	71
3 (h = 6)	1, 4, 19, 33 (k = 4)	114

Several comments are in order:

The second and the third row represent a communication-computation trade-off. The two computations have the same depth (2), but one (second row) requires 40% more communication. The computational cost will be only slightly lower for the second row, because in both cases 70 - k encrypted multiplications must be performed. Hence, we can conclude that the second row will almost certainly not make sense, and the third row is objectively better.
It is not easy to compare rows with different multiplicative depth. Their performance differences will depend largely on the other protocol parameters – in particular the Microsoft SEAL encryption parameters.
If depth 3 is acceptable, then the last row may be the best choice, as it allows the bin bundle row size to be increased from 70 to 114. This will result in fewer bin bundles, and hence smaller communication from the sender to the receiver. However, now the sender must compute all powers of the query up to 114, increasing the online computation cost.
It is probably necessary to try all options to determine what is overall best for a particular use-case.
Challis and Robinson (2010) also shows a possible set for k = 3 with depth 3 (h = 7): { 1, 8, 13 }. While this only allows a highest power of 69, which does not quite satisfy our requirement of 70, such a set should be considered as it reduces the receiver-to-sender communication by 25%, while increasing the sender-to-receiver communication by only a tiny amount (roughly by a factor of 70/69 = 1.45%) due to the slightly smaller bin bundles. This will almost certainly be a beneficial trade-off.

Thread Control

Many of the computations APSI does are highly parallelizable. APSI runs them on a single process-wide thread pool, controlled through the static functions of apsi::ThreadPoolMgr in apsi/thread_pool_mgr.h.

Two separate numbers govern it. The fan-out width, reported by ThreadPoolMgr::GetThreadCount, is how many tasks a single APSI operation splits itself into. The pool worker count is how many threads are available to run those tasks. ThreadPoolMgr::SetThreadCount sets both at once, and ThreadPoolMgr::SetPoolWorkerCount sets only the worker count, which is what makes the two diverge. Both accept zero to mean the hardware default, and clamp the result to a sane range.

SetThreadCount resets both numbers, so it must be called first; calling it after SetPoolWorkerCount silently discards the worker count. ThreadPoolMgr::GetPoolWorkerCount reports how many workers the pool actually runs, which can be fewer than requested if the operating system refused to create the threads.

By default both are std::thread::hardware_concurrency(), which is often not ideal due to caching effects, especially with hyper-threading enabled; a value near the number of physical cores is usually better.

The pool is used for the sender's computation only. A receiver runs its query on the calling thread and its result workers on threads of their own, so a process that only receives never creates the pool, and no APSI code waits on the network from a pool worker. Raising the worker count above the fan-out width with SetPoolWorkerCount therefore only affects how much concurrent work can proceed at once; it is a tuning knob, not a requirement.

The pool exists only while at least one ThreadPoolMgr instance does; it is created with the first and destroyed with the last, so an idle process holds no worker threads. Instances are cheap and scope-bound, and cannot be copied or moved.

Logging

APSI ships a simple built-in logger. The level threshold is controlled by apsi::SetLogLevel (one of "trace", "debug", "info", "warning", "error", or "suppress"); the active sink is controlled by apsi::SetLogger. By default — when no logger has been installed — APSI lazily installs apsi::NewDefaultLogger(), which writes trace/debug/info to stdout and warning/error to stderr.

Log messages for different log levels are emitted with the macros APSI_LOG_TRACE, APSI_LOG_DEBUG, APSI_LOG_INFO, APSI_LOG_WARNING, and APSI_LOG_ERROR. The macros allow "streaming"; for example,

int val = 3;
APSI_LOG_INFO("My value is " << val);

would log the message My value is 3 at "info" log level.

To redirect output, install a different logger via apsi::SetLogger:

Append to a file (and optionally also keep stdout/stderr): apsi::SetLogger(apsi::NewFileLogger("/path/to/log", /*also_console=*/true));
Suppress all output: prefer apsi::SetLogLevel("suppress") (equivalently apsi::SetLogLevel(apsi::LogLevel::suppress)). This drops every message at the level check, before it is formatted or dispatched, and is undone simply by raising the level again. Installing a no-op logger with apsi::SetLogger(apsi::Logger::Create({}, {}, {})) also discards all output, but only after each message has been formatted and passed through the logger, so reach for it only when you want to detach the sink while leaving the level threshold in place.
Forward into your own logging stack (spdlog, glog, an internal logger, a test capture buffer, etc.): construct an apsi::Logger via apsi::Logger::Create with per-level handler callbacks and install it. Each handler receives an already-formatted std::string. Logger::log invokes the handler while holding the logger's internal mutex, so emissions on a single logger are serialized and your handler need not be thread-safe; it must, however, not re-enter the logger (for example by calling an APSI_LOG_* macro), as the mutex is not recursive.

APSI's global logger is intentionally never destroyed at process exit — it is a heap-allocated singleton that outlives static destruction. This keeps APSI safe to call from a host object's static or global destructor: it avoids the static destruction-order problem, in which a namespace-scope mutex or pointer destroyed before such a host static would be used after destruction. The tradeoff is that the global logger's destructor never runs at exit, so its flush/close handlers are not invoked automatically on shutdown.

The built-in loggers account for this by flushing on every write: both apsi::NewDefaultLogger() and apsi::NewFileLogger() flush the console and (when present) the file after each line, so they lose no output and need no explicit teardown. If you install a custom logger that buffers output or holds a resource such as a file handle, call apsi::CloseLogger() during your controlled shutdown to guarantee a final flush and close; installing a replacement with apsi::SetLogger also flushes and closes the previous logger first. For the same reason, avoid APSI-dependent logging in your own static or global destructors, where ordering relative to the C++ runtime's stream flushing is undefined.

Building APSI

To simply use the APSI library, we recommend installing APSI with vcpkg. To use the example command-line interface, run tests, or work on APSI itself, build from source.

Requirements

System	Toolchain
Windows	Visual Studio 2022 or 2026 with C++ CMake Tools for Windows
Linux	Clang++ or GNU G++ with full C++17 support, CMake (>= 3.25)
macOS	Xcode toolchain with full C++17 support, CMake (>= 3.25)

APSI is C++17. Only static builds are supported; the build configuration fails fast if BUILD_SHARED_LIBS=ON is passed.

Note: The win-vs2026-* presets use the Visual Studio 18 2026 generator, which requires CMake ≥ 4.2 (newer than the ≥ 3.25 baseline). All other presets work with CMake ≥ 3.25.

Installing APSI with vcpkg

The easiest way to obtain APSI for downstream use is via vcpkg.

On Linux and macOS, first follow Quick Start on Unix, and then run:

./vcpkg install apsi

On Windows, first follow Quick Start on Windows, and then run:

.\vcpkg install apsi:x64-windows-static-md

To consume APSI from a CMake project, follow this guide.

Building APSI from Source

APSI uses CMake (≥ 3.25) and resolves its external dependencies via vcpkg in manifest mode. The vcpkg.json at the project root pins the dependency set, and the vcpkg toolchain file picks the packages up automatically at CMake configure time. There is no separate "install dependencies" step.

Prerequisites

A C++17 toolchain (see Requirements above).
CMake ≥ 3.25.
A clone of vcpkg with bootstrap-vcpkg.sh (or bootstrap-vcpkg.bat on Windows) run, and the environment variable VCPKG_ROOT set to its path.

Configuring and building with CMake presets

CMakePresets.json ships ready-to-use presets for the common host/configuration combinations. To list available presets, use cmake --list-presets. To configure and build:

cmake --preset linux-debug          # or linux-release
cmake --build --preset linux-debug

The same pattern works for macos-arm64-debug, macos-arm64-release, macos-x64-debug, and macos-x64-release. The Windows presets separate the two steps: configure with win-vs2022-x64, win-vs2022-arm64, win-vs2026-x64, or win-vs2026-arm64, then build with the matching -debug or -release build preset, for example win-vs2022-x64-release. The win-vs2026-* presets require CMake ≥ 4.2 (see the Requirements note); all others work with CMake ≥ 3.25. The base preset enables both tests and CLI; binaries land under out/build/<preset>/bin/.

To run the tests:

./out/build/linux-debug/bin/unit_tests
./out/build/linux-debug/bin/integration_tests

Configuring without presets

If presets are not desired, the equivalent manual invocation is:

cmake -S . -B build \
    -DCMAKE_BUILD_TYPE=Debug \
    -DAPSI_BUILD_TESTS=ON \
    -DAPSI_BUILD_CLI=ON \
    -DVCPKG_MANIFEST_FEATURES="tests;cli" \
    -DCMAKE_TOOLCHAIN_FILE=${VCPKG_ROOT}/scripts/buildsystems/vcpkg.cmake
cmake --build build

On Windows, add -DVCPKG_TARGET_TRIPLET=x64-windows-static-md.

Build options

Option	Default	Purpose
`APSI_BUILD_TESTS`	OFF	Build `unit_tests` and `integration_tests`. Pulls in `gtest` via the `tests` manifest feature.
`APSI_BUILD_CLI`	OFF	Build the example `sender_cli`, `receiver_cli`, and `pd_tool` programs. Requires `APSI_USE_ZMQ=ON`.
`APSI_USE_ZMQ`	ON	Enable the ZeroMQ-backed `network::Channel` implementation. Required for the CLI.
`BUILD_SHARED_LIBS`	OFF	Must remain OFF; APSI does not support shared builds and configuration fails fast otherwise.
`APSI_USE_AVX`	ON	Use the FourQ AVX implementation where the target supports it. Advanced option.
`APSI_USE_AVX2`	ON	Use the FourQ AVX2 implementation where the target supports it. Advanced option.
`APSI_USE_ASM`	ON	Use the FourQ assembly implementation on supported static UNIX builds. Advanced option.
`APSI_SECURE_COMPILE_OPTIONS`	ON	Apply the mitigations listed under Build Hardening. Advanced option.

Build Hardening

APSI_SECURE_COMPILE_OPTIONS is on by default and covers APSI's own sources, the vendored FourQ sources, and the CLI and test executables. The flags that not every compiler or target honors are probed before use, and one the compiler merely warns about counts as unsupported and is dropped: a compiler that parses a flag and then ignores it reports it only as an unused argument, which would warn on every source file while hardening nothing. The remaining flags are selected by platform and target rather than probed.

Toolchain	Applied
GCC, Clang	Stack protection; position-independent code; bounds-checked standard library containers outside `Debug` (`_GLIBCXX_ASSERTIONS`, `_LIBCPP_HARDENING_MODE`)
GCC, Clang, except Apple	Stack-clash protection; fortified libc calls outside `Debug` (`_FORTIFY_SOURCE=2`)
GCC, Clang on Linux and Android	Full RELRO, immediate binding, and a non-executable stack
MSVC	Control Flow Guard; the Spectre variant 1 mitigation; EH continuation metadata on a 64-bit target; shadow-stack marking (`/CETCOMPAT`) on x64

Apple platforms are excluded from two of these deliberately: Clang there accepts -fstack-clash-protection and ignores it, and Apple's libc does not implement the fortified entry points. The standard library hardening is applied to APSI's own translation units, not to a consumer's, so a consumer that wants it enables it for its own build.

These options apply to the code built in this tree and are not part of the installed target's interface, so a consumer chooses its own. One consequence is worth knowing: APSI installs a static library, and Control Flow Guard is enforced by the link that produces the final image. Compiling APSI with /guard:cf instruments its objects, but a consumer on MSVC has to pass /guard:cf to its own link for that instrumentation to be enforced.

Dependencies pulled from `vcpkg.json`

These are resolved automatically by manifest mode at configure time; no explicit ./vcpkg install ... step is needed. Exact versions come from the builtin-baseline pinned in vcpkg.json. APSI additionally requires a minimum Microsoft SEAL version, enforced at configure time; the exact range is in CMakeLists.txt. Older SEAL releases carry known vulnerabilities, including in the deserialization paths APSI exposes to a remote peer, so the check should not be relaxed.

Dependency	Used for
Microsoft SEAL	BFV homomorphic encryption
Microsoft Kuku	Cuckoo hashing on the receiver's side
ms-gsl	`gsl::span` for I/O buffers
FlatBuffers	Serialization of network messages
jsoncpp	Parsing `PSIParams` from JSON
cppzmq	ZeroMQ network channels (default, `APSI_USE_ZMQ=ON`)
Google Test	Unit and integration tests (`APSI_BUILD_TESTS=ON`)
TCLAP	CLI argument parsing (`APSI_BUILD_CLI=ON`)

Note on Microsoft SEAL and Intel HEXL

Intel HEXL is an optional dependency of Microsoft SEAL that accelerates low-level arithmetic with advanced vector extensions. Its impact depends on the processor, but it can substantially reduce APSI sender online computation time. To enable, configure with -DVCPKG_MANIFEST_FEATURES=hexl (in addition to any other features), which adds seal[hexl] to the manifest-mode resolution.

Command-Line Interface (CLI)

The APSI library comes with example command-line programs implementing a sender and a receiver. In this section we describe how to run these programs.

Common Arguments

The following optional arguments are common both to the sender and the receiver applications.

Parameter	Explanation
`-t` \| `--threads`	Number of threads to use
`-f` \| `--logFile`	Log file path
`-s` \| `--silent`	Do not write output to console
`-l` \| `--logLevel`	One of `trace`, `debug`, `info` (default), `warning`, `error`, `suppress`

Receiver

The following arguments specify the receiver's behavior.

Parameter	Explanation
`-q` \| `--queryFile`	Path to a text file containing query data (one per line)
`-o` \| `--outFile`	Path to a file where intersection result will be written
`-a` \| `--ipAddr`	IP address for a sender endpoint
`--port`	TCP port to connect to (default is 1212)
`--timeout`	Seconds of sender silence to tolerate before giving up (default is 1800; 0 waits forever)

Every message received restarts the --timeout clock, so it bounds how long the sender may stay silent, not how long the query may take. A sender that is slow but responsive is never cut off, however large its database. Passing 0 disables the deadline, which is appropriate only against a sender you trust: a hostile or broken one can then hold the receiver indefinitely.

Sender

The following arguments specify the sender's behavior and determine the parameters for the protocol. In our CLI implementation the sender always chooses the parameters and the receiver obtains them through a parameter request. Note that in other applications the receiver may already know the parameters, and the parameter request may not be necessary.

Parameter	Explanation
`-d` \| `--dbFile`	Path to a CSV file describing the sender's dataset (an item-label pair on each row) or a file containing a serialized `SenderDB`; the CLI will first attempt to load the data as a serialized `SenderDB`, and – upon failure – will proceed to attempt to read it as a CSV file
`-p` \| `--paramsFile`	Path to a JSON file describing the parameters to be used by the sender
`--port`	TCP port to bind to (default is 1212)
`-n` \| `--nonceByteCount`	Number of bytes used for the nonce in labeled mode (default is 16)
`-c` \| `--compress`	Whether to compress the SenderDB in memory; this will make the memory footprint smaller at the cost of increased computation
`-o` \| `--sdbOutFile`	Save the `SenderDB` in the given file

Note: The first row of the CSV file provided to --dbFile determines whether APSI will be used in unlabeled or labeled mode. If the first row contains two values, the first will be interpreted as the item and the rest will be interpreted as the label data. Leading and trailing whitespaces will be trimmed from both the item and the label data. If the first row contains only a single value (i.e., no label), then APSI will read only items from the subsequent rows and set up an unlabeled SenderDB instance. In the labeled mode the longest label appearing will determine the label byte count.

pd_tool

pd_tool explores PowersDag configurations offline, which is how the query_powers set in a parameter file is chosen. Given a bound and a set of source powers it reports the depth of the resulting PowersDag, so candidate configurations can be compared without running a query.

Parameter	Explanation
`-b` \| `--bound`	Required. Up to what power to compute, i.e. `max_items_per_bin`
`-p` \| `--ps_low_degree`	Low power when using Paterson-Stockmeyer for polynomial evaluation (default is 0)
`-o` \| `--out`	Write the `PowersDag` in DOT format to the given file
`<list of unsigned integers>`	Required. The source powers, given as positional arguments

Test Data

The library contains a Python script tools/scripts/test_data_creator.py that can be used to easily create test data for the CLI. Running the script is easy; it accepts three necessary arguments and two optional parameters as follows:

python3 test_data_creator.py <sender_size> <receiver_size> <intersection_size> [<label_byte_count>] [<item_byte_count>]

Here <sender_size> denotes the size of the sender's dataset that will be written in a file db.csv. If this file already exists, it will be overwritten. Similarly <receiver_size> denotes the size of the receiver's query that will be written in a file query.csv. The third argument, <intersection_size>, denotes the number of items common in both the generated db.csv and query.csv. The fourth (optional) argument denotes the byte size of the randomly generated labels in db.csv; if omitted, the data will be unlabeled. The last (optional) argument denotes the item byte size; it defaults to 64 if omitted. Since long the items will automatically be hashed before they are inserted into a SenderDB, the item byte size does not matter much in practice.

Acknowledgments

Multiple people have contributed substantially to the APSI library but may not appear in Git history. We wish to extend special thanks to Hao Chen, Peter Rindal, and Michael Rosenberg for major contributions to the protocol and the library. We wish to also thank Craig Costello and Patrick Longa for helping implement hash-to-curve for the awesome FourQ curve, and Mariana Botelho da Gama for helping with the Paterson-Stockmeyer implementation.

Contributing

For contributing to APSI, please see CONTRIBUTING.md.

Value	First summand	Second summand	Total # of summands
1	1	N/A	1
2	1	1	2
3	1	2	3
4	4	N/A	1
5	5	N/A	1
6	1	5	2
7	2	5	3
8	4	4	2
9	4	5	2
10	5	5	2
11	5	6	3
12	4	8	3
13	5	8	3
14	4	10	3
15	5	10	3

Value	First summand	Second summand	Total # of summands
1	1	N/A	1
2	1	1	2
3	1	2	3
4	4	N/A	1
5	5	N/A	1
6	1	5	2
7	2	5	3
8	4	4	2
9	4	5	2
10	5	5	2
11	5	6	3
12	4	8	3
13	5	8	3
14	4	10	3
15	5	10	3

Value	First summand	Second summand	Total # of summands
1	1	N/A	1
2	1	1	2
3	1	2	3
4	4	N/A	1
5	5	N/A	1
6	1	5	2
7	2	5	3
8	4	4	2
9	4	5	2
10	5	5	2
11	5	6	3
12	4	8	3
13	5	8	3
14	4	10	3
15	5	10	3