Zero round trip secure communications are implemented based on noisy secrets with a polynomial secret sharing scheme. A sender identifies two negotiated noisy secrets associated with an encrypted message to send to a receiver system. The sender utilizes a first negotiated noisy secret for sub-key selection, and generates a secret polynomial using Shamir's polynomial-based secret sharing scheme with N positive integer points and a message key as a secret. The sender divides the first negotiated noisy secret into a plurality of sub-keys, and divides a second negotiated noisy secret into test blocks of a length equivalent to a length of a sub-key. The sender utilizes each of the plurality sub-keys for encrypting a corresponding test block along with one unique point of the secret polynomial. Moreover, the sender sends all encrypted test blocks and corresponding encrypted points of the secret polynomial to the receiver with the encrypted message.