Abstract. The influence of a variable is an important concept in the analysis of Boolean functions. The more general notion of influence of a set of variables on a Boolean function has four separate definitions in the literature. In the present work, we introduce a new definition of influence of a set of variables which is based on the auto-correlation function and develop its basic theory. Among the new results that we obtain are generalizations of the Poincaré inequality and the edge expansion property of the influence of a single variable. Further, we obtain new characterizations of resilient and bent functions using the notion of influence. We show that the previous definition of influence due to Fischer et al. [ Proceedings of the 43 rd Symposium on Foundations of Computer Science (FOCS 2002 ), Vancouver, BC, Canada, IEEE Computer Society, 2002, pp. 103–112] and Blais [ Proceedings of the 41 st Annual ACM Symposium on Theory of Computing, STOC 2009, M. Mitzenmacher, ed., Bethesda, MD, ACM, 2009, pp. 151–158] is half the value of the auto-correlation based influence that we introduce. Regarding the other prior notions of influence, we make a detailed study of these and show that each of these definitions does not satisfy one or more desirable properties that a notion of influence may be expected to satisfy.

We propose two new algorithms for 4-way vectorization of the well known Montgomery ladder over elliptic curves of Montgomery form. The first algorithm is suitable for variable base scalar multiplication. In comparison to the previous work by Hisilet al.[17], it eliminates a number of non-multiplication operations at the cost of a single multiplication by a curve constant. Implementation results show this trade-off to be advantageous. The second algorithm is suitable for fixed base scalar multiplication and provides clear speed improvement over a previous vectorization strategy due to Costigan and Schwabe (2009). The well known Montgomery curves Curve25519 and Curve448 are part of the TLS protocol, version 1.3. For these two curves, we provide constant time assembly implementations of the new algorithms. Additionally, for the algorithm of Hisilet al.[17], we provide improved implementations for Curve25519 and new implementation for Curve448. Timings results on the Haswell and Skylake processors indicate that in practice the new algorithms are to be preferred over previous methods for scalar multiplication on these curves.

This paper makes a comprehensive comparison of the efficiencies of vectorized implementations of Kummer lines and Montgomery curves at various security levels. For the comparison, nine Kummer lines are considered, out of which eight are new, and new assembly implementations of all nine Kummer lines have been made. Seven previously proposed Montgomery curves are considered and new vectorized assembly implementations have been made for three of them. Our comparisons show that for all security levels, Kummer lines are consistently faster than Montgomery curves, though the speed-up gap is not much.

Poly1305 is a polynomial hash function designed by Bernstein in 2005. Presently, it is part of several major platforms, including the Transport Layer Security protocol. Vectorised implementation of Poly1305 was proposed by Goll and Gueron in 2015. The authors provide some simple algorithmic improvements to the Goll–Gueron vectorisation strategy. Implementation of the modified strategy on modern Intel processors shows marked improvements in speed for short messages.

In this study, the authors introduce new Montgomery and Edwards form elliptic curves targeted at the 256‐bit security level. To this end, they work with three primes, namely , and . While has been considered earlier in the literature, and are new. They define a pair of birationally equivalent Montgomery and Edwards form curves over all the three primes. Efficient 64‐bit assembly implementations targeted at Skylake and later generation Intel processors have been made for the shared secret computation phase of the Diffie‐Hellman key agreement protocol for the new Montgomery curves. Curve448 of the Transport Layer Security, Version 1.3 is a Montgomery curve which provides security at the 224‐bit security level. Compared to the best publicly available 64‐bit implementation of Curve448, the new Montgomery curve over leads to a 3–4% slowdown and the new Montgomery curve over leads to a 4.5–5% slowdown; on the other hand, 29 and 30.5 extra bits of security, respectively, are gained. For designers aiming for the 256‐bit security level, the new curves over and provide an acceptable trade‐off between security and efficiency.

