Error-correcting key agreement for noisy cryptographic systems

A non-transitory computer readable medium storing computer code executable by a processor to perform a method comprising:

• negotiating N secret keys using a noisy cryptographic system, wherein K secret keys of the N secret keys are expected to be noiseless;
• generating a secret polynomial that includes the N secret keys;
• deriving K points on the secret polynomial;
• for each secret key of the N secret keys in an order of the negotiation, deriving a secret key message authentication code (MAC) key and calculating a secret key MAC for the secret key using the derived secret key MAC key;
• generating a secret key MAC header that includes an array comprised of each of the secret key MACs and a corresponding public key;
• generating message integrity plaintext that includes an encrypted message, the secret key MAC header, and an array of the K points on the secret polynomial;
• generating a final message that includes the message integrity plaintext;
• and
• sending the final message.

An apparatus, comprising:

• a memory storing instructions, and
• a computer processor executing the instructions to perform a method comprising:
• negotiating N secret keys using a noisy cryptographic system, wherein K secret keys of the N secret keys are expected to be noiseless;
• generating a secret polynomial that includes the N secret keys;
• deriving K points on the secret polynomial;
• for each secret key of the N secret keys in an order of the negotiation, deriving a secret key message authentication code (MAC) key and calculating a secret key MAC for the secret key using the derived secret key MAC key;
• generating a secret key MAC header that includes an array comprised of each of the secret key MACs and a corresponding public key;
• generating message integrity plaintext that includes an encrypted message, the secret key MAC header, and an array of the K points on the secret polynomial;
• generating a final message that includes the message integrity plaintext;
• and
• sending the final message.

A method for receiving a message using a noisy cryptographic system, comprising:

• negotiating N secret keys using a noisy cryptographic system, wherein K secret keys of the N secret keys are expected to be noiseless;
• receiving a final message having message integrity plaintext, the message integrity plaintext including:
• an encrypted message,
• a secret key MAC header that includes an array comprised of a secret key MAC and a corresponding public key for each of the N secret keys, and
• an array of K points on a secret polynomial;
• determining at least K secret key candidates from the N secret keys;
• using the at least K secret key candidates to determine N coefficients for the secret polynomial;
• using a key derivation function (KDF) on the N coefficients of the secret polynomial to derive a message encryption key;
• and
• decrypting the encrypted message using the message encryption key.