International Association
for Cryptologic Research

State channels are an attractive layer-two solution for improving the throughput and latency of blockchains. They offer optimistic fast offchain settlement of payments and rapid offchain evolution of smart contracts between multiple parties without imposing any additional assumptions beyond those of the underlying blockchain. In the case of disputes, or if a party fails to respond, cryptographic evidence collected in the offchain channel is used to settle the last confirmed state onchain, such that in-progress contracts can be continued under mainchain consensus. A serious disadvantage present in current layer-two state channel protocols is that existing layer-one smart contract infrastructure and contract code cannot be reused offchain without change. In this paper, we introduce Hydra, an isomorphic multi-party state channel. Hydra simplifies offchain protocol and contract development by directly adopting the layer-one smart contract system. We present the onchain contracts to open and close Hydra heads (our isomorphic state channels) and a novel offchain protocol for fast evolution of heads. We establish strong security properties for the protocol, and we present and evaluate extensive simulation results that demonstrate that Hydra approaches the physical limits of the network in terms of transaction confirmation time and throughput while keeping storage requirements at the lowest possible.

The NIST PQC standardization project evaluates multiple new designs for post-quantum Key Encapsulation Mechanisms (KEMs). Some of them present challenging tradeoffs between communication bandwidth and computational overheads. An interesting case is the set of QC-MDPC based KEMs. Here, schemes that use the Niederreiter framework require only half the communication bandwidth compared to schemes that use the McEliece framework. However, this requires costly polynomial inversion during the key generation, which is prohibitive when ephemeral keys are used. One example is BIKE, where the BIKE-1 variant uses McEliece and the BIKE-2 variant uses Niederreiter. This paper shows an optimized constant-time polynomial inversion method that makes the computation costs of BIKE-2 key generation tolerable. We report a speedup of 11.8x over the commonly used NTL library, and 55.5 over OpenSSL. We achieve additional speedups by leveraging the latest Intel's Vector-PCLMULQDQ instructions on a laptop machine, 14.3x over NTL and 96.8x over OpenSSL. With this, BIKE-2 becomes a competitive variant of BIKE.

Fixing a number field, the space of all ideal lattices, up to isometry, is naturally an Abelian group, called the *Arakelov class group*. This fact, well known to number theorists, has so far not been explicitly used in the literature on lattice-based cryptography. Remarkably, the Arakelov class group is a combination of two groups that have already led to significant cryptanalytic advances: the class group and the unit torus.

In the present article, we show that the Arakelov class group has more to offer. We start with the development of a new versatile tool: we prove that, subject to the Riemann Hypothesis for Hecke $L$-functions, certain random walks on the Arakelov class group have a rapid mixing property. We then exploit this result to relate the average-case and the worst-case of the Shortest Vector Problem in ideal lattices. Our reduction appears particularly sharp: for Hermite-SVP in ideal lattices of certain cyclotomic number fields, it loses no more than a $\tilde O(\sqrt n)$ factor on the Hermite approximation factor.

Furthermore, we suggest that this rapid-mixing theorem should find other applications in cryptography and in algorithmic number theory.

This work considers the security of systems that process encrypted multi-dimensional range queries with only access pattern leakage. Recent work of Kellaris et al. (CCS 2016) showed that in one dimension, an adversary could use the access patterns of several uniformly random range queries to reconstruct a plaintext column of numbers “up to reflection.” We extend this attack to two dimensions and find that the situation is much more complicated: Information theoretically it is complex to describe even what is possible to recover for the adversary in general. We provide a classification of these limits under certain technical conditions. We also give a faster algorithm that works for “dense” databases that contain at least one record for each possible value. Finally we explore the implications for our classification with real data sets.

In this work we give several generalizations of the isotopic shift construction, introduced recently by Budaghyan et al. (2018), when the starting function is a Gold function. In particular, we derive a general construction of APN functions which produces one new APN function for $n=8$ and fifteen new APN functions for $n=9$.

