SCIENCE CHINA Information Sciences, Volume 63 , Issue 11 : 212206(2020) https://doi.org/10.1007/s11432-019-2813-7

Boolean-network-based approach for construction of filter generators

More info
  • ReceivedNov 24, 2019
  • AcceptedFeb 5, 2020
  • PublishedOct 9, 2020


In this paper, we view filter generators as Boolean networks (BNs), and discuss their power-analysis-based side-channel analysis. An incompletely specified binary sequencealways contains some bits called unnecessary bitscomprising $1$ or $0$. Our motivation for considering this type of sequence is to reduce direct dependencies between side-channel information and key sequences. An algorithm is proposed to determine the unnecessary bitsto increase the key search time required for adversaries rather than simply turning all unnecessary bitsto $0$ (or $1$). Then, to reduce area dissipation, under the framework of semi-tensor product (STP) of matrices, the problem of constructing filter generators with minimum number of stages is converted into the one of determining the corresponding transition matrices. Compared with the existing results, the lower bound of the minimum number of stages is provided, which can reduce the exhaustive search time required to find it. Finally, one example is used to illustrate the efficacy of the proposed algorithm.


[1] Jian Wang , Jiaqi Mu , Shuangqing Wei . Statistical Characterization of Decryption Errors in Block-Ciphered Systems. IEEE Trans Commun, 2015, 63: 4363-4376 CrossRef Google Scholar

[2] Zhong J, Lin D. Driven Stability of Nonlinear Feedback Shift Registers With Inputs. IEEE Trans Commun, 2016, 64: 2274-2284 CrossRef Google Scholar

[3] Zhong J, Lin D. Decomposition of nonlinear feedback shift registers based on Boolean networks. Sci China Inf Sci, 2019, 62: 39110 CrossRef Google Scholar

[4] Liu Y P, Tang X B, Xu Z H. Optimization and temperature effects on sandwich betavoltaic microbattery. Sci China Technol Sci, 2014, 57: 14-18 CrossRef ADS Google Scholar

[5] Kauffman S A. Metabolic stability and epigenesis in randomly constructed genetic nets. J Theor Biol, 1969, 22: 437-467 CrossRef Google Scholar

[6] Zhang Y, Liu Y. Nonlinear second-order multi-agent systems subject to antagonistic interactions without velocity constraints. Appl Math Comput 2020, 364:124667. Google Scholar

[7] Cheng D Z, Qi H S, Li Z Q. Analysis and Control of Boolean Networks: A Semi-tensor Product Approach London: Springer, 2011. Google Scholar

[8] Zhong J, Liu Y, Kit Ian Kou, et al. On the ensemble controllability of Boolean control networks using STP method. Appl Math Comput 2019, 358:51--62. Google Scholar

[9] Lin L, Cao J, Rutkowski L. Robust Event-Triggered Control Invariance of Probabilistic Boolean Control Networks. IEEE Trans Neural Netw Learning Syst, 2020, 31: 1060-1065 CrossRef Google Scholar

[10] Huang C, Lu J, Ho D W C. Stabilization of probabilistic Boolean networks via pinning control strategy. Inf Sci, 2020, 510: 205-217 CrossRef Google Scholar

[11] Zhu S, Lu J, Liu Y. Asymptotical Stability of Probabilistic Boolean Networks With State Delays. IEEE Trans Automat Contr, 2020, 65: 1779-1784 CrossRef Google Scholar

[12] Zhong J, Li B, Liu Y. Output feedback stabilizer design of Boolean networks based on network structure. Front Inform Technol Electron Eng, 2020, 21: 247-259 CrossRef Google Scholar

[13] Li H, Zhao G, Meng M. A survey on applications of semi-tensor product method in engineering. Sci China Inf Sci, 2018, 61: 010202 CrossRef Google Scholar

[14] Xu M, Liu Y, Lou J. Set Stabilization of Probabilistic Boolean Control Networks: A Sampled-Data Control Approach. IEEE Trans Cybern, 2019, : 1-8 CrossRef Google Scholar

[15] Zhu S Y, Liu Y, Lou Y J, et al. Stabilization of logical control networks: An event-triggered control approach. Sci China Inf Sci 2020, 63(1):1--11. Google Scholar

[16] Lu J, Sun L, Liu Y. Stabilization of Boolean Control Networks Under Aperiodic Sampled-Data Control. SIAM J Control Optim, 2018, 56: 4385-4404 CrossRef Google Scholar

[17] Li X H, Lu J Q, Qiu J L, et al. Set stability for switched Boolean networks under open-loop/closed-loop switching signals. Sci China Inf Sci 2018, 61:092207. Google Scholar

[18] Liu Y, Li B, Chen H. Function perturbations on singular Boolean networks. Automatica, 2017, 84: 36-42 CrossRef Google Scholar

[19] Zhu Q, Liu Y, Lu J. Observability of Boolean control networks. Sci China Inf Sci, 2018, 61: 092201 CrossRef Google Scholar

[20] Liu H C, Liu Y, Li Y Y, et al. Observability of Boolean networks via stp and graph methods. IET Control Theor Appl 2018, 13(7):1031--1037. Google Scholar

[21] Liu Y, Li B, Lu J. Pinning Control for the Disturbance Decoupling Problem of Boolean Networks. IEEE Trans Automat Contr, 2017, 62: 6595-6601 CrossRef Google Scholar

[22] Li Y, Liu R, Lou J. Output Tracking of Boolean Control Networks Driven by Constant Reference Signal. IEEE Access, 2019, 7: 112572 CrossRef Google Scholar

