Publications
Detailed Information
Adventures in crypto dark matter: attacks, fixes and analysis for weak pseudorandom functions
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Cheon, Jung Hee | - |
dc.contributor.author | Cho, Wonhee | - |
dc.contributor.author | Kim, Jeong Han | - |
dc.contributor.author | Kim, Jiseung | - |
dc.date.accessioned | 2022-09-30T05:52:54Z | - |
dc.date.available | 2022-09-30T05:52:54Z | - |
dc.date.created | 2022-08-17 | - |
dc.date.issued | 2022-08 | - |
dc.identifier.citation | Designs, Codes, and Cryptography, Vol.90 No.8, pp.1735-1760 | - |
dc.identifier.issn | 0925-1022 | - |
dc.identifier.uri | https://hdl.handle.net/10371/184908 | - |
dc.description.abstract | A weak pseudorandom function (weak PRF) is one of the most important cryptographic primitives for its efficiency although it has lower security than a standard PRF. Recently, Boneh et al. (in: Theory of cryptography conference, Springer, pp 699-729, 2018) introduced two types of new weak PRF candidates, which are called a basicMod-2/Mod-3 and alternative Mod-2/Mod-3 weak PRF. Both use the mixture of linear computations defined on different small moduli to satisfy conceptual simplicity, low complexity (depth-2 ACC(0)) and MPC friendliness. In fact, the new candidates are conjectured to be exponentially secure against any adversary that allows exponentially many samples, and a basicMod-2/Mod-3 weak PRF is the only candidate that satisfies all the features above. However, none of the direct attacks which focus on basic and alternative Mod-2/Mod-3 weak PRFs use their own structures. In this paper, we investigate weak PRFs from two perspectives; attacks, fixes. We first propose direct attacks for an alternative Mod-2/Mod-3 weak PRF and a basic Mod-2/Mod-3 weak PRF when a circulant matrix is used as a secret key. For an alternative Mod-2/Mod-3 weak PRF, we prove that the adversary's advantage is at least 2(-0.105n), where n is the size of the input space of the weak PRF. Similarly, we show that the advantage of our heuristic attack on the weak PRF with a circulant matrix key is larger than 2(-0.21n), which is contrary to the previous expectation that 'structured secret key' does not affect the security of a weak PRF. Thus, for an optimistic parameter choice n = 2 lambda for the security parameter lambda, parameters should be increased to preserve lambda-bit security when an adversary obtains exponentially many samples. Next, we suggest a simple method for repairing two weak PRFs affected by our attack. Moreover, we provide the first direct algorithm for a basic Mod-2/Mod-3 weak PRF with a random secret key even though it does not capture the current parameters. | - |
dc.language | 영어 | - |
dc.publisher | Kluwer Academic Publishers | - |
dc.title | Adventures in crypto dark matter: attacks, fixes and analysis for weak pseudorandom functions | - |
dc.type | Article | - |
dc.identifier.doi | 10.1007/s10623-022-01071-x | - |
dc.citation.journaltitle | Designs, Codes, and Cryptography | - |
dc.identifier.wosid | 000815560400001 | - |
dc.identifier.scopusid | 2-s2.0-85132824523 | - |
dc.citation.endpage | 1760 | - |
dc.citation.number | 8 | - |
dc.citation.startpage | 1735 | - |
dc.citation.volume | 90 | - |
dc.description.isOpenAccess | N | - |
dc.contributor.affiliatedAuthor | Cheon, Jung Hee | - |
dc.type.docType | Article | - |
dc.description.journalClass | 1 | - |
- Appears in Collections:
- Files in This Item:
- There are no files associated with this item.
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.