# Bent Combining Functions

Bent functions are boolean functions with maximum nonlinearity and are widely studied for their potential applications in cryptography. Lets say you wanted to use a simple two input AND gate as a nonlinear combiner for the outputs of two Linear Feedback Shift Registers . Because a two 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).Thank you for commenting.

-

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.

-
@DW: nice answer but it does matter what I call the sequence if I am writing a paper that will be seen by experts . I want to be technically correct. Maybe there is no name designation for the sequence I described, why don't you invent a name for it, I will cite you in the paper ;-) –  William Hird Dec 3 '12 at 9:26
@WilliamHird, OK, you are right! It does make sense to use standard terminology. I withdraw my comment about names. (A suggestion for future questions: maybe including the definition of the term you are asking about in the question would help others answer?) –  D.W. Dec 3 '12 at 19:05
@DW: You are right , I did not define what I meant by a bent sequence , I incorrectly assumed that a bent boolean function like the AND function when used as a combining function for psuedorandom sequences will produce a bent sequence. A novice error to be sure. –  William Hird Dec 4 '12 at 7:56

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)}$.

-
I'm not sure how your answer relates to my question. The AND function for two variables is bent according to Claude Carlet(he should know!) so if you use it to combine two m-sequence LFRS"s the output is a nonlinear representation of the input. Looking at the truth table for the AND function we see that three out of four lines of the table resolve to 0. So an attacker does not know if the 0 was caused by inputs {0,0} {0,1} or {1,0}. Of course the output will not be balanced but for my circuit I don't care about balance . Sorry if mis-named this sequence a "bent sequence". –  William Hird Dec 3 '12 at 16:47
You propose taking the AND of two LFSR outputs which is not a bent function in this particular context (where the number of variables is the LFSR length $n$, usually $n \gg 2$), and I doubt very much that Claude would say the AND function is a bent function of $n$ variables. I told you how to get a bent function (of $n = 2m$ variables) from LFSRs with a total of $3n/2$ stages instead of your proposed idea using $2n$ stages. Incidentally, the Kasami sequences that you get this way are slightly imbalanced, but you say you don't care so that is OK. –  Dilip Sarwate Dec 3 '12 at 18:13
How does what Claude said contradict what I said, that the AND function is not a bent function of $n$ variables if $n\gg 2$? You need not snidely and suggestively put Claude's name in quotation marks. For the record, I am an Associate Editor of the journal Cryptography and Communications - Discrete Structures, Boolean Functions and Sequences of which Claude is the Editor, and do know him quite well. I am flagging your comment. –  Dilip Sarwate Dec 4 '12 at 11:01
I meant no disrespect to Mr. Carlet, I was suggesting that I have no way to verify that any emails I have received are actually from the real Mr. Carlet. You have misunderstood my comment. –  William Hird Dec 4 '12 at 12:47