Search

Your search keyword '"Cryptanalyse (CRYPT)"' showing total 8 results
Start Over Author "Cryptanalyse (CRYPT)" Publication Year Range Last 10 years
8 results on '"Cryptanalyse (CRYPT)"'

1. Counting Co-Cyclic Lattices

Author

Phong Q. Nguyen, Igor E. Shparlinski, 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), University of New South Wales [Sydney] (UNSW), Tsinghua University [Beijing], Inria de Paris, Japanese French Laboratory for Informatics (JFLI), and National Institute of Informatics (NII)-Université Pierre et Marie Curie - Paris 6 (UPMC)-The University of Tokyo (UTokyo)-Centre National de la Recherche Scientifique (CNRS)

Subjects
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), High Energy Physics::Lattice, General Mathematics, 0102 computer and information sciences, 01 natural sciences, Combinatorics, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Integer, FOS: Mathematics, Natural density, Asymptotic formula, Number Theory (math.NT), [MATH]Mathematics [math], Mathematics, Discrete mathematics, homogeneous congruences, Mathematics - Number Theory, cyclic lattices, Group (mathematics), Lattice problem, Order (ring theory), [MATH.MATH-NT]Mathematics [math]/Number Theory [math.NT], multiplicative functions, 010201 computation theory & mathematics, Computer Science - Discrete Mathematics
Abstract

International audience; There is a well-known asymptotic formula, due to W. M. Schmidt [Duke Math. J., 35 (1968), pp. 327--339], for the number of full-rank integer lattices of index at most $V$ in ${\mathbb{Z}}^n$. This set of lattices $L$ can naturally be partitioned with respect to the factor group ${\mathbb{Z}}^n/L$. Accordingly, we count the number of full-rank integer lattices $L \subseteq {\mathbb{Z}}^n$ such that ${\mathbb{Z}}^n/L$ is cyclic and of order at most $V$, and deduce that these co-cyclic lattices are dominant among all integer lattices: their natural density is $(\zeta(6) \prod_{k=4}^n \zeta(k))^{-1} \approx 85\%$. The problem is motivated by complexity theory, namely worst-case to average-case reductions for lattice problems.

Published
2016
Full Text
View/download PDF

2. A Genetic Algorithm for Searching the Shortest Lattice Vector of SVP Challenge

Author

Guizhen Zhu, Dan Ding, 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), Data Communication Science And Technology Research Institute [Beijing], ACM, and Tsinghua University [Beijing]

Subjects
Theoretical computer science, Markov chain, business.industry, Lattice problem, Cryptography, Sparse approximation, Computer Science::Computational Complexity, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Lattice (order), Genetic algorithm, Cryptosystem, Lattice-based cryptography, business, ComputingMilieux_MISCELLANEOUS, MathematicsofComputing_DISCRETEMATHEMATICS, Mathematics
Abstract

In this paper, we propose a genetic algorithm for solving the shortest vector problem (SVP) based on sparse representation of short lattice vectors, which, we prove, can guarantee finding the shortest lattice vector under a Markov analysis. With some heuristic improvements (local search and heuristic pruning), the SVP genetic algorithm, by experimental results, outperforms other SVP algorithms, like the famous Kannan-Helfrich algorithm under SVP challenge benchmarks. In summary, we, for the first time, adopt the genetic algorithm in solving the shortest vector problem, based on which lattice-based cryptosystem is as a promising candidate for post-quantum cryptography.

Published
2015
Full Text
View/download PDF

3. The Hardness of Lattice Problems: Worst-case to Average-case Reductions and Security Estimates

Author

Nguyen, Phong Q., 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), and Tsinghua University [Beijing]

Subjects
[INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2015

4. Finding Shortest Lattice Vectors in the Presence of Gaps

Author

Xiaoyun Wang, Wei Wei, Mingjie Liu, Chinese Academy of Sciences [Beijing] (CAS), Beijing Research Institute of Telemetry [Beijing], 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), Kaisa Nyberg, and Tsinghua University [Beijing]

Subjects
Combinatorics, Physics, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Sphere packing, Successive minima, Lattice problem, Lattice (order), Approximation algorithm, Voronoi diagram, Lambda, Time complexity, ComputingMilieux_MISCELLANEOUS
Abstract

The \(\lambda _i\)-gap \(\lambda _i/\lambda _1\) among the successive minima of a lattice especially its \(\lambda _2\)-gap often provides useful information for analyzing the security of lattice-based cryptographic schemes. In this paper, we mainly study the efficiency of shortest vector problem (SVP) algorithms for lattices with \(\lambda _i\)-gap. First, we prove new upper bounds for the packing density of this type of lattices. Based on these results, we discuss the efficiency of the ListSieve-Birthday algorithm proposed by Pujol and Stehle for SVP, and obtain the conclusion that the complexity will decrease obviously as the \(\lambda _i\)-gap increases. Particularly, ListSieve-Birthday becomes faster than the current best deterministic (Voronoi cell-based) algorithm for SVP, as long as \(\lambda _2\)-gap is larger than 1.78. When \(\lambda _2\)-gap is up to 28, the time complexity is \(2^{0.9992n+o(n)}\), and the coefficient factor of \(n\) is approximately to 0.802 if \(\lambda _2\)-gap is large enough. Moreover, we provide an SVP approximation algorithm modified by the ListSieve-Birthday algorithm. This algorithm terminates sieve process earlier and relaxes the birthday search, and hence decreases the time complexity significantly.

