International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Lossy Algebraic Filters with Short Tags

Benoît Libert
Chen Qian
DOI: 10.1007/978-3-030-17253-4_2
Search ePrint
Search Google
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.
  title={Lossy Algebraic Filters with Short Tags},
  booktitle={Public-Key Cryptography – PKC 2019},
  series={Lecture Notes in Computer Science},
  author={Benoît Libert and Chen Qian},