We study the problem of constructing locally computable Universal One-Way Hash Functions (UOWHFs) H:\{0,1\}^n \rightarrow \{0,1\}^m. A construction with constant \emph{output locality}, where every bit of the output depends only on a constant number of bits of the input, was established by [Applebaum, Ishai, and Kushilevitz, SICOMP 2006]. However, this ... more >>>