[go: up one dir, main page]

What a lovely hat

Is it made out of tin foil?




Dates are inconsistent

Dates are inconsistent

309 results sorted by ID

2024/2046 (PDF) Last updated: 2024-12-18
Decompressing Dilithium's Public Key with Fewer Signatures Using Side Channel Analysis
Ruize Wang, Joel Gärtner, Elena Dubrova
Attacks and cryptanalysis

The CRYSTALS-Dilithium digital signature scheme, selected by NIST as a post-quantum cryptography (PQC) standard under the name ML-DSA, employs a public key compression technique intended for performance optimization. Specifically, the module learning with error instance $({\bf A}, {\bf t})$ is compressed by omitting the low-order bits ${\bf t_0}$ of the vector ${\bf t}$. It was recently shown that knowledge of ${\bf t_0}$ enables more effective side-channel attacks on Dilithium...

2024/1977 (PDF) Last updated: 2024-12-20
Bounded CCA Secure Proxy Re-encryption Based on Kyber
Shingo Sato, Junji Shikata
Public-key cryptography

Proxy re-encryption (PRE) allows semi-honest party (called proxy) to convert a ciphertext under a public key into a ciphertext under another public key. Due to this functionality, there are various applications such as encrypted email forwarding, key escrow, and securing distributed file systems. Meanwhile, post-quantum cryptography (PQC) is one of the most important research areas because development of quantum computers has been advanced recently. In particular, there are many researches...

2024/1957 (PDF) Last updated: 2024-12-03
NICE-PAKE: On the Security of KEM-Based PAKE Constructions without Ideal Ciphers
Nouri Alnahawi, Jacob Alperin-Sheriff, Daniel Apon, Alexander Wiesmaier
Cryptographic protocols

The interest in realizing generic PQC KEM-based PAKEs has increased significantly in the last few years. One such PAKE is the CAKE protocol, proposed by Beguinet et al. (ACNS ’23). However, despite its simple design based on the well-studied PAKE protocol EKE by Bellovin and Merritt (IEEE S&P ’92), both CAKE and its variant OCAKE do not fully protect against quantum adversaries, as they rely on the Ideal Cipher (IC) model. Related and follow-up works, including Pan and Zeng (ASIACRYPT ’23),...

2024/1836 (PDF) Last updated: 2024-11-08
Symmetric Encryption on a Quantum Computer
David Garvin, Oleksiy Kondratyev, Alexander Lipton, Marco Paini
Secret-key cryptography

Classical symmetric encryption algorithms use $N$ bits of a shared secret key to transmit $N$ bits of a message over a one-way channel in an information theoretically secure manner. This paper proposes a hybrid quantum-classical symmetric cryptosystem that uses a quantum computer to generate the secret key. The algorithm leverages quantum circuits to encrypt a message using a one-time pad-type technique whilst requiring a shorter classical key. We show that for an $N$-qubit...

2024/1817 (PDF) Last updated: 2024-11-12
Improved ML-DSA Hardware Implementation With First Order Masking Countermeasure
Kamal Raj, Prasanna Ravi, Tee Kiah Chia, Anupam Chattopadhyay
Implementation

We present the protected hardware implementation of the Module-Lattice-Based Digital Signature Standard (ML-DSA). ML-DSA is an extension of Dilithium 3.1, which is the winner of the Post Quantum Cryptography (PQC) competition in the digital signature category. The proposed design is based on the existing high-performance Dilithium 3.1 design. We implemented existing Dilithium masking gadgets in hardware, which were only implemented in software. The masking gadgets are integrated with the...

2024/1777 (PDF) Last updated: 2024-11-16
Masking Gaussian Elimination at Arbitrary Order, with Application to Multivariate- and Code-Based PQC
Quinten Norga, Suparna Kundu, Uttam Kumar Ojha, Anindya Ganguly, Angshuman Karmakar, Ingrid Verbauwhede
Implementation

Digital signature schemes based on multivariate- and code-based hard problems are promising alternatives for lattice-based signature schemes, due to their smaller signature size. Hence, several candidates in the ongoing additional standardization for quantum secure digital signature (DS) schemes by the National Institute of Standards and Technology (NIST) rely on such alternate hard problems. Gaussian Elimination (GE) is a critical component in the signing procedure of these schemes. In this...

2024/1754 (PDF) Last updated: 2024-10-28
PQNTRU: Acceleration of NTRU-based Schemes via Customized Post-Quantum Processor
Zewen Ye, Junhao Huang, Tianshun Huang, Yudan Bai, Jinze Li, Hao Zhang, Guangyan Li, Donglong Chen, Ray C.C. Cheung, Kejie Huang
Implementation

Post-quantum cryptography (PQC) has rapidly evolved in response to the emergence of quantum computers, with the US National Institute of Standards and Technology (NIST) selecting four finalist algorithms for PQC standardization in 2022, including the Falcon digital signature scheme. The latest round of digital signature schemes introduced Hawk, both based on the NTRU lattice, offering compact signatures, fast generation, and verification suitable for deployment on resource-constrained...

2024/1715 (PDF) Last updated: 2024-10-20
OT-PCA: New Key-Recovery Plaintext-Checking Oracle Based Side-Channel Attacks on HQC with Offline Templates
Haiyue Dong, Qian Guo
Attacks and cryptanalysis

In this paper, we introduce OT-PCA, a novel approach for conducting Plaintext-Checking (PC) oracle based side-channel attacks, specifically designed for Hamming Quasi-Cyclic (HQC). By calling the publicly accessible HQC decoder, we build offline templates that enable efficient extraction of soft information for hundreds of secret positions with just a single PC oracle call. Our method addresses critical challenges in optimizing key-related information extraction, including maximizing...

2024/1517 (PDF) Last updated: 2024-09-30
A Note on the SNOVA Security
Lih-Chung Wang, Chun-Yen Chou, Jintai Ding, Yen-Liang Kuan, Jan Adriaan Leegwater, Ming-Siou Li, Bo-Shu Tseng, Po-En Tseng, Chia-Chun Wang
Attacks and cryptanalysis

SNOVA is one of the submissions in the NIST Round 1 Additional Signature of the Post-Quantum Signature Competition. SNOVA is a UOV variant that uses the noncommutative-ring technique to educe the size of the public key. SNOVA's public key size and signature size are well-balanced and have good performance. Recently, Beullens proposed a forgery attack against SNOVA, pointing out that the parameters of SNOVA can be attacked. Beullens also argued that with some slight adjustments his attacks...

2024/1515 (PDF) Last updated: 2024-09-26
Optimized Software Implementation of Keccak, Kyber, and Dilithium on RV{32,64}IM{B}{V}
Jipeng Zhang, Yuxing Yan, Junhao Huang, Çetin Kaya Koç
Implementation

With the standardization of NIST post-quantum cryptographic (PQC) schemes, optimizing these PQC schemes across various platforms presents significant research value. While most existing software implementation efforts have concentrated on ARM platforms, research on PQC implementations utilizing various RISC-V instruction set architectures (ISAs) remains limited. In light of this gap, this paper proposes comprehensive and efficient optimizations of Keccak, Kyber, and Dilithium on...

2024/1513 (PDF) Last updated: 2024-10-07
Depth Optimized Circuits for Lattice Based Voting with Large Candidate Sets
Oskar Goldhahn, Kristian Gjøsteen
Cryptographic protocols

Homomorphic encryption has long been used to build voting schemes. Additively homomorphic encryption only allows simple count- ing functions. Lattice-based fully (or somewhat) homomorphic encryp- tion allows more general counting functions, but the required parameters quickly become impractical if used naively. It is safe to leak information during the counting function evaluation, as long as the information could be derived from the public result. To exploit this observation, we...

2024/1404 (PDF) Last updated: 2024-09-09
$\Pi$-signHD: A New Structure for the SQIsign Family with Flexible Applicability
Kaizhan Lin, Weize Wang, Chang-An Zhao, Yunlei Zhao
Implementation

Digital signature is a fundamental cryptographic primitive and is widely used in the real world. Unfortunately, the current digital signature standards like EC-DSA and RSA are not quantum-resistant. Among post-quantum cryptography (PQC), isogeny-based signatures preserve some advantages of elliptic curve cryptosystems, particularly offering small signature sizes. Currently, SQIsign and its variants are the most promising isogeny-based digital signature schemes. In this paper, we propose a...