We revisit the problem of proving that a user algorithm selected and correctly used a truly random seed in the generation of her cryptographic key. A first approach was proposed in 2002 by Juels and Guajardo for the validation of RSA secret keys. We present a new security model and general tools to efficiently prove that a private key was generated at random according to a prescribed process, without revealing any further information about the private key. In addition to formalizing randomness verifiability in key generation, which turns out to be highly non-trivial, we give a generic protocol for all key-generation algorithms based on probabilistic circuits and prove its security. We also propose a new protocol for factoring-based cryptography that we prove secure in the aforementioned model, as well as a practical instantiation. This latter relies on a new efficient zero-knowledge argument for the double discrete logarithm problem that achieves an exponential improvement in communication complexity compared to the state of the art, and is of independent interest.

Dear IACR Member,

As a consequence of the COVID-19 crisis, the Greek Health ministry took on March 8 the decision to suspend all conference events for the next four weeks (the announcement in Greek can be found here.).

Under these force majeure circumstances, FSE 2020 is postponed.

More details will follow soon.

For any questions please contact the General Chairs at fse2020@iacr.org

Event date: 16 July to 17 July 2020
Submission deadline: 24 April 2020
Notification: 4 May 2020

We introduce a family of extensions to the one-out-of-many proofs of Groth and Kohlweiss (Eurocrypt 2015), which efficiently prove statements about many messages among a list of commitments. These extensions prove knowledge of a secret subset of the list, and assert that the commitments in the subset satisfy certain properties (expressed as linear equations). Our communication remains logarithmic; our computation increases only by a logarithmic multiplicative factor. Our work introduces a new "circular rotation" technique, and a novel instantiation of the number-theoretic transform.

