International Association
for Cryptologic Research

Privacy and machine learning are difficult to coexist due to their nature: parivacy should be kept from others while machine learning requires large amount of data. Among several possible solutions to this problem, Fully Homomorphic Encryption has been a center of intensive researches in this field. FHE enables linear operations of ciphertext. To take advantage of this property, many protocols to achieve statistical operaions have been proposed. On the other hand, many of them are impractical. Some of the approaches introduce cryptosystems that are not familiar. Moreover, most of their protocols are approximation which might sensitively depend on our choice of parameters. In this paper, we propose fast, simple, and exact privacy-preserving linear equation solver using FHE. Our two-party protocol is secure against at least semi-honest model, and we can exactly calculate the model even without the bootstrapping.

OR-proofs enable a prover to show that it knows the witness for one of many statements, or that one out of many statements is true. OR-proofs are a remarkably versatile tool, used to strengthen security properties, design group and ring signature schemes, and achieve tight security. The common technique to build OR-proofs is based on an approach introduced by Cramer, Damgård, and Schoenmakers (CRYPTO’94), where the prover splits the verifier’s challenge into random shares and computes proofs for each statement in parallel. In this work we study a different, less investigated OR-proof technique, put forward by Abe, Ohkubo, and Suzuki (ASIACRYPT’02). The difference is that the prover now computes the individual proofs sequentially. We show that such sequential OR-proofs yield signature schemes which can be proved secure in the non-programmable random oracle model. We complement this positive result with a black-box impossibility proof, showing that the same is unlikely to be the case for signatures derived from traditional OR-proofs. We finally argue that sequential-OR signature schemes can be proved secure in the quantum random oracle model, albeit with very loose bounds and by programming the random oracle.

Inner product encryption is a powerful cryptographic primitive, where a private key and a ciphertext are both associated with a predicate vector and an attribute vector, respectively. A successful decryption requires the inner product of the predicate vector and the attribute vector to be zero. Most of the existing inner product encryption schemes suffer either long private key or heavy decryption cost. In this manuscript, an efficient inner product encryption is proposed. The length for a private key is only an element in $\mathbb{G}$ and an element in $\mathbb{Z}_p$. Besides, only a pairing is needed for decryption. Moreover, both formal security proof and implementation result are demonstrated in this manuscript. To the best of our knowledge, our scheme is the most efficient one in terms of the private key length and the number of pairings for decryption.

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.