Real Crypto via @like
Real World Crypto 2019
Part 3 (Day 2 Afternoon-1)
19) https://youtu.be/JoaYGncArwU?t=1266 https://rwc.iacr.org/2019/slides/DAA.pdf Direct Anonymous Attestation (DAA) is a scheme that unites a number of TPM-enabled devices in a group signature scheme, so that their signatures are by default anonymous but can be linked quite flexibly. Devices can get (anonymous) credentials in a way similar to Anoncred frameworks Idemix (IBM) or U-Prove (Microsoft). The talk covers vulnerabilities in previous versions, issues in DAA applied to automobiles, and quantum-secure version with lattice signatures.
20) https://youtu.be/JoaYGncArwU?t=2178 https://rwc.iacr.org/2019/slides/how-hard-is-solving-lwe-anyway.pdf
There are several schemes submitted to NIST quantum-secure competition that are based on Learning with Errors (LWE). Apparently each scheme has its own security model, and there as many ways to compare schemes as many schemes you have. The talk goes deep to the existing attacks on LWE, and shows that their complexity can be evaluated differently, both in classical or quantum world.
21) https://rwc.iacr.org/2019/slides/RWC87slides.pdf The story how the cryptographic community managed to block the acceptance of NSA-designed ciphers SIMON and SPECK as ISO standards because of past NSA trapdoor-placing activity. Interestingly the community found no cryptographic vulnerabilities nor trapdoors in these ciphers (and they indeed look well designed). The authors convinced the working group to state that "both algorithm are not properly motivated and their security properties are not sufficiently understood."
I think this can be said about almost any cipher (except AES and DES maybe) with the same confidence.
Part 3 (Day 2 Afternoon-1)
19) https://youtu.be/JoaYGncArwU?t=1266 https://rwc.iacr.org/2019/slides/DAA.pdf Direct Anonymous Attestation (DAA) is a scheme that unites a number of TPM-enabled devices in a group signature scheme, so that their signatures are by default anonymous but can be linked quite flexibly. Devices can get (anonymous) credentials in a way similar to Anoncred frameworks Idemix (IBM) or U-Prove (Microsoft). The talk covers vulnerabilities in previous versions, issues in DAA applied to automobiles, and quantum-secure version with lattice signatures.
20) https://youtu.be/JoaYGncArwU?t=2178 https://rwc.iacr.org/2019/slides/how-hard-is-solving-lwe-anyway.pdf
There are several schemes submitted to NIST quantum-secure competition that are based on Learning with Errors (LWE). Apparently each scheme has its own security model, and there as many ways to compare schemes as many schemes you have. The talk goes deep to the existing attacks on LWE, and shows that their complexity can be evaluated differently, both in classical or quantum world.
21) https://rwc.iacr.org/2019/slides/RWC87slides.pdf The story how the cryptographic community managed to block the acceptance of NSA-designed ciphers SIMON and SPECK as ISO standards because of past NSA trapdoor-placing activity. Interestingly the community found no cryptographic vulnerabilities nor trapdoors in these ciphers (and they indeed look well designed). The authors convinced the working group to state that "both algorithm are not properly motivated and their security properties are not sufficiently understood."
I think this can be said about almost any cipher (except AES and DES maybe) with the same confidence.
YouTube
Real World Crypto 2019 - Day 2 - Session 2 - Afternoon - Part 1
Real World Crypto January 9, 2019 meeting at the San Jose Marriott. This is day 2 session 2 which goes from 2:00PM until 5:05PM
Real Crypto via @like
ZETHER
https://crypto.stanford.edu/~buenz/papers/zether.pdf
Zether is a new privacy-oriented cryptocurrency, notably different from Monero, Zcash and their derivatives. First, its ledger is an Ethereum smart contract (but of course one can imagine a separated ledger with its own consensus for that). In contrast to all alternatives, Zether is balance-based rather than UTXO-based. It means that the available coins for spending are not just incoming transactions (UTXO, like in Bitcoin/Zcash/Monero), but just an integer number in the balance table.
There are two components in privacy-oriented currencies: anonymity of spender and confidentiality of amount. The amount is ElGamal-encrypted for each public key, and thanks to the homomorphic property, it is sufficient to just multiply the ciphertext of incoming amount by the ciphertext of existing balance to get a new one. The spender provides a ZK proof that the transaction is well-formed, input/output balances match, and each amount is a not so large positive integer (here Bulletproofs are used for range proofs).
Spender anonymity is achieved, similarly to Monero, by enabling a verifiable corruption of many balances at once, so that keys from the anonymity set get the verifiable 0 of coins to their account, and only sender/receiver balances change.
Since the correctness proof involves several simple statements on encrypted amounts, the authors use standard sigma-protocols for such statements instead of Bulletproofs, which reduces proving and verification time considerably (and thus the gas costs). They call this combination of protocols Sigma-Bullet.
Even though the proofs are reasonably short and can be verified in the Ethereum Virtual Machine within the block gas limit of 8 mln, there are still several drawbacks. The evident one is that the anonymity is limited and scales linearly with proof size/cost. The second problem is that all transactions are vulnerable to front-runs: if any other transaction changes the balance from the anonymity set, our transaction will fail. To prevent that, the authors suggest a real, excuse me, kludge: they put all transactions into the pending state so that they are applied only after a certain period of time, in certain order, and only by designated senders. The authors claim to mitigate several new attack vectors that are caused by this approach, but I am not really convinced that these attacks are excluded.
To summarize, this paper looks to me an excellent example why privacy-oriented currencies should be UTXO-based rather than balance-based.
https://crypto.stanford.edu/~buenz/papers/zether.pdf
Zether is a new privacy-oriented cryptocurrency, notably different from Monero, Zcash and their derivatives. First, its ledger is an Ethereum smart contract (but of course one can imagine a separated ledger with its own consensus for that). In contrast to all alternatives, Zether is balance-based rather than UTXO-based. It means that the available coins for spending are not just incoming transactions (UTXO, like in Bitcoin/Zcash/Monero), but just an integer number in the balance table.
There are two components in privacy-oriented currencies: anonymity of spender and confidentiality of amount. The amount is ElGamal-encrypted for each public key, and thanks to the homomorphic property, it is sufficient to just multiply the ciphertext of incoming amount by the ciphertext of existing balance to get a new one. The spender provides a ZK proof that the transaction is well-formed, input/output balances match, and each amount is a not so large positive integer (here Bulletproofs are used for range proofs).
Spender anonymity is achieved, similarly to Monero, by enabling a verifiable corruption of many balances at once, so that keys from the anonymity set get the verifiable 0 of coins to their account, and only sender/receiver balances change.
Since the correctness proof involves several simple statements on encrypted amounts, the authors use standard sigma-protocols for such statements instead of Bulletproofs, which reduces proving and verification time considerably (and thus the gas costs). They call this combination of protocols Sigma-Bullet.
Even though the proofs are reasonably short and can be verified in the Ethereum Virtual Machine within the block gas limit of 8 mln, there are still several drawbacks. The evident one is that the anonymity is limited and scales linearly with proof size/cost. The second problem is that all transactions are vulnerable to front-runs: if any other transaction changes the balance from the anonymity set, our transaction will fail. To prevent that, the authors suggest a real, excuse me, kludge: they put all transactions into the pending state so that they are applied only after a certain period of time, in certain order, and only by designated senders. The authors claim to mitigate several new attack vectors that are caused by this approach, but I am not really convinced that these attacks are excluded.
To summarize, this paper looks to me an excellent example why privacy-oriented currencies should be UTXO-based rather than balance-based.
Real Crypto via @like
Real World Crypto 2019
Part 4 (Day 2 Afternoon-2)
22) https://youtu.be/4hq4yiVCopU?t=181 Intel SGX is an CPU extension enabling computing on secret data with attestation of correctness. It uses a part of memory encrypted with a boot-generated key, all this is protected by the OS. Recent attacks Meltdown and Spectre exploit pipeline organization in the modern CPU to access forbidden data. Similarly to those, it is possible to request data from address dependent on the SGX memory, and apparently a crafted request (usually, an intentionally faulty one) can expose the secret data between the moments of decryption and garbage collection.
23) https://youtu.be/4hq4yiVCopU?t=1743 Standardizing a new RISC architecture, called RISC-V, with a help from a broad community. Calls for expertise and R&D activities.
24) https://youtu.be/4hq4yiVCopU?t=2774 Explaining True2F, an extension to U2F, a token, which can authenticate using a public-key crypto. This extension protects from possible backdoors in the token, making the public key generation part of the initialization process. It also creates a public key deterministically from the website address. Overall, 2-3x overhead.
25) https://youtu.be/4hq4yiVCopU?t=4257 Reverse-engineering and breaking the authentication process in Tesla and McLaren cars. Apparently the fob hardware uses a stream cipher with a 40-bit key. The authors eavesdropped the fob-car communication and managed to send a correct response after guessing the key. It is also possible to clone the fob rather easily. The car manufacturers were notified but made false statements on the attack complexity. Very interesting and clever research!
Part 4 (Day 2 Afternoon-2)
22) https://youtu.be/4hq4yiVCopU?t=181 Intel SGX is an CPU extension enabling computing on secret data with attestation of correctness. It uses a part of memory encrypted with a boot-generated key, all this is protected by the OS. Recent attacks Meltdown and Spectre exploit pipeline organization in the modern CPU to access forbidden data. Similarly to those, it is possible to request data from address dependent on the SGX memory, and apparently a crafted request (usually, an intentionally faulty one) can expose the secret data between the moments of decryption and garbage collection.
23) https://youtu.be/4hq4yiVCopU?t=1743 Standardizing a new RISC architecture, called RISC-V, with a help from a broad community. Calls for expertise and R&D activities.
24) https://youtu.be/4hq4yiVCopU?t=2774 Explaining True2F, an extension to U2F, a token, which can authenticate using a public-key crypto. This extension protects from possible backdoors in the token, making the public key generation part of the initialization process. It also creates a public key deterministically from the website address. Overall, 2-3x overhead.
25) https://youtu.be/4hq4yiVCopU?t=4257 Reverse-engineering and breaking the authentication process in Tesla and McLaren cars. Apparently the fob hardware uses a stream cipher with a 40-bit key. The authors eavesdropped the fob-car communication and managed to send a correct response after guessing the key. It is also possible to clone the fob rather easily. The car manufacturers were notified but made false statements on the attack complexity. Very interesting and clever research!
YouTube
Real World Crypto 2019 - Day 2 - Session 2 - Afternoon - Part 3
Real World Crypto January 9, 2019 meeting at the San Jose Marriott. This is day 2 session 2 part 3 which goes from 2:00PM until 5:05PM
Real Crypto via @like
ZcashGate
Today the Zcash team announced a major vulnerability found and fixed in the Zcash protocol. https://z.cash/blog/zcash-counterfeiting-vulnerability-successfully-remediated/
The story is quite controversial: the flaw was deemed too complicated to discover by attackers but extremely exploitable under a smallest hint. Because of that the fix was covertly added to the upcoming hard fork, Sapling, 8 months after its discovery.
The details are as follows. The zkSNARK technique requires a trusted party to generate the key pair needed for proof construction and verification. The key generation requires a secret, which should be kept secret by the trusted party or generated collectively by a group of participants ("trusted setup ceremony"), because the one who knows the secret can generate fake proofs.
The original Zcash was based on the 2014 paper by Ben-Sasson et al., which was itself a modification of the 2013 paper by Parno et al. The newer paper introduced a faster proof technique, which required publishing a few more secret-dependent polynomials during the setup phase. The 2014 paper did not prove the necessity of all these polynomials (the 2013 one did for its own set). In 2015, before the Zcash launch, Parno found a flaw in the 2014 paper, showing that these polynomials contain an excessive information about the secret used by the trusted party and thus allowing easy fake proof generation. The revised setup still did not come with a proof of correctness.
Apparently this was not the only bug to be found in that setup. In March 2018 Gabizon discovered another bug of the same kind. The problem was that the trusted setup for Zcash has already happened and anyone who would find this bug could print ZEC coins out of air. Given the alternative of stopping the entire Zcash protocol, the small subteam of Zcash decided to keep it secret till the next trusted setup, which eventually happened in October 2018 and was based on a different 2016 paper by Groth, now with a security proof.
Gabizon has since found the proof of correctness for the revised 2014 paper, but it was too late. https://github.com/arielgabizon/bctv/blob/master/bctv.pdf?fbclid=IwAR1wKtN8Ddh9IDuhIqd2O55MKQQG1z5tJB_t-X6ZgXYIPKzhbjSsIRCGv7o
This story demonstrates that the trusted setup ceremony, due to its complicacy, is error-prone and is very difficult to fix. I also lost confidence (a bit) in Zcash, as we do not know if they have already found a bug after the second ceremony and wait for the third one. I doubt the judgement that no one else could have found the bug. I think that even though a cryptographer was needed for that, the place to search was very clear: it is a lemma without a proof.
Let us see how it goes.
Today the Zcash team announced a major vulnerability found and fixed in the Zcash protocol. https://z.cash/blog/zcash-counterfeiting-vulnerability-successfully-remediated/
The story is quite controversial: the flaw was deemed too complicated to discover by attackers but extremely exploitable under a smallest hint. Because of that the fix was covertly added to the upcoming hard fork, Sapling, 8 months after its discovery.
The details are as follows. The zkSNARK technique requires a trusted party to generate the key pair needed for proof construction and verification. The key generation requires a secret, which should be kept secret by the trusted party or generated collectively by a group of participants ("trusted setup ceremony"), because the one who knows the secret can generate fake proofs.
The original Zcash was based on the 2014 paper by Ben-Sasson et al., which was itself a modification of the 2013 paper by Parno et al. The newer paper introduced a faster proof technique, which required publishing a few more secret-dependent polynomials during the setup phase. The 2014 paper did not prove the necessity of all these polynomials (the 2013 one did for its own set). In 2015, before the Zcash launch, Parno found a flaw in the 2014 paper, showing that these polynomials contain an excessive information about the secret used by the trusted party and thus allowing easy fake proof generation. The revised setup still did not come with a proof of correctness.
Apparently this was not the only bug to be found in that setup. In March 2018 Gabizon discovered another bug of the same kind. The problem was that the trusted setup for Zcash has already happened and anyone who would find this bug could print ZEC coins out of air. Given the alternative of stopping the entire Zcash protocol, the small subteam of Zcash decided to keep it secret till the next trusted setup, which eventually happened in October 2018 and was based on a different 2016 paper by Groth, now with a security proof.
Gabizon has since found the proof of correctness for the revised 2014 paper, but it was too late. https://github.com/arielgabizon/bctv/blob/master/bctv.pdf?fbclid=IwAR1wKtN8Ddh9IDuhIqd2O55MKQQG1z5tJB_t-X6ZgXYIPKzhbjSsIRCGv7o
This story demonstrates that the trusted setup ceremony, due to its complicacy, is error-prone and is very difficult to fix. I also lost confidence (a bit) in Zcash, as we do not know if they have already found a bug after the second ceremony and wait for the third one. I doubt the judgement that no one else could have found the bug. I think that even though a cryptographer was needed for that, the place to search was very clear: it is a lemma without a proof.
Let us see how it goes.
Electric Coin Company
Zcash Counterfeiting Vulnerability Successfully Remediated
Eleven months ago we discovered a counterfeiting vulnerability in the cryptography underlying some kinds of zero-knowledge proofs. This post provides details on the vulnerability, how we fixed it and…
Real Crypto via @like
SboxGate
Leo Perrin has just published a paper [1] with new reverse-engineering results on the Sbox used in recent Russian cipher and hash function. Such primitives, like AES and SHA-3, alternate linear and nonlinear layers to achieve confusion and diffusion, and the nonlinear layer is usually a bytewise application of the same nonlinear transformation, called the S-box. The AES Sbox is based on the inversion in GF(256).
The Russian Sbox was introduced in 2012 with no design rationale except some mentions of random trials. In 2016, Perrin et al. identified a structure inside the Sbox, showing it was unlikely to be randomly chosen, and in the two follow-up papers (2017, 2019) finally discovered a structure which resembles a discrete logarithm in GF(256) with some modifications. Whereas the logarithm as a non-linear transformation poses no threat to the knowledge of cryptanalysts, we now know that the Russian Agency lied that no structure was used in the Sbox [3]. Perrin calls [2] for the exclusion of the designs using this Sbox from ISO and RFC standards, or at least for the investigation. I agree with that.
Perrin et al. also found in 2017 [4] that the Sbox used in the Belorussian standard is similar to the Russian one, whereas for the former the design criteria are partly known [5], and its designers later published two papers about building Sboxes out of the exponentiation in GF(256). Indeed, the Belorussian Sbox was found to be a simple composition of the exponentiation with an affine mapping [4]. This hinted at the logarithm in the Russian Sbox, because Perrin considers its inverse. If we use the direct Sbox, both would use exponentiation. One more link between both is that the nonlinearity is the same 102.
This story implies a guess that the Russians took the idea of the exponentiatial Sbox from the Belorussian standard and applied some tiny masking transformations atop to hide its structure. Apparently, these are not hiding enough.
[1] https://eprint.iacr.org/2019/092
[2] https://mailarchive.ietf.org/arch/msg/cfrg/4PmssKzCBsxTmLCieDgqD7Nynwg
[3] https://www.ruscrypto.ru/resource/archive/rc2013/files/03_shishkin.pdf
[4] https://tosc.iacr.org/index.php/ToSC/article/view/567/509
[5] http://elib.bsu.by/bitstream/123456789/24140/1/BelT.pdf
[6] http://elib.bsu.by/bitstream/123456789/24138/1/exps%28%D1%84%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D1%8F%D1%80-2%29.pdf
[7] https://eprint.iacr.org/2004/024.pdf
Leo Perrin has just published a paper [1] with new reverse-engineering results on the Sbox used in recent Russian cipher and hash function. Such primitives, like AES and SHA-3, alternate linear and nonlinear layers to achieve confusion and diffusion, and the nonlinear layer is usually a bytewise application of the same nonlinear transformation, called the S-box. The AES Sbox is based on the inversion in GF(256).
The Russian Sbox was introduced in 2012 with no design rationale except some mentions of random trials. In 2016, Perrin et al. identified a structure inside the Sbox, showing it was unlikely to be randomly chosen, and in the two follow-up papers (2017, 2019) finally discovered a structure which resembles a discrete logarithm in GF(256) with some modifications. Whereas the logarithm as a non-linear transformation poses no threat to the knowledge of cryptanalysts, we now know that the Russian Agency lied that no structure was used in the Sbox [3]. Perrin calls [2] for the exclusion of the designs using this Sbox from ISO and RFC standards, or at least for the investigation. I agree with that.
Perrin et al. also found in 2017 [4] that the Sbox used in the Belorussian standard is similar to the Russian one, whereas for the former the design criteria are partly known [5], and its designers later published two papers about building Sboxes out of the exponentiation in GF(256). Indeed, the Belorussian Sbox was found to be a simple composition of the exponentiation with an affine mapping [4]. This hinted at the logarithm in the Russian Sbox, because Perrin considers its inverse. If we use the direct Sbox, both would use exponentiation. One more link between both is that the nonlinearity is the same 102.
This story implies a guess that the Russians took the idea of the exponentiatial Sbox from the Belorussian standard and applied some tiny masking transformations atop to hide its structure. Apparently, these are not hiding enough.
[1] https://eprint.iacr.org/2019/092
[2] https://mailarchive.ietf.org/arch/msg/cfrg/4PmssKzCBsxTmLCieDgqD7Nynwg
[3] https://www.ruscrypto.ru/resource/archive/rc2013/files/03_shishkin.pdf
[4] https://tosc.iacr.org/index.php/ToSC/article/view/567/509
[5] http://elib.bsu.by/bitstream/123456789/24140/1/BelT.pdf
[6] http://elib.bsu.by/bitstream/123456789/24138/1/exps%28%D1%84%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D1%8F%D1%80-2%29.pdf
[7] https://eprint.iacr.org/2004/024.pdf
Real Crypto via @like
Real World Crypto 2019, Day 3-1 (Part 5)
26) https://youtu.be/W2thViwbEQQ?t=563 New finite field library Solinas in development. It is integrated with the Coq correctness checker to avoid overflows and other flaws, the code is thus less readable.
27) https://youtu.be/W2thViwbEQQ?t=1966 https://rwc.iacr.org/2019/slides/VerifiedVectorizedCrypto-Bhargavan.pdf Cryptographic code bugs are very dangerous, so a lot of effort is needed to eliminate most of them, and formal verification is not enough (works for small gadgets only). How to scale up? There exist proof-oriented languages such as F*, which generate reasonably fast C code. Authors suggest in the case of vectorized code to extract the generic part (like the Counter mode for block ciphers) and verify it manually, leaving other checks to automated tools.
28) https://youtu.be/W2thViwbEQQ?t=3746 https://rwc.iacr.org/2019/slides/srini.pdf Modern CPU architecture is a mess as many processes/data inside are shared by a number of different actors, leading to attacks such as Spectre/Meltdown. How to build a processor architecture that facilitates isolation and memory control? The idea is to use enclaves on many levels. There are some academic-designed open-source RISC processors such as Sanctum built in this philosophy.
29) https://youtu.be/5pkDq4sRWyQ?t=51 https://rwc.iacr.org/2019/slides/RWC-Raykova.pdf There is emerging need in the advanced crypto for privacy-preserving computations (ML, DB), multi-user data processing. In Google they run a lot of data mining/ML algorithms and show which kind of crypto is used to increase privacy.
30) https://youtu.be/5pkDq4sRWyQ?t=2079 https://rwc.iacr.org/2019/slides/lucy.pdf Story of practical deployment of secure multiparty aggregation of salary data in Boston in order to compute how less women earn than men.
31) https://youtu.be/5pkDq4sRWyQ?t=3654 https://rwc.iacr.org/2019/slides/Partisia_RWC_2019_final.pdf The guys developed a blockchained tailored for multiparty and threshold applications: multisig wallets, privacy-preserving analytics. They provide a lot of motivation reasons, but so far no significant applications.
26) https://youtu.be/W2thViwbEQQ?t=563 New finite field library Solinas in development. It is integrated with the Coq correctness checker to avoid overflows and other flaws, the code is thus less readable.
27) https://youtu.be/W2thViwbEQQ?t=1966 https://rwc.iacr.org/2019/slides/VerifiedVectorizedCrypto-Bhargavan.pdf Cryptographic code bugs are very dangerous, so a lot of effort is needed to eliminate most of them, and formal verification is not enough (works for small gadgets only). How to scale up? There exist proof-oriented languages such as F*, which generate reasonably fast C code. Authors suggest in the case of vectorized code to extract the generic part (like the Counter mode for block ciphers) and verify it manually, leaving other checks to automated tools.
28) https://youtu.be/W2thViwbEQQ?t=3746 https://rwc.iacr.org/2019/slides/srini.pdf Modern CPU architecture is a mess as many processes/data inside are shared by a number of different actors, leading to attacks such as Spectre/Meltdown. How to build a processor architecture that facilitates isolation and memory control? The idea is to use enclaves on many levels. There are some academic-designed open-source RISC processors such as Sanctum built in this philosophy.
29) https://youtu.be/5pkDq4sRWyQ?t=51 https://rwc.iacr.org/2019/slides/RWC-Raykova.pdf There is emerging need in the advanced crypto for privacy-preserving computations (ML, DB), multi-user data processing. In Google they run a lot of data mining/ML algorithms and show which kind of crypto is used to increase privacy.
30) https://youtu.be/5pkDq4sRWyQ?t=2079 https://rwc.iacr.org/2019/slides/lucy.pdf Story of practical deployment of secure multiparty aggregation of salary data in Boston in order to compute how less women earn than men.
31) https://youtu.be/5pkDq4sRWyQ?t=3654 https://rwc.iacr.org/2019/slides/Partisia_RWC_2019_final.pdf The guys developed a blockchained tailored for multiparty and threshold applications: multisig wallets, privacy-preserving analytics. They provide a lot of motivation reasons, but so far no significant applications.
YouTube
Real World Crypto 2019 - Day 3 - Session 1 - Morning - Part 1
Real World Crypto January 11, 2019 meeting at the San Jose Marriott. This is day 3 session 1 which goes from 9:00AM until 12:35PM
Real Crypto via @like
Some interesting recent preprints:
https://eprint.iacr.org/2019/142.pdf
How to combine many statements (commitment, computation, different groups etc.) into one single succinct SNARK proof, which is also faster to compute than separately.
https://eprint.iacr.org/2019/162.pdf
Blockchain that builds on several parallel blockchains with each block referring to different lanes simultaneously, and all hash functions are different.
https://eprint.iacr.org/2019/186.pdf
Formal treatment of Monero traceability: how many coins from the mix you have to guess, how to improve bounds, how to program clients for optimally private mixing.
https://eprint.iacr.org/2019/166.pdf
https://eprint.iacr.org/2019/205.pdf
How to build verifiable delay functions (VDF) on elliptic curves: let one supersingular curve be created from another using a backdoored morphism, and the computation is to compute its inverse on some input. The backdoor requires a trusted setup, like in some RSA-based VDF.
https://eprint.iacr.org/2019/269.pdf
https://eprint.iacr.org/2019/261.pdf
Two papers on the same topic: aggregetable multisignatures (like BLS) where signers can irreversibly update their keys so that the keys used for signing can be one-time and deleted. Once a key is leaked, the signatures from its predecessor remain secure.
https://eprint.iacr.org/2019/251.pdf
Consensus algorithm that solves the problem of adaptively corrupting adversaries, at polylogarithmic communication cost.
https://eprint.iacr.org/2019/188.pdf
Verifiable computation on secret-shared or distributed input
https://eprint.iacr.org/2019/142.pdf
How to combine many statements (commitment, computation, different groups etc.) into one single succinct SNARK proof, which is also faster to compute than separately.
https://eprint.iacr.org/2019/162.pdf
Blockchain that builds on several parallel blockchains with each block referring to different lanes simultaneously, and all hash functions are different.
https://eprint.iacr.org/2019/186.pdf
Formal treatment of Monero traceability: how many coins from the mix you have to guess, how to improve bounds, how to program clients for optimally private mixing.
https://eprint.iacr.org/2019/166.pdf
https://eprint.iacr.org/2019/205.pdf
How to build verifiable delay functions (VDF) on elliptic curves: let one supersingular curve be created from another using a backdoored morphism, and the computation is to compute its inverse on some input. The backdoor requires a trusted setup, like in some RSA-based VDF.
https://eprint.iacr.org/2019/269.pdf
https://eprint.iacr.org/2019/261.pdf
Two papers on the same topic: aggregetable multisignatures (like BLS) where signers can irreversibly update their keys so that the keys used for signing can be one-time and deleted. Once a key is leaked, the signatures from its predecessor remain secure.
https://eprint.iacr.org/2019/251.pdf
Consensus algorithm that solves the problem of adaptively corrupting adversaries, at polylogarithmic communication cost.
https://eprint.iacr.org/2019/188.pdf
Verifiable computation on secret-shared or distributed input
Some interesting recent preprints
1) https://eprint.iacr.org/2019/352.pdf "SoK: A Taxonomy for Layer-2 Scalability Related Protocols for Cryptocurrencies"
Survey of Layer-2 solutions in cryptocurrencies: routing, channels, etc. A lot of problems to solve are stated, for those who wants a quick publication:)
2) https://eprint.iacr.org/2019/344.pdf Cryptanalysis of the hash function used in the IOTA blockchain. Never design your own crypto, including a hash function, hire a pro!:)
3) https://eprint.iacr.org/2019/317.pdf A new very interesting zero-knowledge proof system called Libra. It uses trusted setup, but only one for all circuits with bounded-size inputs. Its prover time seems to be smaller than in SNARKs and should grow slower (exactly linear in circuit size). Verification and proof size scale logarithmically with circuit size but linearly with its depth (!), so useful for shallow circuits only.
1) https://eprint.iacr.org/2019/352.pdf "SoK: A Taxonomy for Layer-2 Scalability Related Protocols for Cryptocurrencies"
Survey of Layer-2 solutions in cryptocurrencies: routing, channels, etc. A lot of problems to solve are stated, for those who wants a quick publication:)
2) https://eprint.iacr.org/2019/344.pdf Cryptanalysis of the hash function used in the IOTA blockchain. Never design your own crypto, including a hash function, hire a pro!:)
3) https://eprint.iacr.org/2019/317.pdf A new very interesting zero-knowledge proof system called Libra. It uses trusted setup, but only one for all circuits with bounded-size inputs. Its prover time seems to be smaller than in SNARKs and should grow slower (exactly linear in circuit size). Verification and proof size scale logarithmically with circuit size but linearly with its depth (!), so useful for shallow circuits only.
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.