Pith. sign in

REVIEW 4 major objections 4 minor 16 references

A symmetric LWE-based Multi-Recipient Cryptosystem

T0 review · 4 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper claims that a single LWE-based broadcast ciphertext can deliver distinct messages to multiple recipients without letting any recipient read another's data.

desk verdict A plausible symmetric LWE broadcast construction undone by a receiver-isolation theorem whose residual LWE dimension can shrink to 1, plus off-by-one loop bugs. read the letter →

arxiv 2506.05711 v1 pith:PCAPSQZ3 submitted 2025-06-06 cs.CR

Saikat Gope , Srinivasan Krishnaswamy , Chayan Bhawal This is my paper
classification cs.CR MSC 94A60
keywords LWEproblempseudorandommapmulti-recipientcryptosystemsymmetricencryptionpost-quantumcryptographyIND-CPAsecuritybroadcastciphertext
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proposes a symmetric multi-recipient encryption scheme built on the Learning With Errors problem. One sender encrypts $m$ different message streams for $m$ recipients into a single broadcast ciphertext, and each recipient uses her own secret key to recover her stream with a small added noise term. The central claim is that the whole ciphertext is pseudorandom under the LWE assumption, which gives IND-CPA security, and that even a coalition of recipients who know several keys cannot extract the remaining messages. The scheme targets error-tolerant data such as images and audio, where small per-symbol noise is harmless.

What carries the argument

The load-bearing object is the LWE-based pseudorandom map $f_\chi(S, v) = S v + E \pmod q$, where the rows of $S$ are the recipients' secret keys, $v$ is a public vector, and $E$ is a small discrete-Gaussian error. Encryption chains this map through the message columns by $v_i = m_i + f_\chi(S, v_{i-1})$, starting from a random initial vector $v_0$, so each ciphertext block is a fresh LWE sample masking one message column. Decryption subtracts the recipient's own inner product $\langle s_j, v_{i-1}\rangle$, leaving the intended message plus the noise term. The security argument is a hybrid proof that swaps the pseudorandom-map outputs for genuine uniform samples block by block, so the entire ciphertext becomes indistinguishable from random.

What would settle it

Set $m=2$ and let one recipient collude, knowing the other key's last entry; with a few known plaintext-ciphertext pairs, the coalition obtains noisy one-dimensional equations in the remaining key entry, and averaging or standard lattice reduction recovers it. Success in that experiment would show the residual $\mathrm{LWE}_{1,q,\chi}$ problem used by Theorem 3 is easy and the coalition can read the other recipient's message.

Watch

Extended reading notes

Core claim

The scheme's core claim is stated in Theorem 2: under the $\mathrm{LWE}_{m,q,\chi}$ assumption, encryptions of two distinct $m$-tuples of messages are computationally indistinguishable from each other and from uniform random data, so an adversary with encryption-oracle access cannot win the IND-CPA game. Theorem 3 extends this to the multi-recipient setting: an adversary who knows $k$ of the $m$ secret keys, plus the last $k$ entries of the remaining keys, still cannot distinguish the first $m-k$ rows of a fresh ciphertext from random, under the $\mathrm{LWE}_{m-k,q,\chi}$ assumption. Taken together, the paper claims that the broadcast ciphertext leaks nothing about the messages, and that no recipient or coalition of recipients can read messages intended for others.

Load-bearing premise

The claim that a coalition of recipients cannot read the remaining messages depends on the leftover part of the key system being hard to solve once some keys are known; if the coalition is large enough that almost nothing stays unknown, that hardness disappears and the claimed protection does not follow.

Editorial extensions

