# zbMATH — the first resource for mathematics

Locally computable UOWHF with linear shrinkage. (English) Zbl 1377.94028
Summary: We study the problem of constructing locally computable universal one-way hash functions (UOWHFs) $$\mathcal {H}:\{0,1\}^n \rightarrow \{0,1\}^m$$. A construction with constant output locality, where every bit of the output depends only on a constant number of bits of the input, was established by the first author et al. [SIAM J. Comput. 36, No. 4, 845–888 (2006; Zbl 1126.94014)]. However, this construction suffers from two limitations: (1) it can only achieve a sublinear shrinkage of $$n-m=n^{1-\epsilon }$$ and (2) it has a super-constant input locality, i.e., some inputs influence a large super-constant number of outputs. This leaves open the question of realizing UOWHFs with constant output locality and linear shrinkage of $$n-m= \epsilon n$$, or UOWHFs with constant input locality and minimal shrinkage of $$n-m=1$$. We settle both questions simultaneously by providing the first construction of UOWHFs with linear shrinkage, constant input locality and constant output locality. Our construction is based on the one-wayness of “random” local functions–a variant of an assumption made by O. Goldreich [Studies in complexity and cryptography. Lect. Notes Comput. Sci. 6650, 76–87 (2011; Zbl 1306.94056)]. Using a transformation of Y. Ishai et al. [Proceedings of the 40th annual ACM symposium on theory of computing 2008, STOC 2008. New York, NY: ACM, 433–442 (2008; Zbl 1231.94050)], our UOWHFs give rise to a digital signature scheme with a minimal additive complexity overhead: signing $$n$$-bit messages with security parameter $$\kappa$$ takes only $$O(n+\kappa )$$ time instead of $$O(n\kappa )$$ as in typical constructions. Previously, such signatures were only known to exist under an exponential hardness assumption. As an additional contribution, we obtain new locally computable hardness amplification procedures for UOWHFs that preserve linear shrinkage.
An extended abstract appeared in [Eurocrypt 2013, Lect. Notes Comput. Sci. 7881, 486–502 (2013; Zbl 1306.94022)].
##### MSC:
 94A60 Cryptography
