ASIACRYPT 2018 Part 7

37) "Quantum Algorithms for the k-xor Problem" Not avalaible yet. Is it about the generalized birthday problem?

38) "Concretely Efficient Large-Scale MPC with Active Security" https://eprint.iacr.org/2018/843.pdf
Shows that if certain number (more than one) of MPC participants is honest, the performance of known algorithms can be improved by a small factor.

39) "Short Variable Length Domain Extenders With Beyond Birthday Bound Security" https://eprint.iacr.org/2018/783.pdf
Based on N-bit blockcipher, create a mode that encrypts up to 2N bits with security beyond 2^(N/2).

40) "Decentralized Multi-Client Functional Encryption for Inner Product" https://eprint.iacr.org/2017/989.pdf
Again functional encryption (see paper 29) with similar results. Recall that FE is helpful to compute certain functions on the encrypted data, in this case the function is inner product and is helpful to compute, for example, weighted average of some encrypted tuples.

41) "Homomorphic Secret Sharing for Low Degree Polynomials" Not available yet.

42) "CSIDH: An Efficient Post-Quantum Commutative Group Action" https://eprint.iacr.org/2018/383.pdf
A new key agreement cryptosystem based on the problem of finding an explicit isogeny between two elliptic curves. Supposedly quantum-resistant, this method makes use of supersingular curves.

43) "Multi-Key Homomorphic Signatures Unforgeable under Insider Corruption" https://eprint.iacr.org/2016/834.pdf
Homomorphic Signatures are those where one can compute a signature over a function of already signed arguments. This paper suggests a design that withstands corrupted signers (who each sign its own input).

44) "On the Concrete Security of Goldreich’s Pseudorandom Generator" Not available yet.

45) "Cryptanalysis of MORUS" https://eprint.iacr.org/2018/464.pdf
Linear cryptanalysis of an authenticated encryption scheme Morus based on the rotational invariance of some components. Requires 2^152 data.

Our Memory-hard Proof of Work Equihash gains popularity. In the recent GPU miner publication I have found out that quite many cryptocurrencies are using it with different parameters: https://cryptomining-blog.com/10300-new-lolminer-0-5-amd-and-nvidia-opencl-multi-equihash-gpu-miner/

Note that Equihash-144/5 requires 2.2 GB, and Equihash-192/7 - 3GB. This is not a record: the Grin project has recently discussed using Equihash-108/3 with 7 GB memory requirements. https://www.grin-forum.org/t/proof-of-work-update/713

I believe this is due low spread of 8GB+ GPU. It will be also quite difficult to build an ASIC with 7 GB RAM, as it will be quite big. And by the time of the delivery one can switch for higher parameters.

The performance of these parameters should be reasonable. LolMiner claims 90 sol/sec for 144/5 on 1080ti, https://forum.bitcoingold.org/t/lolminer-0-6-alpha-preview-is-available-1080ti-89sol-s-1080-54-sol-s-vega-64-44sol-s/2447
so 108/3 should be at least 10 sol/s (2^27 entries in the 108/3 list vs 2^24 in the 144/5 list with more iterations in the latter)

ASIACRYPT 2018 Part 8
46) "State Separation for Code-Based Game-Playing Proofs" https://eprint.iacr.org/2018/306.pdf (early version)
A new framework for scheme security analysis.

47) "Two attacks on rank metric code-based schemes: RankSign and an Identity-Based-Encryption scheme" https://eprint.iacr.org/2018/339.pdf
Code-Based schemes are post-quantum candidates as decoding in certain metrics is NP-hard. However, the existing primitives have big keys and signatures. The paper shows that one of recent proposals can be broken because the codewords produced with recommended parameters have low weight.

48) "An efficient structural attack on NIST submission DAGS" https://eprint.iacr.org/2018/456.pdf
Another code-based scheme is broken, now the encryption one. The scheme instantiates McEliece cryptosystem with Srivastava codes, and, as typical for structured codes (cf. attacks on McEliece with Reed-Muller or Reed-Solomon), is broken for suggested parameters.

49) "Attacks and Countermeasures for White-box Designs" https://eprint.iacr.org/2018/049.pdf
White-box schemes obfuscate the secret key so that the entire encryption algorithm with the key can be published and neither the key nor a compact representation of the scheme can be found. This paper shows that the common masking technique (to protect from side channel analysis) does not increase the security level since the obfuscation by masking is weak.

50) "Improved (Almost) Tightly-Secure Simulation-Sound QA-NIZK with Applications" https://eprint.iacr.org/2018/849.pdf
A zero-knowledge argument system that delivers a public-key encryption in the strongest security model and is verifiable.

