{"id":"1cf75fff-7dd1-484c-8ffa-db3f7e65ac27","arxiv_id":"1908.09032","paper_version":4,"verdict":"REJECT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A lattice-based pseudorandom function with key and partial-input homomorphism and variable input length is introduced, and it is used to propose a claimed unidirectional updatable encryption scheme.","lead":"This cryptography paper defines a new kind of pseudorandom function that is homomorphic in both the key and part of the input, and uses it to build an updatable encryption scheme claimed to be quantum-safe and one-way. The reason to read it is the promise of cloud key rotation that cannot be undone, a property previous schemes did not achieve.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Eq. (4) in the proof of Theorem 2 is false: binary decomposition is not additive under integer addition, so the homomorphic identity and the UE update formula collapse.","rationale":"The reader's weakest assumption is exactly the load-bearing flaw. The central novelty of the paper is the bi-homomorphic PRF construction, and Theorem 2 is the only place where key plus input homomorphism is proved. Its proof depends on Eq. (4), which asserts linearity of binary decomposition under integer addition. That assertion is false because carries are not represented in componentwise addition of bit vectors. A single leading zero bit does not make the decomposition linear: adding two l-bit values can require a carry chain, and g^{-1}(A_i) + g^{-1}(A_j) is a vector with entries up to 2, not the bit decomposition of A_i + A_j. The concrete q = 8, A_i = 3, A_j = 5 example is decisive. Without Eq. (4), Eq. (3) cannot be derived, so the homomorphic identity that powers the updatable encryption scheme is not established. The unidirectional update formula in Fig. 1 subtracts F'_{\\Delta k}(i, \\Delta N) and relies on the same cancellation; its correctness therefore fails with the same step. The security proof has an additional independent gap: Theorem 4 infers that F_S is a PRF from the fact that its terms are individually PRFs, with coefficients d_1, d_2, d_3 that depend on the input. Sums of correlated PRFs under the same seed are not generally pseudorandom, and the proof gives no hybrid argument or independence justification. This gap would matter even if Eq. (4) were repaired. I credit the paper for defining the KIH/HVL notion and for adapting Banerjee--Peikert's tree construction, but these contributions do not rescue the central theorems as written. Since the reader's rejection is supported and my stress test does not change that verdict, the appropriate output is UNCHANGED.","tokens_in":20751,"tokens_out":8696,"duration_ms":90137,"concrete_test":"Instantiate the construction with a tiny modulus, e.g., q = 8, l = 3, d = 4, and a two-leaf tree. Evaluate both sides of Eq. (4) for A_i = 3 and A_j = 5 to confirm the generic failure. Then, using the recursive definitions of B^S_T and C^S_T from Section 4.3, compute F'_{S_1+S_2}(z_0, z_1) and F_{S_1}(x) + F_{S_2}(y) for random small S_1, S_2 and inputs satisfying x_{lh} = y_{lh} and x_{rh} \\bar{\\oplus} y_{rh} = z_1. If the entrywise difference has any component outside [-1, 1], or does not match Eq. (3), the homomorphism theorem is falsified. Repeating over several random choices removes ambiguity from the algebraic claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 2 hinges on Eq. (4) in Section 4.4: G^{-1}(A_i + A_j) = G^{-1}(A_i) + G^{-1}(A_j) for the binary decomposition defined in Section 4.2. This equality is false under integer addition. Componentwise addition of two bit vectors produces entries 0, 1, and 2, with no carry propagation; binary decomposition of the integer sum requires carries that can ripple through more than one bit position. The extra leading bit in g^{-1} = (0, 1, 2, ..., 2^{l-1}) is fixed to 0, so it cannot absorb such carries. For example, with q = 8, l = 3, and d = 4, g^{-1}(3) + g^{-1}(5) = (0, 2, 1, 1), while g^{-1}(3 + 5) = g^{-1}(8) is either undefined or reduced modulo q to g^{-1}(0) = (0, 0, 0, 0); the two sides are not equal. The proof then uses this false equality to replace G^{-1}(B^{S_1}_T(x_{rh}) + B^{S_2}_T(y_{rh})) by G^{-1}(C^S_T(z_1)) in deriving Eq. (3). Thus the key/input homomorphism claim is not established. The QPC-UE-UU scheme of Section 8 inherits this failure, because its update formula in Fig. 1 relies on the same cancellation. A separate gap appears in Theorem 4, which concludes that F_S is a PRF because it is a sum of PRF terms with input-dependent coefficients d_1, d_2, d_3; a sum of correlated PRFs with input-dependent weights is not generally a PRF. Both the PRF and updatable-encryption claims are therefore unsupported as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a new class of pseudorandom functions called bi-homomorphic PRFs, which are simultaneously fully key homomorphic and partially input homomorphic (KIH), with the input homomorphism inducing a variable input length (HVL). The main construction is an LWE-based family inspired by the Banerjee--Peikert key-homomorphic PRF, and the paper claims this family is a secure PRF (Theorem 4), satisfies an approximate key-and-input homomorphic identity (Theorem 2), and yields the first quantum-safe, post-compromise secure updatable encryption scheme with unidirectional updates (QPC-UE-UU, Section 8). The paper also sketches left/right key-homomorphic constrained PRFs with HVL from the same family and an open problem on searchable encryption.","tokens_in":21161,"tokens_out":5595,"duration_ms":57003,"significance":"If the main claims were correct, the paper would introduce a novel and potentially useful primitive: a lattice-based PRF that is simultaneously key homomorphic and partially input homomorphic with variable output length. The application to unidirectional updatable encryption addresses a recognized open problem, and building it from LWE gives a plausible route to post-quantum security. The definitions are clearly presented, and the proposed use of input homomorphism to refresh nonces during key rotation is conceptually interesting. However, the central derivation rests on an incorrect algebraic claim about the binary decomposition function, and the security proof uses an invalid composition argument. Since these issues affect the correctness of the PRF homomorphism, the PRF security proof, and the updatable encryption update formula, the main results are not established as written.","major_comments":[{"comment":"The claimed linearity G^{-1}(A_i + A_j) = G^{-1}(A_i) + G^{-1}(A_j) is false for the decomposition function defined in Section 4.2. In that definition, g^{-1}(a) outputs a bit vector whose leading entry x' is fixed to 0, and the gadget vector g has first entry 0, so the leading position cannot absorb a carry out of the top bit. Componentwise addition of two bit vectors yields entries 0, 1, or 2 with no carry propagation, while the binary decomposition of the integer sum requires carries. For example, with q = 8, l = 3, and d = 4, one has g^{-1}(3) + g^{-1}(5) = (0, 2, 1, 1), whereas g^{-1}(3 + 5) = g^{-1}(8) is not defined in Z_8 (or, reducing modulo q, equals g^{-1}(0) = (0, 0, 0, 0)); the two sides are not equal. Equation (4) is exactly the step that converts the sum of two evaluations F_{S_1}(x) + F_{S_2}(y) into F'_{S_1+S_2}(z_0, z_1) in the proof of Theorem 2, so the homomorphic identity is unsupported. The updatable encryption scheme in Section 8 inherits this failure because its update formula relies on the same cancellation.","section":"Section 4.4, Eq. (4)"},{"comment":"The proof of Theorem 4 concludes that F_S is a secure PRF because it is written as a sum of terms of the form d_1 * [rounding term 1] + d_2 * [rounding term 2] + d_3 * [rounding term 3] + E, where each individual rounding term is claimed to be a PRF. This does not imply that their sum is a PRF. Pseudorandomness is not closed under addition, especially when the terms share the same seed S and when the coefficients d_1, d_2, d_3 depend on the input length or on x. A valid argument would need a hybrid reduction or an independent-key composition theorem, neither of which is provided. Corollary 4 extends the claim to the family F' without addressing the new C matrices or the extended domain {0, 1, bar-0}^{|T|}, so the security of F' is also not established.","section":"Section 5.2, Theorem 4 proof"},{"comment":"The ciphertext update formula in Fig. 1 is algebraically invalid. The scheme sets Delta N_{e+1} = N_e bar-oplus N_{e+1} and then computes C_{e+1} = C_e - F'_{Delta k}(i, Delta N_{e+1}), and the displayed simplification to F'_{2 k_e - k_{e+1}}(i, N_{e+1}) + m requires both the law N_e - (N_e bar-oplus N_{e+1}) = N_{e+1} and exact cancellation of rounding errors. Subtraction is not defined for the almost-XOR operation, and the asserted law already fails for single bits: 0 - (0 bar-oplus 1) = -1, not 1. Moreover, the almost-homomorphic identity in Theorem 2 holds only up to an error E with ||E||_infty <= 1, and that error is ignored in the update computation, so even a repaired homomorphic identity would not give the exact equality used for decryption. Consequently, the correctness of the update procedure and the unidirectionality proof in Lemma 2 are not supported.","section":"Section 8, Fig. 1 and Lemma 2"}],"minor_comments":[{"comment":"The truth table for the almost-XOR operation omits the entry for 1 bar-oplus 0; commutativity presumably gives 1, but this should be stated explicitly.","section":"Table 1"},{"comment":"The text says that addition inside g^{-1} and G^{-1} is performed as simple integer operations over Z, but the interaction of this convention with the requirement that g^{-1} output {0,1}^d is never formalized; a precise definition of how sums of bit vectors are decomposed would prevent the ambiguity that surrounds Eq. (4).","section":"Section 4.2"},{"comment":"The displayed equation for the decomposition of F_S(x) contains malformed brace-control text ('/bracehtipupleft', '/bracehtipdownright'), which obscures the intended expression and should be fixed.","section":"Section 5.2, Observation 2"},{"comment":"The sentence 'Wlog, we demonstrate left' is incomplete, and the paragraph on achieving HVL presents the left and right cases in a confusingly interleaved way; the exposition should be restructured.","section":"Section 7"},{"comment":"The symbol d is used both for the bit length d = l + 1 in Section 4.2 and for a data block identifier d_i in Section 8.1; this overloading is confusing and should be resolved.","section":"Section 8.1"},{"comment":"The phrase 'as defined in Corollary 4,z' appears to contain a typo ('4,z' instead of '4'), and should be corrected.","section":"Section 8.2"}],"recommendation":"reject","confidential_remarks":"The paper's central claims depend on an algebraic identity that is false, and the error cannot be repaired by a local correction within the present construction: the leading bit of the gadget decomposition is multiplied by a zero gadget entry, so it cannot absorb carries. The security proof also uses a non-standard composition argument. The high-level idea of bi-homomorphic PRFs and the updatable-encryption application is interesting, but the submitted manuscript does not establish the main results. I would recommend rejection; the authors would need a substantially redesigned construction and security proof to address these concerns."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the paper introduces genuinely new definitional machinery and aims at a real open problem, but the central homomorphic identity is false, so both the PRF and the updatable-encryption results are unsupported as written.\n\nWhat is actually new: the KIH/HVL-PRF definitions, the left/right KH-CPRF notion, and the attempt at unidirectional updatable encryption. The construction is a direct extension of the Banerjee-Peikert KH-PRF, which is fine; the paper is transparent about that. The writing is mostly clear, and the UE application is motivated by a real gap in the literature.\n\nThe soft spots are not minor. Theorem 2 depends on Eq. (4), the claim that G^{-1}(A_i+A_j)=G^{-1}(A_i)+G^{-1}(A_j). That is false for the standard binary-decomposition gadget. G^{-1} outputs bit vectors; componentwise addition of two bit vectors can produce a 2 in some coordinate, and carries are not represented in the output. The paper tries to fix this by adding an extra leading zero bit, but that does not absorb carries that can ripple more than one position. So the homomorphic identity is not established, and the proof of Theorem 2 fails at its load-bearing step.\n\nTheorem 4 has a separate problem: it argues that F_S is a PRF because it is a sum of four PRF terms with input-dependent coefficients. A sum of correlated PRFs with input-dependent weights is not generally a PRF; the proof would need a hybrid argument over the sum, not a claim about each summand. That is a real gap in the security argument.\n\nThe QPC-UE-UU scheme inherits these failures. The update formula in Figure 1 relies on the same cancellation, and it also uses an 'almost-XOR' subtraction that is not defined. Lemma 2 is an informal statement, not a reduction, and it does not establish unidirectionality. I don't see a way to patch these locally; the framework would need a genuinely linear decomposition and a proper security proof for the sum.\n\nThat said, the paper is not a waste of time. The definitions are interesting, and if the homomorphism were repaired, the UE idea might work. I would take a look at a revised version if the authors fix the algebra and redo the security reduction.\n\nFor peer review: this deserves a serious referee, because the definitions and the open problem are real. But the current version should be rejected; the central claims do not hold up.","headline":"Interesting new definitions and a real open problem, but the central homomorphic identity is false, so the main results collapse.","tokens_in":21713,"tokens_out":3465,"would_cite":false,"duration_ms":32819,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A60"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper constructs a lattice-based PRF that is homomorphic in both key and part of the input, and uses it to build updatable encryption whose update tokens cannot undo ciphertext updates.","keywords":["bi-homomorphic PRF","key-homomorphic PRF","input-homomorphic PRF","learning with errors","learning with rounding","updatable encryption","unidirectional updates","post-compromise security"],"falsifier":"Take $q=4$, so $l=2$ and $d=3$, with $g=(0,1,2)$. Compute $g^{-1}(1)+g^{-1}(1)=(0,2,0)$ and $g^{-1}(2)=(0,0,1)$; they are unequal, so Equation (4) is false already for the scalar case, and therefore Equation (3) lacks a valid proof. The same test applies entrywise to any matrix pair.","tokens_in":20467,"feed_emoji":"🔐","tokens_out":8101,"duration_ms":76691,"temperature":0.7,"pith_summary":"The paper introduces bi-homomorphic pseudorandom functions: PRFs that remain key-homomorphic and are also homomorphic on a fixed subset of input bits, where the input operation can lengthen the input. It claims a learning-with-errors construction of such a family and proves it pseudorandom under the decision-LWE assumption. The family is then used to build QPC-UE-UU, an updatable encryption scheme with unidirectional updates: tokens can move ciphertexts from one epoch key to the next but cannot be used to move them back. The whole construction hangs on the identity $F'_{S_1+S_2}(z_0,z_1)=F_{S_1}(x)+F_{S_2}(y)+E$ with $\\lVert E\\rVert_\\infty\\le 1$, where the right halves of the inputs are combined by an 'almost XOR' operation.","feed_headline":"Bi-homomorphic PRF makes encrypted updates one-way","feed_subtitle":"A lattice-based PRF that is homomorphic in both key and input lets update tokens move ciphertexts forward only.","key_machinery":"The machinery is a gadget matrix $G=I_n\\otimes g$ with binary decomposition $G^{-1}$ whose output dimension is $d=\\lceil\\log q\\rceil+1$ bits, one more than the usual bit length; the paper claims this extra bit makes $G^{-1}$ additive, $G^{-1}(A_i+A_j)=G^{-1}(A_i)+G^{-1}(A_j)$, by absorbing carries. The recursive tree functions $A_T$, $B^S_T$, and $C^S_T$ build the key and input homomorphism from matrices $A_0,A_1$ and seed $S$, and the 'almost XOR' operation $1\\bar{\\oplus}1=0$, $0\\bar{\\oplus}0=00$, $0\\bar{\\oplus}1=1$ produces the variable input length and the nonce-update token. The identity in the correctness proof is exactly the point where these three ingredients meet.","core_discovery":"On the paper's own terms, the central discovery is a PRF family of the form $F_S(y)=\\lfloor S^T A_T(y_{\\ell h})+R_0(y_{\\ell h})G^{-1}(B^S_T(y_{r h}))\\rceil_p$, with $A_T$ and $B^S_T$ defined recursively over a full binary tree, together with a companion family $F'$ on the larger domain $\\{0,1,\\bar{0}\\}^{|T|}$. The paper claims that these families are decision-LWE-secure PRFs and that they satisfy approximate bi-homomorphism: for inputs sharing a left half $z_0$, the output at summed keys and almost-XORed right halves equals the sum of the two outputs up to a rounding error bounded by 1. This identity is what carries the unidirectional-update property of the updatable encryption scheme.","pith_inferences":["Editorial inference: the additivity of $G^{-1}$ is not a minor technicality; ordinary binary decomposition cannot be made linear over the integers by appending a single bit, because carries can propagate through several positions. Any repair would require a different decomposition, and the security proof would need to be reworked.","If the homomorphic identity fails, the update formula in the proposed scheme no longer produces a ciphertext decryptable under the new epoch key, so the unidirectional-update claim collapses along with it.","The paper's open searchable-encryption idea would test the same identity across multiple servers: the owner combines $t$ PRF outputs and needs the sum to equal the PRF at the combined key and input, so the identical carry problem would reappear there."],"forward_implications":["If the construction is sound, updatable encryption gains a genuinely one-way rotation: a host holding the update token can roll ciphertexts forward, but cannot recover the previous epoch's ciphertext from the current ciphertext and the token.","The PRF's security is claimed under decision-LWE, so the resulting updatable encryption scheme would be quantum-safe in the usual cryptographic sense, unlike prior post-compromise schemes based on discrete-log-style assumptions vulnerable to quantum computers.","The restricted left/right variant would supply the first key-homomorphic constrained PRF with variable input length, enabling delegation of evaluation on one fixed side of the input.","Using fresh random nonces per epoch makes the encryption probabilistic while keeping the underlying PRF deterministic, which is what defeats attacks aimed at reusing old nonces."],"supporting_citations":[{"why":"Supplies the key-homomorphic PRF construction, gadget matrix, tree parameters, and security template that the paper modifies by adding input homomorphism and an extra decomposition bit.","marker":"[7]"},{"why":"Introduces key-homomorphic PRFs and the updatable-encryption framework whose nonce update is replaced here by a fresh random nonce per epoch.","marker":"[13]"},{"why":"Provides the post-compromise security notion for updatable encryption and the observation that prior schemes are bidirectional, which the paper aims to improve.","marker":"[38]"},{"why":"Defines the learning-with-errors problem and its worst-case lattice hardness, the foundation for the PRF security and quantum-safety claims.","marker":"[51]"},{"why":"Introduces learning with rounding and rounding-based PRFs, which justify using the deterministic rounding function in the construction.","marker":"[8]"},{"why":"Introduces key-homomorphic constrained PRFs, the class that the paper extends to left/right HVL-KH-CPRF as a special case.","marker":"[6]"}],"fun_headline_variants":["Lattice PRF enables one-way ciphertext updates","Bi-homomorphic keys and inputs for updatable encryption","PRF with dual homomorphism secures unidirectional updates","LWE-based PRF proves updatable encryption without undo","New PRF family makes ciphertext updates irreversible"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that decomposing the sum of two matrices into bits gives the same result as adding their separate bit decompositions; this is what makes the PRF's homomorphic identity and the encryption update formula go through.","fun_headline_variants_meta":{"raw":{"variants":["Lattice PRF enables one-way ciphertext updates","Bi-homomorphic keys and inputs for updatable encryption","PRF with dual homomorphism secures unidirectional updates","LWE-based PRF proves updatable encryption without undo","New PRF family makes ciphertext updates irreversible"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000616,"raw_usage":{"total_tokens":2974,"prompt_tokens":1171,"completion_tokens":1803,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":787,"completion_tokens_details":{"reasoning_tokens":1725}},"tokens_in":787,"tokens_out":1803,"duration_ms":12288,"temperature":1.0,"reasoning_tokens":1725,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:25:15.697250+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take $q=4$, so $l=2$ and $d=3$, with $g=(0,1,2)$. Compute $g^{-1}(1)+g^{-1}(1)=(0,2,0)$ and $g^{-1}(2)=(0,0,1)$; they are unequal, so Equation (4) is false already for the scalar case, and therefore Equation (3) lacks a valid proof. The same test applies entrywise to any matrix pair.","supporting_citations":[{"cited_title":"New and Improved Key -Homomorphic Pseudorandom Functions","cited_arxiv_id":null,"evidence_quote":"Supplies the key-homomorphic PRF construction, gadget matrix, tree parameters, and security template that the paper modifies by adding input homomorphism and an extra decomposition bit."},{"cited_title":"Key homomorphic PRFs and their applications","cited_arxiv_id":null,"evidence_quote":"Introduces key-homomorphic PRFs and the updatable-encryption framework whose nonce update is replaced here by a fresh random nonce per epoch."},{"cited_title":"Updatable encryption w ith post-compromise security","cited_arxiv_id":null,"evidence_quote":"Provides the post-compromise security notion for updatable encryption and the observation that prior schemes are bidirectional, which the paper aims to improve."},{"cited_title":"On lattices, learning with errors, random li near codes, and cryptography","cited_arxiv_id":null,"evidence_quote":"Defines the learning-with-errors problem and its worst-case lattice hardness, the foundation for the PRF security and quantum-safety claims."},{"cited_title":"Pseudo random functions and lattices","cited_arxiv_id":null,"evidence_quote":"Introduces learning with rounding and rounding-based PRFs, which justify using the deterministic rounding function in the construction."},{"cited_title":"Key-homomorphic cons trained pseudorandom functions","cited_arxiv_id":null,"evidence_quote":"Introduces key-homomorphic constrained PRFs, the class that the paper extends to left/right HVL-KH-CPRF as a special case."}],"review_version":1}