Paper 2025/551

ANARKey: A New Approach to (Socially) Recover Keys

Aniket Kate, Purdue University / Supra Research
Pratyay Mukherjee, Supra Research
Hamza Saleem, Supra Research
Pratik Sarkar, Supra Research
Bhaskar Roberts, University of California, Berkeley
Abstract

In a social key recovery scheme, users back up their secret keys (typically using Shamir's secret sharing) with their social connections, known as a set of guardians. This places a heavy burden on the guardians, as they must manage their shares both securely and reliably. Finding and managing such a set of guardians may not be easy, especially when the consequences of losing a key are significant. We take an alternative approach of social recovery within a community, where each member already holds a secret key (with possibly an associated public key) and uses other community members as their guardians forming a mutual dependency among themselves. Potentially, each member acts as a guardian for upto other community members. Therefore, in this setting, using standard Shamir's sharing leads to a linear () blow-up in the internal secret storage of the guardian for each key recovery. Our solution avoids this linear blowup in internal secret storage by relying on a novel secret-sharing scheme, leveraging the fact that each member already manages a secret key. In fact, our scheme does not require guardians to store anything beyond their own secret keys. We propose the first formal definition of a social key recovery scheme for general access structures in the community setting. We prove that our scheme is secure against any malicious and adaptive adversary that may corrupt up to parties. As a main technical tool, we use a new notion of secret sharing, that enables out of sharing of a secret even when the shares are generated independently -- we formalize this as bottom-up secret sharing (BUSS), which may be of independent interest. Finally, we provide an implementation benchmarking varying the number of guardians both in a regional, and geo-distributed setting. For instance, for 8 guardians, our backup protocol takes around 146-149 ms in a geo-distributed WAN setting, and 4.9-5.9 ms in the LAN setting; for recovery protocol, the timings are approximately the same for the WAN setting (as network latency dominates), and 1.2-1.4 ms for the LAN setting.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Key RecoveryKey ManagementSecret Sharing
Contact author(s)
aniket @ purdue edu
pratyay85 @ gmail com
h saleem @ supraoracles com
iampratiksarkar @ gmail com
bhaskarr @ berkeley edu
History
2025-03-26: approved
2025-03-25: received
See all versions
Short URL
https://ia.cr/2025/551
License
Creative Commons Attribution-NonCommercial-ShareAlike
CC BY-NC-SA

BibTeX

@misc{cryptoeprint:2025/551,
      author = {Aniket Kate and Pratyay Mukherjee and Hamza Saleem and Pratik Sarkar and Bhaskar Roberts},
      title = {{ANARKey}: A New Approach to (Socially) Recover Keys},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/551},
      year = {2025},
      url = {https://eprint.iacr.org/2025/551}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.