{"id":"a3080c67-6091-4e1a-9a2e-9377db160826","arxiv_id":"2507.21122","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Kintsugi combines a threshold password-protected function with dynamic secret sharing to enable decentralized, password-based key recovery for end-to-end encrypted data.","lead":"Kintsugi is a new protocol that lets people recover encrypted data after losing a device by getting help from a group of independent computers, using only their password. It is designed to prevent attackers from guessing passwords offline, without requiring expensive special hardware.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Central offline-brute-force claim hinges on unenforced rate-limiting; the paper admits per-IP rate-limiting is botnet-bypassable and per-user rate-limiting enables DoS, so the guarantee is not established without an additional mechanism.","rationale":"The paper's stated contribution is password-based decentralized recovery that resists offline brute-force without HSMs. The cryptographic core in Section 3.1 correctly forces each password guess through an interaction with a live recovery node, so the only barrier to brute-force is the rate-limiting those nodes perform. The paper explicitly delegates this to operators in Section 3.2 and admits, in the Q&A transcript, that both natural policies fail: per-IP rate-limiting is botnet-bypassable, and per-user rate-limiting enables trivial denial-of-service. Hence the central claim rests on an operational property that the protocol does not enforce and that the paper does not solve. This is not a mathematical flaw in the OPRF or secret-sharing construction; it is an unresolved dependency of the headline property. The reader's conditional verdict correctly captures this. The proposed test, a botnet-scale dictionary attack against one honest rate-limiting node, would empirically settle whether the rate-limit can be bypassed; a complementary formal analysis would show whether any rate-limiting policy can simultaneously prevent brute-force and denial-of-service without authentication. Other concerns, such as the prototype's omission of Byzantine agreement and the unproven asynchronous safety of the full design, are real but secondary: they affect availability and robustness rather than the core confidentiality claim addressed here.","tokens_in":12753,"tokens_out":8354,"duration_ms":96527,"concrete_test":"Build a testbed with n=5, t=3, one honest recovery node that rate-limits per IP (for example, one recovery request per second per IP), three compromised nodes that do not rate-limit, and a simulated adversary with B=1000 distinct IPs. Run a dictionary attack: if the attacker can submit roughly 1000 guesses per second and recover the backup key within a bounded time, per-IP rate-limiting is bypassed and the offline-brute-force claim fails. Repeat with per-user rate-limiting: an unauthenticated attacker impersonates the victim to exhaust the user's quota, demonstrating denial-of-service. If both attacks succeed, no proposed rate-limiting policy sustains the paper's security claim without an additional authentication or hardware mechanism.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The headline claim is that Kintsugi protects against offline password guessing without specialized hardware. The threshold OPRF in Section 3.1 ensures that with at most t compromised shares, an adversary cannot try a password offline; each guess requires a response from an additional, uncompromised recovery node. Section 3.2 therefore makes rate-limiting the central dependency: recovery nodes must rate-limit requests to slow online brute-force. The paper itself concedes, in Section 3.2 and the appended Q&A, that per-IP rate-limiting is circumvented by botnets or cloud IP blocks, and that per-user rate-limiting is vulnerable to denial-of-service by impersonating the victim. No protocol mechanism guarantees that even one node in every quorum enforces an effective rate limit; it is an operational assumption outside the protocol. Consequently, the advertised property is conditional on an unsolved operational requirement, not on the protocol design alone. This is not an internal inconsistency, but it is the single most load-bearing assumption behind the central claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"Kintsugi proposes a decentralized end-to-end encrypted key recovery protocol in which the user's recovery key is encrypted under the output of a threshold oblivious pseudorandom function (OPRF). The user's password is hashed to a curve point; secret shares of an OPRF key are distributed among n recovery nodes with reconstruction threshold t. During recovery, the user's new device blinds the password point, sends it to t+1 nodes, receives partial evaluations, and interpolates the OPRF output to decrypt a backup. The protocol uses Shamir secret sharing, a dynamic proactive secret sharing scheme based on Honey Badger for refreshing shares and changing the recovery committee, and a Kademlia DHT for locating recovery nodes. The paper claims offline brute-force resistance without specialized hardware, tolerance of t honest-but-curious colluding nodes and n-t-1 offline nodes, and safe operation under asynchronous network delays. An open-source prototype is provided.","tokens_in":12900,"tokens_out":7696,"duration_ms":87332,"significance":"If the security claims hold, Kintsugi fills a real gap: it offers decentralized key recovery with low-entropy passwords and no HSM requirement, which is relevant for peer-to-peer E2EE applications. The work is grounded in standard, independently established primitives (threshold OPRF, Shamir secret sharing, DPSS) and provides a concrete open-source implementation, a useful comparison table, and a clear statement of the threat model. The paper is honest about several limitations, including the lack of Byzantine fault tolerance and the dependence on rate-limiting. However, the absence of a formal security proof and the unresolved rate-limiting dependency mean the central claims are not yet established at the level expected for a security venue.","major_comments":[{"comment":"The paper provides no formal security definition or proof for the threshold OPRF or the overall key recovery protocol. The informal argument in §3.1 that 'no party can reconstruct s' and that the OPRF output is 'computationally indistinguishable from random' is not sufficient to establish the headline offline-brute-force claim. The protocol adapts the standard OPRF by evaluating Shamir shares in the exponent and interpolating, so a reduction to the discrete-log assumption or to the security of the underlying OPRF should be provided. Without such a proof, the central security assertion rests on heuristic reasoning.","section":"§3.1, §2"},{"comment":"The protocol's resistance to offline brute-force password guessing depends entirely on recovery nodes enforcing effective rate-limiting, but the paper concedes that per-IP rate-limiting is bypassable by botnets or cloud IP blocks and that per-user rate-limiting is vulnerable to denial-of-service. No mechanism in the protocol guarantees that at least one node in every t+1 quorum enforces a rate limit that cannot be circumvented, especially when recovery nodes are end-user devices with no trusted hardware. The headline claim of protecting against offline brute-force without specialized hardware is therefore established only under an operational assumption outside the protocol; the paper should either provide a concrete rate-limiting mechanism with provable bounds or weaken the claim accordingly.","section":"§3.2"},{"comment":"The refresh protocol as described requires each node to broadcast new sub-shares to every other node; a recovery node that is offline during a refresh will not receive its updated share and thus cannot participate in subsequent recoveries. The threat model in §2 claims tolerance of n-t-1 offline nodes, but no mechanism is specified for bringing offline nodes up to date after a refresh or for removing them from the DHT mapping. This gap affects the availability guarantee in the asynchronous setting and should be resolved, for example by specifying a catch-up protocol or by clarifying that offline nodes are permanently removed.","section":"§3.3"},{"comment":"Section 3.2 notes that Kademlia DHT provides no integrity guarantees and dismisses this because the threat model assumes no Byzantine nodes. However, §2 assumes an active network adversary who can interfere with network traffic. Such an adversary can tamper with DHT lookups and replace the recovery-node list for a user, causing denial of service or directing the user to attacker-controlled endpoints. The paper should either include DHT message authentication or integrity, or explicitly exclude DHT tampering from the threat model.","section":"§3.2"}],"minor_comments":[{"comment":"In the first bullet list, 'an threshold Oblivious Pseudo-Random Function' should read 'a threshold Oblivious Pseudo-Random Function'.","section":"§3"},{"comment":"The paper acknowledges that the DHT leaks the identities of each user's recovery nodes; this may be problematic for peer-to-peer settings where recovery nodes are contacts, and the paper should discuss potential mitigations such as encrypted mapping entries.","section":"§3.2"},{"comment":"The description of the 'high-threshold Honey Badger approach' is vague; the paper should clarify which specific components of Honey Badger are used and under what assumptions the simplified DPSS without Byzantine agreement remains correct.","section":"§3.3"},{"comment":"The statement that 'former recovery nodes are expected to cooperate and delete their old shares' is an additional unenforced assumption; since the threat model describes honest-but-curious nodes, the protocol should either enforce deletion or explicitly state that security after node removal depends on deletion.","section":"§3.4"},{"comment":"Figure 1 is referenced in the text but the figure appears in the manuscript only as a caption; ensure the diagram is correctly placed and labeled in the published version.","section":"§3.1"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses a timely and relevant problem and the construction is built from sound standard primitives, but it currently lacks a formal security proof and leaves the rate-limiting dependency unresolved. The DPSS offline-node handling and DHT integrity issues are fixable within the manuscript's scope. I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Kintsugi is a systems paper, not a new primitive. The novelty is the combination: threshold OPRF with dynamic proactive secret sharing, user as dealer, and a DHT for node discovery. It avoids DKG and HSMs, which prior work like Jarecki et al. and Juicebox did not fully manage. That is a real contribution for practical E2EE recovery.\n\nThe paper is well-written and unusually candid. The threat model is explicit, the comparison to existing services is useful, and they ship a prototype. The appended Q&A transcript shows the authors engaged honestly with tough questions. That gives me confidence they understand their own limitations.\n\nThe main soft spot is the rate-limiting dependency. The security guarantee against offline brute-force relies on recovery nodes enforcing rate limits. The paper concedes that per-IP limiting is botnet- and cloud-IP-bypassable, and per-user limiting enables DoS. So the property is conditional on an operational mechanism that is not part of the protocol. This is not fatal, but it means the headline claim is weaker than it sounds.\n\nTwo more issues. There is no formal security proof; the arguments are plausible but not rigorous. And the prototype omits the Byzantine agreement from Honey Badger, so the asynchronous and offline-tolerance claims are not fully backed by the implementation. The paper says this, which is good, but it also means the tested system is more fragile than the design intends.\n\nI agree with the reader's assessment: conditional, pending stronger analysis and a more complete implementation. The idea is sound, the presentation is trustworthy, and the topic matters. I would cite this in my own work and might bring it to a reading group.\n\nRecommendation: send to peer review. A serious referee can push on the threat model and the rate-limiting assumption. With a formal analysis, this could become a strong paper.","headline":"Kintsugi is a genuinely new combination of known primitives for decentralized key recovery; the main soft spot is the rate-limiting dependency, which the paper itself candidly acknowledges.","tokens_in":13458,"tokens_out":3447,"would_cite":true,"duration_ms":39028,"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":"Kintsugi lets a user recover end-to-end encrypted keys with only a password and any $t+1$ of $n$ decentralized recovery nodes, converting offline password guessing into rate-limited online guessing without specialized hardware.","keywords":["decentralized key recovery","end-to-end encryption","threshold OPRF","secret sharing","proactive secret sharing","password-authenticated","asynchronous network","brute-force resistance"],"falsifier":"Run a Kintsugi deployment with attacker-controlled access to $t$ shares and a full transcript of one successful recovery, give the attacker no further node access, and check whether they can test a password candidate offline by computing the OPRF output; if they can, the core claim that offline guessing requires $t+1$ colluding nodes is false.","tokens_in":12530,"feed_emoji":"🔐","tokens_out":10041,"duration_ms":100269,"temperature":0.7,"pith_summary":"This paper proposes Kintsugi, a protocol that lets a user who has lost their device recover their end-to-end encrypted keys using only a remembered password, without trusting a single service provider or requiring specialized hardware. The idea is to spread the user's recovery secret across multiple independent recovery nodes so that any $t+1$ of them can help, while fewer than $t+1$ cannot do anything useful. The central trick is a threshold oblivious pseudorandom function (OPRF): the password is hashed to a secret point on an elliptic curve, each node contributes a share of a secret key without seeing the password, and the user's device combines the blinded responses into a high-entropy decryption key. Because an attacker cannot test candidate passwords offline from a transcript, every password guess requires a fresh round trip to the nodes, which can be rate-limited. A sympathetic reader would care because this removes the expensive HSM-based, single-provider trust model used by current end-to-end encrypted services.","feed_headline":"One password can restore encrypted data with no single trusted party","feed_subtitle":"Kintsugi splits your key across nodes and rate-limits guesses, so no single provider or expensive hardware is needed.","key_machinery":"The load-bearing object is a threshold OPRF: an oblivious pseudo-random function whose key is secret-shared, so that evaluating it requires $t+1$ cooperating parties and no party learns either the input or the output. Kintsugi realises it by Shamir-sharing a random scalar $s$ and evaluating $s \\cdot P$ in an elliptic-curve group: users send blinded points $r_i \\cdot P$, nodes return $s_i \\cdot r_i \\cdot P$, and Lagrange interpolation in the exponent reconstructs $s \\cdot P$. The companion machinery is dynamic proactive secret sharing (Honey Badger), which refreshes all node shares and lets the committee and threshold change while keeping $s$ fixed, so old shares and former nodes become useless.","core_discovery":"Kintsugi's core claim is that password-based key recovery can be made decentralized and hardware-free by combining a threshold OPRF with Shamir secret sharing and an asynchronous dynamic proactive secret-sharing refresh. During registration, the user samples a random secret $s$, splits it into shares via Shamir's scheme, and distributes them to $n$ recovery nodes; the password is mapped by Elligator to a curve point $P$ whose discrete logarithm is unknown. To recover, the user blinds $P$ with random scalars, sends $r_i \\cdot P$ to $t+1$ nodes, each responds with $s_i \\cdot r_i \\cdot P$, and the user unblinds and Lagrange-interpolates in the exponent to obtain $s \\cdot P$, which serves as the decryption key for the encrypted backup. Because $P$ is not $p \\cdot G$ for an efficiently computable $p$, an adversary who obtains responses cannot offline brute-force the password: each candidate requires a new interactive OPRF evaluation, which nodes can rate-limit. Kintsugi also uses the Honey Badger DPSS protocol to periodically refresh shares and to change the set of nodes or threshold without changing the underlying secret, giving forward secrecy against compromised nodes and letting former recovery nodes lose their power. The paper argues this remains secure with up to $t$ honest-but-curious colluding nodes and $n-t-1$ offline nodes in an asynchronous network.","pith_inferences":["Because rate-limiting is an operational assumption rather than a cryptographic guarantee, the practical security floor is set by the weakest rate-limiting node; a botnet or IP-rotation attack is a genuine residual risk the paper acknowledges but does not solve.","The same construction could plausibly be used for password-authenticated account recovery in federated identity settings where no single identity provider should be able to mount offline guessing, or to protect low-entropy secrets held across multiple parties.","Replacing rate-limiting with a proof-of-work or other per-request cost factor might make the anti-brute-force guarantee cryptographic rather than operational, a natural extension the paper hints at with its PKI-based future work."],"forward_implications":["A user who remembers only a low-entropy password can recover their keys on a new device with the help of any $t+1$ of $n$ recovery nodes, without a central service or HSM.","Offline brute-force password guessing is impossible unless $t+1$ nodes collude; otherwise an attacker can only make one password guess per interactive round, subject to rate limiting.","Changing recovery nodes or changing $t$ can be done at any time via a DPSS refresh; former nodes cannot participate afterward, and refreshes limit the damage if shares leak over time.","The protocol remains correct under arbitrary network delays, tolerating up to $t$ honest-but-curious colluding nodes and $n-t-1$ offline nodes.","Any party can operate a recovery node on consumer hardware or an end-user device, which removes the cost barrier of HSMs and enables peer-to-peer or multi-provider deployments."],"supporting_citations":[{"why":"Supplies the Shamir secret sharing scheme used to split the OPRF secret $s$ among recovery nodes.","marker":"[23]"},{"why":"Provides the threshold OPRF construction that Kintsugi adapts, including interpolation in the exponent.","marker":"[14]"},{"why":"Hashes the password to a curve point whose discrete logarithm is unknown, which is what forces password guesses to happen online.","marker":"[9]"},{"why":"Defines the Ristretto elliptic-curve group in which OPRF evaluations are performed.","marker":"[25]"},{"why":"Supplies the password-authenticated OPRF flow that Kintsugi reframes as key recovery.","marker":"[28]"},{"why":"Supplies the asynchronous dynamic proactive secret-sharing protocol used to refresh shares and change recovery nodes.","marker":"[29]"}],"fun_headline_variants":["Decentralized key recovery: password-only, no trusted server","Password-only key recovery, rate-limited, no special hardware","Kintsugi: trust split across nodes, password restores keys","No single point of trust: E2EE key recovery via threshold OPRF","E2EE key recovery: distribute trust, avoid offline brute force"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The security claim depends on recovery nodes actually enforcing rate limits on recovery requests; if an attacker can send unlimited requests, for example by using a botnet to evade IP-based limits, the password can be brute-forced online.","fun_headline_variants_meta":{"raw":{"variants":["Decentralized key recovery: password-only, no trusted server","Password-only key recovery, rate-limited, no special hardware","Kintsugi: trust split across nodes, password restores keys","No single point of trust: E2EE key recovery via threshold OPRF","E2EE key recovery: distribute trust, avoid offline brute force"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000926,"raw_usage":{"total_tokens":4004,"prompt_tokens":1015,"completion_tokens":2989,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":631,"completion_tokens_details":{"reasoning_tokens":2898}},"tokens_in":631,"tokens_out":2989,"duration_ms":27410,"temperature":1.0,"reasoning_tokens":2898,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T16:12:04.375462+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run a Kintsugi deployment with attacker-controlled access to $t$ shares and a full transcript of one successful recovery, give the attacker no further node access, and check whether they can test a password candidate offline by computing the OPRF output; if they can, the core claim that offline guessing requires $t+1$ colluding nodes is false.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the Ristretto elliptic-curve group in which OPRF evaluations are performed."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the password-authenticated OPRF flow that Kintsugi reframes as key recovery."},{"cited_title":"In: 32nd USENIX Security Symposium (USENIX Security 23)","cited_arxiv_id":null,"evidence_quote":"Supplies the asynchronous dynamic proactive secret-sharing protocol used to refresh shares and change recovery nodes."}],"review_version":1}