13

The problem

I am in charge of implementing a secure, secret election for a small group of students on my school. I have a list linking valid student IDs to emails, and I want each one of them to vote in a candidate that will ultimately be elected. It is acceptable to use that email for authentication.

Naive solution

The obvious solution would be ask each student to mail me a public key, put a simple web-UI that used such key to cryptographically sign a vote (client-side), and then a HTTP server that received signed votes, incremented the candidate's vote counter, and erased the info. This is mostly secure, but there is still one problem: a malicious agent with access to the server could be able to see and log the vote of each particular student. Of course, I won't do that and the students trust me not to do it - but, since this is a CS course, I'd like to be able to use the opportunity to make a point and create a cryptographically safe ballot on which no party at all should be able to see the votes.

My solution

After some research, I've come to what I think is the perfect solution, which is Linkable Ring Signatures. It would work the same as the system above, with the small modification that we'd keep public map of StudentID -> PublicKey, and each student would sign in name of each other student. The server is, then, able to verify that the vote came from an actual student, without being able to tell which. If a student votes twice, it is able to detect so using the "Linkable" aspect of those signatures.

Question

Unfortunately, I couldn't find any verified, open-source implementation of linkable ring signatures. I'm aware Monero uses a similar cryptographic scheme to grant anonymity to its users. I wonder, thus: is there any way Monero can help me implementing my system?

1 Answer 1

10

This is possible with a "daughter" project of Monero called URS (Unique Ring Signatures) and was introduced by core-team member tacotime. From the README of the repository:

URS can be used to sign plaintext or binaries anonymously (among a group of known users). That is a user can sign a message, hiding among a group of known/registered users, that prevents the verifier from revealing the signer's identity other than knowing that it is in the set of registered users. The size of the set of registered users is flexible. Increasing this number slows down signing and verifying linearly, and also increases the size of the signatures linearly.

Bitcoin public and private keys are used to generate the signatures. You may generate your own keypairs with the set-generate function described below. Bitcoin addresses are also generated.

When in default (unique) mode, signatures are generated with the prefix '1' and contain immutable Hx, Hy values as the first two bigints in the signature. These are immutable per message and private key. That is, any single message signed with the same private key and keyring will always generate the same Hx, Hy values, so for this single message you can identify if multiple members of the keyring have signed (but not which one).

Signature blinding has also been implemented. Blind signatures are prefixed with '2'. While blind signatures lose their Hx, Hy uniqueness, they use an ephemeral key to generate that signature that is afterwards discarded. This will prevents someone in the future from being able to identify which member of the ring signaturesigned the message, even if all private keys for the public keys in the keyring are later revealed.

For more information on signature blinding, refer to this link.

From the abstract of the paper:

Abstract. We propose unique ring signatures that simplify and capture the spirit of linkable ring signatures. We use new techniques to provide an instantiation which can be tightly related to the DDH problem in the random oracle model, leading to the most efficient linkable/unique ring signature.

With these sources you should be able solve your "problem".

2
  • How Unique Ring Signatures solve my problem if they are only linkable when a user signs the same message? E-voting requires identifying if the same user signed two different messages on the same ring (i.e., "I vote X", and "I vote Y")...
    – MaiaVictor
    Sep 11, 2016 at 12:23
  • @Viclib: You should read this thread (bitcointalk.org/index.php?topic=768499.0;all) and in particular message #26.
    – Clement J.
    Sep 12, 2016 at 21:13

Your Answer

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

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