51) "Identity-based Encryption Tightly Secure under Chosen-ciphertext Attacks" https://eprint.iacr.org/2018/834.pdf
An IBE scheme in a weak security model (only one challenge ciphertext allowed for CCA) but whose security is very tightly reduced to the underlying assumption.

Threshold signatures allow you to split the private key into N parts and give them to N parties so that T-of-N guys can always create a signature. In some case a verifier can not even distinguish who the signers are. Threshold signatures have been proposed as variations of many popular schemes (for example, the BLS threshold signatures by Boldyreva), but
for quite some time they did not exist for ECDSA. As ECDSA is widely used in Bitcoin, Ethereum and many other blockchains, such a scheme would allow for more compact multisignature wallets, potentially indistinguishable from regular accounts.

I was quite surprised when learned that no threshold signature protocol exists for ECDSA with more than 2 parties. The problem was that the parties have to collectively exponentiate both to the secret and its inverse. Still, the two papers on exactly this subject have appeared at the ACM CCS 2018 a year ago, which I missed in the review. One is "Fast Multiparty Threshold ECDSA with Fast Trustless Setup" http://stevengoldfeder.com/papers/GG18.pdf and another "Fast Secure Multiparty ECDSA with Practical Distributed Key Generation and Applications to Cryptocurrency Custody" https://eprint.iacr.org/2018/987.pdf

The protocols are notably similar, even the trick of splitting a quadratic monomial in the exponent into a sum of monomials. However, the further implementations are different, so that the former paper performs better by a factor of magnitude or so. Both can finish within a few seconds with dozens of parties, but the problem is with the protocol. Currently it is 4-5 rounds of "interact_with_each_party-compute-broadcast" which will of course be nightmare for human multisig signers, but viable for machines. Startup idea for cold storage?

At the latest DevCon4 conference, Eli Ben-Sasson presented several notable improvements to ZK-STARKs.

The improvements were quite practical, as the proof generation time and size decreased. For certain amount of computation, it is cheaper to verify a STARK proof than the computation itself. Currently the threshold is about 100 (Pedersen) hashes. Therefore, even when the zero knowledge is not required (like scalability issues), STARKs can play a significant role. As I understand, removing zero knowledge does not bring much gain, but this can change.

The proof size for payment blockchains has decreased almost tenfold, from 500KB to 50KB. Bulletproofs proof (just the range proof) can do it in 1.5KB. The proof generation for Pedersen Merkle trees takes about 1 second and increases logarithmically with the number of layers.

It is important to note that the verifier runs part of the original computation, so the decrease in the computation (not necessarily the proof) will also reduce the verification time.

A new STARK-friendly hash function, Friday, has been presented, with quite small proof generation time but only 64-bit collision resistance. Our own hash function design (will talk about it later) seems to be more perspective.


Still, Zcash architects are hesitant to replace SNARKs with STARKs. This makes sense: for a big number of proofs the STARK size overhead is significant. It might be possible to prune the proofs by replacing them with metaproofs, but then the receipients must obtain more information from senders.

ASIACRYPT 2018 Part 9
52) "Simulatable Channels: Extended Security that is Universally Composable and Easier to Prove" https://eprint.iacr.org/2018/844.pdf
Cryptographic constructions often come with formal proofs, and there are several techniques to compose such proofs. One of them is simulation where the behaviour of a secret-possesing party is simulated by a machine without a secret. This paper shows how some secret-channel protocols can be proven secure in this paradigm.\

53) "On the Hardness of the Computational Ring-LWR Problem and its Applications" https://eprint.iacr.org/2018/536.pdf
Learning With Rounding (LWR) is an area potentially suitable for post-quantum cryptography as related problems have not been sped up with a quantum computer yet. The paper introduces some new security assumptions based on the hardness of LWR and puts certain post-quantum schemes into their context.

54) "Towards practical key exchange from ordinary isogeny graphs" https://eprint.iacr.org/2018/485.pdf
Isogeny-based protocols is another family of (potential) quantum-secure schemes, but so far all constructions were impractical. This paper makes significant performance improvements, but the parameter generation remains a complicated and open problem.

55) "SQL on Structurally-Encrypted Databases" https://eprint.iacr.org/2016/453.pdf
A rather old paper on how to encrypt a database so that some (but not all) relational algebra queries can be performed. The authors' approach leaks less data at the cost of supporting fewer queries compared to other approaches such as property-preserving encryption (PPE)

