文章基本信息

标题：On the Inner Product Predicate and a Generalization of Matching Vector Families
本地全文：下载
作者：Balthazar Bauer ; Jevgenijs Vihrovs ; Hoeteck Wee 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2018
卷号：122
页码：1-13
DOI：10.4230/LIPIcs.FSTTCS.2018.41
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Motivated by cryptographic applications such as predicate encryption, we consider the problem of representing an arbitrary predicate as the inner product predicate on two vectors. Concretely, fix a Boolean function P and some modulus q. We are interested in encoding x to x_vector and y to y_vector so that P(x,y) = 1 <=> = 0 mod q, where the vectors should be as short as possible. This problem can also be viewed as a generalization of matching vector families, which corresponds to the equality predicate. Matching vector families have been used in the constructions of Ramsey graphs, private information retrieval (PIR) protocols, and more recently, secret sharing. Our main result is a simple lower bound that allows us to show that known encodings for many predicates considered in the cryptographic literature such as greater than and threshold are essentially optimal for prime modulus q. Using this approach, we also prove lower bounds on encodings for composite q, and then show tight upper bounds for such predicates as greater than, index and disjointness.
关键词：Predicate Encryption; Inner Product Encoding; Matching Vector Families