International Association
for Cryptologic Research

In this work, we present a systematic study of Side-Channel Attacks (SCA) and Fault Injection Attacks (FIA) on structured lattice-based schemes, with main focus on Kyber Key Encapsulation Mechanism (KEM) and Dilithium signature scheme, which are leading candidates in the NIST standardization process for Post-Quantum Cryptography (PQC). Through our study, we attempt to understand the underlying similarities and differences between the existing attacks, while classify them into different categories. Given the wide-variety of reported attacks, simultaneous protection against all the attacks requires to implement customized protections/countermeasures for both Kyber and Dilithium. We therefore present a range of customized countermeasures, capable of providing defenses/mitigations against existing SCA/FIA. Amongst the presented countermeasures, we propose two novel countermeasures to protect Kyber KEM against SCA and FIA assisted chosen-ciphertext attacks. We implement the presented countermeasures within two well-known public software libraries for PQC - (1) pqm4 library for the ARM Cortex-M4 based microcontroller and (2) liboqs library for the Raspberry Pi 3 Model B Plus based on the ARM Cortex-A53 processor. Our performance evaluation reveals that the presented custom countermeasures incur reasonable performance overheads, on both the evaluated embedded platforms. We therefore believe our work argues for usage of custom countermeasures within real-world implementations of lattice-based schemes, either in a standalone manner, or as reinforcements to generic countermeasures such as masking.

This work surveys mathematical aspects of division property, which is a state of the art technique in cryptanalysis of symmetric-key algorithms, such as authenticated encryption, block ciphers and stream ciphers. It aims to find integral distinguishers and cube attacks, which exploit weakness in the algebraic normal forms of the output coordinates of the involved vectorial Boolean functions. Division property can also be used to provide arguments for security of primitives against these attacks.

The focus of this work is a formal presentation of the theory behind the division property, including rigorous proofs, which were often omitted in the existing literature. This survey covers the two major variants of division property, namely conventional and perfect division property. In addition, we explore relationships of the technique with classic degree bounds.

We describe a new paradigm for multi-party private set intersection cardinality (PSI-CA) that allows n parties to compute the intersection size of their datasets without revealing any additional information. We explore a variety of instantiations of this paradigm. Our protocols avoid computationally expensive public-key operations and are secure in the presence of a malicious adversary.

We demonstrate the practicality of our PSI-CA protocol with an implementation. For n = 16 parties with data-sets of 2^20 items each, our server-aided variant takes 71 seconds. Interestingly, in the server-less setting, the same task takes only 7 seconds. To the best of our knowledge, this is the first ‘special purpose’ implementation of a multi-party PSI-CA (i.e., an implementation that does not rely on a generic underlying MPC protocol).

Our PSI-CA protocols can be used to securely compute the dot-product function. The dot-product function takes n binary vectors v1, ..., vn, each of m elements, and outputs the sum of m entries, where the i-th entry is equal the product of the i-th entries in all n input vectors. Importantly, the complexity of our protocol for secure dot-product (where party Pi has a secret vector vi) is linear only in the Hamming weight of the vectors, which is potentially sub-linear in the input size.

We demonstrate that two interesting applications, namely, ‘COVID-19 heatmap’ and ‘associated rule learning (ARL)’, can be computed securely using a dot-product as a building block. We analyse the performance of securely computing Covid-19 heatmap and ARL using our protocol and compare that to the state-of-the-art.

The cryptographic sponge is a popular method for hash function design. The construction is in the ideal permutation model proven to be indifferentiable from a random oracle up to the birthday bound in the capacity of the sponge. This result in particular implies that, as long as the attack complexity does not exceed this bound, the sponge construction achieves a comparable level of collision, preimage, and second preimage resistance as a random oracle. We investigate these state-of-the-art bounds in detail, and observe that while the collision and second preimage security bounds are tight, the preimage bound is not tight. We derive an improved and tight preimage security bound for the cryptographic sponge construction. The result has direct implications for various lightweight cryptographic hash functions. For example, the NIST Lightweight Cryptography finalist Ascon-Hash does not generically achieve $2^{128}$ preimage security as claimed, but even $2^{192}$ preimage security. Comparable improvements are obtained for the modes of Spongent, PHOTON, ACE, and Subterranean 2.0, among others.

