A system, method, and computer program product are provided for implementing zero round trip secure communications based on a noisy secret with a reduced message size. A receiver system receives from a sender system an encrypted message including encrypted message keys and a message MAC that is calculated and added for every sub-key. The receiver system determines if any one of the sub-keys is noiseless based on its corresponding message MAC. If none of the sub-keys are noiseless, the receiver system adjusts bits of the sub-keys until a sub-key with one noisy bit is found and corrected to form a noiseless sub-key. The noiseless sub-key is then processed to obtain a message key to decrypt the encrypted message.