CryptoDB
Lossy Algebraic Filters with Short Tags
| Authors: | |
|---|---|
| Download: | |
| Conference: | PKC 2019 |
| Abstract: | Lossy algebraic filters (LAFs) are function families where each function is parametrized by a tag, which determines if the function is injective or lossy. While initially introduced by Hofheinz (Eurocrypt 2013) as a technical tool to build encryption schemes with key-dependent message chosen-ciphertext (KDM-CCA) security, they also find applications in the design of robustly reusable fuzzy extractors. So far, the only known LAF family requires tags comprised of $$\varTheta (n^2)$$ group elements for functions with input space $$\mathbb {Z}_p^n$$, where p is the group order. In this paper, we describe a new LAF family where the tag size is only linear in n and prove it secure under simple assumptions in asymmetric bilinear groups. Our construction can be used as a drop-in replacement in all applications of the initial LAF system. In particular, it can shorten the ciphertexts of Hofheinz’s KDM-CCA-secure public-key encryption scheme by 19 group elements. It also allows substantial space improvements in a recent fuzzy extractor proposed by Wen and Liu (Asiacrypt 2018). As a second contribution, we show how to modify our scheme so as to prove it (almost) tightly secure, meaning that security reductions are not affected by a concrete security loss proportional to the number of adversarial queries. |
BibTeX
@inproceedings{pkc-2019-29276,
title={Lossy Algebraic Filters with Short Tags},
booktitle={Public-Key Cryptography – PKC 2019},
series={Lecture Notes in Computer Science},
publisher={Springer},
volume={11442},
pages={34-65},
doi={10.1007/978-3-030-17253-4_2},
author={Benoît Libert and Chen Qian},
year=2019
}