The potential advent of large-scale quantum computers in the near future poses a threat to contemporary cryptography. Without doubt, one of the most active and ubiquitous usage of cryptography is currently present in the very vibrant field of cellular networks, i.e., 3G, 4G, 5G and 6G, which is already in the planning phase. The entire cryptography of cellular networks is centered around seven secret-key algorithms $f1,\ldots, f_5, f_1^{*}, f5^{*}$, aggregated into an "authentication and key agreement" algorithm set. Still, these secret key algorithms have not yet been subject to quantum cryptanalysis. Instead, many quantum security considerations for telecommunication networks argue that the threat posed by quantum computers is restricted to public-key cryptography. On the other hand, the only threat to secret-key algorithms would stem from the famous Grover quantum search algorithm, which admits a general square root speedup of all oracle based search problems, thus resulting in an effectively halved key length of the above algorithms. However, various recent works have presented quantum attacks on secret key cryptography that result in more than a quadratic speedup. These attacks call for a re-evaluation of quantum security considerations for cellular networks, encompassing a quantum cryptanalysis of the secret-key primitives used in cellular security. In this paper, we conduct such a quantum cryptanalysis for the Milenage algorithm set, the prevalent instantiation of the seven secret-key algorithms that underpin cellular security. Building upon recent quantum cryptanalytic results, we show attacks that go beyond a quadratic speedup. Concretely, we provide for all Milenage algorithms various quantum attack scenarios, including exponential speedups distinguishable by different quantum attack models. The presented attacks include a polynomial time quantum existential forgery attack, assuming an attacker has access to a superposition oracle of Milenage and key recovery attacks that reduce the security margin beyond the quadratic speedup of Grover. Our results do not constitute an immediate quantum break of the Milenage algorithms, but they do provide strong evidence against choosing Milenage as the cryptographic primitive underpinning the security of quantum resistant telecommunication networks.

The dream of software obfuscation is to take programs, as they are, and then compile them into obfuscated versions that hide their secret inner workings. In this work we investigate notions of obfuscations weaker than virtual black-box (VBB) but which still allow obfuscating cryptographic primitives preserving their original functionalities as much as possible. In particular we propose two new notions of obfuscations, which we call oracle-differing-input obfuscation (odiO) and oracle-indistinguishability obfuscation (oiO). In a nutshell, odiO is a natural strengthening of differing-input obfuscation (diO) and allows obfuscating programs for which it is hard to find a differing-input when given only oracle access to the programs. An oiO obfuscator allows to obfuscate programs that are hard to distinguish when treated as oracles. We then show applications of these notions, as well as positive and negative results around them. A few highlights include: – Our new notions are weaker than VBB and stronger than diO. – As it is the case for VBB, we show that there exist programs that cannot be obfuscated with odiO or oiO. – Our new notions allow to compile several flavours of secret key primitives (e.g., SKE, MAC, designated verifier NIZK) into their public key equivalent (e.g., PKE, signatures, publicly verifiable NIZK) while preserving one of the algorithms of the original scheme (function-preserving), or the structure of their outputs (format-preserving).

The rebound attack was introduced by Mendel et al. at FSE 2009 to fulfill a heavy middle round of a differential path for free, utilizing the degree of freedom from states. The inbound phase was extended to 2 rounds by the Super-Sbox technique invented by Lamberger et al. at ASIACRYPT 2009 and Gilbert and Peyrin at FSE 2010. In ASIACRYPT 2010, Sasaki et al. further reduced the requirement of memory by introducing the non-full-active Super-Sbox. In this paper, we further develop this line of research by introducing Super-Inbound, which is able to connect multiple 1-round or 2-round (non-full-active) Super-Sbox inbound phases by utilizing fully the degrees of freedom from both states and key, yet without the use of large memory. This essentially extends the inbound phase by up to 3 rounds. We applied this technique to find classic or quantum collisions on several AES-like hash functions, and improved the attacked round number by 1 to 5 in targets including AES-128 and SKINNY hashing modes, Saturnin-Hash, and Grostl-512. To demonstrate the correctness of our attacks, the semi-free-start collision on 6-round AES-128-MMO/MP with estimated time complexity $2^{24}$ in classical setting was implemented and an example pair was found instantly on a standard PC.

In 1985, Dolev and Reischuk proved a fundamental communication lower bounds on protocols achieving fault tolerant synchronous broadcast and consensus: any deterministic protocol solving those tasks requires at least a quadratic number of message to be sent by nonfaulty parties. Followup work by Abraham, Chun, Dolev, Nayak, Pass, Ren and Shi shows a similar lower bound for randomized protocols. With the rise of blockchain systems, there have been many real-world systems that achieve consensus with seemingly linear communication per instance. We bridge this discrepancy in two ways. First, we generalize the lower bound to Crusader Broadcast protocols, and to all-but $m$ Crusader Broadcast. Second, we discuss the ways these lower bounds relate to the security of blockchain systems. Specifically, we show how eclipse style attacks in such systems can be viewed as specific instances of Dolev-Reischuk style attacks. Our observation suggests a more systematic way of analyzing and thinking about eclipse style attacks through the lens of the Dolev-Reischuk family of attacks. Finally, we present an example of a simple subquadratic Crusader Broadcast protocol whose security is highly dependent on insights from the presented lower bounds.

