PaperlayerView exact revision on arXiv

Source-linked AI summary

Subgroup Packing for Batched PASTA Transciphering

Mugurel Barcau, Vicenţiu Paşol, George C. Ţurcaş

arXiv:2609.12624v1cs.CR

TL;DR

The paper asks whether rearranging a fixed PASTA batch can lower the cost of transciphering dense word maps. It uses subgroup-aligned interleaving and characterizes direct translation support, then measures a cost reduction alongside reduced noise headroom.

  • Problem

    The paper asks whether rearranging the same number of PASTA records in a ciphertext can make transciphering cheaper, since dense linear-map implementation depends on word placement.

    Source: §1 · p. 2

  • Method

    The study compares equally batched contiguous and subgroup-aligned layouts, characterizing their required direct translation labels and implementing complete PASTA-3 conversion and later queries.

    Source: §1.1 · p. 2, §1.2 · p. 3

  • Results

    The median paired direct/subgroup server-cost ratio is 1.60 across twelve corpora and six HE keys, with all measured conversions and subsequent queries returning expected values and required zeroes.

    Source: §8 · p. 16

  • Takeaways & Limitations

    The results establish a packing-dependent cost–noise tradeoff: subgroup layout reduces this conversion workload’s cost while leaving less query headroom.

    Source: §8 · p. 16

    At 400 bits, direct and subgroup conversions pass but their later queries are refused, locating the difficulty in the margin left after conversion.

    Source: §6.3 · p. 13

Abstract

from arXiv · show

With transciphering, a server converts symmetrically encrypted records into homomorphic ciphertexts without learning the records or the symmetric key. For the PASTA cipher, this conversion involves dense linear maps whose implementation depends on how record words are arranged in the ciphertext. We ask whether rearranging a fixed batch can reduce its conversion cost. Instead of storing each record's words in a contiguous block, our layout interleaves records so that cyclic word shifts preserve each record's positions, which form a coset of a cyclic subgroup. For direct evaluation as a sum of masked translations, we characterize the required displacements and relate their counts, 255 for the contiguous layout and 128 for the subgroup layout, to a prior transversal-difference invariant. We implement three equally batched schedules for complete PASTA-3 conversion and subsequent public subset-sum queries in HElib. 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. The reduction comes with less remaining noise capacity. These results establish a packing-dependent cost--noise tradeoff.

1. Introduction

The paper asks whether rearranging a fixed batch of PASTA records can reduce conversion cost, then connects subgroup-aligned packing to fewer direct translation labels and evaluates complete conversions with later queries.

1.1. Four records, four words.

  • In the four-record example, contiguous block starts need a repair using two row rotations and one public mask product, while BSGS can share repaired rotations across matrix terms.Interleaved placement makes a right rotation by four slots move each record to its preceding word without crossing record positions.Source: §1.1 · p. 2
  • Interleaving places record b, word w at b + 128w, so cyclic word shifts preserve each record’s positions as a coset of a cyclic subgroup.The compared contiguous placement is 128b + w; both layouts batch the same number of states.Source: §1.1 · p. 2

1.2. What the algebra explains, and what we compare.

  • Subgroup packing reduces the required direct translation labels from 255 for contiguous placement to 128, while the result does not lower-bound factored circuits or runtime.The comparison connects counter-dependent matrix evaluation to a transversal-difference invariant for direct sums of masked translations.Source: §1.2 · p. 3
  • The paper’s contribution is an exact direct-matrix interpretation, equally batched PASTA programs with counter-specific coefficients, and a comparison through conversion and later queries.These connect the algebraic criterion to mask-preparation and noise costs that support counts alone do not predict.Source: §1.2 · p. 3
  • The median paired direct/subgroup server-cost ratio is 1.60 across twelve corpora and six HE keys, with all conversions and later queries returning the required values and zeroes.The measured cost includes fresh public generation, conversion, and two queries; subgroup packing leaves less noise margin, and the evidence does not establish faster subsequent queries.Source: §1.2 · p. 3

2. PASTA-3 and Packed Evaluation

This section specifies the PASTA-3 computation and packed evaluation model, then sets out the ownership assumptions and quotient geometry used to analyze word movements.

2.1. The complete computation.

  • PASTA-3 runs four affine/Mix layers, two predecessor-square transformations, and a componentwise cube; transciphering subtracts the computed keystream from the public symmetric ciphertext under HE.The evaluator carries the ciphertext through the complete graph without intermediate decryption or oracle replacement.Source: §2.1 · pp. 3–4

2.2. Data ownership and the server’s view.

  • The server is assumed to follow the circuit while attempting to learn the data; HE does not authenticate malicious computation, and the owner can decrypt any ciphertext it obtains.The setting adds neither multiowner keys nor a verification protocol.Source: §2.2 · p. 4

