Improved techniques are provided for the generation of exfiltration-resilient cryptographic keys. A method is provided for generating exfiltration-resilient cryptographic keys for authentication and/or digital signing. A set of authentication information sk[i] is stored in a device associated with a user and a set of public keys pk[i] are provided to a verifier corresponding to the set of authentication information sk[i], where sk[i] is mapped to pk[i] using a hash function. The device obtains a challenge from the verifier comprising a sequence C of k indices. A response is provided to the verifier comprising elements of the set of authentication information sk[i] corresponding to the k indices. The set of authentication information sk optionally has a size that satisfies one or more leakage-resilient criteria.