International Association
for Cryptologic Research

Decades of research in both cryptography and distributed systems has extensively studied the problem of state machine replication, also known as Byzantine consensus. A consensus protocol must satisfy two properties: consistency and liveness. These properties ensure that honest participating nodes agree on the same log and dictate when fresh transactions get added. They fail, however, to ensure against adversarial manipulation of the actual ordering of transactions in the log. Indeed, in leader-based protocols (almost all protocols used today), malicious leaders can directly choose the final transaction ordering.

To rectify this problem, we propose a third consensus property: transaction order-fairness. We initiate the first formal investigation of order-fairness and explain its fundamental importance. We provide several natural definitions for order-fairness and analyze the assumptions necessary to realize them.

We also propose a new class of consensus protocols called Aequitas. Aequitas protocols are the first to achieve order-fairness in addition to consistency and liveness. They can be realized in a black-box way using existing broadcast and agreement primitives (or indeed using any consensus protocol), and work in both synchronous and asynchronous network models.

Since the introduction of the ring-learning with errors problem, the number theoretic transform (NTT) based polynomial multiplication algorithm has been studied extensively. Due to its faster quasilinear time complexity, it has been the preferred choice of cryptographers to realize ring-learning with errors cryptographic schemes. Compared to NTT, Toom-Cook or Karatsuba based polynomial multiplication algorithms, though being known for a long time, still have a fledgling presence in the context of post-quantum cryptography. In this work, we observe that the pre- and post-processing steps in Toom-Cook based multiplications can be expressed as linear transformations. Based on this observation we propose two novel techniques that can increase the efficiency of Toom-Cook based polynomial multiplications. Evaluation is reduced by a factor of 2, and we call this method precomputation, and interpolation is reduced from quadratic to linear, and we call this method lazy interpolation. As a practical application, we applied our algorithms to the Saber post-quantum key-encapsulation mechanism. We discuss in detail the various implementation aspects of applying our algorithms to Saber. We show that our algorithm can improve the efficiency of the computationally costly matrix-vector multiplication by12−37%compared to previous methods on their respective platforms. Secondly, we propose different methods to reduce the memory footprint of Saber for Cortex-M4microcontrollers. Our implementation shows between2.6 and 5.7KB reduction in memory usage with respect to the smallest implementation in the literature.

Post-quantum cryptography introduces cryptographic algorithms that are secure against adversaries who can employ a quantum computer and it is the inevitable next-step in the evolution of the cryptographic algorithms. In order to create a conventional foundation the National Institute of Standards and Technology (NIST) started a competition for Post-Quantum Cryptography in 2017.

This paper introduces the first differential side channel analysis of a candidate in the competition; the Picnic Signature Scheme. We present a successful side channel analysis of the underlying Multiparty LowMc implementation and show how leakages can be exploited to recover the entire secret key using two different parts of the algorithm. LowMc key recovery then allows to forge signatures for the calling Picnic post-quantum signature scheme. We target the NIST reference implementation executed on a FRDM-K66F development board. Key recovery succeeds with less than 1000 traces, which can be obtained from less than 30 observed Picnic signatures.

In this work we study the (superposition-based, or QS2) quantum security of public key encryption schemes. Boneh and Zhandry (CRYPTO 2013) initiated this research area for symmetric and public key encryption, albeit restricted to a classical indistinguishability phase. Gagliardoni et al. (CRYPTO 2016) advanced the study of quantum security, for symmetric key encryption schemes, by giving the first definition where the indistinguishability phase is quantum. For public key encryption schemes, on the other hand, no notion of quantum security with a quantum indistinguishability phase exists. In this work we close this gap by defining strong QS2 security notions for the public key case. Our core idea follows the approach of Gagliardoni et al. by using so-called type-2 operators for encrypting the challenge message. Extending this idea to the public key case brings non-trivial obstacles: On the one hand, public key encryption schemes typically cannot recover the randomness when decrypting ciphertexts. On the other hand, many real-world schemes (including most quantum-resistant NIST candidates) suffer from a small probability of decryption failures. These two problems make it difficult to enforce the reversibility of the encryption operation needed by type-2 operators. Nevertheless, we identify a class of encryption schemes, which we call recoverable, that allow to avoid decryption failures given knowledge of the original encryption randomness, and we show that many real-world quantum-resistant schemes, including many NIST candidates, are of this type. Then we show how to define and construct type-2 encryption operators for schemes that are fully correct or recoverable. Moreover, we show that for recoverable schemes, the type-2 operator can be efficiently implemented even without knowledge of the secret key. This means that, for the public key case, type-2 operators are actually very natural, and already included in the traditional "post-quantum" (QS1) definition of security. Equipped with these results, we (1) give the first quantum security notion (qINDqCPA) for public key encryption with a quantum indistinguishability phase, (2) prove that the canonical LWE-based encryption scheme achieves our security notion, (3) show that our notion is strictly stronger than existing security notions, and (4) study the general classification of quantum-resistant public key encryption schemes.

