ABSTRACT

It is difficult to find Boolean functions achieving many good cryptographic properties. Recently, Tu and Deng obtained two classes of Boolean functions with good properties based on a combinatorial conjecture about binary strings. In this paper, using different approaches, we prove this conjecture is true in some cases. This conjecture has resisted different attempts of proof since it is hard to find a recursive method. In this paper we give a recursive formula in a special case.

1. Introduction

Let x be a nonnegative integer. If the binary expansion of x is

then the Hamming weight of x is

.

In [1] Tu and Deng proposed the following conjecture.

Conjecture 1: Let

where. Then the cardinality.

Based on this conjecture, Tu and Deng [1] constructed two classes of Boolean functions with many good cryptographic properties. In this paper we always use the following bijection, where is the set of binary strings of length except the string consisting of n copies of 1.

We use to denote the length of a binary string

. Let. And we use the following notation where there are k consecutive 1 and m consecutive 0 in the string.

In [1] Tu and Deng construct an algorithm which they used it to show that the conjecture above is true when. Cusick, Li and Stanica [2] show that Conjecture 1 is true when. In this paper, we will consider the following conjecture, which is equivalent to Conjecture 1.

Conjecture 2: Suppose that

Let

then.

The following lemma is easy so we omit the proof.

Lemma 1.1 Let Then following statements are true:

1)

2);

3) The map is bijective.

Hence

So the authors in [3] actually showed that Conjecture 2 is true when

.

According to Lemma 1.1. Deng and Yuan [4] show that Conjecture 2 is true if

The outline of this paper is as follows. In Section 2 we introduce some notations. In Section 3, we consider what happen if we change some digit 1 into 0 in the strings. We get a recursive formula about and prove a new case of the conjecture.

2. A Partition of

The following lemma is about the relation between and, which is proved in [4].

Lemma 2.1 Let

Suppose that

where Assume that. Then

where we set

Let

for any and

Then

and

which are disjoin unions. We define a partition on according to Lemma 2.1.

Definition 2.1 Let be a binary string of length n. Suppose that

and

where Let be a binary string. Suppose that

where We set

to be the subset of such that if and only if the following two conditions hold i), if

ii), if

And we will use that notation if.

Definition 2.2 Let and be two given binary strings. For any, we set, if for each.

We say that is free if there are two strings and in such that and.

From Definition 2.1 and Lemma 2.1 we see that

andwhere k is the number of indices such that is free.

Example 2.1 Let

, , and

Then

and

,

,

.

So

, and.

Moreover, by Definition 2.2 if and only if, or. That is, is free for. We also have if and only if

,

if and only if

, or.

3. Main Results

If with each, then we say that the block of is. Jean-P. Flori and H. Randriam [5] give some asymptotic results when each. In particular, they show that Conjecture 2 is true if the block of t is smaller than 3 or each is sufficient large for a fixed length of block. We give a recursive formula to show that we can restrict our attention to the case each is smaller than the block of in this situation. They also conjectured that

if.

Lemma 3.1 Let

and

with

and.

Let

for,

and

Then

Proof. Note that for any, if, then for each, moreover in this case we have

.

Let

then. Similarly we write

where

We observe that if, then if and only if each Now if by comparing the number of free indices we have

.

Hence,. If each, then

.

Suppose that. Then

So

Therefore

This finishes the proof.

Remark 3.1 Let with. It is clear that

for any So we use the following notation means that there are sufficient consecutive 0 in the string.

We set

for.

Theorem 3.1 Let

, ,

, ,

, where each and Then

.

Proof. Suppose that those strings have the same length and. By Lemma 3.1

Let

.

If, by comparing the number of free indices we have

where. We set

and

.

Then

Let

and

.

Now consider the following mapping and. If

andthen

.

Then

.

So

.

If

then

.

It is easy to see that

and.

By the discussion above we obtain

, and.

This finishes the proof.

Corollary 3.1 With the same notations in Theorem 3.1. Suppose that

then

.

Proof. We proof the statement by induction on

.

The case implies that

.

This was proved in [4]. Without loss of generality we can assume that and. By induction

by Theorem 3.1

.

The proof is completed by induction on.

Corollary 3.2 Let. Then

.

Proof. By Corollary 3.1 it suffice to show that case when each. So we have, which is proved in [4].

REFERENCES