Welcome to the resource topic for 2017/808
Title:
On the Untapped Potential of Encoding Predicates by Arithmetic Circuits and Their Applications
Authors: Shuichi Katsumata
Abstract:Predicates are used in cryptography as a fundamental tool to control the disclosure of secrets. However, how to embed a particular predicate into a cryptographic primitive is usually not given much attention. In this work, we formalize the idea of encoding predicates as arithmetic circuits and observe that choosing the right encoding of a predicate may lead to an improvement in many aspects such as the efficiency of a scheme or the required hardness assumption. In particular, we develop two predicate encoding schemes with different properties and construct cryptographic primitives that benefit from these: verifiable random functions (VRFs) and predicate encryption (PE) schemes. - We propose two VRFs on bilinear maps. Both of our schemes are secure under a non-interactive Q-type assumption where Q is only poly-logarithmic in the security parameter, and they achieve either a poly-logarithmic verification key size or proof size. This is a significant improvement over prior works, where all previous schemes either require a strong hardness assumption or a large verification key and proof size. - We propose a lattice-based PE scheme for the class of \emph{multi-dimensional equality} (MultEq) predicates. This class of predicate is expressive enough to capture many of the appealing applications that motivates PE schemes. Our scheme achieves the best in terms of the required approximation factor for LWE (we only require \poly(\lambda)) and the decryption time. In particular, all existing PE schemes that support the class of MultEq predicates either require a subexponential LWE assumption or an exponential decryption time (in the dimension of the MultEq predicates).
ePrint: https://eprint.iacr.org/2017/808
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .