The Journal of the Korea institute of electronic communication sciences (한국전자통신학회논문지)

Korea Institute of Electronic Communication Science (한국전자통신학회)
권호 표지
DOI QR코드

DOI QR Code

90/150 RCA Corresponding to Maximum Weight Polynomial with degree 2n

2n 차 최대무게 다항식에 대응하는 90/150 RCA

  • 최언숙 (동명대학교 정보통신공학과) ;
  • 조성진 (부경대학교 응용수학과)
  • Received : 2018.05.21
  • Accepted : 2018.08.15
  • Published : 2018.08.31
Download PDF
⟨ Previous Next ⟩

Abstract

The generalized Hamming weight is one of the important parameters of the linear code. It determines the performance of the code when the linear codes are applied to a cryptographic system. In addition, when the block code is decoded by soft decision using the lattice diagram, it becomes a measure for evaluating the state complexity required for the implementation. In particular, a bit-parallel multiplier on finite fields based on trinomials have been studied. Cellular automata(CA) has superior randomness over LFSR due to its ability to update its state simultaneously by local interaction. In this paper, we deal with the efficient synthesis of the pseudo random number generator, which is one of the important factors in the design of effective cryptosystem. We analyze the property of the characteristic polynomial of the simple 90/150 transition rule block, and propose a synthesis algorithm of the reversible 90/150 CA corresponding to the trinomials $x^2^n+x^{2^n-1}+1$($n{\geq}2$) and the 90/150 reversible CA(RCA) corresponding to the maximum weight polynomial with $2^n$ degree by using this rule block.

일반화된 해밍무게는 선형부호의 중요한 파라미터의 하나로써 암호시스템에 적용할 때 부호의 성능을 결정한다. 그리고 격자도를 이용하여 블록부호를 연판정으로 복호할 때 구현에 필요한 상태복잡도를 평가하는 척도가 되기도 함으로써 그 중요성이 한층 부각되고 있다. 특별히 삼항다항식을 기반으로 하는 유한체 상의 비트-병렬 곱셈기에 대한 연구가 진행되어왔다. 셀룰라오토마타(Cellular Automata, 이하 CA)는 국소적 상호작용에 의해 상태가 동시에 업데이트되는 성질이 있어서 LFSR보다 랜덤성이 우수하다. 본 논문에서는 효과적인 암호시스템 설계에 있어 중요한 요소 중 하나인 의사난수열 생성기의 효과적 합성에 관하여 다룬다. 먼저 간단한 90/150 전이규칙 블록의 특성 다항식의 성질을 분석하고, 이 규칙블록을 이용하여 삼항다항식 $x^2^n+x^{2^n-1}+1$($n{\geq}2$)에 대응하는 가역 90/150 CA와 $2^n$차 최대무게다항식에 대응하는 90/150 가역 CA(RCA)의 합성알고리즘을 제안한다.

Keywords

