International Association
for Cryptologic Research

Public key cryptography is widely used in key exchange and digital signature protocols. Public key cryptography requires expensive primitive operations, such as finite-field and group operations. These finite-field and group operations require a number of clock cycles to exe- cute. By carefully optimizing these primitive operations, public key cryp- tography can be performed with reasonably fast execution timing. In this paper, we present the new implementation result of Curve448 on 32-bit ARM Cortex-M4 microcontrollers. We adopted state-of-art implementa- tion methods, and some previous methods were re-designed to fully uti- lize the features of the target microcontrollers. The implementation was also performed with constant timing by utilizing the features of micro- controllers and algorithms. Finally, the scalar multiplication of Curve448 on 32-bit ARM Cortex-M4@168MHz microcontrollers requires 6,285,904 clock cycles. To the best of our knowledge, this is the first optimized im- plementation of Curve448 on 32-bit ARM Cortex-M4 microcontrollers. The result is also compared with other ECC and post-quantum cryptog- raphy (PQC) implementations. The proposed ECC and the-state-of-art PQC results show the practical usage of hybrid post-quantum TLS on the target processor.

There are two main aims to this paper. Firstly, we survey the relevant existing attack strategies known to apply to the most commonly used lattice-based cryptographic problems as well as to a number of their variants. In particular, we consider attacks against problems in the style of LWE, SIS and NTRU defined over rings of the form $\mathbb{Z}[X]/(f(X), g(X))$, where classically $g(X) = q$ is an integer modulus. We also include attacks on variants which use only large integer arithmetic, corresponding to the degree one case $g(X) = X - c$. Secondly, for each of these approaches we investigate whether they can be generalised to the case of a polynomial modulus $g(X)$ having degree larger than one, thus addressing the security of the generalised cryptographic problems from linear algebra introduced by Bootland et al. We find that some attacks readily generalise to a wide range of parameters while others require very specific conditions to be met in order to work.

