Hardness-Preserving Reductions via Cuckoo Hashing
Abstract The focus of this work is hardness-preserving transformations of somewhat limited pseudorandom functions families (PRFs) into ones with more versatile characteristics. Consider the problem of domain extension of pseudorandom functions: given a PRF that takes as input elements...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer US
2021
|
| Online Access: | https://hdl.handle.net/1721.1/131491 |
| _version_ | 1826195536310435840 |
|---|---|
| author | Berman, Itay Haitner, Iftach Komargodski, Ilan Naor, Moni |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Berman, Itay Haitner, Iftach Komargodski, Ilan Naor, Moni |
| author_sort | Berman, Itay |
| collection | MIT |
| description | Abstract
The focus of this work is hardness-preserving transformations of somewhat limited pseudorandom functions families (PRFs) into ones with more versatile characteristics. Consider the problem of domain extension of pseudorandom functions: given a PRF that takes as input elements of some domain
$$\mathcal {U}$$
U
, we would like to come up with a PRF over a larger domain. Can we do it with little work and without significantly impacting the security of the system? One approach is to first hash the larger domain into the smaller one and then apply the original PRF. Such a reduction, however, is vulnerable to a “birthday attack”: after
$$\sqrt{\left| \mathcal {U}\right| }$$
U
queries to the resulting PRF, a collision (i.e., two distinct inputs having the same hash value) is very likely to occur. As a consequence, the resulting PRF is insecure against an attacker making this number of queries. In this work, we show how to go beyond the aforementioned birthday attack barrier by replacing the above simple hashing approach with a variant of cuckoo hashing, a hashing paradigm that resolves collisions in a table by using two hash functions and two tables, cleverly assigning each element to one of the two tables. We use this approach to obtain: (i) a domain extension method that requires just two calls to the original PRF can withstand as many queries as the original domain size, and has a distinguishing probability that is exponentially small in the amount of non-cryptographic work; and (ii) a security-preserving reduction from non-adaptive to adaptive PRFs. |
| first_indexed | 2024-09-23T10:14:16Z |
| format | Article |
| id | mit-1721.1/131491 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T10:14:16Z |
| publishDate | 2021 |
| publisher | Springer US |
| record_format | dspace |
| spelling | mit-1721.1/1314912023-09-26T20:24:37Z Hardness-Preserving Reductions via Cuckoo Hashing Berman, Itay Haitner, Iftach Komargodski, Ilan Naor, Moni Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Abstract The focus of this work is hardness-preserving transformations of somewhat limited pseudorandom functions families (PRFs) into ones with more versatile characteristics. Consider the problem of domain extension of pseudorandom functions: given a PRF that takes as input elements of some domain $$\mathcal {U}$$ U , we would like to come up with a PRF over a larger domain. Can we do it with little work and without significantly impacting the security of the system? One approach is to first hash the larger domain into the smaller one and then apply the original PRF. Such a reduction, however, is vulnerable to a “birthday attack”: after $$\sqrt{\left| \mathcal {U}\right| }$$ U queries to the resulting PRF, a collision (i.e., two distinct inputs having the same hash value) is very likely to occur. As a consequence, the resulting PRF is insecure against an attacker making this number of queries. In this work, we show how to go beyond the aforementioned birthday attack barrier by replacing the above simple hashing approach with a variant of cuckoo hashing, a hashing paradigm that resolves collisions in a table by using two hash functions and two tables, cleverly assigning each element to one of the two tables. We use this approach to obtain: (i) a domain extension method that requires just two calls to the original PRF can withstand as many queries as the original domain size, and has a distinguishing probability that is exponentially small in the amount of non-cryptographic work; and (ii) a security-preserving reduction from non-adaptive to adaptive PRFs. 2021-09-20T17:17:18Z 2021-09-20T17:17:18Z 2018-05-07 2020-09-24T21:22:04Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/131491 en https://doi.org/10.1007/s00145-018-9293-0 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. International Association for Cryptologic Research application/pdf Springer US Springer US |
| spellingShingle | Berman, Itay Haitner, Iftach Komargodski, Ilan Naor, Moni Hardness-Preserving Reductions via Cuckoo Hashing |
| title | Hardness-Preserving Reductions via Cuckoo Hashing |
| title_full | Hardness-Preserving Reductions via Cuckoo Hashing |
| title_fullStr | Hardness-Preserving Reductions via Cuckoo Hashing |
| title_full_unstemmed | Hardness-Preserving Reductions via Cuckoo Hashing |
| title_short | Hardness-Preserving Reductions via Cuckoo Hashing |
| title_sort | hardness preserving reductions via cuckoo hashing |
| url | https://hdl.handle.net/1721.1/131491 |
| work_keys_str_mv | AT bermanitay hardnesspreservingreductionsviacuckoohashing AT haitneriftach hardnesspreservingreductionsviacuckoohashing AT komargodskiilan hardnesspreservingreductionsviacuckoohashing AT naormoni hardnesspreservingreductionsviacuckoohashing |