Weak Keys for the Quasi-Cyclic MDPC Public Key Encryption Scheme

详细信息    查看全文

• 关键词：Quasi ; cyclic MDPC codes ; McEliece scheme ; Rational reconstruction problem ; Extended euclidean algorithm
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9646
• 期：1
• 页码：346-367
• 全文大小：451 KB
• 参考文献：[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
  
• 作者单位：Magali Bardet (16)
  Vlad Dragoi (16)
  Jean-Gabriel Luque (16)
  Ayoub Otmani (16)
  
  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.