Pith. sign in

REVIEW 4 major objections 5 minor 31 references

Kintsugi: Decentralized E2EE Key Recovery

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

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

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2507.21122 v1 pith:I2GFJPSD submitted 2025-07-18 cs.CR

Emilie Ma , Martin Kleppmann This is my paper · ORCID
classification cs.CR MSC 94A60
keywords decentralizedkeyrecoveryend-to-endencryptionthresholdOPRFsecretsharingproactivepassword-authenticatedasynchronousnetworkbrute-forceresistance
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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 5 minor

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.

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 (4)
  1. [§3.1, §2] 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.
  2. [§3.2] 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.
  3. [§3.3] 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.
  4. [§3.2] 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.
minor comments (5)
  1. [§3] In the first bullet list, 'an threshold Oblivious Pseudo-Random Function' should read 'a threshold Oblivious Pseudo-Random Function'.
  2. [§3.2] 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.
  3. [§3.3] 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.
  4. [§3.4] 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.
  5. [§3.1] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Kintsugi's security claims follow from independently established cryptographic primitives and explicit protocol assumptions, with no fitted parameters or self-citation chain.

full rationale

The paper's derivation chain is self-contained relative to its stated assumptions. The threshold OPRF construction in Section 3.1 combines an OPRF with Shamir secret sharing; the claim that offline brute-force is prevented follows from the requirement that t+1 recovery-node responses are needed per password guess, combined with the discrete-log assumption and the blinding of P. The encryption key s·P is derived from independently chosen inputs (password-derived point P and random shared secret s), not fitted to any target output. The dynamic proactive secret sharing in Section 3.3 is imported from externally published work (Yurek et al.'s Honey Badger) and is not used to justify the paper's own novel claims by self-citation. The most load-bearing practical dependency, rate-limiting, is explicitly stated as an operational requirement rather than a protocol guarantee, and the paper candidly discusses its limitations (botnet circumvention of IP-based limits and DoS via per-user limits). That is a limitation or an unproven assumption, but it is not circular: the protocol's internal security derivation does not presuppose the conclusion that offline brute-force is impossible. No equation in the paper reduces to its own output by construction, and no fitted parameter is renamed as a prediction. Therefore the appropriate circularity score is 0.

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

The central security claim rests on standard cryptographic hardness assumptions (discrete log, random oracle), an honest-but-curious threat model, the assumption that recovery nodes enforce rate limits, and the correctness of the DPSS protocol as specified. The paper also relies on the DHT providing reliable lookup and on the password having sufficient entropy under online guessing.

assumptions (8)
  • standard math The elliptic-curve discrete log problem is hard for the Ristretto group.
    The OPRF security relies on the infeasibility of computing the discrete log of P or s*P in the group, as stated in Section 3.1.
  • domain assumption HashToCurve (e.g., Elligator) behaves as a random oracle, producing curve points whose discrete log is unknown.
    Section 3.1 relies on this to prevent offline brute-force when the user sends blinded points to recovery nodes.
  • domain assumption All recovery nodes are honest-but-curious and correctly follow the protocol.
    Section 2 explicitly assumes no Byzantine nodes; the prototype does not implement Byzantine fault tolerance.
  • domain assumption Recovery nodes enforce rate-limiting on recovery requests.
    Section 3.2 states rate-limiting protects against online brute-force; if not enforced, security degrades to online guessing.
  • domain assumption The password space is large enough that an online brute-force attack, limited by rate limiting, is infeasible.
    The abstract claims support for 'potentially low-entropy' passwords, but the actual security depends on the rate limit and password entropy, which is not quantified.
  • domain assumption The network is asynchronous, and messages are delivered eventually.
    Section 2 models an asynchronous network; however, the simplified DPSS without Byzantine agreement may not handle offline nodes during refresh.
  • domain assumption The DPSS protocol (Honey Badger) is secure and supports dynamic committees.
    Section 3.3 relies on [29] for the DPSS properties; the prototype implements only the share-refresh part, not the agreement protocols.
  • domain assumption The DHT (Kademlia) provides liveness and consistency for lookups despite lacking integrity.
    Section 3.2 uses the DHT to map usernames to recovery nodes; a misbehaving DHT node could serve fake recovery node information.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Kintsugi: Decentralized E2EE Key Recovery." pith.science (2026). https://pith.science/paper/I2GFJPSD

@misc{pith2026250721122,
  author       = {Pith},
  title        = {Pith review of: Kintsugi: Decentralized E2EE Key Recovery},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/I2GFJPSD}},
  note         = {Machine review of arXiv:2507.21122}
}
abstract

