Search

Your search keyword '"Cryptanalyse (CRYPT)"' showing total 18 results
Start Over Author "Cryptanalyse (CRYPT)" Topic 0202 electrical engineering, electronic engineering, information engineering
18 results on '"Cryptanalyse (CRYPT)"'

1. Meet-in-the-Middle Technique for Truncated Differential and Its Applications to CLEFIA and Camellia

Author

Xiaoyun Wang, Keting Jia, Xiaoyang Dong, Leibo Li, Shandong University, Tsinghua University [Beijing], Institute for Advanced Study [Tsinghua], Cryptanalyse (CRYPT), Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées (LIAMA), Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria), IACR, and Tsinghua University [Beijing] (THU)

Subjects
Discrete mathematics, Differential cryptanalysis, 020207 software engineering, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, law.invention, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], 010201 computation theory & mathematics, law, CLEFIA, Camellia, 0202 electrical engineering, electronic engineering, information engineering, Truncated differential cryptanalysis, Cryptanalysis, Meet in the middle, Differential (mathematics), ComputingMilieux_MISCELLANEOUS, Block cipher, Mathematics
Abstract

As one of the generalizations of differential cryptanalysis, the truncated differential cryptanalysis has become a powerful toolkit to evaluate the security of block ciphers. In this article, taking advantage of the meet-in-the-middle like technique, we introduce a new method to construct truncated differential characteristics of block ciphers. Based on the method, we propose 10-round and 8-round truncated differential characteristics for CLEFIA and Camellia, respectively, which are ISO standard block ciphers. Applying the 10-round truncated differential characteristic for CLEFIA, we launch attacks on 14/14/15-round CLEFIA-128/192/256 with \(2^{108}\), \(2^{135}\) and \(2^{203}\) encryptions, respectively. For Camellia, we utilize the 8-round truncated differential to attack 11/12-round Camellia-128/192 including the \(FL/FL^{-1}\) and whiten layers with \(2^{121.3}\) and \(2^{185.3}\) encryptions. As far as we know, most of the cases are the best results of these attacks on both ciphers.

Published
2015
Full Text
View/download PDF

2. Advances in Cryptology - EUROCRYPT 2014: 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, May 11-15, 2014. Proceedings

Author

Phong Q. Nguyen, Elisabeth Oswald, Institute for Advanced Study [Tsinghua], Tsinghua University [Beijing], Cryptanalyse (CRYPT), Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées (LIAMA), Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria), University of Bristol [Bristol], IACR, and Tsinghua University [Beijing] (THU)

Subjects
060201 languages & linguistics, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Computer science, 0602 languages and literature, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, 06 humanities and the arts, 02 engineering and technology, ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2014
Full Text
View/download PDF

3. Rounding and Chaining LLL: Finding Faster Small Roots of Univariate Polynomial Congruences

Author

Jean-Sébastien Coron, Guénaël Renault, Phong Q. Nguyen, Rina Zeitoun, Jingguo Bi, Jean-Charles Faugère, Institute for Advanced Study [Tsinghua], Tsinghua University [Beijing] (THU), Cryptanalyse (CRYPT), Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées (LIAMA), Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria), Université du Luxembourg (Uni.lu), Polynomial Systems (PolSys), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Oberthur Card Systems - Puteaux, Oberthur Card Systems, Hugo Krawczyk, and Tsinghua University [Beijing]

Subjects
Polynomial, Speedup, Small Roots of Polynomial Equations, LLL, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Reduction (complexity), [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], RSA, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, 0202 electrical engineering, electronic engineering, information engineering, Coppersmith's Algorithm, Coppersmith, Time complexity, Mathematics, Coppersmith–Winograd algorithm, Discrete mathematics, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Rounding, people.profession, 020206 networking & telecommunications, 010201 computation theory & mathematics, Lattice reduction, people, Algorithm
Abstract

