Paper 2013/423

Locally Computable UOWHF with Linear Shrinkage

Benny Applebaum, Tel Aviv University
Yoni Moses

This is an errata for our paper, ``Locally Computable UOWHF with Linear Shrinkage''. There is a gap in the proof of Theorem 4.1 that asserts that the collection $F_{P,n,m}$ is $\delta$-secure $\beta$-random target-collision resistant assuming the one-wayness and the pseudorandomness of the collection for related parameters. We currently do not know whether Theorem 4.1 (as stated in Section 4) holds. We are grateful to Colin Sandon for pointing out the gap. We note that Theorem 5.1, which transforms any $\delta$-secure $\beta$-random target collision resistant collection to a target collision resistant collection while preserving constant locality and linear shrinkage, remains intact. Thus, one can construct a locally computable UOWHF with linear shrinkage based on the hypothesis that random local functions are $\delta$-secure $\beta$-random target-collision resistant. We also mention that locally-computable functions with linear-shrinkage that achieve a stronger form of *collision-resistance* were constructed by Applebaum, Haramaty, Ishai, Kushilevitz and Vaikuntanathan (ITCS 2017) based on incomparable assumptions.

Note: This is an errata.

Available format(s)
Publication info
Published elsewhere. An extended abstract of this work appears in Eurocrypt 2013
hash functions NC0 input locality output locality
Contact author(s)
benny applebaum @ gmail com
ymoses @ gmail com
2022-11-27: last of 2 revisions
2013-07-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Benny Applebaum and Yoni Moses},
      title = {Locally Computable {UOWHF} with Linear Shrinkage},
      howpublished = {Cryptology ePrint Archive, Paper 2013/423},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.