American Institute of Mathematical Sciences

Advanced
February  2017, 11(1): 139-150. doi: 10.3934/amc.2017008

AFSRs synthesis with the extended Euclidean rational approximation algorithm

Weihua Liu 1, and  Andrew Klapper 2,

1. 

Department of Computer Science, William Paterson University of New Jersey, Wayne, NJ 07470 USA
2. 

Department of Computer Science, University of Kentucky, Lexington, KY 40506, USA

Received  July 2015 Published  February 2017

Fund Project: This material is based upon work supported by the National Science Foundation under grants No. CCF-0514660 and CNS-1420227. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation.

Pseudo-random sequence generators are widely used in many areas, such as stream ciphers, radar systems, Monte-Carlo simulations and multiple access systems. Generalization of linear feedback shift registers (LFSRs) and feedback with carry shift registers (FCSRs), algebraic feedback shift registers (AFSRs) [7] can generate pseudo-random sequences over an arbitrary finite field. In this paper, we present an algorithm derived from the Extended Euclidean Algorithm that can efficiently find a smallest AFSR over a quadratic field for a given sequence. It is an analog of the Extended Euclidean Rational Approximation Algorithm [1] used in solving the FCSR synthesis problem. For a given sequence $\mathbf{a}$, $2\Lambda(\alpha)+1$ terms of sequence $\mathbf{a}$ are needed to find the smallest AFSR, where $\Lambda(\alpha)$ is a complexity measure that reflects the size of the smallest AFSR that outputs $\mathbf{a}$.

Keywords: AFSR synthesis, rational approximation, the extended Euclidean algorithm, sequences, stream ciphers.
Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.
Citation: Weihua Liu, Andrew Klapper. AFSRs synthesis with the extended Euclidean rational approximation algorithm. Advances in Mathematics of Communications, 2017, 11 (1) : 139-150. doi: 10.3934/amc.2017008
References:
[1]

F. Arnault, T. P. Berger and A. Necer, Feedback with carry shift registers synthesis with the Euclidean algorithm, IEEE Trans. Inform. Theory, 50 (2004), 910-917.  doi: 10.1109/TIT.2004.826651.

[2]

N. Courtois and W. Meier, Algebraic attacks on stream ciphers with linear feedback, in Advances in Cryptology-EUROCRYPT 2003, Springer, 2003,345-359. doi: 10.1007/3-540-39200-9_21.

[3]

M. Goresky and A. Klapper, Feedback registers based on ramified extensions of the 2-adic numbers, in Advances in Cryptology-EUROCRYPT '94, Springer, 1995,215-222. doi: 10.1007/BFb0053437.

[4]

M. Goresky and A. Klapper, Algebraic Shift Register Sequences, Cambridge Univ. Press, 2012.

[5]

A. Klapper and M. Goresky, Cryptanalysis based on 2-adic rational approximation, in Advances in Cryptology-CRYPTO '95, Springer, 1995,262-273. doi: 10.1007/3-540-44750-4_21.

[6]

A. Klapper and M. Goresky, Feedback shift registers. 2-adic span, and combiners with memory, Cryptology J., 10 (1997), 111-147.  doi: 10.1007/s001459900024.

[7]

A. Klapper and J. Xu, Algebraic feedback shift registers, Theoret. Comp. Sci., 226 (1999), 61-92.  doi: 10.1016/S0304-3975(99)00066-3.

[8]

A. Klapper and J. Xu, Register synthesis for algebraic feedback shift registers based on nonprimes, Des. Codes Cryptogr., 31 (2004), 227-250.  doi: 10.1023/B:DESI.0000015886.71135.e1.

[9]

D. Lee, J. Kim, J. Hong, J. Han and D. Moon, Algebraic attacks on summation generators, in Fast Software Encryption, Springer, 2004, 34-48. doi: 10.1007/978-3-540-25937-4_3.

[10]

W. LeVeque, Topics in Number Theory, Courier Corporation, 2002.

[11]

W. Liu and A. Klapper, A lattice rational approximation algorithm for AFSRs over quadratic integer rings, in Sequences and Their Applications -SETA 2014, Springer, 2014,200-211. doi: 10.1007/978-3-319-12325-7_17.