Published
2015
Full Text
View/download PDF

5. Improved Attacks on Reduced-Round Camellia-128/192/256

Author

Keting Jia, Xiaoyang Dong, Xiaoyun Wang, Leibo Li, Shandong University, Tsinghua University [Beijing] (THU), 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), Springer, and Tsinghua University [Beijing]

Subjects
Combinatorics, Keyspace, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Cover (topology), Key (cryptography), Fraction (mathematics), Meet-in-the-middle attack, Type (model theory), Time complexity, ComputingMilieux_MISCELLANEOUS, Mathematics, Block cipher
Abstract

Camellia is a widely used block cipher, which has been selected as an international standard by ISO/IEC. In this paper, we consider a new family of differentials of round-reduced Camellia-128 depending on different key subsets. There are totally 224 key subsets corresponding to 224 types of 8-round differentials, which cover a fraction of \(1-1/2^{15}\) of the keyspace. And each type of 8-round differential consists of \(2^{43}\) differentials. Combining with the multiple differential attack techniques, we give the key-dependent multiple differential attack on 10-round Camellia-128 with data complexity \(2^{91}\) and time complexity \(2^{113}\). Furthermore, we propose a 7-round property for Camellia-192 and an 8-round property for Camellia-256, and then mount the meet-in-the-middle attacks on 12-round Camellia-192 and 13-round Camellia-256, with complexity of \(2^{180}\) encryptions and \(2^{232.7}\) encryptions, respectively. All these attacks start from the first round in a single key setting.

Published
2015
Full Text
View/download PDF

6. Simpler Efficient Group Signatures from Lattices

Author

Jiang Zhang, Phong Q. Nguyen, Zhenfeng Zhang, 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), Trusted Computing and Information Assurance Laboratory, State Key Laboratory in Computer Science [Beijing] (SKLCS), Institute of Software Chinese Academy of Sciences [Beijing]-Institute of Software Chinese Academy of Sciences [Beijing], IACR, and Tsinghua University [Beijing]

Subjects
business.industry, Lattice problem, Group signature, Binary logarithm, Random oracle, Public-key cryptography, Combinatorics, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Lattice (order), business, Security parameter, Schnorr signature, ComputingMilieux_MISCELLANEOUS, Computer Science::Cryptography and Security, Mathematics
Abstract

A group signature allows a group member to anonymously sign messages on behalf of the group. In the past few years, new group signatures based on lattice problems have appeared: the most efficient lattice-based constructions are due to Laguillaumie et al. (Asiacrypt ’13) and Langlois et al. (PKC ’14). Both have at least \(O(n^2\log ^2 n \log N)\)-bit group public key and \(O(n\log ^3 n\log N)\)-bit signature, where \(n\) is the security parameter and \(N\) is the maximum number of group members. In this paper, we present a simpler lattice-based group signature, which is more efficient by a \(O(\log N)\) factor in both the group public key and the signature size. We achieve this by using a new non-interactive zero-knowledge (NIZK) proof corresponding to a simple identity-encoding function. The security of our group signature can be reduced to the hardness of SIS and LWE in the random oracle model.

Published
2015
Full Text
View/download PDF

7. 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

8. Improved boomerang attacks on round-reduced SM3 and keyed permutation of BLAKE-256

Author

Dongxia Bai, Hongbo Yu, Xiaoyun Wang, Gaoli Wang, 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], Institute for Advanced Study [Tsinghua], and Tsinghua University [Beijing]

Subjects
Computer Networks and Communications, business.industry, Computer science, Hash function, Cryptography, Computer security, computer.software_genre, Permutation, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Collision attack, Hash chain, Boomerang attack, NIST, business, computer, Software, ComputingMilieux_MISCELLANEOUS, Information Systems
Abstract

In this study, the authors study the security of hash functions SM3 and BLAKE-256 against boomerang attack. SM3 is designed by Wang et al. and published by Chinese Commercial Cryptography Administration Office for the use of electronic certification service system in China. BLAKE is one of the five finalists of the NIST SHA-3 competition submitted by Aumasson et al. For SM3, they present boomerang distinguishers for the compression function reduced to 34/35/36/37 steps out of 64 steps, with time complexities 231.4, 233.6, 273.4 and 2192, respectively. Then, they show some incompatible problems existed in the previous boomerang attacks on SM3. Meanwhile, they launch boomerang attacks on up to 7- and 8-round keyed permutation of BLAKE-256, which are the first valid 7-round and 8-round boomerangs for BLAKE-256. Especially, since the author's distinguishers on 34/35-steps compression function of SM3 and 7-round keyed permutation of BLAKE-256 are practical, they are able to obtain boomerang quartets of these attacks. As far as they know, these are the best results against round-reduced SM3 and BLAKE-256.

Published
2015
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results