1
$\begingroup$

I'm a crypto newbie and hoping to get pointed in the right direction. I've seen some related questions like this but none that satisfy my requirements.

Let's say Jane's Forum is a large community, and every member of Jane's Forum has a public/private keypair. The public key is associated with their profile and visible to anyone.

Bob's Backpack Shop is willing to send a free backpack to every member of Jane's Forum, but members of Jane's Forum are very private and don't want anyone, even Bob, to know which of them have ordered a backpack from Bob.

Is it possible for members of Jane's Forum to prove to Bob that they're registered with the forum and qualify for the free backpack without disclosing exactly which member they are?

Two requirements that make this harder:

  1. New members will continue joining the forum over time, and the new members should also be eligible for the backpack giveaway.
  2. Bob needs to be able to verify that each order comes from a unique forum member (each member is only eligible for one free backpack).

As a bonus, it would be great if Bob could identify which members have been kicked out of Jane's Forum. Eg., maybe Bob provides a VPN service instead of a backpack, and he wants to terminate the accounts of users who are kicked off the forum.

$\endgroup$
1

1 Answer 1

1
$\begingroup$

First to adress the bonus part: When you solve this kind of problem, you typically end up with some kind of protocol to prove that the claimed forum user is part of the current set of forum users. When the set of current forum users changes, you should be able to just re-run this protocol to verify that the user in question is still authorized. This works even better if you have some sort of deterministic pseudo-random identifier for each forum user.

For the actual proof part, there are two options I see: Using a zero-knowledge proof with a hash and a group membership proof or using a two-party-computation protocol with a PRF and a group membership predicate. Without the pseudonymization part this would be a standard case for ring signature or a group signature which prove that you can produce a signature valid under one public key from a group. As an alternative if you can convince the forum operation to collaborate would be the use of anonymous credentials / blinded tokens like Privacy Pass.

The tricky part about this is that you need to have the service provider learn an identifier for the user that cannot be arbitrarily (re-)chosen by the user while at the same time not allowing a resourceful attacker to identify the exact user from the identifier. The best solution I could come up with for this is to hash / PRF the private key which should not be brute-forceable anyways and so doesn't leak the identity while preventing other users posing as each other through the AND part of the proof / protocol.

Concretely, assuming you have a generic zero-knowledge proof protocol, you want to prove that the user knows their private key $x$ such that $H=\operatorname{Hash}(x)\land \exists i: \operatorname{is-public-key-of}(\text{pk}_i,x)$ holds where $\{\text{pk}_i\}$ is the set of current forum user public keys and modeling the hash function as a random oracle as to not be one of those "dumb" hash functions which leak the input. An alternative formulation of the above statement to be proven would be $H=\operatorname{Hash}(x)\land (\bigvee_i \operatorname{is-public-key-of}(\text{pk}_i,x))$ to emphasize the "OR"-nature of the second part. This paper looks like it could help with this approach.

Alternatively, the same should also be achievable under different assumptions by using secure multi-party computation. In particular, here you'd define a functionality which takes from the forum user the private key $x$, from the service provider a static symmetric random key $k$ and then as public input the current list of forum public keys. The functionality would then output a bit $b$ indicating whether $\bigvee_i \operatorname{is-public-key-of}(\text{pk}_i,x)$ holds and a random string $I=\operatorname{PRF}(k,x)$ as the forum user identifier. While I think that both of these sub-operations tend to have efficient specialized protocols individually, unfortunately I don't think there is in general a good way to "tie" the inputs to these protocols together so that the user doesn't use a different input for one sub-protocol. For this, a mixed-protocol 2PC framework would probably be the best option, e.g. ABY, MOTION, or ABY 2.0 as they allow you to do the private-public key relation check with arithmetic operations and the hash verification / PRF evaluation with binary ones.

$\endgroup$
1
  • $\begingroup$ Thank you! I've started looking into both approaches you mentioned, and while I still don't have enough context to totally evaluate the tradeoffs, this has given me a great place to continue my research and (importantly) some confirmation that it's possible. $\endgroup$
    – kcorbitt
    Aug 18, 2021 at 13:13

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.