Proving spatial eligibility, hardness definition

[dbosk]

We need some formal definition of spatial eligibility, e.g.

• the coordinates provided by a proof should be within a certain area, or
• the user must have followed the protest trajectory.

Then we need some adversarial game defining the hardness of providing a proof of being in a location where the adversary actually hasn't been.

The protesters actually have an incentive for providing false proofs, thus they are incentivized to not use the distance-bounding protocol (see #22). So we need to change the incentives. The trusted journalist Jane is probably our only tool for this, since she is assumed honest --- but she cannot sign for everyone.

Probably, this hardness will reduce to forging Jane's signatures or trick Jane into accepting relays (i.e. break the distance-bounding protocol).

[dbosk]

Will the witnesses sign the proofs? Or will they use a similar technique as in #27 ? They can "sign" using $z \gets PRF_{kw} (id | location)$ and provide a NIZK proof.

[dbosk]

What about tracking of witnesses? How can we ensure privacy?

[dbosk]

In some sense we need a confidence of how likely a proof is correct, since there can be e.g. multiple witnesses with different levels of trust. (The same for #25 .)

This should go into the definition of the participation proof (def 3, replace $l\subseteq l_j$).

This is fixed by the strength function in Def 4.

[dbosk]

Why do we need more than one witness?

The original idea was that if you have only one signature, that might be your friend vouching for you --- thus it's easy to collude. So, the more signatures you have, the higher the chance of it actually being valid.

Now that I think about it, the assumption at the core of this statement is that honest users will form the majority, you don't have enough malicious friends to get a valid fake proof.

How does this work for our scenario where all protesters are assumed malicious? We only have the journalist Jane who is honest. Clearly only one signature from her will suffice. But she cannot act as a witness for a million people.

Actually my idea of trust propagation might not work either, because the protesters don't have an incentive to perform the distance bounding. Once Alice is witnessed by Jane, Alice can still accept any relayed computations from Bob to sign Bob's location-proof share. Can we do something with the multi-hop distance-bounding protocol (see #22 )?

[dbosk]

Assumption: Jane will not sign any proof share for someone who tries to cheat.

Jane can identify cheats using their $pid$'s. Furthermore, Jane can perform any computation $wsig \gets PRF_{k_J}(pid)$ and give $wsig$ to the cheater, she can later simply withhold the NIZK proof of its validity. This makes Jane indistinguishable from any other protester.

How can people who don't know each other organize the collusion? How can they distinguish Jane?

Assumption: The protesters cannot exclude Jane from participating in organizing the collusion.

Thus Jane can learn the $pid$'s of everyone who tries to cheat. Thus everyone is incentivized to perform the distance-bounding protocol. However, they need not follow it: anyone can (and has the incentive to) generate witness signatures even for those who failed the distance-bounding, they just don't send it to the protester (since it might be Jane testing them). Since the $pid$ and $wid$ of the witness are unlinkable ($PRF_{kW}(cid), PRF{k_W}(pid')$ are unlinkable), there is nothing Jane can do to detect cheats. Thus nothing to prevent them from sending these proof shares to the storage.

In fact, as soon as Jane has published her NIZK proofs, anyone is free to cheat. We thus have a waiting game.

[dbosk]

One solution might be that we assume all NIZK proofs published after Jane has published hers as attempts to cheat. The we would need another round of timestamping though.

[dbosk]

Assume limited collusion, i.e. the majority of protesters are honest. Then we can set a threshold in the number of needed signatures which is greater than the size of the collusion clusters. This would not need any change to the protocol, just adapt the security analysis to this.

Another approach (or complementary) is for a witness to only issue a maximum of N witness signatures. However, this requires a change in the protocol and I'm not sure about its effects.

[dbosk]

they actually connected to physical coordinates? Can, for example, a group of protesters collude and provide proof each other's location but actually only prove proximity to each other?

Well, the only thing the proof actually tells you is that a few individuals (as we've constructed it we know its not Sybil) has signed a statement saying you were in place (x,y).

So yes, there could be a group of people colluding and there is no way to tell the difference.

We've discussed two approaches (in #26): (1) We have a trusted witness and only accept proofs signed by her. (2) We assume limited collusion, i.e. we set a threshold for the number of signatures we require. The threshold must be set to a number larger than the number of people you can collude with. E.g. if we set it to 2000 you need at least 2000 actual friends to collude with you.

[dbosk]

What the verifier does is to collect all the proof shares, get all proof shares issued for a specific $pid$ and that set is the proof for the protester with ID $pid$. Each proof share is a signature, so just could all the proof shares that fulfil the required time (and location).

Actually, one possible attack is that Eve issues a lot of proof shares for a $pid$ but with different coordinates --- that will cause uncertainty about the proof of $pid$. (If Eve is the government, she can do this as a Sybil attack too, she can create as many unique witnesses as she likes.)

[dbosk]

This is solved now, it reduces to the properties of the anonymous credential system. (And finding colluding witnesses in the no-trusted-witnesses case.)