International Association
for Cryptologic Research

Supersingular isogeny Diffie-Hellman key exchange (SIDH) is a post-quantum protocol based on the presumed hardness of computing an isogeny between two supersingular elliptic curves given some additional torsion point information. Unlike other isogeny-based protocols, SIDH has been widely believed to be immune to subexponential quantum attacks because of the non-commutative structure of the endomorphism rings of supersingular curves. We contradict this commonly believed misconception in this paper. More precisely, we highlight the existence of an abelian group action on the SIDH key space, and we show that for sufficiently unbalanced and overstretched SIDH parameters, this action can be efficiently computed (heuristically) using the torsion point information revealed in the protocol. This reduces the underlying hardness assumption to a hidden shift problem instance which can be solved in quantum subexponential time. We formulate our attack in a new framework allowing the inversion of one-way functions in quantum subexponential time provided a malleability oracle with respect to some commutative group action. This framework unifies our new attack with earlier subexponential quantum attacks on isogeny-based protocols, and it may be of further interest for cryptanalysis.

In a seminal work, Micali (FOCS 1994) gave the first succinct non-interactive argument (SNARG) in the random oracle model (ROM). The construction combines a PCP and a cryptographic commitment, and has several attractive features: it is plausibly post-quantum; it can be heuristically instantiated via lightweight cryptography; and it has a transparent (public-coin) parameter setup. However, it also has a significant drawback: a large argument size.

In this work, we provide a new construction that achieves a smaller argument size. This is the first progress on the Micali construction since it was introduced over 25 years ago.