Full Text:
##### References:
 [1] D. Achlioptas, F. Ricci-Tersenghi, On the solution-space geometry of random constraint satisfaction problems, in J.M. Kleinberg, editor, 38th ACM STOC (ACM Press, 2006), pp. 130-139 · Zbl 1301.68190 [2] M. Alekhnovich, E.A. Hirsch, D. Itsykson, Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas. J. Autom. Reason., 35(1-3), 51-72 (2005) · Zbl 1109.68098 [3] B. Applebaum, Cryptography in Constant Parallel Time. Phd thesis, Technion (Israel Institute of Technology, 2007) [4] B. Applebaum, Pseudorandom generators with long stretch and low locality from random local one-way functions. SIAM J. Comput.42(5), (2013) · Zbl 1317.94081 [5] B. Applebaum, A. Bogdanov, A. Rosen, A dichotomy for local small-bias generators, in R. Cramer, editor, TCC 2012, volume 7194 of LNCS (Springer, 2012), pp. 600-617 · Zbl 1304.68041 [6] B. Applebaum, Y. Ishai, E. Kushilevitz, Computationally private randomizing polynomials and their applications. J. Comput. Complex.15(2), 115-162 (2006) · Zbl 1143.94009 [7] B. Applebaum, Y. Ishai, E. Kushilevitz, Cryptography in $$\text{NC}^{\text{0 }}$$. SIAM J. Comput.36(4), 845-888 (2006) · Zbl 1126.94014 [8] B. Applebaum, Y. Ishai, E. Kushilevitz, Cryptography with constant input locality. J. Cryptol.22(4), 429-469 (2009) · Zbl 1183.94018 [9] M. Bellare, P. Rogaway, Collision-resistant hashing: towards making UOWHFs practical, in B.S. Kaliski Jr., editor, CRYPTO’97, volume 1294 of LNCS (Springer, 1997), pp. 470-484 · Zbl 0882.94015 [10] A. Bogdanov, Y. Qiao. On the security of goldreich’s one-way function, in Proceedings of the 13th RANDOM (2009), pp. 392-405 · Zbl 1255.94053 [11] A. Bogdanov, A. Rosen, Input locality and hardness amplification, in Y. Ishai, editor, TCC 2011, volume 6597 of LNCS (Springer, 2011), pp. 1-18 · Zbl 1281.94016 [12] M.R. Capalbo, O. Reingold, S.P. Vadhan, A. Wigderson, Randomness conductors and constant-degree lossless expanders, in 34th ACM STOC (ACM Press, 2002), pp. 659-668 · Zbl 1192.68475 [13] J. Cook, O. Etesami, R. Miller, L. Trevisan, Goldreich’s one-way function candidate and myopic backtracking algorithms, in O. Reingold, editor, TCC 2009, volume 5444 of LNCS (Springer, 2009), pp. 521-538 · Zbl 1213.94092 [14] S.O. Etesami. Pseudorandomness against depth-2 circuits and analysis of goldreich’s candidate one-way function. Technical Report EECS-2010-180 (UC Berkeley, 2010) [15] O. Goldreich, Foundations of Cryptography: Basic Tools (Cambridge University Press, 2001) · Zbl 1007.94016 [16] O. Goldreich, Candidate one-way functions based on expander graphs, in Studies in Complexity and Cryptography (2011), pp. 76-87. ECCC 2010 · Zbl 1306.94056 [17] I. Haitner, T. Holenstein, O. Reingold, S.P. Vadhan, H. Wee. Universal one-way hash functions via inaccessible entropy, in H. Gilbert, editor, EUROCRYPT 2010, volume 6110 of LNCS (Springer, 2010), pp. 616-637 · Zbl 1280.94065 [18] R. Impagliazzo, V. Kabanets, Constructive proofs of concentration bounds, in APPROX-RANDOM (2010), pp. 617-631 · Zbl 1305.68331 [19] Y. Ishai, E. Kushilevitz, R. Ostrovsky, A. Sahai, Cryptography with constant computational overhead, in R.E. Ladner, C. Dwork, editors, 40th ACM STOC (ACM Press, 2008), pp. 433-442 · Zbl 1231.94050 [20] D. Itsykson, Lower bound on average-case complexity of inversion of goldreich’s function by drunken backtracking algorithms, in Computer Science - Theory and Applications, 5th International Computer Science Symposium in Russia (2010), pp. 204-215 · Zbl 1285.68056 [21] R. Miller, Goldreich’s one-way function candidate and drunken backtracking algorithms. Distinguished major thesis (University of Virginia, 2009) · Zbl 1213.94092 [22] E. Mossel, A. Shpilka, L. Trevisan, On e-biased generators in NC0, in 44th FOCS (IEEE Computer Society Press, 2003), pp. 136-145 [23] M. Naor, M. Yung, Universal one-way hash functions and their cryptographic applications, in 21st ACM STOC (ACM Press, 1989), pp. 33-43 [24] S.K. Panjwani, An experimental evaluation of goldreich’s one-way function. Technical report (IIT, Bombay, 2001) [25] P. Rogaway, T. Shrimpton, Cryptographic hash-function basics: Definitions, implications, and separations for preimage resistance, second-preimage resistance, and collision resistance, in B.K. Roy, W. Meier, editors, FSE 2004, volume 3017 of LNCS (Springer, 2004), pp. 371-388 · Zbl 1079.68560 [26] J. Rompel, One-way functions are necessary and sufficient for secure signatures, in 22nd ACM STOC (ACM Press, 1990), pp. 387-394 [27] M. Sipser, D.A. Spielman, Expander codes. IEEETIT: IEEE Transactions on Information Theory (1996), p. 42 · Zbl 0943.94543
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.