Subgroup Packing for Batched PASTA Transciphering

A packing-dependent cost-noise tradeoff in homomorphic transciphering

Mugurel Barcau; Vicenţiu Paşol; George C. Ţurcaş· 2026· DOI 10.48550/arXiv.2609.12624

The core problem

Transciphering lets a server convert symmetrically encrypted records into homomorphic ciphertexts without learning either the records or the symmetric key. For the PASTA cipher, this conversion requires dense linear maps whose implementation cost depends on how record words are arranged inside the ciphertext. The authors ask a simple but consequential question: can rearranging a fixed batch reduce its conversion cost? Their answer is yes, and the mechanism is a change of packing layout. Instead of storing each record's words in a contiguous block, they interleave records so that cyclic word shifts preserve each record's positions. Those positions form a coset of a cyclic subgroup, hence the name *subgroup packing*. The paper characterizes the displacements needed for direct evaluation as a sum of masked translations and relates their counts—255 for the contiguous layout and 128 for the subgroup layout—to a prior transversal-difference invariant. The work is positioned within the broader taxonomy of Architecture, Cybersecurity, Network, and Cryptography, and it targets the practical cost of batched PASTA-3 conversion followed by public subset-sum queries.

Across twelve paired corpora under six homomorphic keys, all 24 direct and subgroup conversions and all 48 subsequent queries return the expected values and required zeroes. The median paired ratio of direct to subgroup server cost is 1.60, including fresh public generation, conversion, and two queries. In other words, the subgroup layout reduces server cost by roughly 37.5% relative to the contiguous layout on the median paired run. The reduction is consistent across the paired corpora and keys, and it is attributed to the halving of required displacements: 255 for the contiguous layout versus 128 for the subgroup layout. The authors also report that the reduction comes with less remaining noise capacity, establishing a packing-dependent cost–noise tradeoff. The results are summarized in the following flow:The cost model can be written as $C_{\tex

Transciphering lets a server convert symmetrically encrypted records into homomorphic ciphertexts without learning either the records or the symmetric key. For the PASTA cipher, this conversion requires dense linear maps whose implementation cost depends on how record words are arranged inside the ciphertext. The authors ask a simple but consequential question: can rearranging a fixed batch reduce its conversion cost? Their answer is yes, and the mechanism is a change of packing layout. Instead of storing each record's words in a contiguous block, they interleave records so that cyclic word shifts preserve each record's positions. Those positions form a coset of a cyclic subgroup, hence the name *subgroup packing*. The paper characterizes the displacements needed for direct evaluation as a sum of masked translations and relates their counts—255 for the contiguous layout and 128 for the subgroup layout—to a prior transversal-difference invariant. The work is positioned within the broader taxonomy of Architecture, Cybersecurity, Network, and Cryptography, and it targets the practical cost of batched PASTA-3 conversion followed by public subset-sum queries.

The authors implement three equally batched schedules for complete PASTA-3 conversion and subsequent public subset-sum queries in HElib. The experimental design is paired: twelve corpora are evaluated under six homomorphic keys, yielding 24 direct and subgroup conversions and 48 subsequent queries. The direct layout stores each record's words contiguously, while the subgroup layout interleaves records so that cyclic shifts act within a coset of a cyclic subgroup. Formally, if the batch has B records and each record has W words, the contiguous layout places record r at positions {r W, r W + 1, \dots, r W + W - 1}, whereas the subgroup layout places it at a coset g H of a cyclic subgroup H \leq Z_{N} . The conversion is expressed as a sum of masked translations, and the required displacement count is characterized as 255 for the contiguous layout and 128 for the subgroup layout. This count is tied to a prior transversal-difference invariant, which explains why the subgroup layout halves the number of translations. The implementation uses HElib and measures server cost including fresh public generation, conversion, and two queries. The evaluation checks that all conversions and queries return the expected values and required zeroes, and it reports the median paired ratio of direct to subgroup server cost.

The paper's central contribution is the identification and quantification of a packing-dependent cost-noise tradeoff. By interleaving records so that cyclic word shifts preserve each record's positions, the subgroup layout reduces the number of masked translations from 255 to 128. This reduction is not merely an implementation trick; it is grounded in a transversal-difference invariant that characterizes the required displacements. The median paired ratio of 1.60 demonstrates a substantial server-cost saving, but the authors are careful to note that the reduction comes with less remaining noise capacity. This tradeoff matters for practical deployments: a server that needs to perform many queries or deeper circuits may prefer the contiguous layout for its noise headroom, while a server optimizing for throughput on shallow queries may prefer the subgroup layout. The results are validated across twelve paired corpora and six homomorphic keys, with all conversions and queries returning expected values and required zeroes. The work therefore provides a clear, reproducible basis for choosing a packing layout in batched PASTA transciphering, and it opens the question of whether similar subgroup-based packings can be designed for other ciphers or for different homomorphic schemes. The taxonomy candidates—Architecture, Cybersecurity, Network, and Cryptography—reflect the work's relevance to secure computation infrastructure and cryptographic protocol design.

CS practitioners and researchers

Opening member content…