A user device can segment a secret (e.g., a data recovery key) into a master segment and a shared segment such that possession of both segments is necessary and sufficient to reconstruct the secret. The user device can provide the master segment to a server system. The user device can further segment the shared segment to generate a set of M shares such that any subset of the shares that includes at least a threshold number t of the shares can be used to reconstruct the shared segment, while fewer than t shares provide no information about the shared segment. The M shares can be distributed to shareholder devices. To reconstruct the secret, a recovery device can obtain the master segment and at least t of the M shares, then reconstruct the secret.