CS Paper Radar

Equivalent Non-linear Shift Register Transformations and Espresso

Anirban Ghatak, Kaushik Sarkar, Anupam Chattopadhyay, Ambrish Awasthi, Indivar Gupta

cs.CR ·submitted 2026-10-18 15:42 UTC · v1
unusual

Abstract

The stream cipher Espresso was designed by E. Dubrova and M. Hell as a hardware-efficient candidate for 5G security. It has two components - a 256-bit binary non-linear feedback shift register (NFSR), with 14 feedback taps, and a 20-variable non-linear output function. However, the security of Espresso with regard to several standard cryptanalytic attacks are estimated using an alternate NFSR, which has only two feedback taps. The above analysis is based on the claim that this alternate NFSR is obtained using a transformation algorithm which preserves the output sequence of the original NFSR. This issue has become all the more significant in the light of recent results on hardware performance evaluations, which assume that the stated equivalence holds. This article presents the first successful attempt in settling the above question of Espresso NFSR equivalence. We arrive at our main result by a careful analysis of existing transformation methods relevant to the question. In doing so, we first identify and correct a critical flaw in the proof of a foundational result of E. Dubrova. Next, in the context of Espresso equivalence, we analyze and unify the transformation framework of Dubrova and the one proposed by Yao and Parampalli. Based on our analysis, we have succeeded in transforming the LFSR in an Espresso-equivalent design reported by Yao and Parampalli to the Espresso alternate NFSR. Further, we have obtained a corresponding non-linear output function which achieves output-equivalence with the LFSR design, and hence, with Espresso.

Closest papers

Nearest neighbours by meaning across the whole index.

A Combined Streaming FPGA Architecture for Client-Side CKKS Encoding and Encryption

cs.CR cs.AR ·2026-10-19 ·Joseph Kurina, Bogdan Pasca, Suleyman Demirsoy, Sunwoong Kim
published similarity 0.57
Abstract · Accepted to the International Conference on Field Programmable Technology (FPT) 2026

Homomorphic encryption allows a computing service to process encrypted data, but the client must first encode and encrypt its inputs. Sharing hardware between floating-point encoding and modular encryption reduces area but requires those transform roles to execute at different times. We present a streaming FPGA architecture for CKKS encoding and encryption that computes the shared floating-point encoding transform once and performs the integer transforms for six residue moduli in parallel. Dedicated transform pipelines exchange intermediate results on chip rather than through off-chip memory. DSP Builder generates the transform RTL, and Altera HLS IP Gen compiler compiles the surrounding SYCL pipeline into IP integrated with DMA and control logic in an accelerator functional unit. At polynomial degree N = 8192, the Altera Agilex 7 implementation delivers 5,143 complete ciphertexts per second at 471 MHz. One SEAL-Embedded CPU worker on the same workstation delivers 113 ciphertexts per second for real-valued inputs using all 4,096 slots. Measurements cover prepared-input computation through complete ciphertext construction, including FPGA submission and output delivery.

0.24

On cryptographically non-linear all-or-nothing transforms

cs.CR ·2026-11-12 ·Anantajeet Devaraj, Navid Nasr Esfahani
unusual similarity 0.54
Abstract

An unconditionally secure $(t, s, v)$-all-or-nothing transform (AONT) is a bijection from $s$ input elements to $s$ output elements over an alphabet of size $v$, such that given any $s - t$ output elements, no information can be obtained about any $t$ input elements. While linear AONTs have been extensively studied, comparatively little is known about the existence of non-linear AONTs. In this paper, we investigate unconditionally secure cryptographically non-linear $(t, s, v)$-AONTs, distinguishing between non-additivity, non-affinity, and cryptographic non-linearity. To achieve this, we first present a computational method for enumerating general AONTs focusing on the case $(t, 3, 3)$-AONTs for $t = 1 and 2$, establishing the existence of non-additive AONTs. We then introduce a general construction of non-additive AONTs from linear ones using coordinate-wise symbol permutations. We measure the non-linearity of the AONT instances generated from this construction, using differential $Δ_F$-uniformity and Walsh magnitude. Finally, we establish theoretical conditions under which $Δ_F$-uniformity is reduced and present statistical results examining the non-linearity of AONTs obtained through our construction.

0.37

Reaction Attack on CKKS Deployments with Asymptotically Optimal Query Complexity

cs.CR ·2026-10-15 ·Song Bian, Hyeongmin Choe, Jiseung Kim, Changmin Lee
top venuetheory similarity 0.54
Abstract · Accepted to the 2027 IEEE Symposium on Security and Privacy

