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

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.

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.