Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
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 Connect in order to contact the contributor
Submitted on : Friday, May 10, 2019 - 9:33:09 AM
Last modification on : Monday, May 16, 2022 - 4:58:02 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