PaperlayerView exact revision on arXiv

Source-linked AI summary

Homomorphic Encryption with Coset Code Construction

Haodong Yang, Venkata Gandikota

arXiv:2610.31437v1cs.ITcs.CRmath.IT

TL;DR

This paper addresses how to carry multiple message symbols in code-based homomorphic encryption while supporting public arithmetic on ciphertexts. It uses coset-based vector messages and compatible code spaces; security is conditional, and rank tests identify parameter choices where the required assumption can fail.

  • Problem

    Code-based homomorphic encryption faces a representation trade-off: packing message symbols must be considered alongside the code structure used for public computation and security.

    Source: §I · pp. 1–2

  • Method

    The construction uses coset codes for vector messages and compatible code spaces to support public addition and multiplication.

    Source: §IX · p. 27

  • Results

    Under the IID-DSCP assumption, the scheme has conditional bounded chosen-plaintext security, but rank tests show that public product results invalidate this assumption for certain parameters.

    Source: 2) Proof of the product-rank restriction · p. 21, §IX · p. 27

  • Takeaways & Limitations

    For a fixed field and ciphertext-vector length, packing reduces the number of vectors required to transmit and process a record.

    Source: §IX · p. 27

    Concrete secure instantiations have not yet been developed.

    Source: §IX · p. 28

Abstract

from arXiv · show

Homomorphic encryption enables computation on input data without decrypting it. This paper extends a construction based on scalar message codes, utilizing coset codes to pack $k$ message symbols into a ciphertext vector of length $n$. For a given field and vector length, this packing method reduces the number of ciphertext vectors required to transmit a message record. A compatible family of evaluation codes supports public addition and multiplication operations up to a predetermined degree. We prove that the scheme achieves bounded chosen-plaintext security under the coordinate-label distinguishability assumption.

I. INTRODUCTION

Homomorphic encryption lets a computing party evaluate supported operations without the decryption key, while code-based schemes use algebraic code structure to enable encrypted computation. This paper extends a scalar-message construction to coset-packed vector messages and states the organization of its construction, security analysis, results, and proofs.

I. INTRODUCTION

A. Our Contributions

  • The scheme extends Armknecht et al.’s scalar construction to coset-based vector messages, packing multiple symbols into one ciphertext while requiring code parameters for comparable security.For a three-symbol sensor record, the example uses one evaluation vector instead of three at a common field and ciphertext-vector length.Source: §I · p. 2, A. Our Contributions · p. 2
  • A compatible sequence of code spaces supports public addition and multiplication while preserving the message space and ciphertext-vector length.The paper establishes recovery and operation-preservation conditions, with the receiver solving one code-space recovery problem for all packed symbols.Source: A. Our Contributions · p. 2
  • Bounded chosen-plaintext security is reduced to a coordinate-label distinguishing assumption, and rank tests rule out that assumption for some parameter choices.The sample budget, message dimension, and supported computation degree must be assessed together.Source: A. Our Contributions · p. 2

B. Organization of the Paper

  • The paper proceeds from construction and assumptions to results and comparisons, then to proofs and detailed constructions.Its sections cover prior work, the scheme idea, notation, algorithms, security, results, proofs, and conclusion.Source: B. Organization of the Paper · pp. 2–3

III. THE IDEA OF THE ENCRYPTION SCHEME

The scheme represents a message vector by a coset, encrypts a randomized representative with errors outside secret good positions, and recovers the message from those positions. Public coordinatewise operations produce derived ciphertexts, with multiplication requiring compatible output codes and recovery conditions.

III. THE IDEA OF THE ENCRYPTION SCHEME

  • A coset jointly represents multiple message symbols: distinct codewords in that coset carry the same message vector.Errors are introduced outside the good positions, which the receiver uses to identify the message coset and recover the vector.Source: §III · p. 4, A. Message and Mask Subspaces · p. 5

A. Message and Mask Subspaces

  • The message subspace supplies canonical representatives, while the mask subspace supplies alternate representatives without changing the represented message.The sender and receiver share the message basis, mask bases, and fixed good-position set under a key.Source: A. Message and Mask Subspaces · p. 5

B. Encryption and Message Recovery

  • Encryption adds an independently sampled mask and error to the message representative; the receiver uses good positions to recover its coset, not the original randomized codeword.The receiver rejects if no clean codeword matches the received information at those positions.Source: B. Encryption and Message Recovery · p. 5