We study a protocol-level reaction leakage in CKKS deployments where public coefficient-to-slot (C2S) evaluation keys are combined with a client's 1-bit validity response. Under this deployment surface, a malicious evaluator can recover a ternary secret key using asymptotically optimal $O(H)$ reaction queries, where $H$ is the entropy of the secret key. The attack does not break RLWE or CKKS IND-CPA security. Instead, it exploits the interaction between client-side validity reactions and public homomorphic linear transformations. A shift of a public encryption key yields a ciphertext whose plaintext is a function of the secret key; the public ${\sf C2S}$ layer then repacks this information to construct a ciphertext whose validity depends strictly on whether a targeted secret coefficient matches a guessed value. Furthermore, each submitted query is independently randomized with a fresh encryption of zero, so that each resulting malicious ciphertext appears entirely distinct, thereby allowing the attack to simply evade trivial detection mechanisms on the client side. We implemented the full end-to-end attack in Lattigo v6.2.0 and recovered the full secret key across four parameter sets drawn from standard CKKS presets. For uniform ternary secrets, the attack uses $O(N)$ queries and is within a factor $2/\log_2 3 < 2$ of the oracle-only entropy lower bound. For sparse ternary secrets, a tailored variant further reduces the number of queries in practice. Our results show that observable validity reactions form a practical key-recovery channel in CKKS deployments exposing this surface, even when the underlying cryptographic assumptions remain intact.

0.36

Verified DRAM Address Mapping Reverse Engineering with Threshold Sweep

cs.AR ·2026-10-21 ·Hewen Zhang, Ian G. Harris
published similarity 0.53
Abstract · 4 pages. Accepted at DFTS 2026

We propose an end-to-end software pipeline for solving and validating DRAM address mapping functions on embedded LPDDR5 systems, and we instantiate it on embedded platforms. Starting from a large latency dataset of address pairs, the pipeline first builds a latency histogram and then performs a threshold sweep to obtain candidate same-bank address pairs. For each threshold, we apply a Knock-Knock-style linear-constraint solver to recover candidate bank masks. Final bank masks are calculated using GF(2) reduced row echelon form (RREF). To verify correctness, we implement two verification stages, group verification and single function verification, inspired by prior work. Group verification checks whether bank partitions induced by the recovered masks agree with observed timing behavior. Single function verification removes one addressing function at a time and measures the resulting change in verification pass rate. Unlike approaches that return only a single inferred mapping, our workflow systematically records, for each candidate threshold, the solved bank masks and validation metrics. This pipeline supports more robust selection of bank masks on ARM-based embedded devices and provides an efficient method for reverse engineering DRAM address mapping functions and subsequent Rowhammer analysis.

0.39

How to break the Miranda signature scheme over matrix Gabidulin codes

cs.CR ·2026-09-25 ·Adrien Vinçotte
similarity 0.52
Abstract · 21 pages, 3 tables, 2 algorithms