If this is right

  • A single broadcast ciphertext serves any number of recipients, so the bandwidth cost of multi-recipient communication is essentially one stream plus the initial vector.
  • Encryption and decryption are only repeated matrix-vector products; the paper demonstrates the speed by encrypting roughly 260 MB of image data in about four seconds on a commodity workstation.
  • The scheme offers a post-quantum multi-recipient option because its security rests on LWE rather than on factoring or discrete logarithms.
  • The scheme is appropriate only for noise-tolerant data, since each recipient's recovered stream carries the Gaussian error introduced during encryption.
  • If Theorem 3 is correct, a recipient cannot extract other recipients' messages even after colluding with other key holders, as long as the residual LWE dimension stays large.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Extrapolating from Theorem 3, the coalition guarantee fades as the number of colluding recipients grows: when $k = m-1$, the residual problem is LWE in dimension $1$, where known plaintext-ciphertext pairs make the last unknown key entry recoverable; the paper does not discuss this boundary.
  • The recursive map acts like a mode of operation, so pairing it with an error-correcting code would extend the scheme to exact data such as text, at the cost of some overhead.
  • The same construction could plausibly be instantiated with Ring-LWE, replacing the $m$-dimensional matrix-vector products with polynomial arithmetic to shrink keys and ciphertexts; this is an extension the paper does not explore.
  • A quantitative noise measurement would be a useful next step: the paper shows decrypted images but does not report the empirical error rate or signal-to-noise ratio at the proposed parameters.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The manuscript proposes a symmetric multi-recipient encryption scheme (MKMR) in which a single sender encrypts m message streams under m independent secret keys and broadcasts one ciphertext. Each recipient decrypts one message stream with her own key and, the paper claims, cannot learn information about other recipients' messages. The security argument proceeds through an LWE-based pseudorandom map, a hybrid argument for ciphertext pseudorandomness (Lemma 2 and Theorem 2), and a receiver-isolation theorem (Theorem 3) that considers adversaries who know some keys. The paper also reports an image-encryption demonstration with m=1024 and q=2^31-1.

Significance. The problem is relevant: compact multi-recipient encryption with post-quantum security is a natural design goal, and the proposed construction is simple and computationally light. The paper has two genuine strengths: it reduces the main IND-CPA claim to the external LWE assumption with no fitted parameters or circular normalization choices, and it includes a concrete implementation example on images. If the security claims were correct, the scheme would be a useful contribution to lightweight multi-recipient symmetric encryption. However, the central receiver-isolation theorem is false as stated, and the encryption/decryption algorithms contain an off-by-one loop error, so the paper's core claims are not currently supported.

major comments (4)
  1. [Section III-C, Theorem 3] Theorem 3 is false as stated for coalitions close to the full receiver set. The theorem claims security under the LWE_{m-k,q,χ} assumption for any k, but when k=m-1 the residual dimension is 1, and LWE_{1,q,χ} is easy whenever χ has small noise, as required for the decryption procedure. Concretely, the oracle in assumption (iv) evaluates f(v)=S1 v + ε with S1 a 1×1 entry s11; an adversary queries v=1 repeatedly, recovers s11 by averaging or median estimation, and then uses the ciphertext and the known S2 to compute v_{i,1} - S2 v_{i-1,bottom} - s11 v_{i-1,1} = m_{i,1} + e_i, which leaks the first recipient's message up to small noise. Thus the receiver-isolation premise is not merely unproven; it is violated in exactly the parameter regime the paper recommends for its image application.
  2. [Section III-B, Algorithms 1 and 2] Algorithm 1 has an off-by-one error: the loop runs while i < l, so it computes v_1 through v_{l-1}, but the ciphertext is declared as C = [v0 v1 ... v_l], leaving v_l undefined and the last message column m_l unencrypted. Similarly, Algorithm 2 loops while i < l and recovers only m_{j1} through m_{j,l-1}, omitting the last message block. The recurrence in Eq. (13) and the decryption formula in Eq. (14) both require i to range over 1,...,l. This is a correctness bug that affects the stated message length and the example.
  3. [Definition 7 and Lemma 1] The pseudorandom-map security notion in Definition 7 is not a well-defined oracle model. Equation (5) compares A(f(s,.)) with A(U(F_q^m)), but it is not specified whether A receives a single output of the map or oracle access to it; Theorem 1 uses the map on multiple inputs, so a one-output definition is insufficient. In addition, the proof of Lemma 1 in the appendix is only a sketch: the hybrid experiments over the m noise coordinates do not by themselves constitute a reduction to LWE_{m,q,χ}, and the construction of the adversary A' from a distinguisher is not described. Since Lemma 1 is the bridge from LWE to the scheme's pseudorandomness, this gap is load-bearing.
  4. [Section III-C, Theorem 2 proof] The proof of Theorem 2 does not present a valid reduction. The algorithm A' is said to distinguish the p-tuple (C_1,...,C_p) from random by running the IND-CPA adversary A, but when the input to A' is a random tuple there is no corresponding set of messages (M_1,...,M_p), and the proof does not specify how the challenge bit and challenge ciphertext are generated in that case. A standard hybrid argument from Lemma 2 would establish the claim, but the proof as written is not rigorous.