WARP is a 128-bit block cipher published by Banik et al. at SAC 2020 as a lightweight alternative to AES. It is based on a generalized Feistel network and achieves the smallest area footprint among 128-bit block ciphers in many settings. Previous analysis results include integral key-recovery attacks on 21 out of 41 rounds.

In this paper, we propose integral key-recovery attacks on up to 32 rounds by improving both the integral distinguisher and the key-recovery approach substantially. For the distinguisher, we show how to model the monomial prediction technique proposed by Hu et al. at ASIACRYPT 2020 as a SAT problem and thus create a bit-oriented model of WARP taking the key schedule into account. Together with two additional observations on the properties of WARP's construction, we extend the best previous distinguisher by 2 rounds (as a classical integral distinguisher) or 4 rounds (for a generalized integral distinguisher). For the key recovery, we create a graph-based model of the round function and demonstrate how to manipulate the graph to obtain a cipher representation amenable to FFT-based key recovery.

The performance of Side-Channel Attacks (SCAs) decays rapidly when considering more sub-keys, making the full-key recovery a very challenging problem. Limited to independent collision information utilization, collision attacks establish the relationship among sub-keys but do not significantly slow down this trend. To solve it, we first exploit the samples from the previously attacked S-boxes to assist attacks on the targeted S-box under an assumption that similar leakage occurs in program loop or code reuse scenarios. The later considered S-boxes are easier to be recovered since more samples participate in this assist attack, which results in the ``snowball'' effect. We name this scheme as Snowball, which significantly slows down the attenuation rate of attack performance. We further introduce confusion coefficient into the collision attack to construct collision confusion coefficient, and deduce its relationship with correlation coefficient. Based on this relationship, we give two optimizations on our Snowball exploiting the ``values'' information and ``rankings'' information of collision correlation coefficients named Least Deviation from Pearson correlation coefficient (PLD) and Least Deviation from confusion coefficient (CLD). Experiments show that the above optimizations significantly improve the performance of our Snowball.

Regev's Learning with Errors (LWE) problem (STOC 2005) is a fundamental hardness assumption for modern cryptography. The Learning with Rounding (LWR) Problem was put forth by Banarjee, Peikert and Rosen (Eurocrypt 2012) as an alternative to LWE, for use in cryptographic situations which require determinism. The only method we currently have for proving hardness of LWR is the so-called "rounding reduction" which is a specific reduction from an analogous LWE problem. This reduction works whenever the LWE error is small relative to the noise introduced by rounding, but it fails otherwise. For this reason, all prior work on establishing hardness of LWR forces the LWE error to be small, either by setting other parameters extremely large (which hurts performance), or by limiting the number of LWR samples seen by the adversary (which rules out certain applications). Hardness of LWR is poorly understood when the LWE modulus ($q$) is polynomial and when the number of LWE samples ($m$) seen by the adversary is an unbounded polynomial. This range of parameters is the most relevant for practical implementations, so the lack of a hardness proof in this situation is not ideal.

In this work, we identify an obstacle for proving the hardness of LWR via a reduction from LWE in the above parameter regime. Specifically, we show that any "point-wise" reduction from LWE to LWR can be used to directly break the corresponding LWE problem. A reduction is "point-wise" if it maps LWE samples to LWR samples one at a time. Our argument goes roughly as follows: first we show that any point-wise reduction from LWE to LWR must have good agreement with some affine map; then we use a Goldreich-Levin-type theorem to extract the LWE secret given oracle access to a point-wise reduction with good affine agreement. Both components may be of independent interest.

The lattice-based cryptography is considered a strong candidate amongst many other proposed quantum-safe schemes for the currently deployed asymmetric cryptosystems that do not seem to stay secure when quantum computers come into play. Lattice-based algorithms possess a time-consuming operation of polynomial multiplication. As it is relatively the highest time-consuming operation in lattice-based cryptosystems, one can obtain fast polynomial multiplication by using number theoretic transform (NTT). In this paper, we focus on and develop a radix-3 NTT polynomial multiplication and compute its computational complexity. In addition, utilizing the ring structure, we propose two parameter sets of CRYSTALS-KYBER, one of the four round-three finalists in the NIST Post-Quantum Competition.