The Miranda signature scheme relies on masking a matrix code which disposes of a masked underlying structure, and the knowledge of which allows for efficient error decoding. We consider a Gabidulin code which is expanded into a matrix code, that is only \Fq-linear. An additional masking is then applied to it. The attack proposed here shares similarities with that of [Le26, https://arxiv.org/abs/2608.03328] on the EGMC encryption scheme, which also follows the paradigm described above. It consists in recovering the Fqm-linear structure of a masked matrix Gabidulin code by reducing to a MinRank instance to be solved over the extension field Fqm, but where the matrices have coefficients in Fq. Such an instance can be efficiently solved. However, unlike the previous attack, it is possible to reduce in polynomial time to such a MinRank instance in the case of the Miranda signature scheme. This results in a particularly efficient key recovery attack against the parameters proposed for Miranda. For example, for the proposed parameter set with m=79, the complexity drops from 146 bits to 46 bits in this attack.

0.31

Optimizing Polynomial Multiplication and Fixed-Weight Sampling for HQC on ARM Cortex-M4

cs.AR cs.CR ·2026-08-10 ·Jihoon Jang, Hanbeom Shin, Suhri Kim, Seokhie Hong, Donggeun Kwon
published similarity 0.52
Abstract · 22 pages, 1 figure, 11 tables

In this paper, we present an optimized implementation of Hamming Quasi-Cyclic (HQC) on the ARM Cortex-M4. We optimize (i) the polynomial multiplication and (ii) the support expansion in fixed-weight sampling, and (iii) propose an optional caching strategy that reuses the public transforms and hash recomputed under a fixed key. For the polynomial multiplication, the fixed-constant multiplications in the Frobenius additive FFT (FAFFT) butterfly spend nearly half of their instructions on VMOV data movements between general-purpose and floating-point registers rather than arithmetic. Because minimizing the XOR count alone can increase the total instruction count, we propose a dirty-aware register-allocation policy and an XOR-operation reordering that reduce the VMOV count by up to 48.1% while leaving the XOR count unchanged. We apply these to a multiplication that combines prior FAFFT-CRT methods, and for HQC-1 we further find a 34% sparser FAFFT modulus that lowers the CRT reconstruction cost. For fixed-weight sampling, we rewrite the support expansion with predicated execution and 4-way unrolling, lowering the per-word cost of its inner loop from 22 to 6 cycles while remaining constant-time. On the NUCLEO-L4R5ZI board, our implementation reduces key generation, encapsulation, and decapsulation by up to 33.1%, 34.6%, and 29.8% over the faster of the two prior state-of-the-art implementations, and the optional caching yields a further reduction of up to 32.7% and 18.9% for encapsulation and decapsulation.

0.28

Batch, Pack, and Prove: More Efficient Verifiable Computation for CKKS

cs.CR ·2026-11-12 ·Ignacio Cascudo, Anamaria Costache, Daniele Cozzo, Dario Fiore, Antonio Guimarães +1 more
publishedhot direction similarity 0.52
Abstract · Full version of a paper accepted at ASIACRYPT 2026. 92 pages

An important challenge in homomorphic encryption (HE) is ensuring the integrity of the encrypted computations. Although verifiable computation can address this in theory, making it practical is far from trivial. [Cascudo et al. CRYPTO 2025] recently proposed a solution to this problem for the CKKS scheme. In particular, they propose new succinct arguments that efficiently prove arithmetic circuits and range checks over the ring $R_q = \mathbb{Z}_q[Y]/(Y^N+1)$, and combine them to prove computations on CKKS ciphertexts. Despite the important progress, their work faces scalability challenges: the size of the polynomial commitment proofs, a large $O(N)$ overhead in range proofs, and the lack of an explicit method for efficient -- sublinear in circuit size -- verification. In this paper we present new techniques that remove all these bottlenecks. First, we provide a more efficient arithmetization of CKKS computations. Second, we introduce BatchFold, a new polynomial commitment for $R_q$ that supports batched evaluations and achieves shorter proofs. Third, we design packing, a novel algebraic technique that eliminates the need to commit to massive polynomials and removes the $O(N)$ overhead in range proofs. Finally, we introduce SparsePack, an efficient protocol for proving the evaluations of sparse, circuit-dependent polynomials, leveraging both packing and batched evaluations. We evaluate the efficiency of our solution on a generic neural network architecture, achieving proofs several orders of magnitude smaller and faster than prior approaches.

0.70

TUTTI: Parallel CKKS Bootstrapping in under 3 ms on CPU

cs.CR ·2026-11-09 ·Robin Köstler, Antonio Guimarães
similarity 0.52
Abstract

This paper introduces TUTTI, a new CKKS bootstrapping procedure that outperforms previous low-latency solutions in multi-threaded latency for any number of messages and, most notably, has a lower latency than TFHE when bootstrapping a single one. Our bootstrapping builds upon SPRU (CK, TCHES 2027), improving it with new methods for exploiting parallelism and increasing the number of messages, as well as with a refined security analysis, of independent interest, of the block-binary secret keys of LMSS (AsiaCCS 2023). TUTTI bootstraps 4096 real-number messages in 46 to 83.4 ms on 192 threads to restore 1 to 9 multiplicative levels, outperforming SHIP (CHKS, Eurocrypt 2025) by a factor of up to 3 on the same machine. Unlike SHIP, TUTTI gains immediately from bootstrapping fewer messages, with a 256-message bootstrapping taking just 15 to 34 ms on 32 threads. For a single message, TUTTI takes 4.6 ms on 32 threads, whereas TFHE-rs needs 7.3 ms for a 4-bit bootstrapping on the same machine and thread count. We show that this advantage persists across different architectures: on an Apple M5 Pro laptop (ARM), TUTTI takes 2.4 ms on 14 threads, against 4.5 ms for TFHE-rs. Differences between CKKS and lightweight schemes such as TFHE remain on several fronts, from functionality to key sizes and security assumptions, but our work shows that multi-threaded latency is no longer one of them, closing a long-standing gap in the practical FHE literature.

0.45