## An attendee’s report: crypto means Crypto (2019)

Steven Galbraith, who maintains this blog, has been inviting me to write a blog post on several conferences for quite some time, and I’ve consistently postponed accepting the invitations for, well, too long, so here you go. Yet, the reader is kindly asked not to expect a masterpiece of literature in this very first attempt of mine at blogging (in other words: read on at your own peril; you won’t be able to unread it later).

Continuing the unavoidable trend for large conferences, Crypto 2019 offered two parallel tracks, and understandably I’ll report on but a few presentations of the one specific track I happened to choose at each segment of the program (I tried to vary my choice of track for every session block, though).

And yet, the dichotomy of parallel sessions got me into existential anguish (of sorts) right from the start for being unable to attend both. The very first parallel pair was on lattice-based ZK proofs on the one hand, and on certain symmetric constructions on the other. I chose symmetric constructions.
I found the notion of secure PRNGs that lack a random seed, introduced by S. Coretti et al. (“Seedless Fruit is the Sweetest: Random Number Generation, Revisited”), particularly intriguing (to say the least). The authors bypass the impossibility of attaining this by compromising: yes, the entropy source is still implicitly there despite the name, but instead of modeling the extraction procedure by feeding the PRNG a randomness seed, it assumes the underlying random oracle itself (called the “monolithic extractor”) is picked uniformly at random all at once. Building on this idea, the authors offer provably secure constructions and show how some existing ones are insecure. Unfortunately, delays between clicks and slide changes, coupled with a few other issues (including, I should say, a somewhat inordinate number of jokes), made it impossible to cover the extensive slide set in the allotted time… and to check if I got the ideas right.
My session choice meant I couldn’t attend the simultaneous presentation of the equally intriguing solution to the problem of constructing a non-interactive zero-knowledge (NIZK) proof system from the LWE assumption for any NP language, discovered by C. Peikert and S. Shiehian and described in their paper “Noninteractive Zero Knowledge for NP from (Plain) Learning with Errors”. That was a pity, but it was somewhat compensated by the work “Nonces Are Noticed: AEAD Revisited” by M. Bellare, Ruth Ng, and B. Tackmann. This work reveals an enormous gap between the usual theory of nonce-based schemes and the actual (sometimes even standardized) usage of those schemes in practice: nonces become a kind of metadata that can reveal a surprising amount of information about the users or devices originating them. Quite creepy, but the authors address it by providing new notions and solutions whereby the nonce is hidden as well, and also resist nonce misuse.

As usual, there was a session on FHE. The work “On the Plausibility of Fully Homomorphic Encryption for RAMs” by A. Hamlin et al., the authors tackle the problem of hiding the sequence of memory addresses that are accessed when doing some processing on a large database. Using their notion of rewindable oblivious RAM, they obtain a preliminary single-hop scheme where the multiplicative running time overhead is $O(\mathrm{polylog} N)$, where $N$ is the database size.
In the same session, Sri A. K. Thyagarajan talked about his joint work with G. Malavolta on “Homomorphic Time-Lock Puzzles and Applications” whereby one can evaluate functions over puzzles without solving them. This amusing notion has nice applications like e-voting: in a simple setting, the voters create one encryption of 1 for the candidate they are voting for and distinct encryptions of 0 for all the others, so that summing up those sets over all voters yields the encrypted voting tally for all candidates (without revealing who voted for them), while adding the all encryptions, and independently the squares of all encryptions, for each individual voter yields a proof that they voted exactly once for each candidate. Transforming the encryptions into time-lock puzzles makes the decryption operations public, and does away with the need for a trusted third party. Other applications were suggested, like sealed e-auction bidding, multiparty coin flipping, or multiparty contract signing.

The session on the communication complexity of multiparty computation (MPC), which I chose over malleable codes, was no less striking, in particular the presentation by Mark Simkin and the one by Abhi Shelat.
Mark, who presented his work with S. Ghosh (“The Communication Complexity of Threshold Private Set Intersection”), started with applications of private set intersection (like the intersection of fingerprints) where one only cares about large intersections. In that case, it pays to set up the protocol so that one actually learns the complement of the intersection instead. One can see this as MPC of the ratio between characteristic polynomials, so that common factors (that is, those corresponding to the intersection) cancel. I didn’t quite gather whether a trusted third party is essential or just a secondary concern for the proposed protocol, though.
Abhi delighted the audience with a long, slow-motion clip of radical acrobatic skiing and the associated adrenaline rush. This blogger is not really sure the subject of MPC communication complexity causes a similar physiological effect, although the presenter claimed it does. After a recapitulation of the milestones of the subject, the audience was finally rewarded with a quite detailed mathematical treatment of the contribution, though this time at a very, very fast pace. Perhaps the subject does cause an adrenaline rush after all. Anyway, the work covered adaptively secure MPC with sublinear communication cost, in a scenario where the adversary can corrupt parties at any time, even after the end of the protocol, at which time the adversary can potentially corrupt all parties.