minor comments (4)
  1. [Section III-C, Lemma 3 proof] In the proof of Lemma 3, P0 is defined using a sample from U(F_q^{m×l}) (Eq. 15), but the ciphertexts C01 and C02 are elements of F_q^{m×(l+1)}; the dimensions should be consistent throughout.
  2. [Section III-C, Lemma 2 proof] The induction in Lemma 2 is misstated: the base case is written as |P_p - P_0| being the advantage, but the subsequent bound is for |P_p - P_{p-1}|, and the claim |P_p - P_{p-i}| ≤ i l ε(m) uses an inconsistent subscript. The argument is repairable but should be rewritten.
  3. [Section II-B, Definition 2] The discrete Gaussian formula is malformed: ρ_σ(v) is written with an expression involving both π and 2πσ^2 in a way that does not match the standard definition exp(-π∥v∥^2/σ^2). Please correct the formula and the surrounding text.
  4. [References] References [5] and [6] appear to be duplicate entries for the same work, and [3] and [4] also overlap; the reference list should be deduplicated.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the security claims reduce to the external LWE assumption and to Peikert-Waters Lemma 6.2, not to the paper's own outputs.

full rationale

The derivation chain is transparently assumption-based rather than self-referential. Lemma 1 states that the map fχ(S,v)=Sv+E is a pseudorandom map under LWE_{m,q,χ}; the paper explicitly identifies this as a special case of Peikert-Waters Lemma 6.2, an external result, and the appendix proof reduces indistinguishability between hybrids to the LWE assumption. Theorem 1 then proves by a standard hybrid argument that recursive composition of any PRM is a PRM, with the hybrids constructed from the PRM oracle itself rather than from the conclusion. Lemma 2 repeats the hybrid argument over p ciphertexts; Lemma 3 and Theorem 2 bound distinguishing advantages by lϵ(m) and plϵ(m), where ϵ is the LWE/PRM advantage. Theorem 3 partitions the secret matrix S and reduces distinguishing the first m−k rows of a ciphertext to LWE_{m−k,q,χ}; this is again a reduction to an external assumption. No fitted parameter is renamed as a prediction, no theorem assumes its own conclusion, and the paper contains no self-citations that carry any load-bearing argument. The appendix proof of Lemma 1 is terse and would benefit from a fully formal adversary construction, but the missing detail is a reduction step, not a circular step. Even the observation that 'LWE-PRM' is essentially a restatement of LWE pseudorandomness does not make the scheme's security circular, because the later hybrid lemmas do substantive composition work. A possible weakness of Theorem 3 when m−k is small would be a soundness or parameter-selection problem, not a circularity problem.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim rests on the LWE hardness assumption, on a nonstandard pseudorandom-map oracle model, and on the unstated condition that decryption noise is small enough for lossy media. No free parameters are fitted to data.