International audience; In a seminal work at EUROCRYPT '96, Coppersmith showed how to find all small roots of a univariate polynomial congruence in polynomial time: this has found many applications in public-key cryptanalysis and in a few security proofs. However, the running time of the algorithm is a high-degree polynomial, which limits experiments: the bottleneck is an LLL reduction of a high-dimensional matrix with extra-large coefficients. We present in this paper the first significant speedups over Coppersmith's algorithm. The first speedup is based on a special property of the matrices used by Coppersmith's algorithm, which allows us to provably speed up the LLL reduction by rounding, and which can also be used to improve the complexity analysis of Coppersmith's original algorithm. The exact speedup depends on the LLL algorithm used: for instance, the speedup is asymptotically quadratic in the bit-size of the small-root bound if one uses the Nguyen-Stehlé L2 algorithm. The second speedup is heuristic and applies whenever one wants to enlarge the root size of Coppersmith's algorithm by exhaustive search. Instead of performing several LLL reductions independently, we exploit hidden relationships between these matrices so that the LLL reductions can be somewhat chained to decrease the global running time. When both speedups are combined, the new algorithm is in practice hundreds of times faster for typical parameters.

Published
2014
Full Text
View/download PDF

4. Cryptanalysis of GOST R hash function

Author

Hongbo Yu, Xiaoyun Wang, Zongyue Wang, Shandong University, Cryptanalyse (CRYPT), Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées (LIAMA), Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria), Department of Computer Science and Technology (CST), Tsinghua University [Beijing], Institute for Advanced Study [Tsinghua], and Tsinghua University [Beijing] (THU)

Subjects
021110 strategic, defence & security studies, Theoretical computer science, Computer science, business.industry, Hash function, Rebound attack, 0211 other engineering and technologies, Cryptography, 02 engineering and technology, Computer Science Applications, Theoretical Computer Science, law.invention, GOST (hash function), [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Collision attack, law, Signal Processing, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Meet-in-the-middle attack, Arithmetic, business, Cryptanalysis, Time complexity, Information Systems
Abstract

International audience; GOST R 34.11-2012 is the new Russian hash function standard. This paper presents some cryptanalytic results on GOST R. Using the rebound attack technique, we achieve collision attacks on the reduced round compression function. Result on up to 9.5 rounds is proposed, the time complexity is 2176 and the memory requirement is 2128 bytes. Based on the 9.5-round collision result, a limited birthday distinguisher is presented. More over, a k-collision on 512-bit version of GOST R is constructed which shows the weakness of the structure used in GOST R.

Published
2014
Full Text
View/download PDF

5. A Three-Level Sieve Algorithm for the Shortest Vector Problem

Author

Gengran Hu, Yanbin Pan, Feng Zhang, Cryptanalyse (CRYPT), Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées (LIAMA), Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria), Key Laboratory of Mathematics Mechanization (KLMM), Chinese Academy of Sciences [Changchun Branch] (CAS)-Institute of Systems Science (ISS), China-Academy of Mathematics and Systems Science [Beijing], and Tanja Lange and Kristin Lauter and Petr Lisonek

Subjects
Discrete mathematics, Lattice sieving, Lattice problem, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, General number field sieve, Combinatorics, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Shortest Path Faster Algorithm, 010201 computation theory & mathematics, Lattice (order), 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Special number field sieve, Time complexity, Algorithm, Quadratic sieve, Mathematics
Abstract

In AsiaCCS 2011, Wang et al. proposed a two-level heuristic sieve algorithm for the shortest vector problem in lattices, which improves the Nguyen-Vidick sieve algorithm. Inspired by their idea, we present a three-level sieve algorithm in this paper, which is shown to have better time complexity. More precisely, the time complexity of our algorithm is $$2^{0.3778n+on}$$ polynomial-time operations and the corresponding space complexity is $$2^{0.2833n+on}$$ polynomially many bits.

Published
2013

6. Fault Rate Analysis: Breaking Masked AES Hardware Implementations Efficiently

Author

An Wang, Man Chen, Zongyue Wang, Xiaoyun Wang, Institute for Advanced Study [Tsinghua], Tsinghua University [Beijing] (THU), Cryptanalyse (CRYPT), Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées (LIAMA), Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria), Shandong University, and Tsinghua University [Beijing]