Applying these techniques, we construct a protocol for the Anonymous Zether payment system—as proposed in Bünz, Agrawal, Zamani, and Boneh (FC'20)—which improves upon the communication complexity attained by existing efforts. We describe an open-source, Ethereum-based implementation of our protocol.

We propose a framework for cryptanalysis of lattice-based schemes, when side information---in the form of ``hints''--- about the secret and/or error is available. Our framework generalizes the so-called primal lattice reduction attack, and allows the progressive integration of hints before running a final lattice reduction step. Our techniques for integrating hints include sparsifying the lattice, projecting onto and intersecting with hyperplanes, and/or altering the distribution of the secret vector. Our main contribution is to propose a toolbox and a methodology to integrate such hints into lattice reduction attacks and to predict the performance of those lattice attacks with side information.

While initially designed for side-channel information, our framework can also be used in other cases: exploiting decryption failures, or simply exploiting constraints imposed by certain schemes (LAC, Round5, NTRU), that were previously not known to (sligthly) benefit from lattice attacks.

We implement a Sage 9.0 toolkit to actually mount such attacks with hints when computationally feasible, and to predict their performances on larger instances. We provide several end-to-end application examples, such as an improvement of a single trace attack on Frodo by Bos et al (SAC 2018). Contrary to ad-hoc practical attacks exploiting side-channel leakage, our work is a generic way to estimate security loss even given very little side-channel information.

Defining unforgeability and designing cryptographic primitives that provide unforgeability in the quantum setting, i.e. where the adversary has quantum capabilities including quantum oracle access to the primitive, has proven to be a hard challenge. The classical notions and techniques do not transpose directly to the quantum setting. In this paper, we continue the line of work initiated by Boneh and Zhandry at CRYPTO 2013 and EUROCRYPT 2013 in which they formally define the notion of unforgeability against quantum adversaries specifically for Message Authentication Codes and Digital Signatures schemes. We develop a general and parameterized quantum game-based security framework for both classical and quantum primitives modelled by unitary transformations. We provide general possibility and impossibility results for such primitives. In particular, we show that no unitary primitive can provide existential unforgeability against quantum adversaries. Our main impossibility result relies on a new and generic quantum attack. We demonstrate this attack both on classical and quantum primitives to show its applicability as well as the completeness of our definitions of security. On the other hand, we show that selective unforgeability is satisfied by a specific class of unitaries that we term unknown unitaries.

We present attacks on 21-rounds of SIMON 32/64, 21-rounds of SIMON 48/96, 25-rounds of SIMON 64/128, 35-rounds of SIMON 96/144 and 43-rounds of SIMON 128/256, often with direct recovery of the full master key without repeating the attack over multiple rounds. These attacks result from the observation that, after four rounds of encryption, one bit of the left half of the state of 32/64 SIMON depends on only 17 key bits (19 key bits for the other variants of SIMON). Further, linear cryptanalysis requires the guessing of only 16 bits, the size of a single round key of SIMON 32/64. We partition the key into smaller strings by focusing on one bit of state at a time, decreasing the cost of the exhaustive search of linear cryptanalysis to 16 bits at a time for SIMON 32/64. We also present other example linear cryptanalysis, experimentally verified on 8, 10 and 12 rounds for SIMON 32/64.

Recent work using groups of unknown order to construct verifiable delay functions, polynomial commitment schemes and non interactive zero knowledge proofs have provoked fresh interest in the construction of efficient cryptographic groups of unknown order. It has been suggested that the Jacobian of hyperelliptic curves of genus 3 could be suitable for this purpose. Regrettably, efficient algorithms to compute the order of the Jacobian of a hyperelliptic curve are known. Concretely, it is unclear whether these groups are competitive with RSA groups or class groups at or above the 128 bit security level.

Light key schedule has found many applications in lightweight blockciphers, e.g. LED, PRINTcipher and LBlock. In this paper, we study an interesting question of how to design a as light as possible key schedule from the view of provable security and revisit the four-round key-alternating Feistel cipher by Guo and Wang in Asiacrypt 18. We optimize the construction by Guo and Wang and propose a four-round key-alternating Feistel cipher with an ultra-light (in fact non-existent) key schedule. We prove our construction retain the same security level as that of Guo and Wang's construction. To the best of our knowledge, this is the first provably secure key-alternating Feistel cipher using identical round function and one n-bit master key but with ultra-light (non-existent) key schedule. We also investigate whether the same renement works for the three-round key-alternating Feistel cipher. This time we show a distinguishing attack on such three-round construction with only four encryption queries. On the positive side, we prove that three-round key-alternating Feistel cipher with a suitable key schedule is a pseudorandom permutation. This is also the first provable-security result for three-round key-alternating Feistel cipher.

This paper introduces a new cryptographic primitive called a private resource allocator (PRA) that can be used to allocate resources (e.g., network bandwidth, CPUs) to a set of clients without revealing to the clients whether any other clients received resources. We give several constructions of PRAs that provide guarantees ranging from information-theoretic to differential privacy. PRAs are useful in preventing a new class of attacks that we call allocation-based side-channel attacks. These attacks can be used, for example, to break the privacy guarantees of anonymous messaging systems that were designed specifically to defend against side-channel and traffic analysis attacks. Our implementation of PRAs in Alpenhorn, which is a recent anonymous messaging system, shows that PRAs increase the network resources required to start a conversation by up to 16X (can be made as low as 4X in some cases), but add no overhead once the conversation has been established.

We put forth a new framework for building pairing-based non-interactive zero- knowledge (NIZK) arguments for a wide class of algebraic languages, which are an extension of linear languages, containing disjunctions of linear languages and more. Our approach differs from the Groth-Sahai methodology, in that we rely on pairings to compile a $\Sigma$-protocol into a NIZK. Our framework enjoys a number of interesting features: – conceptual simplicity, parameters derive from the $\Sigma$-protocol; – proofs as short as resulting from the Fiat-Shamir heuristic applied to the underlying $\Sigma$-protocol; – fully adaptive soundness and perfect zero-knowledge in the common random string model with a single random group element as CRS; – yields simple and efficient two-round, public coin, publicly-verifiable perfect witness-indistinguishable (WI) arguments (ZAPs) in the plain model. To our knowledge, this is the first construction of two-rounds statistical witness-indistinguishable arguments from pairing assumptions. Our proof system relies on a new (static, falsifiable) assumption over pairing groups which generalizes the standard kernel Diffie-Hellman assumption in a natural way and holds in the generic group model (GGM) and in the algebraic group model (AGM). Replacing Groth-Sahai NIZKs with our new proof system allows to improve several important cryptographic primitives. In particular, we obtain the shortest tightly-secure structure-preserving signature scheme (which are a core component in anonymous credentials), the shortest tightly-secure quasi-adaptive NIZK with unbounded simulation soundness (which in turns implies the shortest tightly-mCCA-secure cryptosystem), and shorter ring signatures.

We revisit the security of various generalized Feistel networks. Concretely, for unbalanced, alternating, type-1, type-2, and type-3 Feistel networks built from random functions, we substantially improve the coupling analyzes of Hoang and Rogaway (CRYPTO 2010). For a tweakable blockcipher-based generalized Feistel network proposed by Coron et al. (TCC 2010), we present a coupling analysis and for the first time show that with enough rounds, it achieves 2n-bit security, and this provides highly secure, double-length tweakable blockciphers.

The PhD student will join the Prof. Mitrokotsa's group, working in the area of information and communication security and machine learning with a focus on mechanisms and protocols for secure and private machine learning. More precisely, we envision secure and privacy-preserving machine learning algorithms for artificial intelligence applications in everyday life that can provide confidentiality and integrity guarantees. In particular the main aims of the project are to: (i) Safeguard the privacy of individuals that participate by either providing their data to build the AI system or being end-users of the system, (ii) safeguard the integrity of the system by ensuring its robustness to adversarial inputs and cryptographically limiting the possible points of adversarial manipulation.

Closing date for applications:

Contact: Katerina Mitrokotsa, aikmitr@chalmers.se

More information: https://www.chalmers.se/en/about-chalmers/Working-at-Chalmers/Vacancies/Pages/default.aspx?rmpage=job&rmjob=p8402

Algorand is looking for a Cryptography Intern to join our Team. This is an opportunity for someone who is genuinely excited by new technologies to influence the design and implementation of Algorand’s consensus infrastructure. You will be working on a fast-paced, rapidly growing, high-profile project with a significant opportunity for industry-level impact on emerging blockchain and cryptocurrency technologies. Core Responsibilities: Design and build cryptographic protocols and schemes for privacy preserving assets Design and build cryptographic protocols for cross-chain transfers Partner with the larger organization (including Product and Engineering) regarding the implementation of designs at scale Be a key part of an inclusive environment that fosters collaboration and creativity both internally and externally Requirements & Qualifications: Masters in Computer Science or related technical field is required; PhD (either earned or in progress) preferred Expertise in distributed computation, probabilistic analysis, data structure, algorithm design and analysis required Experience with zero-knowledge proofs and proof systems Solid mathematics training, highly capable of abstract thinking and modeling Good written communication and ability to communicate technical information with wide variety of audiences Exposure to game theory, cryptography, or distributed systems preferred Experience in driving the implementation of complex theoretical designs or as a technical participant for highly scalable distributed system designs preferred Enjoyment for working in a highly collaborative, fast-paced, and dynamic environment Internships at Algorand, Inc. are non-exempt temporary positions, with hourly rates set to market standards. You must be a matriculated university student, scheduled to return in the Fall.

Closing date for applications:

Contact: Makena Stone

A postdoctoral positions related to privacy-enhancing cryptography in distributed ledgers. Strong applicants in other areas of cryptography, or security & privacy might also be considered. Candidates should have a PhD in cryptography, or a security & privacy related field.

Closing date for applications:

Contact: Interested persons please email with a cover letter and updated curriculum vitae to mkohlwei@ed.uk.ac. The position will be available until filled; only short-listed candidates will be notified.