2024/1374 (PDF) Last updated: 2024-11-25
Lifting approach against the SNOVA scheme
Shuhei Nakamura, Yusuke Tani, Hiroki Furue
Attacks and cryptanalysis

In 2022, Wang et al. proposed the multivariate signature scheme SNOVA as a UOV variant over the non-commutative ring of $\ell \times \ell $ matrices over $\mathbb{F}_q$. This scheme has small public key and signature size and is a first round candidate of NIST PQC additional digital signature project. Recently, Ikematsu and Akiyama, and Li and Ding show that the core matrices of SNOVA with $v$ vinegar-variables and $o$ oil-variables are regarded as the representation matrices of UOV with...

2024/1345 (PDF) Last updated: 2024-08-30
SoK: The Engineer’s Guide to Post-Quantum Cryptography for Embedded Devices
Maximilian Pursche, Nikolai Puch, Sebastian N. Peters, Michael P. Heinl
Applications

Embedded systems are flexible and cost-effective and thus have found a use case in almost every part of our daily lives. Due to their widespread use, they have also become valuable targets for cyber attacks. However, translating cutting-edge cyber security from servers and desktops to the embedded realm can be challenging due to the limited computational power and memory of embedded devices. Although quantum computing is still in early research and development, it threatens to break...

2024/1282 (PDF) Last updated: 2024-09-02
NTRU+PKE: Efficient Public-Key Encryption Schemes from the NTRU Problem
Jonghyun Kim, Jong Hwan Park
Public-key cryptography

We propose a new NTRU-based Public-Key Encryption (PKE) scheme called $\mathsf{NTRU+}\mathsf{PKE}$, which effectively incorporates the Fujisaki-Okamoto transformation for PKE (denoted as $\mathsf{FO}_{\mathsf{PKE}}$) to achieve chosen-ciphertext security in the Quantum Random Oracle Model (QROM). While $\mathsf{NTRUEncrypt}$, a first-round candidate in the NIST PQC standardization process, was proven to be chosen-ciphertext secure in the Random Oracle Model (ROM), it lacked corresponding...

2024/1256 (PDF) Last updated: 2024-08-08
Concrete Analysis of Schnorr-type Signatures with Aborts
Theo Fanuela Prabowo, Chik How Tan
Attacks and cryptanalysis

Lyubashevsky’s signature can be viewed as a lattice-based adapation of the Schnorr signature, with the core difference being the use of aborts during signature generation process. Since the proposal of Lyubashevsky’s signature, a number of other variants of Schnorr-type signatures with aborts have been proposed, both in lattice-based and code-based setting. In this paper, we examine the security of Schnorr-type signature schemes with aborts. We give a detailed analysis of when the expected...

2024/1233 (PDF) Last updated: 2024-08-02
Binding Security of Implicitly-Rejecting KEMs and Application to BIKE and HQC
Juliane Krämer, Patrick Struck, Maximiliane Weishäupl
Public-key cryptography