Kintsugi is a protocol for key recovery, allowing a user to regain access to end-to-end encrypted data after they have lost their device, but still have their (potentially low-entropy) password. Existing E2EE key recovery methods, such as those deployed by Signal and WhatsApp, centralize trust by relying on servers administered by a single provider. Kintsugi is decentralized, distributing trust over multiple recovery nodes, which could be servers run by independent parties, or end user devices in a peer-to-peer setting. To recover a user's keys, a threshold $t+1$ of recovery nodes must assist the user in decrypting a shared backup. Kintsugi is password-authenticated and protects against offline brute-force password guessing without requiring any specialized secure hardware. Kintsugi can tolerate up to $t$ honest-but-curious colluding recovery nodes, as well as $n - t - 1$ offline nodes, and operates safely in an asynchronous network model where messages can be arbitrarily delayed.

Figures

Figures reproduced from arXiv: 2507.21122 by the authors.

Figure 1
Figure 1. Threshold OPRF evaluation after secret share setup. User Recovery Node 1 Recovery Node i . . . Recovery Node t + 1 r1 · P ri · P rt+1 · P s1 · r1 · P si · ri · P st+1 · rt+1 · P Multiply each response by λi(0) · r −1 i Sum responses = s · P See [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. DPSS Secret Refreshing Node 1 Node i Node t+1 Former Recovery Nodes New Recovery Node j s1 si st+1 SSS ′ 1(j) SSS ′ i(j) SSS ′ t+1(j) Multiply responses by λi(0) and sum = SSS0(j) = s ′ j s ′ j Honey Badger is able to tolerate up to one-third of nodes being Byzantine and not following the protocol. The Kintsugi prototype currently does not imple￾ment these aspects of Honey Badger (e.g. the multi-valued validated Byz… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

31 extracted references · 28 canonical work pages

  1. [1]

    Automerge CRDT, https://automerge .github.io/

    work page

  2. [2]

    Kademlia DHT (2023), https://docs .libp2p.io/concepts/discovery-routing/ kaddht/

    work page 2023

  3. [3]

    1Password: 1Password Security Design (2024), https://1passwordstatic .com/files/ security/1password-white-paper.pdf

    work page 2024

  4. [4]

    1Password: If you forgot your 1Password account password or you can’t unlock the app (2024), https://support .1password.com/forgot-account-password/

    work page 2024

  5. [5]

    Anderson, J., Stajano, F.: On Storing Private Keys in the Cloud, vol. 7061, p. 98–106. Springer Berlin Heidelberg, Berlin, Heidelberg (2014). https:// doi.org/10.1007/978-3-662-45921-8_16, http://link .springer.com/10.1007/978-3- 662-45921-8_16

    work page doi:10.1007/978-3-662-45921-8_16 2014

  6. [6]

    Apple: Escrow security for iCloud Keychain (2024), https://support .apple.com/ en-gb/guide/security/sec3e341e75d/web

    work page 2024

  7. [7]

    Apple: Set up a recovery key for your Apple Account (2024), https:// support.apple.com/en-gb/109345

    work page 2024

  8. [8]

    Apple: Set up an account recovery contact (2024), https://support .apple.com/en- gb/102641

    work page 2024

Show all 31 references
  1. [9]

    In: Proceedings of the 2013 ACM SIGSAC conference on Computer & Communications Security

    Bernstein, D.J., Hamburg, M., Krasnova, A., Lange, T.: Elligator: elliptic-curve points indistinguishable from uniform random strings. In: Proceedings of the 2013 ACM SIGSAC conference on Computer & Communications Security. p. 967–980. 14 E. Ma, M. Kleppmann. CCS ’13, Associat...

    2013

  2. [10]

    https://doi .org/10.48550/arXiv.2406.18226, http://arxiv .org/abs/ 2406.18226, arXiv:2406.18226 [cs]

    Blessing, J., Hugenroth, D., Anderson, R.J., Beresford, A.R.: SoK: Web Authentication in the Age of End-to-End Encryption (arXiv:2406.18226) (Jun 2024). https://doi .org/10.48550/arXiv.2406.18226, http://arxiv .org/abs/ 2406.18226, arXiv:2406.18226 [cs]

    2024 doi arXiv

  3. [11]

    In: 18th USENIX Sym- posium on Operating Systems Design and Implementation (OSDI 24)

    Connell, G., Fang, V., Schmidt, R., Dauterman, E., Popa, R.A.: Secret Key Re- covery in a Global-Scale End-to-End Encryption System. In: 18th USENIX Sym- posium on Operating Systems Design and Implementation (OSDI 24). pp. 703–

  4. [12]

    In: 32nd USENIX Security Symposium (USENIX Security 23)

    Das, S., Xiang, Z., Kokoris-Kogias, L., Ren, L.: Practical asynchronous high- threshold distributed key generation and distributed polynomial sampling. In: 32nd USENIX Security Symposium (USENIX Security 23). pp. 5359–5376. USENIX Association, Anaheim, CA (Aug 2023), https://w...

    2023

  5. [13]

    Hu, B., Zhang, Z., Chen, H., Zhou, Y., Jiang, H., Liu, J.: DyCAPS: Asyn- chronous Dynamic-committee Proactive Secret Sharing (2022/1169) (2022), https: //eprint.iacr.org/2022/1169, publication info: Preprint

    2022

  6. [14]

    In: Gollmann, D., Miyaji, A., Kikuchi, H

    Jarecki, S., Kiayias, A., Krawczyk, H., Xu, J.: TOPPSS: Cost-Minimal Password- Protected Secret Sharing Based on Threshold OPRF. In: Gollmann, D., Miyaji, A., Kikuchi, H. (eds.) Applied Cryptography and Network Security. pp. 39–58. Springer International Publishing, Cham (2017...

    2017 doi

  7. [15]

    In: Proceedings of the 2019 ACM SIGSAC Conference on Com- puter and Communications Security

    Jarecki, S., Krawczyk, H., Resch, J.: Updatable Oblivious Key Management for Storage Systems. In: Proceedings of the 2019 ACM SIGSAC Conference on Com- puter and Communications Security. p. 379–393. ACM, London United King- dom (Nov 2019). https://doi .org/10.1145/3319535.3363...

    2019

  8. [16]

    Krassovsky, S., Cadden, G.: How WhatsApp is enabling end-to-end encrypted back- ups (Sep 2021), https://engineering .fb.com/2021/09/10/security/whatsapp-e2ee- backups/

    2021

  9. [17]

    Laroche, G.: (2024), https://www .preveil.com/blog/product-release-selective- sync-account-recovery/

    2024

  10. [18]

    LastPass: Recover your lost master password for LastPass (2024), https://support.lastpass.com/s/document-item?language=en_US&bundleId= lastpass&topicId=LastPass%2Frecover-master-password.html&_LANG=enus

    2024

  11. [19]

    In: Revised Papers from the First International Work- shop on Peer-to-Peer Systems

    Maymounkov, P., Mazières, D.: Kademlia: A Peer-to-Peer Information System Based on the XOR Metric. In: Revised Papers from the First International Work- shop on Peer-to-Peer Systems. p. 53–65. IPTPS ’01, Springer-Verlag, Berlin, Hei- delberg (2002)

    2002

  12. [20]

    MEGA: What is my MEGA recovery key? (Dec 2021), https://help .mega.io/ accounts/password-management/recovery-key

    2021

  13. [21]

    Palatinus, M., Rusnak, P., Voisine, A., Bowe, S.: Mnemonic code for generat- ing deterministic keys (2013), https://github .com/bitcoin/bips/blob/master/bip- 0039.mediawiki

    2013

  14. [22]

    PreVeil: PreVeil Security and Design (Jul 2023), https://www .preveil.com/wp- content/uploads/2019/10/PreVeil_Security_Whitepaper-v1.5.pdf Kintsugi: Decentralized E2EE Key Recovery 15

    2023

  15. [23]

    Shamir, A.: How to share a secret. Commun. ACM 22(11), 612–613 (Nov 1979). https://doi .org/10.1145/359168.359176, https://dl .acm.org/doi/10.1145/ 359168.359176

    1979

  16. [24]

    Trapp, N.: Key to Simplicity: Squeezing the hassle out of encryption key recov- ery (Apr 2024), https://juicebox .xyz/blog/key-to-simplicity-squeezing-the-hassle- out-of-encryption-key-recovery

    2024

  17. [25]

    de Valence, H.: Ristretto - The Ristretto Group, https://ristretto .group/

  18. [26]

    WhatsApp: Can’t remember password for encrypted backup (2022), https:// faq.whatsapp.com/639067727894647

    2022

  19. [27]

    WhatsApp: How to reset your two-step verification PIN (2022), https:// faq.whatsapp.com/2183055648554771/

    2022

  20. [28]

    Wood, C., Bourdrez, D., Lewi, K., Krawczyk, H.: The OPAQUE Augmented PAKE Protocol (2024), https://cfrg .github.io/draft-irtf-cfrg-opaque/draft-irtf- cfrg-opaque.html

    2024

  21. [29]

    In: 32nd USENIX Security Symposium (USENIX Security 23)

    Yurek, T., Xiang, Z., Xia, Y., Miller, A.: Long Live The Honey Badger: Robust Asynchronous DPSS and its Applications. In: 32nd USENIX Security Symposium (USENIX Security 23). pp. 5413–5430. USENIX Association, Anaheim, CA (Aug 2023), https://www .usenix.org/conference/usenixse...

    2023

  22. [30]

    It is totally socially engineerable, in the sense that they will always respond, but becau se there’s a limit, they can’t go very far

    Zelenka, B., Good, A.: Beehive lab notebook (2024), https:// www.inkandswitch.com/beehive/notebook/ 1 William W ayman: When the user is setting out the nodes that they want to share the secrets with, is there a central trusted party that has knowledge of these nodes? Reply: Th...

    2024

  23. [719]

    USENIX Association, Santa Clara, CA (Jul 2024), https://www .usenix.org/ conference/osdi24/presentation/connell

    2024

Pith tools

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