C. Homomorphic Computation

  • Public addition and multiplication operate on ciphertext vectors, but multiplication requires compatible message cosets and a recoverable product code.The construction tracks formal degree with a public level label and specifies a maximum supported degree; derived outputs do not add fresh encryption randomness.Source: Figure 1 · p. 6, C. Homomorphic Computation · p. 6

IV. NOTATION AND PRELIMINARIES

The preliminaries set up finite-field linear codes, quotient cosets, and evaluation codes whose products describe how code spaces change under computation. They define message encoding and extraction and introduce exponent-set conditions used in the Reed–Solomon construction.

A. Codes, Cosets, and Encoding

  • A coset code partitions a linear code into classes modulo a subcode, with a complementary message subspace giving each coset a unique representative.The representative specifies k message symbols, while adding a mask-subcode element preserves the represented message.Source: A. Codes, Cosets, and Encoding · pp. 6–7
  • Coordinatewise products of codewords need not remain in the original code, so product codes formalize the spaces needed for multiplication.Evaluation-code products correspond to products of their function spaces, but message-multiplication compatibility remains an additional requirement.Source: A. Codes, Cosets, and Encoding · p. 7
  • The canonical encoder maps message coordinates to codewords, and coset encoding identifies all representatives that extract to the same message.The extraction map has the mask subcode as its kernel and inverts coset encoding on the quotient.Source: A. Codes, Cosets, and Encoding · pp. 7–8
  • The Reed–Solomon construction uses D-average-free exponent sets to separate pure powers from mixed products.The defining condition applies to integer exponents, with repeated summands allowed.Source: A. Codes, Cosets, and Encoding · p. 8

B. Recovery and Public Computation

Recovery depends on whether the good coordinates distinguish message cosets, while public computation requires a compatible sequence of message codes. Computation levels track formal degree, and the fresh-sample budget separately limits independently randomized encryptions.

B. Recovery and Public Computation

  • The message is recoverable from good positions exactly when codewords supported only on erased positions do not differ across message cosets.This recovers the message without requiring reconstruction of the original codeword; the stronger distance bound permits full codeword recovery.Source: B. Recovery and Public Computation · p. 8
  • Compatible code spaces keep message maps consistent across levels and ensure mask products cannot change the output message.Multiplication errors remain confined to the bad positions, supporting public multiplication under the stated conditions.Source: B. Recovery and Public Computation · p. 9
  • Addition raises the level to the larger input level, while multiplication adds input levels and is allowed only up to degree ∆.The level bounds formal degree, not circuit depth; L separately limits fresh encryptions, and derived evaluations need not be distributed like fresh ciphertexts.Source: B. Recovery and Public Computation · p. 9

V. THE ENCRYPTION SCHEME

The scheme is specified over sampler-generated compatible instances, and its security framework formalizes a bounded coordinate-label distinguishing problem as the required hardness assumption.

V. THE ENCRYPTION SCHEME

  • The scheme assumes a sampled compatible instance and specifies setup, encryption, decryption, addition, and multiplication, with level labels attached to ciphertexts.Source: A. Description and… · p. 9

A. Description and Encryption/Decryption Algorithms

  • Setup builds nested masking spaces from a basis for the largest space, while the shared secret key determines the code spaces and message maps.Source: A. Description and… · pp. 9–10
  • Fresh encryption uses independent randomness; decryption restricts to good positions and recovers the unique message component from a solvable system.Source: A. Description and… · p. 10
  • Addition combines vectors and takes the maximum input level, while multiplication is coordinatewise and is rejected when the summed levels exceed ∆.Source: A. Description and… · p. 10
  • Public evaluation uses neither decryption nor re-encryption; L bounds fresh-encryption exposure, and evaluated outputs add no fresh randomness.Source: A. Description and… · p. 10

A. Decisional Synchronized Codewords Problem with Independent Errors

B. Encryption and Sample-Distinguishing Experiments

The results establish correctness and conditional bounded encryption security, then identify parameter regimes where products of zero encryptions undermine the required hardness assumption.

