Coset-code packing reduces ciphertext count for homomorphic encryption
The claim
The proposed scheme achieves bounded chosen-plaintext security using coset codes
Published as: “Homomorphic Encryption with Coset Code Construction”
So what
Packing cuts communication and storage overhead for homomorphic encryption, but practical security guarantees remain conditional and unvalidated for concrete parameter sets.
The five-minute version
The paper shows that packing multiple message symbols into a single ciphertext vector cuts the number of ciphertexts needed for a given record, but this alone does not improve security. It proves bounded-chosen-plaintext security under a coordinate-label distinguishability (IID-DSCP) assumption, yet a rank-test attack can break that assumption for some parameter choices. The construction extends the scalar scheme of Armknecht et al. with coset codes and provides compatible code families (Reed-Muller, average-free Reed-Solomon) for addition and multiplication up to a fixed degree. Security remains conditional and concrete secure instantiations are not yet demonstrated.
What they found 4
- Packing reduces the number of fresh ciphertexts required for a fixed number of message symbols.
“Packing reduces the number of fresh ciphertexts required to transmit a fixed number of message symbols, but this representation benefit does not by itself establish stronger security.”
- The scheme supports public coordinate-wise addition and multiplication on packed ciphertexts up to a predetermined formal degree.
“We propose a coset-based encryption framework in which a single ciphertext carries a vector of message symbols and supports public coordinate-wise addition and multiplication operations up to a predetermined formal degree.”
- Security is shown under the IID-DSCP (coordinate-label distinguishability) assumption, yielding conditional bounded chosen-plaintext security.
“Security analysis indicates that, under the established IID-DSCP assumption, the scheme satisfies conditional bounded chosen-plaintext security.”
- A rank-test can invalidate the security assumption for certain parameter choices.
“rank tests reveal that for certain parameter choices, publicly computed product results can invalidate this assumption, even without leaking the secret code space or error location information.”
What undercuts it the paper’s own results
- The rank-test attack shows that for some parameters the IID-DSCP assumption fails, undermining the claimed security.
Stated limits 2
- While specific code family constructions establish the scheme’s correctness, concrete secure instantiations have not yet been developed.
- the ’fresh sample budget’ and ’supported computational operations’ must be evaluated jointly.
What’s new here 4
- Extends scalar homomorphic encryption to vector messages via coset codes, enabling packing of k symbols per ciphertext.
- Defines compatible sequences of evaluation codes that support public addition and multiplication up to a predetermined degree.
- Reduces the number of fresh ciphertexts required for transmitting a fixed number of symbols.
- Provides a security reduction to a new coordinate-label distinguishability assumption.
Artifacts & methods 4
- Coset code construction
- Evaluation code families (Reed-Muller, average-free Reed-Solomon)system
- IID-DSCP security assumptiontheory
- Rank-test attackevaluation