参考文献:[BBK08]Belbachir, H., Bouroubi, S., Khelladi, A.: Connection between ordinary multinomials, fibonacci numbers, bell polynomials and discrete uniform distribution. Ann. Math. Inform. 35, 21–30 (2008)MathSciNet MATH [CCD+09]Cesaratto, E., Clément, J., Daireaux, B., Lhote, L., Maume-Deschamps, V., Vallée, B.: Regularity of the euclid algorithm, application to the analysis of fast GCD algorithms. J. Symbolic Comput. 44(7), 726 (2009)MathSciNet CrossRef MATH [Dav79]Davis, P.J.: Circulant Matrices. Pure and applied mathematics. Wiley, New York (1979)MATH [FOP+14]Faugère, J.C., Otmani, A., Perret, L., de Portzamparc, F., Tillich, J.P.: Folding alternant and goppa codes with non-trivial automorphism groups, submitted, [cs.IT] (2014). arxiv:1405.5101 [Gen01]Gentry, C.: Key recovery and message attacks on NTRU-composite. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 182–194. Springer, Heidelberg (2001)CrossRef [Gou72]Gould, H.W.: Combinatorial identities: a standardized set of tables listing 500 binomial coefficient summations. Morgantown, W Va (1972) [GR61]Gilbert, E.N., Riordan, J.: Symmetry types of periodic sequences. Illinois J. Math. 5, 657–665 (1961)MathSciNet MATH [HS13]Hamdaoui, Y., Sendrier, N.: A non asymptotic analysis of information set decoding. In: Cryptology ePrint Archive, Report /162 (2013) [Knu71]Knuth, D.E.: The analysis of algorithms. Actes Congr. Internat. Math. 3, 269–274 (1971). http://cr.yp.to/bib/entries.html#1971/knuth-gcd MathSciNet MATH [KTC58]Lyndon, R.C., Chen, K.T., Fox, R.H.: Free differential calculus, iv. the quotient groups of the lower central series. Ann. Math. 68(1), 81–95 (1958)MathSciNet CrossRef MATH [Lan09]Landau, E.: Handbuch der Lehre von der Verteilung der Primzahlen. Teubner(1909) [Leh38]Lehmer, D.H.: Euclid’s algorithm for large numbers. Am. Math. Monthly 45(4), 227–233 (1938)MathSciNet CrossRef MATH [Loi01]Loidreau, P.: Codes derived from binary goppa codes. Probl. Inf. Transm. 37(2), 91–99 (2001)MathSciNet CrossRef MATH [Lot02]Lothaire, M.: Algebraic Combinatorics on Words. Encyclopedia of mathematics and its applications. Cambridge University Press, New York (2002)CrossRef MATH [LV06]Lhote, L., Vallée, B.: Sharp estimates for the main parameters of the euclid algorithm. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol. 3887, pp. 689–702. Springer, Heidelberg (2006)CrossRef [LV08]Lhote, L., Vallée, B.: Gaussian laws for the main parameters of the euclid algorithms. Algorithmica 50(4), 497–554 (2008)MathSciNet CrossRef MATH [McE78]McEliece, R.J.: A Public-Key System Based on Algebraic Coding Theory, pp. 114–116. Jet Propulsion Lab, DSN Progress Report, 44 (1978) [Mob32]Möbius, A.F.: Über eine besondere art von umkehrung der reihen. Journal für die reine und angewandte Mathematik 9, 105–123 (1832)CrossRef [MTSB12]Misoczki, R., Tillich, J.-P., Sendrier, N., Barreto, P.S.L.M.: MDPC-McEliece: New McEliece variants from moderate density parity-check codes. IACR Cryptology ePrint Archive, 409 (2012) [Ric03]Richomme, G.: Lyndon morphisms. Bull. Belg. Math. Soc. Simon Stevin 10(5), 761–785 (2003)MathSciNet MATH [Sch71]Schönhage, A.: Schnelle Berechnung von Kettenbruchentwicklungen. (German) [Fast calculation of expansions of continued fractions]. ACTA-INFO, 1, 139–144 (1971) [SZ04]Stehlé, D., Zimmermann, P.: A binary recursive GCD algorithm. In: Buell, D.A. (ed.) ANTS 2004. LNCS, vol. 3076, pp. 411–425. Springer, Heidelberg (2004)CrossRef
16. Normandie Univ, France; UR, LITIS, 76821, Mont-saint-aignan, France
丛书名:Progress in Cryptology ᾿AFRICACRYPT 2016
ISBN:978-3-319-31517-1
刊物类别:Computer Science
刊物主题:Artificial Intelligence and Robotics Computer Communication Networks Software Engineering Data Encryption Database Management Computation by Abstract Devices Algorithm Analysis and Problem Complexity
出版者:Springer Berlin / Heidelberg
ISSN:1611-3349
文摘
We analyze a new key recovery attack against the Quasi-Cyclic MDPC McEliece scheme. Retrieving the secret key from the public data is usually tackled down using exponential time algorithms aiming to recover minimum weight codewords and thus constructing an equivalent code. We use here a different approach and give under certain hypothesis an algorithm that is able to solve a key equation relating the public key to the private key. We relate this equation to a well known problem the Rational Reconstruction Problem and therefore propose a natural solution based on the extended Euclidean algorithm. All private keys satisfying the hypothesis are declared weak keys. In the same time we give a precise number of weak keys and extend our analysis by considering all possible cyclic shifts on the private keys. This task is accomplished using combinatorial objects like Lyndon words. We improve our approach by using a generalization of the Frobenius action which enables to increase the proportion of weak keys. Lastly, we implement the attack and give the probability to draw a weak key for all the security parameters proposed by the designers of the scheme.