Subjects
Hardware implementations, Computer science, Real-time computing, Cryptography, 0102 computer and information sciences, 02 engineering and technology, fault rate analysis (FRA), 01 natural sciences, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], side-channel attack, Collision attack, 0202 electrical engineering, electronic engineering, information engineering, Fault rate, Side channel attack, Electrical and Electronic Engineering, business.industry, Advanced Encryption Standard, Byte, masking, 010201 computation theory & mathematics, path delay, 020201 artificial intelligence & image processing, business, Critical path method, Computer hardware
Abstract

International audience; In 2011, Li presented clockwise collision analysis on nonprotected Advanced Encryption Standard (AES) hardware implementation. In this brief, we first propose a new clockwise collision attack, called fault rate analysis (FRA), on masked AES. Then, we analyze the critical and noncritical paths of the S-box and find that, for its three input bytes, namely, the input value, the input mask, and the output mask, the path relating to the output mask is much shorter than those relating to the other two inputs. Therefore, some sophisticated glitch cycles can be chosen such that the values in the critical path of the whole S-box are destroyed but this short path is not affected. As a result, the output mask does not offer protection to the S-box, which leads to a more efficient attack. Compared with three attacks on masking countermeasures at the Workshop on Cryptographic Hardware and Embedded Systems 2010 and 2011, our method only costs about 8% of their time and 4% of their storage space.

Published
2013
Full Text
View/download PDF

7. Solving BDD by Enumeration: An Update

Author

Phong Q. Nguyen, Mingjie Liu, Beijing International Center for Mathematical Research, Peking University [Beijing], Institute for Advanced Study [Tsinghua], Tsinghua University [Beijing], Cryptanalyse (CRYPT), Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées (LIAMA), Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria), Ed Dawson, China's 973 Program, Grants 2013CB834201 and 2013CB834205, Beijing International Center for Mathematical Research (BiCMR), and Tsinghua University [Beijing] (THU)

Subjects
Theoretical computer science, Speedup, Enumeration, 0102 computer and information sciences, 02 engineering and technology, Encryption, 01 natural sciences, law.invention, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], law, LWE, 0202 electrical engineering, electronic engineering, information engineering, Cryptosystem, ACM: E.: Data/E.3: DATA ENCRYPTION/E.3.0: Code breaking, Mathematics, business.industry, Lattice problem, 020206 networking & telecommunications, Lattices, 010201 computation theory & mathematics, Lattice reduction, Cryptanalysis, business, Algorithm, BDD, Decoding methods
Abstract

International audience; Bounded Distance Decoding (BDD) is a basic lattice problem used in cryptanalysis: the security of most lattice-based encryption schemes relies on the hardness of some BDD, such as LWE. We study how to solve BDD using a classical method for finding shortest vectors in lattices: enumeration with pruning speedup, such as Gama-Nguyen-Regev extreme pruning from EUROCRYPT '10. We obtain significant improvements upon Lindner-Peikert's Search-LWE algorithm (from CT-RSA '11), and update experimental cryptanalytic results, such as attacks on DSA with partially known nonces and GGH encryption challenges. Our work shows that any security estimate of BDD-based cryptosystems must take into account enumeration attacks, and that BDD enumeration can be practical even in high dimension like 350.

Published
2013
Full Text
View/download PDF

8. Improved Boomerang Attacks on SM3

Author

Gaoli Wang, Xiaoyun Wang, Dongxia Bai, Hongbo Yu, Department of Computer Science and Technology (CST), Tsinghua University [Beijing], Cryptanalyse (CRYPT), Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées (LIAMA), Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria), Donghua University [Shanghai], Institute for Advanced Study [Tsinghua], School of Mathematics [Shandong], Shandong University, Colin Boyd and Leonie Simpson, and Tsinghua University [Beijing] (THU)