2.3. Slots, rotations, and matrix schedules.

  • Packed HE performs slotwise arithmetic in parallel, while rotations move values between slots; BSGS shares rotations and partial sums, so diagonal support and scheduled rotation counts differ.A rotation request may use one or more backend key switches, and the paper keeps support, operations, key material, noise capacity, and runtime distinct.Source: §2.3 · p. 4

2.4. The fixed quotient geometry.

  • For contiguous packing, counters index the subgroup H = ⟨128⟩ of C16384 and words use representatives s(w) = w; the transversal-difference invariant is fixed by the pair (G, H).A particular choice of representatives determines its difference set, while translating the whole transversal leaves that set unchanged.Source: §2.4 · p. 5

3. Exact Support of Direct Matrix Evaluation

The section characterizes the exact displacement labels required when a packed word map is evaluated as a direct sum of masked translations. For dense maps, contiguous and subgroup-aligned placements yield different direct supports.

Exact direct form

  • The packed linear map has an exact aggregated masked-translation form, and every required section-difference label is necessary in that form.The result permits a different word matrix on each packed-counter fibre.Source: §3 · pp. 5–6

Density and minimum support

  • Under the stated density condition across fibres, the minimum number of direct aggregated summands is δ(G, H), or δ(G, H) − 1 nonidentity summands.Sparse workloads may use a strict subset of the full difference set.Source: §3 · p. 6

Cyclic placements

  • For n = 128, contiguous placement has 255 dense word-difference labels, while the kernel-axis placement has 128 subgroup labels.The first support is T0 − T0; the second is the order-n subgroup K.Source: §3 · p. 6

Scope of the result

  • The 255-label obstruction applies to changing the section alone; the kernel–section axis transpose changes which logical axis lies on the kernel.The direct-form theorem does not lower-bound a factored circuit’s rotations, products, noise, key material, or runtime.Source: §3 · p. 7

4. Factoring Movements with BSGS

The section factors translation supports into baby and giant steps, reusing baby rotations across shifted masks. It gives explicit covers for full cyclic and contiguous supports, with their role counts characterized for the uniform role-count objective.

Factoring movements with BSGS

  • The identity permits baby rotations to be evaluated once, combined with shifted masks, and then acted on by giant rotations.A cover containing zero in both sets uses |B|−1 nonidentity baby rotations and |J|−1 nonidentity giant rotations.Source: §4 · p. 7

Full cyclic support

  • 21 nonidentity roles suffice for full cyclic support at n = 128, and this is optimal only for the uniform role-count objective.The construction uses B = {0, …, 9} and assigns each of 128 displacements to a baby and giant step.Source: §4 · p. 7

Cost qualification

  • The 21-role cyclic cover need not minimize weighted costs when baby operations, giant operations, or physical key switches have different costs.Role counts are requests, not necessarily distinct evaluation keys.Source: §4 · p. 7

Contiguous support

  • The contiguous signed support has 255 labels and a complete 15 × 17 cover costing 30 nonidentity roles, matching the product lower bound.The cover uses babies −7 through 7 and giants −120 through 120 in steps of 15.Source: §4 · p. 7

5. Three Equally Batched PASTA-3 Implementations

The implementations compare equally batched PASTA-3 layouts from native encrypted inputs to native outputs. They specify affine and nonlinear conversion schedules and a subsequent public subset-sum query over the retained ciphertext.

5. Three Equally Batched PASTA-3 Implementations

  • Both contiguous and subgroup candidates batch 128 records of 128 words, use native inputs and outputs, and encrypt the same repeated key in their state slots.The layouts are 128b + w and b + 128w, respectively.Source: §5 · p. 8

5.1. The affine schedules.

  • The affine schedules use signed masked translations for contiguous placement and subgroup shifts for interleaved placement; subgroup word shifts require no wrap repair.The composed contiguous schedule factors local block rotations but adds wrap-mask multiplications and rotations, so its costs must be measured rather than inferred from support size.Source: §5.1 · p. 8

5.2. Nonlinear layers and returned slots.

  • Each predecessor-square step uses a square, row rotation, plaintext product, and addition, with a mask suppressing the unwanted predecessor at word zero.The two operation orders implement the same PASTA transformation, but need not have equal noise.Source: §5.2 · p. 9

5.3. Consuming a converted batch with a later query.

  • After conversion, each public query copies the retained ciphertext and returns the subset sum only in designated branch-zero slots, with every other slot zero.The query uses seven row rotations, seven additions, and two plaintext products; independent queries do not consume the stored batch’s noise.Source: §5.3 · pp. 9–10

6. Evaluation: Conversion and Later Queries

The evaluation compares equally batched PASTA-3 conversion schedules and subsequent queries under stated measurement boundaries. Subgroup packing lowers recurring server cost, but retains less query noise capacity; direct-ingestion and security comparisons remain limited.