[12]

J. L. Massey, Shift register synthesis and BCH decoding, IEEE Trans. Inform. Theory, 15 (1969), 122-127. 

[13]

P. Q. Nguyen and D. Stehlé, Low-dimensional lattice basis reduction revisited, ACM Trans. Algor. (TALG), 5 (2009), 46. doi: 10.1145/1597036.1597050.

show all references

References:
[1]

F. Arnault, T. P. Berger and A. Necer, Feedback with carry shift registers synthesis with the Euclidean algorithm, IEEE Trans. Inform. Theory, 50 (2004), 910-917.  doi: 10.1109/TIT.2004.826651.

[2]

N. Courtois and W. Meier, Algebraic attacks on stream ciphers with linear feedback, in Advances in Cryptology-EUROCRYPT 2003, Springer, 2003,345-359. doi: 10.1007/3-540-39200-9_21.

[3]

M. Goresky and A. Klapper, Feedback registers based on ramified extensions of the 2-adic numbers, in Advances in Cryptology-EUROCRYPT '94, Springer, 1995,215-222. doi: 10.1007/BFb0053437.

[4]

M. Goresky and A. Klapper, Algebraic Shift Register Sequences, Cambridge Univ. Press, 2012.

[5]

A. Klapper and M. Goresky, Cryptanalysis based on 2-adic rational approximation, in Advances in Cryptology-CRYPTO '95, Springer, 1995,262-273. doi: 10.1007/3-540-44750-4_21.

[6]

A. Klapper and M. Goresky, Feedback shift registers. 2-adic span, and combiners with memory, Cryptology J., 10 (1997), 111-147.  doi: 10.1007/s001459900024.

[7]

A. Klapper and J. Xu, Algebraic feedback shift registers, Theoret. Comp. Sci., 226 (1999), 61-92.  doi: 10.1016/S0304-3975(99)00066-3.

[8]

A. Klapper and J. Xu, Register synthesis for algebraic feedback shift registers based on nonprimes, Des. Codes Cryptogr., 31 (2004), 227-250.  doi: 10.1023/B:DESI.0000015886.71135.e1.

[9]

D. Lee, J. Kim, J. Hong, J. Han and D. Moon, Algebraic attacks on summation generators, in Fast Software Encryption, Springer, 2004, 34-48. doi: 10.1007/978-3-540-25937-4_3.

[10]

W. LeVeque, Topics in Number Theory, Courier Corporation, 2002.

[11]

W. Liu and A. Klapper, A lattice rational approximation algorithm for AFSRs over quadratic integer rings, in Sequences and Their Applications -SETA 2014, Springer, 2014,200-211. doi: 10.1007/978-3-319-12325-7_17.

[12]

J. L. Massey, Shift register synthesis and BCH decoding, IEEE Trans. Inform. Theory, 15 (1969), 122-127. 

[13]

P. Q. Nguyen and D. Stehlé, Low-dimensional lattice basis reduction revisited, ACM Trans. Algor. (TALG), 5 (2009), 46. doi: 10.1145/1597036.1597050.

Figure 1.  An algebraic feedback shift register of Length m
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  The Extended Euclidean Rational Approximation Algorithm
Figure Options

Download full-size image

Download as PowerPoint slide

[1]

Alexander Zeh, Antonia Wachter. Fast multi-sequence shift-register synthesis with the Euclidean algorithm. Advances in Mathematics of Communications, 2011, 5 (4) : 667-680. doi: 10.3934/amc.2011.5.667
[2]

Ravi Anand, Dibyendu Roy, Santanu Sarkar. Some results on lightweight stream ciphers Fountain v1 & Lizard. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020128
[3]

Claude Carlet, Khoongming Khoo, Chu-Wee Lim, Chuan-Wen Loe. On an improved correlation analysis of stream ciphers using multi-output Boolean functions and the related generalized notion of nonlinearity. Advances in Mathematics of Communications, 2008, 2 (2) : 201-221. doi: 10.3934/amc.2008.2.201
[4]

A. Gasull, Víctor Mañosa, Xavier Xarles. Rational periodic sequences for the Lyness recurrence. Discrete and Continuous Dynamical Systems, 2012, 32 (2) : 587-604. doi: 10.3934/dcds.2012.32.587
[5]

