Grant Discussion On-Chain Voting Protocol Grant: Milestone 7

Secured
#1
Factomatic is excited to share the report on privacy-preserving voting on the Factom blockchain. You can find it attached.

We propose two different voting protocols, one based on ring signatures and a second one based on homomorphic encryption and zero-knowledge proofs. We hope you enjoy the report and are happy to answer any questions.
 

Attachments

Secured
#2
Thank you for writing this up! It's truly fascinating.

1. The use of commit - reveal for on chain voting where the reveal is not an automated process is still highly concerning to me. I realize this has to do with the underlying voting protocol and not what you present here today, but I wanted to mention it again. Requiring people to in essence vote twice is going to cause problems in a world where getting them to vote once is hard enough. If someone can come up with an efficient means to automate this, then it's a non issue.

2.
To make the process trustless, but at the same time robust, we suggest a distributed encryption scheme, meaning that it requires the cooperation of several parties to decrypt the results.
Is there any reason this can't be implemented in a manner where it's not people but decentralized systems that cooperate to decrypt the results? The systems are programmed in a manner where they automatically decrypt the results at a certain time unless there is manual intervention by the system's operator. When it comes to voting, people need to know that the results WILL be revealed at a certain time. I always worry about people not doing their jobs, especially when X (who may be globally distributed) need to perform the same task for it to be successful.
 
Secured
#3
Thank you for writing this up! It's truly fascinating.

1. The use of commit - reveal for on chain voting where the reveal is not an automated process is still highly concerning to me. I realize this has to do with the underlying voting protocol and not what you present here today, but I wanted to mention it again. Requiring people to in essence vote twice is going to cause problems in a world where getting them to vote once is hard enough. If someone can come up with an efficient means to automate this, then it's a non issue.

2.
Is there any reason this can't be implemented in a manner where it's not people but decentralized systems that cooperate to decrypt the results? The systems are programmed in a manner where they automatically decrypt the results at a certain time unless there is manual intervention by the system's operator. When it comes to voting, people need to know that the results WILL be revealed at a certain time. I always worry about people not doing their jobs, especially when X (who may be globally distributed) need to perform the same task for it to be successful.
1. I completely understand your concern. You could in principle automate the revealing, but not really in a trustless way (or at least I'm not aware of one if it exists) and it would defeat the purpose of having it in the first place. That said, the second protocol we have suggested -- based on homomorphic encryption and zero-knowledge -- I believe could get around this, but it would require some more investigation. With this protocol, you have the identity of the voter revealed, as they sign the messages they record on-chain with a vanilla digital signature. However, the options they voted for and the weight they assigned to each option are hidden and they don't have to be revealed by the voter. Essentially, the voter only casts their vote once and forgets about it. However, we would have to check if there are adaptive adversary attacks to this approach: i.e. security attacks on the protocol, which rely on the fact that there are no vote commitments, so you're free to construct your encrypted vote in potentially malicious ways.

2. There is no reason and that would be exactly the way to go, should we decide to implement such a system. Any party interested in securing the voting protocol, could download an open-source software, which runs as a daemon (similar to factomd or fatd, e.g.; or to the current on-chain voting daemon we're using). This daemon monitors special vote registration chains, registers as a processor for the vote and then participates in the decryption phase by contributing its share in a period between two blocks, which have been configured when the vote was created.
 
Secured
#5
Cryptographic capabilities are truly amazing, that's one of the closest thing to magic I know of! Nice read, thanks @Valentin Ganev! Traceable ring signatures sounds like a truly perfect fit for voting systems (weighting apart) and "relatively simple" to understand and put in practice. Homomorphic encryption is pretty hardcore in comparison.

Your conclusion is:
but require considerable scrutiny from cryptographic experts before being used in production.
What do you mean exactly? Ring signatures for instance have been around for some time, why couldn't we start using it right now?
 
Secured
#6
I cannot open link 7

We note that the security properties of the signature scheme are argued in the random oracle model [7], due to the reliance of the signatures on the Fiat-Shamir heuristic [8] for producing a non-interactive zero-knowledge proof of a secret key corresponding to a public key, which is part of the ring.
What does that mean exactly ? What is the "weak link" of this system in terms of security?
 
Secured
#7
Cryptographic capabilities are truly amazing, that's one of the closest thing to magic I know of! Nice read, thanks @Valentin Ganev! Traceable ring signatures sounds like a truly perfect fit for voting systems (weighting apart) and "relatively simple" to understand and put in practice. Homomorphic encryption is pretty hardcore in comparison.

Your conclusion is:

What do you mean exactly? Ring signatures for instance have been around for some time, why couldn't we start using it right now?
Glad you enjoyed it, Paul! We could use the traceable ring signature or the HE/ZKP approach right now IMO. However, the big caveat is that I'm not a cryptographer, so what I meant by the above is that I think no matter which approach we use, there should be an expert cryptographer reviewing it and also reviewing the code that is used or we end up writing. Essentially, we would need a security audit before potentially going live with either of those solutions.
 
Secured
#8
I cannot open link 7


What does that mean exactly ? What is the "weak link" of this system in terms of security?
Hmm, I'm able to access the link here: https://cseweb.ucsd.edu/~mihir/papers/ro.pdf. The title of the paper is "Random Oracles are Practical: A Paradigm for Designing Efficient Protocols", you could Google it if you're interested to find more details. It's a rather popular publication (4800+ citations).

I would also refer you to this simple explanation, as well as the Wikipedia article on Random Oracles, which gives a very accessible overview.

Bottom line is that a random oracle is a function accessible to everyone in the system (adversaries included). This function outputs a unique (and random) output for each input it receives. There is some concern about the random oracle model, as it places an assumption over cryptographic hash functions, which is not part of the "standard model", namely that the output of the hash function to every unique query is uniformly random over its output domain. While this is not the case in theory, in practice a hash function is deemed a good enough approximation of a random oracle for a large number of problems.
 
Secured
#10
About the broken link I think it's because in your pdf the ~ is missing (at least when with my PDF reader)

Ok now I'm clear on the random oracle/hash function thing. So hash functions are deemed good enough to be used for ring signatures right?
Yes, you're right about the link...

Yes, hash functions are used for the Fiat-Shamir heuristic (in both protocols we suggested actually) and it's fine to use them for this purpose.