In recent years, several MILP models were introduced to search automatically for boomerang distinguishers and boomerang attacks on block ciphers. However, they can only be used when the key schedule is linear. Here, a new model is introduced to deal with nonlinear key schedules as it is the case for AES. This model is more complex and actually it is too slow for exhaustive search. However, when some hints are added to the solver, it found the current best related-key boomerang attack on AES 192 with $2^{136.4}$ time, $2^{126.2}$ data, and $2^{94.4}$ memory complexities, which is better than the one presented by Biryukov and Khovratovich at ASIACRYPT 2009 with complexities $2^{176}/2^{123}/2^{152}$ respectively. This represents a huge improvement for the time and memory complexity, illustrating the power of MILP in cryptanalysis.

The code-based post-quantum algorithm Hamming Quasi-Cyclic (HQC) is a third round alternative candidate in the NIST standardization project. For their third round version the authors utilize a new combination of error correcting codes, namely a combination of a Reed-Muller and a Reed-Solomon code, which requires an adaption of published attacks. We identify that the power side-channel attack by Uneo et al. from CHES 2021 does not work in practice as they miss the fact that the implemented Reed-Muller decoder does not have a fixed decoding boundary. In this work we provide a novel attack strategy that again allows for a successful attack. Our attack does not rely on simulation to verify it success but is proven with high probability for the HQC parameter sets. In contrast to the timing side-channel attack by Guo et al. we are able to reduce the required attack queries by a factor of 12 and are able to eliminate the inherent uncertainty of their used timing oracle. We show practical attack results utilizing a power side-channel of the used Reed-Solomon decoder on an ARM Cortex-M4 microcontroller. In addition, we provide a discussion on how or whether our attack strategy to be usable with the side-channel targets of mentioned related work. Finally, we use information set decoding to evaluate the remaining attack complexity for partially retrieved secret keys. This work again emphasizes the need for a side-channel secure implementation of all relevant building blocks of HQC.

Technology Innovation Institute (TII) is a publicly funded research institute, based in Abu Dhabi, United Arab Emirates. It is home to a diverse community of leading scientists, engineers, mathematicians, and researchers from across the globe, transforming problems and roadblocks into pioneering research and technology prototypes that help move society ahead.

Cryptography Research Center

In our connected digital world, secure and reliable cryptography is the foundation of digital information security and data integrity. We address the world’s most pressing cryptographic questions. Our work covers post-quantum cryptography, lightweight cryptography, cloud encryption schemes, secure protocols, quantum cryptographic technologies and cryptanalysis.

Position: Post Quantum Cryptography Expert

Study and design post quantum primitives such as PKE, KEM, KEX, and Digital Signatures

Conduct research, with particular focus on how to improve or attack existing proposals

Design new and/or more efficient post quantum Zero Knowledge Proofs

Collaboration and possible participation in NIST proposals

Design and implementation of hybrid (post quantum – classical) solutions

We welcome candidates specializing in lattices and codes. Exceptional candidates with expertise in other areas of PQC are also encouraged

Collaborate with skillful software, hardware, and telecommunication engineers

Attend personalized in-house trainings with top cryptographers and international conferences and workshops

Skills required for the job

A strong publication record in post quantum cryptography

Extensive knowledge on post quantum cryptography

Extensive experience in secure software development

Extensive experience developing in C, C++, or RUST

Willingness to continue learning and push the limits of knowledge

Qualifications

PhD degree in Cryptography, Applied Cryptography, Information Theory and Mathematics, Computer Science or any relevant Engineering degree

Closing date for applications:

Contact:
Mehdi Messaoudi - Talent Acquisition Manager
mehdi.messaoudi@tii.ae

The School of Electrical & Data Engineering is recruiting for two Postdoctoral Research Associates or Postdoctoral Research Fellows to join a multi-disciplinary collaborative research team comprising industry (Bosch) and UTS academics, postdocs and PhD students working on Privacy Preserving Technologies. The position will be based at the centrally located UTS Campus in Ultimo and will report directly to the Director RF Communications Technologies Lab, Associate Professor Justin Lipman

The School of Electrical & Data Engineering is deeply engaged in research of national and international standing in many areas. Key areas include: wireless communications and networking, Internet of Things (IoT), applied electro-magnetics and antennas, electrical systems and power electronics, image processing, computer vision, machine learning, cybersecurity, big data analytics and big data systems, and RF IC design. Our School hosts three IEEE Fellows and 3 ARC DECRA grant holders and we conduct research funded by government agencies and national and international industry partners.

About the role
Conduct research in:
1) Computing on encrypted data technologies in the context of privacy-preserving Federated Learning in particular secure multi-party computation and homomorphic encryption
2) Design and development of trustworthy digital cleanrooms/marketplaces using privacy-preserving computing technologies

