System, method, and computer program product for implementing zero round trip secure communications based on noisy secrets with a polynomial secret sharing scheme

1. A method, comprising:

identifying, by a sender device, two negotiated noisy secrets associated with an encrypted message to send to a receiver device;

utilizing, by the sender device, a first negotiated noisy secret for sub-key selection;

generating, by the sender device, a secret polynomial using Shamir's polynomial-based secret sharing scheme with N points, where N is a positive integer, and a message key as a secret;

dividing, by the sender device, the first negotiated noisy secret into a plurality of sub-keys;

dividing, by the sender device, a second negotiated noisy secret into test blocks of a length equivalent to a length of a sub-key;

utilizing, by the sender device, each of the plurality sub-keys for encrypting a corresponding test block along with one unique point of the secret polynomial; and

sending, by the sender device, all encrypted test blocks and corresponding encrypted points of the secret polynomial to the receiver device with the encrypted message;

wherein the receiver device utilizes the second negotiated noisy secret for sub-key validity testing;

wherein the receiver device finds M noiseless sub-key candidates, where M is a positive integer, by decrypting the encrypted test blocks and comparing the encrypted test blocks with corresponding test blocks obtained from the second negotiated noisy secret by the receiver device.

2. The method of claim 1 , wherein the receiver device decrypts the N points of the secret polynomial with the M noiseless sub-key candidates.

3. The method of claim 2 , wherein the receiver device converts the secret polynomial into the secret message key.

4. The method of claim 3 , wherein the receiver device eliminates false positives by testing the secret message key using a special hardcoded message authentication code (MAC).

5. The method of claim 4 , wherein the receiver device tests the secret message key using a full encrypted message MAC.

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

identifying, by a sender device, two negotiated noisy secrets associated with an encrypted message to send to a receiver device;

utilizing, by the sender device, a first negotiated noisy secret for sub-key selection;

generating, by the sender device, a secret polynomial using Shamir's polynomial-based secret sharing scheme with N points, where N is a positive integer, and a message key as a secret;

dividing, by the sender device, the first negotiated noisy secret into a plurality of sub-keys;

dividing, by the sender device, a second negotiated noisy secret into test blocks of a length equivalent to a length of a sub-key;

utilizing, by the sender device, each of the plurality sub-keys for encrypting a corresponding test block along with one unique point of the secret polynomial; and

sending, by the sender device, all encrypted test blocks and corresponding encrypted points of the secret polynomial to the receiver device with the encrypted message;

wherein the receiver device utilizes the second negotiated noisy secret for sub-key validity testing;

wherein the receiver device finds M noiseless sub-key candidates, where M is a positive integer, by decrypting the encrypted test blocks and comparing the encrypted test blocks with corresponding test blocks obtained from the second negotiated noisy secret by the receiver device.

7. The non-transitory computer readable medium of claim 6 , wherein the receiver device decrypts the N points of the secret polynomial with the M noiseless sub-key candidates.

8. The non-transitory computer readable medium of claim 7 , wherein the receiver device converts the secret polynomial into the secret message key.

9. The non-transitory computer readable medium of claim 8 , wherein the receiver device eliminates false positives by testing the secret message key using a special hardcoded message authentication code (MAC).

10. The non-transitory computer readable medium of claim 9 , wherein the receiver device tests the secret message key using a full encrypted message MAC.

11. A sender device, comprising:

a memory storing instructions, and

a computer processor executing the instructions for:

identifying two negotiated noisy secrets associated with an encrypted message to send to a receiver device;

utilizing a first negotiated noisy secret for sub-key selection;

generating a secret polynomial using Shamir's polynomial-based secret sharing scheme with N points, where N is a positive integer, and a message key as a secret;

dividing the first negotiated noisy secret into a plurality of sub-keys;

dividing a second negotiated noisy secret into test blocks of a length equivalent to a length of a sub-key;

utilizing each of the plurality sub-keys for encrypting a corresponding test block along with one unique point of the secret polynomial; and

sending all encrypted test blocks and corresponding encrypted points of the secret polynomial to the receiver device with the encrypted message;

wherein the receiver device utilizes the second negotiated noisy secret for sub-key validity testing;

wherein the receiver device finds M noiseless sub-key candidates, where M is a positive integer, by decrypting the encrypted test blocks and comparing the encrypted test blocks with corresponding test blocks obtained from the second negotiated noisy secret by the receiver device.

12. The sender device of claim 11 , wherein the receiver device decrypts the N points of the secret polynomial with the M noiseless sub-key candidates.

13. The sender device of claim 12 , wherein the receiver device converts the secret polynomial into the secret message key.

14. The sender device of claim 13 , wherein the receiver device eliminates false positives by testing the secret message key using a special hardcoded message authentication code (MAC).