SIV Now Uses Elliptic Curve Cryptography

We've released the biggest upgrade to SIV since its creation: Elliptic Curve Cryptography.

This means SIV is now able to achieve vast security levels, all while remaining ultra fast.

Summary

• Attempting to brute force the underlying cryptography behind SIV now costs more than billions of times global GDP.
• All of SIV's cryptography, including the full Zero-Knowledge Proofs of accurate results, can be generated and confirmed in just seconds.

What's this for?

SIV makes it easy to run fast, private, and completely verifiable elections.

Under the hood, SIV relies upon a number of cryptographic operations:

1. There's the basic public-key encryption system, for keeping votes private.
2. There are homomorphic cryptographic shuffles, for anonymizing votes before they are unlocked.
3. Those also include Zero-Knowledge Valid Shuffle Proofs, to ensure each shuffle doesn't replace or modify any of the underlying votes.
4. SIV allows multiple parties ("Verifying Observers") to work together, to divide the decryption key into multiple parts. This relies upon a Decentralized Verifiable Key Generation Ceremony.
5. When the parties are ready to unlock the shuffled votes, they each do a Partial Decryption, also including Zero Knowledge Valid Partial Decryption Proofs.

One-Way Functions

Each of these depend upon cryptographic difficulty, so called "hard" computational problems. These can be used to create "One-Way Functions": operations that are quick to do in one direction, but far more difficult to attempt to reverse.

For the last year, SIV has based these on the hardness of calculating a "Discrete Log", over a Finite Field.

This means that for some big ("safe") prime number p and a secret value x, it's quick and easy to calculate 4 ^ x % p — 4 raised to the power of x, modulo p. This is often called modPow for short, and we can call the result y.

But reversing the operation is very hard. Even if y, 4, and p are known values, x can be made completely impractical to recover. That would be calculating the base-4 logarithm of y, in the discrete "finite field" p.

This is an amazing result of mathematics, discovered by Stanford researchers Martin Hellman and Whitfield Diffie in their paradigm shifting 1976 paper "New Directions in Cryptography". It has served as the basis for nearly all digital network security: every time we create an https connection, we use it for the initial "key agreement handshake".

Tradeoffs

When designing security, it's useful to think in terms of "cost to attack". No system is completely impenetrable, but defenses can be strengthened through individual upgrades, each step increasing the cost to attack.

For example, say someone wanted to protect a building:

1. To start, they may have only closed doors.
2. They could add locks to the doors.
3. They could add signs that say "Trespassers Will Be Prosecuted".
4. They could add a small simple fence.
5. They could add a higher, metal fence.
6. They could add razor wire atop the fence.
7. They could add security cameras.
8. They could hire live guards posted around the perimeter.

Each addition increases the difficulty of getting inside, the "cost to attack". Each addition also brings its own cost to the defenders, such a paying for the material or the ongoing staffing costs for guards.

So it's useful to set a threshold for "What are our security requirements? How difficult must it be to attack our system?" — called Thread Modeling — and then figuring out what it takes to establish such defenses.

Cryptographic Security Levels

One-way Cryptographic Functions work the same way. By simply increasing the size of the prime number p, we can increase the "Security Level" of a particular operation. This "Security Level" tells you how many operations it takes to reverse the function, log base-2.

So if the security level is 10, that says it takes 2^10, which is 1024 operations.

But computers are very fast — the smartphone in your pocket can do on the order of a billion operations every second. So we need much higher security levels.

NIST, the U.S. National Institute of Standards and Technology, has published SP 800-57 - Recommendation for Key Management, which recommends 128 bits of security for government systems.

This means 2^128 operations, or approximately 3.4 x 10^38, which spoken aloud is:

340 undecillion 282 decillion 366 nonillion 920 octillion 938 septillion 463 sextillion 463 quintillion 374 quadrillion 607 trillion 431 billion 768 million 211 thousand 456

One of the largest publicly known attacks on a cryptographic system cost ~$45k for 900 rented GPUs over two months, breaking a 63.4 bit system.