B. Encryption and Sample-Distinguishing Experiments

  • The bounded chosen-plaintext experiment allows at most L fresh ciphertexts and has no decryption oracle, while public computations remain available to the adversary.Source: B. Encryption and… · pp. 11–12
  • The sample experiment compares the joint view of L zero encryptions and auxiliary information with a view of L independent uniform vectors.Source: B. Encryption and… · p. 12

A. Correctness and Conditional Security

B. A Restriction on the Security Assumption

C. Compatible Code Families

The section presents compatible binary Reed–Muller and Reed–Solomon code towers, then compares message packing and storage under explicit conventions.

1) Binary Reed–Muller codes:

  • A compatible binary Reed–Muller tower carries k message bits at every level, with exact distance exposing a tradeoff between message dimension and computation degree.The construction and proof are in Section VIII-C.Source: 1) Binary Reed–Muller codes · p. 13

2) Reed–Solomon subcodes:

  • A compatible Reed–Solomon subcode tower carries k message symbols at every level, with a lower bound on distance between distinct message cosets.Its attainable message dimension depends on available average-free sets, and the theorem does not establish the IID-DSCP assumption for this family.Source: 2) Reed–Solomon subcodes · p. 14

D. Message Packing and Comparison

  • At common field and ciphertext length n, packing four symbols cuts payload from 4n to n field elements, a 75% reduction.The comparison assumes both representations support the operation being counted and excludes level labels and other metadata.Source: D. Message Packing and Comparison · pp. 14–15, Table II · p. 15
  • For supported componentwise addition or multiplication, one packed-vector operation replaces four scalar operations, but packed coordinates do not support arbitrary cross-coordinate operations.Source: D. Message Packing and Comparison · p. 15
  • The scalar construction’s reported n-bit key omits supports x and y; the full direct-storage counts are explicit-storage choices, not minimum key lengths.Source: D. Message Packing and Comparison · p. 16
  • The storage comparison does not establish a matched-security advantage; security assessment requires concrete setup, sample-budget, degree, and attack analysis.Source: D. Message Packing and Comparison · p. 16

VIII. PROOFS

The proofs establish unique recovery from the good coordinates and preserve message operations under the compatible code spaces. They then reduce bounded chosen-plaintext security to the coordinate-label assumption, subject to that assumption holding for the selected setup.

A. Recovery and Correctness

  • Recovery is possible exactly when C ∩ EB ⊆ K; otherwise the same received vector can encode distinct messages.For valid ciphertexts, restricting to good coordinates removes errors, and the recovery condition makes all compatible codewords represent the same message.Source: A. Recovery and Correctness · p. 16
  • Addition preserves validity at the maximum input level, while multiplication preserves it at the summed level when r + s ≤ ∆.For multiplication, the clean product represents m ⊙ m′ and the remaining error lies in EB; induction extends correctness across circuit gates.Source: A. Recovery and Correctness · p. 16

B. Security Proofs

1) Reduction to the coordinate-label problem:

  • The sample-to-coordinate reduction relates advantages by αS,L(D) = 2TδS,L(B), using a one-call fair-coin construction.The reduction preserves bad-coordinate distributions because errors there are independent and uniform.Source: 1) Reduction to the coordinate-label… · pp. 18–19
  • Under Assumption 1, the combined reductions imply bounded IND-CPA security, including against adversaries performing public evaluations.The guarantee is conditional: the proof does not establish IID-DSCP hardness for particular code families or parameter choices.Source: 1) Reduction to the coordinate-label… · p. 19

2) Proof of the product-rank restriction:

The product-rank restriction turns publicly derived products of zero encryptions into a real-versus-uniform sample test. Its usefulness depends on the parameters and does not itself establish an IND-CPA attack or certify security when the test is inconclusive.