assumptions (4)
  • domain assumption The LWE_{m,q,χ} problem is computationally hard for the chosen parameters.
    All security proofs reduce to the LWE assumption; if LWE is easy, the scheme is insecure. The paper cites Regev and Peikert for this hardness.
  • ad hoc to paper The pseudorandom map security notion in Definition 7 is a meaningful oracle model and the LWE-PRM satisfies it.
    Definition 7 is nonstandard and its advantage equation is not a well-defined game; the security proofs rely on this informal notion.
  • domain assumption The decryption noise e is small enough that recovered messages remain usable for lossy media.
    The scheme only works if the added noise does not corrupt the message alphabet; the paper never specifies the noise width or the resulting error probability.
  • domain assumption LWE hardness holds for the residual dimension m-k after k keys are compromised.
    Theorem 3 reduces receiver-isolation security to LWE_{m-k,q,χ}; this is false when m-k is small, so the assumption is not valid in general.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A symmetric LWE-based Multi-Recipient Cryptosystem." pith.science (2026). https://pith.science/paper/PCAPSQZ3

@misc{pith2026250605711,
  author       = {Pith},
  title        = {Pith review of: A symmetric LWE-based Multi-Recipient Cryptosystem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PCAPSQZ3}},
  note         = {Machine review of arXiv:2506.05711}
}
read the original abstract

This article describes a post-quantum multirecipient symmetric cryptosystem whose security is based on the hardness of the LWE problem. In this scheme a single sender encrypts multiple messages for multiple recipients generating a single ciphertext which is broadcast to the recipients. Each recipient decrypts the ciphertext with her secret key to recover the message intended for her. In this process, the recipient cannot efficiently extract any information about the other messages. This scheme is intended for messages like images and sound that can tolerate a small amount of noise. This article introduces the scheme and establishes its security based on the LWE problem. Further, an example is given to demonstrate the application of this scheme for encrypting multiple images.

Figures

Figures reproduced from arXiv: 2506.05711 by the authors.

