security protocol developers

Abstract: We show that a variant of the Wagner/BKW-style algorithm for LWE of Kirchner and Fouque [KF15] solves decision and search LWE with secrets of size $n$ over prime moduli $q=n^{κ+o(1)}$, for any fixed $κ>0$, with errors bounded by $\exp((\ln n)^{o(1)})$, in time $2^{O(n/\ln\ln n)}$ given $n+O(n/\ln\ln n)$ original samples. Further, if each coordinate of the secret is also bounded by $\exp((\ln n)^{o(1)})$, the same time bound holds with errors bounded by $n^{o(1)}$ and only $O(n/\ln\ln q)$ samples. Earlier, it was known that Kirchner and Fouque's algorithm could solve LWE with these parameters in subexponential time with a much larger number of samples $m = Ω(n\log{n})$ [HKM18]. Ducas et al. [DEL25] showed that an adaptation of this algorithm could solve the corresponding dual, the $\mathrm{SIS}^{\infty}$ problem, with a suitable norm bound $q/\operatorname{polylog}(n)$ and $m=n+ω(n/\ln\ln n)$ variables in subexponential time. Whereas their analysis involves interpreting the algorithm in terms of chains of lattices, our approach is quite elementary and is based on bounding the lower moments of a Fourier statistic.

Abstract: The Noisy Linear Equations problem involves finding the solution to a random linear system over a finite field given noisy evaluations. This is a generalisation of various learning problems widely used in cryptography, including Learning with Errors (LWE), Learning with Rounding (LWR), and Learning Parity with Noise (LPN). We present a new sample-preserving search-to-decision reduction for Noisy Linear Equations that has complexity $\mathrm{poly}(n,m,\log q, q/σ)$, where $n$ is the dimension of the secret, $m$ is the number of samples, $q$ is the modulus, and $σ$ is the magnitude of the noise (defined suitably for the kind of noise involved). In particular, this implies search-to-decision reductions for LWE and LWR that run in time $\mathrm{poly}(n)$ even if the modulus $q$ is exponentially large, as long as the noise-to-modulus ratio $σ/q$ is non-negligible. Our reduction works for prime moduli $q$. If $q$ is composite, it instead produces a list that contains a small multiple of the solution. Prior to this work, known search-to-decision reductions for LWE and LWR either did not preserve the parameters of the problem (i.e., $m$, $n$, $σ$, and $q$), or had complexity that scaled polynomially with either $σ$ or the largest prime factor of $q$.

Abstract: Protocol verifiers check whether a protocol meets a security goal under stated trust assumptions, such as that a key is never leaked, a value is fresh, or a channel is authentic. They do not say which of those assumptions the goal needs. Rowe, Guttman and Liskov asked for the weakest assumptions under which a protocol achieves a goal and left the question open. We answer it for assumptions about keys, values and channels. Call a run that violates the goal an attack, and the assumptions that would rule it out its stopping set. The least a protocol must trust to meet a goal is exactly the set of minimal ways to stop all of its minimal attacks. Several such sets may exist. The answer becomes unique once either/or assumptions are allowed, and it is a single set exactly when every minimal attack is stopped by a single assumption. A Galois connection between assumptions and goals explains why: a goal may end in "or", but its hypothesis may not. The same structure gives the trust needed by a conjunction of goals and an exact condition under which composed protocols need no extra trust. To compute the answer, a loop asks a verifier whether a candidate suffices, records what stops each attack it reports, and recomputes the candidates. Deciding whether some trust of at most k assumptions suffices is NP-hard. With a bounded analyser of our own and with CPSA, the loop finds the weakest trust for 18 goals over ten protocols and their variants, and on each it agrees with evaluating every trust using the same verifier. The answers include an assumption that our model of the adopted fix of Kerberos PKINIT states but the client's authentication of the server does not need, and channel assumptions under which Needham-Schroeder meets its goal in a bounded model.

