International Association
for Cryptologic Research

In the context of the NIST post-quantum cryptography project, there have been claims that the Gaborit&Aguilar-Melchor patent could apply to the Kyber and Saber encryption schemes. In this short note, we argue that these claims are in contradiction with the potential validity of the patent.

Thermal jitter (phase noise) from a free-running ring oscillator is a common, easily implementable physical randomness source in True Random Number Generators (TRNGs). We show how to evaluate entropy, autocorrelation, and bit pattern distributions of ring oscillator noise sources, even with low jitter levels or some bias. Entropy justification is required in NIST 800-90B and AIS-31 testing and for applications such as the RISC-V entropy source extension. Our numerical evaluation algorithms outperform Monte Carlo simulations in speed and accuracy. We also propose a new lower bound estimation formula for the entropy of ring oscillator sources which applies more generally than previous ones.

We focus on the multiple persistent faults analysis in this paper to fill existing gaps in its application in a variety of scenarios. Our major contributions are twofold. First, we propose a novel technique to apply persistent fault apply in the multiple persistent faults setting that decreases the number of survived keys and the required data. We demonstrate that by utilizing 1509 and 1448 ciphertexts, the number of survived keys after performing persistent fault analysis on AES in the presence of eight and sixteen faults can be reduced to only $2^9$ candidates, whereas the best known attacks need 2008 and 1643 ciphertexts, respectively, with a time complexity of $2^{50}$. Second, we develop generalized frameworks for retrieving the key in the ciphertext-only model. Our methods for both performing persistent fault attacks and key-recovery processes are highly flexible and provide a general trade-off between the number of required ciphertexts and the time complexity. To break AES with 16 persistent faults in the Sbox, our experiments show that the number of required ciphertexts can be decreased to 477 while the attack is still practical with respect to the time complexity. To confirm the accuracy of our methods, we performed several simulations as well as experimental validations on the ARM Cortex-M4 microcontroller with electromagnetic fault injection on AES and LED, which are two well-known block ciphers to validate the types of faults and the distribution of the number of faults in practice.

Syncing the latest state of a blockchain can be a resource-intensive task, driving (especially mobile) end users towards centralized services offering instant access. To expand full decentralized access to anyone with a mobile phone, we introduce a consensus-agnostic compiler for constructing {\em ultralight clients}, providing secure and highly efficient blockchain syncing via a sequence of SNARK-based state transition proofs, and prove its security formally. Instantiating this, we present Plumo, an ultralight client for the Celo blockchain capable of syncing the latest network state summary in just a few seconds even on a low-end mobile phone. In Plumo, each transition proof covers four months of blockchain history and can be produced for just $25 USD of compute. Plumo achieves this level of efficiency thanks to two new SNARK-friendly constructions, which may also be of independent interest: a new BLS-based offline aggregate multisignature scheme in which signers do not have to know the members of their multisignature group in advance, and a new composite algebraic-symmetric cryptographic hash function.