Message Authentication Code or MAC, is a well-studied cryptographic primitive that is used in order to authenticate communication between two parties sharing a secret key. A Tokenized MAC or TMAC is a related cryptographic primitive, introduced by Ben-David & Sattath (QCrypt'17) which allows limited signing authority to be delegated to third parties via the use of single-use quantum signing tokens. These tokens can be issued using the secret key, such that each token can be used to sign at most one document. We provide an elementary construction for TMAC based on BB84 states. Our construction can tolerate up to 14% noise, making it the first noise-tolerant TMAC construction. The simplicity of the quantum states required for our construction combined with its noise tolerance, makes it practically more feasible than the previous TMAC construction. The TMAC is existentially unforgeable against adversaries with signing and verification oracles (i.e., analogous to EUF-CMA security for MAC), assuming post-quantum one-way functions exist.

We have multiple open positions for PhD students in the area of symmetric and post-quantum cryptography in the Digital Security group at Radboud University in Nijmegen. The positions cover different topics, ranging from the provable security of modes of use, design of primitives supported by cryptanalysis, post-quantum algorithms and implementations, and protection against implementation attacks based on power, electromagnetic side channel analysis, and fault attacks. For the symmetric crypto topic, we focus on cryptography based on permutations as in the sponge, duplex and farfalle constructions, especially suited for low energy consumption. For the post-quantum cryptography position, a suggestion is to work on isogeny-based crypto but this can be discussed based on a candidate’s background.

The Digital Security Group of Radboud University is one of the leading groups in computer security in The Netherlands and Europe, and one of the pioneers in permutation-based crypto and corresponding leakage-resilient modes.

The successful candidate should ideally have a master in Computer Science, Mathematics, or Electrical engineering. Applications will be considered until the positions are filled.

To apply, please send the following documents to dis-secr (at) cs.ru.nl, with the subject "PhD position in cryptography":
- a motivation letter
- your cv
- your master diploma certificate (scanned)
- transcript of the courses you took (including grades)
- up to 3 references

To enquire about the positions you can contact: Joan Daemen, joan (at) cs.ru.nl, Lejla Batina, lejla (at) cs.ru.nl, and Bart Mennink, b.mennink (at) cs.ru.nl

Closing date for applications:

Contact: dis-secr (at) cs.ru.nl

Applications are invited for a post-doctoral fellow position in one or more of these areas- cryptographic engineering/applied cryptography as it relates to blockchain technology, cryptocurrencies and digital payments. The successful candidate will join Professor Anwar Hasan’s research group at the University of Waterloo. Applicants with a recent Ph.D. in Computer Engineering, Computer Science or a related discipline, and publications at premium venues are encouraged to send pdf copies of their CVs and cover letters via email to Professor Anwar Hasan (ahasan at uwaterloo.ca). Application deadline: November 8, 2021 for full consideration. After this deadline, applications will be processed as they arrive.

Closing date for applications:

Contact: Anwar Hasan

I (Ni Trieu) am looking for 2 Ph.D. students to join my group. An ideal candidate should be interested in security, privacy, applied cryptography. No prior experience in cryptography or security is required. Experience in other areas, including theory, math, database, machine learning, bioinformatics is a plus. If you are interested, please send your CV, transcripts, and everything that you believe will help your application in PDF format to nitrieu@asu.edu. Thank you.
Please see more information at https://nitrieu.github.io/position/.

Closing date for applications:

Contact: Ni Trieu

More information: https://nitrieu.github.io/position/

Place of work: Warsaw, Poland. The newly established IDEAS NCBR center is looking for a position of Research Team Leader dealing with formal modeling and proving the security of cryptographic protocols used in blockchain technology. The research will be carried out in cooperation with the cryptography and blockchain laboratory headed by prof. Stefan Dziembowski at the University of Warsaw. Requirements: • very good knowledge of at least one of the following theorem proving systems: Coq, Easycrypt, Why3, and Isabelle/HOL, • PhD in computer science/mathematics or comparable professional experience, • significant experience in communicating scientific results in English both orally and in writing, • ability to understand scientific papers in English, • experience in working in an international scientific environment. Desirable qualifications: • scientific achievements in the field of automated theorem proving documented by publications, • knowledge of scientific aspects of cryptography and blockchain technology. We offer: • work on very interesting scientific projects with the possibility of implementing the obtained results in practice, • frequent interaction with Prof. S. Dziembowski's scientific team implementing ERC (European Research Council) and NSC (National Science Centre) projects, • opportunity to co-create a scientific team, • form of employment: work contract, • remuneration: PLN 15 000 gross, • the Innovation Bonus - a share in the benefits of future commercialization of the results of a Research Project, constituting an additional remuneration in relation to the basic remuneration. The Innovation Bonus, depending on the adopted model of commercialization of the results of the Research Project, may take the form of: - the right to participate in our income from their commercialization (in particular in the form of a license or disposal of intellectual property rights), or - the right of acquisition of shares or stocks in a spin-out company commercializing such solutions. • medical care • multisport card • group insurance • lunch cards • benefits from the Company Social Benefit Fund • work tools: mobile phone, laptop

Closing date for applications:

Contact: Prof. Stefan Dziembowski

The Department of Mathematical Sciences at NTNU is looking for a post-doc in public-key cryptography. The position is hosted by Jiaxin Pan. It is funded by a project from the Research Council of Norway with focus on provable security. Potential topics are, but not limited to, digital signatures, zero-knowledge proofs, and post-quantum cryptography.

The candidate will work on theoretical aspects of public-key cryptography and is expected to publish at IACR conferences (such as Crypto, Eurocrypt, Asiacrypt, etc.) and renowned security conferences (such as IEEE S&P, ACM CCS, etc.). Thus, a track record of publications at these conferences is expected for the successful candidate.

Further details: The position holder will participate in many activities of the Cryptology Lab (NaCl) at NTNU which has 9 faculty members working on both applied and theoretical aspects of cryptology. The working place is in Trondheim, Norway. Trondheim is a modern European city with a rich cultural scene. It offers great opportunities for education (including international schools) and possibilities to enjoy nature, culture and family life and has low crime rates and clean air quality.

Application: More details are given here: https://www.jobbnorge.no/en/available-jobs/job/213223/postdoctoral-fellow-in-cryptography. We can only accept applications from this jobbnorge.no page.

Application deadline: 7th November 2021.

Starting date: May 2022, but it can be flexible. We encourage candidates who finish their PhD within (or before) 2022 to apply.

Duration: The position is for 3 years. The department might offer you 1 year in addition with teaching duties.

Closing date for applications:

Contact: Jiaxin Pan (first.last@ntnu.no)

More information: https://www.jobbnorge.no/en/available-jobs/job/213223/postdoctoral-fellow-in-cryptography

Cryptography based on the hardness of lattice problems over polynomial rings currently provides the most practical solution for public key encryption in the quantum era. The first encryption scheme utilizing properties of polynomial rings was NTRU (ANTS '98), but in the recent decade, most research has focused on constructing schemes based on the hardness of the somewhat related Ring/Module-LWE problem. Indeed, 14 out of the 17 encryption schemes based on the hardness of lattice problems in polynomial rings submitted to the first round of the NIST standardization process used some version of Ring/Module-LWE, with the other three being based on NTRU.

The preference for using Ring/Module-LWE is due to the fact that this problem is at least as hard as NTRU, is more flexible in the algebraic structure due to the fact that no polynomial division is necessary, and that the decryption error is independent of the message. And indeed, the practical NTRU encryption schemes in the literature generally lag their Ring/Module-LWE counterparts in either compactness or speed, or both.

In this paper, we put the efficiency of NTRU-based schemes on equal (even slightly better, actually) footing with their Ring/Module-LWE counterparts. We provide several instantiations and transformations, with security given in the ROM and the QROM, that detach the decryption error from the message, thus eliminating the adversary's power to have any effect on it, which ultimately allows us to decrease parameter sizes. The resulting schemes are on par, compactness-wise, with their counterparts based on Ring/Module-LWE. Performance-wise, the NTRU schemes instantiated in this paper over NTT-friendly rings of the form $Z_q[X]/(X^d-X^{d/2}+1)$ are the fastest of all public key encryption schemes, whether quantum-safe or not. When compared to the NIST finalist NTRU-HRSS-701, our scheme is $15\%$ more compact and has a $15$X improvement in the round-trip time of ephemeral key exchange, with key generation being $35$X faster, encapsulation being $6$X faster, and decapsulation enjoying a $9$X speedup.

Constructing an efficient CCA-secure KEM is generally done by first constructing a passively-secure PKE scheme, and then applying the Fujisaki-Okamoto (FO) transformation. The original FO transformation was designed to offer security in a single user setting. A stronger notion, known as multi-user security, considers the attacker's advantage in breaking one of many user's ciphertexts. Bellare et al.~(EUROCRYPT 2020) showed that standard single user security implies multi-user security with a multiplicative tightness gap equivalent to the number of users.

To obtain even more confidence in the security of KEMs in the multi-user setting, it is a common design paradigm to also ``domain separate'' the random oracles of each user by including his public key as an input to the hash function. We are not aware of any formal analysis of this technique, but it was at least informally thought to be a computationally cheap way to add security. This design principle was carried over into the FO transformations used by several schemes in the NIST post-quantum standardization effort -- notably the lattice-based schemes Kyber and Saber, which are two of the four KEM finalists.

In this work, we formally analyze domain separation in the context of the FO transformation in the multi-user setting. We first show that including the public key in the hash function is indeed important for the tightness of the security reductions in the ROM and the QROM. At the same time, we show that including the \emph{entire} public key into the hash function is unnecessarily wasteful -- it is enough to include just a small (e.g. $32$ byte) unpredictable part of the key to achieve the same security. Reducing the input of the hash function results in a very noticeable improvement in the running time of the lattice-based KEMs. In particular, using this generic transform results in a 2X - 3X speed-up over the current (Round 3) key generation and encapsulation procedures in Kyber, and up to a $40\%$ improvement in the same functions in Saber.

Proof of liabilities (PoL) allows a prover to prove his/her liabilities to a group of verifiers. This is a cryptographic primitive once used only for proving financial solvency but is also applicable to domains outside finance, including transparent and private donations, new algorithms for disapproval voting and publicly verifiable official reports such as COVID-19 daily cases. These applications share a common nature in incentives: it's not in the prover's interest to increase his/her total liabilities. We generalize PoL for these applications by attempting for the first time to standardize the goals it should achieve from security, privacy and efficiency perspectives. We also propose DAPOL+, a concrete PoL scheme extending the state-of-the-art DAPOL protocol but providing provable security and privacy, with benchmark results demonstrating its practicality. In addition, we explore techniques to provide additional features that might be desired in different applications of PoL and measure the asymptotic probability of failure.

Private set intersection (PSI) allows two mutually distrusting parties each with a set as input, to learn the intersection of both their sets without revealing anything more about their respective input sets. Traditionally, PSI studies the static setting where the computation is performed only once on both parties' input sets. We initiate the study of updatable private set intersection (UPSI), which allows parties to compute the intersection of their private sets on a regular basis with sets that also constantly get updated. We consider two specific settings. In the first setting called UPSI with addition, parties can add new elements to their old sets. We construct two protocols in this setting, one allowing both parties to learn the output and the other only allowing one party to learn the output. In the second setting called UPSI with weak deletion, parties can additionally delete their old elements every $t$ days. We present a protocol for this setting allowing both parties to learn the output. All our protocols are secure against semi-honest adversaries and have the guarantee that both the computational and communication complexity only grow with the set updates instead of the entire sets.

Finally, we implement our UPSI with addition protocols and compare with the state-of-the-art PSI protocols. Our protocols compare favorably when the total set size is sufficiently large, the new updates are sufficiently small, or in networks with low bandwidth.

In this paper, we report the first quantum key-recovery attack on a symmetric block cipher design, using classical queries only, with a more than quadratic time speedup compared to the best classical attack.

We study the 2XOR-Cascade construction of Ga{\v{z}}i and Tessaro (EUROCRYPT~2012). It is a key length extension technique which provides an n-bit block cipher with 5n/2 bits of security out of an n-bit block cipher with 2n bits of key, with a security proof in the ideal model. We show that the offline-Simon algorithm of Bonnetain et al. (ASIACRYPT~2019) can be extended to, in particular, attack this construction in quantum time Õ(2^n), providing a 2.5 quantum speedup over the best classical attack.

Regarding post-quantum security of symmetric ciphers, it is commonly assumed that doubling the key sizes is a sufficient precaution. This is because Grover's quantum search algorithm, and its derivatives, can only reach a quadratic speedup at most. Our attack shows that the structure of some symmetric constructions can be exploited to overcome this limit. In particular, the 2XOR-Cascade cannot be used to generically strengthen block ciphers against quantum adversaries, as it would offer only the same security as the block cipher itself.

We present fully homomorphic encryption schemes for fixed-point arithmetic with fixed precision. Our scheme achieves $\mathsf{IND}$-$\mathsf{CPA^D}$ security and uses $\mathsf{RLWE}$ ring with dimension ${2^{13}}$ or less. Our techniques could also be extended to construct fully homomorphic encryption schemes for approximate numbers with $\mathsf{IND}$-$\mathsf{CPA}$ security. The bootstrapping process of our $\mathsf{IND}$-$\mathsf{CPA}$ scheme preserves about 39-bit precision with ring dimension $2^{13}$, which is the first construction that preserves high precision while keeping the parameters small.

The core technique in this paper is a new and efficient functional bootstrapping algorithm that avoids the negacyclicity constraint of the evaluated functions, which enables us to extract bits blocks homomorphically. This new functional bootstrapping algorithm could be applied to BFV and TFHE schemes as well, and is of independent interest.

The preponderance of smart devices, such as smartphones, has boosted the development and use of mobile applications (apps) in the recent years. This prevalence induces a large volume of mobile app usage data. The analysis of such information could lead to a better understanding of users' behaviours in using the apps they have installed, even more if these data can be coupled with a given context (location, time, date, sociological data...). However, mobile and apps usage data are very sensitive, and are today considered as personal. Their collection and use pose serious concerns associated with individuals' privacy. To reconcile harnessing of data and privacy of users, we investigate in this paper the possibility to conduct privacy-preserving mobile data usage statistics that will prevent any inference or re-identification risks. The key idea is for each user to encrypt their (private and sensitive) inputs before sending them to the data processor. The possibility to perform statistics on those data is then possible thanks to the use of functional encryption, a cryptographic building block permitting to perform some allowed operations over encrypted data. In this paper, we first show how it is possible to obtain such individuals' usage of their apps, which step is necessary for our use case, but can at the same time pose some security problems w.r.t. those apps. We then design our new encryption scheme, adding some fault tolerance property to a recent dynamic decentralized function encryption scheme. We finally show how we have implemented all that, and give some benchmarks.

Cryptanalysis of the LowMC block cipher when the attacker has access to a single known plaintext/ciphertext pair is a mathematically challenging problem. This is because the attacker is unable to employ most of the standard techniques in symmetric cryptography like linear and differential cryptanalysis. This scenario is particularly relevant while arguing the security of the \picnic digital signature scheme in which the plaintext/ciphertext pair generated by the LowMC block cipher serves as the public (verification) key and the corresponding LowMC encryption key also serves as the secret (signing) key of the signature scheme. In the paper by Banik et al. (IACR ToSC 2020:4), the authors used a linearization technique of the LowMC S-box to mount attacks on some instances of the block cipher. In this paper, we first make a more precise complexity analysis of the linearization attack. Then, we show how to perform a 2-stage MITM attack on LowMC. The first stage reduces the key candidates corresponding to a fraction of key bits of the master key. The second MITM stage between this reduced candidate set and the remaining fraction of key bits successfully recovers the master key. We show that the combined computational complexity of both these stages is significantly lower than those reported in the ToSC paper by Banik et al.

BIKE is a Key Encapsulation Mechanism selected as an alternate candidate in NIST’s PQC standardization process, in which performance plays a significant role in the third round. This paper presents FPGA implementations of BIKE with the best area-time performance reported in literature. We optimize two key arithmetic operations, which are the sparse polynomial multiplication and the polynomial inversion. Our sparse multiplier achieves time-constancy for sparse polynomials of indefinite Hamming weight used in BIKE’s encapsulation. The polynomial inversion is based on the extended Euclidean algorithm, which is unprecedented in current BIKE implementations. Our optimized design results in a 5.5 times faster key generation compared to previous implementations based on Fermat’s little theorem.

Besides the arithmetic optimizations, we present a united hardware design of BIKE with shared resources and shared sub-modules among KEM functionalities. On Xilinx Artix-7 FPGAs, our light-weight implementation consumes only 3 777 slices and performs a key generation, encapsulation, and decapsulation in 3 797 µs, 443 µs, and 6 896 µs, respectively. Our high-speed design requires 7 332 slices and performs the three KEM operations in 1 672 µs, 132 µs, and 1 892 µs, respectively.

Blum, Kalai and Wasserman (JACM 2003) gave the first sub-exponential algorithm to solve the Learning Parity with Noise (LPN) problem. In particular, consider the LPN problem with constant noise $\mu=(1-\gamma)/2$. The BKW solves it with space complexity $2^{\frac{(1+\epsilon)n}{\log n}}$ and time/sample complexity $2^{\frac{(1+\epsilon)n}{\log n}}\cdot 2^{O(n^{\frac{1}{1+\epsilon}})}$ for small constant $\epsilon\to 0^+$. We propose a variant of the BKW by tweaking Wagner's generalized birthday problem (Crypto 2002) and adapting the technique to a $c$-ary tree structure. In summary, our algorithm achieves the following:

(Time-space tradeoff). We obtain the same time-space tradeoffs for LPN and LWE as those given by Esser et al. (Crypto 2018), but without resorting to any heuristics. For any $2\leq c\in\mathbb{N}$, our algorithm solves the LPN problem with time/sample complexity $2^{\frac{\log c(1+\epsilon)n}{\log n}}\cdot 2^{O(n^{\frac{1}{1+\epsilon}})}$ and space complexity $2^{\frac{\log c(1+\epsilon)n}{(c-1)\log n}}$, where one can use Grover's quantum algorithm or Dinur et al.'s dissection technique (Crypto 2012) to further accelerate/optimize the time complexity.

(Time/sample optimization). A further adjusted variant of our algorithm solves the LPN problem with sample, time and space complexities all kept at $2^{\frac{(1+\epsilon)n}{\log n}}$ for $\epsilon\to 0^+$, saving factor $2^{\Omega(n^{\frac{1}{1+\epsilon}})}$ in time/sample compared to the original BKW, and the variant of Devadas et al. (TCC 2017). This benefits from a careful analysis of the error distribution among the correlated candidates, and therefore avoids repeating the same process $2^{\Omega(n^{\frac{1}{1+\epsilon}})}$ times on fresh new samples.

(Sample reduction) Our algorithm provides an alternative to Lyubashevsky's BKW variant (RANDOM 2005) for LPN with a restricted amount of samples. In particular, given $Q=n^{1+\epsilon}$ (resp., $Q=2^{n^{\epsilon}}$) samples, our algorithm saves a factor of $2^{\Omega(n)/(\log n)^{1-\kappa}}$ (resp., $2^{\Omega(n^{\kappa})}$) for constant $\kappa \to 1^-$ in running time while consuming roughly the same space, compared with Lyubashevsky's algorithm.

We seek to bridge the gaps between theoretical and heuristic LPN solvers, but take a different approach from Devadas et al. (TCC 2017). We exploit weak yet sufficient conditions (e.g., pairwise independence), and the analysis uses only elementary tools (e.g., Chebyshev's inequality).

We construct efficient functional commitments for all bounded size arithmetic circuits. A (function hiding) functional commitment scheme allows a committer to commit to a secret function f and later prove that y = f(x) for public x and y—without revealing any other information about f. Thus, functional commitments allow the operator of a secret process to prove that the process is being applied uniformly to everyone. Possible applications include bail decisions, credit scores, online ranking algorithms, and proprietary software-as-a-service. To build functional commitments, we introduce a new type of protocol: a proof of function relation (PFR) to show that a committed relation is a function. We show that combining a suitable preprocessing zk-SNARK with a PFR yields a secure functional commitment scheme. We then construct efficient PFRs for two popular preprocessing zk-SNARKs, and obtain two functional commitment schemes for arithmetic circuits. These constructions build on polynomial commitments (a special case of functional commitments), so our work shows that polynomial commitments are “complete” for functional commitments.

IRIF (Institut de Recherche en Informatique Fondamentale, https://www.irif.fr/) will be offering one to two years of postdoc in cryptography, starting October 2022. Topics of interest include, but are not limited to, secure computation, zero-knowledge proofs, post-quantum cryptography, code-based cryptography, and foundational aspects of cryptography (including black-box separations and connections to learning theory). Anyone interested should apply via algocomp-apply (at) irif (dot) fr (see https://www.irif.fr/postes/postdoc for how to apply). The deadline is November 1st, 2021. Further details: IRIF (research institute in theoretical computer science) is a laboratory of the University of Paris. It's the largest TCS lab in France, with more than 90 permanent members and dozens of PhDs & postdocs. It is located in the south of Paris, and is well connected to everything via public transportation.

Closing date for applications:

Contact: Geoffroy Couteau

More information: https://www.irif.fr/postes/postdoc