How does ODIS blinding and ODIS querying work?

[arthurgousset]

Re-posting a question asked and answered on Discord (for future reference).

Discord user:

Hello devs,

I have read the identity protocol but one key point is not clear. I could understand the pepper generation in this link - https://docs.celo.org/celo-codebase/protocol/odis. I also could understand that there is a limitation in the number of possible peppers a user can query. What is not clear to me is how a user (user "A") can find the pepper of a user "B" to discover the Celo address of user "B" if user "A" does not have the initial key that user "B" used to sign the original BLS message.

The first step of this pic is to "BLIND (Phone number)". The description is "When a client queries ODIS to get an OPRF evaluation, the client first blinds the phone number locally using a secret one-time key. This blinding process preserves the privacy of underlying message (e.g. a mobile number or password) such that ODIS nodes won't learn any of the user's sensitive information. In addition to protecting the user's privacy, it reduces the risk of targeted censorship."
Image
My question is: how is this blind done? If it uses a secret key of the user's phone, how other users can query the phone number?
if it does not use a secret key from the user's phone, where does this key come from?

@nategraf:

So the way this works is that the blinding factor, this one-time key generated by the client, is only used to blind/"encrypt" the query that is sent to ODIS. When ODIS responds, the client removes this blinding factor so the final result does not depend on what blinding factor the user chooses (e.g. If users B and C both send the phone number for user A to ODIS, they will use different blindings such that the requests look different, but the result is the same: user A's pepper).

Another way to put this is that the overall protocol implements a keyed PRF/"hash function" F(k, m) where k is the secret key held by ODIS and m is the message held by the client. In this protocol, the client learns the output of F(k, m) but learns nothing about the secret key. The server(s) learn nothing about the message. The blinding factor is what ensures that the server learns nothing about the input message. You'll notice here that the function output only depends on the ODIS secret key and the message, in particular the blinding factor has no influence on the output. As a result, multiple clients that use their own random blinding factors will all get the same result.

Discord user:

Hello Victor. Thank you for explaining this. I am still trying to understand. In your explanation, you used F(k,m) where k is the secret key held by ODIS and m is the message held by the client. This was clear. What is the result of this F function? The pepper of a user, correct? Also, I understood that k never changes, correct?
What I still could not understand is how different messages m and m’ will both produce the same result. Because if users B and C both send the phone number for user A to ODIS They will produce different messages, let’s say m and m’. Are you saying that F(k,m) will produce the same result that F(k,m’)? What is wrong with my thought?

@nategraf:

What is the result of this F function? The pepper of a user, correct?

Correct, this is the ODIS OPRF function and the result is the pepper when the input is a phone number. And correct, k does not change, it is the key shared among ODIS nodes.

Are you saying that F(k,m) will produce the same result that F(k,m’)? What is wrong with my thought?

So in this case F is the logical function that is actually split across the client and server. If the phone number is the same for users B and C then m is that phone number and is the same for both clients. They will blind it using their own secret values, so the server will see different blinded messages, but the underlying message will be the same in both cases.

Discord user:

Hey victor, thank you for replying. I am so sorry for asking again but this is really important to understand.
Supposing again users B and C both sending the phone number for user A.
You said they will send to the server different messages (this is clear, because they used different client encryption). Supposing Mb and Mc.
Mb – message encrypted by user B to the phone number of A
Mc – message encrypted by user C to the phone number of A
How can the server arrive in the same result (that is the pepper of user A) if it receives different inputs (Mb and Mc)?

[arthurgousset]

Sharing @nategraf's conversation on Discord for future reference:

@nategraf:

So it's not so much that B and C "encrypt" the message to A, it's more that they "encrypt it to themselves". So the ODIS servers will receive the "encrypted" form of the message Mb or Mc, run a computation on it to create the responses Rb and Rc and send them back to B and C respectively. When B and C "decrypt" the responses, they will both yield the same result, the pepper for A.
I put encrypt in quotes because it's technically not encryption, we call it blinding in this context and it has slightly different properties, but it operates mostly the same way as if we'd encrypted it in this context.

Discord user:

Hum. Now I understood what you mean! Thank you for explaining!! Do you have any additional link about this blinding process? Is it a common crypto technique?

@nategraf:

It's used in blind signatures and oblivious pseudo-random functions (OPRF). ODIS is actually both of those things as it's based on blind BLS signatures. I'm having a hard time finding good resources on these systems, but here are the best two I could find. Although the term (blind) itself is mostly used in this context, it's similar to other techniques used in cryptography.

• https://en.wikipedia.org/wiki/Blind_signature
• https://datatracker.ietf.org/doc/draft-irtf-cfrg-voprf/

Thanks for answering @nategraf! 🙏