Towards the Impossibility of Imperfectly Complete Key Agreement in the QROMResearch Paper
Two parties who share no secret want to agree on a key over a public channel, using only a shared random function that everyone, the eavesdropper included, can query. Merkle's puzzle protocol achieves a quadratic gap: the honest parties make queries and an eavesdropper needs about . For classical parties this gap is optimal. Impagliazzo and Rudich…