2) Proof of the product-rank restriction:

  • Correctness confines supported products of zero encryptions to Z∆, whose dimension is at most n − k; thus n − k + 1 such vectors must be linearly dependent.An observer can test this dependence by rank without recovering a basis for the secret spaces or positions.Source: 2) Proof of the product-rank restriction · pp. 19–20
  • For uniform inputs, the determinant bound gives rank deficiency probability at most M∆/q, yielding a real-versus-uniform acceptance gap of at least the stated bound.The determinant of the first M rows is a nonzero polynomial of degree at most M∆; Lemma 3 converts the gap into coordinate-label advantage.Source: 2) Proof of the product-rank restriction · p. 20
  • With n = 10, k = 2, ∆ = 2, L = 3, and q = 101, the rank test has real-versus-uniform sample-distinguishing advantage at least 83/101 ≈ 0.822.Real samples always give rank below nine, while the uniform-input rank-deficiency probability is bounded by 18/101; these are illustrative, not proposed secure parameters.Source: 2) Proof of the product-rank restriction · pp. 20–21
  • Public multiplication supplies derived columns from few fresh samples, but those columns are dependent functions of the inputs, not independent encryptions.The proof accounts for this dependence when bounding rank deficiency under uniform inputs.Source: 2) Proof of the product-rank restriction · pp. 19, 21
  • A nonnegligible rank-test gap can invalidate the sufficient hardness premise, but the test alone is not an IND-CPA attack; an inconclusive bound does not establish security.L, k, ∆, and q must be assessed together, and a concrete claim still requires a justified code family and setup distribution.Source: 2) Proof of the product-rank restriction · pp. 20–21

C. Proof of Theorem 2: the RM Construction

The proof constructs a binary family extending the RM coset construction in [16, Sec. VI-A], with message coefficients and masks assigned to different polynomial degrees.

C. Proof of Theorem 2: the RM Construction

1) Boolean Monomials and the Compatible Tower:

The binary construction uses multilinear monomials to encode messages and masks in a nested code tower. Its message maps remain consistent under multiplication, while the code spaces support recovery from bounded errors.

Boolean monomials

  • A unique multilinear representative lets the construction define message and mask spaces from evaluated monomials over F2^m.On Boolean evaluation points, positive powers reduce to first powers; the evaluated squarefree monomials form a basis.Source: 1) Boolean Monomials and the… · pp. 21–22

Message maps

  • The same selected evaluation coordinates recover degree-r message coefficients at every level, making the clean encoding systematic in those coordinates.The message map is linear and surjective, with kernel Kℓ, and restricts to the inverse encoder on C1.Source: 1) Boolean Monomials and the… · pp. 22–23

Compatible multiplication

  • Products of codewords at levels a and b lie in level a+b and preserve the product message, including for masked representatives.Mask monomials have degree greater than r, so they cannot contribute to the degree-r message terms.Source: 1) Boolean Monomials and the… · p. 23

Distance and recovery

  • For each level ℓ, every nonzero polynomial of degree at most 2ℓr has evaluation weight at least 2^m−2ℓr, and the construction attains that bound with a nonzero message.Choosing disjoint S and J of sizes r and 2ℓr−r yields a codeword of weight 2^m−2ℓr.Source: 1) Boolean Monomials and the… · p. 23
  • When the terminal distance exceeds the number of error positions, no nonzero codeword is supported inside the error set, so the compatibility conditions give message recovery.The passage states b < d∆ ≤ dℓ and applies the recovery lemma at every level.Source: 1) Boolean Monomials and the… · p. 23

Worked example

  • In the m=5, r=1, ∆=2 example, multiplying the evaluation vectors assigns the product to level two while quadratic terms remain masks.The output message map returns the intended product of the two messages despite those mask terms.Source: 1) Boolean Monomials and the… · p. 24

2) Parameters and a Three-Level Example:

For fixed m and supported degree ∆, choosing r determines both packed message dimension and terminal distance. The three-level example demonstrates the trade-off and separates correctness from confidentiality.

Parameter trade-off

  • At fixed m, increasing r raises message dimension but lowers terminal distance, and increasing ∆ likewise lowers distance.For a target distance d0, the passage gives the sufficient condition 2∆r ≤ m−⌈log2 d0⌉ and notes that arbitrary (k,d∆) pairs need not be achievable.Source: 2) Parameters and a Three-Level Example · p. 24

Three-level example

  • With m=8, r=1, and ∆=3, one length-256 binary ciphertext carries k=8 message bits and all three levels recover from any 253 good positions.The remaining three positions are fewer than the terminal distance of four.Source: 2) Parameters and a Three-Level Example · pp. 24–25

Security boundary

  • The example parameters do not satisfy the security assumption: when evaluation ordering is public, a majority of eight unit-point entries distinguishes challenge messages with success probability one.The passage does not establish the same attack when encoding and evaluation ordering are hidden.Source: 2) Parameters and a Three-Level Example · p. 25

