You are looking at a specific version 20200627:184650 of this paper. See the latest version.

Paper 2020/783

Adventures in Crypto Dark Matter: Attacks, Fixes and Analysis for Weak Pseudorandom Function Candidates

Jung Hee Cheon and Wonhee Cho and Jeong Han Kim and Jiseung Kim

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. (TCC'18) introduced two types of new weak PRF candidates, called a basic Mod-2/Mod-3 and alternative Mod-2/Mod-3 weak PRF. They both use the mixture of linear computations defined on different small moduli to satisfy conceptual simplicity, low complexity (depth-2 ${\sf 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 basic Mod-2/Mod-3 weak PRF is the only candidate that satisfies all above features. However, none of direct attacks which focus on a basic and alternative Mod-2/Mod-3 weak PRFs uses their own structures. In this paper, we investigate weak PRFs in three perspectives; attacks, fixes, and a new analysis to support the hardness conjecture of weak PRFs. 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 input space of weak PRF. Similarly, we show that the advantage of our heuristic attack to the weak PRF with a circulant matrix key is larger than $2^{-0.21n}$, which is contrary to previous expectation that `a structured secret key' does not affect the security of a weak PRF. Thus, for 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 provide a simple method for repairing two weak PRFs affected by our attack while preserving the depth-2 ${\sf ACC^0}$ circuit complexity and parameters. Moreover, we provide an observation and a new analysis to support the exponential hardness conjecture of a basic Mod-2/Mod-3 weak PRF when a secret key is uniformly sampled from $\{0,1\}^{m \times n}$.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Cryptanalysisweak PRF
Contact author(s)
wony0404 @ snu ac kr,jiseungkim @ kias re kr
History
2021-05-04: last of 5 revisions
2020-06-27: received
See all versions
Short URL
https://ia.cr/2020/783
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.