Figure 1
Figure 1. A gray-scale image of size (r × c) (on the left) transformed to a message stream of length h (on the right) a uniform distribution over F m q . The window size in this case is taken as 3. Thus each window has 24 bits and is stored as a 32-bit signed integer. During decryption, we first recover the sequence of windows. Each pixel can be recovered from 3 windows. We determine the value of the pixel by considering the … view at source ↗
Figure 2
Figure 2. Simulation plot of Original Images 50 100 150 200 250 Columns of Pixels 50 100 150 200 250 Rows of Pixels Encrypted Images 50 100 150 200 250 Columns of Pixels 50 100 150 200 250 Rows of Pixels 50 100 150 200 250 Columns of Pixels 50 100 150 200 250 Rows of Pixels 50 100 150 200 250 Columns of Pixels 50 100 150 200 250 Rows of Pixels [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Simulation plot of Encrypted Images 50 100 150 200 250 Columns of Pixels 50 100 150 200 250 Rows of Pixels Decrypted Images 100 200 300 400 500 Columns of Pixels 50 100 150 200 250 300 350 Rows of Pixels 100 200 300 Columns of Pixels 50 100 150 200 Rows of Pixels 100 200 300 400 500 Columns of Pixels 100 200 300 400 500 Rows of Pixels [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Simulation plot of Decrypted Images Hm corresponds to the output (v1, v2, . . . , vm) where the error terms are randomly sampled from uniform distribution. Consider a binary algorithm A that accepts elements from F m q and aims to distinguish between experiments H0 and…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

16 extracted references · 15 canonical work pages

  1. [1]

    Public-key encryption in a multi-user setting: Security proofs and improvements,

    M. Bellare, A. Boldyreva, and S. Micali, “Public-key encryption in a multi-user setting: Security proofs and improvements,” in Advances in Cryptology—EUROCRYPT 2000: International Conference on the Theory and Application of Cryptographic Techniques Bruges, Belgium, May 14–18, 2000 Proceedings 19 . Springer, 2000, pp. 259–274

    work page 2000

  2. [2]

    Multi-recipient public-key encryption with shortened ciphertext,

    K. Kurosawa, “Multi-recipient public-key encryption with shortened ciphertext,” in Public Key Cryptography: 5th International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2002 Paris, France, February 12–14, 2002 Proceedings 5 . Springer, 2002, pp. 48–63

    work page 2002

  3. [3]

    Randomness re-use in multi- recipient encryption schemeas,

    M. Bellare, A. Boldyreva, and J. Staddon, “Randomness re-use in multi- recipient encryption schemeas,” in Public Key Cryptography—PKC 2003: 6th International Workshop on Practice and Theory in Public Key Cryptography Miami, FL, USA, January 6–8, 2003 Proceedings 6 . Springer, 2002, pp. 85–99. 9

    work page 2003

  4. [4]

    Multi-recipient encryption schemes: Security notions and ran- domness re-use,

    ——, “Multi-recipient encryption schemes: Security notions and ran- domness re-use,” in PKC, vol. 2003, 2003, pp. 85–99

    work page 2003

  5. [5]

    Multi-recipient encryption schemes: Efficient constructions and their security,

    M. Bellare, A. Boldyreva, K. Kurosawa, and J. Staddon, “Multi-recipient encryption schemes: Efficient constructions and their security,” IEEE Transactions on Information Theory , vol. 53, no. 11, pp. 3927–3943, 2007

    work page 2007

  6. [6]

    Multirecipient encryption schemes: How to save on bandwidth and computation without sacrificing security,

    ——, “Multirecipient encryption schemes: How to save on bandwidth and computation without sacrificing security,” IEEE Transactions on Information Theory, vol. 53, no. 11, pp. 3927–3943, 2007

    work page 2007

  7. [7]

    Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,

    P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,”SIAM review, vol. 41, no. 2, pp. 303–332, 1999

    1999

  8. [8]

    Grover algorithm with zero theoretical failure rate,

    G.-L. Long, “Grover algorithm with zero theoretical failure rate,” Physical Review A , vol. 64, no. 2, pp. 022–307, 2001

    work page 2001

Show all 16 references
  1. [9]

    Hardness of the (approximate) shortest vec- tor problem: A simple proof via Reed-Solomon codes,

    H. Bennett and C. Peikert, “Hardness of the (approximate) shortest vec- tor problem: A simple proof via Reed-Solomon codes,” arXiv preprint arXiv:2202.07736, 2022

    2022 arXiv

  2. [10]

    The shortest vector in a lattice is hard to approximate to within some constant,

    D. Micciancio, “The shortest vector in a lattice is hard to approximate to within some constant,” SIAM journal on Computing , vol. 30, no. 6, pp. 2008–2035, 2001

    2008

  3. [11]

    Public-key cryptosystems from the worst-case shortest vec- tor problem,

    C. Peikert, “Public-key cryptosystems from the worst-case shortest vec- tor problem,” in Proceedings of the forty-first annual ACM symposium on Theory of computing , 2009, pp. 333–342

    2009

  4. [12]

    Sampling methods for shortest vectors, closest vectors and successive minima,

    J. Bl ¨omer and S. Naewe, “Sampling methods for shortest vectors, closest vectors and successive minima,”Theoretical Computer Science, vol. 410, no. 18, pp. 1648–1665, 2009

    2009

  5. [13]

    On lattices, learning with errors, random linear codes, and cryptography,

    O. Regev, “On lattices, learning with errors, random linear codes, and cryptography,” Journal of the ACM (JACM) , vol. 56, no. 6, pp. 1–40, 2009

    2009

  6. [14]

    The learning with errors problem,

    ——, “The learning with errors problem,” Invited survey in CCC, vol. 7, no. 30, p. 11, 2010

    2010

  7. [15]

    Lossy trapdoor functions and their applica- tions,

    C. Peikert and B. Waters, “Lossy trapdoor functions and their applica- tions,” in Proceedings of the fortieth annual ACM symposium on Theory of computing, 2008, pp. 187–196

    2008

  8. [16]

    A tool for fast and secure LWE parameter selection: the FHE case,

    B. Biasioli, E. Kirshanova, C. Marcolla, and S. Rovira, “A tool for fast and secure LWE parameter selection: the FHE case,” Cryptology ePrint Archive, 2024

    2024

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.