Non-interactive zero-knowledge proofs (NIZKs) are important primitives in cryptography. A major challenge since the early works on NIZKs has been to construct NIZKs with a statistical zero-knowledge guarantee against unbounded verifiers. In the common reference string (CRS) model, such "statistical NIZK arguments" are currently known from k-Lin in a pairing-group and from LWE. In the (reusable) designated-verifier model (DV-NIZK), where a trusted setup algorithm generates a reusable verification key for checking proofs, we also have a construction from DCR. If we relax our requirements to computational zero-knowledge, we additionally have NIZKs from factoring and CDH in a pairing group in the CRS model, and from nearly all assumptions that imply public-key encryption (e.g., CDH, LPN, LWE) in the designated-verifier model. Thus, there still remains a gap in our understanding of statistical NIZKs in both the CRS and the designated-verifier models.

In this work, we develop new techniques for constructing statistical NIZK arguments. First, we construct statistical DV-NIZK arguments from the k-Lin assumption in pairing-free groups, the QR assumption, and the DCR assumption. These are the first constructions in pairing-free groups and from QR that satisfy statistical zero-knowledge. All of our constructions are secure even if the verification key is chosen maliciously (i.e., they are "malicious-designated-verifier" NIZKs), and moreover, they satisfy a "dual-mode" property where the CRS can be sampled from two computationally indistinguishable distributions: one distribution yields statistical DV-NIZK arguments while the other yields computational DV-NIZK proofs. We then show how to adapt our k-Lin construction in a pairing group to obtain new publicly-verifiable statistical NIZK arguments from pairings with a qualitatively weaker assumption than existing constructions of pairing-based statistical NIZKs.

Our constructions follow the classic paradigm of Feige, Lapidot, and Shamir (FLS). While the FLS framework has traditionally been used to construct computational (DV)-NIZK proofs, we newly show that the same framework can be leveraged to construct dual-mode (DV)-NIZKs.

Homomorphic encryption primitives have the potential to be the main enabler of privacy preserving computation delegation to cloud environments. One of the avenues which has been explored to reduce their significant computational overhead with respect to cleartext computation is the one of the so-called noise-free homomorphic encryption schemes. In this work, we present an attack against fully homomorphic encryption primitives where a distinguisher for a single plaintext value exists. We employ two noise-free homomorphic encryption schemes where such a property holds as our case studies, providing detailed attack procedure against them. We validate the effectiveness and performance of our attacks on prototype implementations of the said schemes, and suggest two countermeasures to our attack tailored to the schemes at hand.

Event date: 22 June to 25 June 2020
Submission deadline: 25 March 2020
Notification: 25 April 2020

