All times are given in Korea Standard Time (UTC+09:00).
please join our Slack space through the following link to ask your questions and to communicate anytime:
Time | Program (Coordinator: Jooyoung Lee) | |
---|---|---|
13:00-13:15 | Watch Live Session | Opening |
13:15-14:00 | 1.1 Code-Based Cryptography Session Chair: Young-Sik Kim Watch Live Session |
Decoding Supercodes of Gabidulin Codes and Applications to Cryptanalysis Maxime Bombar and Alain Couvreur Best Paper
Abstract
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. |
LESS-FM: Fine-tuning Signatures from the Code Equivalence Problem Alessandro Barenghi, Jean-Francois Biasse, Edoardo Persichetti and Paolo Santini Abstract
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. |
||
Classical and Quantum algorithms for generic Syndrome Decoding problems and applications to the Lee metric Thomas Debris-Alazard, André Chailloux and Simona Etinski Abstract
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. |
||
14:00-14:15 | Break | |
14:15-15:00 | 1.2 Multivariate Cryptography Session Chair: Jae Hong Seo Watch Live Session |
Improving Thomae-Wolf Algorithm for Solving Underdetermined Multivariate Quadratic Polynomial Problem Hiroki Furue, Shuhei Nakamura and Tsuyoshi Takagi Abstract
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(2r, 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(2r, n, m), that is, n > m. Specifically, by eliminating the cross-product terms in α quadratic polynomials through linearization, MQ(2r, n, m) can be reduced to MQ(2r, 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 α = |
New Practical Multivariate Signatures from a Nonlinear Modifier Daniel Smith-Tone Abstract
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. |
||
On the Effect of Projection on Rank Attacks in Multivariate Cryptography Morten øygarden, Daniel Smith-Tone and Javier Verbel Abstract
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. |
||
15:00-15:45 | 1.3 Quantum Algorithms Session Chair: Steven Galbraith Watch Live Session |
Quantum Key Search for Ternary LWE Iggy van Hoof, Elena Kir shanova and Alexander May Abstract
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 S0.24 (classical) down to S0.19 (quantum). This translates into noticeable attack's speed-ups for concrete NTRU instantiations like NTRU-HRSS [CHES'17] and NTRU Prime [SAC'17]. |
A Fusion Algorithm for Solving the Hidden Shift Problem in Finite Abelian Groups Wouter Castryck, Ann Dooms, Carlo Emerencia and Alexander Lemmens Abstract
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|) · 2O(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 = 2tp, 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/2tpG, 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 2t-torsion groups. |
||
The "Quantum Annoying" Property of Password-Authenticated Key Exchange Protocols Edward Eaton and Douglas Stebila Abstract
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. |
||
15:45-16:00 | Break | |
16:00-17:00 | 1.4 Implementation and Side Channel Attack Session Chair: Tommaso Gagliardoni Watch Live Session |
Differential Power Analysis of the Picnic Signature Scheme Tim Gellersen, Okan Seker and Thomas Eisenbarth Abstract
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. |
Implementation of Lattice Trapdoors on Modules and Applications Pauline Bert, Gautier Eberhart, Lucas Prabel, Adeline Roux-Langlois and Mohamed Sabt Abstract
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 Rq (as different schemes have different conditions on q). |
||
Verifying Post-Quantum Signatures in 8 kB of RAM Ruben Gonzalez, Andreas Hülsing, Matthias J. Kannwischer, Juliane Krämer, Tanja Lange, Marc Stöttinger, Elisabeth Waitz, Thom Wiggers and Bo-Yin Yang Abstract
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. |
||
Fast NEON-based Multiplication for Lattice-based NIST Post-Quantum Cryptography Finalists Duc Nguyen and Kris Gaj Abstract
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. |
Time | Program (Coordinator: Young-Sik Kim) | |
---|---|---|
13:00-13:45 | 2.1 Isogeny Session Chair: Benjamin Smith Watch Live Session |
CSI-RAShi: Distributed Key Generation for CSIDH Ward Beullens, Lucas Disson, Robi Pedersen and Frederik Vercauteren Abstract
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. |
SimS: a Simplification of SiGamal Tako Boris Fouotsa and Christophe Petit Abstract
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. |
||
Memory Optimization Techniques for Computing Discrete Logarithms in Compressed SIKE Aaron Hutchinson, Koray Karabina and Geovandro Pereira Abstract
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. |
||
13:45-14:00 | Break | |
14:00-15:00 | Live Only2.2 Invited Talk Session Chair: Jean-Pierre Tillich Watch Live Session |
The Homestretch: the beginning of the end of the NIST PQC 3rd Round Dustin Moody (NIST) Abstract
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. |
15:00-15:10 | Break | |
15:10-15:15 | Live Only2.3 Industrial Track Session Chair: Kyung Chul Jeong Watch Live Session |
Opening Message - PQC Transition Policy in Korea Jin-bae Hong (Ministry of Science and ICT) |
15:15-17:00 |
PQC Transition - ANSSI Views Mélissa Rossi (ANSSI) Abstract
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. |
|
Activities on PQC in Japan Keita Xagawa (NTT) Abstract
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. |
||
Progress and Challenges in the Industrial Adoption of PQC Peter Pessl (Infineon) Abstract
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. |
||
Introduction of PQC Pilot Infrastructure and Services in the Industrial Area Kyoung Hak Mun (LG Uplus) Abstract
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. |
||
<Q|Crypton>, The Quantum Security Evaluation Platform for Cryptographic Algorithms Sokjoon Lee (ETRI) Abstract
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. |
Time | Program (Coordinator: Youngjoo Shin) | |
---|---|---|
13:00-14:00 | Live Only3.1 Invited Talk Session Chair: Jung Hee Cheon Watch Live Session |
Intractability Assumptions on Module Lattices Damien Stehlé (ENS de Lyon) Abstract
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. |
14:00-14:15 | Break | |
14:15-15:30 | 3.2 Lattice Based Cryptography Session Chair: Elena Kirshanova Watch Live Session |
Generating Cryptographically-Strong Random Lattice Bases and Recognizing Rotations of Z^n Tamar Blanks and Stephen Miller Abstract
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 Zn 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 for Committed Symmetric Boolean Functions San Ling, Khoa Nguyen, Duong Hieu Phan, Hanh Tang and Huaxiong Wang Abstract
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}n→ {0, 1}, one’s goal is to prove knowledge of a secret input x ∈ {0, 1}n 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. |
||
Short Identity-Based Signatures with Tight Security from Lattices Jiaxin Pan and Benedikt Wagner Abstract
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. |
||
On Removing Rejection Conditions in Practical Lattice-Based Signatures Rouzbeh Behnia, Yilei Chen and Daniel Masny Abstract
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 proposed, 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. |
||
Secure Hybrid Encryption In the Standard Model from Hard Learning Problems Xavier Boyen, Malika Izabachène and Qinyi Li Abstract
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. |
||
15:30-15:45 | Break | |
15:45-16:45 | 3.3 Cryptanalysis Session Chair: Scott Fluhrer Watch Live Session |
Attacks on Beyond-Birthday-Bound MACs in the Quantum Setting Tingting Guo, Peng Wang, Lei Hu and Dingfeng Ye Abstract
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(22n/3) queries in the classi-cal setting. The best classical attacks need O(23n/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(2n/2n) quantum queries by applying Grover-meet-Simon algorithm. The second attack costs (2m/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. |
An Algebraic Approach to the Rank Support Learning Problem Magali Bardet and Pierre Briaud Abstract
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. |
||
Quantum Indistinguishability for Public Key Encryption Tommaso Gagliardoni, Juliane Krämer and Patrick Struck Abstract
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. |
||
A Practical Adaptive Key Recovery Attack on the LGM (GSW-like) Cryptosystem Prastudy Fauzi, Martha Norberg Hovd and Håvard Raddum Abstract
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. |
||
16:45 | Watch Live Session | Adjourn |