6.1. Experimental setup and measurement boundaries.

  • Twelve paired corpora across six HE keys compare selected width-17 direct and width-11 subgroup schedules under equal batching.Timers include preparation and arithmetic for conversion and queries; reported summaries are descriptive, with six independent HE keys and no failure-probability estimate.Source: §6.1 · pp. 10–11

6.2. Correct conversion and equally batched cost.

  • 1.602 median paired direct/subgroup recurring-cost ratio (36.67 s vs 22.91 s), with all 24 conversions and 48 queries returning expected values and required zeroes.The recurring interval includes fresh public generation, conversion, and two queries; support counts alone do not predict this ratio.Source: §6.2 · pp. 11–12, Table 2 · p. 12

6.3. Capacity and the ability to answer later queries.

  • Direct query capacity ranges from 33–39 bits versus 22–32 bits for subgroup, so the lower-cost subgroup layout retains less headroom.Some answers fall below the 30-bit engineering reserve, which is not a correctness threshold or security level.Source: §6.3 · p. 12
  • The composed width-10 program is refused by HElib’s noise guard in both 400- and 460-bit single-fixture contexts; at 400 bits, both layouts’ later queries are refused.These observations do not establish impossibility for other composed schedules or contiguous packing.Source: §6.3 · pp. 12–13

6.4. Query cost and returned ciphertexts.

  • The two-query median is 0.684 s direct versus 0.708 s subgroup, and returned ciphertexts occupy full-ring sizes despite only 128 permitted answer slots.Decryption and decoding take about 7.2 seconds per answer on this host and are outside the server interval; network transfer and service scheduling are unmeasured.Source: §6.4 · p. 13, Table 4 · p. 13

6.5. Client work, reuse, and direct ingestion.

  • The shallow direct-ingestion baseline fails on its first query, leaving the end-to-end comparison unresolved; native PASTA encryption has a 103.97 ms median.The producer timings do not support a compute advantage over the single shallow-BGV observation.Source: §6.5 · p. 14

6.6. Parameters and security.

  • Conversion security estimates are conditional: minima are 168.60 log-work under MATZOV/BDD and 137.53 under ADPS16/dual-hybrid, with attack coverage incomplete.The proxy does not exactly model ring correlations, polynomial conditioning, or secret-dependent evaluation-key messages; the estimates are not a certificate of 128-bit protocol security.Source: §6.6 · pp. 14–15

7. Related Work

Prior work supplies packing, scheduling, and layout-aware compilation tools; this paper connects counter-dependent matrix evaluation to a transversal-difference invariant and compares complete PASTA conversion with subsequent queries.

7. Related Work

  • HElib’s diagonal, BSGS, and hoisting methods provide basic arithmetic and movement tools; PASTA uses diagonal/BSGS layers and parallel branch rows.Source: §7 · p. 15
  • PASTA’s word-sliced alternative avoids rotations but changes ciphertext organization and packed-output work [DGH+23a, Sections 6.5.2–6.5.3 and Appendix C].Source: §7 · p. 15
  • CHET and Porcupine motivate comparing executable schedules and subsequent computations rather than treating support count as a latency model [DSC+19, CDA+21].CHET records ciphertext layout metadata and delays reshaping, while Porcupine synthesizes vectorized kernels using latency and noise objectives.Source: §7 · p. 15
  • The paper specializes established packing and scheduling tools to complete PASTA conversion and subsequent queries.Source: §7 · p. 15
  • The paper connects counter-dependent matrix evaluation to direct translation support through a transversal-difference invariant [BPT¸26].Peikert and Pepin’s top-down CRT construction uses a transversal to constrain automorphism coefficients by its difference set [PP26].Source: §7 · p. 15

8. Discussion and Conclusion

The subgroup layout lowers the measured cost of the conversion workload relative to the direct layout, while leaving less query headroom. The results establish a packing-dependent cost–noise tradeoff within the tested scope.

8. Discussion and Conclusion

  • 255 direct labels for contiguous placement versus 128 for subgroup placement characterize dense word maps, but rotation counts alone do not determine packing choice.Mask preparation and subsequent computation also matter; composed rotations share work but add masks whose costs propagate through the nonlinear cipher.Source: §8 · p. 16
  • 1.60 was the median paired direct/subgroup server-cost ratio across twelve corpora and six HE keys, including fresh public generation, conversion, and two queries.All 24 conversions and 48 subsequent queries returned the specified values and required zeroes.Source: §8 · p. 16
  • The tested composed schedule was refused by the noise guard in both 400- and 460-bit single-fixture contexts, and the 400-bit context supported neither layout’s converted queries.These observations do not rule out other composed schedules or bound decryption-failure probability; the shallow direct-ingestion baseline’s first-query failure leaves the end-to-end application comparison open.Source: §8 · p. 16
Loading 2609.12624v1…