A SNARG in the ROM is *(t,ε)-secure* if every t-query malicious prover can convince the verifier of a false statement with probability at most ε. For (t,ε)-security, the argument size of all known SNARGs in the ROM (including Micali's) is Õ((log (t/ε))^2) bits, *even* if one were to rely on conjectured probabilistic proofs well beyond current techniques. In practice, these costs lead to SNARGs that are much larger than constructions based on other (pre-quantum and costly) tools. This has led many to believe that SNARGs in the ROM are inherently quadratic.

We show that this is not the case. We present a SNARG in the ROM with a sub-quadratic argument size: Õ(log (t/ε) ∙ log t). Our construction relies on a strong soundness notion for PCPs and a weak binding notion for commitments. We hope that our work paves the way for understanding if a linear argument size, that is O(log (t/ε)), is achievable in the ROM.

We show the following generic result. Whenever a quantum query algorithm in the quantum random-oracle model outputs a classical value $t$ that is promised to be in some tight relation with $H(x)$ for some $x$, then $x$ can be efficiently extracted with almost certainty. The extraction is by means of a suitable simulation of the random oracle and works *online*, meaning that it is *straightline*, i.e., without rewinding, and *on-the-fly*, i.e., during the protocol execution and without disturbing it.

The technical core of our result is a new commutator bound that bounds the operator norm of the commutator of the unitary operator that describes the evolution of the compressed oracle (which is used to simulate the random oracle above) and of the measurement that extracts $x$.

We show two applications of our generic online extractability result. We show *tight* online extractability of commit-and-open $\Sigma$-protocols in the quantum setting, and we offer the first non-asymptotic post-quantum security proof of the *textbook* Fujisaki-Okamoto transformation, i.e, without adjustments to facilitate the proof.

This paper studies how to incorporate small information leakages (called “hints”) into information-set decoding (ISD) algorithms. In particular, the influence of these hints on solving the (n, k, t)-syndrome-decoding problem (SDP), i.e., generic syndrome decoding of a code of length n, dimension k, and an error of weight t, is analyzed. We motivate all hints by leakages obtainable through realistic side-channel attacks on code-based post-quantum cryptosystems. One class of studied hints consists of partial knowledge of the error or message, which allow to reduce the length, dimension, or error weight using a suitable transformation of the problem. As a second class of hints, we assume that the Hamming weights of subblocks of the error are known, which can be motivated by a template attack. We present adapted ISD algorithms for this type of leakage. For each third-round code-based NIST submission (Classic McEliece, BIKE, HQC), we show how many hints of each type are needed to reduce the work factor below the claimed security level. E.g., for Classic McEliece mceliece348864, the work factor is reduced below 2^128 for 175 known message entries, 9 known error locations, 650 known error-free positions, or known Hamming weights of 29 subblocks of roughly equal size.

We prove two classes of lower bounds on the communication complexity of information-theoretically secure multiparty computation. The first lower bound applies to perfect passive secure multiparty computation, in the standard model with $n=2t+1$ parties of which $t$ are corrupted. We show a lower bound that applies to secure evaluation of any function, assuming that each party can choose to learn to learn or not learn the output. Specifically, we show that there is a function $H^*$ such that for any protocol that evaluates $y_i=b_i \cdot f(x_1,...,x_n)$ with perfect passive security (where $b_i$ is a private boolean input), the total communication must be at least $\frac{1}{2} \sum_{i=1}^n H_f^*(x_i)$ bits of information.

The second lower bound applies to the perfect maliciously secure setting with $n=3t+1$ parties. We show that for any $n$ and all large enough $S$, there exists a reactive functionality $F_S$ taking an $S$-bit string as input (and with short output) such that any protocol implementing $F_S$ with perfect malicious security must communicate $\Omega(nS)$ bits. Since the functionalities we study can be implemented with linear size circuits, the result can equivalently be stated as follows: for any $n$ and all large enough $g \in \mathbb{N}$ there exists a reactive functionality $F_C$ doing computation specified by a Boolean circuit $C$ with $g$ gates, where any perfectly secure protocol implementing $F_C$ must communicate $\Omega(n g)$ bits. The results easily extends to constructing similar functionalities defined over any fixed finite field. Using known techniques, we also show an upper bound that matches the lower bound up to a constant factor (existing upper bounds are a factor $\log n$ off for Boolean circuits).

Both results also extend to the case where the threshold $t$ is suboptimal. Namely if $n=kt+s$ the bound is weakened by a factor $O(s)$, which corresponds to known optimizations via packed secret-sharing.

Several recent proposals of efficient public-key encryption are based on variants of the polynomial learning with errors problem ($\mathsf{PLWE}^f$) in which the underlying polynomial ring $\mathbb{Z}_q[x]/f$ \ is replaced with the (related) modular integer ring $\mathbb{Z}_{f(q)}$; the corresponding problem is known as Integer Polynomial Learning with Errors ($\mathsf{I-PLWE}^f$). Cryptosystems based on $\mathsf{I-PLWE}^f$ and its variants can exploit optimised big-integer arithmetic to achieve good practical performance, as exhibited by the $\mathsf{ThreeBears}$ cryptosystem. Unfortunately, the average-case hardness of $\mathsf{I-PLWE}^f$ and its relation to more established lattice problems have to date remained unclear.

We describe the first polynomial-time average-case reductions for the search variant of $\mathsf{I-PLWE}^f$, proving its computational equivalence with the search variant of its counterpart problem $\mathsf{PLWE}^f$. Our reductions apply to a large class of defining polynomials $f$. To obtain our results, we employ a careful adaptation of Rényi divergence analysis techniques to bound the impact of the integer ring arithmetic carries on the error distributions. As an application, we present a deterministic public-key cryptosystem over integer rings. Our cryptosystem, which resembles $\mathsf{ThreeBears}$, enjoys one-way (OW-CPA) security provably based on the search variant of $\mathsf{I-PLWE}^f$.

A proxy re-encryption scheme can be executed by a semi-trusted proxy, so that we can transform a ciphertext encrypted with a key to another ciphertext encrypted with different key without allowing the proxy to access the plaintext. A method to implement a secure proxy re-encryption is by first converting the plaintext to an intermediate form by using an all or nothing transform (AONT). In this paper, we describe an improved proxy re-encryption scheme for symmetric cipher by advocating the usage of a variant of the AONT function in the proxy re-encryption scheme. We show that the scheme secure under Chosen Plaintext Attack (CPA) for all possible types of attackers.

Galois and Fibonacci are two different configurations of stream ciphers. Because the Fibonacci configuration is more convenient for cryptanalysis, most ciphers are designed as Fibonacci-configured. So far, although many transformations between Fibonacci and Galois configurations have been proposed, there is no sufficient analysis of their respective hardware performance. The 128-bit secret key stream cipher Espresso, its Fibonacciconfigured variant and linear Fibonacci variant have a similar security level. We take them as examples to design the optimization strategies in terms of both area and throughput, investigate which configuration is more efficient in a certain aspect. The Fibonacci-configured Espresso occupies 52 slices on Spartan-3 and 22 slices on Virtex-7, which are the minimum solutions among those three Espresso schemes or even smaller than 80-bit secret key ciphers. Based on our throughput improvement strategy, parallel Espresso design can perform 4.1 Gbps on Virtex-7 FPGA and 1.9 Gbps on Spartan-3 FPGA at most. In brief, the Fibonacci cipher is more suitable for extremely resource-constrained or extremely high-throughput applications, while the Galois cipher seems like a compromise between area and speed. Besides, the transformation from nonlinear feedback to linear feedback is not recommended for any hardware implementations.

We present the first homomorphic secret sharing (HSS) construction that simultaneously (1) has negligible correctness error, (2) supports integers from an exponentially large range, and (3) relies on an assumption not known to imply FHE --- specifically, the Decisional Composite Residuosity (DCR) assumption. This resolves an open question posed by Boyle, Gilboa, and Ishai (Crypto 2016). Homomorphic secret sharing is analogous to fully-homomorphic encryption, except the ciphertexts are shared across two non-colluding evaluators. Previous constructions of HSS either had non-negligible correctness error and polynomial-size plaintext space or were based on the stronger LWE assumption. We also present two applications of our technique: a multi-server ORAM with constant bandwidth overhead, and a rate-1 trapdoor hash function with negligible error rate.

Oblivious Pseudorandom Function (OPRF) is a protocol between a client holding input x and a server holding key k for a PRF F. At the end, the client learns F_k(x) and nothing else while the server learns nothing. OPRF's have found diverse applications as components of larger protocols, and the currently most efficient instantiation, with security proven in the UC model, is F_k(x)=H2(x,(H1(x))^k) computed using so-called exponential blinding, i.e., the client sends a=(H1(x))^r for random r, the server responds b=a^k, which the client ublinds as v=b^{1/r} to compute F_k(x)=H2(x,v).

However, this protocol requires two variable-base exponentiations on the client, while a more efficient multiplicative blinding scheme replaces one or both client exponentiations with fixed-base exponentiation, leading to the decrease of the client's computational cost by a factor between two to six, depending on pre-computation. We analyze the security of the above OPRF with multiplicative blinding, showing surprising weaknesses that offer attack avenues which are not present using exponential blinding. We characterize the security of this OPRF implementation as a "Revised OPRF" functionality, a relaxation of UC OPRF functionality used in prior work. On the positive side, we show that the Revised OPRF suffices for the security of OPAQUE, the asymmetric PAKE protocol, hence allowing OPAQUE the computational advantages of multiplicative blinding. Unfortunately, we also show examples of other OPRF applications which become insecure when using such blinding. The conclusion is that usage of multiplicative blinding for F_k(x) defined as above, in settings where correct value g^k (needed for multiplicative blinding) is not authenticated, and OPRF inputs are of low entropy, must be carefully analyzed, or avoided all together. We complete the picture by showing a simple and safe alternative definition of function F_k(x) which offers (full) UC OPRF security using either form of blinding.

SIDH/SIKE-style protocols benefit from key compression to minimize their bandwidth requirements, but proposed key compression mechanisms rely on computing bilinear pairings. Pairing computation is a notoriously expensive operation, and, unsurprisingly, it is typically one of the main efficiency bottlenecks in SIDH key compression, incurring processing time penalties that are only mitigated at the cost of trade-offs with precomputed tables. We address this issue by describing how to compress isogeny-based keys without pairings. As a bonus, we also substantially reduce the storage requirements of other operations involved in key compression.

In this work, we put forth the notion of compatibility of any key generation or setup algorithm. We focus on the specific case of encryption, and say that a key generation algorithm KeyGen is X-compatible (for X \in {CPA, CCA1, CCA2}) if there exist encryption and decryption algorithms that together with KeyGen, result in an X-secure public-key encryption scheme.

We study the following question: Is every CPA-compatible key generation algorithm also CCA-compatible? We obtain the following answers:

- Every sub-exponentially CPA-compatible KeyGen algorithm is CCA1-compatible, assuming the existence of hinting PRGs and sub-exponentially secure keyless collision resistant hash functions. - Every sub-exponentially CPA-compatible KeyGen algorithm is also CCA2-compatible, assuming the existence of non-interactive CCA2 secure commitments, in addition to sub-exponential security of the assumptions listed in the previous bullet.

Here, sub-exponentially CPA-compatible KeyGen refers to any key generation algorithm for which there exist encryption and decryption algorithms that result in a CPA-secure public-key encryption scheme {\em against sub-exponential adversaries}.

This gives a way to perform CCA secure encryption given any public key infrastructure that has been established with only (sub-exponential) CPA security in mind. The resulting CCA encryption makes black-box use of the CPA scheme and all other underlying primitives.

Post-quantum cryptography or PQC is a trend that has a deserved NIST status, and which aims to be resistant to quantum computer attacks like Shor and Grover algorithms. We choose to follow a non-standard way to achieve PQC: taking any standard asymmetric protocol and replacing numeric field arithmetic with GF-256 field operations. By doing so, it is easy to implement R-propped asymmetric systems as present and former papers show. Here R stands for Rijndael as we work over the AES field. This approach yields secure post-quantum protocols since the resulting multiplicative monoid resists known quantum algorithm and classical linearization attacks like Tsaban Algebraic Span or Romankov linearization attacks. Here we develop an original group-based digital signature protocol and R-propped it. The protocol security relies on the intractability of a generalized discrete log problem, combined with the power sets of algebraic ring extension tensors. The semantic security and classical and quantum security levels are discussed. Finally, we present a numerical example of the proposed protocol.

The CryptoLux group of the University of Luxembourg has a vacancy for a post-doctoral researcher in the area of symmetric cryptography. The successful candidate will contribute to a research project entitled Analysis and Protection of Lightweight Cryptographic Algorithms (APLICA), which is funded by the Luxembourgish Fonds National de la Recherche and the German Research Foundation. Starting in 2021, APLICA will run over a period of 3 years as a joint research project between the CryptoLux group and the Workgroup for Symmetric Cryptography of Ruhr-University Bochum. The mission of the APLICA project is to develop new cryptanalytic techniques for lightweight authenticated encryption algorithms and hash functions, and to design and implement new countermeasures against side-channel attacks that are suitable for constrained devices.

Candidates must have a Ph.D. degree in symmetric cryptography or a closely related field. Preference will be given to candidates with a strong publication record that includes at least one paper at an IACR conference/workshop or one of the top-4 security conferences. Experience in software development for embedded systems or mounting side-channel attacks is a plus. Candidates with an interest to conduct research in one of the following areas are particularly encouraged to apply:

• Cryptanalysis of authenticated encryption algorithms or hash functions
• Leakage resilience or leakage reduction by design (e.g. modes of operation)
• Security evaluation of leakage-resilient primitives or constructions

The position is available from Jan. 2021 on basis of a fixed-term contract for 3 years. The University of Luxembourg offers excellent working conditions and a highly competitive salary. Interested candidates are invited to send their application by email to Alex Biryukov before Apr. 1, 2021 (early submission is strongly encouraged, applications will be processed upon receipt). The application material should contain a cover letter explaining the candidate's research interests, a CV (incl. photo), a list of publications, scans of diploma certificates, and contact details of 3 references.

Closing date for applications:

Contact: Prof. Alex Biryukov (alex.biryukov@uni.lu)

More information: https://www.fnr.lu/projects/analysis-and-protection-of-lightweight-cryptographic-algorithms/

Cryptography and Blockchain research group at Fujitsu Laboratories of America is looking for research interns to work in cutting edge research problems of theoretical and practical interest in the areas of cryptography, security, and privacy. Potential research topics include (but not limited to) homomorphic encryption, lattice cryptography, zero knowledge proofs, memory hard functions, consensus algorithms, etc. A broad overview of our current research efforts is available in the link below.

This is a remote position; we are accepting applications from exceptional graduate students based in USA, UK or Japan. The selected candidate will closely work with researchers based in Sunnyvale, California. We offer attractive remuneration and typical length of internship is 12 weeks. Start date is flexible.

Closing date for applications:

Contact: Avradip Mandal (amandal at fujitsu dot com)

More information: https://www.fujitsu.com/us/about/businesspolicy/tech/rd/research/computer-security/cryptography-and-privacy/

The IMDEA Software Institute offers a postdoc position in the area of security and privacy in blockchain. The work may involve a combination of (i) identification of security threats and privacy leakages in cryptocurrencies (e.g., hardware wallets, layer-2 scalability solutions, cross-chain protocols, cybercrime operations), (ii) design and evaluation of cryptographic protocols to enhance the security, privacy, scalability and interoperability of current cryptocurrencies. The postdoc will work under the supervision of Pedro Moreno-Sánchez and Juan Caballero.

Who should apply?

Applicants should have a PhD in computer science or a related discipline with an excellent track-record and an interest in privacy-enhancing technologies, applied cryptography, and data analysis. Good command of English both spoken and written is required.

Working at IMDEA Software

The position is based in Madrid, Spain where the IMDEA Software Institute is situated. Salaries are internationally competitive and include attractive conditions such as access to an excellent public healthcare system. The working language at the institute is English. Knowledge of Spanish is not required.

Dates

The position is for 2 years. The preferred starting date is June 2021 with some flexibility.

How to apply?

Applicants interested in the position should submit their application at https://careers.software.imdea.org/ using reference code 2021-03-postdoc-spblockchain. Review of applications will begin immediately and close when the position is filled or on April 2nd, 2021.

Closing date for applications:

Contact: pedro.moreno(at)imdea.org and/or juan.caballero(at)imdea.org

More information: https://software.imdea.org/open_positions/2021-03-postdoc-spblockchain.html

Trusted execution enviroments (TEEs) enable secure execution of program on untrusted hosts and cryptographically attest the correctness of outputs. As these are complex systems, it is hard to capture the exact security achieved by protocols employing TEEs. Crucially TEEs are typically employed in multiple protocols at the same time, thus composable security (with global subroutines) is a natural goal for such systems.

We show that under an attested execution setup $\Gatt$ we can realise cryptographic functionalities that are unrealizable in the standard model. We propose a new primitive of Functional Encryption for Stateful and Randomised functionalities (FESR) and an associated protocol, Steel, that realizes it. We show that Steel UC-realises FESR in the universal composition with global subroutines model (TCC 2020). Our work is also a validation of the compositionality of earlier work (Iron}, CCS 2017) capturing (non-stateful) hardware-based functional encryption.

