## CryptoDB

### Palash Sarkar

#### Affiliation: Indian Statistical Institute

#### Publications

**Year**

**Venue**

**Title**

2017

TOSC

A Fast Single-Key Two-Level Universal Hash Function
Abstract

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

2009

EPRINT

On Approximating Addition by Exclusive OR
Abstract

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

Trade-Off Between Key Size and Efficiency in Universal Hashing Using Polynomials
Abstract

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

On Stateless Schemes for Message Authentication Using Pseudorandom Functions
Abstract

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

Searching for Low Weight Codewords in Linear Binary Codes
Abstract

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

Efficient Tweakable Enciphering Schemes from (Block-Wise) Universal Hash Functions
Abstract

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

Attacking Reduced Round SHA-256
Abstract

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

Non-Linear Reduced Round Attacks Against SHA-2 Hash family
Abstract

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 Universal Hash Function and Other Cryptographic Algorithms Suitable for Resource Constrained Devices
Abstract

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

Collision attacks against 22-step SHA-512
Abstract

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

Attacking Step Reduced SHA-2 Family in a Unified Framework
Abstract

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

Some Observations on Strengthening the SHA-2 Family
Abstract

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

A Combinatorial Analysis of Recent Attacks on Step Reduced SHA-2 Family
Abstract

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

New Collision attacks Against Up To 24-step SHA-2
Abstract

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

HCH: A New Tweakable Enciphering Scheme Using the Hash-Counter-Hash Approach
Abstract

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

A General Construction of Tweakable Block Ciphers and Different Modes of Operations
Abstract

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

Constant Size Ciphertext HIBE in the Augmented Selective-ID Model and its Extensions
Abstract

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

Improving Upon the TET Mode of Operation
Abstract

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

New Local Collisions for the SHA-2 Hash Family
Abstract

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

EPRINT

Generalization of the Selective-ID Security Model for HIBE Protocols
Abstract

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

Application of LFSRs for Parallel Sequence Generation in Cryptologic Algorithms
Abstract

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

A New Mode of Encryption Secure Against Symmetric Nonce Respecting Adversaries
Abstract

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

A New Cryptanalytic Time/Memory/Data Trade-off Algorithm
Abstract

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

Towards Minimizing Memory Requirement for Implementation of Hyperelliptic Curve Crytosystems
Abstract

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

A New Mode of Encryption Providing A Tweakable Strong Pseudo-Random
Abstract

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

On (Hierarchical) Identity Based Encryption Protocols with Short Public Parameters \\ (With an Exposition of Waters' Artificial Abort Technique)
Abstract

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

Construction of a Hybrid (Hierarchical) Identity-Based Encryption Protocol Secure Against Adaptive Attacks
Abstract

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

EPRINT

Rediscovery of Time Memory Tradeoffs
Abstract

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

TMTO With Multiple Data: Analysis and New Single Table Trade-offs
Abstract

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

EPRINT

Pairing-Based Cryptographic Protocols : A Survey
Abstract

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

A Generalization of PGV-Hash Functions and Security Analysis in Black-Box Model
Abstract

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

Provably Secure Authenticated Tree Based Group Key Agreement Protocol
Abstract

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

EPRINT

Domain Extenders for UOWHF: A Finite Binary Tree Algorithm
Abstract

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

Extending Joux's Protocol to Multi Party Key Agreement
Abstract

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

A General Correlation Theorem
Abstract

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

Hiji-bij-bij: A New Stream Cipher with a Self-Synchronizing Mode of Operation
Abstract

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

Domain Extender for Collision Resistant Hash Functions: Improving Upon Merkle-Damgaard Iteration
Abstract

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

Parallelizing Explicit Formula for Arithmetic in the Jacobian of Hyperelliptic Curves
Abstract

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

Construction of Perfect Nonlinear and Maximally Nonlinear Multi-Output Boolean Functions Satisfying Higher Order Strict Avalanche Criteria
Abstract

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

Masking Based Domain Extenders for UOWHFs: Bounds and Constructions
Abstract

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

Inversion of Several Field Elements: A New Parallel Algorithm
Abstract

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

EPRINT

A Parallelizable Design Principle for Cryptographic Hash Functions
Abstract

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

Construction of UOWHF: Tree Hashing Revisited
Abstract

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.

2000

EPRINT

New Directions in Design of Resilient Boolean Functions
Abstract

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

New Constructions of Resilent and Correlation Immune Boolean Functions achieving Upper Bounds on Nonlinearity
Abstract

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

Spectral Domain Analysis of Correlation Immune and Resilient Boolean Functions
Abstract

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.

#### Program Committees

- 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

#### Coauthors

- Rana Barua (3)
- Sanjay Bhattacherjee (1)
- Debrup Chakraborty (7)
- Donghoon Chang (1)
- Sanjit Chatterjee (7)
- Seongtaek Chee (1)
- Ratna Dutta (3)
- Sebati Ghosh (1)
- Kishan Chand Gupta (3)
- Jin Hong (3)
- Thomas Johansson (1)
- Sabyasachi Karati (1)
- Wonil Lee (1)
- Sangjin Lee (1)
- Dong Hoon Lee (1)
- Subhamoy Maitra (6)
- Cuauhtemoc Mancillas-Lopez (1)
- Pradeep Kumar Mishra (5)
- Joydip Mitra (1)
- Sourav Mukhopadhyay (3)
- Mridul Nandi (1)
- Pinakpani Pal (2)
- Enes Pasalic (1)
- Somindu C. Ramanna (2)
- Kouichi Sakurai (1)
- Subhabrata Samajder (3)
- Somitra Kumar Sanadhya (9)
- Paul J. Schellenberg (1)
- Shashank Singh (5)