In Broadcast Encryption (BE) systems like Pay-TV, AACS, online content sharing and broadcasting, reducing the header length (communication overhead per session) is of practical interest. The Subset Difference (SD) scheme due to Naor-Naor-Lotspiech (NNL) is the most popularly used BE scheme. We introduce the$(a,b,\gamma)$augmented binary tree subset difference ($(a,b,\gamma)$-ABTSD) scheme which is a generalization of the NNL-SD scheme. By varying the parameters$(a,b,\gamma)$, it is possible to obtain$O(n\log n)$different schemes. The average header length achieved by the new schemes is smaller than all known schemes having the same decryption time as that of the NNL-SD scheme and achieving non-trivial trade-offs between the user storage and the header size. The amount of key material that a user is required to store increases. For the earlier mentioned applications, reducing header size and achieving fast decryption is perhaps more of a concern than the user storage.

This paper describes the first constructions of identity-based broadcast encryption (IBBE) using Type-3 pairings, which can be proved secure against adaptive-identity attacks based on the Symmetric eXternal Diffie-Hellman assumption (which is a static, if not a standard, assumption) achieving a security degradation which is not exponential in the size of the target identity set. The constructions are obtained by extending the currently known most efficient identity-based encryption scheme proposed by Jutla and Roy in 2013. The new constructions fill both a practical and a theoretical gap in the literature on efficient IBBE schemes.

This paper builds on the variant of the function field sieve (FFS) algorithm for the medium prime case introduced by Joux and Lercier in 2006. We make several contributions. The first contribution uses a divisibility and smoothness technique and goes on to develop a sieving method based on the technique. This leads to significant practical efficiency improvements in the descent phase and also provides improvement to Joux's pinpointing technique. The second contribution is a detailed analysis of the degree of freedom and the use of a walk technique in the descent phase of the algorithm. Such analysis shows that it is possible to compute discrete logarithms over certain fields, which are excluded by the earlier analyses performed by Joux and Lercier (2006) and Joux (2013). In concrete terms, we present computations of discrete logs for fields with 16 and 19-bit prime characteristic. We also provide concrete analysis of the effectiveness of the FFS algorithm for certain fields of characteristic ranging from 16 to 32-bit primes. The final contribution is to perform a complete asymptotic analysis of the FFS algorithm for fields FQwith p = LQ(1/3, c). This closes gaps and corrects errors in the analysis earlier performed by Joux-Lercier and Joux and also provides new insights into the asymptotic behavior of the algorithm.

The problem of securing data present on USB memories and SD cards has not been adequately addressed in the cryptography literature. While the formal notion of a tweakable enciphering scheme (TES) is well accepted as the proper primitive for secure data storage, the real challenge is to design a low cost TES which can perform at the data rates of the targeted memory devices. In this work, we provide the first answer to this problem. Our solution, called STES, combines a stream cipher with a XOR universal hash function. The security of STES is rigorously analyzed in the usual manner of provable security approach. By carefully defining appropriate variants of the multi-linear hash function and the pseudo-dot product based hash function we obtain controllable trade-offs between area and throughput. We combine the hash function with the recent hardware oriented stream ciphers, namely Mickey, Grain and Trivium. Our implementations are targeted towards two low cost FPGAs-Xilinx Spartan 3 and Lattice ICE40. Simulation results demonstrate that the speeds of encryption/decryption match the data rates of different USB and SD memories. We believe that our work opens up the possibility of actually putting FPGAs within controllers of such memories to perform low-level in-place encryption.

Two key parameters of broadcast encryption (BE) schemes are the transmission size and the user storage. Naor-Naor-Lotspiech (2001) introduced the subset difference (SD) scheme achieving a good trade-off between these two parameters. Halevy-Shamir (2002) introduced the idea of layering to reduce user storage of the NNL scheme at the cost of increased transmission overhead. Here, we introduce several simple ideas to obtain new layering strategies with different trade-offs between user storage and transmission overhead. We define the notion of storage minimal layering and describe a dynamic programming algorithm to compute layering schemes for which the user storage is the minimum attainable using layerings. Further, the constrained minimization problem is considered. A method is described which yields BE schemes whose transmission overhead is not much more than the SD scheme but, whose user storage is still significantly lower. Finally, an$O(r\log^2 n)$algorithm is obtained to compute the average transmission overhead for any layering-based scheme where$r$out of$n$users are revoked. This algorithm works for any layering strategy and also for arbitrary number of users. The algorithm has been used here to generate all data for the average transmission overhead.

