This article discusses the decoding of Gabidulin codes and shows how to extend the usual decoder to any supercode of a Gabidulin code at the cost of a significant decrease of the decoding radius. Using this decoder, we provide polynomial time attacks on the rank metric encryption schemes RAMESSES and LIGA.

Code-based cryptographic schemes are highly regarded among the quantum-safe alternatives to current standards. Yet, designing code-based signatures using traditional methods has always been a challenging task, and current proposals are still far from the target set by other post-quantum primitives (e.g. lattice-based). In this paper, we revisit a recent work using an innovative approach for signing, based on the hardness of the code equivalence problem. We introduce some optimizations and provide a security analysis for all variants considered. We then show that the new parameters produce instances of practical interest.

The security of code-based cryptography usually relies on the hardness of the Syndrome Decoding (SD) problem for the Hamming weight. The best generic algorithms are all improvements of an old algorithm by Prange, and they are known under the name of Information Set Decoding (ISD) algorithms. This work aims to extend ISD algorithms’ scope by changing the underlying weight function and alphabet size of SD. More precisely, we show how to use Wagner’s algorithm in the ISD framework to solve SD for a wide range of weight functions. We also calculate the asymptotic complexities of ISD algorithms, both for the classical and quantum case. We then apply our results to the Lee metric, which is currently receiving a significant amount of attention. By providing the parameters of SD for the Lee weight for which decoding seems to be the hardest, our study could have several applications for designing code-based cryptosystems and their security analysis, especially against quantum adversaries.

The multivariate quadratic polynomial problem (MQ problem) is a fundamental computational problem in post-quantum cryptography. We denote by MQ(q, n, m) the MQ problem of m quadratic equations in n variables over finite field Fq. At PKC 2012, an efficient algorithm for solving the underdetermined MQ(2^r, n, m) for n > m was proposed by Thomae and Wolf (TW algorithm). In PKC 2012, Thomae and Wolf proposed an efficient algorithm (Thomae-Wolf (TW) algorithm) to solve an underdetermined MQ(2^r, n, m), that is, n > m. Specifically, by eliminating the cross-product terms in α quadratic polynomials through linearization, MQ(2^r, n, m) can be reduced to MQ(2^r, m - k - α, m - α), where k is the number of variables fixed in the hybrid approach after the TW algorithm is applied. Then, the algorithm yields the smallest MQ problem for the largest linearization factor α = - 1 among possible α, where b·c is the floor function.
In this study, we propose an algorithm that improves the linearization factor α by combining the hybrid approach and the TW algorithm. In particular, the proposed algorithm can reduce MQ(2^r, n, m) to MQ(2^r, m−k−α_k, m−α_k) with linearization factor α_k = -1. Because α_k ≥ α, the proposed algorithm is more efficient than the TW algorithm for some parameter sets. Furthermore, for the binary field case r = 1, we provide a non-trivial improved algorithm and obtain a larger linearization factor β_k = -1 for suitable k.

Multivariate cryptography is dominated by schemes supporting various tweaks, or "modifiers," designed to patch certain algebraic weaknesses they would otherwise exhibit. Typically these modifiers are linear in nature- either requiring an extra composition with an affine map, or be-ing evaluated by a legitimate user via an affine projection. This description applies to the minus, plus, vinegar and internal perturbation modifiers, to name a few. Though it is well-known that combinations of various modifiers can offer security against certain classes of attacks, cryptanalysts have produced ever more sophisticated attacks against various combinations of these linear modifiers.
In this article, we introduce a more fundamentally nonlinear modifier, called Q, that is inspired from relinearization. The effect of the Q modifier on multivariate digital signature schemes is to maintain inversion efficiency at the cost of slightly slower verification and larger public keys, while altering the algebraic properties of the public key. Thus the Q modifier is ideal for applications of digital signature schemes requiring very fast signing and verification without key transport. As an application of this modifier, we propose new multivariate digital signature schemes with fast signing and verification that are resistant to all known attacks.

