On Graph Algorithms for Degeneracy Test and Recursive Description of Stream Ciphers

• Autorzy: Wang L. , Hu Z.

Identyfikatory

DOI

10.3233/FI-2018-1686

• Języki publikacji: EN

Abstrakty

EN

Keystreams of a degenerate stream cipher can be generated by another stream cipher of less bits, and recursive description of stream ciphers is useful in cryptanalysis. Two algorithms are proposed based on directed graphs informing whether each pair of bits are related in the state transition: One tests two categories of degenerate synchronous additive stream ciphers, particularly for realistic stream ciphers with sparse transition equations; the other finds a recursive description of a given stream cipher. Specially, the latter algorithm has to balance the efficiency and the number of sequences for a recursive description, and a sufficient condition is given to test degeneracy based on the recursive description.

Słowa kluczowe

EN

stream cipher; degeneracy; feedback graph; component graph; feedback vertex set

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 160, nr 3
• Strony: 343--359
• Opis fizyczny: Bibliogr. 19 poz., rys., tab.

Twórcy

autor

Wang L.

• Science and Technology on Communication Security Laboratory, Chengdu 610041, P. R. China

autor

Hu Z.

• School of Mathematics and Statistics, Central South University, Changsha 410083, P. R. China

Bibliografia

• [1] Cusick T, Ding C, Renvall A. Stream Ciphers and Number Theory. North-Holland Mathematical Library, 55. Elsevier, North-Holland, 1998. 1st Edition. ISBN: 9780080541846.
• [2] Rukhin, A et al. Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. NIST Special Publication 800-22 rev1a. 2010.
• [3] Klein A. Stream Ciphers. Springer, London, 2013. doi:10.1007/978-1-4471-5079-4.
• [4] Bernstein, DJ. Re: A reformulation of TRIVIUM. Posted on the eSTREAM Forum. http://www.ecrypt.eu.org/stream/phorum/read.php?1,448. 2006.
• [5] Riera, C. Spectral Properties of Boolean Functions, Graphs and Graph States. PhD dissertation. 2005.
• [6] Dubrova E. A Transformation from the Fibonacci to the Galois NLFSRs. IEEE Transactions on Information Theory, 2009;55(11):5263-5271. doi:10.1109/TIT.2009.2030467.
• [7] Wang L, Shen B, Qiao T. Searching Short Recurrences of Nonlinear Shift Registers via Directed Acyclic Graphs. In: Wu CK., Yung M., Lin D. (eds) Information Security and Cryptology. Inscrypt 2011. Lecture Notes in Computer Science, vol 7537. Springer, Berlin, Heidelberg. 2012 pp. 44-56. doi:10.1007/978-3-642-34704-7_4.
• [8] Bondy J, Murty U. Graph Theory. Springer, 2008. 1st Edition. ISBN: 978-1-84628-969-9, 978-1-84996-690-0.
• [9] Cormen T, Leiserson C, Rivest R, Stein C. Introduction to Algorithms. The MIT Press, 2001. 2nd Edition. ISBN:0-262-03293-7, 9780262032933.
• [10] Jansen C, Boekee D. The Shortest Feedback Shift Register that can Generate a Given Sequence. In: Brassard G. (eds) Advances in Cryptology - CRYPTO’ 89 Proceedings. Lecture Notes in Computer Science, vol 435. Springer, New York. 1989 pp. 90-99. doi:10.1007/0-387-34805-0_10.
• [11] Robshaw M, Billet O. (editors) New Stream Cipher Designs - the eSTREAM Finalists. Springer-Verlag Berlin Heidelberg, 2008. ISBN: 978-3-540-68350-6.
• [12] Erdös P, Rényi A. On Random Graphs I. Publicationes Mathematicae (Debrecen), 1959;6:290-297.
• [13] Erdös P, Rényi A. On the Evolution of Random Graphs. Publ. Math. Inst. Hungar. Acad. Sci., 1960; 5:17-61.
• [14] Graham A, Pike D. A Note on Thresholds and Connectivity in Random Directed Graphs. Atlantic Electronic Journal of Mathematics, 2008;3(1):1-5.
• [15] Palásti I. On the Strong Connectedness of Directed Random Graphs. Studia Scientiarum Mathematicarum Hungarica, 1966;1:205-214.
• [16] Karp R. Reducibility among Combinatorial Problems. Proc. Symposium on Complexity of Computer Computations. 1972 pp. 85-103. doi:10.1007/978-1-4684-2001-2_9.
• [17] Even G, Naor J, Rao S, Schieber B. Divide-and-conquer Approximation Algorithms via Spreading Metrics. Journal of the ACM, 2000;47(4):585-616. doi:10.1145/347476.347478.
• [18] Even G, Naor J, Schieber B, Sudan M. Approximating Minimum Feedback Sets and Multicuts in Directed Graphs. Algorithmica, 1998;20(2):151-174. doi:10.1007/PL00009191.
• [19] Seymour P. Packing Directed Circuits Fractionally. Combinatorica, 1995;15(2):281-288. doi:10.1007/BF01200760.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).