Protocols with noisy response-based cryptographic subkeys
Methods for the storage and retrieval of a digital file are disclosed. The file is encrypted with a random binary key. A mathematical challenge-response-pair (CRP} mechanism is used to generate an ordered list of responses from a list of challenges. A subset of responses within the ordered list of responses is selected, which each selected response occupying a position in the ordered list that is the same position as a first binary symbol in the random key. In this way, the key can be encoded in the selection of responses. To recover the key, the selected responses are compared to a full list of responses to determine which of the responses in the full list match selected responses. Matches indicate the first binary symbol in the corresponding position in the key and non-matches indicate the second binary symbol. In this way, the key is reconstructed, and file may be decrypted.
1 . A method of managing access to a digital file F in a computing environment, comprising an enrollment procedure comprising:
generating a random bitstream L;
using L as a seed input to an asymmetrical encryption algorithm to generate a key pair having a secret key Sk and a public key Pk;
encrypting F with the secret key Sk resulting in an encrypted file C;
generating an encryption key K, and encrypting Pk with K resulting in M*;
generating an ordered sequence of challenges to a Challenge-Response Pair (CRP) generation mechanism;
applying the ordered sequence of challenges to the CRP generation mechanism to generate a first full ordered sequence of responses;
selecting responses within the first full ordered sequence of responses that have positions in the ordered sequence that correspond to positions of a first binary symbol in K, resulting in an ordered subset of responses Kr;
storing Kr in non-volatile storage at a first computing device; and
storing Kc and C in non-volatile storage at a second computing device, where Kc comprises information usable to regenerate the ordered sequence of challenges to the CRP generation mechanism and M*.
2 . The method of claim 1 , further comprising storing the digital file F at the first computing device.
3 . The method of claim 1 , wherein the asymmetrical encryption algorithm comprises one of RSA, ECC, a Lattice-based algorithm, CRYSTALS Kyber, Dilithium, Falcon, SHPINCS or classic McElice code.
4 . The method of claim 1 , wherein the CRP generation mechanism comprises a physical object.
5 . The method of claim 4 , wherein the physical object is a biological object or an addressable array of physical unclonable function devices.
6 . The method of claim 1 , wherein the CRP generation mechanism is a digital file C* comprising an ordered sequence of segments.
7 . The method of claim 6 , further comprising generating C* by steps comprising:
generating a random nonce ω; and
subjecting the encrypted file C to a hashing algorithm and concatenating the resulting hash with random nonce ω.
8 . The method of claim 7 , wherein the hashing algorithm is SHA-256.
9 . The method of claim 7 , further comprising extending C* with an extendable output function until it reaches a predetermined bit length having d segments.
10 . The method of claim 9 , wherein the extendable output function is SHAKE.
11 . The method of claim 6 , wherein generating an ordered sequence of challenges to a CRP generation mechanism comprises:
generating a random bitstream S;
generating a bitstream S* based on S, where S* has a predetermined bit length; and
diving S* into challenge segments, each segment encoding an address of one of the segments of C*.
12 . The method of claim 1 , further comprising a method of decrypting an encrypted file C, encrypted according to the method of claim 1 , comprising:
receiving Kc and using Kc to generate the ordered sequence of challenges to the CRP generation mechanism;
applying the ordered sequence of challenges to the CRP generation mechanism to generate a second full ordered sequence of responses;
receiving Kr, and comparing the ordered subset of responses to the second full ordered sequence of responses to identify positions in the second full sequence of responses for which there are matches in the ordered subset of responses;
constructing a key having a first binary symbol in positions corresponding to matches between responses in the second full sequence of responses and the ordered subset of responses, and a second binary symbol for non-matching positions;
using the key to decrypt M* resulting in Pk; and
using Pk to decrypt C.
13 . The method of claim 12 , wherein identifying positions in the second full sequence of responses for which there are matches in the ordered subset of responses comprises computing a Hamming distance between each response in the ordered subset of responses and each response in the second full sequence of responses and identifying a match where the Hamming distance is below some threshold.