Paper 2013/423
Locally Computable UOWHF with Linear Shrinkage
Abstract
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.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published elsewhere. An extended abstract of this work appears in Eurocrypt 2013
- Keywords
- hash functions NC0 input locality output locality
- Contact author(s)
-
benny applebaum @ gmail com
ymoses @ gmail com - History
- 2022-11-27: last of 2 revisions
- 2013-07-02: received
- See all versions
- Short URL
- https://ia.cr/2013/423
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2013/423,
author = {Benny Applebaum and Yoni Moses},
title = {Locally Computable {UOWHF} with Linear Shrinkage},
howpublished = {Cryptology {ePrint} Archive, Paper 2013/423},
year = {2013},
url = {https://eprint.iacr.org/2013/423}
}
