2 Search Results for "Khovratovich, Dmitry"

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-dev.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}
}
Document
DOI: 10.4230/OASIcs.Tokenomics.2019.13
MixEth: Efficient, Trustless Coin Mixing Service for Ethereum

Authors: István András Seres, Dániel A. Nagy, Chris Buckland, and Péter Burcsi

Published in: OASIcs, Volume 71, International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2019)

Abstract
Coin mixing is a prevalent privacy-enhancing technology for cryptocurrency users. In this paper, we present MixEth, which is a trustless coin mixing service for Turing-complete blockchains. MixEth does not rely on a trusted setup and is more efficient than any proposed trustless coin tumbler. It requires only 3 on-chain transactions at most per user and 1 off-chain message. It achieves strong notions of anonymity and is able to resist denial-of-service attacks. Furthermore the underlying protocol can also be used to efficiently shuffle ballots, ciphertexts in a trustless and decentralized manner.
Cite as

István András Seres, Dániel A. Nagy, Chris Buckland, and Péter Burcsi. MixEth: Efficient, Trustless Coin Mixing Service for Ethereum. In International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2019). Open Access Series in Informatics (OASIcs), Volume 71, pp. 13:1-13:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{seres_et_al:OASIcs.Tokenomics.2019.13,
  author =	{Seres, Istv\'{a}n Andr\'{a}s and Nagy, D\'{a}niel A. and Buckland, Chris and Burcsi, P\'{e}ter},
  title =	{{MixEth: Efficient, Trustless Coin Mixing Service for Ethereum}},
  booktitle =	{International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2019)},
  pages =	{13:1--13:20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-108-5},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{71},
  editor =	{Danos, Vincent and Herlihy, Maurice and Potop-Butucaru, Maria and Prat, Julien and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tokenomics.2019.13},
  URN =		{urn:nbn:de:0030-drops-119770},
  doi =		{10.4230/OASIcs.Tokenomics.2019.13},
  annote =	{Keywords: Cryptography, Verifiable shuffle, Anonymity, Cryptocurrency, Ethereum, Coin mixer, State Channel}
}
  • Refine by Author
  • 1 Buckland, Chris
  • 1 Burcsi, Péter
  • 1 Dodis, Yevgeniy
  • 1 Khovratovich, Dmitry
  • 1 Mouha, Nicky
  • Show More...

  • Refine by Classification
  • 1 Security and privacy → Cryptography
  • 1 Theory of computation → Cryptographic protocols

  • Refine by Keyword
  • 1 Anonymity
  • 1 Coin mixer
  • 1 Cryptocurrency
  • 1 Cryptography
  • 1 Ethereum
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2020
  • 1 2021

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