Simula UiB (http://simula-uib.com) in Bergen, Norway, has one three-year Ph.D positions available in the field of cryptography. Ph.D students at Simula UiB enjoy a startup-like international working environment with good salaries and work-life balance, with very few obligations on top of doing research. Project/Job description: The Ph.D candidate will be supervised by Helger Lipmaa (https://sites.google.com/view/helgerlipmaa) on topics related to zk-SNARKs and zero-knowledge and their various applications (cryptocurrencies, verifiable computation, e-voting, to name a few). Zk-SNARKs have been become excessively popular during the last few years due to the application in privacy-preserving cryptocurrencies, leading the MIT technology review to name them one of the “10 Breakthrough Technologies of 2018” (https://www.technologyreview.com/lists/technologies/2018/). Candidate Profile: a completed MSc degree in cryptography, or related areas (in particular, theoretical computer science, including algorithms and/or complexity theory, and mathematics). We will also consider applicants who are in the final phase of their Master studies. We expect an excellent academic track record, including top grades. The student is expected to be at home both in theory and in practice. Simula UiB is an equal opportunity employer, and women are particularly encouraged to apply. Simula UiB Offers: Modern office facilities located in downtown Bergen ("the gateway to the fjords"). A competitive salary starting from NOK 479.600 (approx 48000 euros). Special emphasis on wellness and work-life balance. Numerous additional benefits. About Simula UiB: Simula UiB AS is a research centre owned by Simula Research Laboratory AS and the University of Bergen (UiB). The goal of Simula UiB is to increase the security expertise in Norway through research and education in cryptography and information theory. The student will officially defend at UiB.

Closing date for applications:

Contact: Helger Lipmaa

More information: https://www.simula.no/about/job/call-phd-student-cryptography

Dear IACR member,

The IACR board is currently monitoring the outbreak of the novel coronavirus (COVID-19) and assessing its potential impact on forthcoming IACR conferences. Although the current conference schedule has not changed, we are in close contact with the conference organizers and constantly reevaluating the situation. In case a conference needs to be postponed, relocated, cancelled, or switched to a web-only format, we will be informing the membership and attendees as soon as possible via the IACR news system and other appropriate communication channels. Publication schedules will not be altered significantly even if conferences are affected.

In the meantime, we are in the process of implementing several measures to ease the burden on attendees who cannot physically attend the conference due to travel restrictions or concerns related to the novel coronavirus outbreak. These include:

• having a more flexible cancellation and refund policy; and
• allowing alternative methods of presentation, such as pre-recorded videos.

In order to guarantee the safety of conference attendees, we are also asking our conference organizers to follow the safety guidelines of the World Health Organization (WHO) and national health protection agencies such as the U.S. Centers for Disease Control and Prevention (CDC) and to ensure attendees are aware of these guidelines. In addition, we also plan to have a point of contact for each conference to address concerns by attendees.

Links:
WHO: https://www.who.int/emergencies/diseases/novel-coronavirus-2019
CDC: https://www.cdc.gov/coronavirus/2019-ncov/index.html
IACR News: https://www.iacr.org/news/

Event date: 15 August 2020
Submission deadline: 10 May 2020
Notification: 1 July 2020

Funded position for PhD in the Mathematics of Post-Quantum Cryptography, to work on theoretical questions. The research will be on some or all of the following: isogenies, algebraic geometry, codes, lattices. The ideal candidate will have a strong undergraduate mathematics knowledge including abstract algebra, number theory and geometry. An MSc is a plus. Experience with computer programming and cryptography is also desirable. This is part of a collaboration with the group of Prof. Steven Galbraith at the University of Auckland and interaction with this group is expected.

Closing date for applications:

Contact: Prof. Felipe Voloch

More information: http://www.math.canterbury.ac.nz/~f.voloch/prospective.html

BIMSA

Beijing Institute of Mathematical Sciences and Applications (BIMSA) is a new research institution to be established and lead by Professor Shing-Tung Yau, a Fields medalist of 1982. Its location is in the Yanqi Lake area of Beijing where APEC 2014 was hosted. It was expected to launch by the end of March 2020.

Program

Advanced Cryptography and Blockchain Program will be one of the many research groups of BIMSA. It will be focused on:

• zero knowledge proofs (zk-SNARKs etc.)
• fully homomorphic encryption
• secure multiparty computation
• other related cryptographic schemes
• blockchain

with a combination of theoretical studies and practical implementations.

Positions

We have 20 open positions on all levels, with competitive compensation packages:

• Distinguished Research Professor
• Research Professor
• Associate Research Professor
• Assistant Research Professor (tenure-track)
• Visiting Research Professor
• Research Fellowship (postdoc)

We intend to build a strong and highly international team, participating in the mainstream of academic studies and industrial innovations worldwide.

Closing date for applications:

Contact: Prof. Kevin Mo

More information: http://ymsc.tsinghua.edu.cn/en/content/show/91-275.html https://www.mathjobs.org/jobs/jobs/14633 https://www.linkedin.co

Event date: 20 August to 21 August 2020
Submission deadline: 24 April 2020
Notification: 29 May 2020

Event date: 25 May to 29 May 2020

Cryptography, Security & Privacy Research Group at Koç University has multiple openings for summer research interns.

For summer research opportunities (at both undergraduate and graduate level), visit

http://kusrp.ku.edu.tr

All applications must be completed online. Deadline is 29 March 2020.

For more information about joining our group and projects, visit

https://crypto.ku.edu.tr/work-with-us/

Application Requirements:

1. CV
2. 2 Recommendation Letters
3. Official transcripts from all the universities attended
4. Statement of Purpose
5. Application Form filled online

Closing date for applications:

Contact: http://kusrp.ku.edu.tr

More information: http://kusrp.ku.edu.tr

In this work, we propose a new table-based block cipher structure, dubbed $\mathsf{FPL}$, that can be used to build white-box secure block ciphers. Our construction is a balanced Feistel cipher, where the input to each round function determines multiple indices for the underlying table via a probe function, and the sum of the values from the table becomes the output of the round function. We identify the properties of the probe function that make the resulting block cipher white-box secure in terms of weak and strong space hardness against known-space and non-adaptive chosen-space attacks. Our construction, enjoying rigorous provable security without relying on any ideal primitive, provides flexibility to the block size and the table size, and permits parallel table look-ups.

We also propose a concrete instantiation of $\mathsf{FPL}$, dubbed $\mathsf{FPL}_{\mathsf{AES}}$, using (round-reduced) $\mathsf{AES}$ for the underlying table and probe functions. Our implementation shows that $\mathsf{FPL}_{\mathsf{AES}}$ provides stronger security without significant loss of efficiency, compared to existing schemes including $\mathsf{SPACE}$, $\mathsf{WhiteBlock}$ and $\mathsf{WEM}$.

It has been suspected that in supersingular isogeny-based cryptosystems the two ending elliptic curves computed by the participants are exactly equal. Resolving this open problem has not been pressing because the elliptic curves are known to be isomorphic, and therefore share a $j$-invariant which can be used as a shared secret. However, this is still an interesting independent problem as other values of the elliptic curves may be valuable as shared information as well. This note answers this open problem in the affirmative.

This paper presents Foxtail+, a new shared-key protocol to securely authenticate resource constrained devices, such as Internet of things (IoT) devices. Foxtail+ is based on a previously proposed protocol to authenticate unaided humans, called the Foxtail protocol, which we modify for authenticating resource constrained devices. It uses a computationally lightweight function, called the Foxtail function, which makes it ideal for IoT nodes with low memory, computational, and/or battery resources. We introduce a new family of functions based on the Foxtail function, analyze its security in terms of the number of samples required to obtain the secret, and demonstrate how it is connected with the learning with rounding (LWR) problem. We then build the Foxtail+ protocol from this function family, secure against active adversaries. Finally, we implement and experimentally evaluate the performance of Foxtail+ against a similar alternate protocol, i.e., the modified version of the Hopper and Blum protocol called HB+, and a block cipher based protocol instantiated with AES. The experiments are run on an IoT device connected to a LoRa network which is an IoT specific Low-Power Wide-Area Network (LPWAN). We show that Foxtail+ outperforms HB+ in terms of overall communication and energy cost, and its parallel implementation is comparable to the AES-based protocol in terms of time and energy consumption. To our knowledge, we provide the first implementation of any member of the HB+ family of protocols that directly compares its performance against an AES-based protocol in terms of time and power consumption. Our experiments shed new light on some of the limitations of identification protocols based on lightweight primitives, of which Foxtail+ is a member, over block cipher based protocols.

We present in this paper a blind signature and its partially blind variant based on lattices assumptions. Blind signature is a cornerstone in privacy-oriented cryptography and we propose the first lattice based scheme without restart. Compare to related work, the key idea of our construction is to provide a trapdoor to the signer in order to let him perform some gaussian pre-sampling during the signature generation process, preventing this way to restart from scratch the whole protocol. We prove the security of our scheme under the ring k-SIS assumption, in the random oracle model. We also explain security issues in the other existing lattice-based blind signature schemes. Finally, we propose a partially blind variant of our scheme, which is done with no supplementary cost, as the number of elements generated and exchanged during the signing protocol is exactly the same.

Two-source non-malleable extractors are pseudorandom objects which extract randomness even when an adversary is allowed to learn the behavior of the extractor on tamperings of the input weak sources, and they have found important applications in non-malleable coding and secret sharing. We begin by asking how hard it is to improve upon the best known constructions of such objects (Chattopadhyay, Goyal, Li, STOC 2016, and Li, STOC 2017). We show that even small improvements to these constructions lead to explicit low-error two-source extractors for very low linear min-entropy, a longstanding open problem in pseudorandomness.

Given the result above in the information-theoretic setting, we turn to studying two-source non-malleable extractors in the computational setting, namely in the CRS model first considered in (Garg, Kalai, Khurana, Eurocrypt 2020). We enforce that both the sampling process for the input sources and the tampering functions must be efficient, but we do not necessarily put such a constraint on the adversary distinguishing the output of the extractor from uniform. We obtain results about two-source non-malleable extractors in the CRS model under different types of hardness assumptions:

- Under standard assumptions, we show that small improvements upon state-of-the-art statistical two-source non-malleable extractors also yield explicit low-error two-source non-malleable extractors in the CRS model for low min-entropy against computationally unbounded distinguishers. Remarkably, all previous results on computational extractors require much stronger assumptions; - Under a quasi-polynomial hardness assumption, we give explicit constructions of low-error two-source non-malleable extractors in the CRS model with much lower min-entropy requirements than their best statistical counterparts, against a computationally bounded distinguisher; - Assuming the existence of nearly optimal collision-resistant hash functions, we give a simple explicit construction of a low-error two-source non-malleable extractors in the CRS model for very low min-entropy, against a computationally unbounded distinguisher.