Learning parity with noise computational hardness conjecture
Statement
Let the secret key be and let the noise rate be . A noisy observation is
where . Learning parity with noise conjecture. Any polynomial-time algorithm with -time query access to these observations requires computational complexity to distinguish, correctly with probability , between pure noise, , and noisy parity, . This is a standard cryptographic hardness assumption used to obtain computational lower bounds; however, the supplied parser marks this candidate as disproved, so its resolution and the evidence for that status should be checked.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.