Generic-Group Barriers for Function-Hiding and Multi-input Functional Encryption
Mohammad Hajiabadi, Roman Langrehr, and Mingyuan Wang
In CRYPTO 2026, Part I, Aug 2026
We show that private-key function-hiding inner-product functional encryption (FH-IPFE) is impossible in the generic group model (GGM). This impossibility extends to (non-compact) two-input quadratic functional encryption (QFE) under a weak security notion that allows only a single key corruption. Our results apply both to the variant where decryption outputs the result directly, and to the variant where the result is encoded in the exponent of a group element.
Our results hold in both Maurer’s and Shoup’s model, with different tradeoffs. In Maurer’s model, we prove that FH-IPFE over Z_q^n cannot be realized even when q^n is polynomially bounded. Here, q denotes the modulus of the inner-product functionality, not the order of the underlying group. This stands in sharp contrast to non-function-hiding FE, which can be constructed from minimal assumptions (one-way functions in the private-key setting and public-key encryption in the public-key setting) whenever the set of functions is polynomially bounded. We extend this impossibility to Shoup’s model when q^n is super-polynomial. Conceptually, our proof simulates any construction in Shoup’s model as one in Maurer’s model equipped with a random oracle.
Our techniques may be of independent interest, offering a general method for upgrading other impossibility results from Maurer’s model to Shoup’s model.
We match these negative results with two positive ones. First, we show that one-sided bounded FH-IPFE (i.e., either the number of key queries or the number of encryption queries is bounded) can be realized from one-way functions. Second, when both the number of key queries and encryption queries are bounded, we show the resulting notion of FH-IPFE can be achieved information-theoretically. These positive results show that our impossibility precisely characterizes the threshold for FH-IPFE.