Abstract: We give an algorithm that samples uniformly random linear codes of any hull dimension and type over finite fields of odd characteristic, implying the first algorithm for sampling uniformly random self-orthogonal codes of any rate, including self-dual codes. Our algorithm is a re-visitation of the algorithm given by Albrecht, Benčina and Lai (EC'25), using the mass formulae proven by Li, Shi and Ling (IEEE Trans. Inf. Theory 71(1)). This allows us to instantiate code-based cryptographic schemes that rely on the hardness of Permutation Code Equivalence (PCE) on `random' self-dual codes for security and that were previously unable to sample them. Building on the observation by Bardet, Otmani and Saeed-Taha (ISIT'19) that Euclidean orthogonality is insufficient when considering PCE over finite extension fields due to non-trivial Galois automorphisms, we study the behaviour of what we call total orthogonality, that is orthogonality with respect to all induced Galois geometries simultaneously. We characterise total orthogonality of vectors and codes, and give an algorithm that samples linear codes with a total hull of a prescribed dimension; a subcode that acts as the hull in all Galois geometries of the ambient space. The algorithm incurs a rate decrease by a factor equal to the extension degree, however, we argue why this may be necessary in the context of PCE and explore how it limits the practicality of our algorithm. We consider the notion of Galois type of a linear code when Galois hulls are symmetric and show that all linear codes have constant Hermitian type.

Abstract: For classical--quantum wiretap channels with a transitive covariant input action, both output ensembles admit a description as unitary group orbits of fixed seed states. We use this structure to construct finite-block preprocessing schemes whose private information is an entropy difference evaluated at two distributions related by group convolution. Applying the construction to product groups allows correlations across any fixed number of channel uses. We give a sufficient condition for the associated uniform-input bound to equal the single-use private information. Constant-composition channel codes and universal$_2$ hashing achieve the resulting rates, with trace-distance leakage controlled by sandwiched Rényi information. For uniform outer randomization, the representation structure reduces the comparison-state optimization to Eve's invariant states. For the hybrid binary channel considered by Tikku, Berta and Renes, numerical optimization at three and four uses gives rates above our numerical estimate of the optimized noisy-repetition benchmark wherever that estimate is positive on the tested grid. The improvement comes from noise distributions beyond the family of independent physical flips and a symmetric logical flip. We also prove nonadditivity at an explicit channel parameter using a two-use encoder, an analytic single-use converse, and certified entropy bounds. Finally, we relate the hybrid model to binary phase-shift keying with a fixed receiver measurement.

Abstract: Z-Sigil is a public-key cryptosystem in which the plaintext selects successive keys from a fixed module-lattice family. Messages are length-prefixed, zero-padded and divided into 32-byte blocks. Each public vector is a shared public matrix applied to a small secret vector, plus a small error. Key indices label torsion points of a flat Kähler torus; the secret family forms a section of a key bundle over them. A public nonce initializes a hash state that selects each block's key and bit mask. The sender updates the state with the plaintext block; the receiver does so after recovering it. The stream and nonce determine a discrete walk along which decryption reads the secret section. We specify the algorithms, prove correctness under an explicit noise condition and bound decoding failure for messages chosen after the public key. Under stated decisional Module-LWE assumptions, we establish IND-CPA confidentiality for the chain without modelling the state hash as a random oracle. The reduction covers quantum adversaries under quantum hardness assumptions, with classical keys, messages and ciphertexts; no concrete security level is established. With independent uniform selectors, a restricted direct-decryption model quantifies reduced fragment recovery under partial key exposure, without improving full-message recovery probability over an independent-block baseline. Known-plaintext and candidate-message attacks, and parallel candidate-table decryption, delimit this result. Neither a universal sequential lower bound nor authentication or chosen-ciphertext security is established. Replacing an earlier scalar-exposing proposal, we give an augmented-lattice interpretation, integral-transport obstructions and a noise budget for research on curved, nontrivial bundles. A byte-level specification, pseudocode, test vectors and numerical checks support verification.

Abstract: Large language models offer a promising interface for translating natural-language protocol descriptions into formal security models, but their outputs remain difficult to trust without expert validation. In this paper, we present a human-in-the-loop framework for generating Tamarin-verifiable formal models of security protocols. Our key observation is that the main correctness bottleneck is the semantic accuracy rather than the syntactic validity of the intermediate protocol representation. To address this problem, we introduce a protocol intermediate representation (IR) that serves as a human-auditable semantic checkpoint between natural-language parsing and formal model generation. The IR explicitly captures protocol participants, message flows, value provenance, cryptographic operations, proof targets, and compromise assumptions. We further design an interactive interface that highlights uncertain fields and guides users to inspect the most critical semantic decisions based on model confidence before model generation. Rather than replacing formal-methods experts, our approach uses LLMs to produce auditable semantic drafts while leveraging verification tools to check the resulting formal models. Code and verification artifacts are available at https://github.com/laplace1002/TamarinAgent.git.

Abstract: We determine the exact second-order asymptotics of covert communication over binary-input discrete memoryless channels when covertness is measured by variational distance. Previous work by Tahmasbi and Bloch [IEEE Trans. Inf. Theory, Apr. 2019] characterized the first-order asymptotics and derived achievability and converse bounds on the second-order term, but these bounds do not match. The gap arises from an additional penalty of order \(n^{1/4}\) in the achievability bound. We show that this penalty can be removed through a sharper analysis of the distribution of the warden's output induced by pulse-position modulation. Specifically, we express the variational distance through the Bhattacharyya coefficient of two distributions and the expectation of a continuous function of the log-likelihood ratio. Because the resulting expectation involves a continuous function rather than the probability of a likelihood-ratio event, an analysis of the characteristic function combined with a Gaussian smoothing argument reduces the approximation error from \(O(n^{-1/4})\) (derived from the Berry--Esseen bound in prior work) to \(O(n^{-1/2})\). With this better controlled approximation error, we manage to derive a matching achievability result to the existing converse result, thus establishing the exact second-order asymptotics.

Abstract: This paper investigates the $c$-differential uniformity of power functions over finite fields, an important class of cryptographic functions with favorable differential properties. Specifically, for finite fields $\mathbb{F}_q$ satisfying $q-1=en$ with $e\ge 3$ and $e\mid n$, we prove that there exists $c\in\mathbb{F}_q\setminus\{0,1,ε,\dots,ε^{e-1}\}$, where $ε$ is an $e$-th primitive root of unity in $\mathbb{F}_q^*$, the constructed power functions $f(x)=x^{ln+1}$ with $1\le l\le e-1$ and $\gcd(l,e)=1$ satisfy the upper bound $Δ(f,c)\le e$, provided that certain cyclotomic conditions hold. We show that our conditions are mild; namely, such power functions can be constructed over infinitely many extension fields $\mathbb{F}_q$ of $\mathbb{F}_p$ for any given $e\ge 3$ and prime $p$ with $p\nmid e$. Furthermore, based on the Weil bound for multiplicative character sums, we prove that the obtained upper bound is tight for sufficiently large $q$, demonstrating the optimality of our results. We also analyze the special case $c=-1$ and derive simplified explicit conditions. In particular, we explicitly characterize the admissible parameters for the case $e=3$ and present concrete function examples for practical validation.

Abstract: Let $q=3^n$, where $n>1$ is odd, and let $g:\Fq\to\Fq$ be a perfect nonlinear (PN) function represented by a Dembowski--Ostrom (DO) polynomial. Put $τ=g(1)$, let $ε$ be the indicator of $\Fthree^*$, and, for $c\in\Fq$, define $\widetilde G_c(x):=g(x+c)+τε(x)$. We prove that every $\widetilde G_c$ is APN and has boomerang uniformity either one or two. More precisely, \[ β_{\widetilde G_c}=1 \quad\Longleftrightarrow\quad c\in\mathcal C_g :=\{c\in\Fq\setminus\Fthree:g(c)+τ\notin g(\Fq)\}, \qquad |\mathcal C_g|=\frac{q-3}{2}, \] whereas $β_{\widetilde G_c}=2$ for the remaining $(q+3)/2$ parameters. We determine the common differential spectrum and complete boomerang spectra of all the functions $\widetilde G_c$. Since boomerang uniformity one is the least possible for an APN function over a finite field of odd characteristic, this gives, to the best of our knowledge, the first general construction yielding infinite families of APN functions attaining this optimum. This common differential spectrum rules out CCZ equivalence with every power function and every Ness--Helleseth-type binomial. We also prove that CCZ equivalence between sign-switches of DO PN functions forces EA equivalence between the original PN functions. Using the orders of the nuclei of the associated presemifields, we exhibit, for infinitely many odd $n$, three pairwise CCZ-inequivalent PN functions over $\F_{3^n}$, one from each of the Gold $f_1$, Ding--Yuan $f_3$, and Bierbrauer $f_5$ families. Consequently, over each such field, our construction produces three pairwise CCZ-inequivalent APN functions with boomerang uniformity one. The smallest extension degree obtained in this way is $n=45$.