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.
SIV makes it easy to run fast, private, and completely verifiable elections.
Under the hood, SIV relies upon a number of cryptographic operations:
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
p. This is often called
modPow for short, and we can call the result
But reversing the operation is very hard. Even if
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"
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".
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:
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.
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.
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.
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.
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.
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:
modPowoperations — keeping
p3072 bits, but using only a 256 bit secret value
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.
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:
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.