Leakage-Resilient Inner-Product Functional Encryption in the Bounded-Retrieval Model

Linru Zhang, Xiangning Wang, Yuechen Chen, Siu-Ming Yiu

TL;DR

This paper introduces the first leakage-resilient inner-product functional encryption (IPFE) scheme in the bounded-retrieval model (BRM). This breakthrough allows for secure computation on encrypted data even when an adversary can extract limited information from secret keys, offering enhanced privacy for sensitive data applications.

What Problem Does This Paper Address?

Traditional cryptography often assumes perfect secrecy of secret keys. However, real-world systems are vulnerable to side-channel attacks that can leak partial information from these keys. This leakage can compromise the entire system's security. Leakage-resilient cryptography aims to build systems that remain secure even when such leaks occur.

Functional Encryption (FE) is a powerful cryptographic primitive that allows users to decrypt only specific functions of encrypted data, enhancing privacy. Inner-product functional encryption (IPFE) is a specific type of FE useful for tasks like calculating weighted means while preserving data privacy.

The challenge addressed here is to combine leakage resilience with IPFE in the bounded-retrieval model (BRM). The BRM is a realistic model where an adversary can obtain a bounded amount of information from secret keys, and importantly, the efficiency of the system (except for secret key size) should not depend on this leakage bound. Previous work on leakage-resilient FE was limited in its applicability or efficiency. This paper bridges this gap by providing the first leakage-resilient IPFE scheme specifically designed for the BRM.

Methods

The authors introduce a novel cryptographic primitive called an Inner-Product Hash Proof System (IP-HPS). This is a variant of traditional hash proof systems, but crucially, its decapsulation algorithm outputs an inner-product value instead of a standard encapsulated key. This modification is key to building IPFE.

The core methodology involves:

  1. Defining IP-HPS: They introduce the IP-HPS notion and its required properties, including valid/invalid ciphertext indistinguishability and a new property called "leakage-smoothness." Leakage-smoothness ensures that even with some leakage from secret keys, the system remains statistically close to a perfectly smooth state.
  2. Constructing an IP-HPS: They first build a basic IP-HPS (denoted $\Pi_1$) based on the DDH assumption.
  3. Achieving Leakage-Smoothness: They then extend $\Pi_1$ to construct a leakage-smooth IP-HPS ($\Pi_2$) that can tolerate arbitrarily large leakage bounds by introducing a key-size parameter. This is achieved through a sophisticated construction that leverages properties of universal hashing and a leakage amplification technique.
  4. Building Leakage-Resilient IPFE: Finally, they show how to construct a leakage-resilient IPFE scheme in the BRM from the leakage-smooth IP-HPS ($\Pi_2$). This construction involves a clever way of combining the IP-HPS ciphertext with the actual message.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The IP-HPS Novelty: The introduction of an IP-HPS, where decapsulation yields an inner-product rather than a raw key, is a crucial technical innovation. This directly maps to the functionality of IPFE and simplifies the construction.
  • Leakage-Smoothness as a Bridge: The concept of "leakage-smoothness" for IP-HPS is central. It provides a formal way to reason about how leakage affects the system and allows for the construction of leakage-resilient schemes.
  • BRM Efficiency Requirements: The paper emphasizes meeting the BRM's efficiency constraints, ensuring that only the secret key size grows with the leakage bound, while other parameters remain constant. This is vital for practical usability.
  • Modular Construction: The approach of building from a basic IP-HPS to a leakage-smooth one, and then to the final IPFE, demonstrates a clear and modular design strategy.

Key Results

  • First Leakage-Resilient IPFE in BRM: The paper presents the first leakage-resilient IPFE scheme specifically designed for the bounded-retrieval model.
  • Arbitrary Leakage Tolerance: The proposed scheme can tolerate arbitrarily large leakage bounds by appropriately increasing the size of the secret keys, while keeping other system parameters independent of the leakage bound.
  • Standard Assumption Based: The constructions are based on the well-studied Decisional Diffie-Hellman (DDH) assumption.
  • Formal Security Proofs: The paper provides formal security proofs for its constructions, demonstrating correctness, valid/invalid ciphertext indistinguishability, and leakage-resilience in the BRM.

Limitations and Future Work

  • Efficiency of Secret Keys: While the scheme meets the BRM's efficiency requirements for most parameters, the size of the secret keys does increase with the leakage bound. The paper aims to make this increase manageable.
  • Practicality: While theoretically sound, the practical efficiency of the scheme (e.g., computational overhead, key sizes) for very large leakage bounds would need further evaluation.
  • Future Work: The paper lays the groundwork for further research into leakage-resilient functional encryption for more complex functionalities and in different leakage models. The authors also suggest exploring more efficient constructions and analyzing their performance in real-world scenarios.

Summary updated

Abstract

We propose a leakage-resilient inner-product functional encryption scheme (IPFE) in the bounded-retrieval model (BRM). This is the first leakage-resilient functional encryption scheme in the BRM. In our leakage model, an adversary is allowed to obtain at most $l$-bit knowledge from each secret key. And our scheme can flexibly tolerate arbitrarily leakage bound $l$, by only increasing the size of secret keys, while keeping all other parts small and independent of $l$. Technically, we develop a new notion: Inner-product hash proof system (IP-HPS). IP-HPS is a variant of traditional hash proof systems. Its output of decapsulation is an inner-product value, instead of the encapsulated key. We propose an IP-HPS scheme under DDH-assumption. Then we show how to make an IP-HPS scheme to tolerate $l'$-bit leakage, and we can achieve arbitrary large $l'$ by only increasing the size of secret keys. Finally, we show how to build a leakage-resilient IPFE in the BRM with leakage bound $l=\frac{l'}{n}$ from our IP-HPS scheme.
BibTeX
@article{zhang2020leakage,
  author = {Linru Zhang and Xiangning Wang and Yuechen Chen and Siu-Ming Yiu},
  title = {{Leakage-Resilient Inner-Product Functional Encryption in the Bounded-Retrieval Model}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2020},
}
Figure