Date de l'exposé : 12 avril 2019
New candidate PRFs and their applications
In this talk, I will present new and simple candidate PRFs
introduced in a recent work. In this work, we depart from the traditional
approaches for building PRFs used in provable security or in applied
cryptography by exploring a new space of plausible PRF candidates. Our
guiding principle is to maximize simplicity while optimizing complexity
measures that are relevant to advanced cryptographic applications. Our
primary focus is on weak PRFs computable by very simple circuits (depth-2
ACC circuits).
The advantage of our approach is twofold. On the theoretical side, the
simplicity of our candidates enables us to draw many natural connections
between their hardness and questions in complexity theory or learning
theory. On the applied side, the piecewise-linear structure of our
candidates lends itself nicely to applications in secure multiparty
computation (MPC). In particular, we construct protocols for distributed
PRF evaluation that achieve better round complexity and/or communication
complexity compared to protocols obtained by combining standard MPC
protocols with practical PRFs (included MPC-friendly ones).
Finally, we introduce a new primitive we call an encoded-input PRF, which
can be viewed as an interpolation between weak PRFs and standard (strong)
PRFs. As we demonstrate, an encoded-input PRF can often be used as a
drop-in replacement for a strong PRF, combining the efficiency benefits of
weak PRFs and the security benefits of strong PRFs. We give a candidate
EI-PRF based on our main weak PRF candidate.
Joint work with Dan Boneh, Yuval Ishai, Amit Sahai, and David J. Wu,
published at TCC 2018