A new class of polynomials was introduced by Bernstein (Bernstein 2007) which were later named by Sarkar as BernsteinRabin-Winograd (BRW) polynomials (Sarkar 2009). For the purpose of authentication, BRW polynomials offer considerable computational advantage over usual polynomials: (m - 1) multiplications for usual polynomial hashing versus ⌊m/2⌋ multiplications and ⌈log2m⌉ squarings for BRW hashing, where m is the number of message blocks to be authenticated. In this paper, we develop an efficient pipelined hardware architecture for computing BRW polynomials. The BRW polynomials have a nice recursive structure which is amenable to parallelization. While exploring efficient ways to exploit the inherent parallelism in BRW polynomials we discover some interesting combinatorial structural properties of such polynomials. These are used to design an algorithm to decide the order of the multiplications which minimizes pipeline delays. Using the nice structural properties of the BRW polynomials we present a hardware architecture for efficient computation of BRW polynomials. Finally, we provide implementations of tweakable enciphering schemes proposed in Sarkar 2009 which use BRW polynomials. This leads to the fastest known implementation of disk encryption systems.

Bellare and Kohno (2004) introduced the notion of balance to quantify the resistance of a hash function$h$to a generic collision attack. Motivated by their work, we consider the problem of quantifying the resistance of$h$to a generic multicollision attack. To this end, we introduce the notion of$r$-balance$\mu_{r}(h)$of$h$and obtain bounds on the success probability of finding an$r$-collision in terms of$\mu_{r}(h)$. These bounds show that for a hash function with$m$image points, if the number of trials$q$is$\Theta\left (rm^{\left ({{r-1}\over{r}}\right)\mu_{r}(h)}\right)$, then it is possible to find$r$-collisions with a significant probability of success. The behavior of random functions and the expected number of trials to obtain an$r$-collision is studied. These results extend and complete the earlier results obtained by Bellare and Kohno (2004) for collisions (i.e.,$r=2$). Going beyond their work, we provide a new design criteria to provide quantifiable resistance to generic multicollision attacks. Further, we make a detailed probabilistic investigation of the variation of$r$-balance over the set of all functions and obtain support for the view that most functions have$r$-balance close to one.

We revisit the problem of constructing a protocol for performing Authenticated Encryption with Associated Data (AEAD). A technique is described which combines a collision-resistant hash function with a protocol for Authenticated Encryption (AE). The technique is both simple and generic and does not require any additional key material beyond that of the AE protocol. Concrete instantiations are shown where a 256-bit hash function is combined with some known single-pass AE protocols employing either 128-bit or 256-bit block ciphers. This results in possible efficiency improvement in the processing of the header.

A general result is proved for constructions which use a pseudo-random function (PRF) with a “small” domain to build a PRF with a “large” domain. This result is used to analyse a new block-cipher based parallelizable PRF, called iPMAC which improves upon the well-known PMAC algorithm. New authenticated encryption schemes are described and then combined with iPMAC to obtain new schemes for authenticated encryption with associated data. Improvements over well known schemes such as the offset codebook (OCB) mode include avoiding a design-stage discrete logarithm computation, a small speed-up and a smaller size decryption algorithm.

In this work, we study several properties of the SHA-2 design which have been utilized in recent collision attacks against reduced round SHA-2. Small modifications to the SHA-2 design are suggested to thwart these attacks. The modified round function provides the same resistance to linearization attacks as the original SHA-2 round function, but, provides better resistance to non-linear attacks. Our next contribution is to introduce the general idea of "multiple feed-forward" for the construction of cryptographic hash functions. This can provide increased resistance to the Chabaud-Joux type "perturbation-correction" collision attacks. The idea of feed-forward is taken further by introducing the idea of feed-forward across message blocks leading to resistance against generic multi-collision attacks. The net effect of the suggested changes to the SHA-2 design has insignificant impact on the efficiency of computing the digest.