Subjects
boomerang attack, Computer science, media_common.quotation_subject, Hash function, Cryptography, 0102 computer and information sciences, 02 engineering and technology, Certification, Computer security, computer.software_genre, 01 natural sciences, law.invention, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], cryptanalysis, SM3, law, 0202 electrical engineering, electronic engineering, information engineering, Cryptographic hash function, Function (engineering), media_common, Service system, business.industry, 010201 computation theory & mathematics, Boomerang attack, hash function, 020201 artificial intelligence & image processing, business, Cryptanalysis, computer
Abstract

International audience; The cryptographic hash function SM3 is designed by X. Wang et al. and published by Chinese Commercial Cryptography Administration Office for the use of electronic certification service system in China. It is based on the Merkle-Damgård design and is very similar to SHA-2 but includes some additional strengthening features. In this paper, we apply the boomerang attack to SM3 compression function, and present such distinguishers on up to 34/35/36/37 steps out of 64 steps, with time complexities 231.4, 233.6, 273.4 and 293 compression function calls respectively. Especially, we are able to obtain the examples of the distinguishers on 34-step and 35-step on a PC due to their practical complexities. In addition, incompatible problems in the recent boomerang attack are pointed out.

Published
2013
Full Text
View/download PDF

9. Advances in Cryptology - ASIACRYPT 2012

Author

Kazue Sako, Xiaoyun Wang, Institute for Advanced Study [Tsinghua], Tsinghua University [Beijing] (THU), Cryptanalyse (CRYPT), Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées (LIAMA), Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria), NEC Corporation, Xiaoyun Wang and Kazue Sako, and Tsinghua University [Beijing]

Subjects
Operations research, business.industry, Cryptography, 02 engineering and technology, Information security, Computer security, computer.software_genre, Secure computation secure computation, 020202 computer hardware & architecture, Homomorphic signatures, Elliptic curve cryptography, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Geography, Beijing, Collision attack, Pairing-based cryptosystems, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, business, China, computer
Abstract

International audience; 18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, December 2-6, 2012. Proceedings

Published
2012
Full Text
View/download PDF

10. Learning a Zonotope and More: Cryptanalysis of NTRUSign Countermeasures

Author

Léo Ducas, Phong Q. Nguyen, Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities (CASCADE), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Cryptanalyse (CRYPT), Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées (LIAMA), Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria), Institute for Advanced Study [Tsinghua], Tsinghua University [Beijing], IACR, Xiaoyun Wang and Kazue Sako, China's 973 Program, Grant 2013CB834205, European Project, École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institute of Automation - Chinese Academy of Sciences-Institut National de Recherche en Informatique et en Automatique (Inria)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de la Recherche Agronomique (INRA)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Centre National de la Recherche Scientifique (CNRS)-Institute of Automation - Chinese Academy of Sciences-Institut National de Recherche en Informatique et en Automatique (Inria)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de la Recherche Agronomique (INRA)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Tsinghua University [Beijing] (THU), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria Paris-Rocquencourt

Subjects
Theoretical computer science, NTRU, 0102 computer and information sciences, 02 engineering and technology, NTRUSign, 01 natural sciences, law.invention, Cryptanalysis, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], IEEE P1363, law, 0202 electrical engineering, electronic engineering, information engineering, Learning, ACM: E.: Data/E.3: DATA ENCRYPTION/E.3.0: Code breaking, Polynomial number, Mathematics, Signatures, NTRUsign, Lattices, Hermite normal form, 020202 computer hardware & architecture, Parallelepiped, 010201 computation theory & mathematics, Algorithm
Abstract

International audience; NTRUsign is the most practical lattice signature scheme. Its basic version was broken by Nguyen and Regev in 2006: one can efficiently recover the secret key from about 400 signatures. However, countermeasures have been proposed to repair the scheme, such as the perturbation used in NTRUsign standardization proposals, and the deformation proposed by Hu et al. at IEEE Trans. Inform. Theory in 2008. These two countermeasures were claimed to prevent the NR attack. Surprisingly, we show that these two claims are incorrect by revisiting the NR gradient-descent attack: the attack is more powerful than previously expected, and actually breaks both countermeasures in practice, e.g. 8,000 signatures suffice to break NTRUsign-251 with one perturbation as submitted to IEEE P1363 in 2003. More precisely, we explain why the Nguyen-Regev algorithm for learning a parallelepiped is heuristically able to learn more complex objects, such as zonotopes and deformed parallelepipeds.