Domingo Gomez-Perez, Ana-Isabel Gomez, Andrew Tirkel. Arrays composed from the extended rational cycle. Advances in Mathematics of Communications, 2017, 11 (2) : 313-327. doi: 10.3934/amc.2017024
[6]

Hassan Emamirad, Arnaud Rougirel. A functional calculus approach for the rational approximation with nonuniform partitions. Discrete and Continuous Dynamical Systems, 2008, 22 (4) : 955-972. doi: 10.3934/dcds.2008.22.955
[7]

Martin Hanke, William Rundell. On rational approximation methods for inverse source problems. Inverse Problems and Imaging, 2011, 5 (1) : 185-202. doi: 10.3934/ipi.2011.5.185
[8]

Rich Stankewitz, Hiroki Sumi. Random backward iteration algorithm for Julia sets of rational semigroups. Discrete and Continuous Dynamical Systems, 2015, 35 (5) : 2165-2175. doi: 10.3934/dcds.2015.35.2165
[9]

Mary Wilkerson. Thurston's algorithm and rational maps from quadratic polynomial matings. Discrete and Continuous Dynamical Systems - S, 2019, 12 (8) : 2403-2433. doi: 10.3934/dcdss.2019151
[10]

Frank Neubrander, Koray Özer, Lee Windsperger. On subdiagonal rational Padé approximations and the Brenner-Thomée approximation theorem for operator semigroups. Discrete and Continuous Dynamical Systems - S, 2020, 13 (12) : 3565-3579. doi: 10.3934/dcdss.2020238
[11]

Xinmin Xiang. The long-time behaviour for nonlinear Schrödinger equation and its rational pseudospectral approximation. Discrete and Continuous Dynamical Systems - B, 2005, 5 (2) : 469-488. doi: 10.3934/dcdsb.2005.5.469
[12]

Kyung Jae Kim, Jin Soo Park, Bong Dae Choi. Admission control scheme of extended rtPS algorithm for VoIP service in IEEE 802.16e with adaptive modulation and coding. Journal of Industrial and Management Optimization, 2010, 6 (3) : 641-660. doi: 10.3934/jimo.2010.6.641
[13]

Steven Richardson, Song Wang. The viscosity approximation to the Hamilton-Jacobi-Bellman equation in optimal feedback control: Upper bounds for extended domains. Journal of Industrial and Management Optimization, 2010, 6 (1) : 161-175. doi: 10.3934/jimo.2010.6.161
[14]

Fan Yuan, Dachuan Xu, Donglei Du, Min Li. An exact algorithm for stable instances of the $ k $-means problem with penalties in fixed-dimensional Euclidean space. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021122
[15]

David Julitz. Numerical approximation of atmospheric-ocean models with subdivision algorithm. Discrete and Continuous Dynamical Systems, 2007, 18 (2&3) : 429-447. doi: 10.3934/dcds.2007.18.429
[16]

Zhenbo Wang. Worst-case performance of the successive approximation algorithm for four identical knapsacks. Journal of Industrial and Management Optimization, 2012, 8 (3) : 651-656. doi: 10.3934/jimo.2012.8.651
[17]

Gaidi Li, Zhen Wang, Dachuan Xu. An approximation algorithm for the $k$-level facility location problem with submodular penalties. Journal of Industrial and Management Optimization, 2012, 8 (3) : 521-529. doi: 10.3934/jimo.2012.8.521
[18]

Brigitte Vallée. Euclidean dynamics. Discrete and Continuous Dynamical Systems, 2006, 15 (1) : 281-352. doi: 10.3934/dcds.2006.15.281
[19]

Marco Calderini. A note on some algebraic trapdoors for block ciphers. Advances in Mathematics of Communications, 2018, 12 (3) : 515-524. doi: 10.3934/amc.2018030
[20]

Riccardo Aragona, Alessio Meneghetti. Type-preserving matrices and security of block ciphers. Advances in Mathematics of Communications, 2019, 13 (2) : 235-251. doi: 10.3934/amc.2019016

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (136)
  • HTML views (63)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy