## CryptoDB

### Palash Sarkar

#### Publications

Year
Venue
Title
2020
JOFC
This work considers the problem of fast and secure scalar multiplication using curves of genus one defined over a field of prime order. Previous work by Gaudry and Lubicz (Finite Fields Appl 15(2):246–260, 2009 ) had suggested the use of the associated Kummer line to speed up scalar multiplication. In the present work, we explore this idea in detail. The first task is to obtain an elliptic curve in Legendre form which satisfies necessary security conditions such that the associated Kummer line has small parameters and a base point with small coordinates. It turns out that the ladder step on the Kummer line supports parallelism and can be implemented very efficiently in constant time using the single-instruction multiple-data (SIMD) operations available in modern processors. For the 128-bit security level, this work presents three Kummer lines denoted as $K_1:=\mathsf{KL2519(81,20)}$ K 1 : = KL 2519 ( 81 , 20 ) , $K_2:=\mathsf{KL25519(82,77)}$ K 2 : = KL 25519 ( 82 , 77 ) and $K_3:=\mathsf{KL2663(260,139)}$ K 3 : = KL 2663 ( 260 , 139 ) over the three primes $2^{251}-9$ 2 251 - 9 , $2^{255}-19$ 2 255 - 19 and $2^{266}-3$ 2 266 - 3 , respectively. Implementations of scalar multiplications for all three Kummer lines using Intel intrinsics have been done, and the code is publicly available. Timing results on the Skylake and the Haswell processors of Intel indicate that both fixed base and variable base scalar multiplications for $K_1$ K 1 and $K_2$ K 2 are faster than those achieved by Sandy2x , which is a highly optimised SIMD implementation in assembly of the well-known Curve25519 . On Skylake, both fixed base and variable base scalar multiplications for $K_3$ K 3 are faster than Sandy2x , whereas on Haswell, fixed base scalar multiplication for $K_3$ K 3 is faster than Sandy2x while variable base scalar multiplication for both $K_3$ K 3 and Sandy2x takes roughly the same time. In practical terms, the particular Kummer lines that are introduced in this work are serious candidates for deployment and standardisation. We further illustrate the usefulness of the proposed Kummer lines by instantiating the quotient Digital Signature Algorithm on all the three Kummer lines.
2017
ASIACRYPT
2017
TOSC
Universal hash functions based on univariate polynomials are well known, e.g. Poly1305 and GHASH. Using Horner’s rule to evaluate such hash functionsrequire l − 1 field multiplications for hashing a message consisting of l blocks where each block is one field element. A faster method is based on the class of Bernstein-Rabin-Winograd (BRW) polynomials which require ⌊l/2⌋ multiplications and ⌊lgl⌋ squarings for l≥3 blocks. Though this is significantly smaller than Horner’s rule based hashing, implementation of BRW polynomials for variable length messages present significant difficulties. In this work, we propose a two-level hash function where BRW polynomial based hashing is done at the lower level and Horner’s rule based hashing is done at the higher level. The BRW polynomial based hashing is applied to a fixed number of blocks and hence the difficulties in handling variable length messages is avoided. Even though the hash function has two levels, we show that it is sufficient to use a single field element as the hash key. The basic idea is instantiated to propose two new hash functions, one which hashes a single binary string and the other can hash a vector of binary strings. We describe two actual implementations, one over F2128 and the other over F2256 both using the pclmulqdq instruction available in modern Intel processors. On both the Haswell and Skylake processors, the implementation over F2128 is faster than both an implementation of GHASH by Gueron; and a highly optimised implementation, also by Gueron, of another polynomial based hash function called POLYVAL. We further show that the Fast Fourier Transform based field multiplication over F2256 proposed by Bernstein and Chou can be used to evaluate the new hash function at a cost of about at most 46 bit operations per bit of digest, but, unlike the Bernstein-Chou analysis, there is no hidden cost of generating the hash key. More generally, the new idea of building a two-level hash function having a single field element as the hash key can be applied to other finite fields to build new hash functions.
2016
EUROCRYPT
2016
ASIACRYPT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2014
EPRINT
2014
EPRINT
2014
EPRINT
2014
EPRINT
2012
PKC
2009
EPRINT
Let $X^{(1)},X^{(2)},\ldots,X^{(n)}$ be independent and uniformly distributed over the non-negative integers $\{0,1,\ldots,2^i-1\}$; $S^{(n)}=X^{(1)}+X^{(2)}+\cdots+X^{(n)}$ and $L^{(n)}=X^{(1)}\oplus X^{(2)}\oplus \cdots\oplus X^{(n)}$. Denote the $i$-th bits of $S^{(n)}$ and $L^{(n)}$ by $S^{(n)}_i$ and $L^{(n)}_i$ respectively. We show that as $i\rightarrow \infty$, $\pr[S^{(n)}_i=L^{(n)}_i]\rightarrow \gamma^{(n)}= \frac{1}{2}+\frac{2^{n+1}(2^{n+1}-1)}{2(n+1)}\times\frac{b_{n+1}}{n!}$, where $b_n$ is the $n$-th Bernoulli number. As a consequence, $\gamma^{(2r)}=1/2$ for every $r$; and we show that $\gamma^{(2r+1)}\rightarrow 1/2$ as $r\rightarrow \infty$. For small values of $r$, $\gamma^{(2r+1)}$ is significantly different from $1/2$; for example $\gamma^{(3)}=1/3$ and $\gamma^{(5)}=17/30$. The behaviour of $\gamma^{(n)}$ for even and odd values of $n$ was earlier shown by Staffelbach and Meier without actually obtaining the formula mentioned above. For every fixed $n\geq 2$, we give a simple method for computing $\pr[S^{(n)}_i=L^{(n)}_i]$ for each $i\geq 0$. The expression involving Bernoulli numbers is arrived at via the Eulerian number triangle which in turn arises in relation to the stationary distribution of a Markov chain formed by the carry values.
2009
EPRINT
Consider the following universal hashing set-up. Let $\rF$ be a finite field and suppose any message consists of at most $2^{30}$ elements of $\rF$. Suppose further that a collision bound of $2^{-128}$ is desired. This can be achieved using usual polynomial hashing with $|\rF|\approx 2^{160}$ and having a digest of $160$ bits and a key of length also $160$ bits; hashing an $n$-bit message requires approximately $n/160$ multiplications over $\rF$. We describe a new hashing method which can achieve the same collision bound of $2^{-128}$ for messages of at most $L$ elements by working over a field $\rF$ of size $\approx 2^{136}$. Hashing an $n$-bit message requires approximately $n/136$ multiplications over $\rF$. Supposing similar efficiency in implementation of field arithmetic in both cases, the ratio of the two processing times is $160/136\times[M_{136}]/[M_{160}]$, where $M_a$ is the time for one multiplication in a field of size $\approx 2^a$. Since $M_a$ is quadratic in $a$, the new algorithm is expected to be faster than usual polynomial hashing. Further, the size of the digest also reduces to $136$ bits. The trade-off is that the key size increases to $5\times 136=680$ bits compared to the key size of $160$ bits for usual polynomial hashing. The method mentioned above is a special case of a general method of combining independent universal hash functions at multiple levels to obtain a new universal hash function. Other consequences of the new algorithm are worked out including how it can be instantiated by a class of polynomials introduced by Bernstein.
2009
EPRINT
We consider the construction and analysis of pseudorandom functions (PRF) for message authentication. Earlier work due to Bernstein and Vaudenay show how to reduce the analysis of PRFs to some probability calculations. We revisit this result and use it to prove some general results on constructions which use a PRF with small'' domain to build a PRF with large'' domain. These results are then used to analyse several existing and new constructions. Important among them is a simplified proof of a bound on the PRF-property of the cipher block chaining (CBC) mode of operation of a block cipher for message authentication code (MAC). Several existing variants of CBC-MAC are analysed using our framework and new schemes are described. One of the new schemes improve upon the NIST standard CMAC scheme by reducing the number of block cipher invocations by one for messages which are longer than $n$ bits. Next, we consider parallelizable constructions. An improved version of the well known PMAC scheme is described; the improvement consists of removing the requirement of a discrete log computation in the design stage of PMAC. An earlier parallel construction called the protected counter sum (PCS) had been proposed by Bernstein. PCS uses a keyed compressing function rather than a block cipher. We describe a variant of PMAC which works with keyed compressing function and compared to PCS requires lesser number of invocations. All our constructions are in the stateless setting, i.e., a setting where the sender and the receiver do not share any state (apart from the common secret key). One of the aspects of our work is the simple and direct approach to the analysis of PRFs. In particular, we avoid the extensive and heavy machinery of game-playing technique which is used in most papers on this topic.
2008
EPRINT
In this work we revisit the known algorithms for searching for low weight codewords in linear binary codes. We propose some improvements on them and also propose a new efficient heuristic.
2008
EPRINT
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) 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 counter mode and the output feedback (OFB) 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.
2008
EPRINT
The SHA-256 hash function has started getting attention recently by the cryptanalysis community due to the various weaknesses found in its predecessors such as MD4, MD5, SHA-0 and SHA-1. We make two contributions in this work. First we describe message modification techniques and use them to obtain an algorithm to generate message pairs which collide for the actual SHA-256 reduced to 18 steps. Our second contribution is to present differential paths for 19, 20, 21, 22 and 23 steps of SHA-256. We construct parity check equations in a novel way to find these characteristics. Further, the 19-step differential path presented here is constructed by using only 15 local collisions, as against the previously known 19-step near collision differential path which consists of interleaving of 23 local collisions. Our 19-step differential path can also be seen as a single local collision at the message word level. We use a linearized local collision in this work. These results do not cause any threat to the security of the SHA-256 hash function.
2008
EPRINT
Most of the attacks against (reduced) SHA-2 family in literature have used local collisions which are valid for linearized version of SHA-2 hash functions. Recently, at FSE '08, an attack against reduced round SHA-256 was presented by Nikoli\'{c} and Biryukov which used a local collision which is valid for the actual SHA-256 function. It is a 9-step local collision which starts by introducing a modular difference of 1 in the two messages. It succeeds with probability roughly 1/3. We build on the work of Nikoli\'{c} and Biryukov and provide a generalized nonlinear local collision which accepts an arbitrary initial message difference. This local collision succeeds with probability 1. Using this local collision we present attacks against 18-step SHA-256 and 18-step SHA-512 with arbitrary initial difference. Both of these attacks succeed with probability 1. We then present special cases of our local collision and show two different differential paths for attacking 20-step SHA-256 and 20-step SHA-512. One of these paths is the same as presented by Nikoli\'{c} and Biryukov while the other one is a new differential path. Messages following both these differential paths can be found with probability 1. This improves on the previous result where the success probability of 20-step attack was 1/3. Finally, we present two differential paths for 21-step collisions for SHA-256 and SHA-512, one of which is a new path. The success probability of these paths for SHA-256 is roughly $2^{-15}$ and $2^{-17}$ which improves on the 21-step attack having probability $2^{-19}$ reported earlier. We show examples of message pairs following all the presented differential paths for up to 21-step collisions in SHA-256. We also show first real examples of colliding message pairs for up to 20-step reduced SHA-512.
2008
EPRINT
A new multi-linear universal hash family is described. Messages are sequences over a finite field $\rF_q$ while keys are sequences over an extension field $\rF_{q^n}$. A linear map $\psi$ from $\rF_{q^n}$ to itself is used to compute the output digest. Of special interest is the case $q=2$. For this case, we show that there is an efficient way to implement $\psi$ using a tower field representation of $\rF_{q^n}$. Such a $\psi$ corresponds to a word oriented LFSR. We describe a method of combining the new universal hash function and a stream cipher with IV to obtain a MAC algorithm. Further, we extend the basic universal hash function to an invertible blockwise universal hash function. Following the Naor-Reingold approach, this is used to construct a tweakable enciphering scheme which uses a single layer of encryption and no finite field multiplications. From an efficiency viewpoint, the focus of all our constructions is small hardware and other resource constrained applications. For such platforms, our constructions compare favourably to previous work.
2008
EPRINT
In this work, we present two attacks against 22-step SHA-512. Our first attack succeeds with probability about $2^{-8}$ whereas the second attack is deterministic. To construct the attack, we use a single local collision and handle conditions on the colliding pair of messages. All but one condition can be satisfied deterministically in our first attack while in the second attack all conditions can be satisfied deterministically. There are four free words in our second attack and hence we get exactly $2^{256}$ collisions for 22-step SHA-512. Recently, attacks against up to 24-step SHA-256 have been reported in the literature which use a local collision given earlier by Nikoli\'{c} and Biryukov at FSE'08. We provide evidence which shows that using this local collision is unlikely to produce collisions for step reduced SHA-512. Consequently, our attacks are currently the best against reduced round SHA-512. The same attacks also work against SHA-256. Since our second attack is a deterministic construction, it is also the best attack against 22-step SHA-256.
2008
EPRINT
In this work, we make a detailed analysis of local collisions and their applicability to obtain collisions for step reduced SHA-2 hash family. Our analysis explains previously reported collisions for up to 22-step SHA-2 hash functions with probability one. We provide new and improved attacks against 23 and 24-step SHA-256 using a local collision given by Sanadhya and Sarkar (SS) at ACISP '08. The computational efforts for the 23-step and 24-step attacks are respectively $2^{12.5}$ and $2^{28.5}$ calls to the corresponding step reduced SHA-256. Using a look-up table having $2^{32}$ entries the computational effort for finding 24-step collisions can be reduced to $2^{14.5}$ calls. We exhibit colliding message pairs for both the 23 and 24-step attacks. The previous work on 23 and 24-step SHA-256 attacks is due to Indesteege et al. and utilizes the local collision presented by Nikoli\'{c} and Biryukov (NB) at FSE '08. The reported computational efforts are $2^{18}$ and $2^{28.5}$ respectively. The previous 23 and 24-step attacks first constructed a pseudo-collision and later converted it into a collision for the reduced round SHA-256. We show that this two step procedure is unnecessary. Although these attacks improve upon the existing reduced round SHA-256 attacks, they do not threaten the security of the full SHA-2 family.
2008
EPRINT
In this work, we study several properties of the SHA-2 design which have been utilized in recent collision attacks against reduced SHA-2. We suggest small modifications to the SHA-2 design to thwart these attacks. The cost of SHA-2 evaluations does not change significantly due to our modifications but the new design provides resistance to the recent collision attacks. Further, we describe an easy method of exhibiting non-randomness of the compression functions of the entire SHA family, that is SHA-0, SHA-1 and all the hash functions in SHA-2. Specifically, we show that given any $\IV_1$ and any pair of messages $M_1$ and $M_2$, an $\IV_2$ can be easily and deterministically constructed such that the relation $H(\IV_1,M_1)-\IV_1 = H(\IV_2,M_2)-\IV_2$ holds. For a truly random hash function $H$ outputting a $k$-bit digest, such a relation should hold with probability $2^{-k}$. We introduce the general idea of multiple feed-forward" in the context of construction of cryptographic hash functions. When used in SHA designs, this technique removes the non-randomness mentioned earlier. Perhaps more importantly, it provides 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. This provides quantifiably better resistance to Joux type generic multi-collision attacks. For example, with our modification of SHA-256, finding $2^r$ messages which map to the same value will require $r\times 2^{384}$ invocations of the compression function.
2008
EPRINT
We perform a combinatorial analysis of SHA-2 compression function. This analysis explains in a unified way the recent attacks against reduced round SHA-2. We start with a general class of local collisions and show that the previously used local collision by Nikoli\'{c} and Biryukov (NB) and Sanadhya and Sarkar (SS) are special cases. The study also clarifies several advantages of the SS local collision over the NB local collision. Deterministic constructions of up to 22-round SHA-2 collisions are described using the SS local collision and up to 21-round SHA-2 collisions are described using the NB local collision. For 23 and 24-round SHA-2, we describe a general strategy and then apply the SS local collision to this strategy. The resulting attacks are faster than those proposed by Indesteege et al using the NB local collision. We provide colliding message pairs for 22, 23 and 24-round SHA-2. Although these attacks improve upon the existing reduced round SHA-256 attacks, they do not threaten the security of the full SHA-2 family. \footnote{This work builds upon and subsumes previous work done by us. Whereas the previous works focused on obtaining collisions for fixed number of rounds, the current work provides the combinatorial framework for understanding how such collisions arise.}
2008
EPRINT
In this work, we provide new and improved attacks against 22, 23 and 24-step SHA-2 family using a local collision given by Sanadhya and Sarkar (SS) at ACISP '08. The success probability of our 22-step attack is 1 for both SHA-256 and SHA-512. The computational efforts for the 23-step and 24-step SHA-256 attacks are respectively $2^{11.5}$ and $2^{28.5}$ calls to the corresponding step reduced SHA-256. The corresponding values for the 23 and 24-step SHA-512 attack are respectively $2^{16.5}$ and $2^{32.5}$ calls. Using a look-up table having $2^{32}$ (resp. $2^{64}$) entries the computational effort for finding 24-step SHA-256 (resp. SHA-512) collisions can be reduced to $2^{15.5}$ (resp. $2^{22.5}$) calls. We exhibit colliding message pairs for 22, 23 and 24-step SHA-256 and SHA-512. This is the \emph{first} time that a colliding message pair for 24-step SHA-512 is provided. The previous work on 23 and 24-step SHA-2 attacks is due to Indesteege et al. and utilizes the local collision presented by Nikoli\'{c} and Biryukov NB) at FSE '08. The reported computational efforts are $2^{18}$ and $2^{28.5}$ for 23 and 24-step SHA-256 respectively and $2^{43.9}$ and $2^{53}$ for 23 and 24-step SHA-512. The previous 23 and 24-step attacks first constructed a pseudo-collision and later converted it into a collision for the reduced round SHA-2 family. We show that this two step procedure is unnecessary. Although these attacks improve upon the existing reduced round SHA-2 attacks, they do not threaten the security of the full SHA-2 family.
2007
EPRINT
The notion of tweakable block ciphers was formally introduced by Liskov-Rivest-Wagner at Crypto 2002. 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. Among the hash-Ctr-hash type constructions, an important advantage of {\hch} compared to the others is that {\hch} has a quadratic security bound; XCB does not provide any security bound while HCTR has a cubic security bound. 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 pre-computation and makes one less block cipher call. This compares favourably to other hash-encrypt-hash type constructions; supports better key agility and requires less key material.
2007
EPRINT
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 {\ring} and by the use of a masking sequence of functions. The ring {\ring} can be instantiated as either $GF(2^n)$ or as $\bbbz_{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 mode 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 OCB.
2007
EPRINT
At Eurocrypt 2005, Boneh, Boyen and Goh presented a constant size ciphertext hierarchical identity based encryption (HIBE) protocol. Our main contribution is to present a variant of the BBG-HIBE. The new HIBE is proved to be secure (without any degradation) in an extension of the sID model (denoted the s$^+$-ID model) and the components of the identities are from $\bbbz_p$, where $p$ is a suitable large prime. The BBG-HIBE is proved to be secure in the selective-ID (sID) security model and the components of the identities are from $\bbbz_p^*$. In the s$^+$-ID model the adversary is allowed to vary the length of the challenge identity whereas this is not allowed in the sID model. The new HIBE shares all the good features of the BBG-HIBE. The drawback is that the public parameters and the private key are longer than that of the BBG-HIBE. We also provide two more extensions of the basic constant size ciphertext HIBE. The first is a constant size ciphertext HIBE secure in the generalised selective-ID model $\clsM_2$. The second one is a product construction composed of two HIBEs and a trade-off is possible between the private key size and the ciphertext size.
2007
EPRINT
Naor and Reingold had proposed the construction of a strong pseudo-random permutation (SPRP) by using a layer of ECB encryption between two layers of invertible block-wise universal hash functions. At Crypto 2007, Halevi presented constructions of invertible block-wise universal hash functions and a new mode of operation (called TET) based on them. In this paper, we present a new mode of operation called {\heh} using the Naor-Reingold approach. This is built using a new construction of invertible block-wise universal hash function. The new construction improves over Halevi's construction by removing restrictions on the hashing key. This in turn, leads to {\heh} improving over TET by allowing more efficient encryption and decryption of variable length messages as well as supporting better key agility. For the important application of disk encryption, we present a variant called {\hehfp} which has better key agility than TET.
2007
EPRINT
The starting point for collision attacks on practical hash functions is a local collision. In this paper, we make a systematic study of local collisions for the SHA-2 family. The possible linear approximations of the constituent Boolean functions are considered and certain impossible conditions for such approximations are identified. Based on appropriate approximations, we describe a general method for finding local collisions. Applying this method, we obtain several local collisions and compute the probabilities of the various differential paths. Previously, only one local collision due to Gilbert-Handschuh was known. We point out two impossible conditions in the GH local collision and provide an example of an impossible differential path for linearized SHA-2 using this local collision. Sixteen new local collisions are obtained none of which have any impossible conditions. The probabilities of these local collisions are a little less than the GH local collision. On the other hand, the absence of impossible conditions may make them more suitable for (reduced round) collision search attacks on the SHA-2 family.
2006
ASIACRYPT
2006
FSE
2006
PKC
2006
EPRINT
We generalize the selective-ID security model for HIBE by introducing two new security models. Broadly speaking, both these models allow the adversary to commit to a set of identities and in the challenge phase choose any one of the previously committed identities. Two constructions of HIBE are presented which are secure in the two models. Further, we show that the HIBEs can be modified to obtain a multiple receiver IBE which is secure in the selective-ID model without the random oracle assumption.
2006
EPRINT
We consider the problem of efficiently generating sequences in hardware for use in certain cryptographic algorithms. The conventional method of doing this is to use a counter. We show that sequences generated by linear feedback shift registers (LFSRs) can be tailored to suit the appropriate algorithms. For hardware implementation, this reduces both time and chip area. As a result, we are able to suggest improvements to the design of DES Cracker built by the Electronic Frontier Foundation in 1998; provide an efficient strategy for generating start points in time-memory trade/off attacks; and present an improved parallel hardware implementation of a variant of the counter mode of operation of a block cipher.
2006
EPRINT
We present MEM, which is a new mode of encryption using a block cipher. MEM is proved to be a strong pseudo-random permutation (SPRP) against {\em symmetric} nonce respecting adversaries, where a symmetric nonce respecting adversary is one which does not repeat nonces to either the encryption or the decryption oracle. Against such adversaries, MEM provides a secure, length preserving, tagless mode of encryption. In our construction, the number of block cipher calls is approximately half that of the earlier known more general constructions CMC, EME and EME$^*$ of tweakable SPRPs. In situations where the appropriate adversary can be assumed, and where a tagless mode of encryption is required, our construction is the most efficient solution till date.
2006
EPRINT
In 1980, Hellman introduced a time/memory trade-off (TMTO) algorithm satisfying the TMTO curve $TM^2=N^2$, where $T$ is the online time, $M$ is the memory and $N$ is the size of the search space. Later work by Biryukov-Shamir incorporated multiple data to obtain the curve $TM^2D^2=N^2$, where $D$ is the number of data points. In this paper, we describe a new table structure obtained by combining Hellman's structure with a structure proposed by Oechslin. Using the new table structure, we design a new multiple data TMTO algorithm both with and without the DP method. The TMTO curve for the new algorithm is obtained to be $T^3M^7D^8=N^7$. This curve is based on a conjecture on the number of distinct points covered by the new table. Support for the conjecture has been obtained through some emperical observations. For $D>N^{1/4}$, we show that the trade-offs obtained by our method are better than the trade-offs obtained by the BS method.
2006
EPRINT
Elliptic (ECC) and hyperelliptic curve cryptosystems (HECC) have emerged as cryptosystems of choice for small handheld and mobile devices. A lot of research has been devoted to the secure and efficient implementation on these devices. As such devices come with very low amount of resources, efficient memory management is an important issue in all such implementations. HECC arithmetic is now generally performed using so called explicit formulae. In literature, there is no result which focuses on the exact memory requirement for implementation these formulae. This is the first work to report such minimal memory requirement. Also, in the work we have provided a general methodology for realization of explicit formulae with minimal number of registers. Applying such methodology this work settles the issue for some important explicit formula available in the literature. This is an attempt to experimentally solve a particular instance based on HECC explicit formulae of the so called Register Sufficiency Problem", which is an NP-complete problem.
2006
EPRINT
We present PEP, which is a new construction of a tweakable strong pseudo-random permutation. PEP uses a hash-encrypt-hash approach which has recently been used in the construction of HCTR. This approach is different from the encrypt-mask-encrypt approach of constructions such as CMC, EME and EME$^*$. The general hash-encrypt-hash approach was earlier used by Naor-Reingold to provide a generic construction technique for an SPRP (but not a tweakable SPRP). PEP can be seen as the development of the Naor-Reingold approach into a fully specified mode of operation with a concrete security reduction for a tweakable strong pseudo-random permutation. The security bound of HCTR which is also based on the Naor-Reingold approach is weaker than that of PEP. Compared to previous known constructions, PEP is the only construction of tweakable SPRP which uses a single key, is efficiently parallelizable and can handle an arbitrary number of blocks.
2006
EPRINT
At Eurocrypt 2005, Waters proposed an efficient identity based encryption (IBE) scheme. One drawback of this scheme is that the size of the public parameter is rather large. Our first contribution is a generalization of Waters scheme. In particular, we show that there is an interesting trade-off between the tightness of the security reduction and smallness of the public parameter size. For a given security level, this implies that if one reduces the public parameter size there is a corresponding increase in the computational cost. This introduces a flexibility in choosing the public parameter size without compromising in security. In concrete terms, to achieve $80$-bit security for 160-bit identities we show that compared to Waters protocol the public parameter size can be reduced by almost $90 \%$ while increasing the computation cost by $30\%$. Our second contribution is to extend the IBE protocol to a hierarchical IBE (HIBE) protocol which can be shown to be secure in the full model without the use of random oracle. A previous construction of a HIBE in the same setting is due to Waters. Our construction improves upon Waters' suggestion by significantly reducing the number of public parameters.
2006
EPRINT
The current work considers the problem of obtaining a hierarchical identity-based encryption (HIBE) protocol which is secure against adaptive key extraction and decryption queries. Such a protocol is obtained by modifying an earlier protocol by Chatterjee and Sarkar (which, in turn, is based on a protocol due to Waters) which is secure only against adaptive key extraction queries. The setting is quite general in the sense that random oracles are not used and security is based on the hardness of the decisional bilinear Diffie-Hellman (DBDH) problem. In this setting, the new construction provides the most efficient (H)IBE protocol known till date. The technique for answering decryption queries in the proof is based on earlier work by Boyen, Mei and Waters. Ciphertext validity testing is done indirectly through a symmetric authentication algorithm in a manner similar to the Kurosawa-Desmedt public key encryption protocol. Additionally, we perform symmetric encryption and authentication by a single authenticated encryption algorithm.
2005
ASIACRYPT
2005
EPRINT
Some of the existing time memory tradeoff attacks (TMTO) on specific systems can be reinterpreted as methods for inverting general oneway functions. We apply these methods back to specific systems in ways not considered before. This provides the following startling results. No streamcipher can provide security equal to its key length; some important blockcipher modes of operations are vulnerable to TMTO; and no hash function can provide preimage resistance equal to its digest length.
2005
EPRINT
Time/memory trade-off (TMTO) was introduced by Hellman and later studied by many other authors. The effect of multiple data in Hellman TMTO was studied by Biryukov and Shamir (BS). We continue the analysis of the general multiple data TMTO started in BS. The trade-offs of Babbage and Golic (BG) and Biryukov-Shamir are obtained as special cases. Further, the general analysis is carried out under different conditions including that of Hellman optimality (online time equal to memory). Our main contribution is to identify a new class of single table multiple data trade-offs which cannot be obtained either as BG or BS trade-off. In certain cases, these new trade-offs can provide more desirable parameters than the BG or the BS methods. We consider the analysis of the rainbow method of Oechslin and show that for multiple data, the TMTO curve of the rainbow method is inferior to the TMTO curve of the Hellman method. The costs of the rainbow method and the Hellman+DP method can be comparable if the size of the search space is small and the cost of one table look-up is relatively high.
2004
ASIACRYPT
2004
ASIACRYPT
2004
FSE
2004
PKC
2004
EPRINT
The bilinear pairing such as Weil pairing or Tate pairing on elliptic and hyperelliptic curves have recently been found applications in design of cryptographic protocols. In this survey, we have tried to cover different cryptographic protocols based on bilinear pairings which possess, to the best of our knowledge, proper security proofs in the existing security models.
2004
EPRINT
In~\cite{B02} it was proved that 20 out of 64 PGV-hash functions~\cite{P94} based on block cipher are collision resistant and one-way-secure in black-box model of the underlying block cipher. Here, we generalize the definition of PGV-hash function into a hash family and we will prove that besides the previous 20 hash functions we have 22 more collision resistant and one-way secure hash families. As all these 42 families are keyed hash family, these become target collision resistant also. All these 42 hash families have tight upper and lower bounds on (target) collision resistant and one-way-ness.
2004
EPRINT
We present a provably secure authenticated tree based key agreement protocol. The protocol is obtained by combining Boldyreva's multi-signature with an unauthenticated ternary tree based multi-party extension of Joux's key agreement protocol. The securiry is in the standard model as formalized by Bresson et al. The proof is based on the techniques used by Katz and Yung in proving the security of their key agreement protocol.
2003
ASIACRYPT
2003
FSE
2003
EPRINT
We obtain a {\em finite} binary tree algorithm to extend the domain of a UOWHF. The associated key length expansion is only a constant number of bits more than the minimum possible. Our finite binary tree algorithm is a practical parallel algorithm to securely extend the domain of a UOWHF. Also the speed-up obtained by our algorithm is approximately proportional to the number of processors.
2003
EPRINT
We present a secure unauthenticated as well as an authenticated multi party key agreement protocol. The unauthenticated version of our protocol uses ternary trees and is based on bilinear maps and Joux's three party protocol. The number of rounds, computation/communication complexity of our protocol compares favourably with previously known protocols. The authenticated version of our protocol also uses ternary trees and is based on public IDs and Key Generation Centres. The authenticated version of our protocol is more efficient than all previously known authenticated key agreement protocols.
2003
EPRINT
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 look-up, addition modulo $2^{2k}$ and X-OR are three frequently occuring 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.
2003
EPRINT
In this paper, we present a new stream cipher called Hiji-bij-bij (HBB). The basic design principle of HBB is to mix a linear and a nonlinear map. Our innovation is in the design of the linear and the nonlinear maps. The linear map is realised using two 256-bit maximal period 90/150 cellular automata. The nonlinear map is simple and consists of several alternating linear and nonlinear layers. We prove that the mixing achieved by the nonlinear map is complete and the maximum bias in any non-zero linear combination of the input and output bits of the nonlinear map is at most $2^{-13}$. We also identify a self-synchronizing mode ({\bf SS}) of operation for HBB. The performance of HBB is reasonably good in software and is expected to be very fast in hardware. To the best of our knowledge, a generic exhaustive search seems to be the only method of attacking the cipher.
2003
EPRINT
We study the problem of securely extending the domain of a collision resistant compression function. A new construction based on directed acyclic graphs is described. This generalizes the usual iterated hashing constructions. Our main contribution is to introduce a new technique for hashing arbitrary length strings. Combined with DAG based hashing, this technique gives a new hashing algorithm. The amount of padding and the number of invocations of the compression function required by the new algorithm is smaller than the general \MD algorithm. Lastly, we describe the design of a new parallel hash algorithm.
2003
EPRINT
One of the recent thrust areas in research on hyperelliptic curve cryptography has been to obtain explicit formulae for performing arithmetic in the Jacobian of such curves. We continue this line of research by obtaining parallel versions of such formulae. Our first contribution is to develop a general methodology for obtaining parallel algorithm of any explicit formula. Any parallel algorithm obtained using our methodology is provably optimal in the number of multiplication rounds. We next apply this methodology to Lange's explicit formula for arithmetic in genus 2 hyperelliptic curve -- both for the affine coordinate and inversion free arithmetic versions. Since encapsulated add-and-double algorithm is an important countermeasure against side channel attacks, we develop parallel algorithms for encapsulated add-and-double for both of Lange's versions of explicit formula. For the case of inversion free arithmetic, we present parallel algorithms using 4, 8 and 12 multipliers. All parallel algorithms described in this paper are optimal in the number of parallel rounds. One of the conclusions from our work is the fact that the parallel version of inversion free arithmetic is more efficient than the parallel version of arithmetic using affine coordinates.
2003
EPRINT
We consider the problem of constructing perfect nonlinear multi-output Boolean functions satisfying higher order strict avalanche criteria (SAC). Our first construction is an infinite family of 2-ouput 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 trade-off 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 multioutput S-boxes satisfying higher order SAC. Lastly, we present a simple method for improving the degree of the constructed functions with a small trade-off in nonlinearity and the SAC property. This yields functions which have possible applications in the design of block ciphers.
2003
EPRINT
We study the class of masking based domain extenders for 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 $\lceil\log s\rceil$ masks. As a consequence we obtain the optimality of Shoup's algorithm among the class of masking based domain extenders. Our second contribution is to present a new parallel domain extender for UOWHF. The new algorithm obtains an asymptotically optimal speed-up 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.
2003
EPRINT
In many crypographic hardware or software packages, a considerable part is devoted to finite field arithmetic. The finite field arithmetic is a very costly operation in comparison to other finite field operations. Taming the complexity of this operation has been a major challenge for researchers and implementers. One approach for the purpose is accumulate all the elements to be inverted and to compute several inversions simultaneously at the cost of one inversion and some multiplictions. One such algorithm is known as Montgomery's trick. However Montgomery's trick does not allow much parallelism. In~\cite{SMB03} an algorithm for computation of inverses of several field elements simultaneously in parallel has been proposed. The algorithm allows ample scope for parallelism and performes well if there is no restriction on the number of processors used. In the current work, we present an algorithm, which is same in complexity as Montgomery's trick but suitable for a parallel implementation. In parallel implementation, it computes inverse of $n$ elements in $2\log n$ parallel rounds. It performs better than both the previous algorithms under the circumstances where the restricted number of multipliers is used.
2002
ASIACRYPT
2002
CRYPTO
2002
EPRINT
We describe a parallel design principle for hash functions. Given a secure hash function $h:\{0,1\}^n\rightarrow \{0,1\}^m$ with $n\geq 2m$, and a binary tree of $2^t$ processors we show how to construct a secure hash function $h^{*}$ which can hash messages of lengths less than $2^{n-m}$ and a secure hash function $h^{\infty}$ which can hash messages of arbitrary length. The number of parallel rounds required to hash a message of length $L$ is $\lfloor\frac{L}{2^t}\rfloor+t+2$. Further, our algorithm is incrementally parallelizable in the following sense : given a digest produced using a binary tree of $2^t$ processors, we show that the same digest can also be produced using a binary tree of $2^{t^{\prime}}$ $(0\leq t^{\prime}\leq t)$ processors.
2002
EPRINT
We present a binary tree based parallel algorithm for extending the domain of a UOWHF. The key length expansion is $2m$ bits for $t=2$; $m(t+1)$ bits for $3\leq t\leq 6$ and $m\times(t+\lfloor\log_2 (t-1)\rfloor)$ bits for $t\geq 7$, where $m$ is the length of the message digest and $t\geq 2$ is the height of the binary tree.
2001
CHES
2000
CRYPTO
2000
EUROCRYPT
2000
EPRINT
There has been a recent upsurge of research in the design of resilient Boolean functions for use in stream cipher systems. The existing research concentrates on maximum degree resilient functions and tries to obtain as high nonlinearity as possible. In sharp contrast to this approach we identify the class of functions with {\em provably best} possible trade-off among the parameters: number of variables, resiliency, nonlinearity and algebraic degree. We first prove a sharper version of McEliece theorem for Reed-Muller codes as applied to resilient functions, which also generalizes the well known Xiao-Massey characterization. As a consequence a nontrivial upper bound on the nonlinearity of resilient functions is obtained. This result coupled with Siegenthaler's inequality naturally leads to the notion of provably best resilient functions. We further show that such best functions can be constructed by the Maiorana-McFarland like technique. In cases where this method fails, we provide new ideas to construct best functions. We also briefly discuss efficient implementation of these functions in hardware.
2000
EPRINT
Recently weight divisibility results on resilient and correlation immune Boolean functions have received a lot of attention. These results have direct consequences towards the upper bound on nonlinearity of resilient and correlation immune Boolean functions of certain order. Now the clear benchmark in the design of resilient Boolean functions (which optimizes Sigenthaler's inequality) is to provide results which attain the upper bound on nonlinearity. Here we construct a 7-variable, 2-resilient Boolean function with nonlinearity 56. This solves the maximum nonlinearity issue for 7-variable functions with any order of resiliency. Using this 7-variable function, we also construct a 10-variable, 4-resilient Boolean function with nonlinearity 480. Construction of these two functions were justified as important open questions in Crypto 2000. Also we provide methods to generate an infinite sequence of Boolean functions on $n = 7 + 3i$ variables $(i \geq 0)$ with order of resiliency $m = 2 + 2i$, algebraic degree $4 + i$ and nonlinearity $2^{n-1} - 2^{m+1}$, which were not known earlier. We conclude with a few interesting construction results on unbalanced correlation immune functions of 5 and 6 variables.
2000
EPRINT
In this paper we prove a general result on the Walsh Transform of an arbitrary Boolean function. As a consequence, we obtain several divisibility results on the Walsh Transform of correlation immune and resilient Boolean functions. This allows us to improve upper bounds on the nonlinearity of correlation immune and resilient Boolean functions. Also we provide new necessary conditions on the algebraic normal form of correlation immune/resilient functions attaining the maximum possible nonlinearity.
1999
CRYPTO

Asiacrypt 2015
Crypto 2015
Asiacrypt 2014
Asiacrypt 2013
Eurocrypt 2012
Crypto 2012
Asiacrypt 2011
Crypto 2010
FSE 2010
Asiacrypt 2008
Asiacrypt 2007
FSE 2007
Crypto 2007
FSE 2005
Eurocrypt 2005