8
$\begingroup$

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?)

$\endgroup$
5
  • $\begingroup$ How many of the participants may be colluding with each other to provide multiple answers or colluding with you to infringe the privacy of others? You might be able to use some kind of MPC where a few participants provide randomness and you use it to derive a random permutation you can't know and apply it to the input. $\endgroup$ May 24, 2023 at 6:55
  • $\begingroup$ I don't see that "only uses e-mail" can be applied to the distribution of tokens if participants seriously attempt to vote several times: it's easy to create multiple email addresses. What constraint/freedom are there in the way the conductor "hand out tokens"? Can that be in a public ceremony that participants watch (in which case there are easy solutions)? Or a near equivalent, like participants queue to get the token so they can see how it's done for people near them in the line? Independently: Can it be used a trusted third party? A trusted device? $\endgroup$
    – fgrieu
    May 25, 2023 at 13:46
  • $\begingroup$ @fgrieu We know the e-mail addresses of all participants. I forgot to mention that. No, we cannot have a public ceremony, otherwise we’d just use a box and let everybody draw a token once. We never gather anywhere (at least it would make it too complicated this way). We might be able to use a trusted third party (or device, service), but I’m not aware of one which does what we need. So pointers to such a solution might be helpful as well. $\endgroup$
    – Alfe
    May 25, 2023 at 14:40
  • $\begingroup$ @CommandMaster We would encourage all participants to exchange their tokens, so if a group gathers and puts all their tokens in a box an draws one, that would be fine for us, but it’s up to them, so this might produce trust in the anonymity or at least that we aren’t interested in finding out which person uses which token. I don’t know what you mean with an MPC providing randomness, but that sounds intriguing. $\endgroup$
    – Alfe
    May 25, 2023 at 14:42
  • 1
    $\begingroup$ anonize.org/technology.html $\endgroup$
    – Andrew
    Jul 31, 2023 at 14:17

2 Answers 2

4
$\begingroup$

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.

enter image description here

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.

$\endgroup$
12
  • $\begingroup$ Please could you clarify what you mean by "They can also use a ring signature to add a new key to the set. This lets users add layers to the decoy tree." $\endgroup$
    – knaccc
    May 25, 2023 at 13:28
  • $\begingroup$ If I do a ring signature with my key +9 decoys, 10 people could have cast the resulting vote. anonymity grows linearly with ring signature size and N must be very big to get good privacy. If they can use these partially anonymised outputs as inputs for other transactions then the anonymity grows exponentially with the number of layers of transactions. The users together form a tangled mess of ring signatures feeding other ring signatures. This makes it much harder to tell which original key is tied to which final vote. $\endgroup$ May 25, 2023 at 16:22
  • $\begingroup$ Note that this assumes most users are honest. If most users are dishonest and colluding, privacy grows much less quickly. $\endgroup$ May 25, 2023 at 16:52
  • $\begingroup$ I understand how that applies to cryptonote, but I'm not sure how you're proposing it applies to voting $\endgroup$
    – knaccc
    May 25, 2023 at 17:37
  • $\begingroup$ If users are using an anonymity network, their actions are anonymous. If someone shows up with a valid ring signature, you have no idea which of the inputs were used to sign the ring signature. In the cryptocurrency keys stand in for currency, here they stand in for votes. To tie this back to the cryptocurrency analogy. A user can "cash out" their vote after it's been mixed with others by submitting another ring signature but this time the "output" is a survey response rather than another key. $\endgroup$ May 25, 2023 at 21:45
3
$\begingroup$

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.
$\endgroup$
2
  • $\begingroup$ Sounds intriguing, but using a registering step is out of the question for practical reasons. My users just won’t do this. We want to enable them to participate without much work (receive an e-mail, click on a link, fill out the form, send it). Only for the ones who distrust us and think we might identify them by their secrets, we also want to empower them to produce their own anonymity, e.g. by exchanging secrets among themselves. But the double use of secrets is a problem then. $\endgroup$
    – Alfe
    May 30, 2023 at 10:18
  • $\begingroup$ @Alfe it's not that complex, I added the workflow to the bottom of the answer $\endgroup$
    – knaccc
    May 30, 2023 at 11:19

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.