Skip to Main content Skip to Navigation
Conference papers

Lossy Algebraic Filters With Short Tags

Benoît Libert 1, 2, 3 Chen Qian 4
1 ARIC - Arithmetic and Computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
4 EMSEC - EMbedded SEcurity and Cryptography
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 $\Theta(n^2)$ group elements for functions with input space $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.
Document type :
Conference papers
Complete list of metadata

Cited literature [46 references]  Display  Hide  Download
Contributor : Benoit Libert <>
Submitted on : Friday, May 10, 2019 - 9:33:09 AM
Last modification on : Thursday, January 7, 2021 - 4:35:10 PM
Long-term archiving on: : Wednesday, October 2, 2019 - 3:27:48 AM


Files produced by the author(s)



Benoît Libert, Chen Qian. Lossy Algebraic Filters With Short Tags. PKC 2019 - 22nd International Conference on Practice and Theory of Public Key Cryptography, Apr 2019, Beijing, China. pp.34--65, ⟨10.1007/978-3-030-17253-4_2⟩. ⟨hal-02124968⟩



Record views


Files downloads