Search Results

Documents authored by Nandi, Mridul

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.26
Improved Streaming Algorithm for the Klee’s Measure Problem and Generalizations

Authors: Mridul Nandi, N. V. Vinodchandran, Arijit Ghosh, Kuldeep S. Meel, Soumit Pal, and Sourav Chakraborty

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

Abstract
Estimating the size of the union of a stream of sets S₁, S₂, …, S_M where each set is a subset of a known universe Ω is a fundamental problem in data streaming. This problem naturally generalizes the well-studied 𝖥₀ estimation problem in the streaming literature, where each set contains a single element from the universe. We consider the general case when the sets S_i can be succinctly represented and allow efficient membership, cardinality, and sampling queries (called a Delphic family of sets). A notable example in this framework is the Klee’s Measure Problem (KMP), where every set S_i is an axis-parallel rectangle in d-dimensional spaces (Ω = [Δ]^d where [Δ] := {1, … ,Δ} and Δ ∈ ℕ). Recently, Meel, Chakraborty, and Vinodchandran (PODS-21, PODS-22) designed a streaming algorithm for (ε,δ)-estimation of the size of the union of set streams over Delphic family with space and update time complexity O((log³|Ω|)/ε² ⋅ log 1/δ) and Õ((log⁴|Ω|)/ε² ⋅ log 1/(δ)), respectively. This work presents a new, sampling-based algorithm for estimating the size of the union of Delphic sets that has space and update time complexity Õ((log²|Ω|)/ε² ⋅ log 1/(δ)). This improves the space complexity bound by a log|Ω| factor and update time complexity bound by a log² |Ω| factor. A critical question is whether quadratic dependence of log|Ω| on space and update time complexities is necessary. Specifically, can we design a streaming algorithm for estimating the size of the union of sets over Delphic family with space and complexity linear in log|Ω| and update time poly(log|Ω|)? While this appears technically challenging, we show that establishing a lower bound of ω(log|Ω|) with poly(log|Ω|) update time is beyond the reach of current techniques. Specifically, we show that under certain hard-to-prove computational complexity hypothesis, there is a streaming algorithm for the problem with optimal space complexity O(log|Ω|) and update time poly(log(|Ω|)). Thus, establishing a space lower bound of ω(log|Ω|) will lead to break-through complexity class separation results.
Cite as

Mridul Nandi, N. V. Vinodchandran, Arijit Ghosh, Kuldeep S. Meel, Soumit Pal, and Sourav Chakraborty. Improved Streaming Algorithm for the Klee’s Measure Problem and Generalizations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 26:1-26:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{nandi_et_al:LIPIcs.APPROX/RANDOM.2024.26,
  author =	{Nandi, Mridul and Vinodchandran, N. V. and Ghosh, Arijit and Meel, Kuldeep S. and Pal, Soumit and Chakraborty, Sourav},
  title =	{{Improved Streaming Algorithm for the Klee’s Measure Problem and Generalizations}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{26:1--26:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.26},
  URN =		{urn:nbn:de:0030-drops-210191},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.26},
  annote =	{Keywords: Sampling, Streaming, Klee’s Measure Problem}
}
Document
DOI: 10.4230/LIPIcs.ITC.2022.11
Revisiting Collision and Local Opening Analysis of ABR Hash

Authors: Chandranan Dhar, Yevgeniy Dodis, and Mridul Nandi

Published in: LIPIcs, Volume 230, 3rd Conference on Information-Theoretic Cryptography (ITC 2022)

Abstract
The question of building the most efficient tn-to-n-bit collision-resistant hash function H from a smaller (say, 2n-to-n-bit) compression function f is one of the fundamental questions in symmetric key cryptography. This question has a rich history, and was open for general t, until a recent breakthrough paper by Andreeva, Bhattacharyya and Roy at Eurocrypt'21, who designed an elegant mode (which we call ABR) achieving roughly 2t/3 calls to f, which matches the famous Stam’s bound from CRYPTO'08. Unfortunately, we have found serious issues in the claims made by the authors. These issues appear quite significant, and range from verifiably false statements to noticeable gaps in the proofs (e.g., omissions of important cases and unjustified bounds). We were unable to patch up the current proof provided by the authors. Instead, we prove from scratch the security of the ABR construction for the first non-trivial case t = 11 (ABR mode of height 3), which was incorrectly handled by the authors. In particular, our result matches Stam’s bound for t = 11. While the general case is still open, we hope our techniques will prove useful to finally settle the question of the optimal efficiency of hash functions.
Cite as

