dbosk / crocus Goto Github PK

Securely and privately verifiable protests

License: Other

Makefile 2.31% TeX 97.69%

paper privacy protesting verification crowd-counting electronic-voting location-proof

crocus's Introduction

I’m Lecturer in Computer Science at the Division of Theoretical Computer Science, Department of Computer Science at the School of Electrical Engineering and Computer Science of KTH Royal Institute of Technology.

I'm interested in

e-learning and have developed distance courses/programmes since 2011,
teaching in programming and security,
research in didactics and computer security, particularly democracy-enhancing technologies.

I teach Python and security, I do a lot of automation in Python.

crocus's People

Contributors

Watchers

crocus's Issues

Improve protocol overview figure with proper notation

Turn it into a proper message-sequence diagram, that makes it easier to read.
Change NIZK proof notation to what is commonly used for Proofs of Knowledge, i.e. PoK with the secrets using greek letters.

Adapt acknowledgement of Protesting Chapter

Adapt the acknowledgement to the Protesting Chapter, since some material comes from there. However, if it's not published the acknowledgement can be removed entirely.

Implement needed anonymous credentials in library

We might have use of the code from Anon-Pass and adapt it to handle NIZK proofs. This relates to #27 . The paper P-signatures and Noninteractive Anonymous Credentials has a theoretical solution that might work for us, but probably no implementation.

ZeroCoin and ZeroCash both use zero-knowledge proofs, or to be exact zkSNARKs (zero-knowledge Succint Non-interactive ARguments), which should work for us.

Terrorist-fraud resistant distance-bounding protocol with malicious verifier

We must solve the terrorist-fraud resistance for the distance-bounding protocol. The problem is this: the protesters have no incentive to follow the protocol of performing the distance-bounding protocol, they have incentives to be dishonest. Thus they cannot be assumed honest verifiers. The only possible honest party is the trusted journalist Jane.

Terrorist-fraud resistance is based on the assumption that Alice will not forward the data to Bob if Bob could later impersonate Alice arbitrarily. We need that Bob must be able to impersonate Alice as a participant of e.g. a counter-protest. If it's only bound to the protest that Alice supports, she will not mind. And this will eventually lead to the protesters boosting their participation count.

Receipt freeness/Unlinkability vs Sybil

Can we have unlinkability between Alice and her proof and still achieve Sybil resistance? With unlinkability, what prevents Alice from obtaining a second valid proof? If Alice can be prevented from obtaining a second proof, cannot that be used to verify Alice's participation?

Emphasize various ways to prevent collusion

