Roman Langrehr

Public Key Encryption for Broadcast (PKEBC) is a multirecipient encryption primitive that guarantees decryption consistency across all designated recipients. Concretely, if a ciphertext c is encrypted for Bob and Charlie, and Bob’s decryption yields a message m, then Charlie’s decryption of c must also succeed and produce the same m. This property, though seemingly natural, is essential in secure group messaging, where consistent message delivery is often implicitly assumed. However, no efficient constructions of PKEBC currently exist: known approaches achieve consistency through Non-Interactive Zero-Knowledge (NIZK) proofs of generic statements. Not only is the complexity of the NIZK statements already prohibitively expensive, but, in addition, it is not even clear if these can be turned into purely algebraic statements while retaining linear-sized ciphertexts. This is crucial to enable the use of efficient NIZK constructions.

This paper presents new generic PKEBC constructions along with optimized instantiations of each. Concretely, we introduce PKEBCSM and PKEBCFO[mPKE] , and prove the security of these constructions in the standard and random oracle models, respectively.

– PKEBCSM achieves consistency via NIZK proofs. Crucially, we handtuned the NIZK statements of our instantiation to ensure the NIZK is only used to prove very simple and carefully optimized purely algebraic statements.

– PKEBCFO[mPKE] achieves consistency via the Fujisaki-Okamoto (FO) transform (CRYPTO 1999 and Journal of Cryptology 2013) applied to a Multi-Recipient Public Key Encryption scheme (mPKE). Specifically, FO’s ciphertext recomputation during decryption ensures ciphertexts are well-formed, eliminating the need for costly NIZK proofs. We then give two suitable mPKE instantiations: one based on Kurosawa’s mPKE (PKC 2002) and the other from Hash Proof Systems.

For all our schemes and their instantiations, ciphertext sizes and encryption and decryption times grow linearly with the number of receivers. Our constructions therefore enable the first practical group messaging applications with consistency guarantees.

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.

Deniable authentication allows Alice to authenticate a message to Bob, while retaining deniability towards third parties. In particular, not even Bob can convince a third party that Alice authenticated that message. Clearly, in this setting Bob should not be considered trustworthy. Furthermore, deniable authentication is necessary for deniable key exchange, as explicitly desired by Signal and off-the-record (OTR) messaging.

In this work we focus on (publicly verifiable) designated verifier signatures (DVS), which are a widely used primitive to achieve deniable authentication. We propose a definition of deniability against malicious verifiers for DVS. We give a construction that achieves this notion in the random oracle (RO) model. Moreover, we show that our notion is not achievable in the standard model with a concrete attack; thereby giving a non-contrived example of the RO heuristic failing.

All previous protocols that claim to achieve deniable authentication against malicious verifiers (like Signal’s initial handshake protocols X3DH and PQXDH) rely on the Extended Knowledge of Diffie–Hellman (EKDH) assumption. We show that this assumption is broken and that these protocols do not achieve deniability against malicious verifiers.

Non-interactive key exchange (NIKE) schemes like the Diffie-Hellman key exchange are a widespread building block in several cryptographic protocols. Since the Diffie-Hellman key exchange is not post-quantum secure, it is important to investigate post-quantum alternatives.

We analyze the security of the LWE-based NIKE by Ding et al. (ePrint 2012) and Peikert (PQCrypt 2014) in a multi-user setting where the same public key is used to generate shared keys with multiple other users. The Diffie-Hellman key exchange achieves this security notion. The mentioned LWE-based NIKE scheme comes with an inherent correctness error (Guo et al., PKC 2020), and this has significant implications for the multi-user security, necessitating a closer examination.

Single-user security generically implies multi-user security when all users generate their keys honestly for NIKE schemes with negligible correctness error. However, the LWE-based NIKE requires a super-polynomial modulus to achieve a negligible correctness error, which makes the scheme less efficient. We show that
- generically, single-user security does not imply multi-user security when the correctness error is non-negligible, but despite this
- the LWE-based NIKE with polynomial modulus is multi-user secure for honest users when the number of users is fixed in advance. This result takes advantage of the leakage-resilience properties of LWE.

We then turn to a stronger model of multi-user security that allows adversarially generated public keys. For this model, we consider a variant of the LWE-based NIKE where each public key is equipped with a NIZKPoK of the secret key. Adding NIZKPoKs is a standard technique for this stronger model and Hesse et al. (Crypto 2018) showed that this is sufficient to achieve security in the stronger multi-user security model for perfectly correct NIKEs (which the LWE-based NIKE is not). We show that
- for certain parameters that include all parameters with polynomial modulus, the LWE-based NIKE can be efficiently attacked with adversarially generated public keys, despite the use of NIZKPoKs, but
- for suitable parameters (that require a super-polynomial modulus), this security notion is achieved by the LWE-based NIKE with NIZKPoKs.
This stronger security notion has been previously achieved for LWE-based NIKE only in the QROM, while all our results are in the standard model.