Real Crypto via @like
ZcoinGate
Quite recently the Zcoin project has published a series of blogposts [1,2] that their protocol has been broken and some coins (though not much) have been minted out of thin air. Let us figure out the details.
Zcoin descends from the Zerocoin protocol, one of the first installments of the anonymous cryptocurrency and a predecessor to Zerocash (on which Zcash is based). In Zerocoin/Zcoin the UTXO model is used (like in Bitcoin) and all coins have the same denomination (thus the coin value is implicit and not hidden). The output transaction is just a commitment C to some serial number S, which is added to the RSA accumulator immediately afterwards. The input transaction consists of just S and the proof that the accumulator contains a commitment to S (without referring which one).
The proof of knowledge of a commitment in an accumulator apparently requires two more commitments to C, denoted C1 and C2, which must be computed in different groups. This requirement stems from the properties of the accumulator. Whereas proving that C1 contains an accumulated value and that we know the double discrete logarithm of C2 is straightforward and has been described before in Jan Camenisch's papers, the trouble comes from proving that both C1 and C2 are commitments to the same value.
The latter proof is fairly non-trivial in distinct prime order groups. The common mistake (exactly the one done in Zcoin) is to adapt a standard proof of knowledge of discrete log for different generators in the same group. The problem is that the latter proof is not sound for the case of different groups: using the Chinese Remainder Theorem it is easy to find a message that would pass the protocol but result in different values in different groups. As a result, an adversary could spend one coin multiple times using the serial numbers that do not really fit.
Solutions to this problem are known but are not easy. One way is to use a third group, now of unknown order, and create a commitment C3 to the same value C there. In the unknown order group the CRT would not work [3]. Another way is to commit to all bits in C separately and prove the equality of discrete logarithm bit by bit [4], but it is quite expensive. Let us see how it goes.
[1] https://zcoin.io/further-disclosure-on-zerocoin-vulnerability/
[2] https://zcoin.io/cryptographic-description-of-zerocoin-attack/
[3] https://s3.amazonaws.com/academia.edu.documents/40153125/Direct_Anonymous_Attestation20151118-6708-12qn3kw.pdf?AWSAccessKeyId=AKIAIWOWYYGZ2Y53UL3A&Expires=1556812848&Signature=eTbkwwj9iYmAWQ1YN1wfJdY4id4%3D&response-content-disposition=inline%3B%20filename%3DDirect_anonymous_attestation.pdf , Section 3.2
[4] https://eprint.iacr.org/2018/557.pdf Appendix D
Quite recently the Zcoin project has published a series of blogposts [1,2] that their protocol has been broken and some coins (though not much) have been minted out of thin air. Let us figure out the details.
Zcoin descends from the Zerocoin protocol, one of the first installments of the anonymous cryptocurrency and a predecessor to Zerocash (on which Zcash is based). In Zerocoin/Zcoin the UTXO model is used (like in Bitcoin) and all coins have the same denomination (thus the coin value is implicit and not hidden). The output transaction is just a commitment C to some serial number S, which is added to the RSA accumulator immediately afterwards. The input transaction consists of just S and the proof that the accumulator contains a commitment to S (without referring which one).
The proof of knowledge of a commitment in an accumulator apparently requires two more commitments to C, denoted C1 and C2, which must be computed in different groups. This requirement stems from the properties of the accumulator. Whereas proving that C1 contains an accumulated value and that we know the double discrete logarithm of C2 is straightforward and has been described before in Jan Camenisch's papers, the trouble comes from proving that both C1 and C2 are commitments to the same value.
The latter proof is fairly non-trivial in distinct prime order groups. The common mistake (exactly the one done in Zcoin) is to adapt a standard proof of knowledge of discrete log for different generators in the same group. The problem is that the latter proof is not sound for the case of different groups: using the Chinese Remainder Theorem it is easy to find a message that would pass the protocol but result in different values in different groups. As a result, an adversary could spend one coin multiple times using the serial numbers that do not really fit.
Solutions to this problem are known but are not easy. One way is to use a third group, now of unknown order, and create a commitment C3 to the same value C there. In the unknown order group the CRT would not work [3]. Another way is to commit to all bits in C separately and prove the equality of discrete logarithm bit by bit [4], but it is quite expensive. Let us see how it goes.
[1] https://zcoin.io/further-disclosure-on-zerocoin-vulnerability/
[2] https://zcoin.io/cryptographic-description-of-zerocoin-attack/
[3] https://s3.amazonaws.com/academia.edu.documents/40153125/Direct_Anonymous_Attestation20151118-6708-12qn3kw.pdf?AWSAccessKeyId=AKIAIWOWYYGZ2Y53UL3A&Expires=1556812848&Signature=eTbkwwj9iYmAWQ1YN1wfJdY4id4%3D&response-content-disposition=inline%3B%20filename%3DDirect_anonymous_attestation.pdf , Section 3.2
[4] https://eprint.iacr.org/2018/557.pdf Appendix D
Real Crypto via @like
Poseidon and Starkad hash functions
Quite often in zero-knowledge based protocols one has to prove knowledge of one element in a set: an unspent coin, a public key from a pool, etc. To do that effectively, you should organize a Merkle tree and prove that you know the opening of an element. The complexity of such a proof depends on how big a circuit to compute the hash function of the Merkle tree is. Regular cryptographic hash functions such as SHA-256 or SHA-3 need too big circuits as they are tailored to the x86 architecture rather than to finite fields used in ZK proof systems Bulletproofs, ZK-SNARKs or ZK-STARKs.
Here is a hash function design that aims to minimize such circuits and thus to minimize the prover and verifier complexities. If you ever saw the AES block cipher, it is something similar, just S-boxes are much bigger and many of them are absent. The functions utilize wide permutations, like Keccak, and are supposed to run in the sponge mode. The authors consider all possible sorts of cryptanalysis, particularly algebraic ones that have recently broken the Friday hash function.
The performance of regular hashing should be slower than that of Blake2/SHA-3, of course, but from the ZK perspective it is much better. The advantage over the closest competitors is the factor of 8 (compared to the Pedersen hash, SNARK/Bulletproofs systems) or 4 (compared to Friday, STARK systems). The implementations are not ready yet, but the one who want to break something, there are enough details.
https://eprint.iacr.org/2019/458.pdf
Quite often in zero-knowledge based protocols one has to prove knowledge of one element in a set: an unspent coin, a public key from a pool, etc. To do that effectively, you should organize a Merkle tree and prove that you know the opening of an element. The complexity of such a proof depends on how big a circuit to compute the hash function of the Merkle tree is. Regular cryptographic hash functions such as SHA-256 or SHA-3 need too big circuits as they are tailored to the x86 architecture rather than to finite fields used in ZK proof systems Bulletproofs, ZK-SNARKs or ZK-STARKs.
Here is a hash function design that aims to minimize such circuits and thus to minimize the prover and verifier complexities. If you ever saw the AES block cipher, it is something similar, just S-boxes are much bigger and many of them are absent. The functions utilize wide permutations, like Keccak, and are supposed to run in the sponge mode. The authors consider all possible sorts of cryptanalysis, particularly algebraic ones that have recently broken the Friday hash function.
The performance of regular hashing should be slower than that of Blake2/SHA-3, of course, but from the ZK perspective it is much better. The advantage over the closest competitors is the factor of 8 (compared to the Pedersen hash, SNARK/Bulletproofs systems) or 4 (compared to Friday, STARK systems). The implementations are not ready yet, but the one who want to break something, there are enough details.
https://eprint.iacr.org/2019/458.pdf
Real Crypto via @like
Chosen-prefix collisions for the full SHA-1
https://eprint.iacr.org/2019/459.pdf
SHA-1 is a hash function designed by NSA in 1995 and was based on the famous MD hash family designed by Ron Rivest. To process 512 message bits, it adds a linear function of message bits to the internal state every round, and there are 80 rounds. Quite quickly researchers realized that these linear functions are vulnerable to differential cryptanalysis, and SHA-1 was theoretically broken (a collision attack with complexity smaller than expected 2^80) in 2005, which triggered a competition for the future SHA-3.
Surprisingly, in those 10 years of life SHA-1 rooted so deeply in web infrastructure that the next 15 years were insufficient to root it out. It is still present in many web servers and accepted as a certificate hash function in many applications.
In 2017 two different PDF files with the same SHA-1 hash were constructed, at the cost of around $100K on GPU clusters, but even that did not end the SHA-1 days. The difference in the files was specially crafted to ease the collision search. The practical certificate forgeries were out of reach and some people thought SHA-1 could be in limited use.
Now, Leurent and Peyrin, two well known cryptanalysts, present a chosen-prefix collision attack. In this attack for any pair of messages (M1,M2) we can find suffixes (S1,S2) so that M1||S1 and M2||S2 produce the same SHA-1 hash. This allows certificate forgeries, Merkle tree forgeries and many other fancy attacks, so that almost any system that uses SHA-1 can be broken.
What is important is the reduction of the chosen-prefix attack to the regular collision attack with almost the same complexity, so that chosen-prefix collisions can be constructed with the same $100K (amortized cost on ASICs would be even smaller if you need thousands of such collisions). To explain how it works, we recall that a collision attack of this kind is done by selecting a proper difference Dm in the message, predicting how it propagates through the state, and playing with free message bits to increase the probability of success. If we use more than 512 bits of message, this process can be done over several blocks, and on each step we have slightly relaxed condition and higher probability.
Leurent and Peyrin show that one can start the collision search in the last blocks having the input difference from a very large set S. We then try many-many message blocks so that by birthday paradox there is at least one pair of blocks giving the difference from the set. With a set of 2^30 differences and the 160-bit state, we obtain the complexity of the first step of 2^65. Then the authors show how to come from a difference from set S to the zero difference, and it is a gradual process over a few steps, applying a kind of SHA-1 regular collision every time, each again costing 2^65 or so. Eventually we have an attack which is at the same order of magnitude as the regular collision, just some factor over it. The exact price is pure speculation, as one can amortize the costs significantly if many attacks are needed.
Very nice result overall, I think it can be further improved using memoryless near-collision search on the first step. And SHA-1 is dead.
https://eprint.iacr.org/2019/459.pdf
SHA-1 is a hash function designed by NSA in 1995 and was based on the famous MD hash family designed by Ron Rivest. To process 512 message bits, it adds a linear function of message bits to the internal state every round, and there are 80 rounds. Quite quickly researchers realized that these linear functions are vulnerable to differential cryptanalysis, and SHA-1 was theoretically broken (a collision attack with complexity smaller than expected 2^80) in 2005, which triggered a competition for the future SHA-3.
Surprisingly, in those 10 years of life SHA-1 rooted so deeply in web infrastructure that the next 15 years were insufficient to root it out. It is still present in many web servers and accepted as a certificate hash function in many applications.
In 2017 two different PDF files with the same SHA-1 hash were constructed, at the cost of around $100K on GPU clusters, but even that did not end the SHA-1 days. The difference in the files was specially crafted to ease the collision search. The practical certificate forgeries were out of reach and some people thought SHA-1 could be in limited use.
Now, Leurent and Peyrin, two well known cryptanalysts, present a chosen-prefix collision attack. In this attack for any pair of messages (M1,M2) we can find suffixes (S1,S2) so that M1||S1 and M2||S2 produce the same SHA-1 hash. This allows certificate forgeries, Merkle tree forgeries and many other fancy attacks, so that almost any system that uses SHA-1 can be broken.
What is important is the reduction of the chosen-prefix attack to the regular collision attack with almost the same complexity, so that chosen-prefix collisions can be constructed with the same $100K (amortized cost on ASICs would be even smaller if you need thousands of such collisions). To explain how it works, we recall that a collision attack of this kind is done by selecting a proper difference Dm in the message, predicting how it propagates through the state, and playing with free message bits to increase the probability of success. If we use more than 512 bits of message, this process can be done over several blocks, and on each step we have slightly relaxed condition and higher probability.
Leurent and Peyrin show that one can start the collision search in the last blocks having the input difference from a very large set S. We then try many-many message blocks so that by birthday paradox there is at least one pair of blocks giving the difference from the set. With a set of 2^30 differences and the 160-bit state, we obtain the complexity of the first step of 2^65. Then the authors show how to come from a difference from set S to the zero difference, and it is a gradual process over a few steps, applying a kind of SHA-1 regular collision every time, each again costing 2^65 or so. Eventually we have an attack which is at the same order of magnitude as the regular collision, just some factor over it. The exact price is pure speculation, as one can amortize the costs significantly if many attacks are needed.
Very nice result overall, I think it can be further improved using memoryless near-collision search on the first step. And SHA-1 is dead.
Real Crypto via @like
Lelantus
https://eprint.iacr.org/2019/373.pdf
This is a new privacy-oriented cryptocurrency protocol, developed by the Zcoin team. Lelantus claims to achieve both transaction privacy and coin amount secrecy, in the line of Monero, Zcash, Zcoin. The authors claim short proofs and fast verification time, also the ability to batch proofs to enable fast verification of multiple proofs.
The ledger is UTXO based. Each output is just a vector commitment to a secret key and the amount, and an input transaction is a commitment to an output one. When spending a set of input transactions, the spender proves for each of them that it has never been spent by providing a deterministic hash of the secret key, which is looked up in the set of spent coins, and proving knowledge of that key. The spender also provides a proof that the input transaction is a valid commitment to one of previously published outputs. Finally, the spender proves that the sum of inputs matches the sum of outputs and all values are positive and not so big.
Whereas the double-spend and the sum proof are standard (prety much like in Monero and Zcoin), the Bulletproofs range proof is proposed for the latter, the proof of input validity is novel and is the main contribution of the paper. The authors employ the 1-of-N proof technique of [1]. First, they select the set of outputs that contain the one we are spending. Both Spender and Verifier are supposed to divide every output from the set by the input to spend. Then Spender proves that one of the results has effectively zero secret key, for which [1] has a logarithmic argument (performance and features similar to Bulletproofs).
The resulting proof is reasonably short, but both proving and verification time grows linearly with the size of the set. Moreover, Verifier must retrieve all the outputs from the anonymity set himself to perform the division and run the proof, i.e. the communication costs are linear for him.
The actual verification time, given in the paper, is quite confusing. We see in Table 1 that the verification for the set of 60,000 takes 13 ms, and for the set of 250,000 -- 38ms. However, the 1-of-N proof takes 2 and 8 seconds, respectively! (Table 2). The answer is that the numbers in Table 1 are amortized over batches of 1000 transactions (Tables 3-6), which are indeed not much more expensive to verify than single proofs. However, I find it misleading: any proof thus takes more than 1 second to verify, no matter how many transactions you check.
It will be very interesting to see the size of anonymity sets eventually selected in applications.
[1] "One-out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin" https://eprint.iacr.org/2014/764.pdf
https://eprint.iacr.org/2019/373.pdf
This is a new privacy-oriented cryptocurrency protocol, developed by the Zcoin team. Lelantus claims to achieve both transaction privacy and coin amount secrecy, in the line of Monero, Zcash, Zcoin. The authors claim short proofs and fast verification time, also the ability to batch proofs to enable fast verification of multiple proofs.
The ledger is UTXO based. Each output is just a vector commitment to a secret key and the amount, and an input transaction is a commitment to an output one. When spending a set of input transactions, the spender proves for each of them that it has never been spent by providing a deterministic hash of the secret key, which is looked up in the set of spent coins, and proving knowledge of that key. The spender also provides a proof that the input transaction is a valid commitment to one of previously published outputs. Finally, the spender proves that the sum of inputs matches the sum of outputs and all values are positive and not so big.
Whereas the double-spend and the sum proof are standard (prety much like in Monero and Zcoin), the Bulletproofs range proof is proposed for the latter, the proof of input validity is novel and is the main contribution of the paper. The authors employ the 1-of-N proof technique of [1]. First, they select the set of outputs that contain the one we are spending. Both Spender and Verifier are supposed to divide every output from the set by the input to spend. Then Spender proves that one of the results has effectively zero secret key, for which [1] has a logarithmic argument (performance and features similar to Bulletproofs).
The resulting proof is reasonably short, but both proving and verification time grows linearly with the size of the set. Moreover, Verifier must retrieve all the outputs from the anonymity set himself to perform the division and run the proof, i.e. the communication costs are linear for him.
The actual verification time, given in the paper, is quite confusing. We see in Table 1 that the verification for the set of 60,000 takes 13 ms, and for the set of 250,000 -- 38ms. However, the 1-of-N proof takes 2 and 8 seconds, respectively! (Table 2). The answer is that the numbers in Table 1 are amortized over batches of 1000 transactions (Tables 3-6), which are indeed not much more expensive to verify than single proofs. However, I find it misleading: any proof thus takes more than 1 second to verify, no matter how many transactions you check.
It will be very interesting to see the size of anonymity sets eventually selected in applications.
[1] "One-out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin" https://eprint.iacr.org/2014/764.pdf
Real Crypto via @like
Libra
https://eprint.iacr.org/2019/317.pdf
Libra is notable for its very fast proof generation time, processing about 50,000 gates per second (order of magnitude faster than Bulletproofs). The downside is the trusted setup requirement and Verifier costs linear in circuit depth. The trusted setup, though, should be performed only once for circuits of certain size (like in Sonics).
The idea is to represent each gate as a polynomial with wire values as coefficients such that the circuit is executed correctly if a certain polynomial sums to 0 over the boolean hypercube of its variables (the domain of each variable is the entire field). By utilizing the sumcheck protocol from Goldwasser-Kalai-Rothblum 2015 paper, it is possible to have a zero-knowledge proof with logarithmic size. However, the circuit must first be decomposed into layers with the sumcheck protocol going layer-by-layer, so that the proof and verification time are linear in depth. For each layer the sumcheck hypercube has dimension as logarithm of layer gate count, which is also the communication complexity. The prover complexity is linear in hypercube size, i.e. linear in gate count.
The resulting protocol, despite some similarity to STARK proofs, is not post-quantum: to make the sumcheck protocol zero-knowledge, Prover blinds its polynomials with predefined blinding quadratic polynomials, to which he has to commit first. The commitments security relies on the hardness of discrete logarithm. The need of trusted setup comes from the same subroutine.
It appears that Libra is fast because it makes very few computations on elliptic curves, working mainly with scalars in the circuit field.
https://eprint.iacr.org/2019/317.pdf
Libra is notable for its very fast proof generation time, processing about 50,000 gates per second (order of magnitude faster than Bulletproofs). The downside is the trusted setup requirement and Verifier costs linear in circuit depth. The trusted setup, though, should be performed only once for circuits of certain size (like in Sonics).
The idea is to represent each gate as a polynomial with wire values as coefficients such that the circuit is executed correctly if a certain polynomial sums to 0 over the boolean hypercube of its variables (the domain of each variable is the entire field). By utilizing the sumcheck protocol from Goldwasser-Kalai-Rothblum 2015 paper, it is possible to have a zero-knowledge proof with logarithmic size. However, the circuit must first be decomposed into layers with the sumcheck protocol going layer-by-layer, so that the proof and verification time are linear in depth. For each layer the sumcheck hypercube has dimension as logarithm of layer gate count, which is also the communication complexity. The prover complexity is linear in hypercube size, i.e. linear in gate count.
The resulting protocol, despite some similarity to STARK proofs, is not post-quantum: to make the sumcheck protocol zero-knowledge, Prover blinds its polynomials with predefined blinding quadratic polynomials, to which he has to commit first. The commitments security relies on the hardness of discrete logarithm. The need of trusted setup comes from the same subroutine.
It appears that Libra is fast because it makes very few computations on elliptic curves, working mainly with scalars in the circuit field.
Real Crypto via @like
Crypto 2019
Part 1
1. "How to Record Quantum Queries, and Applications to Quantum Indifferentiability" https://eprint.iacr.org/2018/276.pdf
In classic cryptography many constructions are proven secure assuming their components are random oracles (respond randomly on new inputs). The security proofs are often conducted by constructing an adversary breaking this randomness (so contradiction) from an adversary breaking the bigger system. Such construction requires recording or replaying inputs using by the smaller adversary. Interestingly, when the component runs on a quantum computer and the adversary can query superpositions, the recordings are not directly possible because they would either break the superposition or make the outer adversary entangled with the inner (which is undesired). This highly interesting paper shows how to overtake this problem, with a very nice introduction to the subject in the first pages.
2. "Efficient Collision Attack Frameworks for RIPEMD-160"
There is an older version of the paper https://eprint.iacr.org/2018/652.pdf , which describes advanced methods of building and handling a differential path in a collision attack on RIPEMD-160.
3. Statistical Zeroizing Attack: Cryptanalysis of Candidates of BP Obfuscation over GGH15 Multilinear Map
After candidate Multilinear maps appeared they turned out to be good primitives on Obfuscation schemes. However, many such maps were broken, and this is another paper that does so by looking at statistical distribution of obfuscated programs.
4. Leakage Certification Revisited: Bounding Model Errors in Side-Channel Security Evaluations
https://eprint.iacr.org/2019/132.pdf
Side-channel attacks exploit leaked information on secret keys/states, but the nature of leakage is often imprecise: we can select the model inaccurately and we may estimate the deviations from the model incorrectly. The paper suggests a new model for bounding model errors.
5. Tight Leakage-Resilient CCA-Security from Quasi-Adaptive Hash Proof System
https://eprint.iacr.org/2019/512.pdf
The authors design a public key crypto system that is resilient to private key leakage and has only a small ciphertext expansion (7 group elements). However, the performance of such systems is unknown.
6. Improving Attacks on Round-Reduced Speck32/64 Using Deep Learning
https://eprint.iacr.org/2019/037.pdf
One of the first truly working ML cryptanalytic attacks. The idea is to teach a network which output differences are possible from certain input one, given quite extensive training. Then sub key guesses can be ranked. While the approach sounds suspicious, the authors report a practical implementation, which recovers some keybits of 11-round Speck. I wonder if this result would lead to better understanding of differential behaviour of Speck.
Part 1
1. "How to Record Quantum Queries, and Applications to Quantum Indifferentiability" https://eprint.iacr.org/2018/276.pdf
In classic cryptography many constructions are proven secure assuming their components are random oracles (respond randomly on new inputs). The security proofs are often conducted by constructing an adversary breaking this randomness (so contradiction) from an adversary breaking the bigger system. Such construction requires recording or replaying inputs using by the smaller adversary. Interestingly, when the component runs on a quantum computer and the adversary can query superpositions, the recordings are not directly possible because they would either break the superposition or make the outer adversary entangled with the inner (which is undesired). This highly interesting paper shows how to overtake this problem, with a very nice introduction to the subject in the first pages.
2. "Efficient Collision Attack Frameworks for RIPEMD-160"
There is an older version of the paper https://eprint.iacr.org/2018/652.pdf , which describes advanced methods of building and handling a differential path in a collision attack on RIPEMD-160.
3. Statistical Zeroizing Attack: Cryptanalysis of Candidates of BP Obfuscation over GGH15 Multilinear Map
After candidate Multilinear maps appeared they turned out to be good primitives on Obfuscation schemes. However, many such maps were broken, and this is another paper that does so by looking at statistical distribution of obfuscated programs.
4. Leakage Certification Revisited: Bounding Model Errors in Side-Channel Security Evaluations
https://eprint.iacr.org/2019/132.pdf
Side-channel attacks exploit leaked information on secret keys/states, but the nature of leakage is often imprecise: we can select the model inaccurately and we may estimate the deviations from the model incorrectly. The paper suggests a new model for bounding model errors.
5. Tight Leakage-Resilient CCA-Security from Quasi-Adaptive Hash Proof System
https://eprint.iacr.org/2019/512.pdf
The authors design a public key crypto system that is resilient to private key leakage and has only a small ciphertext expansion (7 group elements). However, the performance of such systems is unknown.
6. Improving Attacks on Round-Reduced Speck32/64 Using Deep Learning
https://eprint.iacr.org/2019/037.pdf
One of the first truly working ML cryptanalytic attacks. The idea is to teach a network which output differences are possible from certain input one, given quite extensive training. Then sub key guesses can be ranked. While the approach sounds suspicious, the authors report a practical implementation, which recovers some keybits of 11-round Speck. I wonder if this result would lead to better understanding of differential behaviour of Speck.
Real Crypto via @like
7. Adaptively Secure and Succinct Functional Encryption: Improving Security and Efficiency, Simultaneously https://eprint.iacr.org/2018/974.pdf
Functional encryption allows decrypting
8. Data-Independent Memory Hard Functions: New Attacks and Stronger Constructions https://eprint.iacr.org/2018/944.pdf
Data-independent MH functions compute the output using a lot of self-filled RAM, and try to make it in the way one is unable to use less RAM. The authors improve on previous memory reduction algorithms, but the best attacks need quite some precomputation. They provide new but no so clear results on the password hashing function Argon2i, which reminds that Argon2id is the most secure variant.
9. Quantum cryptanalysis in the RAM model: Claw-finding attacks on SIKE https://eprint.iacr.org/2019/103.pdf
New model for cost evaluation of quantum attacks, which demonstrates various time-memory tradeoffs when we choose between quantum and classical computers.
10. On the Shortness of Vectors to be found by the Ideal-SVP Quantum Algorithm https://eprint.iacr.org/2019/234.pdf
Lattice-based crypto has been assumed to be quantum-resistant, but some quantum versions of classical lattice algorithms put this assumption under question. The authors show that for practical key sizes the quantum improvements are not yet relevant.
11. Leakage-Resilient Secret Sharing and Applications https://eprint.iacr.org/2018/1154.pdf
New constructions for secret sharing where malicious participants learn some secret from other shareholders via leakage.
12. Watermarking Public-Key Cryptographic Primitives https://eprint.iacr.org/2019/628.pdf
Watermarking public-key encryption or signatures means modifying the signing/decryption algorithm so that signatures are still verifiable on the same key and ciphertexts decryptable but one can extract a mark from the decryption/signing circuit. The authors suggest new constructions for both, allowing public marking, public mark extraction, and prohibiting mark removal.
Functional encryption allows decrypting
f(plaintext) for a class of functions f, each with a diferent decryption key. This paper shows how to build an FE scheme with polynomially many f’s from weaker versions. 8. Data-Independent Memory Hard Functions: New Attacks and Stronger Constructions https://eprint.iacr.org/2018/944.pdf
Data-independent MH functions compute the output using a lot of self-filled RAM, and try to make it in the way one is unable to use less RAM. The authors improve on previous memory reduction algorithms, but the best attacks need quite some precomputation. They provide new but no so clear results on the password hashing function Argon2i, which reminds that Argon2id is the most secure variant.
9. Quantum cryptanalysis in the RAM model: Claw-finding attacks on SIKE https://eprint.iacr.org/2019/103.pdf
New model for cost evaluation of quantum attacks, which demonstrates various time-memory tradeoffs when we choose between quantum and classical computers.
10. On the Shortness of Vectors to be found by the Ideal-SVP Quantum Algorithm https://eprint.iacr.org/2019/234.pdf
Lattice-based crypto has been assumed to be quantum-resistant, but some quantum versions of classical lattice algorithms put this assumption under question. The authors show that for practical key sizes the quantum improvements are not yet relevant.
11. Leakage-Resilient Secret Sharing and Applications https://eprint.iacr.org/2018/1154.pdf
New constructions for secret sharing where malicious participants learn some secret from other shareholders via leakage.
12. Watermarking Public-Key Cryptographic Primitives https://eprint.iacr.org/2019/628.pdf
Watermarking public-key encryption or signatures means modifying the signing/decryption algorithm so that signatures are still verifiable on the same key and ciphertexts decryptable but one can extract a mark from the decryption/signing circuit. The authors suggest new constructions for both, allowing public marking, public mark extraction, and prohibiting mark removal.
Real Crypto via @like
Crypto 2019 Part 3
13. Two-Party ECDSA from Hash Proof Systems and Efficient Instantiations
https://eprint.iacr.org/2019/503.pdf
Only recently there has appeared a threshold ECDSA for 2 parties, but the construction needed non-trivial assumptions. This scheme removes the assumptions with little effect on performance.
14. iO Without Multilinear Maps: New Paradigms via Low-Degree Weak Pseudorandom Generators and Security Amplification https://eprint.iacr.org/2019/643.pdf
Obfuscation has recently been shown to be possible, but with very expensive (also recent) techniques of multilinear maps. This seems to be a breakthrough as no multilinear maps are needed but a number of other new primitives are involved.
15. Lattice-based Zero-Knowledge Proofs: New Techniques for Shorter and Faster Constructions and Applications
Lattice-based ZKP is promising as it seems to resist quantum attacks. This is the first such construction for generic circuits with applications in ring signatures (40KB, grows logarithmically with ring size) and range proofs (50KB).
16. Adaptively Secure MPC with Sublinear Communication Complexity
https://eprint.iacr.org/2018/1161.pdf
Improvements in MPC protocols where an adversary can corrupt any party during the protocol, many times and adaptively.
17. Correlation of Quadratic Boolean Functions: Cryptanalysis of All Versions of Full MORUS https://eprint.iacr.org/2019/172.pdf
MORUS is bit-oriented cipher for authenticated encryption. It has been shown vulnerable to linear cryptanalysis but linear trails are hard to find because of large function description. The author show how to change the form of encryption functions by linear transformation of input variables so that the correlation of the result is easier to compute. Then they find better trails and break the cipher.
18 Watermarking PRFs from Lattices: Stronger Security via Extractable PRFs https://eprint.iacr.org/2018/986.pdf
Paper 12 watermarks public-key systems whereas this one shows how to watermark symmetric primitives. The authors use the hardness of Learning with Errors on lattices in their construction.
13. Two-Party ECDSA from Hash Proof Systems and Efficient Instantiations
https://eprint.iacr.org/2019/503.pdf
Only recently there has appeared a threshold ECDSA for 2 parties, but the construction needed non-trivial assumptions. This scheme removes the assumptions with little effect on performance.
14. iO Without Multilinear Maps: New Paradigms via Low-Degree Weak Pseudorandom Generators and Security Amplification https://eprint.iacr.org/2019/643.pdf
Obfuscation has recently been shown to be possible, but with very expensive (also recent) techniques of multilinear maps. This seems to be a breakthrough as no multilinear maps are needed but a number of other new primitives are involved.
15. Lattice-based Zero-Knowledge Proofs: New Techniques for Shorter and Faster Constructions and Applications
Lattice-based ZKP is promising as it seems to resist quantum attacks. This is the first such construction for generic circuits with applications in ring signatures (40KB, grows logarithmically with ring size) and range proofs (50KB).
16. Adaptively Secure MPC with Sublinear Communication Complexity
https://eprint.iacr.org/2018/1161.pdf
Improvements in MPC protocols where an adversary can corrupt any party during the protocol, many times and adaptively.
17. Correlation of Quadratic Boolean Functions: Cryptanalysis of All Versions of Full MORUS https://eprint.iacr.org/2019/172.pdf
MORUS is bit-oriented cipher for authenticated encryption. It has been shown vulnerable to linear cryptanalysis but linear trails are hard to find because of large function description. The author show how to change the form of encryption functions by linear transformation of input variables so that the correlation of the result is easier to compute. Then they find better trails and break the cipher.
18 Watermarking PRFs from Lattices: Stronger Security via Extractable PRFs https://eprint.iacr.org/2018/986.pdf
Paper 12 watermarks public-key systems whereas this one shows how to watermark symmetric primitives. The authors use the hardness of Learning with Errors on lattices in their construction.
Real Crypto via @like
Interesting talks from ZCash conference Zcon1, Part 1:
https://www.youtube.com/watch?v=AJGLhaUV8QM&list=PL40dyJ0UYTLLjPZaKjdhMoCNanb77_Ztj&index=4
How to break privacy in cryptocurrencies that use incomplete (ring signatures, mixers) privacy. Smart attackers can flood the network with decoys and identify your transactions.
https://www.youtube.com/watch?v=vuzYwutBqjY&list=PL40dyJ0UYTLLjPZaKjdhMoCNanb77_Ztj&index=5
Light client for Bitcoin or similar that can check the correctness of the longest chain claim by smart queries to a few blocks.
https://www.youtube.com/watch?v=oTRAg6Km1os&list=PL40dyJ0UYTLLjPZaKjdhMoCNanb77_Ztj&index=6
Sonic: a new SNARK system, which is apparently Bulletproofs, from which a circuit-independent computation is extracted and used in trusted setup. The most of the talk is devoted to how exactly such computation is identified and delegated.
https://www.youtube.com/watch?v=O8Cn2X2nWxw&list=PL40dyJ0UYTLLjPZaKjdhMoCNanb77_Ztj&index=7
a survey of SNARKs with different parameters and properties
https://www.youtube.com/watch?v=vWqWM6Un48k&list=PL40dyJ0UYTLLjPZaKjdhMoCNanb77_Ztj&index=9
STARK tools are in development by STARK authors
https://www.youtube.com/watch?v=pG-IZ_7NbR8&list=PL40dyJ0UYTLLjPZaKjdhMoCNanb77_Ztj&index=10
Ristretto is a prime order group with fast operations, built upon the set of points of the Ed25519 curve. Here are the dirty details how the cofactor of 8 is eliminated.
https://www.youtube.com/watch?v=AJGLhaUV8QM&list=PL40dyJ0UYTLLjPZaKjdhMoCNanb77_Ztj&index=4
How to break privacy in cryptocurrencies that use incomplete (ring signatures, mixers) privacy. Smart attackers can flood the network with decoys and identify your transactions.
https://www.youtube.com/watch?v=vuzYwutBqjY&list=PL40dyJ0UYTLLjPZaKjdhMoCNanb77_Ztj&index=5
Light client for Bitcoin or similar that can check the correctness of the longest chain claim by smart queries to a few blocks.
https://www.youtube.com/watch?v=oTRAg6Km1os&list=PL40dyJ0UYTLLjPZaKjdhMoCNanb77_Ztj&index=6
Sonic: a new SNARK system, which is apparently Bulletproofs, from which a circuit-independent computation is extracted and used in trusted setup. The most of the talk is devoted to how exactly such computation is identified and delegated.
https://www.youtube.com/watch?v=O8Cn2X2nWxw&list=PL40dyJ0UYTLLjPZaKjdhMoCNanb77_Ztj&index=7
a survey of SNARKs with different parameters and properties
https://www.youtube.com/watch?v=vWqWM6Un48k&list=PL40dyJ0UYTLLjPZaKjdhMoCNanb77_Ztj&index=9
STARK tools are in development by STARK authors
https://www.youtube.com/watch?v=pG-IZ_7NbR8&list=PL40dyJ0UYTLLjPZaKjdhMoCNanb77_Ztj&index=10
Ristretto is a prime order group with fast operations, built upon the set of points of the Ed25519 curve. Here are the dirty details how the cofactor of 8 is eliminated.
YouTube
The State of Privacy in Cryptocurrencies - Ian Miers
Live at Zcon1: Zero to Privacy Hero - Day 1
Presented by Zcash Foundation in Split, Croatia
Presented by Zcash Foundation in Split, Croatia
Real Crypto via @like
Crypto 2019. Part 4
19. The Communication Complexity of Threshold Private Set Intersection https://eprint.iacr.org/2019/175.pdf
The problem is for Alice and Bob to find an intersection between their sets if it is big enough. The authors prove tight bounds on the communication complexity by encoding set elements as monomials
20. Match Me if You Can: Matchmaking Encryption and its Applications https://eprint.iacr.org/2018/1094.pdf
The new encryption type: users have some attributes, and it is possible to construct an encryption-decryption keypair so that only certain combinations of attributes at each side allows first encryption and then decryption. Allegedly helpful for spies from different agencies.
21. Scalable Zero Knowledge with no Trusted Setup
https://eprint.iacr.org/2018/046.pdf
The paper introduces ZK-STARKs, a recent generic ZK proof technique which uses only polynomial math and collision-resistant hashes, which yields post-quantum security, short proofs, and no need in trusted setup.
22. Seedless Fruit is the Sweetest: Random Number Generation, Revisited https://eprint.iacr.org/2019/198.pdf
Previous pseudo-random number generators that are secure to adversarially-controlled entropy, require adversary-noncontrolled seed to initialize. Here are new definitions and results for PRNG that do not use seeds.
23. Revisiting Post-Quantum Fiat-Shamir https://eprint.iacr.org/2019/262.pdf
Nice complement to Paper 1: the authors show that the Fiat-Shamir technique to turn interactive ZK protocols to non-interactive is secure in the quantum world, i.e. when we can query the underlying hash function with a superposition of inputs. As one result, one post-quantum lattice-based protocol is shown to be secure when using Fiat-Shamir. What about STARKs?
24. Broadcast and Trace with N^\epsilon Ciphertext Size from Standard Assumptions https://eprint.iacr.org/2019/636.pdf
Here the task is to broadcast an encrypted message to a subset of users, where the subset is different every time, and so that the ciphertext does not grow linearly with the (sub)set size. The authors adds many other requirements to advance in the state of art, concretely being able to identify a colluding set of users who publish their combined key to help others.
19. The Communication Complexity of Threshold Private Set Intersection https://eprint.iacr.org/2019/175.pdf
The problem is for Alice and Bob to find an intersection between their sets if it is big enough. The authors prove tight bounds on the communication complexity by encoding set elements as monomials
20. Match Me if You Can: Matchmaking Encryption and its Applications https://eprint.iacr.org/2018/1094.pdf
The new encryption type: users have some attributes, and it is possible to construct an encryption-decryption keypair so that only certain combinations of attributes at each side allows first encryption and then decryption. Allegedly helpful for spies from different agencies.
21. Scalable Zero Knowledge with no Trusted Setup
https://eprint.iacr.org/2018/046.pdf
The paper introduces ZK-STARKs, a recent generic ZK proof technique which uses only polynomial math and collision-resistant hashes, which yields post-quantum security, short proofs, and no need in trusted setup.
22. Seedless Fruit is the Sweetest: Random Number Generation, Revisited https://eprint.iacr.org/2019/198.pdf
Previous pseudo-random number generators that are secure to adversarially-controlled entropy, require adversary-noncontrolled seed to initialize. Here are new definitions and results for PRNG that do not use seeds.
23. Revisiting Post-Quantum Fiat-Shamir https://eprint.iacr.org/2019/262.pdf
Nice complement to Paper 1: the authors show that the Fiat-Shamir technique to turn interactive ZK protocols to non-interactive is secure in the quantum world, i.e. when we can query the underlying hash function with a superposition of inputs. As one result, one post-quantum lattice-based protocol is shown to be secure when using Fiat-Shamir. What about STARKs?
24. Broadcast and Trace with N^\epsilon Ciphertext Size from Standard Assumptions https://eprint.iacr.org/2019/636.pdf
Here the task is to broadcast an encrypted message to a subset of users, where the subset is different every time, and so that the ciphertext does not grow linearly with the (sub)set size. The authors adds many other requirements to advance in the state of art, concretely being able to identify a colluding set of users who publish their combined key to help others.
A couple of remaining Zcon1 talks that worth watching
https://www.youtube.com/watch?v=fXWRJUsq8Ok&list=PL40dyJ0UYTLLjPZaKjdhMoCNanb77_Ztj&index=16
ZEXE: how to make computation decentralized and zero knowledge: allow writes to certain memory/tree leafs only to those who prove identity and transition logic in zero knowledge.
https://www.youtube.com/watch?v=J9OGAwt_f_c&list=PL40dyJ0UYTLLjPZaKjdhMoCNanb77_Ztj&index=19
ZKVM: a virtual machine that is oriented to asset flow provable and enforceable in zero knowledge. More details at https://github.com/stellar/slingshot/blob/main/zkvm/docs/zkvm-design.md
https://www.youtube.com/watch?v=v_EvxrgEhbA&list=PL40dyJ0UYTLLjPZaKjdhMoCNanb77_Ztj&index=22
Explaining a way to STARKs and why they are secure in the quantum ROM setting
https://www.youtube.com/watch?v=fXWRJUsq8Ok&list=PL40dyJ0UYTLLjPZaKjdhMoCNanb77_Ztj&index=16
ZEXE: how to make computation decentralized and zero knowledge: allow writes to certain memory/tree leafs only to those who prove identity and transition logic in zero knowledge.
https://www.youtube.com/watch?v=J9OGAwt_f_c&list=PL40dyJ0UYTLLjPZaKjdhMoCNanb77_Ztj&index=19
ZKVM: a virtual machine that is oriented to asset flow provable and enforceable in zero knowledge. More details at https://github.com/stellar/slingshot/blob/main/zkvm/docs/zkvm-design.md
https://www.youtube.com/watch?v=v_EvxrgEhbA&list=PL40dyJ0UYTLLjPZaKjdhMoCNanb77_Ztj&index=22
Explaining a way to STARKs and why they are secure in the quantum ROM setting
YouTube
ZEXE: Enabling Decentralized Private Computation - Pratyush Mishra
Live at Zcon1: Zero to Privacy Hero - Day 2
Presented by Zcash Foundation in Split, Croatia
Presented by Zcash Foundation in Split, Croatia
Crypto 2019. Part 5
25. Exploring Constructions of Compact NIZKs from Various Assumptions
https://eprint.iacr.org/2019/623.pdf
Very long theoretical paper about asymptotically efficient zero-knowledge proofs for generic circuits.
26. Highly Efficient Key Exchange Protocols with Optimal Tightness
https://eprint.iacr.org/2019/737.pdf
Existing key agreement protocols used in TLS or Signal do not have tight proofs: the security parameters chosen there are too weak for attack lower bounds proven for the protocol. The authors show how to modify those protocols so that the proofs are tight but the parameters are still efficient.
27. Communication-Efficient Unconditional MPC with Guaranteed Output Delivery
https://eprint.iacr.org/2019/646.pdf
The authors show the first MPC protocol with 3 conditions combined: (1) complexity per gate is linear in the number of users (2) unconditional rather than computational security (3) at most n/3 users are corrupted. Previous results could not have that low complexity.
28. Quantum Indistinguishability of Random Sponges https://eprint.iacr.org/2019/069.pdf
It is known that many keyed symmetric cryptoschemes, if queried with a superposition of inputs on a quantum computer, can be easily broken. The paper shows that a keyed random sponge is still secure in the quantum setting, thus highlighting the importance of inner state untouched by an adversary. The authors show how to fix symmetric constructions previously broken with quantum attacks.
29. Simultaneous Amplification: The Case of Non-Interactive Zero-Knowledge
https://eprint.iacr.org/2019/626.pdf
The authors show how to convert ZK protocols with constant errors in soundness and zero-knowledge properties to a fully secure protocol with minimal overhead. The reason is that a protocol with errors can be simpler and easier to construct.
30. Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation
https://eprint.iacr.org/2019/317.pdf
One of promising ZK generic proof systems with a fast prover and verifier being linear in circuit depth rather than in circuit size. Main applications are correctness of Merkle tree construction and else. More details in our earlier post in this channel.
25. Exploring Constructions of Compact NIZKs from Various Assumptions
https://eprint.iacr.org/2019/623.pdf
Very long theoretical paper about asymptotically efficient zero-knowledge proofs for generic circuits.
26. Highly Efficient Key Exchange Protocols with Optimal Tightness
https://eprint.iacr.org/2019/737.pdf
Existing key agreement protocols used in TLS or Signal do not have tight proofs: the security parameters chosen there are too weak for attack lower bounds proven for the protocol. The authors show how to modify those protocols so that the proofs are tight but the parameters are still efficient.
27. Communication-Efficient Unconditional MPC with Guaranteed Output Delivery
https://eprint.iacr.org/2019/646.pdf
The authors show the first MPC protocol with 3 conditions combined: (1) complexity per gate is linear in the number of users (2) unconditional rather than computational security (3) at most n/3 users are corrupted. Previous results could not have that low complexity.
28. Quantum Indistinguishability of Random Sponges https://eprint.iacr.org/2019/069.pdf
It is known that many keyed symmetric cryptoschemes, if queried with a superposition of inputs on a quantum computer, can be easily broken. The paper shows that a keyed random sponge is still secure in the quantum setting, thus highlighting the importance of inner state untouched by an adversary. The authors show how to fix symmetric constructions previously broken with quantum attacks.
29. Simultaneous Amplification: The Case of Non-Interactive Zero-Knowledge
https://eprint.iacr.org/2019/626.pdf
The authors show how to convert ZK protocols with constant errors in soundness and zero-knowledge properties to a fully secure protocol with minimal overhead. The reason is that a protocol with errors can be simpler and easier to construct.
30. Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation
https://eprint.iacr.org/2019/317.pdf
One of promising ZK generic proof systems with a fast prover and verifier being linear in circuit depth rather than in circuit size. Main applications are correctness of Merkle tree construction and else. More details in our earlier post in this channel.
Crypto 2019, part 6
31. Stronger leakage-resilient and non-malleable secret sharing schemes for general access structures
https://eprint.iacr.org/2018/1147.pdf
How to share a secret if leakage is present.
32. Security of the Fiat-Shamir Transformation in the Quantum Random-Oracle Model https://eprint.iacr.org/2019/190.pdf
Similar to paper 23, but with a bit stronger security guarantees.
33. Non-Interactive Non-Malleability from Quantum Supremacy
https://eprint.iacr.org/2018/1118.pdf
Theoretical result about constructing commitments that are non-malleable, so that an adversary can not change the message inside meaningfully.
34. Communication Lower Bounds for Statistically Secure MPC, with or without Preprocessing
https://eprint.iacr.org/2019/220.pdf
Complementing paper 27, the authors show that an MPC protocol secure against an unbounded adversary, must have communication complexity proportional to (number of gates)X(number of parties).
35. The Distinction Between Fixed and Random Generators in Group-Based Assumptions https://eprint.iacr.org/2019/202.pdf
The authors revisit the security of many protocols in the assumption that the group generators are randomly or maliciously chosen. For example, they obtain some lower bounds for preprocessing DLog attacks
36. Non-Malleable Secret Sharing in the Computational Setting: Adaptive Tampering, Noisy-Leakage Resilience, and Improved Rate https://eprint.iacr.org/2019/105.pdf
Complementing paper 31: another paper on how to share a secret for threshold signing/decryption if an adversary can tamper with shares continiously.
31. Stronger leakage-resilient and non-malleable secret sharing schemes for general access structures
https://eprint.iacr.org/2018/1147.pdf
How to share a secret if leakage is present.
32. Security of the Fiat-Shamir Transformation in the Quantum Random-Oracle Model https://eprint.iacr.org/2019/190.pdf
Similar to paper 23, but with a bit stronger security guarantees.
33. Non-Interactive Non-Malleability from Quantum Supremacy
https://eprint.iacr.org/2018/1118.pdf
Theoretical result about constructing commitments that are non-malleable, so that an adversary can not change the message inside meaningfully.
34. Communication Lower Bounds for Statistically Secure MPC, with or without Preprocessing
https://eprint.iacr.org/2019/220.pdf
Complementing paper 27, the authors show that an MPC protocol secure against an unbounded adversary, must have communication complexity proportional to (number of gates)X(number of parties).
35. The Distinction Between Fixed and Random Generators in Group-Based Assumptions https://eprint.iacr.org/2019/202.pdf
The authors revisit the security of many protocols in the assumption that the group generators are randomly or maliciously chosen. For example, they obtain some lower bounds for preprocessing DLog attacks
36. Non-Malleable Secret Sharing in the Computational Setting: Adaptive Tampering, Noisy-Leakage Resilience, and Improved Rate https://eprint.iacr.org/2019/105.pdf
Complementing paper 31: another paper on how to share a secret for threshold signing/decryption if an adversary can tamper with shares continiously.
Crypto 2019 Part 7
37. Unifying Leakage Models on a Rényi Day
https://eprint.iacr.org/2019/138.pdf
How to model the number of probes in side channel attacks: new approaches based on the statistical difference between two distributions.
38. Low Memory Attacks against Two-Round Even-Mansour using the 3-XOR Problem
N/A
39. Cryptographic Sensing https://eprint.iacr.org/2019/637.pdf
This is a new concept with the following scenario. Reader can compute certain functions of a secret object so that (a) the way the concrete functions were selected is itself a trapdoor and can be used to learn the object and (b) without the trapdoor the object can not be learned. An application is a commercial experiment delegated to an untrusted party: the party can do the measurements but without knowledge why the exact measurement had been chosed he can not learn the data.
40. Fully Secure Attribute-Based Encryption for t-CNF from LWE https://eprint.iacr.org/2019/365.pdf
Here is the paper, where for ABE (when users decrypt different subsets of ciphertexts depending on their permissions) a wider class of permissions is implemented: where the conjunctive normal form has only t-size clauses.
41. Universally Composable Secure Computation with Corrupted Tokens
https://eprint.iacr.org/2017/1092.pdf
It is possible to have an MPC that is based on trusted hardware, which is not just secure but secure under composition. This paper shows how to do it if some hardware is corrupted.
42. Non-Malleable Codes for Decision Trees https://eprint.iacr.org/2019/379.pdf
If codewords can be decoded even if a tampering function is applied then the code is non-malleable. This paper presents a code resistant to tampering functions which have constant depth.
43. Non-Uniformly Sound Certificates with Applications to Concurrent Zero-Knowledge https://eprint.iacr.org/2019/631.pdf
Theoretical results for the existence of zero-knowledge arguments, which assume no input from verifier and bounded non-uniform adversary (i.e. only the ones we explicitly build).
37. Unifying Leakage Models on a Rényi Day
https://eprint.iacr.org/2019/138.pdf
How to model the number of probes in side channel attacks: new approaches based on the statistical difference between two distributions.
38. Low Memory Attacks against Two-Round Even-Mansour using the 3-XOR Problem
N/A
39. Cryptographic Sensing https://eprint.iacr.org/2019/637.pdf
This is a new concept with the following scenario. Reader can compute certain functions of a secret object so that (a) the way the concrete functions were selected is itself a trapdoor and can be used to learn the object and (b) without the trapdoor the object can not be learned. An application is a commercial experiment delegated to an untrusted party: the party can do the measurements but without knowledge why the exact measurement had been chosed he can not learn the data.
40. Fully Secure Attribute-Based Encryption for t-CNF from LWE https://eprint.iacr.org/2019/365.pdf
Here is the paper, where for ABE (when users decrypt different subsets of ciphertexts depending on their permissions) a wider class of permissions is implemented: where the conjunctive normal form has only t-size clauses.
41. Universally Composable Secure Computation with Corrupted Tokens
https://eprint.iacr.org/2017/1092.pdf
It is possible to have an MPC that is based on trusted hardware, which is not just secure but secure under composition. This paper shows how to do it if some hardware is corrupted.
42. Non-Malleable Codes for Decision Trees https://eprint.iacr.org/2019/379.pdf
If codewords can be decoded even if a tampering function is applied then the code is non-malleable. This paper presents a code resistant to tampering functions which have constant depth.
43. Non-Uniformly Sound Certificates with Applications to Concurrent Zero-Knowledge https://eprint.iacr.org/2019/631.pdf
Theoretical results for the existence of zero-knowledge arguments, which assume no input from verifier and bounded non-uniform adversary (i.e. only the ones we explicitly build).
Real Crypto via @like
Pedersen hash weaknesses
Pedersen hash has been popularized by Zcash team as ZK-friendly hash function suitable for Merkle trees. Its simplest version operates on an elliptic curve with two fixed generators G and H with unknown discrete log relation. Then to hash two integers (a,b) one computes
P = aG + bH
and takes some compressed version of P (e.g. x-coordinate) as a result. There are several extensions of this construction to longer messages using multiple generators [1] or just by a recursive Merkle-Damgard calling. In contrast to regular hash functions like Keccak there is a formal security proof for collision resistance as any collision implies a discrete logarithm relation between G and H.
There are several problems with this construction. First, from the implementation perspective it is quite complicated. To hash messages within some field F, one has to define an elliptic curve with the order bigger than |F| but the coordinates being in F. For zero-knowledge proofs one has to convert elliptic curve equations into degree-2 constraints, and also work with the bit representation of (a,b) in order to reduce the scalar multiplication to point addition and doubling. Altogether this makes quite a non-trivial circuit, but it is still doable.
From the cryptographic point of view the situation is worse. Pedersen hash has several properties quite unexpected from a cryptographic hash function. First, it is homomorphic: H(ab,cd) = H(a,b) + H(c,d). This property alone is not problematic and is even common for cryptographic commitments and many other primitives. However, it implies that the function is vulnerable to length-extension attacks: given H(A) it is easy to compute H(A,B) for some integer tuples A and B. This property, being present in SHA-0/1/2 and forbidden in SHA-3, caused many attacks like [2]. It makes a natural MAC construction MAC(M) = H(K || M) insecure, and rules out a common domain separation method of creating many functions from one as H_i(x) = H(i||x).
Finally, the preimage security of Pedersen is weaker than expected. For an n-bit elliptic curve it is not 2^(n/2) as one would hope for. If the hashed message is l-bit long for l<n the preimage search cost is not min(2^l,2^(n/2)) but only 2^(l/2). Indeed, let a and b be l/2 -bit long. Then define f(x) = xG and g(y) = P-yH. Thus the preimage for P is just a collision between f and g, which can be found memoryless in 2^(l/2) steps. Last but not least, the multi-target preimage security is even lower: to find 2^k preimages for l-bit messages, one performs only 2^(l/2+k/2) hash function calls thus making the amortized preimage search cost as low as 2^(l/2-k/2). In concrete numbers, if one hashes 1000 128-bit messages with Pedersen, each preimage costs you only 2^59.
We do not recommend using Pedersen hash in protocols and applications.
[1] https://iden3-docs.readthedocs.io/en/latest/iden3_repos/research/publications/zkproof-standards-workshop-2/pedersen-hash/pedersen.html
[2] http://netifera.com/research/flickr_api_signature_forgery.pdf
Pedersen hash has been popularized by Zcash team as ZK-friendly hash function suitable for Merkle trees. Its simplest version operates on an elliptic curve with two fixed generators G and H with unknown discrete log relation. Then to hash two integers (a,b) one computes
P = aG + bH
and takes some compressed version of P (e.g. x-coordinate) as a result. There are several extensions of this construction to longer messages using multiple generators [1] or just by a recursive Merkle-Damgard calling. In contrast to regular hash functions like Keccak there is a formal security proof for collision resistance as any collision implies a discrete logarithm relation between G and H.
There are several problems with this construction. First, from the implementation perspective it is quite complicated. To hash messages within some field F, one has to define an elliptic curve with the order bigger than |F| but the coordinates being in F. For zero-knowledge proofs one has to convert elliptic curve equations into degree-2 constraints, and also work with the bit representation of (a,b) in order to reduce the scalar multiplication to point addition and doubling. Altogether this makes quite a non-trivial circuit, but it is still doable.
From the cryptographic point of view the situation is worse. Pedersen hash has several properties quite unexpected from a cryptographic hash function. First, it is homomorphic: H(ab,cd) = H(a,b) + H(c,d). This property alone is not problematic and is even common for cryptographic commitments and many other primitives. However, it implies that the function is vulnerable to length-extension attacks: given H(A) it is easy to compute H(A,B) for some integer tuples A and B. This property, being present in SHA-0/1/2 and forbidden in SHA-3, caused many attacks like [2]. It makes a natural MAC construction MAC(M) = H(K || M) insecure, and rules out a common domain separation method of creating many functions from one as H_i(x) = H(i||x).
Finally, the preimage security of Pedersen is weaker than expected. For an n-bit elliptic curve it is not 2^(n/2) as one would hope for. If the hashed message is l-bit long for l<n the preimage search cost is not min(2^l,2^(n/2)) but only 2^(l/2). Indeed, let a and b be l/2 -bit long. Then define f(x) = xG and g(y) = P-yH. Thus the preimage for P is just a collision between f and g, which can be found memoryless in 2^(l/2) steps. Last but not least, the multi-target preimage security is even lower: to find 2^k preimages for l-bit messages, one performs only 2^(l/2+k/2) hash function calls thus making the amortized preimage search cost as low as 2^(l/2-k/2). In concrete numbers, if one hashes 1000 128-bit messages with Pedersen, each preimage costs you only 2^59.
We do not recommend using Pedersen hash in protocols and applications.
[1] https://iden3-docs.readthedocs.io/en/latest/iden3_repos/research/publications/zkproof-standards-workshop-2/pedersen-hash/pedersen.html
[2] http://netifera.com/research/flickr_api_signature_forgery.pdf