Aug 2026· IACR Cryptology ePrint Archive· Vol 2026, pp. 1604· 0 citations· 57 references
Computer Science
TL;DR
A refined algebraic analysis of trace evaluation over power-of-two cyclotomics that uncovers structured cancellation effects among noise coefficients induced by subsequent linear operators, in particular the trace mappings of subextensions is presented.
Abstract
Field trace evaluation has emerged as a powerful tool in fully homomorphic encryption, with broad applications ranging from bootstrapping algorithms to privacy-preserving protocols. Recent advances have significantly reduced its noise growth by combining tower-based evaluation strategies with rescaling operations. However, existing analyses rely on uniform noise bounds that fail to capture the actual noise behavior across different coefficients, leading to substantial gaps between theoretical estimates and empirical observations.
In this work, we present a refined algebraic analysis of trace evaluation over power-of-two cyclotomics that uncovers structured cancellation effects among noise coefficients induced by subsequent linear operators, in particular the trace mappings of subextensions. We show that, except for the constant term, the variance of each output noise coefficient depends on the 2-adic valuation of its index, yielding bounds that improve upon prior uniform estimates by a factor of
O
(
log
n
)
both for non-constant coefficients and after a subsequent plaintext-ciphertext multiplication, where
n
is the ring degree. We further extend our analysis to two typical algorithmic applications of trace evaluation. For ciphertext packing, we derive a non-recursive formulation that admits a cleaner structure and slightly tighter noise estimates. For coefficient extraction, our coefficient-wise analysis improves upon prior uniform variance bounds by factors ranging from
Θ
(
n
)
to
Θ
(
n
2
)
for non-constant coefficients and by a factor of
O
(
n
)
after post-multiplication. Experimental results confirm that the observed noise variances follow the coefficient-wise pattern predicted by our analysis and demonstrate pronounced improvements over existing estimates, providing effective guidance for parameter selection and system configuration in practice.
The compressed permutation oracle has been used to analyze the quantum security of a number of cryptographic constructions which resisted prior techniques. However, these analyses were fundamentally limited by the poor soundness of the method: the technique was proven sound only up to $O(N^{1/12})$ queries to permutati...
A setting in which the adversary uses only the public sampling-and-evaluation oracle available to honest participants, the induced distribution is arbitrary, and the goal is to attack future ciphertexts rather than recover the full algebraic span is studied, yielding a generic impossibility theorem.
This work introduces an operator-norm approach for non-uniform security in the quantum random oracle and random permutation models, and proves an optimal generic salting theorem for decision games.
Minki Hhan, Sunghyuk Jo, Qi-Peng Liu· arXiv.org· 0 citations
The amount of secret key that can be obtained from a quantum key distribution run depends on both the physically observed error rates and the mathematical bounds used to certify security. For finite datasets, conservative bounds force users to discard a substantial fraction of the potentially available key. Here we fur...
M. Tan, Bartosz Regula, Marco Tomamichel· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.