56) "Non-Interactive Secure Computation from One-Way Functions" https://eprint.iacr.org/2018/1020.pdf
Non-Interactive Secure Computation (NISC) is a family of MPC protocols where minimal interaction between parties is assumed. For example, to compute a function f(X,Y) the owner of X publishes some precomputation g(X), then the owner of Y interacts with it producing h(Y,g(X)), which allows the former to compute F(X,Y). This paper suggests a generic way to do that that uses only one-way functions and does not need oblivious transfer protocols.

57) "Arya: Nearly Linear-Time Zero-Knowledge Proofs for Correct Program Execution" https://eprint.iacr.org/2018/380.pdf
A new proof system where prover's overhead is minimal (linear of the program size, compared to superlinear in other systems) -- at the cost of quite high verification and communication costs, which attribute to the square root of program size.

ASIACRYPT 2018 Part 10
58) "Building Quantum-One-Way Functions from Block Ciphers: Davies-Meyer and Merkle-Damgard Constructions" https://eprint.iacr.org/2018/841.pdf
Recently several block ciphers were found broken if the adversary can query them on a quantum encryptor (i.e. get a quantum superposition of ciphertexts). As many hash functions are built from block ciphers, it is an open question if collision or preimage resistance suffers in this setting. The authors show that the well-known Merkle-Damgard scheme provides a quantum-secure one-way hash function in the ideal cipher model if the compression function is built from this ideal cipher via Davies-Meyer. Nice positive result in the post quantum security.

59) "A Universally Composable Framework for the Privacy of Email Ecosystems" https://eprint.iacr.org/2018/848.pdf
This paper suggests a formal approach for security evaluation of email systems w.r.t. anonymity. The authors show that some mixing network does provide necessary security guarantees if users are similarly active.

60) "Security of the Blockchain against Long Delay Attack" https://eprint.iacr.org/2018/800.pdf
Previous research showed that Proof of Work is a secure consensus method assuming certain percentage of honest mining power and limit on the message delay an adversary can cause. This paper shows that PoW is still secure if message delay is arbitrarily high but only a fraction of messages can be delayed.

61) "ZCZ – Achieving n-bit SPRP Security with a Minimal Number of Tweakable-block-cipher Calls" https://eprint.iacr.org/2018/819.pdf
Certain recent authenticated encryption modes use a tweakable block cipher (TBC), where public constants (tweaks) are mixed into the secret key. It has been unknown how many TBC calls per message block is necessary for security. The paper presents a new construction with ratio 1.5 while also claiming an attack on any design with ratio 1.5-eps.

62) "New MILP Modeling: Improved Conditional Cube Attacks on Keccak-based Constructions" https://eprint.iacr.org/2017/1030.pdf
Cube attack is a key recovery technique for bit-oriented symmetric primitives of low degree such as Keccak-based MACs, where a hypercube of plaintexts is encrypted. The authors present new results by attacking up to 9 rounds of KMAC256 (2^147 time) and some reduced versions of AE designs Keyak and Ketje. Improvements come from better use of integer linear programming to find such cubes.

63) "Tight Private Circuits: Achieving Probing Security with the Least Refreshing" https://eprint.iacr.org/2018/439.pdf
Masking is a technique to add and remove noise during the computation with a secret, which defeats some side-channel attacks. The paper presents a tool that analyzes and optimizes the mask layout assuming certain number of probing positions.

64) "More is Less: Perfectly Secure Oblivious Algorithms in the Multi-Server Setting?" https://eprint.iacr.org/2018/851.pdf
A counterpart to paper 35, which deals with 2-server oblivious RAM. Here 3 servers are considered, and the improvement over 1 server is logarithmic: log^2 N bandwidth blowup compared to log^3 N for single server, when N elements are stored. Note though that similar improvements have already been achieved with weaker security requirements.

65) "Leakage-Resilient Cryptography from Puncturable Primitives and Obfuscation" https://eprint.iacr.org/2018/781.pdf
Adds new notions and a framework to construct leakage-resilient schemes: those that remain secure despite leaked functions on intermediate variables. Many reductionist results.

Some interesting recent preprints

1) "Parallel Chains: Improving Throughput and Latency of Blockchain Protocols via Parallel Composition" https://eprint.iacr.org/2018/1119.pdf
If you execute the same blockchain in multiple instances simultaneously without synchrony, but with dumping a combined output of all to some another ledger - what can you get? The authors suggest a generic analysis framework + some throughput and latency results for already existing schemes. This applies to sharding and duplication, to PoW and PoS. Should be helpful for blockchain designers.

2) "Proof-of-Stake Protocols for Privacy-Aware Blockchains" https://eprint.iacr.org/2018/1105.pdf

