.svg)
Advancing Cryptography at Zama: Highlights from ASIACRYPT 2025
In this blog post, we give an informal overview of recent research carried out at Zama. These works led to three papers published at ASIACRYPT 2025, which were presented in Melbourne from December 8 to 12.
Paper #1: Anamorphic Signatures with Dictator and Recipient Unforgeability for Long Messages
Anamorphic cryptography embeds covert message channels into existing cryptographic schemes. A covert channel is one whose very existence is hidden from eavesdroppers, while still allowing communication between authorized parties. This means that eavesdroppers can neither detect nor recover messages sent in a covert channel. In anamorphic cryptography, covert channels remain private and undetectable, even against an adversary that seizes the scheme’s secret keys (e.g. a dictator that forces citizens to hand over their private keys).
Anamorphic signatures enable private communication in a world that completely bans encryption, but still allows authentication via digital signatures. An anamorphic mode for a signature scheme S provides users with a way to produce signatures that have undetectable messages embedded in them. An intuitive way to achieve this would be to embed a secret-key encryption of a covert message inside a random-looking part of the signature. Anyone with knowledge of the symmetric key can then decrypt the random-looking part of the signature to recover the covert message, assuming they know of the existence of a covert message. If the symmetric encryption is random-looking, a dictator won’t be able to detect it, even if the secret signing key is known. However, legitimate users will still know it is there, and be able to use it.
Suppose further that the symmetric key encryption scheme provides authentication.Then, an anamorphic signature is guaranteed to never decrypt a valid covert message unless the signature was produced in anamorphic mode. This property is known as dictator unforgeability. Thus, a dictator suspecting the existence of a covert channel cannot use it to send a message. Another requirement, called recipient unforgeability, captures that a covert recipient cannot forge valid signatures. This decouples the ability to receive covert messages from the usual functionality that the signature scheme provides.
In this ASIACRYPT 2025 paper, we construct anamorphic modes for (generalized) Okamoto-Schnorr, GQ and 2t-th root signatures that achieve both dictator and recipient unforgeability. An important metric related to anamorphic signatures is the ratio between the size of the covert plaintext and the size of the signature. This ratio is called the anamorphic rate. A particular point of improvement is that all of the aforementioned constructions achieve an anamorphic rate close to one. We also provide an anamorphic mode for the post-quantum Lyubashevsky signatures that has a slightly lower anamorphic rate. The paper is available on Springer’s website at https://doi.org/10.1007/978-981-95-5119-4_12.
Although we have only discussed anamorphic signatures above, anamorphic modes for public key encryption and homomorphic encryption have also been constructed. To learn more about our work on these related subjects, see https://ia.cr/2025/328.
Paper #2: Bootstrapping (T)FHE Ciphertexts Via Automorphisms: Closing the Gap Between Binary and Gaussian Keys
Fully homomorphic encryption (FHE) makes it possible to compute directly on encrypted data, allowing sensitive information to remain encrypted from end to end even while complex computations are performed. Since the first FHE scheme was introduced in 2009, the cryptography community has invested tremendous effort into making these schemes faster and more practical.
At the heart of FHE lies an unavoidable trade-off: security of modern FHE schemes relies on adding noise to ciphertexts. As homomorphic operations are applied, this noise gradually increases, and once it exceeds a certain limit, decryption becomes impossible. To address this problem, FHE schemes employ bootstrapping, a procedure that refreshes ciphertexts by homomorphically evaluating the decryption algorithm. In essence, bootstrapping takes a very noisy ciphertext and produces a new one encrypting the same message, but with a much lower noise level. The most efficient bootstrapping techniques today are built around a clever mechanism known as blind rotation.
Several blind rotation methods have been proposed, each with different performance trade-offs. The GINX algorithm keeps the evaluation key material relatively small, but requires the secret key to be binary. The AP algorithm, on the other hand, supports more general secret key distributions, in particular Gaussian-distributed keys, but at the cost of a very large amount of evaluation key material. More recent automorphism-based approaches reduce the overall key material; however, they introduce additional computational overhead, as each automorphism requires a costly key-switching step that increases both runtime and noise.
In this ASIACRYPT 2025 paper, we address these limitations by introducing a new primitive that significantly reduces the cost of automorphism-based bootstrapping. At a high level, our key idea is to merge several operations that were previously performed separately into a single, more efficient one. Concretely, we design a new FHE operation that combines automorphism evaluation, key switching, and the external product at essentially the cost of a single external product, thereby substantially reducing both computation time and noise growth.
Building on this new primitive, we then propose improved blind rotation algorithms that take full advantage of this efficiency gain. Our methods offer flexible trade-offs between key size, performance, and noise growth, and can be tuned to different parameter regimes, including settings with Gaussian secret keys. Experimental results show significant reductions in the number of key-switching operations, leading to noticeable runtime improvements compared to prior state-of-the-art approaches. We also provide a theoretical analysis that explains why these improvements occur, offering deeper insight into the complexity of automorphism-based blind rotation.
The paper is available at https://doi.org/10.1007/978-981-95-5122-4_1, or as an ePrint at https://ia.cr/2025/163.
Paper #3: Accelerating TFHE with Sorted Bootstrapping Techniques
Among today’s most practical fully homomorphic encryption schemes, TFHE stands out for its ability to efficiently evaluate boolean and small-integer circuits. Its performance, however, is still largely dominated by a single operation: bootstrapping. In TFHE, bootstrapping is not just a way to refresh noisy ciphertexts, but also the core mechanism that enables the evaluation of arbitrary univariate functions, a feature commonly referred to as programmable bootstrapping (PBS).
At a high level, PBS performs a modulus switch and a blind rotation of a redundant lookup table (LUT): a rotation of a GLWE ciphertext encrypting the LUT by an amount that remains hidden from the server. Internally, this blind rotation is implemented as a chain of encrypted polynomial products, referred to as external products, that progressively select the correct rotation among all candidates.
In this ASIACRYPT 2025 paper, we build on a bootstrapping variant introduced by Lee and Yoon (PKC 2023) , which splits the polynomial manipulated during blind rotation into several smaller polynomials. This technique, referred to as Extended Bootstrapping (EBS), can speed up the computation thanks to smaller polynomial operations, at the cost of requiring more external products.
We study how the lookup table evolves during blind rotation in EBS and identify structured rotation patterns across the split lookup tables, depending on the rotation value. Based on these patterns, we show that some external products are unnecessary to obtain the correct final result, and therefore can be skipped.
By carefully reordering the blind-rotation steps to maximize the number of removable external products, we obtain a new procedure we call Sorted Bootstrapping (SBS). Thanks to this reduction in external products, PBS latency can be significantly reduced.
To amplify the benefits of SBS, we also revisit the first step of bootstrapping: the modulus switch. Instead of performing a standard rounding, we compute a slightly different (larger) approximation designed to increase the number of positions in the blind rotation that satisfy the conditions required to remove external products.
Experimental results demonstrate substantial performance gains. All experiments were run on AWS using an hpc7.96xlarge instance (AMD EPYC 9R14 @ 3.7 GHz, 192 vCPUs, 768 GiB RAM). Extensive benchmarks, covering message precision from 4 to 9 bits and three target failure probabilities (2-40, 2-64, and 2-128), show that our method achieves speedups ranging from 1.75× to 8.28× over traditional bootstrapping, and from 1.26× to 2.14× over EBS-based bootstrapping techniques.
The paper is available via Springer at https://doi.org/10.1007/978-981-95-5122-4_3, and as an ePrint at https://ia.cr/2025/2214. An open-source implementation is also available at https://github.com/zama-ai/tfhe-rs/tree/artifact_asiacrypt_2025/.
Additional links
.png)
