Volume 22 Issue 3
Turn off MathJax
Article Contents
Abstract
References
Related Articles
JIAO Lin, WANG Mingsheng, LI Yongqiang, LIU Meicheng. On Annihilators in Fewer Variables: Basic Theory and Applications[J]. Chinese Journal of Electronics, 2013, 22(3): 489-494.
Citation: JIAO Lin, WANG Mingsheng, LI Yongqiang, LIU Meicheng. On Annihilators in Fewer Variables: Basic Theory and Applications[J]. Chinese Journal of Electronics, 2013, 22(3): 489-494.
shu

On Annihilators in Fewer Variables: Basic Theory and Applications

  • 1.

    Institute of Software, Chinese Academy of Sciences, Beijing 100190, China;

  • 2.

    Graduate University of Chinese Academy of Sciences, Beijing 100049, China;

  • 3.

    State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China

Funds: This work is supported by the National Natural Science Foundation of China (No.60970134, No.11171323), the IIE's Cryptography Research Project (No.Y2Z0011102), and the Strategic Priority Research Program of the Chinese Academy of Sciences (No.XDA06010701).
More Information
  • Received Date: May 31, 2012
  • Revised Date: August 31, 2012
  • Published Date: June 14, 2013
    Graphical Abstract
    • Abstract
  • Algebraic attacks on stream ciphers exploit annihilators of low degree. From another point of view, we concentrate on annihilators in fewer variables in this paper. This work consists of two parts. Firstly, the concept of singular annihilators is proposed and the basic theory is established. Secondly, we present two applications of singular annihilators. We propose a variant of the Filter states guessing attack (FSGA) introduced by Pasalic (2009). Our attack outperforms the FSGA in many cases. Moreover, we put forward a probabilistic algorithm, which can screen out a large number of Boolean functions with annihilators of low degree at a lower cost for the resistance against algebraic attacks.
    • FullText(HTML)
    • References (20)
  • A. Biryukov, A. Shamir, “Cryptanalytic time-memory-data trade-offs for stream ciphers”, ASIACRYPT, kyoto, Japan, Springer-Verlag, LNCS 1976, pp.1-14, 2000.
    P. Hawkes, G. Rose, “Guess-and-determine attacks on SNOW”, SAC, Madrid, Spain, Springer-Verlag, LNCS 2595, pp.37-46, 2002.
    T. Slegenthaler, “Decrypting a class of stream ciphers using ciphertext only”, IEEE Transactions on computers, Vol.34, No.1, pp.81-85, 1985.
    W. Meier, O. Staffelbach, “Fast correlation attacks on certain stream ciphers”, Journal of Cryptology, Vol.1, No.3, pp.159176, 1989.
    Z. Zhuo, W. Zhang, S. Gao, G. Xiao, “On correlation properties of Boolean functions”, Acta Electronica Sinica, Vol.39, No.1, pp.143-146, 2011. (in Chinese)
    N. Courtois, W. Meier, “Algebraic attacks on stream ciphers with linear feedback”, EUROCRYPT, Warsaw, Poland, Springer-Verlag, LNCS 2656, pp.346-359, 2003.
    F. Armknecht, M. Krause, “Algebraic attacks on stream combiners with memory”, CRYPTO, Santa Barbara, California, USA, Springer-Verlag, LNCS 2729, pp.162-176, 2003.
    N. Courtois, “Fast algebraic attacks on stream ciphers with linear feedback”, CRYPTO, Santa Barbara, California, USA, Springer-Verlag, LNCS 2729, pp.176-194, 2003.
    W. Meier, E. Pasalic, “Algebraic attacks and decomposition of Boolean functions”, EUROCRYPT, Interlaken, Switzerland,Springer-Verlag, LNCS 3027, pp.474-491, 2004.
    N. Li, L. Qu, W. Qi et al., “On the construction of Boolean functions with optimal algebraic immunity”, IEEE Transactions on Information Theory, Vol.54, No.3, pp.1330-1334, 2008.
    D. Dalai, S. Maitra, S. Sarkar, “Basic theory in construction of Boolean functions with maximum possible annihilator immunity”, Designs, Codes and Cryptography, Vol.40, No.1, pp.4158, 2006.
    C. Carlet, K. Feng, “An infinite class of balanced functions with optimal algebraic immunity, good immunity to fast algebraic attacks and good nonlinearity advances in cryptology”, ASIACRYPT, Melbourne, Australia, Springer-Verlag, LNCS 5350, pp.425-440, 2008.
    E. Pasalic, “Almost fully optimized infinite classes of Boolean functions resistant to (fast) algebraic cryptanalysis”, ICISC, Korea, Springer-Verlag, LNCS 5461, pp.399-414, 2009.
    M. Liu, D. Lin, “Results on the immunity of Boolean functions against probabilistic algebraic attacks”, Information Security and Privacy, Melbourne, Australia, Springer-Verlag, LNCS 6812, pp.34-46, 2011.
    E. Pasalic, “On guess and determine cryptanalysis of LFSRbased stream ciphers”, IEEE Transactions on Information Theory, Vol.55, No.7, pp.3398-3406, 2009.
    Y. Wei, E. Pasalic, Y. Hu, “Guess and determine attacks on filter generators revisited”, IEEE Transactions on Information Theory, Vol.58, No.4, pp.2530-2539, 2012.
    F. Armknetcht, C. Carlet, P. Gaborit et al., “Efficient computation of algebraic immunity for algebraic and fast algebraic attacks”, EUROCRYPT, Heidelberg, Germany, Springer-Verlag, LNCS 4004, pp.147-164, 2006.
    F. Didier, “Using Wiedemann's algorithm to compute the immunity against algebraic and fast algebraic attacks progress in cryptology”, INDOCRYPT, Kolkata, India, Springer-Verlag, LNCS 4329, pp.236-250, 2006.
    S. Smyshlyaev. “Perfectly balanced Boolean functions and Golic conjecture”, Journal of Cryptology, Vol.25, No.3, pp.464483, 2012.
    M. Liu, Y. Du, “On designated-weight Boolean functions with highest algebraic immunity”, Science China Mathematics,Vol.53, No.11, pp.2847-2854, 2010.
    • Related Articles

  • Related Articles

    [1]MA Zhen, TIAN Tian, QI Wenfeng. Differential Fault Attack on the Stream Cipher LIZARD[J]. Chinese Journal of Electronics, 2021, 30(3): 534-541. DOI: 10.1049/cje.2021.04.007
    [2]GAO Juntao, LI Xuelian. Security Analysis of A Stream Cipher with Proven Properties[J]. Chinese Journal of Electronics, 2021, 30(2): 210-218. DOI: 10.1049/cje.2021.01.002
    [3]GE Hui, SUN Yujuan, ZHUO Zepeng. Constructions of 1-Resilient Boolean Functions with High Nonlinearity and Good Algebraic Degree[J]. Chinese Journal of Electronics, 2020, 29(4): 667-671. DOI: 10.1049/cje.2020.05.011
    [4]YANG Yinghua, ZENG Xiangyong, XU Yunge. Periods on The Cascade Connection of an LFSR and an NFSR[J]. Chinese Journal of Electronics, 2019, 28(2): 301-308. DOI: 10.1049/cje.2019.01.018
    [5]ZHAO Qinglan, HAN Gang, ZHENG Dong, LI Xiangxue. Constructing Odd-Variable Rotation Symmetric Boolean Functions with Optimal Algebraic Immunity and High Nonlinearity[J]. Chinese Journal of Electronics, 2019, 28(1): 45-51. DOI: 10.1049/cje.2018.01.009
    [6]GUO Jiansheng, LUO Wei, WANG Kun. Multiple Related-Key Differential Attacks on Pure DDP-Based Cipher[J]. Chinese Journal of Electronics, 2016, 25(4): 608-613. DOI: 10.1049/cje.2016.06.006
    [7]LIANG Wanwan, ZENG Xiangyong, XU Yunge. The Periods of a Class of Nonlinear Feedback Shift Register Sequences[J]. Chinese Journal of Electronics, 2016, 25(2): 296-303. DOI: 10.1049/cje.2016.03.016
    [8]ZHUO Zepeng, CHONG Jinfeng. On Algebraic Immunity of Boolean Functions by Concatenation[J]. Chinese Journal of Electronics, 2013, 22(2): 273-276.
    [9]DING Lin, GUAN Jie. Related-Key Chosen IV Attack on K2[J]. Chinese Journal of Electronics, 2011, 20(2): 365-369.
    [10]WU Zhijun and SHI Zhen. Filtering LDoS Attack by FIR Filter[J]. Chinese Journal of Electronics, 2010, 19(2): 275-278.

Catalog

    Get Citation
    PDF
    XML

    Article Metrics

    Article views (531) PDF downloads (1269) Cited by()
    Related

    Links

    IEEE CJE Homepage CNKI Chinese Institute of Electronics Journal of Semiconductors
    E-mail Alert RSS

    Chinese Journal of Electronics

    (Bimonthly)

    ISSN    1022-4653CN  10-1284/TN

    eISSN  2075-5597CODEN CHJEEW

    CJE QR CODE

    CIE QR CODE

    Copyright © Editorial Office of Chinese Journal of Electronics | 京ICP备12041980号-1 | Supported by: Beijing Renhe Information Technology Co., Ltd.  Baidu Analytics

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return