The paper addresses the following problem. In protocols like Proof-of-Stake the block generation is awarded to the winner in a kind of lottery, who has to commit (bid) some coins in order to participate. Even though the bid amount affects the winning probability, one might want to both the exact amount and the identity of a winner. The latter is defined as unlinkability between the set of bidder accounts and the identifier of the consensus participant (IP address, consensus-specific public key or something else).

We also assume that the win event does not depend on other's actions, only on the data supplied by the bidder. This simplifies a proof, but requires some control to prevent grinding attack, i.e. quickly searching for the data that would yield a win - before the actual bidding.

Depending on the payment protocol in the blockchain, this requirement can be satisfied differently. My intution says that in the privacy-preserving payment protocol, like Zcash, all bidders may first call a verifiable random function (VRF) to get a random value, then privately transact to a certain address with the VRF output in the attachment, and finally anonymously present a proof-of-bid. If the bid wins, they can accompany it with a proof-of-win, referring to the VRF output included in the bid transaction. The complexity of the latter depends on the winning function, but, in contrast to this paper, I think that SNARK/STARK friendly winning functions are easy to create.

When payments are public we need to additionally break the link between the bid and the winner. The straightforward, for me, solution, would be to effectively emulate the Zcash data structure by keeping all bids in a Merkle tree and by separating bidding accounts from consensus participants. The authors follow pretty much this way by not specifying the data structure for bids. They additionally design a new type of VRF that permit anonymous verification without SNARKs/STARKs. However, since the rest of the method requires such a technique to increase performance, I doubt it is essential.

Quisquis: A New Design for Anonymous Cryptocurrencies
https://eprint.iacr.org/2018/990.pdf

In this recent preprint the authors suggest a new anonymous cryptocurrency, which is most similar to Monero and Coinjoin-based Dash. Recall that in Monero a coin spender can hide in an anonymity set of arbitrary size, but the transaction size grows linearly with anonymity level. Anonymity in Monero is provided by ring signatures, but range proofs must be also provided in order to every coin to have not so large positive value. Recently the range proofs in Monero were upgraded to Bulletproofs, and the transaction for the anonymity set of 7 senders is about 2.5 KB.

This long introduction was needed to compare Quisquis to Monero, which (even though I am not superexcited with Monero either) does not yield an obvious winner. In Quisquis a sender not only hides in an anonymity set, but also is able to modify the keys from the anonymity set so that they are still spendable by legitimate owners. This allows to prune spent transactions thus reducing the memory and hard drive requirements for the nodes. Also Quisquis makes a wider use of Bulletproofs for the zero-knowledge proof of correct spending. These two improvements seem to constitute the main contribution of this cryptocurrency, though maybe the anonymity model also is somewhat novel.

From the performance perspective, the transactions are at least 13 KB long for the anonymity set of 16 (which looks bigger than in Monero with Bulletproofs), and generation/verification take about the same time. So my conclusion is that the improvement is incremental and largely consists of Bulletproofs for other ZK statements.

Real World Crypto 2019, in Stanford
Part 1

1) https://youtu.be/9xePC0Tyeuc?t=975
New protocol suggested MLS (Message Layer Security). It should be a common framework for secure messaging systems, which could share code and, most importantly, its security properties. Desired functionality in contrast to TLS: work in groups (multiple users, multiple devices per user), long sessions. Security properties: forward secrecy (conversations before a compromise occurs) and post-compromise security (next sessions remain secure). Working group is established. Apparently the group scalability requirement is very difficult to achieve.

2) https://youtu.be/9xePC0Tyeuc?t=2918 How to deal with abusive messages in social networks if end-to-end encryption is used, so the transport provider does not know the content of message. The idea is to use a special kind of encryption that allows verification of abuse claims without security violation and false reporting. Existing system in Facebook uses symmetric crypto (HMAC) so this does not scale nice (but does other bad things alongside). The authors suggest a better scheme, also symmetric, very fast (one pass over data). My question: maybe add public verification? with STARKs?

3) https://youtu.be/9xePC0Tyeuc?t=4384 Now about snapchats, where snaps are quickly deleted. The problem is that current solutions are too bound to a device. The authors suggest exchanging session keys at the time of device/user change.

4) https://youtu.be/AyeuIfGjBg4?t=1211 Why (and how) cryptographers should work with politicians. The guys just share their experience.

5) https://youtu.be/AyeuIfGjBg4?t=2527 Matt Blaze talks about US elections, then on possible attacks on existing (or recent) voting tech: software, hardware, etc.. Cryptography does not help much. Need to do more audits, better design, etc.