In this work, we continue the analysis of the binding properties of implicitly-rejecting key-encapsulation mechanisms (KEMs) obtained via the Fujisaki-Okamoto (FO) transform. These binding properties, in earlier literature known under the term robustness, thwart attacks that can arise when using KEMs in larger protocols. Recently, Cremers et al. (ePrint'24) introduced a framework for binding notions, encompassing previously existing but also new ones. While implicitly-rejecting KEMs have...

2024/1206 (PDF) Last updated: 2024-07-26
Applying Post-Quantum Cryptography Algorithms to a DLT-Based CBDC Infrastructure: Comparative and Feasibility Analysis
Daniel de Haro Moraes, Joao Paulo Aragao Pereira, Bruno Estolano Grossi, Gustavo Mirapalheta, George Marcel Monteiro Arcuri Smetana, Wesley Rodrigues, Courtnay Nery Guimarães Jr., Bruno Domingues, Fábio Saito, Marcos Simplício
Implementation

This article presents an innovative project for a Central Bank Digital Currency (CBDC) infrastructure. Focusing on security and reliability, the proposed architecture: (1) employs post-quantum cryptography (PQC) algorithms for long-term security, even against attackers with access to cryptographically-relevant quantum computers; (2) can be integrated with a Trusted Execution Environment (TEE) to safeguard the confidentiality of transaction contents as they are processed by third-parties; and...

2024/1198 (PDF) Last updated: 2024-07-25
ECO-CRYSTALS: Efficient Cryptography CRYSTALS on Standard RISC-V ISA
Xinyi Ji, Jiankuo Dong, Junhao Huang, Zhijian Yuan, Wangchen Dai, Fu Xiao, Jingqiang Lin
Implementation

The field of post-quantum cryptography (PQC) is continuously evolving. Many researchers are exploring efficient PQC implementation on various platforms, including x86, ARM, FPGA, GPU, etc. In this paper, we present an Efficient CryptOgraphy CRYSTALS (ECO-CRYSTALS) implementation on standard 64-bit RISC-V Instruction Set Architecture (ISA). The target schemes are two winners of the National Institute of Standards and Technology (NIST) PQC competition: CRYSTALS-Kyber and CRYSTALS-Dilithium,...

2024/1178 (PDF) Last updated: 2024-07-21
Towards Quantum-Safe Blockchain: Exploration of PQC and Public-key Recovery on Embedded Systems
Dominik Marchsreiter
Applications

Blockchain technology ensures accountability, transparency, and redundancy in critical applications, includ- ing IoT with embedded systems. However, the reliance on public-key cryptography (PKC) makes blockchain vulnerable to quantum computing threats. This paper addresses the urgent need for quantum-safe blockchain solutions by integrating Post- Quantum Cryptography (PQC) into blockchain frameworks. Utilizing algorithms from the NIST PQC standardization pro- cess, we aim to fortify...

2024/1170 (PDF) Last updated: 2024-07-29
Rudraksh: A compact and lightweight post-quantum key-encapsulation mechanism
Suparna Kundu, Archisman Ghosh, Angshuman Karmakar, Shreyas Sen, Ingrid Verbauwhede
Public-key cryptography

Resource-constrained devices such as wireless sensors and Internet of Things (IoT) devices have become ubiquitous in our digital ecosystem. These devices generate and handle a major part of our digital data. In the face of the impending threat of quantum computers on our public-key infrastructure, it is impossible to imagine the security and privacy of our digital world without integrating post-quantum cryptography (PQC) into these devices. Usually, due to the resource constraints of these...

2024/1030 (PDF) Last updated: 2024-06-26
GRASP: Accelerating Hash-based PQC Performance on GPU Parallel Architecture
Yijing Ning, Jiankuo Dong, Jingqiang Lin, Fangyu Zheng, Yu Fu, Zhenjiang Dong, Fu Xiao
Implementation

$SPHINCS^+$, one of the Post-Quantum Cryptography Digital Signature Algorithms (PQC-DSA) selected by NIST in the third round, features very short public and private key lengths but faces significant performance challenges compared to other post-quantum cryptographic schemes, limiting its suitability for real-world applications. To address these challenges, we propose the GPU-based paRallel Accelerated $SPHINCS^+$ (GRASP), which leverages GPU technology to enhance the efficiency of...

2024/927 (PDF) Last updated: 2024-06-12
MATHEMATICAL SPECULATIONS ON CRYPTOGRAPHY
Anjali C B
Foundations

The current cryptographic frameworks like RSA, ECC, and AES are potentially under quantum threat. Quantum cryptographic and post-quantum cryptography are being extensively researched for securing future information. The quantum computer and quantum algorithms are still in the early developmental stage and thus lack scalability for practical application. As a result of these challenges, most researched PQC methods are lattice-based, code-based, ECC isogeny, hash-based, and multivariate...

2024/815 (PDF) Last updated: 2024-05-26
Faster verifications and smaller signatures: Trade-offs for ALTEQ using rejections
Arnaud Sipasseuth
Public-key cryptography

In this paper, we introduce a new probability function parameter in the instantiations of the Goldreich-Micali-Wigderson with Fiat-Shamir and unbalanced challenges used in ALTEQ, a recent NIST PQC candidate in the call for additional signatures. This probability set at 100% does not bring any changes in the scheme, but modifies the public challenge generation process when below 100%, by injecting potential rejections in otherwise completely valid inputs. From a theoretical point of view,...

2024/786 (PDF) Last updated: 2024-05-22
Modelling Ciphers with Overdefined Systems of Quadratic Equations: Application to Friday, Vision, RAIN and Biscuit
Fukang Liu, Mohammad Mahzoun, Willi Meier
Attacks and cryptanalysis

It is well-known that a system of equations becomes easier to solve when it is overdefined. In this work, we study how to overdefine the system of equations to describe the arithmetic oriented (AO) ciphers Friday, Vision, and RAIN, as well as a special system of quadratic equations over $\mathbb F_{2^{\ell}}$ used in the post-quantum signature scheme Biscuit. Our method is inspired by Courtois-Pieprzyk's and Murphy-Robshaw's methods to model AES with overdefined systems of quadratic...

2024/771 (PDF) Last updated: 2024-10-04
SQIsign2D-East: A New Signature Scheme Using 2-dimensional Isogenies
Kohei Nakagawa, Hiroshi Onuki
Public-key cryptography

Isogeny-based cryptography is cryptographic schemes whose security is based on the hardness of a mathematical problem called the isogeny problem, and is attracting attention as one of the candidates for post-quantum cryptography. A representative isogeny-based cryptography is the signature scheme called SQIsign, which was submitted to the NIST PQC standardization competition. SQIsign has attracted much attention because of its very short signature and key size among the candidates for the...

2024/739 (PDF) Last updated: 2024-05-15
BGJ15 Revisited: Sieving with Streamed Memory Access
Ziyu Zhao, Jintai Ding, Bo-Yin Yang
Implementation

The focus of this paper is to tackle the issue of memory access within sieving algorithms for lattice problems. We have conducted an in-depth analysis of an optimized BGJ sieve (Becker-Gama-Joux 2015), and our findings suggest that its inherent structure is significantly more memory-efficient compared to the asymptotically fastest BDGL sieve (Becker-Ducas-Gama-Laarhoven 2016). Specifically, it necessitates merely $2^{0.2075n + o(n)}$ streamed (non-random) main memory accesses for the...

2024/709 (PDF) Last updated: 2024-09-12
Masked Computation the Floor Function and its Application to the FALCON Signature
Pierre-Augustin Berthet, Justine Paillet, Cédric Tavernier
Public-key cryptography

FALCON is candidate for standardization of the new Post Quantum Cryptography (PQC) primitives by the National Institute of Standards and Technology (NIST). However, it remains a challenge to define efficient countermeasures against side-channel attacks (SCA) for this algorithm. FALCON is a lattice-based signature that relies on rational numbers which is unusual in the cryptography field. While recent work proposed a solution to mask the addition and the multiplication, some roadblocks...

2024/591 (PDF) Last updated: 2024-04-16
Hash your Keys before Signing: BUFF Security of the Additional NIST PQC Signatures
Thomas Aulbach, Samed Düzlü, Michael Meyer, Patrick Struck, Maximiliane Weishäupl
Public-key cryptography

In this work, we analyze the so-called Beyond UnForgeability Features (BUFF) security of the submissions to the current standardization process of additional signatures by NIST. The BUFF notions formalize security against maliciously generated keys and have various real-world use cases, where security can be guaranteed despite misuse potential on a protocol level. Consequently, NIST declared the security against the BUFF notions as desirable features. Despite NIST's interest, only $6$ out of...

2024/585 (PDF) Last updated: 2024-04-29
A Complete Beginner Guide to the Number Theoretic Transform (NTT)
Ardianto Satriawan, Rella Mareta, Hanho Lee
Foundations

The Number Theoretic Transform (NTT) is a powerful mathematical tool that has become increasingly important in developing Post Quantum Cryptography (PQC) and Homomorphic Encryption (HE). Its ability to efficiently calculate polynomial multiplication using the convolution theorem with a quasi-linear complexity $O(n \log{n})$ instead of $O(n^2)$ when implemented with Fast Fourier Transform-style algorithms has made it a key component in modern cryptography. FFT-style NTT algorithm or fast-NTT...

2024/582 (PDF) Last updated: 2024-08-18
Improved Alternating-Moduli PRFs and Post-Quantum Signatures
Navid Alamati, Guru-Vamsi Policharla, Srinivasan Raghuraman, Peter Rindal
Cryptographic protocols

We revisit the alternating-moduli paradigm for constructing symmetric-key primitives with a focus on constructing efficient protocols to evaluate them using secure multi-party computation (MPC). The alternating-moduli paradigm of Boneh, Ishai, Passelègue, Sahai, and Wu (TCC 2018) enables the construction of various symmetric-key primitives with the common characteristic that the inputs are multiplied by two linear maps over different moduli. The first contribution focuses on...

2024/518 (PDF) Last updated: 2024-09-01
Software-Defined Cryptography: A Design Feature of Cryptographic Agility
Jihoon Cho, Changhoon Lee, Eunkyung Kim, Jieun Lee, Beumjin Cho
Foundations

Given the widespread use of cryptography in Enterprise IT, migration to post-quantum cryptography (PQC) is not drop-in replacement at all. Cryptographic agility, or crypto-agility, is a design feature that enables seamless updates to new cryptographic algorithms and standards without the need to modify or replace the surrounding infrastructure. This paper introduces a notion of software-defined cryptography as the desired design feature for crypto-agility, emphasizing the role of software...

2024/401 (PDF) Last updated: 2024-03-05
Plover: Masking-Friendly Hash-and-Sign Lattice Signatures
Muhammed F. Esgin, Thomas Espitau, Guilhem Niot, Thomas Prest, Amin Sakzad, Ron Steinfeld
Public-key cryptography

We introduce a toolkit for transforming lattice-based hash-and-sign signature schemes into masking-friendly signatures secure in the t-probing model. Until now, efficiently masking lattice-based hash-and-sign schemes has been an open problem, with unsuccessful attempts such as Mitaka. A first breakthrough was made in 2023 with the NIST PQC submission Raccoon, although it was not formally proven. Our main conceptual contribution is to realize that the same principles underlying Raccoon...

2024/393 (PDF) Last updated: 2024-08-07
Solving McEliece-1409 in One Day --- Cryptanalysis with the Improved BJMM Algorithm
Shintaro Narisada, Shusaku Uemura, Hiroki Okada, Hiroki Furue, Yusuke Aikawa, Kazuhide Fukushima
Attacks and cryptanalysis

Syndrome decoding problem (SDP) is the security assumption of the code-based cryptography. Three out of the four NIST-PQC round 4 candidates are code-based cryptography. Information set decoding (ISD) is known for the fastest existing algorithm to solve SDP instances with relatively high code rate. Security of code-based cryptography is often constructed on the asymptotic complexity of the ISD algorithm. However, the concrete complexity of the ISD algorithm has hardly ever been known....

2024/367 (PDF) Last updated: 2024-12-06
Accelerating SLH-DSA by Two Orders of Magnitude with a Single Hash Unit
Markku-Juhani O. Saarinen
Implementation

We report on efficient and secure hardware implementation techniques for the FIPS 205 SLH-DSA Hash-Based Signature Standard. We demonstrate that very significant overall performance gains can be obtained from hardware that optimizes the padding formats and iterative hashing processes specific to SLH-DSA. A prototype implementation, SLotH, contains Keccak/SHAKE, SHA2-256, and SHA2-512 cores and supports all 12 parameter sets of SLH-DSA. SLotH also supports side-channel secure PRF computation...

2024/299 (PDF) Last updated: 2024-07-25
Divide and Surrender: Exploiting Variable Division Instruction Timing in HQC Key Recovery Attacks
Robin Leander Schröder, Stefan Gast, Qian Guo
Attacks and cryptanalysis

We uncover a critical side-channel vulnerability in the Hamming Quasi-Cyclic (HQC) round 4 optimized implementation arising due to the use of the modulo operator. In some cases, compilers optimize uses of the modulo operator with compile-time known divisors into constant-time Barrett reductions. However, this optimization is not guaranteed: for example, when a modulo operation is used in a loop the compiler may emit division (div) instructions which have variable execution time depending on...

2024/279 (PDF) Last updated: 2024-03-13
Polynomial-Time Key-Recovery Attack on the ${\tt NIST}$ Specification of ${\tt PROV}$
River Moreira Ferreira, Ludovic Perret
Attacks and cryptanalysis

In this paper, we present an efficient attack against ${\tt PROV}$, a recent variant of the popular Unbalanced Oil and Vinegar (${\tt UOV}$) multivariate signature scheme, that has been submitted to the ongoing ${\tt NIST}$ standardization process for additional post-quantum signature schemes. A notable feature of ${\tt PROV}$ is its proof of security, namely, existential unforgeability under a chosen-message attack (${\tt EUF-CMA}$), assuming the hardness of solving the system formed by the...

2024/195 (PDF) Last updated: 2024-02-09
PQC-AMX: Accelerating Saber and FrodoKEM on the Apple M1 and M3 SoCs
Décio Luiz Gazzoni Filho, Guilherme Brandão, Gora Adj, Arwa Alblooshi, Isaac A. Canales-Martínez, Jorge Chávez-Saab, Julio López
Implementation

As CPU performance is unable to keep up with the dramatic growth of the past few decades, CPU architects are looking into domain-specific architectures to accelerate certain tasks. A recent trend is the introduction of matrix-multiplication accelerators to CPUs by manufacturers such as IBM, Intel and ARM, some of which have not launched commercially yet. Apple's systems-on-chip (SoCs) for its mobile phones, tablets and personal computers include a proprietary, undocumented CPU-coupled matrix...

2024/169 (PDF) Last updated: 2024-02-05
Machine Learning based Blind Side-Channel Attacks on PQC-based KEMs - A Case Study of Kyber KEM
Prasanna Ravi, Dirmanto Jap, Shivam Bhasin, Anupam Chattopadhyay
Attacks and cryptanalysis

Kyber KEM, the NIST selected PQC standard for Public Key Encryption and Key Encapsulation Mechanisms (KEMs) has been subjected to a variety of side-channel attacks, through the course of the NIST PQC standardization process. However, all these attacks targeting the decapsulation procedure of Kyber KEM either require knowledge of the ciphertexts or require to control the value of ciphertexts for key recovery. However, there are no known attacks in a blind setting, where the attacker does not...

2024/166 (PDF) Last updated: 2024-02-05
A Practical MinRank Attack Against VOX
Hao Guo, Jintai Ding
Attacks and cryptanalysis

VOX is a UOV-like signature scheme submitted to Round 1 additional signatures of NIST PQC standardization process. In 2023 Furue and Ikematsu proposed a rectangular MinRank attack on VOX, resulting in the submitters changing their parameters to counter this attack. In this paper we propose a new type of MinRank attack called padded MinRank attack. We show that the attack is highly efficient in its running time, taking less than one minute to break eight of nine parameters and about eight...

2024/150 (PDF) Last updated: 2024-02-02
SALSA FRESCA: Angular Embeddings and Pre-Training for ML Attacks on Learning With Errors
Samuel Stevens, Emily Wenger, Cathy Yuanchen Li, Niklas Nolte, Eshika Saxena, Francois Charton, Kristin Lauter
Attacks and cryptanalysis

Learning with Errors (LWE) is a hard math problem underlying post-quantum cryptography (PQC) systems for key exchange and digital signatures, recently standardized by NIST. Prior work [Wenger et al., 2022; Li et al., 2023a;b] proposed new machine learning (ML)-based attacks on LWE problems with small, sparse secrets, but these attacks require millions of LWE samples to train on and take days to recover secrets. We propose three key methods—better pre-processing, angular embeddings and model...

2024/135 (PDF) Last updated: 2024-11-19
A Closer Look at the Belief Propagation Algorithm in Side-Channel-Assisted Chosen-Ciphertext Attacks
Kexin Qiao, Zhaoyang Wang, Heng Chang, Siwei Sun, Zehan Wu, Junjie Cheng, Changhai Ou, An Wang, Liehuang Zhu
Attacks and cryptanalysis

The implementation security of post-quantum cryptography (PQC) algorithms has emerged as a critical concern with the PQC standardization process reaching its end. In a side-channel-assisted chosen-ciphertext attack, the attacker builds linear inequalities on secret key components and uses the belief propagation (BP) algorithm to solve. The number of inequalities leverages the query complexity of the attack, so the fewer the better. In this paper, we use the PQC standard algorithm...

2024/130 (PDF) Last updated: 2024-01-30
HADES: Automated Hardware Design Exploration for Cryptographic Primitives
Fabian Buschkowski, Georg Land, Jan Richter-Brockmann, Pascal Sasdrich, Tim Güneysu
Implementation

While formal constructions for cryptographic schemes have steadily evolved and emerged over the past decades, the design and implementation of efficient and secure hardware instances is still a mostly manual, tedious, and intuition-driven process. With the increasing complexity of modern cryptography, e.g., Post-Quantum Cryptography (PQC) schemes, and consideration of physical implementation attacks, e.g., Side-Channel Analysis (SCA), the design space often grows exorbitantly without...

2024/112 (PDF) Last updated: 2024-01-25
pqm4: Benchmarking NIST Additional Post-Quantum Signature Schemes on Microcontrollers
Matthias J. Kannwischer, Markus Krausz, Richard Petri, Shang-Yi Yang
Implementation

In July 2022, the US National Institute for Standards and Technology (NIST) announced the first set of Post-Quantum Cryptography standards: Kyber, Dilithium, Falcon, and SPHINCS+. Shortly after, NIST published a call for proposals for additional post-quantum signature schemes to complement their initial portfolio. In 2023, 50 submissions were received, and 40 were accepted as round-1 candidates for future standardization. In this paper, we study the suitability and performance of said...

2024/111 (PDF) Last updated: 2024-01-25
A Novel Power Analysis Attack against CRYSTALS-Dilithium Implementation
Yong Liu, Yuejun Liu, Yongbin Zhou, Yiwen Gao, Zehua Qiao, Huaxin Wang
Attacks and cryptanalysis

Post-Quantum Cryptography (PQC) was proposed due to the potential threats quantum computer attacks against conventional public key cryptosystems, and four PQC algorithms besides CRYSTALS-Dilithium (Dilithium for short) have so far been selected for NIST standardization. However, the selected algorithms are still vulnerable to side-channel attacks in practice, and their physical security need to be further evaluated. This study introduces two efficient power analysis attacks, the optimized...

2024/096 (PDF) Last updated: 2024-01-22
Revisiting the security analysis of SNOVA
Yasuhiko Ikematsu, Rika Akiyama
Attacks and cryptanalysis

SNOVA is a multivariate signature scheme submitted to the ad- ditional NIST PQC standardization project started in 2022. SNOVA is con- structed by incorporating the structure of the matrix ring over a finite field into the UOV signature scheme, and the core part of its public key is the UOV public key whose coefficients consist of matrices. As a result, SNOVA dramatically reduces the public key size compared to UOV. In this paper, we recall the construction of SNOVA, and reconsider its...

2024/076 (PDF) Last updated: 2024-05-07
A provably masked implementation of BIKE Key Encapsulation Mechanism
Loïc Demange, Mélissa Rossi
Public-key cryptography

BIKE is a post-quantum key encapsulation mechanism (KEM) selected for the 4th round of the NIST’s standardization campaign. It relies on the hardness of the syndrome decoding problem for quasi-cyclic codes and on the indistinguishability of the public key from a random element, and provides the most competitive performance among round 4 candidates, which makes it relevant for future real-world use cases. Analyzing its side-channel resistance has been highly encouraged by the community and...

2024/070 (PDF) Last updated: 2024-06-10
Hints from Hertz: Dynamic Frequency Scaling Side-Channel Analysis of Number Theoretic Transform in Lattice-Based KEMs
Tianrun Yu, Chi Cheng, Zilong Yang, Yingchen Wang, Yanbin Pan, Jian Weng
Attacks and cryptanalysis

Number Theoretic Transform (NTT) has been widely used in accelerating computations in lattice-based cryptography. However, attackers can potentially launch power analysis targeting NTT because it is usually the most time-consuming part of the implementation. This extended time frame provides a natural window of opportunity for attackers. In this paper, we investigate the first CPU frequency leakage (Hertzbleed-like) attacks against NTT in lattice-based KEMs. Our key observation is that...

2024/069 (PDF) Last updated: 2024-01-16
SDitH in Hardware
Sanjay Deshpande, James Howe, Jakub Szefer, Dongze Yue
Implementation

This work presents the first hardware realisation of the Syndrome-Decoding-in-the-Head (SDitH) signature scheme, which is a candidate in the NIST PQC process for standardising post-quantum secure digital signature schemes. SDitH's hardness is based on conservative code-based assumptions, and it uses the Multi-Party-Computation-in-the-Head (MPCitH) construction. This is the first hardware design of a code-based signature scheme based on traditional decoding problems and only the second for...

2024/067 (PDF) Last updated: 2024-07-24
A Refined Hardness Estimation of LWE in Two-step Mode
Wenwen Xia, Leizhang Wang, Geng Wang, Dawu Gu, Baocang Wang
Public-key cryptography

Recently, researchers have proposed many LWE estimators, such as lattice-estimator (Albrecht et al, Asiacrypt 2017) and leaky-LWE-Estimator (Dachman-Soled et al, Crypto 2020), while the latter has already been used in estimating the security level of Kyber and Dilithium using only BKZ. However, we prove in this paper that solving LWE by combining a lattice reduction step (by LLL or BKZ) and a target vector searching step (by enumeration or sieving), which we call a Two-step mode, is more...

2024/062 Last updated: 2024-08-05
Double Difficulties, Defense in Depth A succinct authenticated key agreement protocol
WenBin Hsieh

In 2016, NIST announced an open competition with the goal of finding and standardizing a suitable quantum-resistant cryptographic algorithm, with the standard to be drafted in 2023. These algorithms aim to implement post-quantum secure key encapsulation mechanism (KEM) and digital signatures. However, the proposed algorithm does not consider authentication and is vulnerable to attacks such as man-in-the-middle. In this paper, we propose an authenticated key exchange algorithm to solve the...

2024/036 (PDF) Last updated: 2024-01-09
Blink: Breaking Lattice-Based Schemes Implemented in Parallel with Chosen-Ciphertext Attack
Jian Wang, Weiqiong Cao, Hua Chen, Haoyuan Li
Attacks and cryptanalysis

As the message recovery-based attack poses a serious threat to lattice-based schemes, we conducted a study on the side-channel secu- rity of parallel implementations of lattice-based key encapsulation mech- anisms. Initially, we developed a power model to describe the power leakage during message encoding. Utilizing this power model, we pro- pose a multi-ciphertext message recovery attack, which can retrieve the required messages for a chosen ciphertext attack through a suitable mes- sage...

2024/019 (PDF) Last updated: 2024-01-10
Benchmark Performance of Homomorphic Polynomial Public Key Cryptography for Key Encapsulation and Digital Signature Schemes
Randy Kuang, Maria Perepechaenko, Dafu Lou, Brinda Tank
Public-key cryptography

This paper conducts a comprehensive benchmarking analysis of the performance of two innovative cryptographic schemes: Homomorphic Polynomial Public Key (HPPK)-Key Encapsulation Mechanism (KEM) and Digital Signature (DS), recently proposed by Kuang et al. These schemes represent a departure from traditional cryptographic paradigms, with HPPK leveraging the security of homomorphic symmetric encryption across two hidden rings without reliance on NP-hard problems. HPPK can be viewed as a...

2024/002 (PDF) Last updated: 2024-04-09
Fast polynomial multiplication using matrix multiplication accelerators with applications to NTRU on Apple M1/M3 SoCs
Décio Luiz Gazzoni Filho, Guilherme Brandão, Julio López
Implementation

Efficient polynomial multiplication routines are critical to the performance of lattice-based post-quantum cryptography (PQC). As PQC standards only recently started to emerge, CPUs still lack specialized instructions to accelerate such routines. Meanwhile, deep learning has grown immeasurably in importance. Its workloads call for teraflops-level of processing power for linear algebra operations, mainly matrix multiplication. Computer architects have responded by introducing ISA extensions,...

2023/1921 (PDF) Last updated: 2023-12-15
Automated Issuance of Post-Quantum Certificates: a New Challenge
Alexandre Augusto Giron, Frederico Schardong, Lucas Pandolfo Perin, Ricardo Custódio, Victor Valle, Víctor Mateu

The Automatic Certificate Management Environment protocol (ACME) has significantly contributed to the widespread use of digital certificates in safeguarding the authenticity and privacy of Internet data. These certificates are required for implementing the Transport Layer Security (TLS) protocol. However, it is well known that the cryptographic algorithms employed in these certificates will become insecure with the emergence of quantum computers. This study assesses the challenges in...

2023/1889 Last updated: 2024-10-09
Fully Parallel, One-Cycle Random Shuffling for Efficient Countermeasure against Side Channel Attack and its Complexity Verification.
Jong-Yeon Park, Dongsoo Lee, Seonggyeom Kim, Wonil lee, Bo Gyeong Kang, Kouichi Sakurai
Foundations

Hiding countermeasures are the most widely utilized techniques for thwarting side-channel attacks, and their significance has been further emphasized with the advent of Post Quantum Cryptography (PQC) algorithms, owing to the extensive use of vector operations. Commonly, the Fisher-Yates algorithm is adopted in hiding countermeasures with permuted operation for its security and efficiency in implementation, yet the inherently sequential nature of the algorithm imposes limitations on hardware...

2023/1873 (PDF) Last updated: 2024-07-24
SoK: Post-Quantum TLS Handshake
Nouri Alnahawi, Johannes Müller, Jan Oupický, Alexander Wiesmaier
Cryptographic protocols

Transport Layer Security (TLS) is the backbone security protocol of the Internet. As this fundamental protocol is at risk from future quantum attackers, many proposals have been made to protect TLS against this threat by implementing post-quantum cryptography (PQC). The widespread interest in post-quantum TLS has given rise to a large number of solutions over the last decade. These proposals differ in many aspects, including the security properties they seek to protect, the efficiency and...

2023/1850 (PDF) Last updated: 2023-12-01
Accurate Score Prediction for Dual-Sieve Attacks
Léo Ducas, Ludo N. Pulles
Attacks and cryptanalysis

The Dual-Sieve Attack on Learning with Errors (LWE), or more generally Bounded Distance Decoding (BDD), has seen many improvements in the recent years, and ultimately led to claims that it outperforms the primal attack against certain lattice-based schemes in the PQC standardization process organised by NIST. However, the work of Ducas--Pulles (Crypto '23) revealed that the so-called "Independence Heuristic", which all recent dual attacks used, leads to wrong predictions in a contradictory...

2023/1823 (PDF) Last updated: 2023-11-27
PQC-NN: Post-Quantum Cryptography Neural Network
Abel C. H. Chen
Applications

In recent years, quantum computers and Shor’s quantum algorithm have been able to effectively solve NP (Non-deterministic Polynomial-time) problems such as prime factorization and discrete logarithm problems, posing a threat to current mainstream asymmetric cryptography, including RSA and Elliptic Curve Cryptography (ECC). As a result, the National Institute of Standards and Technology (NIST) in the United States call for Post-Quantum Cryptography (PQC) methods that include lattice-based...

2023/1815 (PDF) Last updated: 2023-11-24
Accelerating Polynomial Multiplication for RLWE using Pipelined FFT
Neil Thanawala, Hamid Nejatollahi, Nikil Dutt
Implementation

The evolution of quantum algorithms threatens to break public key cryptography in polynomial time. The development of quantum-resistant algorithms for the post-quantum era has seen a significant growth in the field of post quantum cryptography (PQC). Polynomial multiplication is the core of Ring Learning with Error (RLWE) lattice based cryptography (LBC) which is one of the most promising PQC candidates. In this work, we present the design of fast and energy-efficient pipelined Number...

2023/1812 (PDF) Last updated: 2023-11-23
The NTT and residues of a polynomial modulo factors of $X^{2^d} + 1$
Sahil Sharma
Implementation

The Number Theoretic Transform (NTT) plays a central role in efficient implementations of cryptographic primitives selected for Post Quantum Cryptography. Although it certainly exists, academic papers that cite the NTT omit the connection between the NTT and residues of a polynomial modulo factors of $X^{2^d} + 1$ and mention only the final expressions of what the NTT computes. This short paper establishes that connection and, in doing so, elucidates key aspects of computing the NTT. Based...

2023/1781 (PDF) Last updated: 2023-11-25
A Lattice Attack on CRYSTALS-Kyber with Correlation Power Analysis
Yen-Ting Kuo, Atsushi Takayasu
Attacks and cryptanalysis

CRYSTALS-Kyber is a key-encapsulation mechanism, whose security is based on the hardness of solving the learning-with-errors (LWE) problem over module lattices. As in its specification, Kyber prescribes the usage of the Number Theoretic Transform (NTT) for efficient polynomial multiplication. Side-channel assisted attacks against Post-Quantum Cryptography (PQC) algorithms like Kyber remain a concern in the ongoing standardization process of quantum-computer-resistant cryptosystems. Among the...

2023/1768 (PDF) Last updated: 2023-11-17
Homomorphic Polynomial Public Key Cryptography for Quantum-secure Digital Signature
Randy Kuang, Maria Perepechaenko, Mahmoud Sayed, Dafu Lou
Cryptographic protocols

In their 2022 study, Kuang et al. introduced the Multivariable Polynomial Public Key (MPPK) cryptography, a quantum-safe public key cryptosystem leveraging the mutual inversion relationship between multiplication and division. MPPK employs multiplication for key pair construction and division for decryption, generating public multivariate polynomials. Kuang and Perepechaenko expanded the cryptosystem into the Homomorphic Polynomial Public Key (HPPK), transforming product polynomials over...

2023/1767 (PDF) Last updated: 2024-04-04
The Impact of Hash Primitives and Communication Overhead for Hardware-Accelerated SPHINCS+
Patrick Karl, Jonas Schupp, Georg Sigl
Implementation

SPHINCS+ is a signature scheme included in the first NIST post-quantum standard, that bases its security on the underlying hash primitive. As most of the runtime of SPHINCS+ is caused by the evaluation of several hash- and pseudo-random functions, instantiated via the hash primitive, offloading this computation to dedicated hardware accelerators is a natural step. In this work, we evaluate different architectures for hardware acceleration of such a hash primitive with respect to its...

2023/1760 (PDF) Last updated: 2024-02-11
Biscuit: New MPCitH Signature Scheme from Structured Multivariate Polynomials
Luk Bettale, Delaram Kahrobaei, Ludovic Perret, Javier Verbel
Cryptographic protocols

This paper describes Biscuit, a new multivariate-based signature scheme derived using the MPC-in-the-Head (MPCitH) approach. The security of Biscuit is related to the problem of solving a set of structured quadratic algebraic equations. These equations are highly compact and can be evaluated using very few multiplications (one multiplication per equation). The core of Biscuit is a rather simple MPC protocol for secure multiplications using standard optimized multiplicative triples. This...

2023/1750 (PDF) Last updated: 2024-08-05
A Statistical Verification Method of Random Permutations for Hiding Countermeasure Against Side-Channel Attacks
Jong-Yeon Park, Jang-Won Ju, Wonil Lee, Bo-Gyeong Kang, Yasuyuki Kachi, Kouichi Sakurai
Foundations

As NIST is putting the final touches on the standardization of PQC (Post Quantum Cryptography) public key algorithms, it is a racing certainty that peskier cryptographic attacks undeterred by those new PQC algorithms will surface. Such a trend in turn will prompt more follow-up studies of attacks and countermeasures. As things stand, from the attackers’ perspective, one viable form of attack that can be implemented thereupon is the so-called “side-channel attack”. Two best-known...

2023/1674 (PDF) Last updated: 2024-09-12
Carry Your Fault: A Fault Propagation Attack on Side-Channel Protected LWE-based KEM
Suparna Kundu, Siddhartha Chowdhury, Sayandeep Saha, Angshuman Karmakar, Debdeep Mukhopadhyay, Ingrid Verbauwhede
Attacks and cryptanalysis

Post-quantum cryptographic (PQC) algorithms, especially those based on the learning with errors (LWE) problem, have been subjected to several physical attacks in the recent past. Although the attacks broadly belong to two classes -- passive side-channel attacks and active fault attacks, the attack strategies vary significantly due to the inherent complexities of such algorithms. Exploring further attack surfaces is, therefore, an important step for eventually securing the deployment of these...

2023/1657 (PDF) Last updated: 2023-10-26
PQCMC: Post-Quantum Cryptography McEliece-Chen Implicit Certificate Scheme
Abel C. H. Chen
Public-key cryptography

In recent years, the elliptic curve Qu-Vanstone (ECQV) implicit certificate scheme has found application in security credential management systems (SCMS) and secure vehicle-to-everything (V2X) communication to issue pseudonymous certificates. However, the vulnerability of elliptic-curve cryptography (ECC) to polynomial-time attacks posed by quantum computing raises concerns. In order to enhance resistance against quantum computing threats, various post-quantum cryptography methods have been...

2023/1617 (PDF) Last updated: 2024-09-15
Designing Efficient and Flexible NTT Accelerators
Ahmet MALAL
Implementation

The Number Theoretic Transform (NTT) is a powerful mathematical tool with a wide range of applications in various fields, including signal processing, cryptography, and error correction codes. In recent years, there has been a growing interest in efficiently implementing the NTT on hardware platforms for lattice-based cryptography within the context of NIST's Post-Quantum Cryptography (PQC) competition. The implementation of NTT in cryptography stands as a pivotal advancement,...

2023/1541 (PDF) Last updated: 2023-10-08
TMVP-based Polynomial Convolution for Saber and Sable on GPU using CUDA-cores and Tensor-cores
Muhammad Asfand Hafeez, Wai-Kong Lee, Angshuman Karmakar, Seong Oun Hwang
Implementation

Recently proposed lattice-based cryptography algorithms can be used to protect the IoT communication against the threat from quantum computers, but they are computationally heavy. In particular, polynomial multiplication is one of the most time-consuming operations in lattice-based cryptography. To achieve efficient implementation, the Number Theoretic Transform (NTT) algorithm is an ideal choice, but it has certain limitations on the parameters, which not all lattice-based schemes can...

2023/1539 (PDF) Last updated: 2023-10-07
ELCA: Introducing Enterprise-level Cryptographic Agility for a Post-Quantum Era
Dimitrios Sikeridis, David Ott, Sean Huntley, Shivali Sharma, Vasantha Kumar Dhanasekar, Megha Bansal, Akhilesh Kumar, Anwitha U N, Daniel Beveridge, Sairam Veeraswamy
Implementation

Given the importance of cryptography to modern security and privacy solutions, it is surprising how little attention has been given to the problem of \textit{cryptographic agility}, or frameworks enabling the transition from one cryptographic algorithm or implementation to another. In this paper, we argue that traditional notions of cryptographic agility fail to capture the challenges facing modern enterprises that will soon be forced to implement a disruptive migration from today’s public...

2023/1508 (PDF) Last updated: 2024-02-21
Provable Dual Attacks on Learning with Errors
Amaury Pouly, Yixin Shen
Attacks and cryptanalysis

Learning with Errors (LWE) is an important problem for post-quantum cryptography (PQC) that underlines the security of several NIST PQC selected algorithms. Several recent papers have claimed improvements on the complexity of so-called dual attacks on LWE. These improvements make dual attacks comparable to or even better than primal attacks in certain parameter regimes. Unfortunately, those improvements rely on a number of untested and hard-to-test statistical assumptions. Furthermore, a...

2023/1437 (PDF) Last updated: 2023-10-25
KpqBench: Performance and Implementation Security Analysis of KpqC Competition Round 1 Candidates
YongRyeol Choi, MinGi Kim, YoungBeom Kim, JinGyo Song, JaeHwan Jin, HeeSeok Kim, Seog Chung Seo
Applications

As the global migration to post-quantum cryptography (PQC) continues to progress actively, in Korea, the Post-Quantum Cryptography Research Center has been established to acquire PQC technology, leading the KpqC Competition. In February 2022, the KpqC Competition issued a call for proposals for PQC algorithms. By November 2022, 16 candidates were selected for the first round (7 KEMs and 9 DSAs). Currently, Round 1 submissions are being evaluated with respect to security, efficiency, and...

2023/1427 (PDF) Last updated: 2023-09-21
Efficient Hardware RNS Decomposition for Post-Quantum Signature Scheme FALCON
Samuel Coulon, Pengzhou He, Tianyou Bao, Jiafeng Xie
Implementation

The recently announced National Institute of Standards and Technology (NIST) Post-quantum cryptography (PQC) third-round standardization process has released its candidates to be standardized and Falcon is one of them. On the other hand, however, very few hardware implementation works for Falcon have been released due to its very complicated computation procedure and intensive complexity. With this background, in this paper, we propose an efficient hardware structure to implement residue...

2023/1397 (PDF) Last updated: 2023-09-18
Algebraic Attacks on Round-Reduced RAIN and Full AIM-III
Kaiyi Zhang, Qingju Wang, Yu Yu, Chun Guo, Hongrui Cui
Attacks and cryptanalysis

Picnic is a NIST PQC Round 3 Alternate signature candidate that builds upon symmetric primitives following the MPC-in-the-head paradigm. Recently, researchers have been exploring more secure/efficient signature schemes from conservative one-way functions based on AES, or new low complexity one-way functions like Rain (CCS 2022) and AIM (CCS 2023). The signature schemes based on Rain and AIM are currently the most efficient among MPC-in-the-head-based schemes, making them promising...

2023/1387 (PDF) Last updated: 2023-12-18
Blockwise Rank Decoding Problem and LRPC Codes: Cryptosystems with Smaller Sizes
Yongcheng Song, Jiang Zhang, Xinyi Huang, Wei Wu
Public-key cryptography

In this paper, we initiate the study of the Rank Decoding (RD) problem and LRPC codes with blockwise structures in rank-based cryptosystems. First, we introduce the blockwise errors ($\ell$-errors) where each error consists of $\ell$ blocks of coordinates with disjoint supports, and define the blockwise RD ($\ell$-RD) problem as a natural generalization of the RD problem whose solutions are $\ell$-errors (note that the standard RD problem is actually a special $\ell$-RD problem with...

2023/1368 (PDF) Last updated: 2024-07-24
Towards post-quantum secure PAKE - A tight security proof for OCAKE in the BPR model
Nouri Alnahawi, Kathrin Hövelmanns, Andreas Hülsing, Silvia Ritsch, Alexander Wiesmaier
Cryptographic protocols

We revisit OCAKE (ACNS 23), a generic recipe that constructs password-based authenticated key exchange (PAKE) from key encapsulation mechanisms (KEMs), to allow instantiations with post-quantums KEM like KYBER. The ACNS23 paper left as an open problem to argue security against quantum attackers, with its security proof being in the universal composability (UC) framework. This is common for PAKE, however, at the time of this submission’s writing, it was not known how to prove (computational)...

2023/1293 (PDF) Last updated: 2023-08-29
Applications of Finite non-Abelian Simple Groups to Cryptography in the Quantum Era
María Isabel González Vasco, Delaram Kahrobaei, Eilidh McKemmie
Cryptographic protocols

The theory of finite simple groups is a (rather unexplored) area likely to provide interesting computational problems and modelling tools useful in a cryptographic context. In this note, we review some applications of finite non-abelian simple groups to cryptography and discuss different scenarios in which this theory is clearly central, providing the relevant definitions to make the material accessible to both cryptographers and group theorists, in the hope of stimulating further...

2023/1287 (PDF) Last updated: 2024-02-29
To extend or not to extend: Agile Masking Instructions for PQC
Markus Krausz, Georg Land, Florian Stolz, Dennis Naujoks, Jan Richter-Brockmann, Tim Güneysu, Lucie Kogelheide
Implementation

Splitting up sensitive data into multiple shares – termed masking – has proven an effective countermeasure against various types of Side-Channel Analysis (SCA) on cryptographic implementations. However, in software this approach not only leads to dramatic performance overheads for non-linear operations, but also suffers from microarchitectural leakage, which is hard to avoid. Both problems can be addressed with one solution: masked hardware accelerators. In this context, Gao et al. [GGM+...

2023/1267 (PDF) Last updated: 2024-08-16
Whipping the MAYO Signature Scheme using Hardware Platforms
Florian Hirner, Michael Streibl, Florian Krieger, Ahmet Can Mert, Sujoy Sinha Roy
Implementation

NIST issued a new call in 2023 to diversify the portfolio of quantum-resistant digital signature schemes since the current portfolio relies on lattice problems. The MAYO scheme, which builds on the Unbalanced Oil and Vinegar (UOV) problem, is a promising candidate for this new call. MAYO introduces emulsifier maps and a novel 'whipping' technique to significantly reduce the key sizes compared to previous UOV schemes. This paper provides a comprehensive analysis of the implementation...

2023/1220 (PDF) Last updated: 2024-10-15
Quasilinear Masking to Protect ML-KEM Against Both SCA and FIA
Pierre-Augustin Berthet, Yoan Rougeolle, Cédric Tavernier, Jean-Luc Danger, Laurent Sauvage

The recent technological advances in Post-Quantum Cryptography (PQC) raise the questions of robust implementations of new asymmetric cryptography primitives in today's technology. This is the case for the lattice-based Module Lattice-Key Encapsulation Mechanism (ML-KEM) algorithm which is proposed by the National Institute of Standards and Technology (NIST) as the first standard for Key Encapsulation Mechanism (KEM), taking inspiration from CRYSTALS-Kyber. We must ensure that the ML-KEM...

2023/1194 (PDF) Last updated: 2023-08-06
HI-Kyber: A novel high-performance implementation scheme of Kyber based on GPU
Xinyi Ji, Jiankuo Dong, Pinchang Zhang, Deng Tonggui, Hua Jiafeng, Fu Xiao
Implementation

CRYSTALS-Kyber, as the only public key encryption (PKE) algorithm selected by the National Institute of Standards and Technology (NIST) in the third round, is considered one of the most promising post-quantum cryptography (PQC) schemes. Lattice-based cryptography uses complex discrete alogarithm problems on lattices to build secure encryption and decryption systems to resist attacks from quantum computing. Performance is an important bottleneck affecting the promotion of post quantum...

2023/1188 (PDF) Last updated: 2023-12-03
A Novel CCA Attack for NTRU+ KEM
Joohee Lee, Minju Lee, Hansol Ryu, Jaehui Park
Public-key cryptography

The KpqC competition has begun in 2022, that aims to standardize Post-Quantum Cryptography (PQC) in the Republic of Korea. Among the 16 submissions of the KpqC competition, the lattice-based schemes exhibit the most promising and balanced features in performance. In this paper, we propose an effective classical CCA attack to recover the transmitted session key for NTRU+, one of the lattice-based Key Encapsulation Mechanisms (KEM) proposed in the KpqC competition, for the first time. With the...

2023/1184 (PDF) Last updated: 2023-10-19
STAMP-Single Trace Attack on M-LWE Pointwise Multiplication in Kyber
Bolin Yang, Prasanna Ravi, Fan Zhang, Ao Shen, Shivam Bhasin
Attacks and cryptanalysis

In this work, we propose a novel single-trace key recovery attack targeting side-channel leakage from the key-generation and encryption procedure of Kyber KEM. Our attack exploits the inherent nature of the Module-Learning With Errors (Module-LWE) problem used in Kyber KEM. We demonstrate that the inherent reliance of Kyber KEM on the Module-LWE problem results in higher number of repeated and secret key-related computations, referred to as STAMPs appearing on a single side channel trace,...

2023/1133 (PDF) Last updated: 2023-11-22
Algebraic Attacks on RAIN and AIM Using Equivalent Representations
Fukang Liu, Mohammad Mahzoun, Morten Øygarden, Willi Meier
Attacks and cryptanalysis

Designing novel symmetric-key primitives for advanced protocols like secure multiparty computation (MPC), fully homomorphic encryption (FHE) and zero-knowledge proof systems (ZK), has been an important research topic in recent years. Many such existing primitives adopt quite different design strategies from conventional block ciphers. Notable features include that many of these ciphers are defined over a large finite field, and that a power map is commonly used to construct the nonlinear...

2023/1131 (PDF) Last updated: 2024-05-15
One vector to rule them all: Key recovery from one vector in UOV schemes
Pierre Pébereau
Attacks and cryptanalysis

Unbalanced Oil and Vinegar is a multivariate signature scheme that was introduced in 1999. Most multivariate candidates for signature schemes at NIST's PQC standardization process are either based on UOV or closely related to it. The UOV trapdoor is a secret subspace, the "oil subspace". We show how to recover an equivalent secret key from the knowledge of a single vector in the oil subspace in any characteristic. The reconciliation attack was sped-up by adding some bilinear equations...

2023/1038 (PDF) Last updated: 2023-07-05
PQC Cloudization: Rapid Prototyping of Scalable NTT/INTT Architecture to Accelerate Kyber
Mojtaba Bisheh-Niasar, Daniel Lo, Anjana Parthasarathy, Blake Pelton, Bharat Pillilli, Bryan Kelly
Public-key cryptography

The advent of quantum computers poses a serious challenge to the security of cloud infrastructures and services, as they can potentially break the existing public-key cryptosystems, such as Rivest–Shamir–Adleman (RSA) and Elliptic Curve Cryptography (ECC). Even though the gap between today’s quantum computers and the threats they pose to current public-key cryptography is large, the cloud landscape should act proactively and initiate the transition to the post-quantum era as early as...

2023/994 (PDF) Last updated: 2023-06-26
A proposal for quantum GRS algorithm and the cryptanalysis for ROLLO and RQC
Asuka Wakasugi, Mitsuru Tada
Attacks and cryptanalysis

Code-Based Cryptosystem, CBC, is one of the candidates for Post-Quantum Cryptosystems, PQCs. Its security primarily bases on the Syndrome Decoding Problem, SDP. In this paper, we focus on the rank CBC whose security relies on the rank SDP. The GRS (Gaborit-Ruatta-Schrek) algorithm is well known as the current best decoding algorithm for the rank SDP. We propose the quantum version of the GRS algorithm. Then, we introduce the attack strategy using that quantum algorithm for previous rank...

2023/965 (PDF) Last updated: 2023-06-20
Post-Quantum Secure Over-the-Air Update of Automotive Systems
Joppe W. Bos, Alexander Dima, Alexander Kiening, Joost Renes
Applications

With the announcement of the first winners of the NIST Post-Quantum Cryptography (PQC) competition in 2022, the industry has now a confirmed foundation to revisit established cryptographic algorithms applied in automotive use cases and replace them with quantum-safe alternatives. In this paper, we investigate the application of the NIST competition winner CRYSTALS-Dilithium to protect the integrity and authenticity of over-the-air update packages. We show how this post-quantum secure digital...

2023/887 (PDF) Last updated: 2023-06-09
Pairwise and Parallel: Enhancing the Key Mismatch Attacks on Kyber and Beyond
Mingyao Shao, Yuejun Liu, Yongbin Zhou
Public-key cryptography

Key mismatch attacks resilience is a great concern for KEMs in the NIST PQC standardization process. In key mismatch attacks, the adversary aims to recover the reused key by sending special form of ciphertexts to the target party and observing whether the shared key matches his guesses or not. In this paper, we propose pairwise-parallel key mismatch attacks on Kyber and other lattice-based KEMs. The strategy is to recover partial information about multiple secret key coefficient-pairs in...

2023/850 (PDF) Last updated: 2023-06-06
Revisiting the Constant-sum Winternitz One-time Signature with Applications to SPHINCS+ and XMSS
Kaiyi Zhang, Hongrui Cui, Yu Yu
Public-key cryptography

Hash-based signatures offer a conservative alternative to post-quantum signatures with arguably better-understood security than other post-quantum candidates. As a core building block of hash-based signatures, the efficiency of one-time signature (OTS) largely dominates that of hash-based signatures. The WOTS$^{+}$ signature scheme (Africacrypt 2013) is the current state-of-the-art OTS adopted by the signature schemes standardized by NIST---XMSS, LMS and SPHINCS$^+$. A natural...

2023/830 (PDF) Last updated: 2023-06-06
HPPC: Hidden Product of Polynomial Composition
Borja Gomez Rodriguez
Attacks and cryptanalysis

The article introduces HPPC a new Digital Signature scheme that intends to resist known previous attacks applied to HFE-based schemes like QUARTZ and GeMSS. The idea is to use maximal degree for the central HFE polynomial whereas the trapdoor polynomial has low degree in order to sign messages by finding polynomial roots in an extension field via Berlekamp's algorithm. This work has been submitted to NIST's Post-Quantum Cryptography challenge (PQC) and code is available at...

2023/777 (PDF) Last updated: 2023-09-20
Too Many Hints - When LLL Breaks LWE
Alexander May, Julian Nowakowski
Attacks and cryptanalysis

All modern lattice-based schemes build on variants of the LWE problem. Information leakage of the LWE secret $\mathbf{s} \in \mathbb{Z}_q^n$ is usually modeled via so-called hints, i.e., inner products of $\mathbf{s}$ with some known vector. At Crypto`20, Dachman-Soled, Ducas, Gong and Rossi (DDGR) defined among other so-called perfect hints and modular hints. The trailblazing DDGR framework allows to integrate and combine hints successively into lattices, and estimates the resulting LWE...

2023/739 (PDF) Last updated: 2023-09-13
SMAUG: Pushing Lattice-based Key Encapsulation Mechanisms to the Limits
Jung Hee Cheon, Hyeongmin Choe, Dongyeon Hong, MinJune Yi
Public-key cryptography

Recently, NIST has announced Kyber, a lattice-based key encapsulation mechanism (KEM), as a post-quantum standard. However, it is not the most efficient scheme among the NIST's KEM finalists. Saber enjoys more compact sizes and faster performance, and Mera et al. (TCHES '21) further pushed its efficiency, proposing a shorter KEM, Sable. As KEM are frequently used on the Internet, such as in TLS protocols, it is essential to achieve high efficiency while maintaining sufficient security....

2023/734 (PDF) Last updated: 2023-05-22
TLS → Post-Quantum TLS: Inspecting the TLS landscape for PQC adoption on Android
Dimitri Mankowski, Thom Wiggers, Veelasha Moonsamy
Cryptographic protocols

The ubiquitous use of smartphones has contributed to more and more users conducting their online browsing activities through apps, rather than web browsers. In order to provide a seamless browsing experience to the users, apps rely on a variety of HTTP-based APIs and third-party libraries, and make use of the TLS protocol to secure the underlying communication. With NIST's recent announcement of the first standards for post-quantum algorithms, there is a need to better understand the...

2023/716 (PDF) Last updated: 2023-05-18
Towards High-speed ASIC Implementations of Post-Quantum Cryptography
Malik Imran, Aikata Aikata, Sujoy Sinha Roy, Samuel pagliarini
Implementation

In this brief, we realize different architectural techniques towards improving the performance of post-quantum cryptography (PQC) algorithms when implemented as hardware accelerators on an application-specific integrated circuit (ASIC) platform. Having SABER as a case study, we designed a 256-bit wide architecture geared for high-speed cryptographic applications that incorporates smaller and distributed SRAM memory blocks. Moreover, we have adapted the building blocks of SABER to process...

2023/709 (PDF) Last updated: 2023-05-17
Migrating Applications to Post-Quantum Cryptography: Beyond Algorithm Replacement
Alexandre Augusto Giron
Applications

Post-Quantum Cryptography (PQC) defines cryptographic algorithms designed to resist the advent of the quantum computer. Most public-key cryptosystems today are vulnerable to quantum attackers, so a global-scale transition to PQC is expected. As a result, several entities foment efforts in PQC standardization, research, development, creation of Work Groups (WGs), and issuing adoption recommendations. However, there is a long road to broad PQC adoption in practice. This position paper...

2023/678 (PDF) Last updated: 2023-05-17
A 334µW 0.158mm2 ASIC for Post-Quantum Key-Encapsulation Mechanism Saber with Low-latency Striding Toom-Cook Multiplication Extended Version
Archisman Ghosh, Jose Maria Bermudo Mera, Angshuman Karmakar, Debayan Das, Santosh Ghosh, Ingrid Verbauwhede, Shreyas Sen
Public-key cryptography

The hard mathematical problems that assure the security of our current public-key cryptography (RSA, ECC) are broken if and when a quantum computer appears rendering them ineffective for use in the quantum era. Lattice based cryptography is a novel approach to public key cryptography, of which the mathematical investigation (so far) resists attacks from quantum computers. By choosing a module learning with errors (MLWE) algorithm as the next standard, National Institute of Standard \&...

2023/589 (PDF) Last updated: 2023-04-25
$\texttt{CryptographicEstimators}$: a Software Library for Cryptographic Hardness Estimation
Andre Esser, Javier Verbel, Floyd Zweydinger, Emanuele Bellini
Attacks and cryptanalysis

The estimation of the computational complexity of hard problems is essential for determining secure parameters for cryptographic systems. To date, those estimations are often performed in an ad-hoc manner. This led to a scattered landscape of available estimation scripts, with multiple scripts for the same problem with varying outputs. Overall, this complicates the task of reaching consensus on the hardness of cryptographic problems. Furthermore, for designers it makes it difficult to gather...

2023/506 (PDF) Last updated: 2023-04-13
Energy Consumption Evaluation of Post-Quantum TLS 1.3 for Resource-Constrained Embedded Devices
George Tasopoulos, Charis Dimopoulos, Apostolos P. Fournaris, Raymond K. Zhao, Amin Sakzad, Ron Steinfeld
Cryptographic protocols

Post-Quantum cryptography (PQC), in the past few years, constitutes the main driving force of the quantum resistance transition for security primitives, protocols and tools. TLS is one of the widely used security protocols that needs to be made quantum safe. However, PQC algorithms integration into TLS introduce various implementation overheads compared to traditional TLS that in battery powered embedded devices with constrained resources, cannot be overlooked. While there exist several...

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.