Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-23T13:31:16.375Z Has data issue: false hasContentIssue false
  • English
  • Français

On the use of expansion series for stream ciphers

Part of: Arithmetic problems. Diophantine geometry Computational number theory Theory of computing Communication, information

Published online by Cambridge University Press:  01 September 2012

Claus Diem
Claus Diem*
Affiliation:
Mathematical Institute, University of Leipzig, Johannisgasse 26, D-04103 Leipzig, Germany (email: [email protected])

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

From power series expansions of functions on curves over finite fields, one can obtain sequences with perfect or almost perfect linear complexity profile. It has been suggested by various authors to use such sequences as key streams for stream ciphers. In this work, we show how long parts of such sequences can be computed efficiently from short ones. Such sequences should therefore be considered to be cryptographically weak. Our attack leads in a natural way to a new measure of the complexity of sequences which we call expansion complexity.

MSC classification

Secondary: 11Y16: Algorithms; complexity 14G50: Applications to coding theory and cryptography 68Q25: Analysis of algorithms and problem complexity 94A60: Cryptography
Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 15 , May 2012 , pp. 326 - 340
Copyright
Copyright © London Mathematical Society 2012

References

[1]Baker, M., González-Jiménez, E., González, J. and Poonen, B., ‘Finiteness results for modular curves of genus at least 2’, Amer. J. Math. 127 (2005).CrossRefGoogle Scholar
[2]Bosma, W., Cannon, J., Fieker, C. and Steel, A. (eds), Handbook of Magma functions, 2.18 edn 2011.Google Scholar
[3]Cohen, H., A course in computational algebraic number theory (Springer, 1996).Google Scholar
[4]Cohen, H., Number theory – vol. 1: Tools and diophantine equations (Springer, 2007).Google Scholar
[5]Diem, C., ‘On arithmetic and the discrete logarithm problem in class groups of curves’, Habilitation Thesis, 2008.Google Scholar
[6]Diem, C., ‘On the discrete logarithm problem in class groups of curves’, Math. Comp. 80 (2011) 443–475.CrossRefGoogle Scholar
[7]Hartshorne, R., Algebraic geometry (Springer, 1977).CrossRefGoogle Scholar
[8]Heß, F., ‘Computing Riemann–Roch spaces in algebraic function fields and related topics’, J. Symbolic Comput. 11 (2001).Google Scholar
[9]Kohel, D., Ling, S. and Xing, C., ‘Explicit sequence expansions’, Sequences and their applications — proceedings of SETA’98, Discrete Mathematics and Theoretical Computer Science (Springer, 1999).Google Scholar
[10]Lang, S., Algebraic number theory (Springer, 1994).CrossRefGoogle Scholar
[11]Niederreiter, H., ‘The probabilistic theory of linear complexity’, Advances in cryptology — Eurocrypt’88, Lecture Notes in Computer Science, 330 (ed. Günter, C.; Springer, 1988) 191–209.Google Scholar
[12]Niederreiter, H., ‘Sequences with almost perfect linear complexity profile’, Advances in cryptology – Eurocrypt’87, Lecture Notes in Computer Science, 330 (eds Chaum, D. and Price, W.; Springer, 1988) 37–51.Google Scholar
[13]Niederreiter, H., ‘Keystream squences with a good linear complexity profile for every starting point’, Advances in cryptology – Eurocrypt ’89, Lecture Notes in Computer Science, 434 (eds Quisquater, J.-J. and Vandewalle, J.; Springer, 1989) 523–532.Google Scholar
[14]Niederreiter, H., ‘A combinatorial approach to probabilistic results on the linear complexity profile of random sequences’, J. Cryptology (1990) 105–112.CrossRefGoogle Scholar
[15]Niederreiter, H. and Xing, C., Rational points on curves over finite fields (Cambridge University Press, 2001).CrossRefGoogle Scholar
[16]Piper, F., ‘Stream ciphers’, Elektrotechnik und Maschinenbau 104 (1987) 564–568.Google Scholar
[17]Rueppel, R., Analysis and design of stream ciphers (Springer, Berlin, 1986).CrossRefGoogle Scholar
[18]Rukhin, A.et al., ‘A statistical test suite for random and pseudorandom number generators for cryptographic applications’, NIST special publication (2010) 800–822.Google Scholar
[19]Stein, A., ‘Explicit infrastructure for real quadratic function fields and real hyperelliptic curves’, Glas. Mat. 44 (2009) 89–126.CrossRefGoogle Scholar
[20]Xing, C. and Lam, K., ‘Sequences with almost perfect linear complexity profiles and curves over finite fields’, IEEE Trans. Inform. Theory (1999) 1267–1270.CrossRefGoogle Scholar
[21]Zuccherato, R., ‘The continued fraction algorithm and regulator for quadratic function fields of characteristic 2’, J. Algebra (1997) 563–587.CrossRefGoogle Scholar