4
$\begingroup$

I'm a software engineer, so I generally think in building blocks. And I'm not so familiar with the Math notation in Crytography, so I'll stick with function calls and function blueprints (which I assume would be as intuitive).

Lately I've been asking and reading several questions here and also some related papers on these topics. So I'll try to first list the definitions on how I understand them; and propose a protocol for an OPRF using OT and a PRF.

Can you please comment on the validity and security of this protocol?

Here are my definitions, which are independent of each others.

PRG

Alice initiates a PRG with an arbitrary seed. Alice can generate a random looking output of an arbitrary length of n. If Alice at another time, and another system would seed the PRG with the same seed, the the first n bits of the output would be the same as the previous output she got.

PRF

Alice has a key. Alice initiates her PRF with this key. And given any input of an arbitrary length of bits, Alice can deterministically get a random looking output of an arbitrary length of k. (sizes k and n don't necessarily have to be in any relation to each-other)

OT (specifically 1-2 OT)

Alice creates two messages of the same length (n-bits) m0 and m1. And Bob chooses either 0 or 1 and gets the respective message. Alice won't know which one Bob got, and Bob will get m0 if he has chosen 0, and will never know about m1 (or vice versa)

OPRF

Bob has an input. Alice has the key of the OPRF function. During the execution of the OPRF, Alice interactively generates a random looking output based on Bob's input, however Bob's input is concealed from Alice. Alice will never know Bob's input, and Bob will never know Alice's key. However if Alice were to share her key with Bob, or Bob were to share his input with Alice, the same "random looking output" could be re-generated.

Based on the definitions i have listed, I will now try to propose a Protocol which satisfies the definition of the OPRF above.

I'll first propose a naive and probably not so-secure version; and try to fix the security issue I see, with a small twist.

Alice has a PRG and this is how she uses it to build a PRF using it.

//input and output are bit arrays of any arbitrary size.

//output is initialized with 0 (identity element for XOR)

    prf(key, input[], output[]) {
      prg.setSeed(key)

      for(i = 0; i < input.length; i++) {

      bits0 = prg.nextBits(output.length)
      bits1 = prg.nextBits(output.length)

      if(input[i] == 0)
        output (XOR) bits0
       else
        output (XOR) bits1

      }
    }

This approach of creating a PRF out of a PRG is built on the premises that:

  • XOR operation will preserve entropy
  • The PRG will be generating random sequences with no correlation.

Now Bob wants to use this PRF using Alice's key. The OPRF is as follows.

  • Bob has an input of size n and wants a random output of size k
  • Alice seeds the PRG with her key
  • [OT] They execute an OT protocol for each bit in Bob's input
  • [OT] Alice creates two random messages of size k-bits {bits0, bits1}
  • [OT] If the current bit of Bob's input is 0 Bob chooses bits0, otherwise chooses bits1
  • Finally Bob XOR's all the messages to get the output.

This protocol is equivalent to the PRF described above.

The above protocol would be secure:

  1. If we would run this protocol only once
  2. If Alice would use a random key for each execution

Because in a second run, Bob can switch the bits in his input and learn the full random sequence from Alice's PRG.

However none of the requirements above are realistic. The twist to make this protocol secure would be as follows:

  • Alice requires an input of even size
  • Bob has an input of size 2n and wants a random output of size k
  • Using a PRG with a one-time seed, Alice generates n random masks of k-bits
  • Alice generates a random permutation of these n masks in a sequence where every message is repeated exactly once. (giving us a sequence of size 2n, remember that's the size of Bob's input)
  • [OT] Now, they execute an OT protocol for each bit in Bob's input
  • [OT] Alice creates two random messages of size k-bits {bits0, bits1} and XORs them with the next mask from the sequence {bits0 (XOR) maskR, (bits1 (XOR) maskR}
  • [OT] If the current bit of Bob's input is 0 Bob chooses the masked bits0, otherwise chooses masked bits1
  • Finally Bob XOR's all the messages.

Since masks are going to cancel each-other out, and every execution of this protocol will involve a random mask. This protocol should still be equivalent to the PRF defined above and should not be suffering from the problem defined in the previous protocol.

My final goal for this OPRF is to use it for a Private Set Intersection protocol. see the answer of @Mikero in the question: How can Alice enable Bob to look-up values in a private map

Can you please comment on the validity and security of this protocol? And how can I improve it if you see any drawbacks on it.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
2
$\begingroup$

What you describe sounds a lot like the encoding mechanism in this paper:

Benny Pinkas, Thomas Schneider, Michael Zohner: Faster Private Set Intersection based on OT Extension, Usenix 2014.

See section 5.1 of that paper. Basically there is an OT of random strings for each bit of Bob's input. Bob takes the XOR of his OT outputs. Alice can compute the corresponding thing for her input as well.

I don't understand your second protocol where there are $2n$ OTs, and the "maskR" value is unclear to me.

Anyway, there is nothing wrong with this protocol per se. It is fine for securely testing the equality of two strings. But it can be extended to a private set membership test (Bob has one value and Alice has many. Bob wants to learn whether his item is in Alice's set.) if you hash this XOR value at the end. Alice can send many such values, one for each of her items. Without the hash, the multiple XOR values have correlations that leak correlations about the inputs.

You mention that you like thinking in terms of well-defined components. If you feel limited to just using plain 1-out-of-2 OT than this might be the best way to construct an OPRF suitable for PSI. But more recent work in PSI gets improvements by generalizing the 1-out-of-2 OT into something more sophisticated. Even the paper above suggests that using 1-out-of-$N$ OT is better (because of the specifics of OT extension). The following paper uses a generalization which is similar to 1-out-of-$N$ OT for an unbounded $N$:

Vladimir Kolesnikov, Ranjit Kumaresan, Mike Rosulek, Ni Trieu. Efficient Batched Oblivious PRF with Applications to Private Set Intersection

Using these generalizations you don't have to do an OT for each bit of the strings, but for each base-$N$ digit. In the case that $N$ is unbounded, you are basically doing only one "OT".

Improve this answer
$\endgroup$
2
  • $\begingroup$ the maskR for the first bit on Bob's input will be repeated for another (random) bit for Bob's input down the line. Which will eventually unmask and only reveal the actual PRF output. This serves the purpose of concealing the bits Alice use for every bit of Bob's input, so that Bob won't be able to construct the result of the PRF by himself for another input. This should effectively enable Alice to re-use the key for multiple inputs from Bob. $\endgroup$
    – zetaprime
    Jul 22, 2018 at 20:51
  • $\begingroup$ The second protocol ensures there are even number of bits in Bob's input. Say Bob's input is: 1011. For each input, Alice will calculate two random masks {m0, m1} and create a random permutation of these with repetition {m1, m0, m0, m1} and four random strings for Bob's input {b0, b1, b2, b3} instead of sending these, Alice will be sending these: {b0 ^ m1, b1 ^ m0, b2 ^ m0, b3 ^ m1}. Bob calculates (b0 ^ m1) ^ (b1 ^ m0) ^ (b2 ^ m0) ^ (b3 ^ m1), which is equal to b0 ^ b1 ^ b2 ^ b3. The individual messages Bob receives from Alice, (in my understanding) should conceal the actual correlation. $\endgroup$
    – zetaprime
    Jul 22, 2018 at 21:13
0
$\begingroup$

Basically, if I understand correctly you want to create a protocol which would allow Alice and Bob compute a random value together without revealing their secrets to each other (Alice's key and Bob's input). If so, there's already a generalization of such protocols called Secret Sharing. The idea of protocols of Secret Sharing is to compute a secret value that can only be obtained using keys. Those keys are distributed among parties and each party is unwilling to share its key.

Improve this answer
$\endgroup$
0
$\begingroup$

if you want to convert prf to oprf, maybe like this? enter image description here

https://scholar.archive.org/work/uf6brybixrfozltlltnehtem7y/access/wayback/https://dl.acm.org/doi/pdf/10.1145/3503045

https://www.iacr.org/archive/tcc2009/54440575/54440575.pdf

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.