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.

On Annihilators in Fewer Variables: Basic Theory and Applications

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).
  • Received Date: 2012-06-01
  • Rev Recd Date: 2012-09-01
  • Publish Date: 2013-06-15
  • 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.
  • loading
  • 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.
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (289) PDF downloads(1264) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return