International Association
for Cryptologic Research

Subversion-resilient cryptography has garnered increasing attention in recent years due to growing concerns about cryptographic subversions in real-world applications. Among the existing countermea sures, the notion of cryptographic reverse firewalls (RFs), initially pro posed by Mironov and Stephens-Davidowitz (EUROCRYPT 2015) and later extended by Chakraborty et al. (EUROCRYPT 2022) to the univer sally composable (UC) model, has proven to be a powerful tool for build ing subversion-resilient cryptographic protocols. In this work, we focus on designing subversion-resilient authenticated key exchange (AKE) pro tocols, which are critical components of secure Internet communication. Wepresent the first generic framework for subversion-resilient UC-secure AKE protocols leveraging RFs. Inspired by the state-of-the-art advance ments by Chakraborty et al. (ASIACRYPT 2024), we address subver sions: where a party’s implementation is covertly altered to exfiltrate secrets or behave unpredictably when triggered by adversarial inputs. A key contribution of our work is the introduction of a new AKE function ality which, for the first time, incorporates security against key control, an essential aspect of achieving subversion resilience. We also provide a concrete instantiation of our framework, demonstrating its feasibility in practice. Notably, the RFs in our proposed AKE protocol are transparent, an important property of RF as defined originally, which allows deploy ment of RF without all parties explicitly knowing about it and allows robust security. Achieving transparency for RFs has been widely regarded as challenging, particularly when addressing broader subversion attacks (e.g., input-trigger attacks) in the UC model. Our approach, thus, not only advances the state of AKE protocol design, but also offers insights into building other subversion-resilient protocols in the UC model using transparent RFs.

Order-Revealing Encryption (ORE) provides a practical solution for conducting range queries over encrypted data. Achieving a desirable privacy-efficiency tradeoff in designing ORE schemes has posed a significant challenge. At Asiacrypt 2018, Cash et al. proposed Parameter-hiding ORE (pORE), which specifically targets scenarios where the data distribution shape is known, but the underlying parameters (such as mean and variance) need to be protected. However, existing pORE constructions rely on impractical bilinear maps, limiting their real-world applicability. In this work, we propose an alternative and efficient method for constructing pORE using identification schemes. By leveraging the map-invariance property of identification schemes, we eliminate the need for pairing computations during ciphertext comparison. Specifically, we instantiate our framework with the pairing-free Schnorr identification scheme and demonstrate that our proposed pORE scheme reduces ciphertext size by approximately 31.25\% and improves encryption and comparison efficiency by over two times compared to the current state-of-the-art pORE construction. Our work provides a more efficient alternative to existing pORE constructions and could be viewed as a step towards making pORE a viable choice for practical applications.

In this work, we provide new, tighter proofs for the $T_{RH}$-transformation by Jiang {et al.} (ASIACRYPT 2023), which converts OW-CPA secure PKEs into KEMs with IND-1CCA security, a variant of typical IND-CCA security where only a single decapsulation query is allowed. Such KEMs are efficient and have been shown sufficient for real-world applications by Huguenin-Dumittan and Vaudenay at EUROCRYPT 2022. We reprove Jiang {et al.}'s $T_{RH}$-transformation in both the random oracle model (ROM) and the quantum random oracle model (QROM), for the case where the underlying PKE is rigid deterministic. In both ROM and QROM models, our reductions achieve security loss factors of $\bigO{1}$, significantly improving Jiang {et al.}'s results which have security loss factors of $\bigO{q}$ in the ROM and $\bigO{q^2}$ in the QROM respectively. Notably, central to our tight QROM reduction is a new tool called ``reprogram-after-measure'', which overcomes the reduction loss posed by oracle reprogramming in QROM proofs. This technique may be of independent interest and useful for achieving tight QROM proofs for other post-quantum cryptographic schemes. We remark that our results also improve the reduction tightness of the $T_{H}$-transformation (which also converts PKEs to KEMs) by Huguenin-Dumittan and Vaudenay (EUROCRYPT 2022), as Jiang {et al.} provided a tight reduction from $T_H$-transformation to $T_{RH}$-transformation (ASIACRYPT 2023).

Motivated by the violation of two fundamental assumptions in secure communication - receiver-privacy and sender-freedom - by a certain entity referred to as ``the dictator'', Persiano et al. introduced the concept of Anamorphic Encryption (AME) for public key cryptosystems (EUROCRYPT 2022). Specifically, they presented receiver/sender-AME, directly tailored to scenarios where receiver privacy and sender freedom assumptions are compromised, respectively. In receiver-AME, entities share a double key to communicate in anamorphic fashion, raising concerns about the online distribution of the double key without detection by the dictator. The sender-AME with no shared secret is a potential candidate for key distribution. However, the only such known schemes (i.e., LWE and Dual LWE encryptions) suffer from an intrinsic limitation and cannot achieve reliable distribution. Here, we reformulate the sender-AME, present the notion of $\ell$-sender-AME and formalize the properties of (strong) security and robustness. Robustness refers to guaranteed delivery of duplicate messages to the intended receiver, ensuring that decrypting normal ciphertexts in an anamorphic way or decrypting anamorphic ciphertexts with an incorrect duplicate secret key results in an explicit abort signal. We first present a simple construction for pseudo-random and robust public key encryption that shares the similar idea of public-key stegosystem by von Ahn and Hopper (EUROCRYPT 2004). Then, inspired by Chen et al.'s malicious algorithm-substitution attack (ASA) on key encapsulation mechanisms (KEM) (ASIACRYPT 2020), we give a generic construction for hybrid PKE with special KEM that encompasses well-known schemes, including ElGamal and Cramer-Shoup cryptosystems. The constructions of $\ell$-sender-AME motivate us to explore the relations between AME, ASA on PKE, and public-key stegosystem. The results show that a strongly secure $\ell$-sender-AME is such a strong primitive that implies reformulated receiver-AME, public-key stegosystem, and generalized ASA on PKE. By expanding the scope of sender-anamorphic encryption and establishing its robustness, as well as exploring the connections among existing notions, we advance secure communication protocols under challenging operational conditions.