We study the relationship between the Walsh transform and the algebraic normal form (ANF) of a Boolean function. In the first part of the paper, we obtain a formula for the Walsh transform at a certain point in terms of parameters derived from the algebraic normal form. We use previous results by Carlet and Guillot to obtain an explicit expression for the Walsh transform at a point in terms of parameters derived from the ANF. The second part of the paper is devoted to simplify this formula and develop an algorithm to evaluate it. This algorithm can be applied in situations where it is practically impossible to use the fast Walsh transform algorithm. Experimental results show that under certain conditions it is possible to execute our algorithm to evaluate the Walsh transform (at a small set of points) of functions on a few scores of variables having a few hundred terms in the algebraic normal form.

This paper describes several constructions of tweakable strong pseudorandom permutations (SPRPs) built from different modes of operations of a block cipher and suitable universal hash functions. For the electronic codebook (ECB) mode based construction, an invertible blockwise universal hash function is required. We simplify an earlier construction of such a function described by Naor and Reingold. The other modes of operations considered are the output feedback (OFB) mode and a counter-like mode. All the constructions make the same number of block cipher calls and the same number of multiplications. Combined with a class of polynomials defined by Bernstein, the new constructions provide the currently best known algorithms for the important practical problem of disk encryption.

The notion of tweakable block ciphers was formally introduced by Liskov-Rivest-Wagner at Crypto 2002 (the 2002 Annual International Cryptology Conference). The extension and the first construction, called CMC, of this notion to tweakable enciphering schemes which can handle variable length messages was given by Halevi-Rogaway at Crypto 2003. In this paper, we present HCH, which is a new construction of such a scheme. The construction uses two universal hash computations with a counter mode of encryption in-between. This approach was first proposed by McGrew-Viega to build a scheme called XCB and later used by Wang-Feng-Wu, to obtain a scheme called HCTR. A unique feature of HCH compared to all known tweakable enciphering schemes is that HCH uses a single key, can handle arbitrary length messages, and has a quadratic security bound. An important application of a tweakable enciphering scheme is disk encryption. HCH is well suited for this application. We also describe a variant, which can utilize precomputation and makes one less block cipher call. This compares favorably to other hash-encrypt-hash-type constructions, supports better key agility and requires less key material.

This work builds on earlier work by Rogaway at Asiacrypt 2004 on tweakable block cipher (TBC) and modes of operations. Our first contribution is to generalize Rogaway's TBC construction by working over a ring${\mmb R}$and by the use of a masking sequence of functions. The ring${\mmb R}$can be instantiated as either GF$(2^{n})$or as$ {\BBZ }_{2^{n}}$. Further, over GF$(2^{n})$, efficient instantiations of the masking sequence of functions can be done using either a binary linear feedback shift register (LFSR); a powering construction; a cellular automata map; or by using a word-oriented LFSR. Rogaway's TBC construction was built from the powering construction over GF$(2^{n})$. Our second contribution is to use the general TBC construction to instantiate constructions of various modes of operations including authenticated encryption (AE) and message authentication code (MAC). In particular, this gives rise to a family of efficient one-pass AE modes of operation. Out of these, the mode of operation obtained by the use of word-oriented LFSR promises to provide a masking method which is more efficient than the one used in the well known AE protocol called OCB1.

Time-memory trade-off (TMTO) is a twenty five years old technique for inverting one-way functions. The most feasible implementation of TMTO is in special purpose hardware. Till date the work on hardware architecture for TMTO has been somewhat sketchy. In this paper, we describe a systematic architecture for implementing TMTO. We break down the offline and online phases into simpler tasks and identify opportunities for pipelining and parallelism. This results in a sufficiently detailed top-level architecture. To the best of our knowledge, such architecture does not appear in the literature

