Here we will review papers and blogposts, designs and attacks, competitions and conferences - that deal with the real-world applications of cryptography
A recent ePrint submission claims a combination of anonymous credential and reputation system. Here every credential holder is given a review token, which he can anonymously spend. A double spending can be traced and identity revealed. The credentials are based on the bilinear-map signature by Pointcheval-Sanders.
It does not look novel to me. A reputation system with an anonymous one-time review token can be implemented using a privacy-preserving cryptocurrency, like Zcash or Zcoin. Here a token would be a coin, which can not be doublespent as the ledger would prevent this, so this is even better than tracing in this paper. Also what looks weird is that the authors state that idemix does not include range proofs, whereas it does. https://eprint.iacr.org/2018/835
It does not look novel to me. A reputation system with an anonymous one-time review token can be implemented using a privacy-preserving cryptocurrency, like Zcash or Zcoin. Here a token would be a coin, which can not be doublespent as the ledger would prevent this, so this is even better than tracing in this paper. Also what looks weird is that the authors state that idemix does not include range proofs, whereas it does. https://eprint.iacr.org/2018/835
ASIACRYPT 2018 Accepted Papers. Part 1:
1) "New Instantiations of the CRYPTO 2017 Masking Schemes" https://eprint.iacr.org/2018/492.pdf
To protect a multiplication operation from side-channel leakage, we introduce masks. Apparently the proper mask generation is difficult and the authors show how to do it for high number of shares. A lot of matrix playing in the paper, and note the use of Schwartz-Zippel lemma, which occurs frequently now (cf. Groth's SNARKs). #side-channels
2) "Pattern Matching on Encrypted Streams" https://eprint.iacr.org/2017/148.pdf
Not only normal words but patterns like (almost) regular expressions can be searched in an encrypted text. This comes at a cost of large public key and ciphertext growth, but it may worth it. The idea is to encode all words in the plaintext as powers of some generator, and then use pairings to confirm matching. #searchable-encryption
3) "Revisiting Key-alternating Feistel Ciphers for Shorter Keys and Multi-user Security" https://eprint.iacr.org/2018/816.pdf
Just another theoretical result on Feistels.
4) "Practical attacks against the Walnut digital signature scheme" https://eprint.iacr.org/2018/318.pdf
A full break of a post-quantum signature proposal, which relies on non-commutative groups (somewhat similar to code-based signatures). Apparently can be broken easily with memoryless collision search algorithm
5) "Tweakable Block Ciphers Secure Beyond the Birthday Bound in the Ideal Cipher Model" https://eprint.iacr.org/2018/784.pdf
Yet another mode of operations for tweakable ciphers.
6) "On Multiparty Garbling of Arithmetic Circuits" https://eprint.iacr.org/2017/1186.pdf
An improvement in garbled circuits (needed for MPC)
1) "New Instantiations of the CRYPTO 2017 Masking Schemes" https://eprint.iacr.org/2018/492.pdf
To protect a multiplication operation from side-channel leakage, we introduce masks. Apparently the proper mask generation is difficult and the authors show how to do it for high number of shares. A lot of matrix playing in the paper, and note the use of Schwartz-Zippel lemma, which occurs frequently now (cf. Groth's SNARKs). #side-channels
2) "Pattern Matching on Encrypted Streams" https://eprint.iacr.org/2017/148.pdf
Not only normal words but patterns like (almost) regular expressions can be searched in an encrypted text. This comes at a cost of large public key and ciphertext growth, but it may worth it. The idea is to encode all words in the plaintext as powers of some generator, and then use pairings to confirm matching. #searchable-encryption
3) "Revisiting Key-alternating Feistel Ciphers for Shorter Keys and Multi-user Security" https://eprint.iacr.org/2018/816.pdf
Just another theoretical result on Feistels.
4) "Practical attacks against the Walnut digital signature scheme" https://eprint.iacr.org/2018/318.pdf
A full break of a post-quantum signature proposal, which relies on non-commutative groups (somewhat similar to code-based signatures). Apparently can be broken easily with memoryless collision search algorithm
5) "Tweakable Block Ciphers Secure Beyond the Birthday Bound in the Ideal Cipher Model" https://eprint.iacr.org/2018/784.pdf
Yet another mode of operations for tweakable ciphers.
6) "On Multiparty Garbling of Arithmetic Circuits" https://eprint.iacr.org/2017/1186.pdf
An improvement in garbled circuits (needed for MPC)
Google has added Ethereum to its data cloud. If they provide signed responses, we can use it for proving Ethereum events in other blockchains https://cloud.google.com/bigquery/
Google Cloud
BigQuery | AI data platform | EDW
BigQuery is the autonomous data and AI platform, automating the entire data life cycle so you can go from data to AI to action faster.
"Privacy Amplification by Iteration" https://ai.google/research/pubs/pub47118 FOCS'2018
Google researchers show that a sequence of privacy-preserving AI algorithms can increase the (differential) privacy with the same utility. It is more a privacy benchmark rather than a guideline how to compose algorithms, but still.
Google researchers show that a sequence of privacy-preserving AI algorithms can increase the (differential) privacy with the same utility. It is more a privacy benchmark rather than a guideline how to compose algorithms, but still.
Google Research
Privacy Amplification by Iteration – Google Research
Enigma blockchain project https://blog.enigma.co/
has just announced its testnet, and we decided to take a look at the project.
Apparently the idea is to extend Ethereum with decentralized data storage where data is stored in encrypted form. To process it in a contract, a distributed multiparty computation (!) is performed by a group of nodes. As one would expect, a majority of those nodes can disrupt the procedure, and a bit more of them can break confidentiality.
The assumption that such a majority is never assembled to process valuable data looks unlikely to me. Instead, one should expect that nodes opportunistically join the computing committee to form a critical majority and then decrypt inputs or outputs. Worse than for mining, such a cartel will remain unnoticed until you realize that the data was stolen. So the trust requirements for nodes in this blockchain is very high, not speaking of low performance of available MPC primitives, which will lessen the computing power of the blockchain.
But this is a far future plan anyway, as in the testnet the nodes are equipped with an SGX processor which already has all the necessary keys to encrypt and decrypt. I do not know why it is called testnet and not
has just announced its testnet, and we decided to take a look at the project.
Apparently the idea is to extend Ethereum with decentralized data storage where data is stored in encrypted form. To process it in a contract, a distributed multiparty computation (!) is performed by a group of nodes. As one would expect, a majority of those nodes can disrupt the procedure, and a bit more of them can break confidentiality.
The assumption that such a majority is never assembled to process valuable data looks unlikely to me. Instead, one should expect that nodes opportunistically join the computing committee to form a critical majority and then decrypt inputs or outputs. Worse than for mining, such a cartel will remain unnoticed until you realize that the data was stolen. So the trust requirements for nodes in this blockchain is very high, not speaking of low performance of available MPC primitives, which will lessen the computing power of the blockchain.
But this is a far future plan anyway, as in the testnet the nodes are equipped with an SGX processor which already has all the necessary keys to encrypt and decrypt. I do not know why it is called testnet and not
alpha, but let's see. The whitepaper is here https://enigma.co/enigma_full.pdfASIACRYPT 2018 accepted papers part 2
7) "Learning Strikes Again: the Case of the DRS Signature Scheme" https://eprint.iacr.org/2018/294.pdf
Full break of a post-quantum submission. Apparently in many lattice-based signature schemes signatures and messages are algebraically related with this relation being statistically detected and thus secret key deduced. The paper is a very nice collection of geometric tricks that lead to the cryptanalysis.
#lattices
8) "Unbounded Inner Product Functional Encryption from Bilinear Maps" https://eprint.iacr.org/2018/696.pdf
How to compute inner product over encrypted data if you do not know the key. Now it is possible for arbitrary long plaintexts, but no implementation.
#functional_encryption
9) "Practical Fully Secure Unrestricted Inner Product Functional Encryption modulo p" https://eprint.iacr.org/2018/791.pdf
The same topic as number 8
#functional_encryption
10) "Signatures with Flexible Public Key: Introducing Equivalence Classes for Public Keys" https://eprint.iacr.org/2018/191.pdf
How to construct a group of related public and private keys so that the relation is easy to assert but difficult to check. It is somewhat similar to the idea of hierarchical wallets (BIP32) in bitcoin and other currencies, where a new public key is the old one + a constant times the base point. It seems that this paper claims more privacy and less leakage in their approach, but it is not easy to figure out what are the advantages exactly. Maybe an original private key is more difficult to recover if the related one is leaked? A more careful reading is needed. The signatures in the paper are pairing-based so direct application to ECDSA-bound currencies might be problematic. However, better-than-existing ring and group signature schemes are presented, so maybe not for BIP but for Monero-like currencies this would work out.
#group_signature
11) "Compact Multi-Signatures for Smaller Blockchains" https://eprint.iacr.org/2018/483.pdf
Recently Boneh showed that the BLS multisignature is error-prone and needs a protection against rogue keys. Now the authors demonstrate a secure aggregated multisignature based on BLS with clear application to cryptocurrencies (e.g. for multisig addresses in Bitcoin). Note that all public keys must be known before aggregation, so arbitrary subsets are not allowed - so potential difficulty when exact set of signers is unknown. Still, a very useful primitive.
#multisignature #bitcoin
12) "How to Securely Compute with Noisy Leakage in Quasilinear Complexity" https://eprint.iacr.org/2017/929.pdf
Theoretical constructions for leakage-resilient schemes, that withstand side-channel leakage of high rate.
#side_channels
7) "Learning Strikes Again: the Case of the DRS Signature Scheme" https://eprint.iacr.org/2018/294.pdf
Full break of a post-quantum submission. Apparently in many lattice-based signature schemes signatures and messages are algebraically related with this relation being statistically detected and thus secret key deduced. The paper is a very nice collection of geometric tricks that lead to the cryptanalysis.
#lattices
8) "Unbounded Inner Product Functional Encryption from Bilinear Maps" https://eprint.iacr.org/2018/696.pdf
How to compute inner product over encrypted data if you do not know the key. Now it is possible for arbitrary long plaintexts, but no implementation.
#functional_encryption
9) "Practical Fully Secure Unrestricted Inner Product Functional Encryption modulo p" https://eprint.iacr.org/2018/791.pdf
The same topic as number 8
#functional_encryption
10) "Signatures with Flexible Public Key: Introducing Equivalence Classes for Public Keys" https://eprint.iacr.org/2018/191.pdf
How to construct a group of related public and private keys so that the relation is easy to assert but difficult to check. It is somewhat similar to the idea of hierarchical wallets (BIP32) in bitcoin and other currencies, where a new public key is the old one + a constant times the base point. It seems that this paper claims more privacy and less leakage in their approach, but it is not easy to figure out what are the advantages exactly. Maybe an original private key is more difficult to recover if the related one is leaked? A more careful reading is needed. The signatures in the paper are pairing-based so direct application to ECDSA-bound currencies might be problematic. However, better-than-existing ring and group signature schemes are presented, so maybe not for BIP but for Monero-like currencies this would work out.
#group_signature
11) "Compact Multi-Signatures for Smaller Blockchains" https://eprint.iacr.org/2018/483.pdf
Recently Boneh showed that the BLS multisignature is error-prone and needs a protection against rogue keys. Now the authors demonstrate a secure aggregated multisignature based on BLS with clear application to cryptocurrencies (e.g. for multisig addresses in Bitcoin). Note that all public keys must be known before aggregation, so arbitrary subsets are not allowed - so potential difficulty when exact set of signers is unknown. Still, a very useful primitive.
#multisignature #bitcoin
12) "How to Securely Compute with Noisy Leakage in Quasilinear Complexity" https://eprint.iacr.org/2017/929.pdf
Theoretical constructions for leakage-resilient schemes, that withstand side-channel leakage of high rate.
#side_channels
USENIX 2018 Crypto papers
1) "A Single-Decryption EM-Based Attack on OpenSSL’s Constant-Time Blinded RSA" https://www.usenix.org/sites/default/files/conference/protected-files/security18_slides_prvulovic.pdf
The constant-time implementation is shown to be vulnerable to Simple Power Analysis and thus secret exponent derivation just from a few bits. Constant time is not a bulletproof side-channel protection!
2) "DIZK A Distributed Zero Knowledge Proof System" https://www.usenix.org/sites/default/files/conference/protected-files/security18_slides_wu_0.pdf
How to distribute the computation (not MPC!) of a zkSNARK proof. Libsnark can process millions of gates, whereas this system can do billions! Very promising for some ICO :)
3) "Arbitrum: Scalable, private smart contracts" https://www.usenix.org/system/files/conference/usenixsecurity18/sec18-kalodner.pdf
It is not zkSNARKs on Ethereum. Instead, the authors suggest maintaining the current state hash of your chain/contract in a Virtual Machine, which has well-defined rules of state transitioning. Unless some of pre-designated maintainers challenge the new hash value, the VM operates smoothly and the parties agree on the state. In the case of a challenge the VM can be halted or forced to distribute its balance. Somewhat resembles Lightning channels and many other concepts, but seems to be a more powerful and standalone. The authors developed their own assembly and a standard library for VMs. Worth watching
1) "A Single-Decryption EM-Based Attack on OpenSSL’s Constant-Time Blinded RSA" https://www.usenix.org/sites/default/files/conference/protected-files/security18_slides_prvulovic.pdf
The constant-time implementation is shown to be vulnerable to Simple Power Analysis and thus secret exponent derivation just from a few bits. Constant time is not a bulletproof side-channel protection!
2) "DIZK A Distributed Zero Knowledge Proof System" https://www.usenix.org/sites/default/files/conference/protected-files/security18_slides_wu_0.pdf
How to distribute the computation (not MPC!) of a zkSNARK proof. Libsnark can process millions of gates, whereas this system can do billions! Very promising for some ICO :)
3) "Arbitrum: Scalable, private smart contracts" https://www.usenix.org/system/files/conference/usenixsecurity18/sec18-kalodner.pdf
It is not zkSNARKs on Ethereum. Instead, the authors suggest maintaining the current state hash of your chain/contract in a Virtual Machine, which has well-defined rules of state transitioning. Unless some of pre-designated maintainers challenge the new hash value, the VM operates smoothly and the parties agree on the state. In the case of a challenge the VM can be halted or forced to distribute its balance. Somewhat resembles Lightning channels and many other concepts, but seems to be a more powerful and standalone. The authors developed their own assembly and a standard library for VMs. Worth watching
"Bulletproofs: Short Proofs for Confidential Transactions and More"
https://eprint.iacr.org/2017/1066.pdf and IEEE S&P 2018
For quite some time proving computation in zero knowledge needed pairings because when you compute z = x*y and commit to z, x, and y separately it is very difficult to prove that g^z = (g^x)^y without revealing y. With pairings you have e(g^x,g^y)= e(g,g)^(xy) and there are SNARKs that exploit this property. Now Bulletproofs shows that it is apparently possible to prove the same without resorting to pairings. In the meanwhile, a trusted setup is not needed either.
The paper has two main ideas, though the second one is more opaque. The first idea is to reduce a range proof or an arithmetic circuit proof to an inner product argument, concretely proving that for some P you know A,B, c such that P = (X^A)(Y^B)z^c, where A,B are integer vectors, X,Y are group vectors, and c = <A,B> (inner product). Section 3 contains a nice chain of derivations that show how to make such proofs using the proofs for shorter vectors, and finally get the result by recursion. However, the resulting argument is not zero-knowledge.
The more interesting part comes in the last parts of Sections 4 and 5 where for range proofs and circuit proofs the authors show how to get a zero-knowledge proof from the above. After the recursion boils down to single-element vectors, we consider degree-2 polynomials with coefficients from these vectors, and evaluate them on a verifier-given point. Again, since the vectors are short, we can replace the Verifier with Fiat-Shamir and still get the proofs of reasonable size.
After all that we are left with range and circuit proofs of logarithmic (in length) complexity for all parties in both time and memory. Only discrete-log assumptions are needed, and the setup only requires generators without discrete-log relations among them.
The technique is great but I am sure we will see improvements. For circuits it remains to see which hash function delivers the smallest and fast-to-verify proof. Since the circuits operate in a prime field just as SNARKs, such a hash function will probably suit both worlds.
https://eprint.iacr.org/2017/1066.pdf and IEEE S&P 2018
For quite some time proving computation in zero knowledge needed pairings because when you compute z = x*y and commit to z, x, and y separately it is very difficult to prove that g^z = (g^x)^y without revealing y. With pairings you have e(g^x,g^y)= e(g,g)^(xy) and there are SNARKs that exploit this property. Now Bulletproofs shows that it is apparently possible to prove the same without resorting to pairings. In the meanwhile, a trusted setup is not needed either.
The paper has two main ideas, though the second one is more opaque. The first idea is to reduce a range proof or an arithmetic circuit proof to an inner product argument, concretely proving that for some P you know A,B, c such that P = (X^A)(Y^B)z^c, where A,B are integer vectors, X,Y are group vectors, and c = <A,B> (inner product). Section 3 contains a nice chain of derivations that show how to make such proofs using the proofs for shorter vectors, and finally get the result by recursion. However, the resulting argument is not zero-knowledge.
The more interesting part comes in the last parts of Sections 4 and 5 where for range proofs and circuit proofs the authors show how to get a zero-knowledge proof from the above. After the recursion boils down to single-element vectors, we consider degree-2 polynomials with coefficients from these vectors, and evaluate them on a verifier-given point. Again, since the vectors are short, we can replace the Verifier with Fiat-Shamir and still get the proofs of reasonable size.
After all that we are left with range and circuit proofs of logarithmic (in length) complexity for all parties in both time and memory. Only discrete-log assumptions are needed, and the setup only requires generators without discrete-log relations among them.
The technique is great but I am sure we will see improvements. For circuits it remains to see which hash function delivers the smallest and fast-to-verify proof. Since the circuits operate in a prime field just as SNARKs, such a hash function will probably suit both worlds.
Algorand: Scaling Byzantine Agreements for Cryptocurrencies
https://people.csail.mit.edu/nickolai/papers/gilad-algorand-eprint.pdf
There were a few Algorand papers; the first one by two authors describes quite a different version of Algorand with (seemingly) stronger claims and simpler algorithm.
The most important novelty of Algorand is its consensus, as the rest looks similar to Bitcoin. The consensus is Proof-of-Stake, where the probability to create a new block is proportional to party's wealth. As usual, not every public key participates in the block selection; moreover, those who do can step aside in the middle. There are alternatives: Ouroboros, SnowWhite, and Casper (some will be reviewed as well).
The main problem the PoS algorithms face is how to select a leader who proposes blocks so that the result can not be influenced by an adversary who joins at the last moment. There exist distributed key generation protocols and their derivatives, where m parties participate and exchange messages. If m/2+1 out of m parties are honest, all of them can reconstruct a collectively generated key. However, there are still some technical difficulties to overcome, which the Algorand designers claim to solve as follows.
First, Algorand selects a committee using a so-called Verifiable Random Function (VRF), such that each user can check and prove in zero-knowledge if he is in the committee and what his priority is, but he can not check that for other users (that's crucial). This is called sortition, but its straightforward implementation is still vulnerable to adversarial guessing. Algorand has to refresh the seed for VRF and use it only after a certain delay. Note that the sortition provides only a weak guarantee that the selected committee has enough honest nodes. For example, when honest users possess 80% of wealth, as many as 2000 members of committee are needed to ensure the majority for the next step, and this happens with probability 2^(-30) - which is not so low for me.
At the next step the committee decides on a block in the BFT-like fashion. In the normal situation the most prioritized committee member suggests a block, and everyone agrees, but when the leader is not available or there are conflicting ones, or even worse the network malfunctions, then the procedure gets much more involved. For example there is an option when an empty block is suggested. There are again some heuristically chosen parameters to prevent that from happening, but we do not know the behavior under a real attack. Once finalized, the block can not be reverted but it is a common BFT property.
The authors' benchmarking shows that Algorand can handle up to 50K users (the number of different IPs is much smaller though) with latency of under a minute and block size of a few MBytes. This is bigger than in the wild Ethereum but is comparable to the permissioned (Proof-of-Authority) Ethereum.
To summarize, the algorithm has some novelties and interesting performance, but it remains to see how it behaves under active attacks.
https://people.csail.mit.edu/nickolai/papers/gilad-algorand-eprint.pdf
There were a few Algorand papers; the first one by two authors describes quite a different version of Algorand with (seemingly) stronger claims and simpler algorithm.
The most important novelty of Algorand is its consensus, as the rest looks similar to Bitcoin. The consensus is Proof-of-Stake, where the probability to create a new block is proportional to party's wealth. As usual, not every public key participates in the block selection; moreover, those who do can step aside in the middle. There are alternatives: Ouroboros, SnowWhite, and Casper (some will be reviewed as well).
The main problem the PoS algorithms face is how to select a leader who proposes blocks so that the result can not be influenced by an adversary who joins at the last moment. There exist distributed key generation protocols and their derivatives, where m parties participate and exchange messages. If m/2+1 out of m parties are honest, all of them can reconstruct a collectively generated key. However, there are still some technical difficulties to overcome, which the Algorand designers claim to solve as follows.
First, Algorand selects a committee using a so-called Verifiable Random Function (VRF), such that each user can check and prove in zero-knowledge if he is in the committee and what his priority is, but he can not check that for other users (that's crucial). This is called sortition, but its straightforward implementation is still vulnerable to adversarial guessing. Algorand has to refresh the seed for VRF and use it only after a certain delay. Note that the sortition provides only a weak guarantee that the selected committee has enough honest nodes. For example, when honest users possess 80% of wealth, as many as 2000 members of committee are needed to ensure the majority for the next step, and this happens with probability 2^(-30) - which is not so low for me.
At the next step the committee decides on a block in the BFT-like fashion. In the normal situation the most prioritized committee member suggests a block, and everyone agrees, but when the leader is not available or there are conflicting ones, or even worse the network malfunctions, then the procedure gets much more involved. For example there is an option when an empty block is suggested. There are again some heuristically chosen parameters to prevent that from happening, but we do not know the behavior under a real attack. Once finalized, the block can not be reverted but it is a common BFT property.
The authors' benchmarking shows that Algorand can handle up to 50K users (the number of different IPs is much smaller though) with latency of under a minute and block size of a few MBytes. This is bigger than in the wild Ethereum but is comparable to the permissioned (Proof-of-Authority) Ethereum.
To summarize, the algorithm has some novelties and interesting performance, but it remains to see how it behaves under active attacks.
ASIACRYPT 2018 Accepted Papers Part 3:
13) "Hidden Shift Quantum Cryptanalysis and Implications" https://eprint.iacr.org/2018/432.pdf
When the quantum encryption oracle is available, the authors show how to break several symmetric schemes that use the modular addition (previous attacks exploited XORs). The complexity is practical, so never encrypt on a quantum computer.
14) "Secure Computation with Low Communication from Cross-checking" https://eprint.iacr.org/2018/216.pdf
Very efficient multiparty-computation protocols for generic circuits and a few (4 or 6) players: up to 1 bit per circuit gate. However, needs bigger preprocessing data.
15) "Programming the Demirci-Selcuk Meet-in-the-Middle Attack with Constraints" https://eprint.iacr.org/2018/813.pdf
The DS-MITM attack is a very powerful cryptanalysis method for AES-like ciphers, but the parameters (constraints) are non-trivial to find. This papers makes it automatic for some ciphers.
16) "Parameter-Hiding Order Revealing Encryption" https://eprint.iacr.org/2018/698.pdf
When you encrypt a database of integers and wants that the relative order of elements can be deduced from ciphertexts - it is ORE. However, for non-random data and practical-performance implementations of ORE - much more information can be obtained. This paper defines a parameter that can be guaranteely concealed even for such ORE
17) "Computing supersingular isogenies on Kummer surfaces" https://eprint.iacr.org/2018/850.pdf
Supersingular isogenies are candidates for quantum-secure public crypto with small keys and slow processing. This paper tries to make them faster
18) "Robustly Reusable Fuzzy Extractor from Standard Assumptions" https://eprint.iacr.org/2018/818.pdf
To compute a key from fingerprint, one can choose a codeword of a linear code as the key and difference to this codeword as a witness. Then applying a witness to a noisy reading of the same finger would bring to the vicinity of the same codeword. It is an example of a fuzzy extractor. Original designs could not derive many unrelated keys from the same source, and this paper provides a mechanism for that.
13) "Hidden Shift Quantum Cryptanalysis and Implications" https://eprint.iacr.org/2018/432.pdf
When the quantum encryption oracle is available, the authors show how to break several symmetric schemes that use the modular addition (previous attacks exploited XORs). The complexity is practical, so never encrypt on a quantum computer.
14) "Secure Computation with Low Communication from Cross-checking" https://eprint.iacr.org/2018/216.pdf
Very efficient multiparty-computation protocols for generic circuits and a few (4 or 6) players: up to 1 bit per circuit gate. However, needs bigger preprocessing data.
15) "Programming the Demirci-Selcuk Meet-in-the-Middle Attack with Constraints" https://eprint.iacr.org/2018/813.pdf
The DS-MITM attack is a very powerful cryptanalysis method for AES-like ciphers, but the parameters (constraints) are non-trivial to find. This papers makes it automatic for some ciphers.
16) "Parameter-Hiding Order Revealing Encryption" https://eprint.iacr.org/2018/698.pdf
When you encrypt a database of integers and wants that the relative order of elements can be deduced from ciphertexts - it is ORE. However, for non-random data and practical-performance implementations of ORE - much more information can be obtained. This paper defines a parameter that can be guaranteely concealed even for such ORE
17) "Computing supersingular isogenies on Kummer surfaces" https://eprint.iacr.org/2018/850.pdf
Supersingular isogenies are candidates for quantum-secure public crypto with small keys and slow processing. This paper tries to make them faster
18) "Robustly Reusable Fuzzy Extractor from Standard Assumptions" https://eprint.iacr.org/2018/818.pdf
To compute a key from fingerprint, one can choose a codeword of a linear code as the key and difference to this codeword as a witness. Then applying a witness to a noisy reading of the same finger would bring to the vicinity of the same codeword. It is an example of a fuzzy extractor. Original designs could not derive many unrelated keys from the same source, and this paper provides a mechanism for that.
ZK-STARKs
"Scalable, transparent, and post-quantum secure computational integrity" https://eprint.iacr.org/2018/046.pdf
STARKs are one of the most interesting concepts of year 2018. I do not say "interesting papers" because the paper is unfortunately not so interesting but is quite involving. It remains to see when an easier formal description appears in a follow-up paper, as currently "popular" explanations (such as Buterin's https://vitalik.ca/general/2017/11/09/starks_part_1.html ) are largely based on Ben-Sasson's video lectures
https://www.youtube.com/watch?v=9VuZvdxFZQo
https://www.youtube.com/watch?v=L7tZeO8ihcQ
which I too recommend for watching.
STARKs serve for zero-knowledge proof of program execution. Like SNARKs are based on the idea of representing a program code as a circuit with algebraic operations in nodes. A statement about a program execution can be written as a statement on polynomials. It is apparently easy to design a short interactive proof about statements like "this list is a set of values of a low degree function F" with a small assumption that the prover selects another low-degree polynomial G as part of the proof. The proof requires the prover to compute F on a much larger set and can be used in zero-knowledge if only queries to these extra values are allowed.
The difficulty lies in making the prover to use a low-degree G. In SNARKs this is done by using quadratic polynomials with trapdoors so that the statement XY=Z can be asserted using pairings over user-provided X and pre-committed Y as g^Y. In STARKs the prover instead creates a proof of low-degree, which is a major contribution by itself. During the proof the prover commits to the values of F and G via Merkle trees and provides selective openings. The authors' widely-advertised FRI algorithm of proximity proof works in these conditions. The proof size depends logarithmically on the circuit size, and thus the verifier's work, but for hash function circuits this all is within 1 MB size and 1 second time.
It is interesting to note that due to nature of proximity proof algorithm, the computation is done in not so large binary fields (e.g. 2^32), which contrasts to big prime fields of SNARKs. Consecutively, for zero-knowledge proofs of hash computations, the best hash functions are those native to these fields (or subfields). The AES-based hash function from the paper is insecure, but others with bigger S-boxes are worth looking at.
"Scalable, transparent, and post-quantum secure computational integrity" https://eprint.iacr.org/2018/046.pdf
STARKs are one of the most interesting concepts of year 2018. I do not say "interesting papers" because the paper is unfortunately not so interesting but is quite involving. It remains to see when an easier formal description appears in a follow-up paper, as currently "popular" explanations (such as Buterin's https://vitalik.ca/general/2017/11/09/starks_part_1.html ) are largely based on Ben-Sasson's video lectures
https://www.youtube.com/watch?v=9VuZvdxFZQo
https://www.youtube.com/watch?v=L7tZeO8ihcQ
which I too recommend for watching.
STARKs serve for zero-knowledge proof of program execution. Like SNARKs are based on the idea of representing a program code as a circuit with algebraic operations in nodes. A statement about a program execution can be written as a statement on polynomials. It is apparently easy to design a short interactive proof about statements like "this list is a set of values of a low degree function F" with a small assumption that the prover selects another low-degree polynomial G as part of the proof. The proof requires the prover to compute F on a much larger set and can be used in zero-knowledge if only queries to these extra values are allowed.
The difficulty lies in making the prover to use a low-degree G. In SNARKs this is done by using quadratic polynomials with trapdoors so that the statement XY=Z can be asserted using pairings over user-provided X and pre-committed Y as g^Y. In STARKs the prover instead creates a proof of low-degree, which is a major contribution by itself. During the proof the prover commits to the values of F and G via Merkle trees and provides selective openings. The authors' widely-advertised FRI algorithm of proximity proof works in these conditions. The proof size depends logarithmically on the circuit size, and thus the verifier's work, but for hash function circuits this all is within 1 MB size and 1 second time.
It is interesting to note that due to nature of proximity proof algorithm, the computation is done in not so large binary fields (e.g. 2^32), which contrasts to big prime fields of SNARKs. Consecutively, for zero-knowledge proofs of hash computations, the best hash functions are those native to these fields (or subfields). The AES-based hash function from the paper is insecure, but others with bigger S-boxes are worth looking at.
ASIACRYPT 2018 Accepted Papers Part 4
19) "Adaptively Simulation-Secure Attribute-Hiding Predicate Encryption"
not available yet
20) "A Framework for Achieving KDM-CCA Secure Public-Key Encryption" https://eprint.iacr.org/2018/845.pdf
How to secure a cryptosystem if an adversary can ask for encryption of secret keys.
21) "On the Statistical Leak of the GGH13 Multilinear Map and some Variants" https://eprint.iacr.org/2017/482.pdf
The multilinear maps were a long standig problem seemingly solved in 2013. Since then, a number of attacks have been proposed making the original proposal insecure. It is still in use as there are few alternatives. Many attacks result from statistical attacks on lattices, as lattices are crucial part of the MM design. This paper tries to quantify the statistical leak in many settings.
22) "Understanding and Constructing AKE via Double-key Key Encapsulation Mechanism" https://eprint.iacr.org/2018/817.pdf
AKE (authenticated key exchange) is a group of secure channel protocols where for each session a new (ephemeral) key pair is generated using the long-term key (which is common in secure messengers such as Signal, for example). This paper provides a formal treatment of this approach.
23) "Block Cipher Invariants as Eigenvectors of Correlation Matrices" https://eprint.iacr.org/2018/763.pdf
When round constants or their combination with round keys have low entropy, a state invariant can undergo quite many rounds. The paper shows how to express such invariants via correlation matrices. This does not lead to any significant new attack on well known ciphers, but is a good reminder to choose random constants when possible.
24) "Quantum Lattice Enumeration and Tweaking Discrete Pruning" https://eprint.iacr.org/2018/546.pdf
Lattice-based cryptography seemingly resist quantum computers which makes it promising for post-quantum NIST competition. However, quantum lattice attacks get better even though they remain exponential. This paper establishes new security parameters for some post-quantum candidates based on new attacks.
19) "Adaptively Simulation-Secure Attribute-Hiding Predicate Encryption"
not available yet
20) "A Framework for Achieving KDM-CCA Secure Public-Key Encryption" https://eprint.iacr.org/2018/845.pdf
How to secure a cryptosystem if an adversary can ask for encryption of secret keys.
21) "On the Statistical Leak of the GGH13 Multilinear Map and some Variants" https://eprint.iacr.org/2017/482.pdf
The multilinear maps were a long standig problem seemingly solved in 2013. Since then, a number of attacks have been proposed making the original proposal insecure. It is still in use as there are few alternatives. Many attacks result from statistical attacks on lattices, as lattices are crucial part of the MM design. This paper tries to quantify the statistical leak in many settings.
22) "Understanding and Constructing AKE via Double-key Key Encapsulation Mechanism" https://eprint.iacr.org/2018/817.pdf
AKE (authenticated key exchange) is a group of secure channel protocols where for each session a new (ephemeral) key pair is generated using the long-term key (which is common in secure messengers such as Signal, for example). This paper provides a formal treatment of this approach.
23) "Block Cipher Invariants as Eigenvectors of Correlation Matrices" https://eprint.iacr.org/2018/763.pdf
When round constants or their combination with round keys have low entropy, a state invariant can undergo quite many rounds. The paper shows how to express such invariants via correlation matrices. This does not lead to any significant new attack on well known ciphers, but is a good reminder to choose random constants when possible.
24) "Quantum Lattice Enumeration and Tweaking Discrete Pruning" https://eprint.iacr.org/2018/546.pdf
Lattice-based cryptography seemingly resist quantum computers which makes it promising for post-quantum NIST competition. However, quantum lattice attacks get better even though they remain exponential. This paper establishes new security parameters for some post-quantum candidates based on new attacks.