The session on post-quantum security focused on the quantum random oracle model (QROM). Both papers in the first part of that session, “How to Record Quantum Queries, and Applications to Quantum Indifferentiability” by M. Zhandry, and “Quantum Security Proofs Using Semi-classical Oracles” by A. Ambainis, M. Hamburg and D. Unruh, were thickly theoretical. The talk on “Quantum Indistinguishability of Random Sponges” by J. Czajkowski, A. Hülsing, and C. Schaffner was more approachable in my opinion (TL;DR: the sponge construction can be used to build quantum-secure pseudorandom functions when the adversary has superposition access to the input-output behavior of the sponge but not to the sponge’s internal function or permutation function itself, assumed to be random in their model). Sure enough, the more theoretically-oriented results have a clear and welcome niche even here, since these results build upon Zhandry’s prior switching lemma for pseudo-random functions or permutations from 2015. Zhandry is also a co-author of another paper from that session, “Revisiting Post-Quantum Fiat-Shamir” (joint work with Q. Liu), which was presented together with the last one, “Security of the Fiat-Shamir Transformation in the Quantum Random-Oracle Model” by J. Don et al.

Several other works are worth mentioning; I’ll mention a few more, but alas, not a full list: hanc blogis exiguitas non caperet. I found the paper “Unifying Leakage Models on a Rényi Day” by T. Prest, D. Goudarzi, A. Martinelli, and A. Passelègue, whose presentation I could not attend for not being proficient at ubiquity, quite entertaining (I assure the reader that this has nothing to do with my living in the often rainy Seattle area). The paper “It Wasn’t Me! Repudiability and Claimability of Ring Signatures” by S. Park and A. Sealfon deals with the question of enabling repudiation for ring signature non-signers, and claimability for actual signers of ring signatures. The importance of the first is to deflect undue responsibility for ring signatures produced by another ring member, and the importance of the latter lies in taking due credit for signing when that turns out to be, or becomes, desirable, but prior notions of security for ring signatures were ambivalent at best on such issues. Besides updated notions, the authors offer a repudiable scheme based on a variety of assumptions (for instance, bilinear maps), and unclaimable scheme based on the SIS assumption, and constructions for claimable or unrepudiable schemes that can be obtained from certain existing ring signatures.

Last but obviously not least, three papers got awards:

1. “Cryptanalysis of OCB2: Attacks on Authenticity and Confidentiality,” by A. Inoue, T. Iwata, K. Minematsu, and B. Poettering got the Best Paper award;
2. “Quantum Cryptanalysis in the RAM Model: Claw-Finding Attacks on SIKE,” by
S. Jaques and J. M. Schanck, got Best Young Researcher Paper award;
3. “Fully Secure Attribute-Based Encryption for $t$-CNF from LWE,” by R. Tsabary, got Best Young Researcher Paper award.

The papers are quite well written. The interested readers are encouraged to avail themselves of them for all of the fascinating details of these works. I was personally interested in the second of them and, to a smaller degree, the first, so I’ll try and briefly summarize those (I’m afraid the third falls somewhat outside my areas of expertise so I refer the interested reader to the corresponding paper).

Kazuhiko Minematsu began describing their work on OCB2 by showing how easy it is to attain a minimal forgery with one single encryption query. The general attack follows the model previously applied against the EAX Prime mode of operation, which lacked a formal security analysis (so it was not really a big surprise that scheme turned out to succumb to attacks). However, OCB2 was supported by a full-fledged security proof and remained unscathed for fifteen years. The attack described in the paper stems from an observed gap in that security proof which turned out to be a severe flaw. On the bright side, the attack does not extend to OCB1 nor OCB3, nor to certain suggested tweaks to OCB2. This shows that the overall structure of OCB is sound, but also the necessity of active verification of proofs.

Sam Jaques explained that their claw-finding paper set forth three goals. The first goal was to fairly compare attacks with classical and quantum resources. The second goal was to view gates as processes (which is indeed the view suggested by current quantum technology). The third goal was to include error correction as part of the cost and effort of the attack, since those are essential to overcome the exquisite fragility (in the sense of susceptibility to decoherence) of quantum computations. Their main idea was thus to view quantum memory as a physical system acted upon by a memory controller. As such, it undergoes two kinds of time evolution: free (caused by noise) and costly (caused by the controller). The computation cost becomes the number of iterations (ignoring construction costs, focusing on the controller cost instead). Two cost models are covered: the so-called G (gate) cost, which assumes passive error correction and 1 RAM operation per gate, and the DW (depth-width) cost, which counts 1 RAM operation per qubit per time unit. This sets the framework for their analysis of the claw-finding algorithm, which is a meet-in-the-middle attack to recover a path spelled out by the private key in the isogeny graph, between the initial curve and the final one (which is part of the public key). It can be realized by Tani’s collision-finding algorithm, by following random walks on two Johnson graphs, looking for a collision, and doing all computations in a quantum setting. The complexity is $\tilde{O}(p^{1/6})$. Despite the paper title, a quite surprising conclusion of their analysis is that SIDH and SIKE are actually harder to break than initially thought. In particular, it appears that the minimum SIKE parameter set (namely, SIKE434) cannot be broken by any known attack in less than the cost and effort needed to break AES128, specifically $2^{143}$. This scales to other parameter sets, to the effect that the revised SIKE parameters for the 2nd round of the NIST PQC process are smaller than their 1st round counterparts.

So, there you have it, a brief (and necessarily incomplete, but hopefully helpful) appraisal of Crypto 2019. Scripsi. Vale.

This entry was posted in Uncategorized. Bookmark the permalink.