Availability of OPRF?

[matthiasgeihs]

OPRFs can be useful primitives in privacy-preserving protocols.

Does this library contain any OPRF implementations? If not, are there plans to include some in the future?

In particular, I'm looking for a verifiable threshold OPRF with committed inputs that can be composed with other primitives. For example, I'd like to be able to prove that for a given value pid, I posses a credential for a value id (i.e., a signature sig = SIGN(id) from a credential issuer) and that OPRF(id) = pid, without revealing id.

[lovesh]

Hi,

Does this library contain any OPRF implementations? If not, are there plans to include some in the future?

No.

I'd like to be able to prove that for a given value pid, I posses a credential for a value id (i.e., a signature sig = SIGN(id) from a credential issuer) and that OPRF(id) = pid, without revealing id.

If this is the exact requirement, then pid is what's called a pseudonym and you can use SyRA for this. The user's sig is what SyRA calls "user secret key" which contains user's unique attribute id and the user generates a pseudonym using his sig and a value Z given by the verifier as pseudo(sig, Z) and a proof that the inputs to pseudo were infact sig and Z without revealing sig or id. Note that pseudo is not randomized and depends only on sig and Z so the user cant create a different pseudonym from the same sig and Z.
Technically pseudo is not an OPRF, since the user learns Z but doesn't look like that's your requirement. But you can make it a OPRF by verifier first blinding Z by random r and then unblinding the output of pseudo by multiplying by 1/r.

You can combine (that was our intention) this construction with schemes like BBS+ to get anonymous credentials with attributes where the BBS+ credential has other user attributes and the issuer, in addition to BBS+ signature, gives a SyRA signature.

You said threshold OPRF. Which part of would you want to thresholdize, SIGN?

[matthiasgeihs]

Hi, thx for the reply, will definitely have a look at SyRA.

Threshold OPRF because of the following. (Also wanted to ask whether this is a problem with respect to SyRA.)

So in my setting, the user id id certified in the credential is low entropy (you can consider this a passport number, which is essentially guessable). Still we want to hide it when proving eligibility (the application I have in mind is voting). Furthermore, the mapping from id to pid should be deterministic (there should be exactly one pid for a corresponding id), so that we can check if somebody voted twice. Still pid should not leak id. An OPRF can generate pid from id such that this holds as long as the OPRF key is not leaked. If the OPRF is evaluated by just a single party, then this party knows the key and could identify id from pid simply by evaluating the OPRF itself. Hence, I'd thought the solution to this problem would be to thresholdize the OPRF, so that no single party actually knows the OPRF key.

Does that make sense?

[matthiasgeihs]

Had a look at SyRA. This looks very promising for my use case.

One differentiation though, I think, is that in SyRA the issuer plays a central role. If I understand correctly, credentials issued by different issuers cannot be mixed.

For example, I could not allow voters who received their credential from different issuers, to vote on the same poll.

Is my understanding correct?

[lovesh]

So in my setting, the user id id certified in the credential is low entropy (you can consider this a passport number, which is essentially guessable). Still we want to hide it when proving eligibility (the application I have in mind is voting). Furthermore, the mapping from id to pid should be deterministic (there should be exactly one pid for a corresponding id), so that we can check if somebody voted twice. Still pid should not leak id.

This is achieved by SyRA.

An OPRF can generate pid from id such that this holds as long as the OPRF key is not leaked.

I should have mentioned before but when using SyRA as (O)PRF, id is the PRF key. But if the user want's to secret share id (seems impractical as all share holders have to be invoked on each usage of the credential), the current proving protocol won't work.

I could not allow voters who received their credential from different issuers, to vote on the same poll.

You mean if a single voter got multiple credentials, one from each issuer, then correct. Their pseudonyms (or PRF output) on same id will be different thus counting as different votes. If you can share more details about your use-case, like what conditions must be met to get a credential, can issuers collaborate, etc, I can think a bit more

[matthiasgeihs]

Read further into the paper. Another noticeable difference: In SyRA, the user private key is chosen by the issuer. Hence, if the issuer is compromised, it could generate signatures on behalf of the user. (For that reason, thresholdizing the issuer seems absolutely necessary. As far as I can see, the thresholdized issuer protocol has not been implemented yet, correct?)

In my imagined design, the user secret key is chosen by the user and not revealed to anyone. Generating a pseudonym is a separate step. Compromising the pseudonym issuer would only compromise anonymity, but not allow voting on behalf of the user.

I'll write up a few more details below on what I have in mind. (Note that I have not been able to come up with a concrete and efficient realization of the protocol so far, but I think it's theoretically possible.)

[matthiasgeihs]

Target application: anonymous voting Involved parties: User/Voter (U), Credential Issuer (CI), Poll Organizer (PO), Append-only Public Bulletin Board (B)

Step 1: U proves identity and obtains credential from CI U convinces CI of identity id U chooses secret key sk U requests credential cred for (id, sk) from CI, which is a partially blind signature for on (id, sk) where sk is blinded. (This can be realized using BBS.)

Step 2: U obtains poll id from PO U and PO evaluate pid = OPRF(id), where PO holds OPRF key. U obtains a proof pi of correct evaluation. (Something like this can be realized using BLS, but there is a catch, see below.)

Step 3: U publishes vote on B U creates a signature sig on vote v using sk. U then creates a proof pi_vote for the following:

• VerifyCred(cred, (id, sk)) = 1
• VerifyPid(id, pid) = 1
• VerifyVote(sk, sig, v) = 1

U publishes (pi_vote, v, pid) on B. Anybody can verify that the voter is eligible by checking pi_vote and detect double-voting by checking for duplicate pid. (Generating a proof of knowledge of a signature that has been created using a secret key contained in a credential shouldn't be too hard using known techniques. What I currently don't know is how to connect the OPRF proof with the rest of the two statements. Afaik, BLS can used as a verifiable OPRF (and is easy to thresholdize), but correct evaluation can only be verified if the input is revealed. I don't know how to make this work for committed inputs to the OPRF. I.e., we want to prove that for some commitment, the result of evaluating the OPRF on the committed value is correct, and there are certain relations of that committed input value to other inputs of the protocol (like there is a credential for that input).)

[lovesh]

(For that reason, thresholdizing the issuer seems absolutely necessary. As far as I can see, the thresholdized issuer protocol has not been implemented yet, correct?)

Correct, it hasn't been. But I discussed with one of the SyRA authors to add it but the implementation is going to be different than the one in the paper.

Step 1: U proves identity and obtains credential from CI U convinces CI of identity id U chooses secret key sk U requests credential cred for (id, sk) from CI

Do you assume CI can't be malicious, i.e. issue cred with different id to same U. And I don't think you need sk (see below)

Step 2: U obtains poll id from PO U and PO evaluate pid = OPRF(id), where PO holds OPRF key.

Before PO generates pid, it needs to check if U has a cred with id. And in your first comment, were you meaning to thresholdize PO?

Step 3: U publishes vote on B U creates a signature sig on vote v using sk. U then creates a proof pi_vote for the following:

sk isn't needed as pi_vote can just be the proof of knowledge of signature in cred with the same id as used in generation of pid and v is just included in the challenge thus forming a signature over v. The same idea of getting a Schnorr signature from Schnorr's identification protocol. Also note that a malicious PO cannot vote as it does not have cred but it surely can break anonymity of voter if using SyRA as it is.

Finally, I need to look more into the OPRF with desired property. Will get back to you on this.