Computing Algebraic Immunity by Reconfigurable Computer
Abstract
Algebraic immunity (AI) is a property of a Boolean function f that measures its susceptibility to an algebraic attack. If f has a low algebraic immunity and f is used in an encryption protocol, then there are ways to successfully cryptanalyze the system. As a result, it is important to have an efficient means to compute the algebraic immunity of Boolean functions. Unfortunately, algebraic immunity is one of the most complex cryptographic properties to compute. For example, it is significantly more difficult to compute than nonlinearity [2]. Here, we show the advantage of a reconfigurable computer in computing a function's algebraic immunity. For example, we show that a reconfigurable computer is 4.9 times faster than a conventional computer in this computation for 5-variable functions. Indeed, we compute the distribution of functions to algebraic immunity for all 5-variable functions, a computation that has not been previously accomplished. Interestingly, the problem we address is to design a logic circuit that computes a characteristic of a logic function.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 2012
- Accession Number
- ADA613768
Entities
People
- Jon T. Butler
- M. E. Mccay
- Pantelimon Stanica
Organizations
- Naval Postgraduate School