Chandranan Dhar, Yevgeniy Dodis, and Mridul Nandi. Revisiting Collision and Local Opening Analysis of ABR Hash. In 3rd Conference on Information-Theoretic Cryptography (ITC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 230, pp. 11:1-11:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dhar_et_al:LIPIcs.ITC.2022.11,
  author =	{Dhar, Chandranan and Dodis, Yevgeniy and Nandi, Mridul},
  title =	{{Revisiting Collision and Local Opening Analysis of ABR Hash}},
  booktitle =	{3rd Conference on Information-Theoretic Cryptography (ITC 2022)},
  pages =	{11:1--11:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-238-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{230},
  editor =	{Dachman-Soled, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2022.11},
  URN =		{urn:nbn:de:0030-drops-164890},
  doi =		{10.4230/LIPIcs.ITC.2022.11},
  annote =	{Keywords: ABR hash, collision resistance, local opening}
}
Document
DOI: 10.4230/LIPIcs.ITC.2021.24
T₅: Hashing Five Inputs with Three Compression Calls

Authors: Yevgeniy Dodis, Dmitry Khovratovich, Nicky Mouha, and Mridul Nandi

Published in: LIPIcs, Volume 199, 2nd Conference on Information-Theoretic Cryptography (ITC 2021)

Abstract
Given 2n-to-n compression functions h₁,h₂,h₃, we build a new 5n-to-n compression function T₅, using only 3 compression calls: T₅(m₁, m₂, m₃, m₄, m₅) : = h₃(h₁(m₁, m₂)⊕ m₅ , h₂(m₃, m₄)⊕ m₅) ⊕ m₅ We prove that this construction matches Stam’s bound, by providing Õ(q²/2ⁿ) collision security and O(q³/2^{2n}+ nq/2ⁿ) preimage security (the latter term dominates in the region of interest, when q < 2^{n/2}). In particular, it provides birthday security for hashing 5 inputs using three 2n-to-n compression calls, instead of only 4 inputs in prior constructions. Thus, we get a sequential variant of the Merkle-Damgård (MD) hashing, where t message blocks are hashed using only 3t/4 calls to the 2n-to-n compression functions; a 25% saving over traditional hash function constructions. This time reduces to t/4 (resp. t/2) sequential calls using 3 (resp. 2) parallel execution units; saving a factor of 4 (resp. 2) over the traditional MD-hashing, where parallelism does not help to process one message. We also get a novel variant of a Merkle tree, where t message blocks can be processed using 0.75(t-1) compression function calls and depth 0.86 log₂ t, thereby saving 25% in the number of calls and 14% in the update time over Merkle trees. We provide two modes for a local opening of a particular message block: conservative and aggressive. The former retains the birthday security, but provides longer proofs and local verification time than the traditional Merkle tree. For the aggressive variant, we reduce the proof length to a 29% overhead compared to Merkle trees (1.29log₂ t vs log₂ t), but the verification time is now 14% faster (0.86log₂ t vs log₂ t). However, birthday security is only shown under a plausible conjecture related to the 3-XOR problem, and only for the (common, but not universal) setting where the root of the Merkle tree is known to correspond to a valid t-block message.
Cite as

Yevgeniy Dodis, Dmitry Khovratovich, Nicky Mouha, and Mridul Nandi. T₅: Hashing Five Inputs with Three Compression Calls. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 24:1-24:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{dodis_et_al:LIPIcs.ITC.2021.24,
  author =	{Dodis, Yevgeniy and Khovratovich, Dmitry and Mouha, Nicky and Nandi, Mridul},
  title =	{{T₅: Hashing Five Inputs with Three Compression Calls}},
  booktitle =	{2nd Conference on Information-Theoretic Cryptography (ITC 2021)},
  pages =	{24:1--24:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-197-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{199},
  editor =	{Tessaro, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2021.24},
  URN =		{urn:nbn:de:0030-drops-143430},
  doi =		{10.4230/LIPIcs.ITC.2021.24},
  annote =	{Keywords: hash functions, Merkle trees, Merkle-Damg\r{a}rd, collision resistance}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact