TY - GEN
T1 - (Almost) optimal constructions of UOWHFs from 1-to-1, regular one-way functions and beyond
AU - Yu, Yu
AU - Gu, Dawu
AU - Li, Xiangxue
AU - Weng, Jian
N1 - Publisher Copyright:
© International Association for Cryptologic Research 2015.
PY - 2015
Y1 - 2015
N2 - We revisit the problem of black-box constructions of universal one-way hash functions (UOWHFs) from several typical classes of one-way functions (OWFs), and give respective constructions that either improve or generalize the best previously known. – For any 1-to-1 one-way function, we give an optimal construction of UOWHFs with key and output length Θ(n) by making a single call to the underlying OWF. This improves the constructions of Naor and Yung (STOC 1989) and De Santis and Yung (Eurocrypt 1990) that need key length O(n · ω(log n)). – For any known-(almost-)regular one-way function with known hardness, we give an optimal construction of UOWHFs with key and output length Θ(n) and a single call to the one-way function. – For any known-(almost-)regular one-way function, we give a construction of UOWHFs with key and output length O(n·ω(1)) and by making ω(1) non-adaptive calls to the one-way function. This improves the construction of Barhum and Maurer (Latincrypt 2012) that requires key and output length O(n·ω(log n)) and ω(log n) calls. – For any weakly-regular one-way function introduced by Yu et al. at TCC 2015 (i.e., the set of inputs with maximal number of siblings is of an n −c-fraction for some constant c), we give a construction of UOWHFs with key length O(n·logn) and output length Θ(n). This generalizes the construction of Ames et al. (Asiacrypt 2012) which requires an unknown-regular one-way function (i.e., c = 0). Along the way, we use several techniques that might be of independent interest. We show that almost 1-to-1 (except for a negligible fraction) one-way functions and known (almost-)regular one-way functions are equivalent in the known-hardness (or non-uniform) setting, by giving an optimal construction of the former from the latter. In addition, we show how to transform any one-way function that is far from regular (but only weakly regular on a noticeable fraction of domain) into an almost-regular one-way function.
AB - We revisit the problem of black-box constructions of universal one-way hash functions (UOWHFs) from several typical classes of one-way functions (OWFs), and give respective constructions that either improve or generalize the best previously known. – For any 1-to-1 one-way function, we give an optimal construction of UOWHFs with key and output length Θ(n) by making a single call to the underlying OWF. This improves the constructions of Naor and Yung (STOC 1989) and De Santis and Yung (Eurocrypt 1990) that need key length O(n · ω(log n)). – For any known-(almost-)regular one-way function with known hardness, we give an optimal construction of UOWHFs with key and output length Θ(n) and a single call to the one-way function. – For any known-(almost-)regular one-way function, we give a construction of UOWHFs with key and output length O(n·ω(1)) and by making ω(1) non-adaptive calls to the one-way function. This improves the construction of Barhum and Maurer (Latincrypt 2012) that requires key and output length O(n·ω(log n)) and ω(log n) calls. – For any weakly-regular one-way function introduced by Yu et al. at TCC 2015 (i.e., the set of inputs with maximal number of siblings is of an n −c-fraction for some constant c), we give a construction of UOWHFs with key length O(n·logn) and output length Θ(n). This generalizes the construction of Ames et al. (Asiacrypt 2012) which requires an unknown-regular one-way function (i.e., c = 0). Along the way, we use several techniques that might be of independent interest. We show that almost 1-to-1 (except for a negligible fraction) one-way functions and known (almost-)regular one-way functions are equivalent in the known-hardness (or non-uniform) setting, by giving an optimal construction of the former from the latter. In addition, we show how to transform any one-way function that is far from regular (but only weakly regular on a noticeable fraction of domain) into an almost-regular one-way function.
UR - https://www.scopus.com/pages/publications/84943402050
U2 - 10.1007/978-3-662-48000-7_11
DO - 10.1007/978-3-662-48000-7_11
M3 - 会议稿件
AN - SCOPUS:84943402050
SN - 9783662479995
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 209
EP - 229
BT - Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Proceedings
A2 - Robshaw, Matthew
A2 - Gennaro, Rosario
PB - Springer Verlag
T2 - 35th Annual Cryptology Conference, CRYPTO 2015
Y2 - 16 August 2015 through 20 August 2015
ER -