6) https://youtu.be/AyeuIfGjBg4?t=4949 Levchin prize is awarded to Mihir Bellare (author of hundreds of design/analysis papers, HMAC, random oracle model, etc.) and Eric Rescorla (development and standardization of TLS 1.3)

Real World Crypto 2019
Part 2 (Day 1 Afternoon)

7) https://youtu.be/xADRUcTf-9A?t=967 Noise protocols: framework for secure messaging. It is just a language, not a protocol. There is an automatic tool (NoiseExplorer) to check the security goals: authentication, confidentiality, identity hiding, all with different levels. Authors show a number of simple protocols and how the tool evaluates them. Looks very useful for protocol developers!

8) https://youtu.be/xADRUcTf-9A?t=2526 Google suggests Application Layer Transport Security (ALTS), which aims to secure RPC calls. Authentication is based on providing identities to all network entities and handling authorization policy accordingly.

9) https://youtu.be/xADRUcTf-9A?t=4066 The infamous password-based security suffers from many problems, including a server seeing passwords in cleartext. PAKE protocols allow password-based authentication without password sending, but they have not used salt so are vulnerable to precomputation attacks. The new protocol OPAQUE eliminates the precomputation attack. Integratable with TLS 1.3.

10) https://youtu.be/xADRUcTf-9A?t=5630 How to store on server a list of most popular passwords so that 1) dynamically track if a new popular password appears and prohibit it (2) prevent a malicious observer to learn passwords of specific users just by looking at the list at dynamics.

11) https://youtu.be/xADRUcTf-9A?t=8814 How US defence agency (DARPA) works with crypto. Topics include computation on encrypted data, privacy-aware systems (Brandeis), obfuscation, secure messaging. In Brandeis they try to operate on encrypted and/or private data without breaking privacy (too much). The talk is quite generic, but mentions a number of advanced techniques like differential privacy.

12) https://youtu.be/xADRUcTf-9A?t=9737 The talk is about joint journalist access to high-value data, which is threshold encrypted so that at least a certain number of users can access the data, and they must do it together. The devil lies in the organization of sharing the secrets needed for access: managing losses, timeouts, adversaries, etc. Sometimes a special ceremony is needed (like in Zcash) The authors suggest a framework for that called "Sunder".

13) https://youtu.be/xADRUcTf-9A?t=10612 How to make the software development more secure (from cryptographic points of view). THe authors studied the genesis of 800 vulnerabilities, classified them, suggested solutions (quite straightforward).

Real World Crypto 2019
Part 3 (Day 2 Morning)

14) https://youtu.be/xwIEjVRvVXU?t=3 How Amazon handles encryption given its AWS keeps trillions of files? Their key service (KMS) interacts with HSMs and obtains mid-living keys for encryption and decryption. A lot of dirty details on how to avoid key collisions and how to use the encryption API in general.

15) https://youtu.be/xwIEjVRvVXU?t=1621 In VISA, when you buy from a merchant, a transaction travels across some payment network that includes a merchant bank and a customer bank. Whenever PIN or CVV check is involved, they go alongside with a transaction to a certain verifier. On its way there are a lot of HSMs, as the encryption is symmetric (3DES) and the keys must be shared. They need proxy reencryption to transfer messages across many hops and mitigate disconnects. All this a bit reminds the envelope encryption in TOR (where there are several layers of stream encryption). VISA handles on average 5000 transactions per second.

16) https://youtu.be/xwIEjVRvVXU?t=3410 If we have teams to manage and keys to handle, can we decentralize it? Example: managing Slack teams with many devices per user, can we avoid email registration? The authors suggest a system (KeyBase) that handles team keys that rotate with every team change. Every user builds a chain (or tree) of his messages about new devices. Revocation is apparently easy. Claim to scale up to 2K-teams

17) https://youtu.be/xwIEjVRvVXU?t=7348 A tutorial talk about side channel attacks (Riscure is a company that does this (defense against) commercially. Discusses tools, devices; presents examples. Apparently there are technical problems of automating analysis of an unknown device (where to probe, how to probe, how to align readings etc.). From the attack perspective, the old Correlation Power Analysis is still very powerful and often is hard to beat. Devices that pass all these attacks/tools are certified. Also, very interesting new approach: use machine learning in place of signal analysis (alignment->D/SPA->key ranking).

18) https://youtu.be/xwIEjVRvVXU?t=9210 Google suggests new API for cryptographic primitives, explicitly for non-crypto developers. Goals: security (hard to misuse) and usability (easy to use). Several examples, particularly in authenticated encryption. Currently available for Java, C++, Objective C.

I have not found anything particularly interesting in Lightning talks...

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.

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.

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!

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.

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

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.

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

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.

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