Search

Proofs of Retrievability (PoR) allows a client (verifier) to store a file at an untrusted remote storage, and later be able to check the integrity of the file through an interactive challenge-response protocol. A challenge specifies a random subset of blocks and the response is a function of the challenged block. An unbounded-use PoR scheme allows an arbitrary number of challenge-response interactions. Efficient PoR schemes must minimize the communication complexity of the challenge-response protocol, the storage overhead and computation of response by the prover. The security of a PoR scheme is against an erasing adversary and by showing the existence of an extractor which can extract the file from the set of challenges and their corresponding correct responses. In this paper, we modify the unbounded-use PoR scheme of Shacham and Waters (2008) such that the number of challenged data blocks in each round is determined by a probability distribution over a set of possible values. For the security parameter l, the average number of challenged blocks is O(logl), and so is smaller that the original scheme of Shacham and Waters, and in the worst case, is O(l). The response to a challenge is obtained by XORing the challenged data blocks and so is very fast. We show that to ensure security the original verification method of Shacham and Waters must be slightly modified.

Based on a criterion of permutation polynomials of the form $x^rf(x^{\frac{q-1}{m}})$ by Wan and Lidl (1991) and some very elementary techniques we show existence of permutation binomials of the following forms 1 $x(x^{\frac{2^n-1}{3}}+a) \in \mathbb{F}_{2^n}[x]$, for n>4 2 $x^{\frac{2^{2n}-1}{2^{n}-1} + 1}+ax = x^{2^n+2} + ax \in \mathbb{F}_{2^{2n}}[x]$, for n≥3. In (i), we extend a result of Carlitz (1962) for even characteristic. Moreover we present the count of such permutation binomials when a is in a certain subfield of $\mathbb{F}_{2^n}$. In (ii), we reprove, using much simpler technique, a recent result of Charpin and Kyureghyan (2008) and give the number of permutation binomials of this form. Finally, we discuss some cryptographic relevance of these results.

We consider negabent Boolean functions that have Trace representation. To the best of our knowledge, this is the first ever work on negabent functions with such representation. We completely characterize negabent quadratic monomial functions. We also present necessary and sufficient condition for a Maiorana-McFarland bent function to be a negabent function. As a consequence of that result we present a nice characterization of a bent-negabent Maiorana-McFarland function which is based on the permutation $x \mapsto x^{2^i}$.

We consider a class of 3-error-correcting cyclic codes of length 2m −1 over the two-element field $\mathbb{F}_2$ . The generator polynomial of a code of this class has zeroes $\alpha, \alpha^{2^i+1}$ and $\alpha^{2^j+1}$ , where α is a primitive element of the field ${\mathbb{F}_{2^m}}$ . In short, {1, 2i +1, 2j +1} refers to the zero set of these codes. Kasami in 1971 and Bracken and Helleseth in 2009, showed that cyclic codes with zeroes {1, 2l+1, 23l+1} and {1, 2l+1, 22l+1} respectively are 3-error correcting, where $\gcd(\ell,m) = 1$ . We present a sufficient condition so that the zero set {1, 2l+1, 2p l+1}, $\gcd(\ell,m)=1$ gives a 3-error-correcting cyclic code. The question for p >3 is open. In addition, we determine all the 3-error-correcting cyclic codes in the class {1, 2i +1, 2j +1} for m ${\mathbb{F}_{2^m}}$ . We apply the improved Schaub algorithm in order to find a lower bound of the spectral immunity of a Boolean function related to the zero set {1, 2i +1, 2j +1}.

We study the negabent Boolean functions which are symmetric. The Boolean function which has equal absolute spectral values under the nega-Hadamard transform is called a negabent function. For a bent function, the absolute spectral values are the same under the Hadamard-Walsh transform. Unlike bent functions, negabent functions can exist on odd number of variables. Moreover, all the affine functions are negabent. We prove that a symmetric Boolean function is negabent if and only if it is affine.

In this paper we present a theoretical construction of Rotation Symmetric Boolean Functions (RSBFs) on odd number of variables with maximum possible algebraic immunity (AI) and further these functions are not symmetric. Our RSBFs are of better nonlinearity than the existing theoretical constructions with maximum possible AI. To get very good nonlinearity, which is important for practical cryptographic design, we generalize our construction to a construction cum search technique in the RSBF class. We find 7, 9, 11 variable RSBFs with maximum possible AI having nonlinearities 56, 240, 984 respectively with very small amount of search after our basic construction.

The existence of 9-variable Boolean functions having nonlinearity strictly greater than 240 has been shown very recently (May 2006) by Kavut, Maitra and Yucel; a few functions with nonlinearity 241 have been identified by a heuristic search in the class of Rotation Symmetric Boolean Functions (RSBFs). In this paper, using combinatorial results related to the Walsh spectra of RSBFs, we efficiently perform the exhaustive search to enumerate the 9-variable RSBFs having nonlinearity > 240 and found that there are 8 ×189 many functions with nonlinearity 241 and there is no RSBF having nonlinearity > 241. We further prove that among these functions, there are only two which are different up to the affine equivalence. This is found by utilizing the binary nonsingular circulant matrices and their variants. Finally we explain the coding theoretic significance of these functions. This is the first time orphan cosets of R(1, n) having minimum weight 241 are demonstrated for n = 9. Further they provide odd weight orphans for n = 9; earlier these were known for certain n ≥11.