References

  1. J. Kim and J. Chon, "Decoding problem of random linear codes and its cryptographic application," J. of the Korean Institute of Communication Sciences, vol. 32, no. 6, 2015, pp. 30-38.
  2. E. Jang, "Synchronization and Secure Communication Application of Chaos Based Malasoma System," J. of the Korea Institute of Electronic Communication Sciences, vol. 12, no. 5, 2017, pp. 747-754. https://doi.org/10.13067/JKIECS.2017.12.5.747
  3. J. Saidov, B. Kim, J. Lee, and G. Lee, "Distributed Hardware Security System with Secure Key Update," J. of the Korea Institute of Electronic Communication Sciences, vol. 12, no. 4, 2017, pp. 671-678. https://doi.org/10.13067/JKIECS.2017.12.4.671
  4. N. Jang, C. Kim, S. Hong, and Y. Park, "Efficient Bit-Parallel Shifted Polynomial Basis Multipliers for All Irreducible Trinomial," J. of the Korea Institute of Information Security & Cryptology, vol. 19, no. 2, 2009, pp.49-61.
  5. S. Wolfram, "Cryptography with Cellular Automata," in Advances in Cryintology: Crypto '85 Proceedings, Lecture Notes in Computer Science 218, Springer, 1986, pp. 429-432.
  6. P. Hortensius, R. McLeod, and H. Card, "Parallel random number generation for VLSI systems using cellular automata," IEEE Trans. on Computers, vol. 38, no. 10, 1989, pp. 1466-1473. https://doi.org/10.1109/12.35843
  7. S. Nandi, B. Kar, and P. Chaudhuri, "Theory and Applications of Cellular Automata in Cryptography," IEEE Trans. on Computers, vol. 43, no. 12, 1994, pp. 1346-1357. https://doi.org/10.1109/12.338094
  8. S. Das and D. Chowdhury, "On usage of cellular automata in strengthening stream ciphers," J. Discrete Mathematical Sciences and Cryptography, vol. 14, no. 4, 2011, pp. 369-390. https://doi.org/10.1080/09720529.2011.10698343
  9. M. Tomassini and M. Perrenoud, "Stream Ciphers with One- and Two-Dimensional Cellular Automata," Parallel Problem Solving from Nature - PPSN VI, Lecture Notes in Computer Science 1917, Springer, 2000, pp. 722-731.
  10. P. Guan, "Cellular Automaton Public-Key Cryptosystern," Complex Systems I, 1987, pp. 51-56.
  11. H. Kim and S. Cho, "Synthesis of Uniform CA and 90/150 Hybrid CA," J. of the Korea Institute of Electronic Communication Sciences, vol. 11, no. 3, 2016, pp. 293-302. https://doi.org/10.13067/JKIECS.2016.11.3.293
  12. U. Choi, S. Cho, M. Kwon, S. Kim, and H. Kim, "Synthesis of 90/102(170)/150 linear CA using 90/150 linear CA," J. of the Korea Institute of Electronic Communication Sciences, vol. 11, no. 9, 2016, pp. 885-892. https://doi.org/10.13067/JKIECS.2016.11.9.885
  13. H. Kim, S. Cho, and U. Choi, "On the Construction of the 90/150 State Transition Matrix Corresponding to the Trinomial $x^{(2^n-1)}+x+1$," J. of the Korea Institute of Electronic Communication Sciences, vol. 13, no. 2, 2017, pp. 383-389. https://doi.org/10.13067/JKIECS.2018.13.2.383
  14. S. Cho, U. Choi, H. Kim, Y. Hwang, J. Kim, and S. Heo, "New synthesis of one-dimensional 90/150 linear hybrid group cellular automata," IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, vol. 26, no. 9, 2007, pp. 1720-1724. https://doi.org/10.1109/TCAD.2007.895784
  15. K. Cattell and J. Muzio, "Synthesis of one-dimensional linear hybrid cellular automata," IEEE Trans. Comput-Aided Design Integrated Circuits and Systems, vol. 15, no. 3, 1996, pp. 325-335. https://doi.org/10.1109/43.489103
  16. A. Sabater and P. Gil, "Synthesis of cryptographic interleaved sequences by means of linear cellular automata," Applied Mathematics Letters, vol. 22, no. 10, 2009, pp. 1518-1524. https://doi.org/10.1016/j.aml.2009.03.018
  17. S. Cho, U. Choi, H. Kim, and H. An, "Analysis of nonlinear sequences based on shrinking generator," J. of the Korea Institute of Electronic Communication Sciences, vol. 5, no. 4, 2010, pp. 412-417.
  18. U. Choi, S. Cho, H. Kim, and J. Kim, "90/150 CA corresponding to polynomial of maximum weight," J. of Cellular Automata, vol. 13, no. 4, 2018, pp.347-358.
  19. U. Choi and S. Cho, "Characteristic Polynomial of 90 UCA and Synthesis of CA using Transition Rule Blocks," J. of the Korea Institute of Electronic Communication Sciences, J. of the Korea Institute of Electronic Communication Sciences, vol. 13, no. 3, 2018, pp. 593-600. https://doi.org/10.13067/JKIECS.2018.13.3.593
  20. P. Chaudhuri, D.RChowdhury, S. Nandi and S. Chattopadhyay, Additive Cellular Automata Theory and Applications. Los Alamitos, California: IEEE Computer Society Press, 1997.
  21. U. Choi, S. Cho, and G. Kong, "Analysis of Characteristic Polynomial of Cellular Automata with Symmetrical Transition Rules," Proceedings of the Jangjeon Mathematical Society, vol. 18, no. 1, 2015, pp. 85-93.
  22. H. Kim, S. Cho, U. Choi, and M. Kwon, "Analysis of 90/150 Cellular Automata with Extended Symmetric Transition Rules." Proceedings of the Jangjeon Mathematical Society, vol. 20, no. 2, 2017, pp. 193-201.
  23. H. Meyn, "On the Construction of Irreducible Self-Reciprocal Polynomials Over Finite Fields," Applicable Algebra in Engineering, Communication and Computing, vol. 1, no. 1, 1990, pp. 43-53. https://doi.org/10.1007/BF01810846
  24. S. Golomb, Shift Register Sequences. Los Alamitos, California: Aegean Park Press, 1982.