Published
2012
Full Text
View/download PDF

11. Improved Cryptanalysis of the Block Cipher KASUMI

Author

Leibo Li, Christian Rechberger, Jiazhe Chen, Keting Jia, Xiaoyun Wang, Institute for Advanced Study [Tsinghua], Tsinghua University [Beijing] (THU), Cryptanalyse (CRYPT), Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées (LIAMA), Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria), Computer Security and Industrial Cryptography [KU Leuven] (ESAT-COSIC), Department of Electrical Engineering [KU Leuven] (KU-ESAT), Catholic University of Leuven - Katholieke Universiteit Leuven (KU Leuven)-Catholic University of Leuven - Katholieke Universiteit Leuven (KU Leuven), Department of Mathematics (Kongens Lyngby, Denmark), Danmarks Tekniske Universitet = Technical University of Denmark (DTU), Lars R. Knudsen and Huapeng Wu, European Project: 216676,EC:FP7:ICT,FP7-ICT-2007-1,ECRYPT II(2008), Tsinghua University [Beijing], and Technical University of Denmark [Lyngby] (DTU)

Subjects
Theoretical computer science, Computer science, business.industry, Impossible Differential, 020206 networking & telecommunications, Cryptography, 02 engineering and technology, XSL attack, law.invention, KASUMI, Cryptanalysis, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], law, 0202 electrical engineering, electronic engineering, information engineering, Boomerang attack, 020201 artificial intelligence & image processing, Slide attack, business, Key schedule, Block cipher
Abstract

International audience; KASUMI is a block cipher which consists of eight Feistel rounds with a 128-bit key. Proposed more than 10 years ago, the confidentiality and integrity of 3G mobile communications systems depend on the security of KASUMI. In the practically interesting single key setting, only up to 6 rounds have been attacked so far. In this paper we use some observations on the FL and FO functions. Combining these observations with a key schedule weakness, we select some special input and output values to refine the general 5-round impossible differentials and propose the first 7-round attack on KASUMI with time and data complexities similar to the previously best 6-round attacks. This leaves now only a single round of security margin. The new impossible differential attack on the last 7 rounds needs 2114.3 encryptions with 252.5 chosen plaintexts. For the attack on the first 7 rounds, the data complexity is 262 known plaintexts and the time complexity is 2115.8 encryptions.

Published
2012
Full Text
View/download PDF

12. The Boomerang Attacks on the Round-Reduced Skein-512

Author

Jiazhe Chen, Xiaoyun Wang, Hongbo Yu, Cryptanalyse (CRYPT), Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées (LIAMA), Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria), Department of Computer Science and Technology (CST), Tsinghua University [Beijing] (THU), School of Mathematics [Shandong], Shandong University, Computer Security and Industrial Cryptography [KU Leuven] (ESAT-COSIC), Department of Electrical Engineering [KU Leuven] (KU-ESAT), Catholic University of Leuven - Katholieke Universiteit Leuven (KU Leuven)-Catholic University of Leuven - Katholieke Universiteit Leuven (KU Leuven), Institute for Advanced Study [Tsinghua], Lars R. Knudsen and Huapeng Wu, and Tsinghua University [Beijing]

Subjects
Skein, Hash function, 020206 networking & telecommunications, 02 engineering and technology, Function (mathematics), Computer security, computer.software_genre, Threefish, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], 0202 electrical engineering, electronic engineering, information engineering, Boomerang attack, 020201 artificial intelligence & image processing, Arithmetic, computer, Bitwise operation, Block cipher, Mathematics
Abstract

