One question for kkrt: what happens if the same secret key is used to calculate the OPRF

[Shareong]

As mentioned in the paper, both parties compute the mapping of inputs to buckets based on the same cuckoo hash, and then perform 1.2n + s times OPRF (Don't consider OTE) with different random numbers corresponding to hash buckets.

I envisioned an optimization method: if only one random number is used, one party uses this random number to execute n times PRF, and both parties perform n times OPRF with the same random number. In this way, there is no need to calculate the cuckoo hash, and the number of OPRF calculations is also reduced.

Is there any problem with this?

[ladnir]

I dont fully follow. The main reason KKRT uses cuckoo hashing is that their OPRF allows the receiver to evaluate it once per OPRF key. So there are m = 1.3n cuckoo hashing bins, and m OPRF keys k1,...,km, where ki is for the i'th bin.

The receiver performs cuckoo hashing and holds xi in bin i. They learn

wi = OPRF(ki, xi)

For any given ki, the receiver can only call OPRF once. Then sender performs simple hashing where each yi is mapped to 3 bins, bi1,bi2,bi3. The sender computes

yij' = PRF(k_bij, yi) for j=1,2,3

and sends them to the receivers who can infer the intersection.

[ladnir]

This is in contrast to the ECDH construction where you can reuse the OPRF key. But is also a lot slower. You should also look at my recent VOLE-PSI paper. We construct an OPRF that allows the key to be reused.

[Shareong]

Thanks very much.

I'm very excited to see VOLE-PSI has a nice performance in Wan. It is a very beautiful work.

Finally, let me confirm. Whether it means that the OPRF in kkrt does not support random number reuse for some reasons.

[ladnir]

Also see this for fast Lan performance https://eprint.iacr.org/2022/320

For kkrt, there is a setup that outputs the oprf keys k1,..., km. These are chosen at random by the kkrt protocol. Each can be used once by the receiver.

In reality it's a bit backwards. For a unique index i, the receiver can choose an oprf input xi. The parties compute

(xi', ki) = oprf(i, xi)

where the receiver learns xi' and the sender learns ki. In this formulation its a bit more clear why the receiver can use ki only once. Since by calling the oprf, a key is picked at random. The key is not a input but an output of the oprf...

[Shareong]

Sorry, I'm confused again. My initial idea was this.

We define an OPRF protocol in which a sender chooses a random PRF seed s while the receiver chooses r and learns PRF(s,r).

With this definition, we can construct a simple PSI scheme similar to hash comparison where hash is replaced by OPRF:

1. S chooses a sk, and completes PRF(sk, si) for all elements of S independently. Then S sends outputs (hash set_1) to R.
2. S and R complete OPRF(sk, ri) for all elements of R with same sk, and R gets hash set_2.
3. R finds the intersection between set_1 and set_2.

Therefore, the key of this scheme is to find an efficient OPRF with less traffic and low computational complexity.

[ladnir]

As I keep saying, kkrt is not a normal oprf. It does not allow the sender to choose the oprf key/seed s. It does not allow the receiver to use the same key twice.

The protocol you described is exactly what vole-psi and ecdh-psi does since the oprf they use allows this.

[Shareong]

Oh. I see, thanks.