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 $$-secure $$-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 $$-secure $$-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.