As the existing functionality for attested execution of Pass et al. (Eurocrypt 2017) is too strong for real world use, we propose a weaker functionality that allows the adversary to conduct rollback and forking attacks. We show that the stateful variant of $\Steel$, contrary to the stateless variant corresponding to Iron, is not secure in this setting and propose several mitigation techniques.

Updatable encryption (UE; CRYPTO 2013) is a symmetric encryption primitive that allows to periodically rotate encryption keys without the need to decrypt and re-encrypt already encrypted data. This is achieved by means of an update token that allows to perform the ciphertext update. In existing UE constructions, the update token thereby allows bi-directional updates of keys and ciphertexts, which leads to undesired information leakage and rather involved security models. A recent work by Jiang (ASIACRYPT 2020) shows that in the currently strongest UE model due to Boyd et al. (CRYPTO 2020), UE with bi-directional key and ciphertext updates implies schemes with uni-directional ones. While this might suggests that uni-directionality does not add security, we show that this rather stems from a defective security model and in an adequate model uni-directionality is indeed stronger. Irrespective of this fact, even uni-directional UE schemes still do not capture the intuitive security requirements expected from UE. To overcome this leakage problem and obtain natural security guarantees, UE schemes with so-called no-directional key updates are necessary, i.e., where tokens can solely update ciphertexts and only in one direction. However, it stayed unclear whether such UE schemes can be constructed and this tasks is presented as a challenging open problem in both aforementioned works.