Emphasize the assumption about honest majority and setting a threshold larger than the size of any possible group of colluders. (From #57 )

Present as an alternative that it's possible to have a trusted entity there too. We have both the journalist Jane scenario and the solution presented in Le Monde (see #87). We can use the infrastructure developed for the solution in Le Monde.

Participant privacy

The $cid$ is static for a protest and represents a cause, \ie opinion, maybe government critical.

Hide $cid$. If the $cid$ is not hidden, the government can attend the protest and arrest everyone supporting $cid$. Also, witnesses might discriminate against participants with $cid$s they disapprove of. E.g. a small minority can never reach the threshold in the trustless scenario. So we should hide $cid$.
Blind $pid$. Since the pseudonym $pid$ is static for a participant during a protest and after. Each witness can map a person (e.g. take a photo) to the $pid$. When the associated $cid$ is revealed in the submission step, the government can again find the $pid--cid$ relation, and thus map persons (phots) to $cid$s. Thus we must blind $pid$ for the witnesses and then unblind $pid$, $wid$, $wsig$ in the verification phase, then we achieve unlinkability.

Since the witnesses computes $wid = PRF_k(pid)$ they should not be trackable across different proofs, only "within" proofs. We need an adversarial game which formally defined how hard this is. Probably the security analysis will be similar as for #29 .

Change paper format to PETS

This is being worked on in the PETS-formatbranch.

Check consistent terminology: protester, witness

The term user can be ambiguous. We want to ensure that we use the following terminology consistently:

a protester is someone who participates in the protest.
a witness is someone who witnesses the participation of a protester.

Who are the adversaries?

As foreign states, say Rusuk, might have interest in affecting the result, maybe we should cover that.

Since the PRF-key $k$ will be signed by the government, we can detect if the key of a proof is signed by a foreign government. Thus Rusuk cannot create valid proofs to increase the number of any foreign protest.

Ensure consistent use of Alice, Bob and Eve for readability

We should write consistently in the terms of Alice, Bob and Eve for readability.

Ensure to address Carmela's comments

During the IEEE WIFS workshop I got a review of our work by Carmela Troncoso. One comment worth mentioning was "You submit this to PETS in February, they'll love it".

The main comments she had that we should not forget to address are:

Analyse whether a social graph can be constructed from either communication or proof shares. Proof shares should be fine, since they are unlinkable. But the communication might actually reveal this, e.g. a witness uploads NIZK proofs for all witnessed proof shares.
Emphasize the assumption about honest majority and setting a threshold larger than the size of any possible group of colluders.

We've planned to do these, but these were the two main points she would consider as a reviewer.

Performance measurements

We want to measure how much computations and storage the protocol requires in different stages. We are mostly interested in efficiency (or lack thereof) during the protest, when all parts rely on battery. We need to evaluate

how expensive is the distance bounding proof of knowledge during witnessing (DBPK in Fig 5) for a witness?
how expensive are the needed PRF computations for the witness?

Assume that a witness must run the protocol 1000 times.

Communication: how expensive is the communication in terms of energy (battery consumption)?

keeping the Bluetooth/wifi on and scanning?
sending all the needed messages?

Storage:

what's the size of each proof share?

We should have a table of costs. Some entries can come from our performance measurements and some can come from the literature.

Broadcasting proofs for witnessing

Can we use ad-hoc networks or bluetooth? The latest spec of bluetooth seems to have increased the limit of 10m to 100m. Can it be used for broadcast?

We can always fall back to publishing them on the Internet? Although it would be undesirable to require an Internet connection due to government DoS attacks.

Add Venezuela protests as another example

The 2017 Venezuela protests are useful to have in the intro (and maybe the related work).

Merge authenticity with verifiability

In some sense, the properties under authenticity could be considered part of the eligibility property. Should these be merged?

Storage branch and merge

At some points there might be reason for the network around the blockchain to split. What will happen with the blockchain-free stuff then? Can it simply merge if everyone has been honest? The problem is double-spending attacks, for those some transactions must be invalidated.

Put copy on arXiv

Authors are strongly encouraged to register their manuscript in arXiv preprint server and submit it to our Editorial Manager using arXiv's paper ID.

Upload to arXiv.
Make GitHub repo public.

Proving temporal eligibility, hardness definition

We need to relate the proofs to time, both formally in the model and in the protocol.

The protocol will simply use a hash chain to create a poset. (A blockchain or similar data structure will also work.) Either we rely on timestamps being added by some trusted entity or something like the fact that a new block is created every 10 minutes (as in Bitcoin). This way everything that is submitted to the chain can be related to time.

More formally, we need to relate each proof to time. E.g. a proof's possible time-interval is a function of the proof and the chain.

Update abstract

The abstract should better represent the final paper:

What's the problem?
Why is it a problem?
What's the approach?
What are the results?

Security definitions of individual and universal verifiability

We need adversarial games for individual and universal verifiability. In general I think we must show soundness and completeness, i.e. that we can prove what we want.

What are the roles in the system?

Who does what? There should be a description in the Protocol section who does what, to outline who sends what to whom. This might also be useful in the System Model section.

We have

organizers
protesters
witnesses
verifiers

Possibly interesting literature on voting

There is an old (2010) conference proceedings on voting:

https://link.springer.com/book/10.1007/978-3-642-12980-3/page/2

Analyse possible during-protest inferences/linking

From #57 .

Analyse whether a social graph can be constructed from either communication or proof shares. Proof shares should be fine, since they are unlinkable.

The communication might actually reveal this, e.g. a witness uploads NIZK proofs for all witnessed proof shares (see #32). Also the submission pattern to the blockchain. This is reduced to traffic analysis.

Systematically fix "e.g." and "i.e." in paper

There is the package foreign which does this. We should use it: this would change "e.g.\ " and "\emph{e.g.}" to "\eg".

Add EuroStat code of practice to motivation

EuroStat has a code of practice which contains some guidelines about the quality of their statistics. Maybe we can use it to argue for improved statistics. It can be found here:
http://ec.europa.eu/eurostat/web/quality/european-statistics-code-of-practice

Write a complete system model

Add the different phases of the protocol (#44) as algorithms used in the system model?

Split protocol into phases

Split it into a setup phase, etc:

Setup: issue keys with blind signatures.
Organizing: write manifesto and publish.
Joining: ask for manifesto, approve or reject (i.e. abort protocol).
Participate: Compute $cid$ and proceed with the protocol in the figure.
Verify: verify the validity of the proof shares and count the valid proofs.

Defs etc in hidden frames increase counters

When using the overlay specification <presentation> on frames, things inside, like definitions, are still "executed", so a hidden definition increases the counter in the article. This doesn't happen with \mode<presentation{...}.

Change all

\begin{frame}<presentation>
...
\end{frame}

into

\mode<presentation>{%
\begin{frame}
...
\end{frame}
}

NIZK anonymous credentials for protester and witness identifiers

To designate the event: each protest has a cause, this cause can be documented in some type of manifesto. Simply run this manifesto through a hash function to get a unique ID.

To ensure one-proof-per-person we can use a technique from Camenisch (How to Win the Clone Wars, CCS 2006):

An authority blindly signs a PRF-key $k$.
Protester computes $y \gets PRF_k(id)$, where $id$ is the unique protest ID (hash of manifesto).
Protester computes a non-interactive zero-knowledge (NIZK) proof of: $y$ is the result of a PRF-computation with the key $k$ and that the key $k$ is signed by the authority.

To get "receipt freeness" (forward secrecy?) we must delete $k$ after the protest (see #23).

We can simply give $y$ to someone, but an interactive zero-knowledge proof of knowledge of $k$ will solve that (e.g. for Jane to trust she is talking to the right person).

Implement needed distance-bounding protocol in library

We need to perform the computations needed in the distance-bounding protocol, i.e. those computations done in the setup and verification phases. It seems to be difficult to implement the distance-bounding phase other than in hardware. But maybe Sébastien has more insights.

How to propagate the protest ID?

For protesters to be able to participate, they must know the protest ID. Actually they should know the protest manifesto and through that the protest ID follows.

The organizer can make a placard with a QR-code going to a website with the manifesto. Users scan the code with their phone and those who agree can compute the hash of the manifesto and use that as an ID.

State assumption already in introduction

E.g. that by Alice we mean Alice's cryptographic key (or at least her device).

What authority should issue credentials?

A fair assumption is to use the government-issued credentials available in national identity-cards. Or identities issued by some cothority of governments, e.g. EU or UN.

There seem to be some alternative approaches to this. Proof-of-personhood relies on "pseudonym parties" (Bryan Ford, SocialNets'08, "An offline foundation for online accountable pseudonyms"). A few organizers form a cothority with an anytrust assumption (one of the organizers must be honest). Then people meet in a physical location to get a token. The guarantee is one token per person if you trust one of the organizers.

It seems more like it that our solution can improve the proof-of-personhood than the other way around.

Decide on acronym and title

Alternatives:

Proof privacy (in storage)

We need the proof to be unlinkable to Alice. We need an adversarial game which formally defines the hardness to violate privacy.

Given the protest pseudonym ($y$) which is derived from the blindly signed key $k$ using the PRF, Eve shouldn't be able to figure out who belongs to $y$. This probably follows from Camenisch's paper (see #27 ).

Fix Henri's entry in the author list

@HePineau, can you update your entry in the author list (in paper.tex)? I'm not sure what email to put. I suppose the affiliation should be UQÀM, check with Sébastien if you're unsure about the University's policy.

Make sure to fix it both in the master branch and the PETS-format branch, the latter is more important.

Improve ProofFig to have more details in the figure

Currently \cref{ProofFig} has an overview sketch of the structure of proofs and proof shares. This one should be updated to contain slightly more details, e.g. an arrow from manifest to $cid$ with $H(\cdot)$ on the arrow.

Move some protocol details to building blocks?

Shall we move the parts of the protocol which is similar to Anon-Pass to the building blocks and simply use the AC-scheme notation in the protocol?

Then we can specify the proofs of knowledge for each AC algorithm in the building blocks too.

I think this abstraction is possible. And it would be good for two things: readability and reducing the proofs to the proofs of those algorithms. Then we only need to prove the new parts we do.

Proving spatial eligibility, hardness definition

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).~~

Update Related Work section

Danielis, Peter and Kouyoumdjieva, Sylvia T. (KTH, School of Electrical Engineering (EES)) and Karlsson, Gunnar (KTH, School of Electrical Engineering (EES)): UrbanCount: Mobile Crowd Counting in Urban Environments

Surveillance, management and estimation of spontaneous crowd formations in urban environments, e.g., during open-air festivals or rush hours, are necessary measures for city administration. Most solutions that implement these measures however require additional costly hardware installations (e.g., installation of observation cameras) and infrastructure support, and often pose privacy concerns. In this work, we present UrbanCount, a fully distributed crowd counting protocol for cities with high crowd densities. UrbanCount relies on mobile device-to-device communication to perform crowd estimation. Each node collects crowd size estimates from other participants in the system whenever in communication range and immediately integrates these estimates into a local estimate. The objective of UrbanCount is to produce a precise mapping of the local estimate to the anticipated global result while preserving node privacy. We evaluate the proposed protocol via extensive tracedriven simulations of synthetic and realistic mobility models. Furthermore, we investigate the dependency between accuracy and density, and demonstrate that in dense environments the local estimate does not deviate by more than 2% for synthetic and 7% for realistic scenarios.

DiVote: A Distributed Voting Protocol for Mobile Device-to-Device Communication

Distributed aggregation algorithms have traditionally been applied to environments with no or rather low rates of node churn. The proliferation of mobile devices in recent years introduces high mobility and node churn to these environments, thus imposing a new dimension on the problem of distributed aggregation in terms of scalability and convergence speed. To address this, we present DiVote, a distributed voting protocol for mobile device-to-device communication. We investigate a particular use case, in which pedestrians equipped with mobile phones roam around in an urban area and participate in a distributed yes/no poll, which has both spatial and temporal relevance to the community. Each node casts a vote and collects votes from other participants in the system whenever in communication range; votes are immediately integrated into a local estimate. The objective of DiVote is to produce a precise mapping of the local estimate to the anticipated global voting result while preserving node privacy. Since mobile devices may have limited resources allocated for mobile sensing activities, DiVote utilizes D-GAP compression. We evaluate the proposed protocol via extensive trace-driven simulations of realistic pedestrian behavior, and demonstrate that it scales well with the number of nodes in the system. Furthermore, in densely populated areas the local estimate of participants does not deviate by more than 3% from the global result. Finally, in certain scenarios the achievable compression rate of DiVote is at least 19% for realistic vote distributions.

Protest or demonstration?

Which of the terms should we use: protest or demonstration?

Demonstration seen to be the most correct term. But it can easily be confused with what we call a "demo", thus favouring protest.

However, a protest is not necessarily a gathering of people in a physical location. On the other hand, we can simply replace the location proof with some other piece of data to change it to another type of protest. Thus making protest the most general term.

On the other hand, the definition of demonstration is to express an opinion, which is not necessarily a protest (it can be in agreement). However, as we cannot securely verify demonstrations in agreement of the government, most demonstrations we can verify turn into protests.

Keep protest as the term?

Adapt blockchain for implementation

We should be able to run on any blockchain. The most general ones are:

Ethereum
Algorand (proof-of-stake)

It should be quite straight forward to implement our protocol on these.

What to assume and not about the storage (blockchain)

How much should we assume about the storage? We had a discussion about letting it be run by independent organizations with conflicting interests, e.g. each country participate as a node --- i.e. the countries must collude to drop proofs etc.

A blockchain must be slightly adapted, e.g. all these "altcoins", except maybe for Ethereum. Then we'll go all the way to P2P. However, if we go for the various organizations running it together, they don't need the monetary mining incentive to run the infrastructure.

dbosk / crocus Goto Github PK

crocus's Introduction

crocus's People

Contributors

Watchers

crocus's Issues

Recommend Projects

Recommend Topics

Recommend Org