International audience; The hash function Skein is one of the five finalists of the NIST SHA-3 competition. It is based on the block cipher Threefish which only uses three primitive operations: modular addition, rotation and bitwise XOR (ARX). This paper studies the boomerang attacks on Skein-512. Boomerang distinguishers on the compression function reduced to 32 and 36 rounds are proposed, with time complexities 2^104.5 and 2^454 hash computations respectively. Examples of the distinguishers on 28 and 31 rounds are also given. In addition, the boomerang distinguishers are applicable to the key-recovery attacks on reduced Threefish-512. The time complexities for key-recovery attacks reduced to 32-/33-/34-round are about 2^181, 2^305 and 2^424 encryptions. Because the previous boomerang distinguishers for Threefish-512 are in fact not compatible [14], our attacks are the first valid boomerang attacks for the reduced-round Skein-512.

Published
2012
Full Text
View/download PDF

13. Cryptanalysis of a homomorphic encryption scheme from ISIT 2008

Author

Mingjie Liu, Xiaoyun Wang, Jingguo Bi, Institute for Advanced Study [Tsinghua], Tsinghua University [Beijing], Cryptanalyse (CRYPT), Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées (LIAMA), Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria), IEEE, and Tsinghua University [Beijing] (THU)

Subjects
Key-recovery attack, Homomorphic secret sharing, Theoretical computer science, business.industry, Homomorphic encryption, 0102 computer and information sciences, 02 engineering and technology, Encryption, 01 natural sciences, law.invention, Public-key cryptography, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Symmetric-key algorithm, 010201 computation theory & mathematics, law, Knapsack problem, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, business, Cryptanalysis, Mathematics
Abstract

International audience; At ISIT 2008, Aguilar Melchor, Castagnos and Gaborit presented a lattice-based homomorphic encryption scheme (abbreviated as MCG). Its security is based on the Computational Knapsack Vector Problem. In this paper, we explore a secret linear relationship between the public keys and the secret keys, which can be used to construct a reduced-dimension lattice, and then we obtain a group of equivalent private keys by solving the Closest Vector Problem of the lattice. Moreover, our attack is practical on all the three settings of recommended parameters, and the running time to recover the equivalent private keys is only several hours on a single PC.

Published
2012
Full Text
View/download PDF

14. An efficient broadcast attack against NTRU

Author

Jianwei Li, Guizhen Zhu, Yanbin Pan, Mingjie Liu, Institute for Advanced Study [Tsinghua], Tsinghua University [Beijing] (THU), Cryptanalyse (CRYPT), Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées (LIAMA), Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria), Key Laboratory of Mathematics Mechanization (KLMM), Chinese Academy of Sciences [Changchun Branch] (CAS)-Institute of Systems Science (ISS), China-Academy of Mathematics and Systems Science [Beijing], ACM, Heung Youl Youm and Yoojae Won, and Tsinghua University [Beijing]

Subjects
Ring (mathematics), Theoretical computer science, Degree (graph theory), Computer science, NTRU, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Combinatorics, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Integer, 010201 computation theory & mathematics, Scheme (mathematics), 0202 electrical engineering, electronic engineering, information engineering, Cryptosystem, 020201 artificial intelligence & image processing, Multiplication, ComputingMilieux_MISCELLANEOUS
Abstract

The NTRU cryptosystem is the most practical scheme known to date and has drawn considerable interest, which depends on three integer parameters (N, p, q) and four sets Lf, Lg, Lr, Lm of polynomials of degree N − 1 with small integer coefficients. We choose p, q such that gcd(p, q) = 1 and p is much smaller than q, denote the ring Z[x]/(xN -- 1) by R and the multiplication in R by *.

Published
2012
Full Text
View/download PDF

15. Faster Algorithms for Approximate Common Divisors: Breaking Fully-Homomorphic-Encryption Challenges over the Integers

Author

