Results 1-20 of 39. Search equation: ((uid:50001378)) Sort: Title Issue date Author Filter: All documents types Scientific journals - Article - Short communication - Book review - Letter to the editor - Complete issue - OtherBooks - Book published as author, translator, etc. - Collective work published as editor or directorParts of books - Contribution to collective works - Contribution to encyclopedias, dictionaries... - Preface, postface, glossary...Scientific congresses, symposiums and conference proceedings - Unpublished conference - Paper published in a book - Paper published in a journal - PosterScientific presentation in universities or research centersReports - Expert report - Internal report - External report - OtherDissertations and theses - Bachelor/master dissertation - Doctoral thesis - Postdoctoral thesis - OtherLearning materials - Course notes - OtherPatentCartographic materials - Single work - Part of another publicationComputer developments - Textual, factual or bibliographical database - Software - OtherE-prints/Working papers - First made available on ORBilu - Already available on another siteDiverse speeches and writings - Article for general public - Conference given outside the academic context - Speeches/Talks - Other     1 2   Provably Solving the Hidden Subset Sum Problem via Statistical LearningCoron, Jean-Sébastien ; Gini, Agnese E-print/Working paper (2021)At Crypto ’99, Nguyen and Stern described a lattice based algorithm for solving the hidden subset sum problem, a variant of the classical subset sum problem where the n weights are also hidden. As an ... [more ▼]At Crypto ’99, Nguyen and Stern described a lattice based algorithm for solving the hidden subset sum problem, a variant of the classical subset sum problem where the n weights are also hidden. As an application, they showed how to break the Boyko et al. fast generator of random pairs (x, g x(mod p)). The Nguyen-Stern algorithm works quite well in practice for moderate values of n, but its complexity is exponential in n. A polynomial-time variant was recently described at Crypto 2020, based on a multivariate technique, but the approach is heuristic only. In this paper, we describe a proven polynomial-time algorithm for solving the hidden subset-sum problem, based on statistical learning. In addition, we show that the statistical approach is also quite efficient in practice: using the FastICA algorithm, we can reach n = 250 in reasonable time. [less ▲]Detailed reference viewed: 52 (0 UL) Simultaneous Diagonalization of Incomplete Matrices and ApplicationsCoron, Jean-Sébastien ; Notarnicola, Luca ; Wiese, Gabor in Proceedings of the Fourteenth Algorithmic Number Theory Symposium (ANTS-XIV), edited by Steven Galbraith, Open Book Series 4, Mathematical Sciences Publishers, Berkeley, 2020 (2020, December)We consider the problem of recovering the entries of diagonal matrices {U_a}_a for a = 1, . . . , t from multiple “incomplete” samples {W_a}_a of the form W_a = P U_a Q, where P and Q are unknown matrices ... [more ▼]We consider the problem of recovering the entries of diagonal matrices {U_a}_a for a = 1, . . . , t from multiple “incomplete” samples {W_a}_a of the form W_a = P U_a Q, where P and Q are unknown matrices of low rank. We devise practical algorithms for this problem depending on the ranks of P and Q. This problem finds its motivation in cryptanalysis: we show how to significantly improve previous algorithms for solving the approximate common divisor problem and breaking CLT13 cryptographic multilinear maps. [less ▲]Detailed reference viewed: 151 (23 UL) A Polynomial-Time Algorithm for Solving the Hidden Subset Sum ProblemCoron, Jean-Sébastien ; Gini, Agnese in Advances in Cryptology -- CRYPTO 2020 (2020, August 10)At Crypto '99, Nguyen and Stern described a lattice based algorithm for solving the hidden subset sum problem, a variant of the classical subset sum problem where the n weights are also hidden. While the ... [more ▼]At Crypto '99, Nguyen and Stern described a lattice based algorithm for solving the hidden subset sum problem, a variant of the classical subset sum problem where the n weights are also hidden. While the Nguyen-Stern algorithm works quite well in practice for moderate values of n, we argue that its complexity is actually exponential in n; namely in the final step one must recover a very short basis of a n-dimensional lattice, which takes exponential-time in n, as one must apply BKZ reduction with increasingly large block-sizes. [less ▲]Detailed reference viewed: 163 (24 UL) Eurocrypt 2020Coron, Jean-Sébastien ; Greuet, Aurelien; Zeitoun, Rinain Eurocrypt 2020 (2020)Detailed reference viewed: 38 (1 UL) CRYPTO 2020Coron, Jean-Sébastien ; Belaid, Sonia; Prouff, Emmanuel et alin CRYPTO 2020 (2020)Detailed reference viewed: 38 (1 UL) Cryptanalysis of CLT13 Multilinear Maps with Independent SlotsCoron, Jean-Sébastien ; Notarnicola, Luca Speeches/Talks (2019)Detailed reference viewed: 130 (13 UL) Cryptanalysis of CLT13 Multilinear Maps with Independent SlotsCoron, Jean-Sébastien ; Notarnicola, Luca in Advances in Cryptology – ASIACRYPT 2019, 25th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan, December 8–12, 2019, Proceedings, Part II (2019, December)Detailed reference viewed: 222 (13 UL) Improved Cryptanalysis of the AJPS Mersenne Based CryptosystemCoron, Jean-Sébastien ; Gini, Agnese in Journal of Mathematical Cryptology (2019)At Crypto 2018, Aggarwal, Joux, Prakash and Santha (AJPS) described a new public-key encryption scheme based on Mersenne numbers. Shortly after the publication of the cryptosystem, Beunardeau et al ... [more ▼]At Crypto 2018, Aggarwal, Joux, Prakash and Santha (AJPS) described a new public-key encryption scheme based on Mersenne numbers. Shortly after the publication of the cryptosystem, Beunardeau et al. described an attack with complexity O(2^(2h)). In this paper, we describe an improvedattack with complexity O(2^(1.75h)) . [less ▲]Detailed reference viewed: 64 (17 UL) On Kilian's Randomization of Multilinear Map EncodingsCoron, Jean-Sébastien ; Pereira, Vitor in Coron, Jean-Sébastien; Pereira, Vitor (Eds.) On Kilian's Randomization of Multilinear Map Encodings (2019)Detailed reference viewed: 69 (14 UL) High-Order Conversion from Boolean to Arithmetic MaskingCoron, Jean-Sébastien in Proceedings of CHES 2017 (2017, September)Detailed reference viewed: 164 (18 UL) Zeroizing Attacks on Indistinguishability Obfuscation over CLT13Coron, Jean-Sébastien ; Lee, Moon Sung; Lepoint, Tancrede et alin Proceedings of PKC 2017 (2017)Detailed reference viewed: 132 (18 UL) Faster Evaluation of SBoxes via Common SharesCoron, Jean-Sébastien ; Greuet, Aurelien; Prouff, Emmanuel et alin Proceedings of CHES 2016 (2016)Detailed reference viewed: 112 (2 UL) Horizontal Side-Channel Attacks and Countermeasures on the ISW Masking SchemeCoron, Jean-Sébastien ; Battistello, Alberto; Prouff, Emmanuel et alin Proceedings of CHES 2016 (2016)Detailed reference viewed: 157 (2 UL) Cryptanalysis of GGH15 Multilinear MapsCoron, Jean-Sébastien ; Lee, Moon Sung; Lepoint, Tancrede et alin Proceedings of Crypto 2016 (2016)Detailed reference viewed: 175 (2 UL) Zeroizing Without Low-Level Zeroes: New MMAP Attacks and Their LimitationsCoron, Jean-Sébastien in Proceedings of Crypto 2015 (2015)Detailed reference viewed: 146 (4 UL) New Multilinear Maps over the IntegersCoron, Jean-Sébastien ; Lepoint, Tancrede; Tibouchi, Mehdiin Proceedings of Crypto 2015 (2015)Detailed reference viewed: 156 (15 UL) Conversion from Arithmetic to Boolean Masking with Logarithmic ComplexityCoron, Jean-Sébastien ; Groszschädl, Johann ; Tibouchi, Mehdi et alin Leander, Gregor (Ed.) Fast Software Encryption, 22nd International Workshop, FSE 2015, Istanbul, Turkey, March 8-11, 2015, Revised Selected Papers (2015, March)A general technique to protect a cryptographic algorithm against side-channel attacks consists in masking all intermediate variables with a random value. For cryptographic algorithms combining Boolean ... [more ▼]A general technique to protect a cryptographic algorithm against side-channel attacks consists in masking all intermediate variables with a random value. For cryptographic algorithms combining Boolean operations with arithmetic operations, one must then perform conversions between Boolean masking and arithmetic masking. At CHES 2001, Goubin described a very elegant algorithm for converting from Boolean masking to arithmetic masking, with only a constant number of operations. Goubin also described an algorithm for converting from arithmetic to Boolean masking, but with O(k) operations where k is the addition bit size. In this paper we describe an improved algorithm with time complexity O(log k) only. Our new algorithm is based on the Kogge-Stone carry look-ahead adder, which computes the carry signal in O(log k) instead of O(k) for the classical ripple carry adder. We also describe an algorithm for performing arithmetic addition modulo 2^k directly on Boolean shares, with the same complexity O(log k) instead of O(k). We prove the security of our new algorithm against first-order attacks. Our algorithm performs well in practice, as for k=64 we obtain a 23% improvement compared to Goubin’s algorithm. [less ▲]Detailed reference viewed: 233 (8 UL) Secure Conversion between Boolean and Arithmetic Masking of Any OrderCoron, Jean-Sébastien ; Groszschädl, Johann ; Vadnala, Praveen Kumar in Batina, Lejla; Robshaw, Matthew (Eds.) Cryptographic Hardware and Embedded Systems - CHES 2014, 16th International Workshop, Busan, South Korea, September 23-26, 2014. Proceedings (2014, September)Detailed reference viewed: 184 (12 UL) Higher Order Masking of Look-Up TablesCoron, Jean-Sébastien in Proceedings of Eurocrypt 2014 (2014)Detailed reference viewed: 116 (1 UL) Fast Evaluation of Polynomials over Binary Finite Fields and Application to Side-Channel CountermeasuresCoron, Jean-Sébastien ; Roy, Arnab; Venkatesh, Srinivas Vivek in Batina, Lejla; Robshaw, Matthew (Eds.) Cryptographic Hardware and Embedded Systems – CHES 2014 (2014)We describe a new technique for evaluating polynomials over binary finite fields. This is useful in the context of anti-DPA countermeasures when an S-box is expressed as a polynomial over a binary finite ... [more ▼]We describe a new technique for evaluating polynomials over binary finite fields. This is useful in the context of anti-DPA countermeasures when an S-box is expressed as a polynomial over a binary finite field. For n-bit S-boxes our new technique has heuristic complexity ${\cal O}(2^{n/2}/\sqrt{n})$ instead of ${\cal O}(2^{n/2})$ proven complexity for the Parity-Split method. We also prove a lower bound of ${\Omega}(2^{n/2}/\sqrt{n})$ on the complexity of any method to evaluate $n$-bit S-boxes; this shows that our method is asymptotically optimal. Here, complexity refers to the number of non-linear multiplications required to evaluate the polynomial corresponding to an S-box. In practice we can evaluate any 8-bit S-box in 10 non-linear multiplications instead of 16 in the Roy-Vivek paper from CHES 2013, and the DES S-boxes in 4 non-linear multiplications instead of 7. We also evaluate any 4-bit S-box in 2 non-linear multiplications instead of 3. Hence our method achieves optimal complexity for the PRESENT S-box. [less ▲]Detailed reference viewed: 171 (6 UL) 1 2