I want to conduct an anonymous Internet survey (e.g. “What’s your favorite fruit?” with a multiple choice answer) among a given set of people. Double answers by the same participant are not allowed.

I’m looking for a method to conduct this survey using only e-mail and a web page (and maybe trusted software) in a way so that the participants can be sure it is anonymous and that the conductor is sure that the participants filled out the form only once.

My idea is to hand out tokens (one to each participant), which act somehow as a key to unlock the survey, and a link to the survey itself. My problem is that using the tokens directly as keys would destroy the anonymity. So maybe the method allows that the participants somehow modify their personal token (using some random number) so that it (a) still can unlock the survey and (b) does not allow finding out the original token, hence the anonymity is kept.

I also considered telling the participants to simply exchange their given tokens among themselves (as in a tumbler) to break the connection between token and participant and so create anonymity. But that raises new questions about how to prevent/detect if a participant uses both their original token and the exchanged token.

I also think my plan goes somewhat into cryptographic e-voting, so maybe also there might lie a solution.

So here’s my question: Is there a method which is somehow close to my idea which only uses e-mail and a web page and how does it work?

Or, is there some kind of service on the Internet which could help distribute the tokens in a convincing way so that all my participants can be sure they stay anonymous when filling out the survey?

Or, is there any other way of achieving my goal using other Internet services I did not think of?

I’m also glad if someone can point me the right direction in terms of basic knowledge I might lack.

(Things I looked at and which didn’t solve my problem: Idemix, U-Proove, Unique, anonymous online authentication, State of the art techniques for Anonymous Authentication?)

Blind signatures

One easy way to let users swap tokens is to let them request the authority re-issue tokens blindly. This is how e-cash works but here instead of issued notes being redeemable for currency, they allow you to take the survey or request a blind signature on a new note.

Blind RSA signatures or blind Schnorr signatures would be the way to go.

Note that this allows ballot box stuffing. The results aren't verifiable.

Another option would be to carry out the survey initially and blind sign the responses. Later, the participant uses another anonymous channel to submit it. This is essentially the proposal of [this answer].(https://crypto.stackexchange.com/a/106630/19869)

The difference between the two responses is that blind signing a key for later use lets you choose the responses during submission, whereas blind signing the response has you fill out the survey during the first contact and returns a bundle for later submission.

Linkable ring signatures

Another option that gets rid of the authority would be linkable ring signatures. This is the same thing used in CryptoNote based currencies.

Back’s Linkable Spontaneous Anonymous Group (bLSAG) signatures

Users cast a vote by creating a ring signature from one of N keys, their key, and N-1 decoys. There's some extra magic that prevents a key from being used twice by having a "linking value" in the transaction that depends on the actual key used for signing.

Users get a token that allows them to publish a key to the list of allowed keys. A ring signature using keys from the allowed set allows for submitting a transaction. Transactions either add a new key to the set of allowed keys or submit a survey response.

Each resulting vote can be seen as a tree of possible inputs with each transaction being a node that leads to other nodes eventually bottoming out to the original keys tied to the tokens sent via Email.

The green nodes are the keys, ring signature and votes submitted by one user. Notice how they link their vote to multiple transactions and through those transactions to many of the original non-anonymous keys. This creates a directed acyclic graph of links between votes and the original email linked keys.

The authority must not know the secret key corresponding to the non-anonymous keys. If they do, they know the the linking value used to prevent double spending and can link it to the transaction that spends it. No anonymity is provided by using it as a decoy. The Authority can use the voter's published public key or the voter must use that initial key to mint another (with a simple non-ring signature) before using it later.

Someone needs to run the ledger but they don't need to be trusted except not to delete transactions outright from it. Either have the ledger operator sign receipts for collected transactions or do a distributed ledger as in traditional blockchains.

performance and anonymity

The only reason to use this method is to have the results be verifiable.

The anonymity provided is less than that provided by blind signatures and performance, code size, everything else is worse. Good anonymity requires either monstrously sized ring signatures or that users submit multiple key minting transactions that form a well connected tangle. Participants that collude can reveal where each node actually goes removing it from the graph of honest transactions and reducing anonymity for non-honest users.

Recent work "Omniring: Scaling Private Payments Without Trusted Setup" makes this scale a lot farther since they get ring signature size and verification time down to something logarithmic in ring size. Ring signature generation time is still linear but that's a per-user cost.

In theory a downloadable app could implement this sort of protocol.

Your users need to be using an anonymity network

I'm assuming users have access to anonymous channels (IE:participants are using TOR or I2P anonymity layers so the polling organisation can't just match user IPs to votes. If you want something that's robust to that you'll need a real e-voting protocol.

Good e-voting protocols that allow groups of users to combine votes together so that the organisers only see the final tally are going to require multi round protocols between the people doing the combining. That might not be practical if everyone isn't online at once or can't leave a long running program open to run the protocol.

Email and a web browser

A web browser is a program that runs web pages. Allow users to download your "application" which is just an HTML page with embedded javascript that does all the crypto stuff. That's all you need to do to deploy arbitrary applications. In theory you could embed an entire implementation of TOR to be used over a websocket.

Since this is a survey, I assume that the submissions do not need to be publicly verifiable.

A simple approach you can use is Verifiable Oblivious Pseudorandom Functions (VOPRF). This is the technique behind the Privacy Pass protocol.

The conductor of the survey publicly publishes a (private, public) EC key pair $(a, A=aG)$, where $G$ is a well-known base point on the curve.

A participant creates a uniformly random scalar $r$, and a uniformly random blinding scalar $b$.

The participant registers (non-anonymously) for the survey by sending $X=bH_p(r)$ to the conductor, where $H_p(r)$ means to apply a cryptographically secure hash to $r$ and interpret the result as a valid EC point in the group generated by the base point $G$.

The conductor replies with $Y=aX$, along with a "discrete log equivalence proof". This is proof that $Y$ has been created using the conductor's private key $a$ corresponding to the conductor's published public key $A$, and the conductor has not used a value other than $a$ in order to track the participant.

The participant unblinds the response by calculating $Z=b^{-1}Y==b^{-1}abH_p(r)==aH_p(r)$.

Now, the participant can send $Z$ and $r$ to the conductor, along with their survey response, using an anonymous communication channel. It is important that this communication channel authenticates the conductor to the participant, to avoid a man-in-the-middle attack that substitutes a different survey response (HTTPS/TLS can be used to achieve this).

The conductor can verify that the unblinded token is valid, by checking $Z\overset{?}{=}aH_p(r)$. Since someone with knowledge of $a$ would have been required to collaborate to create $Z$, the conductor knows that the token is valid. However, the blinding mechanism prevents the conductor from knowing which participant it helped create the token for.

The simplest possible workflow would be:

1. User receives a link via email. The link contains a survey access authentication token that instantly authenticates them to the web site, so they do not have to manually log in or enter a password
2. Clicking the link automatically runs Javascript that requests a survey response token and unblinds it. The user is then shown a link they can click on to answer the survey questions. The link is of the form https://www.example.com/survey/<UNBLINDED TOKEN> Optional: The user can also take a copy of the discrete-log-equivalence proof shown on the page, if they are interested enough to verify that the server did not attempt to poison the token such that it is trackable.
3. Depending on their level of caution, the user can then change their internet connection to operate over a VPN or TOR, open up an incognito window, and use the link to fill in the survey. If they are not at all concerned about their privacy, they can just take your word for it that you're not tracking them, and directly click the survey response link without going incognito.