Yuanmi Chen, Phong Q. Nguyen, Laboratoire d'informatique de l'école normale supérieure (LIENS), Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Institute for Advanced Study [Tsinghua], Tsinghua University [Beijing] (THU), Cryptanalyse (CRYPT), Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées (LIAMA), Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria), IACR, David Pointcheval and Thomas Johansson, École normale supérieure - Paris (ENS Paris)-Centre National de la Recherche Scientifique (CNRS), Tsinghua University [Beijing], École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), and Institute of Automation - Chinese Academy of Sciences-Institut National de Recherche en Informatique et en Automatique (Inria)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de la Recherche Agronomique (INRA)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Centre National de la Recherche Scientifique (CNRS)-Institute of Automation - Chinese Academy of Sciences-Institut National de Recherche en Informatique et en Automatique (Inria)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de la Recherche Agronomique (INRA)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt

Subjects
Discrete mathematics, Scheme (programming language), Brute-force search, Homomorphic encryption, 020206 networking & telecommunications, 02 engineering and technology, law.invention, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Factoring, Square root, Integer, Fully-homomorphic encryption, cryptanalysis, approximate gcd, Simple (abstract algebra), law, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, ACM: E.: Data/E.3: DATA ENCRYPTION/E.3.0: Code breaking, Cryptanalysis, Algorithm, computer, Mathematics, computer.programming_language, Computer Science::Cryptography and Security
Abstract

International audience; At EUROCRYPT '10, van Dijk et al. presented simple fully- homomorphic encryption (FHE) schemes based on the hardness of approximate integer common divisors problems, which were introduced in 2001 by Howgrave-Graham. There are two versions for these problems: the partial version (PACD) and the general version (GACD). The seemingly easier problem PACD was recently used by Coron et al. at CRYPTO '11 to build a more efficient variant of the FHE scheme by van Dijk et al.. We present a new PACD algorithm whose running time is essentially the "square root" of that of exhaustive search, which was the best attack in practice. This allows us to experimentally break the FHE challenges proposed by Coron et al. Our PACD algorithm directly gives rise to a new GACD algorithm, which is exponentially faster than exhaustive search. Interestingly, our main technique can also be applied to other settings, such as noisy factoring and attacking low-exponent RSA.

Published
2012
Full Text
View/download PDF

16. New Observations on Impossible Differential Cryptanalysis of Reduced-Round Camellia

Author

Xiaoyun Wang, Jiazhe Chen, Wei Li, Ya Liu, Zhiqiang Liu, Leibo Li, Dawu Gu, Department of Computer Science, Shanghai Jiao Tong University [Shanghai], School of Mathematics [Shandong], Shandong University, Institute for Advanced Study [Tsinghua], Tsinghua University [Beijing] (THU), Cryptanalyse (CRYPT), Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées (LIAMA), Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria), Donghua University [Shanghai], Chinese Academy of Sciences [Beijing] (CAS), IACR, Anne Canteaut, Department of Computer Science (Shanghai Jiao Tong University, China), and Tsinghua University [Beijing]

Subjects
Key space, Camellia, 0102 computer and information sciences, 02 engineering and technology, Impossible differential cryptanalysis, Higher-order differential cryptanalysis, 01 natural sciences, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Impossible Differential Cryptanalysis, 010201 computation theory & mathematics, Linear cryptanalysis, 0202 electrical engineering, electronic engineering, information engineering, Leverage (statistics), Block Cipher, 020201 artificial intelligence & image processing, Arithmetic, Algorithm, Block cipher, Mathematics
Abstract

International audience; Camellia is one of the widely used block ciphers, which has been selected as an international standard by ISO/IEC. In this paper, by exploiting some interesting properties of the key-dependent layer, we improve previous results on impossible differential cryptanalysis of reduced-round Camellia and gain some new observations. First, we introduce some new 7-round impossible differentials of Camellia for weak keys. These weak keys that work for the impossible differential take 3/4 of the whole key space, therefore, we further get rid of the weak-key assumption and leverage the attacks on reduced-round Camellia to all keys by utilizing the multiplied method. Second, we build a set of differentials which contains at least one 8-round impossible differential of Camellia with two FL/FL − 1 layers. Following this new result, we show that the key-dependent transformations inserted in Camellia cannot resist impossible differential cryptanalysis effectively. Based on this set of differentials, we present a new cryptanalytic strategy to mount impossible differential attacks on reduced-round Camellia.