In this work, we resolve these issues and present the first UE constructions with uni- and even no-directional key updates. We show that such UE schemes can be constructed in the standard model via the notion of dual system groups from the standard d-Lin assumption in prime-order bilinear groups. Our approach of constructing UE significantly departs from previous ones and in particular views UE from the perspective of puncturable encryption (Green and Miers, S&P 2015). Towards constructing UE, as an stepping stone, we introduce a variant of puncturable encryption that additionally support puncturing of ciphertexts. This turns out to be a useful abstraction on our way to construct UE and may be of independent interest.

Motivated by new applications such as secure Multi-Party Computation (MPC), Fully Homomorphic Encryption (FHE), and Zero-Knowledge proofs (ZK), the need for symmetric encryption schemes that minimize the number of field multiplications in their natural algorithmic description is apparent. This development has brought forward many dedicated symmetric encryption schemes that minimize the number of multiplications in GF(2^n) or GF(p), with p being prime. These novel schemes have lead to new cryptanalytic insights that have broken many of said schemes. Interestingly, to the best of our knowledge, all of the newly proposed schemes that minimize the number of multiplications use those multiplications exclusively in S-boxes based on a power mapping that is typically x^3 or x^{-1}. Furthermore, most of those schemes rely on complex and resource-intensive linear layers to achieve a low multiplication count.

