Query Parameters Setting Help

[HelmetOff]

{ "table_params": { "hash_func_count": 3, "table_size": 2457, "max_items_per_bin": 72 }, "item_params": { "felts_per_item": 5 }, "query_params": { "ps_low_degree": 11, "query_powers": [ 1, 3, 5, 6, 12, 36, 48] }, "seal_params": { "plain_modulus": 65537, "poly_modulus_degree": 4096, "coeff_modulus_bits": [ 40, 32, 36 ] } }

Above is my params setting for 1M-2048 setup, if I set the ps_low_degree to 0 (disable the Paterson Stockmeyer Algorithm) and pass all needed powers, the setting runs fine. But if I stick to this, the outputs show 0 matchings.

My thought was using n(2,4) for low powers up to 11, and n(2,3) for high powers. Am I missing anything here?

[kimlaine]

You are the first brave person I've heard of to start creating your own parameterizations! Very nice. Let me help you understand this a bit, so you'll see what the problem is.

First, of all, if you run receiver_cli with the flag -l debug, you'll see a bunch of lines like

Received a result package (... bytes)
Matching result noise budget: 0 bits

The problem clearly is that you are running out of SEAL noise budget. I'm not sure how familiar you are with this concept, so you may want to read more about it here and here. In short, the multiplicative depth of the encrypted computation that needs to take place is too high for the seal_params that you specified.

To understand what the multiplicative depth is with Paterson-Stockmeyer, see this. Look at the example

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).

With the parameters you are giving, you hope the inner polynomials here to have degree 11 (this is ps_low_degree) and the outer powers to have degrees multiples of 12, all the way up to 72. You are misunderstanding the parameters slightly, and I'll get to that in a moment. For now, I believe this was your intention so let's go with that. As you see from the example M(x) above, the monomials x^k in the inner polynomials must be multiplied by constants, which actually increases the multiplicative depth by one. When you multiply the inner polynomials with the outer (high) powers, you'd ideally want both of those to have the same multiplicative depth, because the output will in any case have multiplicative depth max(inner_depth + 1, outer_depth) + 1. In your case though, both your inner monomial computations, as well as your outer monomial computations, have depth 1. The multiplication by constants throws this off balance so you end up with a sub-optimal depth-3 computation, which your parameters cannot support. If you look at other 1M-2048 example parameterizations, you'll see they have zero multiplicative depth for the inner monomials and depth 1 for the outer monomials. The multiplication my constants balances these, resulting in an optimal depth-2 computation.

OK, now let me help you understand some mistakes you have in the parameters themselves. You are hoping to use the n(2,4) configuration for low powers. Looking at the paper, you see that [1, 3, 5, 6] can get you up to power 12. Therefore, your ps_low_degree should actually be 12, not 11. Since you are hoping to use the n(2,3) configuration for the high powers, this means the high powers should instead be [13, 39, 52], allowing you to compute multiple-of-13 powers up to 813=104. The max_items_per_bin should be the highest power you can compute by combining these, as in the M(x) example above, so it should be 104+12=116, not* 72.

Couple other notes:

• Your table_size is too small to ensure cuckoo hashing succeeds with high probability. If you look at the Hashing Failures subsection of this paper, you'll see why we ended up using a table size as big as 3410. Long story short, you'll want to make sure receiver_item_count / table_size is about 0.67 or less. Your parameters result in a high likelihood of insertion failures if you actually insert 2048 items on the receiver's side.
• I'm not sure if you knew to look at the false-positive probability for your parameters. Running sender_cli, you should see an output like (towards the beginning):

  PSIParams have false-positive probability 2^(-49.1504) per receiver item

  This means that if the receiver inserts 2048, by the union bound you'll have approximately 2^(-38) probability of at least one false positive in a single execution of the protocol. This is pretty good for many uses, but in our parameterizations we always aim for this to be at most 2^(-40) (more info here).

So, how to fix your parameters? It's not easy and I'm not sure what is the best approach. Depends on what you want to optimize for. The example parameters we provided give you some nicely balanced communication/computation trade-offs. Are these insufficient for you for some reason, for example, are you looking for more extreme trade-offs? Or are you looking to increase the false-positive probability or the receiver insertion failure probability for better performance?

[TY-cc]

What is mean of n(2, 4) or n(2 ,3)? And why does inner_depth and outer_depth need have same depth?

[kimlaine]

The n(-, -) notation is the notation used this paper (see Appendix). You actually want inner_depth + 1 == outer_depth. The reason is that the inner polynomials have also constant multipliers, which increase the depth by one (hence the +1). Here inner_depth refers to the depth of computing the powers of x (monic monomials) in the inner polynomials. The outer_depth refers to computing the (monic) monomials in the outer polynomials. When the inner polynomials are multiplied with the outer monomials, you want both multiplicands to have the same multiplicative depth; this is optimal from the point of view of homomorphic encryption.

[TY-cc]

Thank for your reply, i get it.