About you
• Computer Science or Engineering PhD in cryptographic communication protocols or secure multi-party computation or federated learning.
• Thorough knowledge of the mathematical and statistical foundations of cryptographic systems.
• Proficient in one or more of the following: Rust, Go, C++, C, Python, Java.
• Demonstrated record of research in cryptographic communication protocols or secure multi-party computation.

Closing date for applications:

Contact: A/Prof Justin Lipman
email: justin.lipman@uts.edu.au

More information: https://www.seek.com.au/job/57060632

A candidate will work in the area of post-quantum cryptography. A candidate will conduct research on post-quantum cryptography in term of design and analysis; the emphasis is on quantum analysis. The work requires to carry out some simulations. Applicants are expected to have a PhD degree in Mathematics/Physics/Computer Science and a strong background in quantum algorithm, algebra, linear algebra or algebraic number theory. Preferred candidates are expected to be proficient in Magma software or SAGEMATH software or knowledge on quantum software (eg. Qiskit, etc), a team worker and able to conduct independent research. Interested candidates will kindly include their full CV and transcripts in their applications and send to Dr Chik How Tan, tsltch@nus.edu.sg. Only shortlisted applications will be notified.

Closing date for applications:

Contact: Dr Chik How Tan, tsltch@nus.edu.sg

The rectangle attack has shown to be a very powerful form of cryptanalysis against block ciphers. Given a rectangle distinguisher, one expects to mount key recovery attacks as efficiently as possible. In the literature, there have been four algorithms for rectangle key recovery attacks. However, their performance vary from case to case. Besides, numerous are the applications where the attacks lack optimality. In this paper, we investigate the rectangle key recovery in depth and propose a unified and generic key recovery algorithm, which supports any possible attacking parameters. Notably, it not only covers the four previous rectangle key recovery algorithms, but also unveils five types of new attacks which were missed previously. Along with the new key recovery algorithm, we propose a framework for automatically finding the best attacking parameters, with which the time complexity of the rectangle attack will be minimized using the new algorithm. To demonstrate the efficiency of the new key recovery algorithm, we apply it to Serpent, CRAFT, SKINNY and Deoxys-BC-256 based on existing distinguishers and obtain a series of improved rectangle attacks.

Introducing small errors in the lattice-based key exchange protocols, although it is resistant to quantum computing attacks, will cause both parties to only get roughly equal secret values, which brings uncertainty to the negotiation of the key agreement. The role of the error reconciliation mechanism is to eliminate this uncertainty and ensure that both parties can reach a consensus. This paper designs a new error reconciliation mechanism: Speedy Error Reconciliation (SER), which can efficiently complete key negotiation while ensuring key correctness and security. SER exploits the properties of the approximate secret values σ1 and σ2 shared by the two parties, and simultaneously reconciles the most and least significant bits of the secret value, and a two-bit key can be obtained by one coordination. By sharing g-bit auxiliary information between two entities, SER expands the fault tolerance interval during reconciliation and improves the success rate of consensus. To test the actual performance of SER, we integrate it into key ex- change protocols based on LWE, RLWE, and MLWE, such as Frodo and NewHope. By comparing parameters such as failure rate, security strength, and the number of CPU rounds, we find that SER performs well in various modes, especially in RLWE-based protocol. Since SER doubles the error to reconcile the least significant bit, which in turn leads to a relatively large error in SER; while the RLWE-based key ex- change scheme adopts a polynomial ring and selects a large parameter q, which is very suitable for SER. Compared with Frodo and NewHope, SER improves the reconciliation efficiency of the per-bit key by 61.6% and 797.6%, respectively.

Today, our society produces massive amounts of data, part of which are strictly private. So, a long line of research has worked to design protocols that perform functions on such private data without revealing them. One function that has attracted significant interest is a multi-party private set operation, where each party's input is a set. The parties commonly intend to compute these sets' collective intersection (MPSI) or union (MPSU), which finds uses in various applications, including private scheduling and threat intelligence. Most current protocols use integer-based homomorphic encryption, with large elements and expensive operations, or oblivious transfers, which require communicationally-expensive pairwise interactions between all parties. Thus, existing solutions introduce significant overhead that hinders practical use. This paper considers a certain class of previously-proposed MPSI and MPSU protocols. We propose to express them in terms of new private AND or OR operations among all parties and use elliptic curves to realize these operations efficiently. We achieve a significant performance gain: Firstly, our protocols take only three rounds of communication. Secondly, our constant-time open-source implementation is two orders of magnitude faster than the state-of-the-art MPSI for small universes and outperforms the state-of-the-art MPSI for large universes for three parties or more.