We provide two new construction methods for nonlinear resilient functions. The first method is a simple modification of a construction due to Zhang and Zheng and constructs n-input, m-output resilient S-boxes with degree d>m. We prove by an application of the Griesmer bound for linear error-correcting codes that the modified Zhang-Zheng construction is superior to the previous method of Cheon in Crypto 2001. Our second construction uses a sharpened version of the Maiorana-McFarland technique to construct nonlinear resilient functions. The nonlinearity obtained by our second construction is better than previously known construction methods.

In 2001, Nyberg proved three important correlation theorems and applied them to several cryptanalytic contexts. We continue the work of Nyberg in a more theoretical direction. We consider a general functional form and obtain its Walsh transform. Two of Nyberg's correlation theorems are seen to be special cases of our general functional form. S-box lookup, addition modulo 2/sup 2k/, and X-OR are three frequently occurring operations in the design of symmetric ciphers. We consider two methods of combining these operations and in each apply our main result to obtain the Walsh transform.

We study the class of masking-based domain extenders for universal one-way hash functions (UOWHFs). Our first contribution is to show that any correct masking-based domain extender for UOWHF which invokes the compression UOWHF s times must use at least lceillog2srceil masks. As a consequence, we obtain the key expansion optimality of several known algorithms among the class of all masking-based domain extending algorithms. Our second contribution is to present a new parallel domain extender for UOWHF. The new algorithm achieves asymptotically optimal speedup over the sequential algorithm and the key expansion is almost everywhere optimal, i.e., it is optimal for almost all possible number of invocations of the compression UOWHF

We consider the problem of constructing perfect nonlinear multiple-output Boolean functions satisfying higher order strict avalanche criteria (SAC). Our first construction is an infinite family of 2-output perfect nonlinear functions satisfying higher order SAC. This construction is achieved using the theory of bilinear forms and symplectic matrices. Next we build on a known connection between 1-factorization of a complete graph and SAC to construct more examples of 2- and 3-output perfect nonlinear functions. In certain cases, the constructed S-boxes have optimal tradeoff between the following parameters: numbers of input and output variables, nonlinearity, and order of SAC. In case the number of input variables is odd, we modify the construction for perfect nonlinear S-boxes to obtain a construction for maximally nonlinear S-boxes satisfying higher order SAC. Our constructions present the first examples of perfect nonlinear and maximally nonlinear multiple-output S-boxes satisfying higher order SAC. Finally, we present a simple method for improving the degree of the constructed functions with a small tradeoff in nonlinearity and the SAC property. This yields functions which have possible applications in the design of block ciphers.

In this correspondence, we use affine functions on a small number of variables to construct resilient functions on a large number of variables. We show that by properly combining these functions it is possible to achieve high nonlinearity and high algebraic degree. An important contribution of the correspondence is to show that for each order of resiliency m, it is possible to find infinitely many odd and even positive integers n, such that it is possible to construct (maximum degree) n-variable, m-resilient functions having nonlinearity strictly greater than 2/sup n-1/-2/sup /spl lfloor/n/2/spl rfloor//. We also present construction of some important functions on a small number of variables.

We present low cost hardware architecture for implementing state-of-the-art theoretical constructions of secure Boolean functions suitable for stream ciphers. Using a pipelined architecture, we show that it is possible to implement systems which use Boolean functions of a relatively large number of variables. Our architecture is reconfigurable and provide a universal circuit for a certain class of secure Boolean functions.

Three basic properties of Boolean functions to be useful for cryptographic purposes are balancedness, high algebraic degree, and high nonlinearity. In addition, strict avalanche criteria and propagation characteristics are required for design of S-boxes. We introduce methods to modify the Patterson-Wiedemann (19983, 1990) and bent functions to achieve the above cryptographic properties. In the process, we are able to answer some open questions about Boolean functions.

In this correspondence, we establish that for odd n, the maximum nonlinearity achievable by an n-variable symmetric Boolean function is 2/sup n-1/-2/sup (n-1)///sup 2/ and characterize the set of functions which achieve this value of nonlinearity. In particular, we show that for each odd n/spl ges/3, there are exactly four possible symmetric Boolean functions achieving the nonlinearity 2/sup n-1/-2/sup (n-1)/2/.