The multivariate scheme HFEv- used to be considered a promis-ing candidate for a post-quantum signature system. First suggested in the early 2000s, a version of the scheme made it to the third round of the on-going NIST post-quantum standardization process. In late 2020, the system suffered from an efficient rank attack due to Tao, Petzoldt, and Ding. In this paper, we inspect how this recent rank attack is affected by the projec-tion modification. This modification was introduced to secure the signature scheme PFLASH against its predecessor’s attacks. We prove upper bounds for the rank of projected HFEv- (pHFEv-) and PFLASH under the new at-tack, which are tight for the experiments we have performed. We conclude that projection could be a useful tool in protecting against this recent crypt-analysis.

Ternary LWE, i.e., LWE with coefficients of the secret and the error vectors taken from {−1, 0, 1}, is a popular choice among NTRU-type cryptosystems and some signatures schemes like BLISS and GLP. In this work we consider quantum combinatorial attacks on ternary LWE. Our algorithms are based on the quantum walk framework of Magniez-Nayak-Roland-Santha. At the heart of our algorithms is a combinatorial tool called the representation technique that appears in algorithms for the subset sum problem. This technique can also be applied to ternary LWE resulting in faster attacks. The focus of this work is quantum speed-ups for such representation-based attacks on LWE. When expressed in terms of the search space S for LWE keys, the asymp-totic complexity of the representation attack drops from S^0.24 (classical) down to S^0.19 (quantum). This translates into noticeable attack's speed-ups for concrete NTRU instantiations like NTRU-HRSS [CHES'17] and NTRU Prime [SAC'17].
Our algorithms do not undermine current security claims for NTRU or other ternary LWE based schemes, yet they can lay ground for improvements of the combinatorial subroutines inside hybrid attacks on LWE.

It follows from a result by Friedl, Ivanyos, Magniez, Santha and Sen from 2014 that, for any fixed integer m > 0 (thought of as be-ing small), there exists a quantum algorithm for solving the hidden shift problem in an arbitrary finite abelian group (G, +) with time complexity [poly(log |G|) · 2^{O(log √|mG|}) .] As discussed in the current paper, this can be viewed as a modest statement of Pohlig–Hellman type for hard homogeneous spaces. Our main contribution is a somewhat simpler algorithm achieving the same runtime for m = 2^tp, with t any non-negative integer and p any prime number, where additionally the memory requirements are mostly in terms of quantum random access classical memory; indeed, the amount of qubits that need to be stored is poly(log |G|). Our central tool is an extension of Peik-ert's adaptation of Kuperberg’s collimation sieve to arbitrary finite abelian groups. This allows for a reduction, in said time, to the hidden shift problem in the quotient G/2^tpG, which can then be tackled in polynomial time, by combining methods by Friedl et al. for p-torsion groups and by Bonnetain and Naya-Plasencia for 2^t-torsion groups.

During the Crypto Forum Research Group (CFRG)'s standardization of password-authenticated key exchange (PAKE) protocols, a novel property emerged: a PAKE scheme is said to be "quantum-annoying" if a quantum computer can compromise the security of the scheme, but only by solving one discrete logarithm for each guess of a password. Considering that early quantum computers will likely take quite long to solve even a single discrete logarithm, a quantum-annoying PAKE, combined with a large password space, could delay the need for a post-quantum replacement by years, or even decades.
In this paper, we make the first steps towards formalizing the quantum-annoying property. We consider a classical adversary in an extension of the generic group model in which the adversary has access to an oracle that solves discrete logarithms. While this idealized model does not fully capture the range of operations available to an adversary with a general-purpose quantum computer, this model does allow us to quantify security in terms of the number of discrete logarithms solved. We apply this approach to the CPace protocol, a balanced PAKE advancing through the CFRG standardization process, and show that the CPaceBase variant is secure in the generic group model with a discrete logarithm oracle.

This work introduces the first differential side-channel analysis of the Picnic Signature Scheme, an alternate candidate in the ongoing competition for post-quantum cryptography by the National Institute of Standards and Technology (NIST). We present a successful side-channel analysis of the underlying multiparty implementation of the LowMC block cipher (MPC-LowMC) and show how side-channel information can be used to recover the entire secret key by exploiting two different parts of the algorithm. LowMC key recovery then allows to forge signatures for the calling Picnic post-quantum signature scheme. We target the NIST reference implementation executed on a FRDM-K66F development board. Key recovery succeeds with fewer than 1000 LowMC traces, which can be obtained from fewer than 30 observed Picnic signatures.

We develop and implement efficient Gaussian preimage sampling techniques on module lattices, which rely on the works of Micciancio and Peikert in 2012, and Micciancio and Genise in 2018. The main advantage of our implementation is its modularity, which makes it practical to use for signature schemes, but also for more advanced constructions using trapdoors such as identity-based encryption. In particular, it is easy to use in the ring or module setting, and to modify the arithmetic on R_q (as different schemes have different conditions on q).
Relying on these tools, we also present two instantiations and implementations of proven trapdoor-based signature schemes in the module setting: GPV in the random oracle model and a variant of it in the standard model presented in Bert et al. in 2018. For that last scheme, we address a security issue and correct obsolescence problems in their implementation by building ours from scratch. To the best of our knowledge, this is the first efficient implementation of a lattice-based signature scheme in the standard model. Relying on that last signature, we also present the implementation of a standard model IBE in the module setting. We show that while the resulting schemes may not be competitive with the most efficient NIST candidates, they are practical and run on a standard laptop in acceptable time, which paves the way for practical advanced trapdoor-based constructions.

In this paper, we study implementations of post-quantum signature schemes on resource-constrained devices. We focus on verification of signatures and cover NIST PQC round-3 candidates Dilithium, Falcon, Rainbow, GeMSS, and SPHINCS+. We assume an ARM Cortex-M3 with 8 kB of memory and 8 kB of flash for code; a practical and widely deployed setup in, for example, the automotive sector. This amount of memory is insufficient for most schemes. Rainbow and GeMSS public keys are too big; SPHINCS+ signatures do not fit in this memory. To make signature verification work for these schemes, we stream in public keys and signatures. Due to the memory requirements for efficient Dilithium implementations, we stream in the public key to cache more intermediate results. We discuss the suitability of the signature schemes for streaming, adapt existing implementations, and compare performance.

This paper focuses on high-speed NEON-based constant-time implementations of multiplication of large polynomials in the NIST PQC KEM Finalists: NTRU, Saber, and CRYSTALS-Kyber. We use the Number Theoretic Transform (NTT)-based multiplication in Kyber, the Toom-Cook algorithm in NTRU, and both types of multiplication in Saber. Following these algorithms and using Apple M1, we improve the decapsulation performance of the NTRU, Kyber, and Saber-based KEMs at the security level 3 by the factors of 8.4, 3.0, and 1.6, respectively, compared to the refer-ence implementations. On Cortex-A72, we achieve the speed-ups by factors varying between 5.7 and 7.5× for the Forward/Inverse NTT in Kyber, and between 6.0 and 7.8× for Toom-Cook in NTRU, over the best existing implementations in pure C. For Saber, when using NEON instructions, the implementation based on NTT outperforms the implementation based on the Toom-Cook algorithm by 14% in the case of the MatrixVectorMul function but is slower by 21% in the case of the InnerProduct function. Taking into account that in Saber, keys are not available in the NTT domain, the overall performance of the NTT-based version is very close to the performance of the Toom-Cook version. The differences for the entire decapsulation at the three major security levels (1, 3, and 5) are -4, -2, and +2%, respectively. Our benchmarking results demonstrate that our NEON-based implementa-tions run on an Apple M1 ARM processor are comparable to those obtained using the best AVX2-based implementations run on an Intel Core i7-8750H processor. AMD EPYC 7742 processor. Our work is the first NEON-based ARMv8 implementation of each of the three NIST PQC KEM finalists.

We present an honest-majority Distributed Key Generation protocol (DKG) based on Shamir’s (k,n)-threshold secret sharing in the setting of Very Hard Homogenous Spaces (VHHS). DKGs in the DLOG setting use Pedersen commitments, for which there is no known analogue in the VHHS setting. As a replacement, we introduce a new primitive called piecewise verifiable proofs, which allow a prover to prove that a list of NP-statements is valid with respect to a common witness, and such that the different statements can be verified individually. Our protocol is robust and actively secure in the Quantum Random Oracle Model. For n participants, the total run-time of our protocol is 2 + λ + n(1 + 4λ) group action evaluations, where λ is the underlying security parameter, and is thus independent of the thresh-old k. When instantiated with CSIDH-512, this amounts to approximately 4.5+18n seconds.

At Asiacrypt 2020, Moriya et al. introduced two new IND-CPA secure supersingular isogeny based Public Key Encryption (PKE) protocols: SiGamal and C-SiGamal. Unlike the PKEs canonically derived from SIKE and CSIDH, the new protocols provide IND-CPA security without the use of random oracles. SiGamal and C-SiGamal are however not IND-CCA secure. Moriya et al. suggested a variant of SiGamal that could be IND-CCA secure, but left its study as an open problem.
In this paper, we revisit the protocols introduced by Moriya et al. First, we show that the SiGamal variant suggested by Moriya et al. for IND-CCA security is, in fact, not IND-CCA secure. Secondly, we propose a new isogeny-based PKE protocol named InSIDH, obtained by simplifying SiGamal. In-SIDH has smaller public keys and ciphertexts than (C-)SiGamal and it is more efficient. We prove that InSIDH is IND-CCA secure under CSIDH security assumptions and one Knowledge of Exponent-type assumption we introduce. Interestingly, InSIDH is also much closer to the CSIDH protocol, facilitating a comparison between SiGamal and CSIDH.

The supersingular isogeny-based key encapsulation (SIKE) suite stands as an attractive post-quantum cryptosystem with its relatively small public keys. Public key sizes in SIKE can further be compressed by computing pairings and solving discrete logarithms in certain subgroups of finite fields. This comes at a cost of precomputing and storing large discrete logarithm tables. In this paper, we propose several techniques to optimize memory requirements in computing discrete logarithms in SIKE, and achive to reduce table sizes by a factor of 4. We implement our techniques and verify our theoretical findings.

In 2017, NIST received more than 80 submissions to begin the NIST PQC standardization process. Now four years later, there are 7 finalists and 8 alternates still being evaluated. The 3rd round has been going for one year, and NIST expects to announce which algorithms are selected for standardization in approximately six months. In this talk, I will recap the process and discuss how NIST will approach its decision, as well as look ahead to the future.

Similarly to several other national crypto authorities, the French cybersecurity agency (ANSSI) agrees that the quantum threat should be taken into account in the near future for security products aimed at offering a long lasting protection of information. Thus the question of how to conservatively include post-quantum algorithms in security products is very relevant. In this talk, we will give an outline of ANSSI’s views on the needed gradual transition agenda towards post-quantum security in France, including some positions regarding NIST’s standardization campaign and the short and medium-term necessity of hybridation between pre and post-quantum algorithms.

I review the activities on PQC (including QKD) in Japan academic/industrial research groups. I also review the activities on PQC in CRYPTREC, Cryptography Research and Evaluation Committees, which evaluates and monitors the security of e-Government recommended ciphers in Japan.

Long before NIST’s standardization process comes to a conclusion and standards are being drafted, large parts of the industry already prepare for the adoption of PQC. In this talk, we give some insights into the current state of this adoption and state still open problems. We, for instance, discuss efforts to adapt PQC into industrial standards and applications. Further, we state challenges in the context of secure and efficient implementations and highlight differences between academic research and industrial development in this regard.

The advent of quantum computer is urging security enhancements in various in-dustrial fields. Internet service providers, obligated to provide safe communica-tion services to their subscribers, are rushing to announce quantum security pilot networks and service implementation cases to proactively respond to the quan-tum-threat. PQC (Post Quantum Cryptography) is a next-generation cryptography technology using mathematical difficulties and has the advantage of upgrading the existing security infrastructure and newly applying it to various industrial fields. In this talk, I will introduce a PQC private network pilot service in addition to a PQC-TLS protocol-based application that protect confidential information in the IT and medical fields, which were deployed by LG Uplus.

According to the quantum technology roadmap of global quantum computer vendor such as Google, IBM and IonQ, thousands of qubit quantum processors are expected to be developed in the next few years. But, even if a quantum computer is developed with more qubits than the logical qubit required by Shor algorithm, it won't be able to easily break RSA system on that computer. There is a big difference in the number of qubits and quantum gates on the logical and physical layers.

Motivated by this concern, ETRI started to study quantum security analysis on cryptographic algorithms based on the required quantum resource. ETRI and its collaborating institutes are researching for quantum analysis method for the major cryptographic algorithms (AES, RSA, ECC, NIST round3 PQC, etc.) and developing <Q|Crypton> platform, which is the cryptographic quantum security evaluation platform based on quantum resource estimation. The purpose of the platform is to provide more accurate quantum security of the cryptographic algorithms.

In this talk, I am going to introduce our <Q|Crypton> platform and methodology: visual quantum programming in high-level language with Q-arithmetic library and the detailed quantum resources estimation in logical, FTQC and physical layer.

Lattice problems restricted to module lattices are some of the most common security foundations in post-quantum cryptography. As an example, five out of the seven finalist candidates in the NIST PQC standardisation project have their security that relies on their presumed intractability. These assumptions include NTRU, Ring-LWE/SIS and Module-LWE/SIS, which all depend on a variety of parameters. In this talk, I will provide an overview on module lattice problems used for cryptographic design.

Lattice-based cryptography relies on generating random bases which are difficult to fully reduce. Given a lattice basis (such as the private basis for a cryptosystem), all other bases are related by multiplication by matrices in GL(n, Z). We compare the strengths of various methods to sample random elements of SL(n, Z), finding some are stronger than others with respect to the problem of recognizing rotations of the Zⁿ lattice. In particular, the standard algorithm of multiplying unipotent generators together (as implemented in Magma's RandomSLnZ command) generates instances of this last problem which can be efficiently broken, even in dimensions near-ing 1,500. We also can efficiently break the random basis generation method in one of the NIST Post-Quantum Cryptography competition submissions (DRS). Other random basis generation algorithms (some older, some newer) are described which appear to be much stronger.

Zero-knowledge proofs (ZKP) are a fundamental notion in modern cryptography and an essential building block for countless privacy-preserving constructions. Recent years have witnessed a rapid development in the designs of ZKP for general statements, in which, for a publicly given Boolean function f : {0, 1}ⁿ→ {0, 1}, one’s goal is to prove knowledge of a secret input x ∈ {0, 1}ⁿ satisfying f(x) = b, for a given bit b. Nevertheless, in many interesting application scenarios, not only the input x but also the underlying function f should be kept private. The problem of designing ZKP for the setting where both x and f are hidden, however, has not received much attention.
This work addresses the above-mentioned problem for the class of symmetric Boolean functions, namely, Boolean functions f whose output value is determined solely by the Hamming weight of the n-bit input x. Although this class might sound restrictive, it has exponential cardinality 2ⁿ⁺¹ and captures a number of well-known Boolean functions, such as threshold, sorting and counting functions. Specifically, with respect to a commitment scheme secure under the Learning-Parity-with-Noise (LPN) assumption, we show how to prove in zero-knowledge that f(x) = b, for a committed symmetric function f, a committed input x and a bit b. The security of our protocol relies on that of an auxiliary commitment scheme which can be instantiated under quantum-resistant assumptions (including LPN). The protocol also achieves reasonable communication cost: the variant with soundness error^2−λ has proof size c · λ · n, where c is a relatively small constant. The proto-col can potentially find appealing privacy-preserving applications in the area of post-quantum cryptography, and particularly in code-based cryptography.

We construct a short and adaptively secure identity-based signature scheme tightly based on the well-known Short Integer Solution (SIS) assumption. Although identity-based signature schemes can be tightly constructed from either standard signature schemes against adaptive corruptions in the multi-user setting or a two-level hierarchical identity-based encryption scheme, neither of them is known with short signature size and tight security based on the SIS assumption. Here "short" means the signature size is independent of the message length, which is in contrast to the tree-based (tight) signatures. Our approach consists of two steps: Firstly, we give two generic transformations (one with random oracles and the other without) from non-adaptively secure identity-based signature schemes to adaptively secure ones tightly. Our idea extends the similar transformation for digital signature schemes. Secondly, we construct a non-adaptively secure identitybased signature scheme based on the SIS assumption in the random oracle model.

Digital signatures following the methodology of "Fiat-Shamir with Aborts", proposed by Lyubashevsky, are capable of achieving the smallest public-key and signature sizes among all the existing lattice signature schemes based on the hardness of the Ring-SIS and Ring-LWE problems. Since its introduction, several variants and optimizations have been pro￾posed, and two of them (i.e., Dilithium and qTESLA) entered the second round of the NIST post-quantum cryptography standardization. This method of designing signatures relies on rejection sampling during the signing process. Rejection sampling is crucial for ensuring both the correctness and security of these signature schemes.
In this paper, we investigate the possibility of removing the two rejection conditions used both in Dilithium and qTESLA. First, we show that removing one of the rejection conditions is possible, and provide a variant of Lyubashevsky’s signature with comparable parameters with Dilithium and qTESLA. Second, we give evidence on the difficulty of removing the other rejection condition, by showing that two very general approaches do not yield a signature scheme with correctness or security.

We present chosen-ciphertext secure hybrid encryption systems in the standard model from the learning with errors problem and low-noise learning parity with noise problem. The systems consist of public-key key encapsulation mechanisms that are not chosen-ciphertext secure. The systems are more efficient than the existing chosen-ciphertext secure hybrid encryption encryption systems in the standard model based on the same hard learning problems.

We systematically study the security of twelve Beyond-Birthday-Bound Message Authentication Codes (BBB MACs) in the Q2 model where attackers have quantum-query access to MACs. Assuming the block size of the underlying (tweakable) block cipher is n bits, the security proofs show that they are secure at least up to O(2^2n/3) queries in the classi-cal setting. The best classical attacks need O(2^3n/4) queries. We consider se-cret state recovery against SUM-ECBC-like and PMAC Plus-like MACs and key recovery against PMAC Plus-like MACs. Both attacks lead to success-ful forgeries. The first attack costs O(2^n/2n) quantum queries by applying Grover-meet-Simon algorithm. The second attack costs (2^m/2) quantum queries by applying Grover’s algorithm, assuming the key size of (tweak-able) block cipher is m bits. As far as we know, these are the first quantum attacks against BBB MACs. It is remarkable that our attacks are suitable even for some optimally secure MACs, such as mPMAC+-f, mPMAC+-p1, and mPMAC+-p2.

Rank-metric code-based cryptography relies on the hardness of decoding a random linear code in the rank metric. The Rank Support Learning problem (RSL) is a variant where an attacker has access to N decoding instances which are strongly related and wants to solve any one of them. This problem is used in the Durandal signature scheme [1]. In this paper, we propose an algebraic attack on RSL which clearly outperforms the previous attacks to solve this problem. We build upon [2] where similar techniques we used to solve MinRank and RD. However, our analysis is simpler and therefore our attack relies on very elementary assumptions compared to standard Gr¨obner bases attacks. Also, it suggests that key recovery attacks on Durandal are much more efficient than what was previously thought.

[1] Aragon, N., Blazy, O., Gaborit, P., Hauteville, A., Z´emor, G.: Durandal: a rank metric based signature scheme. In: Advances in Cryptology - EURO-CRYPT 2019.
[2] Bardet, M., Bros, M., Cabarcas, D., Gaborit, P., Perlner, R., Smith-Tone, D., Tillich, J.P., Verbel, J.: Improvements of algebraic attacks for solving the rank decoding and minrank problems. In: Advances in Cryptology - ASI-ACRYPT 2020.

In this work we study the quantum security of public key encryption schemes (PKE). Boneh and Zhandry (CRYPTO'13) initiated this research area for PKE and symmetric key encryption (SKE), albeit restricted to a classical indistinguishability phase. Gagliardoni et al. (CRYPTO'16) advanced the study of quantum security by giving, for SKE, the first definition with a quantum indistinguishability phase. For PKE, on the other hand, no notion of quantum security with a quantum indistinguishability phase exists. Our main result is a novel quantum security notion (qINDqCPA) for PKE with a quantum indistinguishability phase, which closes the aforementioned gap. We show a distinguishing attack against code-based schemes and, for certain parameters, against LWE-based schemes. We also show that the canonical hybrid PKE-SKE construction is secure, even if the underlying PKE scheme by itself is not. Finally, we classify quantum-resistant PKE schemes based on the applicability of our security notion and discuss concurrent and independent work.

We present an adaptive key recovery attack on the leveled homomorphic encryption scheme suggested by Li, Galbraith and Ma (Provsec 2016), which itself is a modification of the GSW cryptosystem designed to resist key recovery attacks by using a different linear combination of secret keys for each decryption. We were able to efficiently recover the secret key for a realistic choice of parameters using a statistical attack. In particular, this means that the Li, Galbraith and Ma strategy does not prevent adaptive key recovery attacks.