USENIX 2018 Crypto papers
1) "A Single-Decryption EM-Based Attack on OpenSSL’s Constant-Time Blinded RSA" https://www.usenix.org/sites/default/files/conference/protected-files/security18_slides_prvulovic.pdf
The constant-time implementation is shown to be vulnerable to Simple Power Analysis and thus secret exponent derivation just from a few bits. Constant time is not a bulletproof side-channel protection!
2) "DIZK A Distributed Zero Knowledge Proof System" https://www.usenix.org/sites/default/files/conference/protected-files/security18_slides_wu_0.pdf
How to distribute the computation (not MPC!) of a zkSNARK proof. Libsnark can process millions of gates, whereas this system can do billions! Very promising for some ICO :)
3) "Arbitrum: Scalable, private smart contracts" https://www.usenix.org/system/files/conference/usenixsecurity18/sec18-kalodner.pdf
It is not zkSNARKs on Ethereum. Instead, the authors suggest maintaining the current state hash of your chain/contract in a Virtual Machine, which has well-defined rules of state transitioning. Unless some of pre-designated maintainers challenge the new hash value, the VM operates smoothly and the parties agree on the state. In the case of a challenge the VM can be halted or forced to distribute its balance. Somewhat resembles Lightning channels and many other concepts, but seems to be a more powerful and standalone. The authors developed their own assembly and a standard library for VMs. Worth watching
1) "A Single-Decryption EM-Based Attack on OpenSSL’s Constant-Time Blinded RSA" https://www.usenix.org/sites/default/files/conference/protected-files/security18_slides_prvulovic.pdf
The constant-time implementation is shown to be vulnerable to Simple Power Analysis and thus secret exponent derivation just from a few bits. Constant time is not a bulletproof side-channel protection!
2) "DIZK A Distributed Zero Knowledge Proof System" https://www.usenix.org/sites/default/files/conference/protected-files/security18_slides_wu_0.pdf
How to distribute the computation (not MPC!) of a zkSNARK proof. Libsnark can process millions of gates, whereas this system can do billions! Very promising for some ICO :)
3) "Arbitrum: Scalable, private smart contracts" https://www.usenix.org/system/files/conference/usenixsecurity18/sec18-kalodner.pdf
It is not zkSNARKs on Ethereum. Instead, the authors suggest maintaining the current state hash of your chain/contract in a Virtual Machine, which has well-defined rules of state transitioning. Unless some of pre-designated maintainers challenge the new hash value, the VM operates smoothly and the parties agree on the state. In the case of a challenge the VM can be halted or forced to distribute its balance. Somewhat resembles Lightning channels and many other concepts, but seems to be a more powerful and standalone. The authors developed their own assembly and a standard library for VMs. Worth watching
"Bulletproofs: Short Proofs for Confidential Transactions and More"
https://eprint.iacr.org/2017/1066.pdf and IEEE S&P 2018
For quite some time proving computation in zero knowledge needed pairings because when you compute z = x*y and commit to z, x, and y separately it is very difficult to prove that g^z = (g^x)^y without revealing y. With pairings you have e(g^x,g^y)= e(g,g)^(xy) and there are SNARKs that exploit this property. Now Bulletproofs shows that it is apparently possible to prove the same without resorting to pairings. In the meanwhile, a trusted setup is not needed either.
The paper has two main ideas, though the second one is more opaque. The first idea is to reduce a range proof or an arithmetic circuit proof to an inner product argument, concretely proving that for some P you know A,B, c such that P = (X^A)(Y^B)z^c, where A,B are integer vectors, X,Y are group vectors, and c = <A,B> (inner product). Section 3 contains a nice chain of derivations that show how to make such proofs using the proofs for shorter vectors, and finally get the result by recursion. However, the resulting argument is not zero-knowledge.
The more interesting part comes in the last parts of Sections 4 and 5 where for range proofs and circuit proofs the authors show how to get a zero-knowledge proof from the above. After the recursion boils down to single-element vectors, we consider degree-2 polynomials with coefficients from these vectors, and evaluate them on a verifier-given point. Again, since the vectors are short, we can replace the Verifier with Fiat-Shamir and still get the proofs of reasonable size.
After all that we are left with range and circuit proofs of logarithmic (in length) complexity for all parties in both time and memory. Only discrete-log assumptions are needed, and the setup only requires generators without discrete-log relations among them.
The technique is great but I am sure we will see improvements. For circuits it remains to see which hash function delivers the smallest and fast-to-verify proof. Since the circuits operate in a prime field just as SNARKs, such a hash function will probably suit both worlds.
https://eprint.iacr.org/2017/1066.pdf and IEEE S&P 2018
For quite some time proving computation in zero knowledge needed pairings because when you compute z = x*y and commit to z, x, and y separately it is very difficult to prove that g^z = (g^x)^y without revealing y. With pairings you have e(g^x,g^y)= e(g,g)^(xy) and there are SNARKs that exploit this property. Now Bulletproofs shows that it is apparently possible to prove the same without resorting to pairings. In the meanwhile, a trusted setup is not needed either.
The paper has two main ideas, though the second one is more opaque. The first idea is to reduce a range proof or an arithmetic circuit proof to an inner product argument, concretely proving that for some P you know A,B, c such that P = (X^A)(Y^B)z^c, where A,B are integer vectors, X,Y are group vectors, and c = <A,B> (inner product). Section 3 contains a nice chain of derivations that show how to make such proofs using the proofs for shorter vectors, and finally get the result by recursion. However, the resulting argument is not zero-knowledge.
The more interesting part comes in the last parts of Sections 4 and 5 where for range proofs and circuit proofs the authors show how to get a zero-knowledge proof from the above. After the recursion boils down to single-element vectors, we consider degree-2 polynomials with coefficients from these vectors, and evaluate them on a verifier-given point. Again, since the vectors are short, we can replace the Verifier with Fiat-Shamir and still get the proofs of reasonable size.
After all that we are left with range and circuit proofs of logarithmic (in length) complexity for all parties in both time and memory. Only discrete-log assumptions are needed, and the setup only requires generators without discrete-log relations among them.
The technique is great but I am sure we will see improvements. For circuits it remains to see which hash function delivers the smallest and fast-to-verify proof. Since the circuits operate in a prime field just as SNARKs, such a hash function will probably suit both worlds.
Algorand: Scaling Byzantine Agreements for Cryptocurrencies
https://people.csail.mit.edu/nickolai/papers/gilad-algorand-eprint.pdf
There were a few Algorand papers; the first one by two authors describes quite a different version of Algorand with (seemingly) stronger claims and simpler algorithm.
The most important novelty of Algorand is its consensus, as the rest looks similar to Bitcoin. The consensus is Proof-of-Stake, where the probability to create a new block is proportional to party's wealth. As usual, not every public key participates in the block selection; moreover, those who do can step aside in the middle. There are alternatives: Ouroboros, SnowWhite, and Casper (some will be reviewed as well).
The main problem the PoS algorithms face is how to select a leader who proposes blocks so that the result can not be influenced by an adversary who joins at the last moment. There exist distributed key generation protocols and their derivatives, where m parties participate and exchange messages. If m/2+1 out of m parties are honest, all of them can reconstruct a collectively generated key. However, there are still some technical difficulties to overcome, which the Algorand designers claim to solve as follows.
First, Algorand selects a committee using a so-called Verifiable Random Function (VRF), such that each user can check and prove in zero-knowledge if he is in the committee and what his priority is, but he can not check that for other users (that's crucial). This is called sortition, but its straightforward implementation is still vulnerable to adversarial guessing. Algorand has to refresh the seed for VRF and use it only after a certain delay. Note that the sortition provides only a weak guarantee that the selected committee has enough honest nodes. For example, when honest users possess 80% of wealth, as many as 2000 members of committee are needed to ensure the majority for the next step, and this happens with probability 2^(-30) - which is not so low for me.
At the next step the committee decides on a block in the BFT-like fashion. In the normal situation the most prioritized committee member suggests a block, and everyone agrees, but when the leader is not available or there are conflicting ones, or even worse the network malfunctions, then the procedure gets much more involved. For example there is an option when an empty block is suggested. There are again some heuristically chosen parameters to prevent that from happening, but we do not know the behavior under a real attack. Once finalized, the block can not be reverted but it is a common BFT property.
The authors' benchmarking shows that Algorand can handle up to 50K users (the number of different IPs is much smaller though) with latency of under a minute and block size of a few MBytes. This is bigger than in the wild Ethereum but is comparable to the permissioned (Proof-of-Authority) Ethereum.
To summarize, the algorithm has some novelties and interesting performance, but it remains to see how it behaves under active attacks.
https://people.csail.mit.edu/nickolai/papers/gilad-algorand-eprint.pdf
There were a few Algorand papers; the first one by two authors describes quite a different version of Algorand with (seemingly) stronger claims and simpler algorithm.
The most important novelty of Algorand is its consensus, as the rest looks similar to Bitcoin. The consensus is Proof-of-Stake, where the probability to create a new block is proportional to party's wealth. As usual, not every public key participates in the block selection; moreover, those who do can step aside in the middle. There are alternatives: Ouroboros, SnowWhite, and Casper (some will be reviewed as well).
The main problem the PoS algorithms face is how to select a leader who proposes blocks so that the result can not be influenced by an adversary who joins at the last moment. There exist distributed key generation protocols and their derivatives, where m parties participate and exchange messages. If m/2+1 out of m parties are honest, all of them can reconstruct a collectively generated key. However, there are still some technical difficulties to overcome, which the Algorand designers claim to solve as follows.
First, Algorand selects a committee using a so-called Verifiable Random Function (VRF), such that each user can check and prove in zero-knowledge if he is in the committee and what his priority is, but he can not check that for other users (that's crucial). This is called sortition, but its straightforward implementation is still vulnerable to adversarial guessing. Algorand has to refresh the seed for VRF and use it only after a certain delay. Note that the sortition provides only a weak guarantee that the selected committee has enough honest nodes. For example, when honest users possess 80% of wealth, as many as 2000 members of committee are needed to ensure the majority for the next step, and this happens with probability 2^(-30) - which is not so low for me.
At the next step the committee decides on a block in the BFT-like fashion. In the normal situation the most prioritized committee member suggests a block, and everyone agrees, but when the leader is not available or there are conflicting ones, or even worse the network malfunctions, then the procedure gets much more involved. For example there is an option when an empty block is suggested. There are again some heuristically chosen parameters to prevent that from happening, but we do not know the behavior under a real attack. Once finalized, the block can not be reverted but it is a common BFT property.
The authors' benchmarking shows that Algorand can handle up to 50K users (the number of different IPs is much smaller though) with latency of under a minute and block size of a few MBytes. This is bigger than in the wild Ethereum but is comparable to the permissioned (Proof-of-Authority) Ethereum.
To summarize, the algorithm has some novelties and interesting performance, but it remains to see how it behaves under active attacks.
ASIACRYPT 2018 Accepted Papers Part 3:
13) "Hidden Shift Quantum Cryptanalysis and Implications" https://eprint.iacr.org/2018/432.pdf
When the quantum encryption oracle is available, the authors show how to break several symmetric schemes that use the modular addition (previous attacks exploited XORs). The complexity is practical, so never encrypt on a quantum computer.
14) "Secure Computation with Low Communication from Cross-checking" https://eprint.iacr.org/2018/216.pdf
Very efficient multiparty-computation protocols for generic circuits and a few (4 or 6) players: up to 1 bit per circuit gate. However, needs bigger preprocessing data.
15) "Programming the Demirci-Selcuk Meet-in-the-Middle Attack with Constraints" https://eprint.iacr.org/2018/813.pdf
The DS-MITM attack is a very powerful cryptanalysis method for AES-like ciphers, but the parameters (constraints) are non-trivial to find. This papers makes it automatic for some ciphers.
16) "Parameter-Hiding Order Revealing Encryption" https://eprint.iacr.org/2018/698.pdf
When you encrypt a database of integers and wants that the relative order of elements can be deduced from ciphertexts - it is ORE. However, for non-random data and practical-performance implementations of ORE - much more information can be obtained. This paper defines a parameter that can be guaranteely concealed even for such ORE
17) "Computing supersingular isogenies on Kummer surfaces" https://eprint.iacr.org/2018/850.pdf
Supersingular isogenies are candidates for quantum-secure public crypto with small keys and slow processing. This paper tries to make them faster
18) "Robustly Reusable Fuzzy Extractor from Standard Assumptions" https://eprint.iacr.org/2018/818.pdf
To compute a key from fingerprint, one can choose a codeword of a linear code as the key and difference to this codeword as a witness. Then applying a witness to a noisy reading of the same finger would bring to the vicinity of the same codeword. It is an example of a fuzzy extractor. Original designs could not derive many unrelated keys from the same source, and this paper provides a mechanism for that.
13) "Hidden Shift Quantum Cryptanalysis and Implications" https://eprint.iacr.org/2018/432.pdf
When the quantum encryption oracle is available, the authors show how to break several symmetric schemes that use the modular addition (previous attacks exploited XORs). The complexity is practical, so never encrypt on a quantum computer.
14) "Secure Computation with Low Communication from Cross-checking" https://eprint.iacr.org/2018/216.pdf
Very efficient multiparty-computation protocols for generic circuits and a few (4 or 6) players: up to 1 bit per circuit gate. However, needs bigger preprocessing data.
15) "Programming the Demirci-Selcuk Meet-in-the-Middle Attack with Constraints" https://eprint.iacr.org/2018/813.pdf
The DS-MITM attack is a very powerful cryptanalysis method for AES-like ciphers, but the parameters (constraints) are non-trivial to find. This papers makes it automatic for some ciphers.
16) "Parameter-Hiding Order Revealing Encryption" https://eprint.iacr.org/2018/698.pdf
When you encrypt a database of integers and wants that the relative order of elements can be deduced from ciphertexts - it is ORE. However, for non-random data and practical-performance implementations of ORE - much more information can be obtained. This paper defines a parameter that can be guaranteely concealed even for such ORE
17) "Computing supersingular isogenies on Kummer surfaces" https://eprint.iacr.org/2018/850.pdf
Supersingular isogenies are candidates for quantum-secure public crypto with small keys and slow processing. This paper tries to make them faster
18) "Robustly Reusable Fuzzy Extractor from Standard Assumptions" https://eprint.iacr.org/2018/818.pdf
To compute a key from fingerprint, one can choose a codeword of a linear code as the key and difference to this codeword as a witness. Then applying a witness to a noisy reading of the same finger would bring to the vicinity of the same codeword. It is an example of a fuzzy extractor. Original designs could not derive many unrelated keys from the same source, and this paper provides a mechanism for that.
ZK-STARKs
"Scalable, transparent, and post-quantum secure computational integrity" https://eprint.iacr.org/2018/046.pdf
STARKs are one of the most interesting concepts of year 2018. I do not say "interesting papers" because the paper is unfortunately not so interesting but is quite involving. It remains to see when an easier formal description appears in a follow-up paper, as currently "popular" explanations (such as Buterin's https://vitalik.ca/general/2017/11/09/starks_part_1.html ) are largely based on Ben-Sasson's video lectures
https://www.youtube.com/watch?v=9VuZvdxFZQo
https://www.youtube.com/watch?v=L7tZeO8ihcQ
which I too recommend for watching.
STARKs serve for zero-knowledge proof of program execution. Like SNARKs are based on the idea of representing a program code as a circuit with algebraic operations in nodes. A statement about a program execution can be written as a statement on polynomials. It is apparently easy to design a short interactive proof about statements like "this list is a set of values of a low degree function F" with a small assumption that the prover selects another low-degree polynomial G as part of the proof. The proof requires the prover to compute F on a much larger set and can be used in zero-knowledge if only queries to these extra values are allowed.
The difficulty lies in making the prover to use a low-degree G. In SNARKs this is done by using quadratic polynomials with trapdoors so that the statement XY=Z can be asserted using pairings over user-provided X and pre-committed Y as g^Y. In STARKs the prover instead creates a proof of low-degree, which is a major contribution by itself. During the proof the prover commits to the values of F and G via Merkle trees and provides selective openings. The authors' widely-advertised FRI algorithm of proximity proof works in these conditions. The proof size depends logarithmically on the circuit size, and thus the verifier's work, but for hash function circuits this all is within 1 MB size and 1 second time.
It is interesting to note that due to nature of proximity proof algorithm, the computation is done in not so large binary fields (e.g. 2^32), which contrasts to big prime fields of SNARKs. Consecutively, for zero-knowledge proofs of hash computations, the best hash functions are those native to these fields (or subfields). The AES-based hash function from the paper is insecure, but others with bigger S-boxes are worth looking at.
"Scalable, transparent, and post-quantum secure computational integrity" https://eprint.iacr.org/2018/046.pdf
STARKs are one of the most interesting concepts of year 2018. I do not say "interesting papers" because the paper is unfortunately not so interesting but is quite involving. It remains to see when an easier formal description appears in a follow-up paper, as currently "popular" explanations (such as Buterin's https://vitalik.ca/general/2017/11/09/starks_part_1.html ) are largely based on Ben-Sasson's video lectures
https://www.youtube.com/watch?v=9VuZvdxFZQo
https://www.youtube.com/watch?v=L7tZeO8ihcQ
which I too recommend for watching.
STARKs serve for zero-knowledge proof of program execution. Like SNARKs are based on the idea of representing a program code as a circuit with algebraic operations in nodes. A statement about a program execution can be written as a statement on polynomials. It is apparently easy to design a short interactive proof about statements like "this list is a set of values of a low degree function F" with a small assumption that the prover selects another low-degree polynomial G as part of the proof. The proof requires the prover to compute F on a much larger set and can be used in zero-knowledge if only queries to these extra values are allowed.
The difficulty lies in making the prover to use a low-degree G. In SNARKs this is done by using quadratic polynomials with trapdoors so that the statement XY=Z can be asserted using pairings over user-provided X and pre-committed Y as g^Y. In STARKs the prover instead creates a proof of low-degree, which is a major contribution by itself. During the proof the prover commits to the values of F and G via Merkle trees and provides selective openings. The authors' widely-advertised FRI algorithm of proximity proof works in these conditions. The proof size depends logarithmically on the circuit size, and thus the verifier's work, but for hash function circuits this all is within 1 MB size and 1 second time.
It is interesting to note that due to nature of proximity proof algorithm, the computation is done in not so large binary fields (e.g. 2^32), which contrasts to big prime fields of SNARKs. Consecutively, for zero-knowledge proofs of hash computations, the best hash functions are those native to these fields (or subfields). The AES-based hash function from the paper is insecure, but others with bigger S-boxes are worth looking at.
ASIACRYPT 2018 Accepted Papers Part 4
19) "Adaptively Simulation-Secure Attribute-Hiding Predicate Encryption"
not available yet
20) "A Framework for Achieving KDM-CCA Secure Public-Key Encryption" https://eprint.iacr.org/2018/845.pdf
How to secure a cryptosystem if an adversary can ask for encryption of secret keys.
21) "On the Statistical Leak of the GGH13 Multilinear Map and some Variants" https://eprint.iacr.org/2017/482.pdf
The multilinear maps were a long standig problem seemingly solved in 2013. Since then, a number of attacks have been proposed making the original proposal insecure. It is still in use as there are few alternatives. Many attacks result from statistical attacks on lattices, as lattices are crucial part of the MM design. This paper tries to quantify the statistical leak in many settings.
22) "Understanding and Constructing AKE via Double-key Key Encapsulation Mechanism" https://eprint.iacr.org/2018/817.pdf
AKE (authenticated key exchange) is a group of secure channel protocols where for each session a new (ephemeral) key pair is generated using the long-term key (which is common in secure messengers such as Signal, for example). This paper provides a formal treatment of this approach.
23) "Block Cipher Invariants as Eigenvectors of Correlation Matrices" https://eprint.iacr.org/2018/763.pdf
When round constants or their combination with round keys have low entropy, a state invariant can undergo quite many rounds. The paper shows how to express such invariants via correlation matrices. This does not lead to any significant new attack on well known ciphers, but is a good reminder to choose random constants when possible.
24) "Quantum Lattice Enumeration and Tweaking Discrete Pruning" https://eprint.iacr.org/2018/546.pdf
Lattice-based cryptography seemingly resist quantum computers which makes it promising for post-quantum NIST competition. However, quantum lattice attacks get better even though they remain exponential. This paper establishes new security parameters for some post-quantum candidates based on new attacks.
19) "Adaptively Simulation-Secure Attribute-Hiding Predicate Encryption"
not available yet
20) "A Framework for Achieving KDM-CCA Secure Public-Key Encryption" https://eprint.iacr.org/2018/845.pdf
How to secure a cryptosystem if an adversary can ask for encryption of secret keys.
21) "On the Statistical Leak of the GGH13 Multilinear Map and some Variants" https://eprint.iacr.org/2017/482.pdf
The multilinear maps were a long standig problem seemingly solved in 2013. Since then, a number of attacks have been proposed making the original proposal insecure. It is still in use as there are few alternatives. Many attacks result from statistical attacks on lattices, as lattices are crucial part of the MM design. This paper tries to quantify the statistical leak in many settings.
22) "Understanding and Constructing AKE via Double-key Key Encapsulation Mechanism" https://eprint.iacr.org/2018/817.pdf
AKE (authenticated key exchange) is a group of secure channel protocols where for each session a new (ephemeral) key pair is generated using the long-term key (which is common in secure messengers such as Signal, for example). This paper provides a formal treatment of this approach.
23) "Block Cipher Invariants as Eigenvectors of Correlation Matrices" https://eprint.iacr.org/2018/763.pdf
When round constants or their combination with round keys have low entropy, a state invariant can undergo quite many rounds. The paper shows how to express such invariants via correlation matrices. This does not lead to any significant new attack on well known ciphers, but is a good reminder to choose random constants when possible.
24) "Quantum Lattice Enumeration and Tweaking Discrete Pruning" https://eprint.iacr.org/2018/546.pdf
Lattice-based cryptography seemingly resist quantum computers which makes it promising for post-quantum NIST competition. However, quantum lattice attacks get better even though they remain exponential. This paper establishes new security parameters for some post-quantum candidates based on new attacks.
Real Crypto via @like
ACM CCS 2018, Part 1.
This major security conference takes place in 2 weeks, so it is good time to review real-crypto-related papers presented there in case you can not attend. There are a few interesting sections, and today we'll look at "Crypto attacks".
1) "Practical state recovery attacks against legacy RNG implementations" https://duhkattack.com/paper.pdf
The ANSI X9.17 key generation algorithm used a block cipher in a way that state or key compromise allow both earlier and future outputs. Interestingly, the secret key for the cipher can often be retrieved from binaries or source code of popular applications.
2) "Prime and Prejudice: Primality Testing Under Adversarial Conditions" https://eprint.iacr.org/2018/749.pdf
Many applications and protocols need prime numbers, and if an adversary manages to slip composite numbers in, the security level drops. Apparently many libraries use Miller-Rabin test as a check, which can be fooled rather easily. The paper shows how easily, where it can be exploited, and which test should be used instead. By the way, I know another usecase: in Zerocoin an issued coin is a commitment to some secret values, which must be prime to be included in an RSA accumulator. If such a coin is not a prime, a forgery inclusion proof can be produced.
3) "Release the Kraken: New KRACKs in the 802.11 Standard" https://papers.mathyvanhoef.com/ccs2018.pdf
How to affect a new key installation in the WiFi protocol.
4) "Pump up the Volume: Practical Database Reconstruction from Volume Leakage on Range Queries"
Not yet available, but the title is self-explaining.
This major security conference takes place in 2 weeks, so it is good time to review real-crypto-related papers presented there in case you can not attend. There are a few interesting sections, and today we'll look at "Crypto attacks".
1) "Practical state recovery attacks against legacy RNG implementations" https://duhkattack.com/paper.pdf
The ANSI X9.17 key generation algorithm used a block cipher in a way that state or key compromise allow both earlier and future outputs. Interestingly, the secret key for the cipher can often be retrieved from binaries or source code of popular applications.
2) "Prime and Prejudice: Primality Testing Under Adversarial Conditions" https://eprint.iacr.org/2018/749.pdf
Many applications and protocols need prime numbers, and if an adversary manages to slip composite numbers in, the security level drops. Apparently many libraries use Miller-Rabin test as a check, which can be fooled rather easily. The paper shows how easily, where it can be exploited, and which test should be used instead. By the way, I know another usecase: in Zerocoin an issued coin is a commitment to some secret values, which must be prime to be included in an RSA accumulator. If such a coin is not a prime, a forgery inclusion proof can be produced.
3) "Release the Kraken: New KRACKs in the 802.11 Standard" https://papers.mathyvanhoef.com/ccs2018.pdf
How to affect a new key installation in the WiFi protocol.
4) "Pump up the Volume: Practical Database Reconstruction from Volume Leakage on Range Queries"
Not yet available, but the title is self-explaining.
ZKSNARK sidechain for Ethereum https://ethresear.ch/t/roll-up-roll-back-snark-side-chain-17000-tps/3675
A group of authors has suggested a sidechain, which is simultaneously anchored to the Ethereum blockchain (resides at some contract address) and whose updates are proved in zero knowledge to be correct Ethereum Virtual Machine executions. Their current suggestion is to use SHA-256 (later Pedersen commitment) as a hash function for the state Merkle tree. A designated operator converts all sidechain transactions to SNARKs. The calculation is 2K constraints for signatures + 30K constraints for the Merkle opening proof. Using DIZK (Usenix'18, see above) for distributed proof generation, they aim for 17K sidechain transactions per single snark proof, but the transactions are currency transfer only (no contracts!).
I also note that for 17K transactions in a single snark you would not need a full Merkle opening for all of them, as these can be compressed. Also Pedersen hash is not 1K constraints but more. For contract calls each transaction would take significantly more time to generate a SNARK. Still, would be nice to see. And of course, replace Pedersen with a suitable version of MIMC.
A group of authors has suggested a sidechain, which is simultaneously anchored to the Ethereum blockchain (resides at some contract address) and whose updates are proved in zero knowledge to be correct Ethereum Virtual Machine executions. Their current suggestion is to use SHA-256 (later Pedersen commitment) as a hash function for the state Merkle tree. A designated operator converts all sidechain transactions to SNARKs. The calculation is 2K constraints for signatures + 30K constraints for the Merkle opening proof. Using DIZK (Usenix'18, see above) for distributed proof generation, they aim for 17K sidechain transactions per single snark proof, but the transactions are currency transfer only (no contracts!).
I also note that for 17K transactions in a single snark you would not need a full Merkle opening for all of them, as these can be compressed. Also Pedersen hash is not 1K constraints but more. For contract calls each transaction would take significantly more time to generate a SNARK. Still, would be nice to see. And of course, replace Pedersen with a suitable version of MIMC.
Ethereum Research
Roll_up / roll_back snark side chain ~17000 tps
Authors BarryWhitehat, Alex Gluchowski, HarryR, Yondon Fu, Philippe Castonguay Overview A snark based side chain is introduced. It requires constant gas per state transition independent of the number of transactions included in each transition. This limits…
Real Crypto via @like
ACM CCS 18 Crypto Part 2
5) "Improved Non-Interactive Zero Knowledge with Applications to Post-Quantum Signatures" https://eprint.iacr.org/2018/475.pdf
ZK proofs of knowledge and thus signatures can be derived from multiparty computation protocols by proving the view correctness of some subset of parties. The benefit of this approach is that only symmetric primitives are needed such as ciphers and hash functions, and the disadvantage is signatures being linear in circuit size. This paper presents some performance improvements in this direction. Note again, like for SNARK and STARKs, that dedicated (low-AND-gate) ciphers may lead to drastic performance improvements.
6) "Symbolic Proofs for Lattice-Based Cryptography" https://eprint.iacr.org/2018/765.pdf
How to prove the security of lattice-based protocols symbolically.
7) "Lattice-Based zk-SNARKs from Square Span Programs" https://eprint.iacr.org/2018/275.pdf
Authors show how to create SNARKs using lattices (in contrast to quantum-vulnerable elliptic curve SNARKs), but the performance is quite slow (and measurements are not fully provided).
8) "Lattice-Based Group Signatures and Zero-Knowledge Proofs of Automorphism Stability" https://eprint.iacr.org/2018/779.pdf
Another lattice-based cryptosystem. Public, private keys and signatures are all hundreds of KBytes. Seems fine in the post-quantum world:)
5) "Improved Non-Interactive Zero Knowledge with Applications to Post-Quantum Signatures" https://eprint.iacr.org/2018/475.pdf
ZK proofs of knowledge and thus signatures can be derived from multiparty computation protocols by proving the view correctness of some subset of parties. The benefit of this approach is that only symmetric primitives are needed such as ciphers and hash functions, and the disadvantage is signatures being linear in circuit size. This paper presents some performance improvements in this direction. Note again, like for SNARK and STARKs, that dedicated (low-AND-gate) ciphers may lead to drastic performance improvements.
6) "Symbolic Proofs for Lattice-Based Cryptography" https://eprint.iacr.org/2018/765.pdf
How to prove the security of lattice-based protocols symbolically.
7) "Lattice-Based zk-SNARKs from Square Span Programs" https://eprint.iacr.org/2018/275.pdf
Authors show how to create SNARKs using lattices (in contrast to quantum-vulnerable elliptic curve SNARKs), but the performance is quite slow (and measurements are not fully provided).
8) "Lattice-Based Group Signatures and Zero-Knowledge Proofs of Automorphism Stability" https://eprint.iacr.org/2018/779.pdf
Another lattice-based cryptosystem. Public, private keys and signatures are all hundreds of KBytes. Seems fine in the post-quantum world:)
Real Crypto via @like
ASIACRYPT 2018 Part 5
25) "Tighter Security Proofs for GPV-IBE in the Quantum Random Oracle Model" https://eprint.iacr.org/2018/451.pdf
As Learning With Errors (LWE) primitives seem to withstand quantum computers, it is natural to see if the security proofs that involve LWE also are quantum-proof (for example that a hash function can be computed on a quantum machine). This paper creates a proof for one identity-based encryption scheme based on LWE.
26) "Attribute-Based Signatures for Unbounded Languages from Standard Assumptions" https://eprint.iacr.org/2018/842.pdf
How to create fine grained authentication for policies expressed in powerful languages.
27) "Free IF: How to Omit Inactive Branches and Implement S-Universal Garbled Circuit (Almost) for Free" https://eprint.iacr.org/2018/789.pdf
Optimizing secure function evaluation based on garbled circuits.
28) "Constructing Ideal Secret Sharing Schemes based on Chinese Remainder Theorem?" https://eprint.iacr.org/2018/837.pdf
Even though Shamir's secret sharing has perfect rate, it can not handle arbitrary weights. This paper is the first example of weight-capable secret sharing scheme based on CRT.
29 ) "Improved Inner-product Encryption with Adaptive Security and Full Attribute-hiding" https://eprint.iacr.org/2018/833.pdf
Improving attribute-based encryption. In ABE each plaintext has some boolean attributes, and multiple secret keys exist for decryption. Each secret key can decrypt only a subset of ciphertexts, concretely those whose attributes turn a boolean function F (specific to this key) - to 1.
30) "Simple and More Efficient PRFs with Tight Security from LWE and Matrix-DDH" https://eprint.iacr.org/2018/826.pdf
Pseudo-random functions from LWE: not so fast, not so small, but interesting in the view of post-quantum use of LWE.
25) "Tighter Security Proofs for GPV-IBE in the Quantum Random Oracle Model" https://eprint.iacr.org/2018/451.pdf
As Learning With Errors (LWE) primitives seem to withstand quantum computers, it is natural to see if the security proofs that involve LWE also are quantum-proof (for example that a hash function can be computed on a quantum machine). This paper creates a proof for one identity-based encryption scheme based on LWE.
26) "Attribute-Based Signatures for Unbounded Languages from Standard Assumptions" https://eprint.iacr.org/2018/842.pdf
How to create fine grained authentication for policies expressed in powerful languages.
27) "Free IF: How to Omit Inactive Branches and Implement S-Universal Garbled Circuit (Almost) for Free" https://eprint.iacr.org/2018/789.pdf
Optimizing secure function evaluation based on garbled circuits.
28) "Constructing Ideal Secret Sharing Schemes based on Chinese Remainder Theorem?" https://eprint.iacr.org/2018/837.pdf
Even though Shamir's secret sharing has perfect rate, it can not handle arbitrary weights. This paper is the first example of weight-capable secret sharing scheme based on CRT.
29 ) "Improved Inner-product Encryption with Adaptive Security and Full Attribute-hiding" https://eprint.iacr.org/2018/833.pdf
Improving attribute-based encryption. In ABE each plaintext has some boolean attributes, and multiple secret keys exist for decryption. Each secret key can decrypt only a subset of ciphertexts, concretely those whose attributes turn a boolean function F (specific to this key) - to 1.
30) "Simple and More Efficient PRFs with Tight Security from LWE and Matrix-DDH" https://eprint.iacr.org/2018/826.pdf
Pseudo-random functions from LWE: not so fast, not so small, but interesting in the view of post-quantum use of LWE.
Real Crypto via @like
Mirror curves
Bulletproofs is a great technique but by default it works with circuits over a prime field. Therefore if the algorithm to prove about works points on elliptic curves over some F_p and order N, it might be nontrivial and/or expensive to express point arithmetic over some another field F_p'. Wonderfully, since a group of curve points as multiples of a base point is isomorphic to prime field F_N (when N is prime), one can extend the bulletproof proofs to curve point statements by replacing integers with scalars.
So if you have two curves (called
https://twitter.com/pwuille/status/993572063389605889
https://github.com/BlockchainCommons/secp256k1/issues/1
https://mathoverflow.net/questions/249982/elliptic-curve-related-equivalence-between-fields-of-different-characteristic
Bulletproofs is a great technique but by default it works with circuits over a prime field. Therefore if the algorithm to prove about works points on elliptic curves over some F_p and order N, it might be nontrivial and/or expensive to express point arithmetic over some another field F_p'. Wonderfully, since a group of curve points as multiples of a base point is isomorphic to prime field F_N (when N is prime), one can extend the bulletproof proofs to curve point statements by replacing integers with scalars.
So if you have two curves (called
mirror): A with prime order N and field F_P, and B with order P and field F_N' (maybe N'=N but not necessary). Then you can assert about, for example, signatures on curve A with Bulletproofs using curve B natively. Interestingly, for the Bitcoin curve Secp256k1 there exists a curve with P and N merely swapped (for this to be legitimate the numbers should be within min(2sqr_root(N,P)) due to the Hasse theorem). Existence of such mirror curve for other curves and the security implications of using both curves simultaneously is the subject of future research. https://twitter.com/pwuille/status/993572063389605889
https://github.com/BlockchainCommons/secp256k1/issues/1
https://mathoverflow.net/questions/249982/elliptic-curve-related-equivalence-between-fields-of-different-characteristic
Twitter
Pieter Wuille
@benediktbuenz @ChristopherA The curve we're calling secq has equation y^2 = x^3 + 7 over integers mod n (secp256k1's curve order). This curve happens to have p (secp256k1's field size) as order. So it is a perfect swap of curve/field size, and even has the…
Real Crypto via @like
How Zcash works
In (simplified) Bitcoin, a transaction consists of a list of unspent outputs (=sender public key + hash of transaction he spends), a list of receiver addresses (=public keys), total amount, and which receiver gets how much. All this is public. In Zcash, all this is hidden: you can think that there are only hashes of all values + proof of correctness. Transactions are ordered by the consensus, and are appended to the addition-only tree T as a leaf, where the root of the tree is assigned with the value of the hash of all leaves.
The proof of correctness evidently includes:
- the proof that for every sender public key the sender knows both his private key, amount and all receiver keys.
- the proof that the amounts for all receivers add up to the total amount.
- the proof that every unspent output is part of the tree T (or some its earlier version).
Since all the values to prove about are hashed, we need a protocol that proves the correctness of computation without revealing inputs and some outputs. In this case only the root value of T and the transaction itself are revealed. The protocol is ZK-SNARK: the proof is short and fast to verify, but its generation is linear (or more) in the computation length. Since the last proof is about a chain of hash function invocations in the tree, it is the most expensive (took 40 seconds before the Sapling upgrade).
One thing we have missed: an unspent output can not be spent twice. To prevent that, we add to every receiver address a spending secret, and open it for every unspent output. The ledger then checks uniqueness. The proof then includes:
- the proof that the each revealed spending secret corresponds to one unspent output.
To prevent front-running, the spending secret is a function of the receiver address, and it is also proved. That's it.
In (simplified) Bitcoin, a transaction consists of a list of unspent outputs (=sender public key + hash of transaction he spends), a list of receiver addresses (=public keys), total amount, and which receiver gets how much. All this is public. In Zcash, all this is hidden: you can think that there are only hashes of all values + proof of correctness. Transactions are ordered by the consensus, and are appended to the addition-only tree T as a leaf, where the root of the tree is assigned with the value of the hash of all leaves.
The proof of correctness evidently includes:
- the proof that for every sender public key the sender knows both his private key, amount and all receiver keys.
- the proof that the amounts for all receivers add up to the total amount.
- the proof that every unspent output is part of the tree T (or some its earlier version).
Since all the values to prove about are hashed, we need a protocol that proves the correctness of computation without revealing inputs and some outputs. In this case only the root value of T and the transaction itself are revealed. The protocol is ZK-SNARK: the proof is short and fast to verify, but its generation is linear (or more) in the computation length. Since the last proof is about a chain of hash function invocations in the tree, it is the most expensive (took 40 seconds before the Sapling upgrade).
One thing we have missed: an unspent output can not be spent twice. To prevent that, we add to every receiver address a spending secret, and open it for every unspent output. The ledger then checks uniqueness. The proof then includes:
- the proof that the each revealed spending secret corresponds to one unspent output.
To prevent front-running, the spending secret is a function of the receiver address, and it is also proved. That's it.
Real Crypto via @like
ASIACRYPT 2018 Part 6
31) "Optimal Linear Multiparty Conditional Disclosure of Secrets Protocols" https://eprint.iacr.org/2018/441.pdf
Many MPC and attribute-based encryption schemes require a Conditional Disclosure of Secrets (CDS) protocol, where a party learns a secret known to the group only if the messages from the group satisfy some predicate. This paper explores messages that are linear functions of the secret value.
32) "Measuring, simulating and exploiting the head concavity phenomenon in BKZ" https://eprint.iacr.org/2018/856.pdf
Investigating the lattice cryptanalysis method BKZ with few results.
33) "LWE Without Modular Reduction and Improved Side-Channel Attacks Against BLISS" https://eprint.iacr.org/2018/822.pdf
BLISS is a lattice-based signature algorithm, which was attacked recently with side-channels. The authors demonstrate that the private key can be recovered using a special, easy instance of the LWE problem. However, they need 20000 traces.
34) "Short Digital Signatures and ID-KEMs via Truncation Collision Resistance" https://eprint.iacr.org/2017/061.pdf
Using collision resistance assumption for truncated hash functions to prove the security of various primitives in the standard model rather than with random oracles.
35) "Simple and Efficient Two-Server ORAM" https://eprint.iacr.org/2018/005.pdf
ORAM is the oblivious RAM protocol, when client stores memory at the server, but hides the access pattern. While most (if not all) methods require the server to compute over the entire data at least once, they compete in communication complexity. This paper shows how to work with two servers and logarithmic communication, improving the previous work by a large constant factor.
36 "Statistical Ineffective Fault Attacks on Masked AES with Fault Countermeasures" https://eprint.iacr.org/2018/357.pdf
Fault attacks are mitigated by redundant computations and other methods; the attackers respond with ineffective fault attacks where faults are analyzed regarding whether they caused an error despite redundancy. This paper shows new features of such attacks (if you can run them).
31) "Optimal Linear Multiparty Conditional Disclosure of Secrets Protocols" https://eprint.iacr.org/2018/441.pdf
Many MPC and attribute-based encryption schemes require a Conditional Disclosure of Secrets (CDS) protocol, where a party learns a secret known to the group only if the messages from the group satisfy some predicate. This paper explores messages that are linear functions of the secret value.
32) "Measuring, simulating and exploiting the head concavity phenomenon in BKZ" https://eprint.iacr.org/2018/856.pdf
Investigating the lattice cryptanalysis method BKZ with few results.
33) "LWE Without Modular Reduction and Improved Side-Channel Attacks Against BLISS" https://eprint.iacr.org/2018/822.pdf
BLISS is a lattice-based signature algorithm, which was attacked recently with side-channels. The authors demonstrate that the private key can be recovered using a special, easy instance of the LWE problem. However, they need 20000 traces.
34) "Short Digital Signatures and ID-KEMs via Truncation Collision Resistance" https://eprint.iacr.org/2017/061.pdf
Using collision resistance assumption for truncated hash functions to prove the security of various primitives in the standard model rather than with random oracles.
35) "Simple and Efficient Two-Server ORAM" https://eprint.iacr.org/2018/005.pdf
ORAM is the oblivious RAM protocol, when client stores memory at the server, but hides the access pattern. While most (if not all) methods require the server to compute over the entire data at least once, they compete in communication complexity. This paper shows how to work with two servers and logarithmic communication, improving the previous work by a large constant factor.
36 "Statistical Ineffective Fault Attacks on Masked AES with Fault Countermeasures" https://eprint.iacr.org/2018/357.pdf
Fault attacks are mitigated by redundant computations and other methods; the attackers respond with ineffective fault attacks where faults are analyzed regarding whether they caused an error despite redundancy. This paper shows new features of such attacks (if you can run them).
Real Crypto via @like
Verifiable Delay Functions
Boneh et al. have recently introduced this concept https://eprint.iacr.org/2018/601.pdf . Shortly, these are functions that guaranteely require certain amount of time to be computed even if parallelism is available, and the output can be easily verified for correctness. For example, a Bitcoin proof of work is not a VDF because it can be (and is) computed quickly by a number of parallel processors. This concept has many practical applications for decentralized protocols such as randomness beacon: participants bring their seeds within time T then apply VDF G to the collection. The result can not be manipulated by any party if G can not be computed faster than T.
Interestingly, one can not obtain such functions if parallelism is unlimited: if both input and output are short, the solution search is an NP problem and we do not know any computation that requires exponential (of input) time, even if we drop the fast verification requirement. Also the solution can be brute forced by an exponential number of processors.
The authors suggest several VDF candidates for bounded parallelism. First, one can obtain a VDF by applying a ZKSNARK proof generation algorithm to a sequence of hash function calls. In the straightforward setting the function is too slow, but it can be sped up using incremental proofs of computation. Secondly, a polynomial GCD of degree t is a candidate if less than t^2 processors are available. There are also some other underexplored candidates, but no definitively good one.
One may wonder if some memory-hard functions such as our Equihash or MTP are good VDF. Unfortunately, the MTP computation is inherently parallel even though we tried to make it as memory-hard as possible by using a large instance of Argon2, thus making it difficult for ASIC implementation. Equihash is more promising as long as the parallelism is bounded: the bottleneck of Equihash is sorting, and there are well known logarithmic parallel sorting algorithms, though they are all very difficult for practical implementation on any architecture. When a more practical mesh architecture is considered, we are aware of a parallel algorithm that sorts N inputs in sqrt(N) time with N^2 processors. The delay is present but it is sublinear. It remains to see if other candidates appear.
Boneh et al. have recently introduced this concept https://eprint.iacr.org/2018/601.pdf . Shortly, these are functions that guaranteely require certain amount of time to be computed even if parallelism is available, and the output can be easily verified for correctness. For example, a Bitcoin proof of work is not a VDF because it can be (and is) computed quickly by a number of parallel processors. This concept has many practical applications for decentralized protocols such as randomness beacon: participants bring their seeds within time T then apply VDF G to the collection. The result can not be manipulated by any party if G can not be computed faster than T.
Interestingly, one can not obtain such functions if parallelism is unlimited: if both input and output are short, the solution search is an NP problem and we do not know any computation that requires exponential (of input) time, even if we drop the fast verification requirement. Also the solution can be brute forced by an exponential number of processors.
The authors suggest several VDF candidates for bounded parallelism. First, one can obtain a VDF by applying a ZKSNARK proof generation algorithm to a sequence of hash function calls. In the straightforward setting the function is too slow, but it can be sped up using incremental proofs of computation. Secondly, a polynomial GCD of degree t is a candidate if less than t^2 processors are available. There are also some other underexplored candidates, but no definitively good one.
One may wonder if some memory-hard functions such as our Equihash or MTP are good VDF. Unfortunately, the MTP computation is inherently parallel even though we tried to make it as memory-hard as possible by using a large instance of Argon2, thus making it difficult for ASIC implementation. Equihash is more promising as long as the parallelism is bounded: the bottleneck of Equihash is sorting, and there are well known logarithmic parallel sorting algorithms, though they are all very difficult for practical implementation on any architecture. When a more practical mesh architecture is considered, we are aware of a parallel algorithm that sorts N inputs in sqrt(N) time with N^2 processors. The delay is present but it is sublinear. It remains to see if other candidates appear.
Real Crypto via @like
ASIACRYPT 2018 Part 7
37) "Quantum Algorithms for the k-xor Problem" Not avalaible yet. Is it about the generalized birthday problem?
38) "Concretely Efficient Large-Scale MPC with Active Security" https://eprint.iacr.org/2018/843.pdf
Shows that if certain number (more than one) of MPC participants is honest, the performance of known algorithms can be improved by a small factor.
39) "Short Variable Length Domain Extenders With Beyond Birthday Bound Security" https://eprint.iacr.org/2018/783.pdf
Based on N-bit blockcipher, create a mode that encrypts up to 2N bits with security beyond 2^(N/2).
40) "Decentralized Multi-Client Functional Encryption for Inner Product" https://eprint.iacr.org/2017/989.pdf
Again functional encryption (see paper 29) with similar results. Recall that FE is helpful to compute certain functions on the encrypted data, in this case the function is inner product and is helpful to compute, for example, weighted average of some encrypted tuples.
41) "Homomorphic Secret Sharing for Low Degree Polynomials" Not available yet.
42) "CSIDH: An Efficient Post-Quantum Commutative Group Action" https://eprint.iacr.org/2018/383.pdf
A new key agreement cryptosystem based on the problem of finding an explicit isogeny between two elliptic curves. Supposedly quantum-resistant, this method makes use of supersingular curves.
43) "Multi-Key Homomorphic Signatures Unforgeable under Insider Corruption" https://eprint.iacr.org/2016/834.pdf
Homomorphic Signatures are those where one can compute a signature over a function of already signed arguments. This paper suggests a design that withstands corrupted signers (who each sign its own input).
44) "On the Concrete Security of Goldreich’s Pseudorandom Generator" Not available yet.
45) "Cryptanalysis of MORUS" https://eprint.iacr.org/2018/464.pdf
Linear cryptanalysis of an authenticated encryption scheme Morus based on the rotational invariance of some components. Requires 2^152 data.
37) "Quantum Algorithms for the k-xor Problem" Not avalaible yet. Is it about the generalized birthday problem?
38) "Concretely Efficient Large-Scale MPC with Active Security" https://eprint.iacr.org/2018/843.pdf
Shows that if certain number (more than one) of MPC participants is honest, the performance of known algorithms can be improved by a small factor.
39) "Short Variable Length Domain Extenders With Beyond Birthday Bound Security" https://eprint.iacr.org/2018/783.pdf
Based on N-bit blockcipher, create a mode that encrypts up to 2N bits with security beyond 2^(N/2).
40) "Decentralized Multi-Client Functional Encryption for Inner Product" https://eprint.iacr.org/2017/989.pdf
Again functional encryption (see paper 29) with similar results. Recall that FE is helpful to compute certain functions on the encrypted data, in this case the function is inner product and is helpful to compute, for example, weighted average of some encrypted tuples.
41) "Homomorphic Secret Sharing for Low Degree Polynomials" Not available yet.
42) "CSIDH: An Efficient Post-Quantum Commutative Group Action" https://eprint.iacr.org/2018/383.pdf
A new key agreement cryptosystem based on the problem of finding an explicit isogeny between two elliptic curves. Supposedly quantum-resistant, this method makes use of supersingular curves.
43) "Multi-Key Homomorphic Signatures Unforgeable under Insider Corruption" https://eprint.iacr.org/2016/834.pdf
Homomorphic Signatures are those where one can compute a signature over a function of already signed arguments. This paper suggests a design that withstands corrupted signers (who each sign its own input).
44) "On the Concrete Security of Goldreich’s Pseudorandom Generator" Not available yet.
45) "Cryptanalysis of MORUS" https://eprint.iacr.org/2018/464.pdf
Linear cryptanalysis of an authenticated encryption scheme Morus based on the rotational invariance of some components. Requires 2^152 data.
Our Memory-hard Proof of Work Equihash gains popularity. In the recent GPU miner publication I have found out that quite many cryptocurrencies are using it with different parameters: https://cryptomining-blog.com/10300-new-lolminer-0-5-amd-and-nvidia-opencl-multi-equihash-gpu-miner/
Note that Equihash-144/5 requires 2.2 GB, and Equihash-192/7 - 3GB. This is not a record: the Grin project has recently discussed using Equihash-108/3 with 7 GB memory requirements. https://www.grin-forum.org/t/proof-of-work-update/713
I believe this is due low spread of 8GB+ GPU. It will be also quite difficult to build an ASIC with 7 GB RAM, as it will be quite big. And by the time of the delivery one can switch for higher parameters.
The performance of these parameters should be reasonable. LolMiner claims 90 sol/sec for 144/5 on 1080ti, https://forum.bitcoingold.org/t/lolminer-0-6-alpha-preview-is-available-1080ti-89sol-s-1080-54-sol-s-vega-64-44sol-s/2447
so 108/3 should be at least 10 sol/s (2^27 entries in the 108/3 list vs 2^24 in the 144/5 list with more iterations in the latter)
Note that Equihash-144/5 requires 2.2 GB, and Equihash-192/7 - 3GB. This is not a record: the Grin project has recently discussed using Equihash-108/3 with 7 GB memory requirements. https://www.grin-forum.org/t/proof-of-work-update/713
I believe this is due low spread of 8GB+ GPU. It will be also quite difficult to build an ASIC with 7 GB RAM, as it will be quite big. And by the time of the delivery one can switch for higher parameters.
The performance of these parameters should be reasonable. LolMiner claims 90 sol/sec for 144/5 on 1080ti, https://forum.bitcoingold.org/t/lolminer-0-6-alpha-preview-is-available-1080ti-89sol-s-1080-54-sol-s-vega-64-44sol-s/2447
so 108/3 should be at least 10 sol/s (2^27 entries in the 108/3 list vs 2^24 in the 144/5 list with more iterations in the latter)
Grin
Proof of work update
Over the past 6 months, it has become apparent to the team that: The availability of an ASIC for Cuckoo Cycle at launch is a distinct possibility. The current ASIC market is centralized, especially when it comes to recent cryptocurrency releases. The development…
ASIACRYPT 2018 Part 8
46) "State Separation for Code-Based Game-Playing Proofs" https://eprint.iacr.org/2018/306.pdf (early version)
A new framework for scheme security analysis.
47) "Two attacks on rank metric code-based schemes: RankSign and an Identity-Based-Encryption scheme" https://eprint.iacr.org/2018/339.pdf
Code-Based schemes are post-quantum candidates as decoding in certain metrics is NP-hard. However, the existing primitives have big keys and signatures. The paper shows that one of recent proposals can be broken because the codewords produced with recommended parameters have low weight.
48) "An efficient structural attack on NIST submission DAGS" https://eprint.iacr.org/2018/456.pdf
Another code-based scheme is broken, now the encryption one. The scheme instantiates McEliece cryptosystem with Srivastava codes, and, as typical for structured codes (cf. attacks on McEliece with Reed-Muller or Reed-Solomon), is broken for suggested parameters.
49) "Attacks and Countermeasures for White-box Designs" https://eprint.iacr.org/2018/049.pdf
White-box schemes obfuscate the secret key so that the entire encryption algorithm with the key can be published and neither the key nor a compact representation of the scheme can be found. This paper shows that the common masking technique (to protect from side channel analysis) does not increase the security level since the obfuscation by masking is weak.
50) "Improved (Almost) Tightly-Secure Simulation-Sound QA-NIZK with Applications" https://eprint.iacr.org/2018/849.pdf
A zero-knowledge argument system that delivers a public-key encryption in the strongest security model and is verifiable.
51) "Identity-based Encryption Tightly Secure under Chosen-ciphertext Attacks" https://eprint.iacr.org/2018/834.pdf
An IBE scheme in a weak security model (only one challenge ciphertext allowed for CCA) but whose security is very tightly reduced to the underlying assumption.
46) "State Separation for Code-Based Game-Playing Proofs" https://eprint.iacr.org/2018/306.pdf (early version)
A new framework for scheme security analysis.
47) "Two attacks on rank metric code-based schemes: RankSign and an Identity-Based-Encryption scheme" https://eprint.iacr.org/2018/339.pdf
Code-Based schemes are post-quantum candidates as decoding in certain metrics is NP-hard. However, the existing primitives have big keys and signatures. The paper shows that one of recent proposals can be broken because the codewords produced with recommended parameters have low weight.
48) "An efficient structural attack on NIST submission DAGS" https://eprint.iacr.org/2018/456.pdf
Another code-based scheme is broken, now the encryption one. The scheme instantiates McEliece cryptosystem with Srivastava codes, and, as typical for structured codes (cf. attacks on McEliece with Reed-Muller or Reed-Solomon), is broken for suggested parameters.
49) "Attacks and Countermeasures for White-box Designs" https://eprint.iacr.org/2018/049.pdf
White-box schemes obfuscate the secret key so that the entire encryption algorithm with the key can be published and neither the key nor a compact representation of the scheme can be found. This paper shows that the common masking technique (to protect from side channel analysis) does not increase the security level since the obfuscation by masking is weak.
50) "Improved (Almost) Tightly-Secure Simulation-Sound QA-NIZK with Applications" https://eprint.iacr.org/2018/849.pdf
A zero-knowledge argument system that delivers a public-key encryption in the strongest security model and is verifiable.
51) "Identity-based Encryption Tightly Secure under Chosen-ciphertext Attacks" https://eprint.iacr.org/2018/834.pdf
An IBE scheme in a weak security model (only one challenge ciphertext allowed for CCA) but whose security is very tightly reduced to the underlying assumption.
Real Crypto via @like
Threshold signatures allow you to split the private key into N parts and give them to N parties so that T-of-N guys can always create a signature. In some case a verifier can not even distinguish who the signers are. Threshold signatures have been proposed as variations of many popular schemes (for example, the BLS threshold signatures by Boldyreva), but
for quite some time they did not exist for ECDSA. As ECDSA is widely used in Bitcoin, Ethereum and many other blockchains, such a scheme would allow for more compact multisignature wallets, potentially indistinguishable from regular accounts.
I was quite surprised when learned that no threshold signature protocol exists for ECDSA with more than 2 parties. The problem was that the parties have to collectively exponentiate both to the secret and its inverse. Still, the two papers on exactly this subject have appeared at the ACM CCS 2018 a year ago, which I missed in the review. One is "Fast Multiparty Threshold ECDSA with Fast Trustless Setup" http://stevengoldfeder.com/papers/GG18.pdf and another "Fast Secure Multiparty ECDSA with Practical Distributed Key Generation and Applications to Cryptocurrency Custody" https://eprint.iacr.org/2018/987.pdf
The protocols are notably similar, even the trick of splitting a quadratic monomial in the exponent into a sum of monomials. However, the further implementations are different, so that the former paper performs better by a factor of magnitude or so. Both can finish within a few seconds with dozens of parties, but the problem is with the protocol. Currently it is 4-5 rounds of "interact_with_each_party-compute-broadcast" which will of course be nightmare for human multisig signers, but viable for machines. Startup idea for cold storage?
for quite some time they did not exist for ECDSA. As ECDSA is widely used in Bitcoin, Ethereum and many other blockchains, such a scheme would allow for more compact multisignature wallets, potentially indistinguishable from regular accounts.
I was quite surprised when learned that no threshold signature protocol exists for ECDSA with more than 2 parties. The problem was that the parties have to collectively exponentiate both to the secret and its inverse. Still, the two papers on exactly this subject have appeared at the ACM CCS 2018 a year ago, which I missed in the review. One is "Fast Multiparty Threshold ECDSA with Fast Trustless Setup" http://stevengoldfeder.com/papers/GG18.pdf and another "Fast Secure Multiparty ECDSA with Practical Distributed Key Generation and Applications to Cryptocurrency Custody" https://eprint.iacr.org/2018/987.pdf
The protocols are notably similar, even the trick of splitting a quadratic monomial in the exponent into a sum of monomials. However, the further implementations are different, so that the former paper performs better by a factor of magnitude or so. Both can finish within a few seconds with dozens of parties, but the problem is with the protocol. Currently it is 4-5 rounds of "interact_with_each_party-compute-broadcast" which will of course be nightmare for human multisig signers, but viable for machines. Startup idea for cold storage?
At the latest DevCon4 conference, Eli Ben-Sasson presented several notable improvements to ZK-STARKs.
The improvements were quite practical, as the proof generation time and size decreased. For certain amount of computation, it is cheaper to verify a STARK proof than the computation itself. Currently the threshold is about 100 (Pedersen) hashes. Therefore, even when the zero knowledge is not required (like scalability issues), STARKs can play a significant role. As I understand, removing zero knowledge does not bring much gain, but this can change.
The proof size for payment blockchains has decreased almost tenfold, from 500KB to 50KB. Bulletproofs proof (just the range proof) can do it in 1.5KB. The proof generation for Pedersen Merkle trees takes about 1 second and increases logarithmically with the number of layers.
It is important to note that the verifier runs part of the original computation, so the decrease in the computation (not necessarily the proof) will also reduce the verification time.
A new STARK-friendly hash function, Friday, has been presented, with quite small proof generation time but only 64-bit collision resistance. Our own hash function design (will talk about it later) seems to be more perspective.
Still, Zcash architects are hesitant to replace SNARKs with STARKs. This makes sense: for a big number of proofs the STARK size overhead is significant. It might be possible to prune the proofs by replacing them with metaproofs, but then the receipients must obtain more information from senders.
The improvements were quite practical, as the proof generation time and size decreased. For certain amount of computation, it is cheaper to verify a STARK proof than the computation itself. Currently the threshold is about 100 (Pedersen) hashes. Therefore, even when the zero knowledge is not required (like scalability issues), STARKs can play a significant role. As I understand, removing zero knowledge does not bring much gain, but this can change.
The proof size for payment blockchains has decreased almost tenfold, from 500KB to 50KB. Bulletproofs proof (just the range proof) can do it in 1.5KB. The proof generation for Pedersen Merkle trees takes about 1 second and increases logarithmically with the number of layers.
It is important to note that the verifier runs part of the original computation, so the decrease in the computation (not necessarily the proof) will also reduce the verification time.
A new STARK-friendly hash function, Friday, has been presented, with quite small proof generation time but only 64-bit collision resistance. Our own hash function design (will talk about it later) seems to be more perspective.
Still, Zcash architects are hesitant to replace SNARKs with STARKs. This makes sense: for a big number of proofs the STARK size overhead is significant. It might be possible to prune the proofs by replacing them with metaproofs, but then the receipients must obtain more information from senders.
Real Crypto via @like
ASIACRYPT 2018 Part 9
52) "Simulatable Channels: Extended Security that is Universally Composable and Easier to Prove" https://eprint.iacr.org/2018/844.pdf
Cryptographic constructions often come with formal proofs, and there are several techniques to compose such proofs. One of them is simulation where the behaviour of a secret-possesing party is simulated by a machine without a secret. This paper shows how some secret-channel protocols can be proven secure in this paradigm.\
53) "On the Hardness of the Computational Ring-LWR Problem and its Applications" https://eprint.iacr.org/2018/536.pdf
Learning With Rounding (LWR) is an area potentially suitable for post-quantum cryptography as related problems have not been sped up with a quantum computer yet. The paper introduces some new security assumptions based on the hardness of LWR and puts certain post-quantum schemes into their context.
54) "Towards practical key exchange from ordinary isogeny graphs" https://eprint.iacr.org/2018/485.pdf
Isogeny-based protocols is another family of (potential) quantum-secure schemes, but so far all constructions were impractical. This paper makes significant performance improvements, but the parameter generation remains a complicated and open problem.
55) "SQL on Structurally-Encrypted Databases" https://eprint.iacr.org/2016/453.pdf
A rather old paper on how to encrypt a database so that some (but not all) relational algebra queries can be performed. The authors' approach leaks less data at the cost of supporting fewer queries compared to other approaches such as property-preserving encryption (PPE)
56) "Non-Interactive Secure Computation from One-Way Functions" https://eprint.iacr.org/2018/1020.pdf
Non-Interactive Secure Computation (NISC) is a family of MPC protocols where minimal interaction between parties is assumed. For example, to compute a function f(X,Y) the owner of X publishes some precomputation g(X), then the owner of Y interacts with it producing h(Y,g(X)), which allows the former to compute F(X,Y). This paper suggests a generic way to do that that uses only one-way functions and does not need oblivious transfer protocols.
57) "Arya: Nearly Linear-Time Zero-Knowledge Proofs for Correct Program Execution" https://eprint.iacr.org/2018/380.pdf
A new proof system where prover's overhead is minimal (linear of the program size, compared to superlinear in other systems) -- at the cost of quite high verification and communication costs, which attribute to the square root of program size.
52) "Simulatable Channels: Extended Security that is Universally Composable and Easier to Prove" https://eprint.iacr.org/2018/844.pdf
Cryptographic constructions often come with formal proofs, and there are several techniques to compose such proofs. One of them is simulation where the behaviour of a secret-possesing party is simulated by a machine without a secret. This paper shows how some secret-channel protocols can be proven secure in this paradigm.\
53) "On the Hardness of the Computational Ring-LWR Problem and its Applications" https://eprint.iacr.org/2018/536.pdf
Learning With Rounding (LWR) is an area potentially suitable for post-quantum cryptography as related problems have not been sped up with a quantum computer yet. The paper introduces some new security assumptions based on the hardness of LWR and puts certain post-quantum schemes into their context.
54) "Towards practical key exchange from ordinary isogeny graphs" https://eprint.iacr.org/2018/485.pdf
Isogeny-based protocols is another family of (potential) quantum-secure schemes, but so far all constructions were impractical. This paper makes significant performance improvements, but the parameter generation remains a complicated and open problem.
55) "SQL on Structurally-Encrypted Databases" https://eprint.iacr.org/2016/453.pdf
A rather old paper on how to encrypt a database so that some (but not all) relational algebra queries can be performed. The authors' approach leaks less data at the cost of supporting fewer queries compared to other approaches such as property-preserving encryption (PPE)
56) "Non-Interactive Secure Computation from One-Way Functions" https://eprint.iacr.org/2018/1020.pdf
Non-Interactive Secure Computation (NISC) is a family of MPC protocols where minimal interaction between parties is assumed. For example, to compute a function f(X,Y) the owner of X publishes some precomputation g(X), then the owner of Y interacts with it producing h(Y,g(X)), which allows the former to compute F(X,Y). This paper suggests a generic way to do that that uses only one-way functions and does not need oblivious transfer protocols.
57) "Arya: Nearly Linear-Time Zero-Knowledge Proofs for Correct Program Execution" https://eprint.iacr.org/2018/380.pdf
A new proof system where prover's overhead is minimal (linear of the program size, compared to superlinear in other systems) -- at the cost of quite high verification and communication costs, which attribute to the square root of program size.
Real Crypto via @like
ASIACRYPT 2018 Part 10
58) "Building Quantum-One-Way Functions from Block Ciphers: Davies-Meyer and Merkle-Damgard Constructions" https://eprint.iacr.org/2018/841.pdf
Recently several block ciphers were found broken if the adversary can query them on a quantum encryptor (i.e. get a quantum superposition of ciphertexts). As many hash functions are built from block ciphers, it is an open question if collision or preimage resistance suffers in this setting. The authors show that the well-known Merkle-Damgard scheme provides a quantum-secure one-way hash function in the ideal cipher model if the compression function is built from this ideal cipher via Davies-Meyer. Nice positive result in the post quantum security.
59) "A Universally Composable Framework for the Privacy of Email Ecosystems" https://eprint.iacr.org/2018/848.pdf
This paper suggests a formal approach for security evaluation of email systems w.r.t. anonymity. The authors show that some mixing network does provide necessary security guarantees if users are similarly active.
60) "Security of the Blockchain against Long Delay Attack" https://eprint.iacr.org/2018/800.pdf
Previous research showed that Proof of Work is a secure consensus method assuming certain percentage of honest mining power and limit on the message delay an adversary can cause. This paper shows that PoW is still secure if message delay is arbitrarily high but only a fraction of messages can be delayed.
61) "ZCZ – Achieving n-bit SPRP Security with a Minimal Number of Tweakable-block-cipher Calls" https://eprint.iacr.org/2018/819.pdf
Certain recent authenticated encryption modes use a tweakable block cipher (TBC), where public constants (tweaks) are mixed into the secret key. It has been unknown how many TBC calls per message block is necessary for security. The paper presents a new construction with ratio 1.5 while also claiming an attack on any design with ratio 1.5-eps.
62) "New MILP Modeling: Improved Conditional Cube Attacks on Keccak-based Constructions" https://eprint.iacr.org/2017/1030.pdf
Cube attack is a key recovery technique for bit-oriented symmetric primitives of low degree such as Keccak-based MACs, where a hypercube of plaintexts is encrypted. The authors present new results by attacking up to 9 rounds of KMAC256 (2^147 time) and some reduced versions of AE designs Keyak and Ketje. Improvements come from better use of integer linear programming to find such cubes.
63) "Tight Private Circuits: Achieving Probing Security with the Least Refreshing" https://eprint.iacr.org/2018/439.pdf
Masking is a technique to add and remove noise during the computation with a secret, which defeats some side-channel attacks. The paper presents a tool that analyzes and optimizes the mask layout assuming certain number of probing positions.
64) "More is Less: Perfectly Secure Oblivious Algorithms in the Multi-Server Setting?" https://eprint.iacr.org/2018/851.pdf
A counterpart to paper 35, which deals with 2-server oblivious RAM. Here 3 servers are considered, and the improvement over 1 server is logarithmic: log^2 N bandwidth blowup compared to log^3 N for single server, when N elements are stored. Note though that similar improvements have already been achieved with weaker security requirements.
65) "Leakage-Resilient Cryptography from Puncturable Primitives and Obfuscation" https://eprint.iacr.org/2018/781.pdf
Adds new notions and a framework to construct leakage-resilient schemes: those that remain secure despite leaked functions on intermediate variables. Many reductionist results.
58) "Building Quantum-One-Way Functions from Block Ciphers: Davies-Meyer and Merkle-Damgard Constructions" https://eprint.iacr.org/2018/841.pdf
Recently several block ciphers were found broken if the adversary can query them on a quantum encryptor (i.e. get a quantum superposition of ciphertexts). As many hash functions are built from block ciphers, it is an open question if collision or preimage resistance suffers in this setting. The authors show that the well-known Merkle-Damgard scheme provides a quantum-secure one-way hash function in the ideal cipher model if the compression function is built from this ideal cipher via Davies-Meyer. Nice positive result in the post quantum security.
59) "A Universally Composable Framework for the Privacy of Email Ecosystems" https://eprint.iacr.org/2018/848.pdf
This paper suggests a formal approach for security evaluation of email systems w.r.t. anonymity. The authors show that some mixing network does provide necessary security guarantees if users are similarly active.
60) "Security of the Blockchain against Long Delay Attack" https://eprint.iacr.org/2018/800.pdf
Previous research showed that Proof of Work is a secure consensus method assuming certain percentage of honest mining power and limit on the message delay an adversary can cause. This paper shows that PoW is still secure if message delay is arbitrarily high but only a fraction of messages can be delayed.
61) "ZCZ – Achieving n-bit SPRP Security with a Minimal Number of Tweakable-block-cipher Calls" https://eprint.iacr.org/2018/819.pdf
Certain recent authenticated encryption modes use a tweakable block cipher (TBC), where public constants (tweaks) are mixed into the secret key. It has been unknown how many TBC calls per message block is necessary for security. The paper presents a new construction with ratio 1.5 while also claiming an attack on any design with ratio 1.5-eps.
62) "New MILP Modeling: Improved Conditional Cube Attacks on Keccak-based Constructions" https://eprint.iacr.org/2017/1030.pdf
Cube attack is a key recovery technique for bit-oriented symmetric primitives of low degree such as Keccak-based MACs, where a hypercube of plaintexts is encrypted. The authors present new results by attacking up to 9 rounds of KMAC256 (2^147 time) and some reduced versions of AE designs Keyak and Ketje. Improvements come from better use of integer linear programming to find such cubes.
63) "Tight Private Circuits: Achieving Probing Security with the Least Refreshing" https://eprint.iacr.org/2018/439.pdf
Masking is a technique to add and remove noise during the computation with a secret, which defeats some side-channel attacks. The paper presents a tool that analyzes and optimizes the mask layout assuming certain number of probing positions.
64) "More is Less: Perfectly Secure Oblivious Algorithms in the Multi-Server Setting?" https://eprint.iacr.org/2018/851.pdf
A counterpart to paper 35, which deals with 2-server oblivious RAM. Here 3 servers are considered, and the improvement over 1 server is logarithmic: log^2 N bandwidth blowup compared to log^3 N for single server, when N elements are stored. Note though that similar improvements have already been achieved with weaker security requirements.
65) "Leakage-Resilient Cryptography from Puncturable Primitives and Obfuscation" https://eprint.iacr.org/2018/781.pdf
Adds new notions and a framework to construct leakage-resilient schemes: those that remain secure despite leaked functions on intermediate variables. Many reductionist results.