Recently, motivated by its increased use in real-world applications, there has been a growing interest on the reduction of trust in the generation of the common reference string (CRS) for zero-knowledge (ZK) proofs. This line of research was initiated by the introduction of subversion non-interactive ZK (NIZK) proofs by Bellare et al. (ASIACRYPT'16). Here, the zero-knowledge property needs to hold even in case of a malicious generation of the CRS. Groth et al. (CRYPTO'18) then introduced the notion of updatable zk-SNARKS, later adopted by Lipmaa (SCN'20) to updatable quasi-adaptive NIZK (QA-NIZK) proofs. In contrast to the subversion setting, in the updatable setting one can achieve stronger soundness guarantees at the cost of reintroducing some trust, resulting in a model in between the fully trusted CRS generation and the subversion setting. It is a promising concept, but all previous updatable constructions are ad-hoc and tailored to particular instances of proof systems. Consequently, it is an interesting question whether it is possible to construct updatable ZK primitives in a more modular way from simpler building blocks.

In this work we revisit the notion of trapdoor smooth projective hash functions (TSPHFs) in the light of an updatable CRS. TSPHFs have been introduced by Benhamouda et al. (CRYPTO'13) and can be seen as a special type of a 2-round ZK proof system. In doing so, we first present a framework called lighter TSPHFs (L-TSPHFs). Building upon it, we introduce updatable L-TSPHFs as well as instantiations in bilinear groups. We then show how one can generically construct updatable quasi-adaptive zero-knowledge arguments from updatable L-TSPHFs. Our instantiations are generic and more efficient than existing ones. Finally, we discuss applications of (updatable) L-TSPHFs to efficient (updatable) 2-round ZK arguments as well as updatable password-authenticated key-exchange (uPAKE).

At CANS’20, El Housni and Guillevic introduced a new 2-chain of pairing-friendly elliptic curves for recursive zero-knowledge Succinct Non-interactive ARguments of Knowledge (zk-SNARKs) made of the former BLS12-377 curve (a Barreto–Lynn–Scott curve over a 377- bit prime field) and the new BW6-761 curve (a Brezing–Weng curve of embedding degree 6 over a 761-bit prime field). First we generalise the curve construction, the pairing formulas (e : G1 × G2 → GT ) and the group operations to any BW6 curve defined on top of any BLS12 curve, forming a family of 2-chain pairing-friendly curves. Second, we investigate other possible 2-chain families made on top of the BLS12 and BLS24 curves. We compare BW6 to Cocks–Pinch curves of higher embedding degrees 8 and 12 (CP8, CP12) at the 128-bit security level. We explicit an optimal ate and optimal Tate pairing on our new CP curves. We show that both for BLS12 and BLS24, the BW6 construction always gives the fastest pairing and curve arithmetic compared to Cocks-Pinch curves. Finally, we suggest a short list of curves suitable for Groth16 and KZG-based universal SNARKs and present an optimized implementation of these curves. Based on Groth16 and PlonK (a KZG- based SNARK) implementations, we obtain that the BLS12-377/BW6-761 pair is optimized for the former while the BLS24-315/BW6-672 pair is optimized for the latter.

The Learning with Errors (LWE) problem consists of distinguishing linear equations with noise from uniformly sampled values. LWE enjoys a hardness reduction from worst-case lattice problems, which are believed to be hard for classical and quantum computers. Besides, LWE allows for the construction of a large variety of cryptographic schemes, including fully-homomorphic encryption and attribute-based cryptosystems. Unfortunately, LWE requires large key sizes and computation times. To improve efficiency, Ring-LWE replaces linear equations with noisy ring products. Nowadays, Ring-LWE and its variants are frequently used in the construction of post-quantum secure cryptosystems.

In this survey, we give an overview of the hardness results for LWE and Ring-LWE, aiming to connect both problems and to provide good intuition to the reader. We present a proof of the strongest hardness result for Ring-LWE available the literature, which is a reduction from ideal lattice problems to its decision form. We start by introducing both Ring-LWE and LWE and their mathematical foundations, focusing on lattices and algebraic number theory. Then, we sketch the classical hardness proof for LWE and extend the proof techniques to the ring case. We also introduce informal discussions on parameter choices, weaknesses, related work, and open problems.

In this paper, we study the round complexity of concurrently secure computation protocols in the plain model, without random oracles or assuming the presence of a trusted setup. In the plain model, it is well known that concurrently secure two-party computation with polynomial simulation is impossible to achieve in two rounds. For this reason, we focus on the well-studied notion of security with super-polynomial simulation (SPS). Our main result is the first construction of two-round SPS two-party computation for general functionalities in the plain model. Prior to our work, we only knew three-round constructions [Badrinarayanan et al., TCC 2017] and two-round protocols were not known from any computational assumption. As immediate applications, we establish the feasibility result for a series of cryptographic primitives of interest, such as: Two-round password authentication key exchange (PAKE) in the plain model, two-round concurrent blind signature in the plain model, and two round concurrent computation for quantum circuits (2PQC).

Shannon mutual information is an effective method to analyze the information interaction in a point-to-point communication system. However, it cannot solve the problem of channel capacity in graph structure communication system. This problem make it impossible to use traditional mutual information (TMI) to detect the real information and to measure the information embedded in the graph structure. Therefore, measuring the interaction of graph structure and the degree of privacy leakage has become an emerging and challenging issue to be considered. To solve this issue, we propose a novel structural mutual information (SMI) theory based on structure entropy model and the Shannon mutual information theorem, following by the algorithms for solving SMI. The SMI is used to detect the real network structure and measure the degree of private data leakage in the graph structure. Our work expands the channel capacity of Shannon’s second theorem in graph structure, discusses the correlation properties between SMI and TMI, and concludes that SMI satisfies some basic properties, including symmetry, non-negativity, and so on. Finally, theoretical analysis and example demonstration show that the SMI theory is more effective than the traditional privacy measurement methods to measure the information amount embedded in the graph structure and the overall degree of privacy leakage. It provides feasible theoretical support for the privacy protection technology in the graph structure.

Algorand Foundation invites proposals for the Algorand Centres of Excellence (ACE) programme to build and run multidisciplinary centers which advance research and support applied education in the blockchain and cryptocurrency space.

Proposals for three to five years are accepted from higher education institutions and non-profit research organizations anywhere in the world. The ACE programme is being launched with a budget of 100,000,000 ALGO for the next ten years.

See the ACE website for further details.

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.