Elliptic Curve Cryptography & Online Voting

Elliptic Curve Cryptography, or ECC, is the kind of cryptography most widely used for blockchains. It is used to validate new transactions to the blockchain and ensure that the transactions are authorized to execute. For example, if a transaction spending Bitcoin appears on the Bitcoin blockchain, ECC is used to verify that the owner of the bitcoins authorized the transaction spending them.

In order to understand what ECC is and how it works, one must first understand modern cryptography in general, especially symmetric and asymmetric cryptography.

Symmetric Cryptography

The most widely understood type of cryptography is symmetric cryptography, also known as classical cryptography or secret-key cryptography. Symmetric cryptography is mostly used to scramble information so unauthorized parties cannot read it. Specifically, two people agree on a secret piece of information, and whenever one of them wishes to send a message to the other, the sender uses the secret information to scramble the message and the receiver uses the same information to unscramble it. Anyone without the secret information is unable to unscramble the message, so it is kept private. The name “symmetric” comes from the fact that the sender and receiver both have the same secret information; in other words, the information is the same on both sides, so it is symmetrical.

Symmetric cryptography has been around for thousands of years. Originally the secret information was simply the steps involved in scrambling (or unscrambling) the message; however, this turned out to be susceptible to attacks (called cryptanalysis) because there are only so many ways to scramble a message so that it can be unscrambled, and someone can usually guess how the scrambling works using statistics and by guessing at what the unscrambled message is and trying all the possible scrambling techniques to see which one fits. In modern symmetric cryptography, the steps involved in scrambling are public and the secret information is a number which is scrambled into the message. Anyone who doesn’t know the secret number can try to unscramble the message with random numbers, but unless they guess the right one, the message unscrambles to nonsense and is still unreadable. Only someone who knows the secret number can unscramble the message to its original form. Of course, anyone could get lucky and guess the secret number, so the secret number is always very large (hundreds of digits long). Someone could theoretically be lucky enough to guess it, but modern cryptography is based on the prediction that no one is that lucky.

The problem with symmetric cryptography is that the secret number (called the key) is simultaneously confidential and shared. It tends to be difficult for two people to agree on this secret number without leaking it to anyone else. Enter asymmetric cryptography.

Asymmetric Cryptography

Unlike symmetric cryptography, asymmetric works without the sender and receiver knowing the same key. Instead, the receiver creates a private key and calculates a public key from it. He then publishes the public key and anyone who wishes to send him a message can encrypt it with the public key, but only the receiver can decrypt it with his private key. This is more secure because it doesn’t matter who gets the public key, and the private key is never shared. As before, it’s possible that someone could guess the private key, but that would require them to be unfathomably lucky, so we don’t worry about it.

As before, it’s possible to use asymmetric cryptography to encrypt and decrypt messages, but this is much slower to do than with symmetric cryptography, so in practice we usually encrypt a symmetric cryptography key with asymmetric cryptography to share it, then use that key to send private messages using symmetric cryptography. In this way, the two complement each other, providing both security and speed. This approach is known as hybrid cryptography.

Asymmetric cryptography has a wider use than just sharing symmetric keys though: signatures. Until now, we’ve talked about sending secret messages, but a second use of cryptography is to verify that a message is authentic, specifically that it comes from the expected sender and that it hasn’t been tampered with in transit. This is the primary use of asymmetric cryptography: a sender signs a message with his private key, and the receiver checks the signature against the message using the sender’s public key. If the signature is valid, it means that only a holder of the sender’s private key could have sent the message (thus, it must have been the sender because he never shares his private key), and no one tampered with the message in transit or the signature would not longer apply to it.

Elliptic Curve Cryptography

Now that we’ve discussed symmetric and asymmetric cryptography, we can understand ECC. ECC is a type of asymmetric cryptography, so it uses key-pairs (a private key and public key). There are two main ways ECC is used. The first is to sign messages, using a technique called the Elliptic Curve Digital Signature Algorithm, or ECDSA for short. The second is to share symmetric keys to encrypt messages, using a technique called the Elliptic Curve Diffie-Hellman key exchange, or ECDH for short.

When blockchains use ECC, they almost exclusively use it with ECDSA for signatures. On the Bitcoin blockchain, all bitcoins balances are marked with an ECC public key belonging to the owner of the bitcoins. If the owner wishes to spend some bitcoins, he creates a transaction declaring which bitcoins he wishes to spend and the public key of the recipient. He signs this transaction with his private key and publishes the transaction and signature. All participants in the Bitcoin network verify that the signature is valid and corresponds to the public key which owned the bitcoins being spent, then they update their records to indicate that the bitcoins now belong to the recipient’s public key. This process is largely automated, but it can be seen when spending bitcoins: the recipient must provide an “address” which is a textual representation of his public key, and the sender directs his Bitcoin wallet to send bitcoins to that address.

How We Use Elliptic Curve Cryptography

At Follow My Vote, we use this technology to create votes. During the registration process, voters create two ECC key-pairs. The voter reveals her identity to a verifier, who certifies the first key-pair (the identity key-pair) as belonging to that voter, then the voter anonymously registers her second key-pair (the voting key-pair) as belonging to one of the identity keys, but the way this is done, no one can determine which identity key owns her voting key. She can then create transactions which state her votes on the contests in an election, and use her voting private key to sign those transactions. Once these are published, everyone participating in the Follow My Vote network can verify that the signature is valid and adjust the tally accordingly. This way the votes are public and anonymous, but each voter can verify that her vote was correctly recorded and counted. Furthermore, all participants can verify that none of the votes were tampered with by validating the signatures. In this way, Follow My Vote software performs transparent, end-to-end verifiable online elections without compromising on security or voter anonymity.