978-3-031-57725-3_12.pdf (470.53 kB)

Rate-1 Fully Local Somewhere Extractable Hashing from DDH

Download (470.53 kB)
conference contribution
posted on 2024-04-26, 12:18 authored by Pedro Branco, Nico DöttlingNico Döttling, Akshayaram Srinivasan, Riccardo ZanottoRiccardo Zanotto
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 2022) 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+poly () (where 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 € {0,1}. 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.


Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

International Conference on Practice and Theory in Public Key Cryptography (PKC)



Page Range



Springer Nature

Open Access Type

  • Not Open Access


@inproceedings{Branco:Döttling:Srinivasan:Zanotto:2024, title = "Rate-1 Fully Local Somewhere Extractable Hashing from DDH", author = "Branco, Pedro" AND "Döttling, Nico" AND "Srinivasan, Akshayaram" AND "Zanotto, Riccardo", year = 2024, month = 4, pages = "356--386", publisher = "Springer Nature", issn = "1611-3349", doi = "10.1007/978-3-031-57725-3_12" }