D. Proof of Theorem 3: the RS Construction

The Reed–Solomon construction uses translated exponent sets and average-freeness to separate message products from mixed terms. The resulting nested codes preserve message products and meet stated recovery bounds, though the construction does not claim optimality.

1) Exponent Separation and the Nested Codes:

  • Average-freeness prevents mixed exponent sums from colliding with pure message-product exponents, including products with repeated summands.Translation separates sums with different numbers of terms, which ordinary 3-AP-freeness alone does not ensure.Source: 1) Exponent Separation and the Nested… · p. 25, D. Proof of Theorem 3: the RS… · p. 25
  • The translated sum-length intervals are disjoint, so exponents identify their sum length; injective evaluation then yields nested code spaces with consistent coefficient-based message maps.The construction gives C1 ⊆ C2=C(1) ⊆ … ⊆ C(∆), with C(ℓ)=C1⊕Kℓ.Source: 1) Exponent Separation and the Nested… · pp. 25–26
  • For r+s≤∆, products from levels r and s lie in level r+s and their mapped message is the coordinatewise message product, even with kernel components.A mixed summand list cannot represent a pure exponent under average-freeness.Source: 1) Exponent Separation and the Nested… · p. 26
  • The root bound gives distance bounds for each level, and T>D2N good positions ensure recovery because no nonzero polynomial in the largest space vanishes on all of them.The passage applies these bounds to differences of representatives from distinct message cosets as well.Source: 1) Exponent Separation and the Nested… · p. 26
  • The theorem does not claim optimal average-free order or distance bounds; supporting degree-∆ computations on fresh masked inputs may require up to 2∆ canonical factors.The passage notes that one public multiplication of two fresh ciphertexts requires ∆≥2 and uses D≥4 in this construction.Source: 1) Exponent Separation and the Nested… · p. 26

2) Parameter Choices and a Three-Level Example:

The parameter choices trade message dimension against supported computation degree and recovery distance; the conclusion presents packing alongside conditional security, while noting that concrete secure instantiations remain undeveloped.

2) Parameter Choices and a Three-Level Example:

  • Selecting a D-average-free set of at least k elements in [N] yields k message symbols and terminal distance at least d0, while d0 is a guaranteed bound, not an exact instance distance.The clean-code dimension is rℓ; k is the message-quotient dimension.Source: 2) Parameter Choices and a Three-Level… · p. 26
  • At fixed length and target distance, increasing the supported degree may reduce the achievable message-symbol count because it strengthens the average-free requirement and raises the evaluation-degree budget.The stated bounds are sufficient parameter choices for Theorem 3.Source: 2) Parameter Choices and a Three-Level… · p. 26, Table V · p. 27
  • With ∆ = 3, n = 80, and k = 2, the example uses three computation levels; all levels retain the same length and message count while code and kernel dimensions grow and guaranteed distance decreases.The example’s T = 73 good positions permit recovery at every level while seven coordinates may contain arbitrary errors.Source: 2) Parameter Choices and a Three-Level… · p. 27, Table VI · p. 27
  • The displayed evaluation points and exponents do not give a secure instantiation: an outsider can recover the fresh polynomial despite seven errors and apply the message map.Revealing G1 also reveals K1 in the tower, so average-freeness establishes product compatibility but not the hardness assumption.Source: 2) Parameter Choices and a Three-Level… · p. 27, §IX · p. 27

IX. CONCLUSION

  • The conclusion’s framework packs message-symbol vectors into one ciphertext and supports public coordinate-wise addition and multiplication up to a predetermined formal degree.Binary Reed-Muller and average-free Reed-Solomon constructions establish the algebraic properties and illustrate trade-offs among message dimension, computation, and recovery distance.Source: §IX · p. 27
  • The scheme’s bounded chosen-plaintext security is conditional on IID-DSCP, and product results can invalidate that assumption for some parameter choices.The fresh-sample budget and supported operations must be assessed jointly.Source: §IX · p. 27
  • Concrete secure instantiations have not yet been developed, so the code families and sampling distributions still require evaluation against structural and sample-based attacks.The paper also calls for comparing packing benefits at equivalent security levels.Source: §IX · p. 28
Loading 2610.31437v1…