Published
2012
Full Text
View/download PDF

17. Faster Gaussian Lattice Sampling Using Lazy Floating-Point Arithmetic

Author

Léo Ducas, Phong Q. Nguyen, Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities (CASCADE), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Cryptanalyse (CRYPT), Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées (LIAMA), Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria), Institute for Advanced Study [Tsinghua], Tsinghua University [Beijing] (THU), IACR, Xiaoyun Wang and Kazue Sako, China's 973 Program, Grant 2013CB834205, European Project, Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Tsinghua University [Beijing], École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Institute of Automation - Chinese Academy of Sciences-Institut National de Recherche en Informatique et en Automatique (Inria)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de la Recherche Agronomique (INRA)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Centre National de la Recherche Scientifique (CNRS)-Institute of Automation - Chinese Academy of Sciences-Institut National de Recherche en Informatique et en Automatique (Inria)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de la Recherche Agronomique (INRA)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria Paris-Rocquencourt

Subjects
Speedup, Floating point, NTRU, Gaussian, 0102 computer and information sciences, 02 engineering and technology, NTRUSign, 01 natural sciences, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], symbols.namesake, Gaussian sampling, Lattice (order), 0202 electrical engineering, electronic engineering, information engineering, Mathematics, Cryptographic primitive, Signatures, NTRUsign, Floating-point arithmetic, 020206 networking & telecommunications, Lattices, Computer Science::Numerical Analysis, 010201 computation theory & mathematics, symbols, ACM: E.: Data/E.3: DATA ENCRYPTION/E.3.2: Public key cryptosystems, Security parameter, Algorithm
Abstract

International audience; Many lattice cryptographic primitives require an efficient algorithm to sample lattice points according to some Gaussian distribution. All algorithms known for this task require long-integer arithmetic at some point, which may be problematic in practice. We study how much lattice sampling can be sped up using floating-point arithmetic. First, we show that a direct floating-point implementation of these algorithms does not give any asymptotic speedup: the floating-point precision needs to be greater than the security parameter, leading to an overall complexity $\softO(n^3)$ where $n$ is the lattice dimension. However, we introduce a laziness technique that can significantly speed up these algorithms. Namely, in certain cases such as NTRUsign lattices, laziness can decrease the complexity to $\softO(n^2)$ or even $\softO(n)$. Furthermore, our analysis is practical: for typical parameters, most of the floating-point operations only require the double-precision IEEE standard.

Published
2012
Full Text
View/download PDF

18. Lattice-Based Fault Attacks on Signatures

Author

Mehdi Tibouchi, Phong Q. Nguyen, Institute for Advanced Study [Tsinghua], Tsinghua University [Beijing], Cryptanalyse (CRYPT), Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées (LIAMA), Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria), NTT Secure Platform Laboratories [Tokyo], Nippon Telegraph & Telephone Corporation - NTT, Marc Joye and Michael Tunstall, and Tsinghua University [Beijing] (THU)

Subjects
060201 languages & linguistics, Theoretical computer science, business.industry, Hash function, Public key cryptosystem, 06 humanities and the arts, 02 engineering and technology, Fault injection, law.invention, Public-key cryptography, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], law, Lattice (order), 0602 languages and literature, 0202 electrical engineering, electronic engineering, information engineering, Short vector, 020201 artificial intelligence & image processing, Lattice reduction, business, Cryptanalysis, Mathematics
Abstract

International audience; Since the introduction of the LLL algorithm in 1982, lattice reduction has proved to be one of the most powerful and versatile tools of public key cryptanalysis. In particular, it has sometimes been combined with fault injection to break physical implementations of public key cryptosystems. We present several examples of lattice-based fault attacks against DSA and RSA signatures, together with the necessary mathematical background.

Published
2012
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results