[23] Wu Y, Shen T. A Finite Convergence Criterion for the Discounted Optimal Control of Stochastic Logical Networks. IEEE Trans Automat Contr, 2018, 63: 262-268 CrossRef Google Scholar

[24] Li Y, Li H, Xu X. Semi-tensor product approach to minimal-agent consensus control of networked evolutionary games. IET Control Theor Appl, 2018, 246: 2269-2275 CrossRef Google Scholar

[25] Zhao J, Chen Z, Liu Z. Modeling and analysis of colored petri net based on the semi-tensor product of matrices. Sci China Inf Sci, 2018, 61: 010205 CrossRef Google Scholar

[26] Li H, Wang Y. Boolean derivative calculation with application to fault detection of combinational circuits via the semi-tensor product method. Automatica, 2012, 48: 688-693 CrossRef Google Scholar

[27] Lu J, Li M, Huang T. The transformation between the Galois NLFSRs and the Fibonacci NLFSRs via semi-tensor product of matrices. Automatica, 2018, 96: 393-397 CrossRef Google Scholar

[28] Dubrova E. On constructing secure and hardware-efficient invertible mappings. In: Proceeding of International Symposium on Multiple-Valued Logic Sapporo, 2016. 211--216. Google Scholar

[29] Liu Z, Wang Y, Cheng D. Nonsingularity of feedback shift registers. Automatica, 2015, 55: 247-253 CrossRef Google Scholar

[30] Lu J, Li M, Liu Y. Nonsingularity of Grain-like cascade FSRs via semi-tensor product. Sci China Inf Sci, 2018, 61: 010204 CrossRef Google Scholar

[31] Zhong J, Lin D. On Minimum Period of Nonlinear Feedback Shift Registers in Grain-Like Structure. IEEE Trans Inform Theor, 2018, 64: 6429-6442 CrossRef Google Scholar

[32] Li N, Dubrova E. Synthesis of power-and area-efficient binary machines for incompletely specified sequences. In: Proceedings of Asia and South Pacific Design Automation Conference Singapore, 2014. 634--639. Google Scholar

[33] Wan Z, Dai Z, Liu M, et al. Nonlinear Feedback Shift Registers (in Chinese. Beijing: Science Press 1978. Google Scholar

[34] Zadeh A A, Heys H M. Simple power analysis applied to nonlinear feedback shift registers. IET Inform Secur, 2014, 3: 188-198 CrossRef Google Scholar

[35] Dubrova E. Synthesis of Binary Machines. IEEE Trans Inform Theor, 2011, 57: 6890-6893 CrossRef Google Scholar

[36] Dubrova E. Synthesis of parallel binary machines. In: Proceedings of the International Conference on Computer-Aided Design San Jose, 2011. 200--206. Google Scholar

[37] Veliz-Cuba A. Reduction of Boolean network models. J Theor Biol, 2011, 289: 167-172 CrossRef Google Scholar

[38] Burman S, Mukhopadhyay D, Veezhinathan K. LFSR based stream ciphers are vulnerable to power attacks. In: Proceedings of International Conference on Cryptology 2007. 384--392. Google Scholar

[39] Goresky M, Klapper A. Algebraic shift register sequences. Cambridge University Press 2012. Google Scholar

[40] Li R, Yang M, Chu T. State Feedback Stabilization for Boolean Control Networks. IEEE Trans Automat Contr, 2013, 58: 1853-1857 CrossRef Google Scholar

  • Table 1  

    Table 1All relations between ${\rm~PD}_{t}$ and $\{{\rm~HW}(x_{1}(t)\oplus~x_{1}(t+1)),~{\rm~HW}(c_{\beta_{t}}\oplus~c_{\beta_{t+1}}),~{\rm~HW}(x_{n}(t+1)\oplus~x_{n}(t+2)),~{\rm~HW}(c_{\beta_{t+1}}\oplus~c_{\beta_{t+2}})\}$

    ${\rm~PD}_{t}$ $\{{\rm~HW}(x_{1}(t)\oplus~x_{1}(t+1)),~{\rm~HW}(c_{\beta_{t}}\oplus~c_{\beta_{t+1}}),~{\rm~HW}(x_{n}(t+1)\oplus~x_{n}(t+2)),~{\rm~HW}(c_{\beta_{t+1}}\oplus~c_{\beta_{t+2}})\}$
    $-$2 0, 0, 1, 1
    $-$1 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1
    0 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1
    1 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0
    2 1, 1, 0, 0

    Algorithm 1 Determine the values of unnecessary bits in sequence $\mathbbm{a}$

    for $t=0$ to $l-1$

    if both of $a_{t}$ and $a_{t+1}$ are unnecessary bits or one of them is unnecessary bit then

    if $(b_{t}\oplus~b_{t+1})=0$ and $(b_{t+1}\oplus~b_{t+2})=1$ then

    Let $a_{t}$ and $a_{t+1}$ satisfy $a_{t}\oplus~a_{t+1}=0$;


    if $(b_{t}\oplus~b_{t+1})=1$ and $(b_{t+1}\oplus~b_{t+2})=0$ then

    Let $a_{t}$ and $a_{t+1}$ satisfy $a_{t}\oplus~a_{t+1}=1$;

    end if

    end if



    end if

    end for

Copyright 2020  CHINA SCIENCE PUBLISHING & MEDIA LTD.  中国科技出版传媒股份有限公司  版权所有

京ICP备14028887号-23       京公网安备11010102003388号