International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Rate-1 Fully Local Somewhere Extractable Hashing from DDH

Authors:
Pedro Branco , Max Planck Institute for Security and Privacy, Germany
Nico Döttling , CISPA Helmholtz Center for Information Security, Germany
Akshayaram Srinivasan , University of Toronto, Canada
Riccardo Zanotto , CISPA Helmholtz Center for Information Security, Germany
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: PKC 2024
Abstract: Somewhere statistically binding (SSB) hashing allows us to sample a special hashing key such that the digest statistically binds the input at $m$ secret locations. This hash function is said to be somewhere extractable (SE) if there is an additional trapdoor that allows the extraction of the input bits at the $m$ locations from the digest. Devadas, Goyal, Kalai, and Vaikuntanathan (FOCS 22) introduced a variant of somewhere extractable hashing called rate-1 fully local SE hash functions. The rate-1 requirement states that the size of the digest is $m + \polyn(\lambda)$ (where $\lambda$ is the security parameter). The fully local property requires that for any index $i$, there is a ``very short" opening showing that $i$-th bit of the hashed input is equal to $b$ for some $b \in \bin$. The size of this opening is required to be independent of $m$ and in particular, this means that its size is independent of the size of the digest. Devadas et al. gave such a construction from Learning with Errors (LWE). In this work, we give a construction of a rate-1 fully local somewhere extractable hash function from Decisional Diffie-Hellman (DDH) and BARGs. Under the same assumptions, we give constructions of rate-1 BARG and RAM SNARG with partial input soundness whose proof sizes are only matched by prior constructions based on LWE.
BibTeX
@inproceedings{pkc-2024-33798,
  title={Rate-1 Fully Local Somewhere Extractable Hashing from DDH},
  publisher={Springer-Verlag},
  author={Pedro Branco and Nico Döttling and Akshayaram Srinivasan and Riccardo Zanotto},
  year=2024
}