In this paper, we present Ciminion, an encryption scheme minimizing the number of field multiplications in large binary or prime fields, while using a very lightweight linear layer. In contrast to other schemes that aim to minimize field multiplications in GF(2^n) or GF(p), Ciminion relies on the Toffoli gate to improve the non-linear diffusion of the overall design. In addition, we have tailored the primitive for the use in a Farfalle-like construction in order to minimize the number of rounds of the used primitive, and hence, the number of field multiplications as far as possible.

In this work we present a new construction for a batched Oblivious Pseudorandom Function (OPRF) based on Vector-OLE and the PaXoS data structure. We then use it in the standard transformation for achieving Private Set Intersection (PSI) from an OPRF. Our overall construction is highly efficient with $O(n)$ communication and computation. We demonstrate that our protocol can achieve malicious security at only a very small overhead compared to the semi-honest variant. For input sizes $n = 2^{20}$, our malicious protocol needs 6.2 seconds and less than 59 MB communication. This corresponds to under 450 bits per element, which is the lowest number for any published PSI protocol (semi-honest or malicious) to date. Moreover, in theory our semi-honest (resp. malicious) protocol can achieve as low as 219 (resp. 260) bits per element for $n=2^{20}$ at the added cost of interpolating a polynomial over $n$ elements. As a second contribution, we present an extension where the output of the PSI is secret-shared between the two parties. This functionality is generally referred to as Circuit-PSI. It allows the parties to perform a subsequent MPC protocol on the secret-shared outputs, e.g., train a machine learning model. Our circuit PSI protocol builds on our OPRF construction along with another application of the PaXoS data structure. It achieves semi-honest security and allows for a highly efficient implementation, up to 3x faster than previous work.