Rishiraj Bhattacharyya

Elena Andreeva, Rishiraj Bhattacharyya, Arnab Roy

We revisit the classical problem of designing optimally efficient cryptographically secure hash functions. Hash functions are traditionally designed via applying modes of operation on primitives with smaller domains. The results of Shrimpton and Stam (ICALP 2008), Rogaway and Steinberger (CRYPTO 2008), and Mennink and Preneel (CRYPTO 2012) show how to achieve optimally efficient designs of $2n$-to-$n$-bit compression functions from non-compressing primitives with asymptotically optimal $2^{n/2-ε}$-query collision resistance. Designing optimally efficient and secure hash functions for larger domains ($> 2n$ bits) is still an open problem. In this work we propose the new \textit{compactness} efficiency notion. It allows us to focus on asymptotically optimally collision resistant hash function and normalize their parameters based on Stam's bound from CRYPTO 2008 to obtain maximal efficiency. We then present two tree-based modes of operation -Our first construction is an \underline{A}ugmented \underline{B}inary T\underline{r}ee (ABR) mode. The design is a $(2^{\ell}+2^{\ell-1} -1)n$-to-$n$-bit hash function making a total of $(2^{\ell}-1)$ calls to $2n$-to-$n$-bit compression functions for any $\ell\geq 2$. Our construction is optimally compact with asymptotically (optimal) $2^{n/2-ε}$-query collision resistance in the ideal model. For a tree of height $\ell$, in comparison with Merkle tree, the $ABR$ mode processes additional $(2^{\ell-1}-1)$ data blocks making the same number of internal compression function calls. -While the $ABR$ mode achieves collision resistance, it fails to achieve indifferentiability from a random oracle within $2^{n/3}$ queries. $ABR^{+}$ compresses only $1$ less data block than $ABR$ with the same number of compression calls and achieves in addition indifferentiability up to $2^{n/2-ε}$ queries.

Rishiraj Bhattacharyya, Mridul Nandi, Anik Raychaudhuri

In CRYPTO 2018, Russell et al introduced the notion of crooked indifferentiability to analyze the security of a hash function when the underlying primitive is subverted. They showed that the $n$-bit to $n$-bit function implemented using enveloped XOR construction (\textsf{EXor}) with $3n+1$ many $n$-bit functions and $3n^2$-bit random initial vectors (iv) can be proven secure asymptotically in the crooked indifferentiability setting. -We identify several major issues and gaps in the proof by Russel et al, We show that their proof can achieve security only when the adversary is restricted to make queries related to a single message. - We formalize new technique to prove crooked indifferentiability without such restrictions. Our technique can handle function dependent subversion. We apply our technique to provide a revised proof for the \textsf{EXor} construction. - We analyze crooked indifferentiability of the classical sponge construction. We show, using a simple proof idea, the sponge construction is a crooked-indifferentiable hash function using only $n$-bit random iv. This is a quadratic improvement over the {\sf EXor} construction and solves the main open problem of Russel et al.