2
$\begingroup$

Bent functions are Boolean functions with maximum nonlinearity and are widely studied for their potential applications in cryptography. Let's say you want to use a simple $2$-input AND gate as a nonlinear combiner for the outputs of two linear feedback shift registers. Because a $2$-input AND gate is a bent function, is it technically correct to call the output sequence of this combination generator a bent sequence? I need to know this for a paper I am writing.

$\endgroup$

2 Answers 2

2
$\begingroup$

No. As far as I can tell, this does not appear to produce a bent sequence. (Or, if it does, that fact requires proof/justification.)

According to Wikipedia, a "bent sequence" is a sequence of the form $(-1)^{f(x_0)}, \dots, (-1)^{f(x_{2^n-1})}$ where $x_0,\dots,x_{2^n-1}$ is the sequence of $n$-bit values in lexicographic order and $f$ is some bent function. That's different from what you are mentioning. If what you're mentioning happens to fit this definition, that fact is far from obvious.

I don't know if this is the same definition of "bent sequence" you are using. If it isn't, I suggest editing your question to include the definition you are using.

$\endgroup$
0
2
$\begingroup$

Bent functions can be obtained from linear feedback shift registers but not by the method that you propose. In fact, the method you propose (using an AND gate to combine the output of two linear feedback shift registers) will not give you a bent function.

Bent functions (though not by that name) were studied for use as signature sequences in direct-sequence spread-spectrum communications. In the literature on this topic, such sequences are called the small set of Kasami sequences. The sequences are of length (or period) $2^{2m}-1$ and can be obtained as the (XOR) sum of the outputs of two maximal-length linear feedback shift registers (LFSRs) of lengths $2m$ and $m$ respectively. The feedback polynomials of the LFSRs thus are primitive polynomials of degrees $2m$ and $m$ respectively, and they produce maximal-length LFSR sequences ($m$-sequences) of periods $2^{2m-1}$ and $2^m-1$ respectively. Thus, $2^m+1$ copies of one period of the shorter sequence get added into one period of the longer sequence, and the result is of period $2^{2m}-1$. A total of $2^m-1$ distinct sequences can generated by using a fixed nonzero initial loading of the longer LFSR and $2^m-1$ nonzero initial loadings of the shorter LFSR. Note that one cannot choose both feedback polynomials arbitrarily. If the longer polynomial is chosen as a specific primitive polynomial of degree $2m$, then only one primitive polynomial of degree $m$ will give you a small set of Kasami sequences. If the shorter polynomial is chosen first, then the longer one must be chosen from a subset of the set of all primitive polynomial of degree $2m$. For more details, see the paper D. V. Sarwate and M. B. Pursley, "Cross-correlation properties of pseudorandom and related sets of sequences," Proc. IEEE, May 1980.

The set of sequences thus generated are of period or length $2^{2m}-1$ whereas the description of bent functions says they are of length $2^{2m}$. To relate this to Wikipedia's version, consider the Boolean function $$f(\mathbf x) = f(x_1, x_2, \ldots, x_2m) = x_1x_2 \oplus x_3x_4 \oplus \cdots \oplus x_{2m-1}x_{2m}.$$ Wikipedia'a definition says that the bent function is the sequence of values of $(-1)^{f(\mathbf x)}$ as we cycle through the $2^{2m}$ values of $\mathbf x$ in lexicographic order. A sequence from the small set of Kasami sequences cycles through all the nonzero values of $\mathbf x$ in a different order, usually in what might be called shift-register order (successive contents of a length-$2m$ maximal-length LFSR) or Galois-field order (polynomial representation of successive powers of a primitive element of $\mathbb F_{2^{2m}}$. So, if you need the symbols in Wikipedia order, you are going to have to do a permutation of the $2^{2m}-1$ bits from the output of the XOR gate that adds the two seqeuences and prepend a $+1$ to get the missing $(-1)^{f(\mathbf 0)}$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.