## CryptoDB

### Paper: Lossy Algebraic Filters with Short Tags

Authors: Benoît Libert Chen Qian DOI: 10.1007/978-3-030-17253-4_2 Search ePrint Search Google PKC 2019 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
}