To extrapolate this to 128 bits, there's a gap of 128 - 63.4 = 64.6. That means the cost to attack a 128 bit security level is 2^64.6 times higher. With the previous cost of $45k, this makes the cost to attack 128 bits equal to $1.2 x 10^24, or over a Septillion Dollars.

The combined GDP of the entire world is approximately $85 trillion. So this cost to attack is approximately 15 billion x World GDP.

Tradeoffs Again

We were determined to get SIV to this level of security.

But raising the security level does have certain tradeoffs. For Finite Field Discrete Logs, achieving 128 bits of security requires a 3072 bit prime number.

We can calculate those prime numbers fast enough. They take about a minute to find, but can be pre-computed.

Whenever we use them — the 5 cryptographic operations listed at the top of this post — we have to send a lot of data back and forth, slowing down network requests and increasing bandwidth costs. But we can make that work too.

The problem came in actually doing all the modPow operations fast enough.

By increasing the size of our prime p, we increase the difficulty to reverse the modPow operation, but it also increases the time it takes to do them in the forward direction too.

This wasn't too much of an issue for the Multi-Party Keygen, Encryption, Re-Encryption during Shuffling, or Partial Decryptions and their Proofs.

But the Shuffle Proofs...

Whenever one of the parties does a Cryptographic Shuffle, they need to generate an accompanying Zero-Knowledge Proof of a Valid Shuffle, a mathematical guarantee that none of the underlying encrypted values were modified or removed.

Generating and Verifying these ZK Proofs involves doing a lot of modPows, nearly 200 or so, for every single vote being shuffled. This adds up fast for an election with just 1000 people, even if they're voting on only a single item.

In our initial profiling, we determined generating these shuffle proofs for 1000 votes, with a 3072 bit prime, took about two and half hours. Verifying a proof took over three hours.

This was slow, but still workable. These proofs aren't necessary right at the end of an election, which usually have at least a week for certification. But adding more items to vote on, more voters, or more shufflers (each with their own Shuffle Proofs) increases the time linearly.

Time to Optimize

We were determined to get these numbers down, way down. SIV's Verifiability is extremely powerful, but we want it all to be quick and easy to use, too.

One constraint we had given ourselves early on was to have all of SIV, including this Proof Generation and Verification logic, work in the browser, with no installs necessary.

There were a number of paths for optimization, which all could build on each other:

1. Using what are called "Short Exponents" in the modPow operations — keeping p 3072 bits, but using only a 256 bit secret value x
2. Rewriting this code in a faster programming language, via WebAssembly
3. Parallelizing the logic using the CPU, via WebWorkers
4. Parallelizing the logic using the GPU, via WebGL
5. Lowering the security level — 112 bits is still approved, just not recommended

We spent weeks exploring each of these, building working systems and timing them. Ultimately we were able to get the proof generation and verification down to just a few minutes each. A huge speedup.

Enter Elliptic Curves

But we still thought we could do better. There was always another potential optimization that we thought seemed very promising: replacing our One-Way Function itself.

Rather than basing all of the operations on modPow and its accompanying "Discrete Logarithm Hardness", we could use an operation called "Elliptic Curve Point Multiplication".

Above is part of what this operation looks like without a modulo, and below is once we add in "modulo a finite field".

The underlying math is rather esoteric, but it's gained widespread adoption in many of the world's most secure technology products, like Signal Messenger, Tor, and blockchains.

For SIV, we had to:

1. Choose an appropriate safe curve.
   • We chose Curve25519, using the Ristretto255 prime-order subgroup, which has 128 bits of security.
2. Get it all working safely in a browser.
3. Upgrade all of our cryptographic protocols for this new foundation.

Results

We're happy to share that we've now completed all 3 steps.

We've now run elections with over 1000 votes: generating the Shuffle Proofs takes only 11 seconds. Verification is about 15 seconds. That's a 824x speedup from where we started.

All of this is now fully integrated into SIV. All new elections use it by default. From an election administrator's point of view, it all "just works", fast and easy.

This upgrade was months in the making and included many thousands of lines of code changed. Well worth it.