Secret key agreement from correlated data, with no prior information
This addresses a fundamental challenge in cryptography for secure communication, though it is incremental as it builds on existing models but removes the need for prior correlation information.
The paper tackles the problem of two parties generating a shared secret key from correlated data without any prior knowledge about the correlation, achieving complexity-theoretical security where the key appears random to a space-bounded eavesdropper, but the protocol is inefficient as it requires more space than the adversary.
A fundamental question that has been studied in cryptography and in information theory is whether two parties can communicate confidentially using exclusively an open channel. We consider the model in which the two parties hold inputs that are correlated in a certain sense. This model has been studied extensively in information theory, and communication protocols have been designed which exploit the correlation to extract from the inputs a shared secret key. However, all the existing protocols are not universal in the sense that they require that the two parties also know some attributes of the correlation. In other words, they require that each party knows something about the other party's input. We present a protocol that does not require any prior additional information. It uses space-bounded Kolmogorov complexity to measure correlation and it allows the two legal parties to obtain a common key that looks random to an eavesdropper that observes the communication and is restricted to use a bounded amount of space for the attack. Thus the protocol achieves complexity-theoretical security, but it does not use any unproven result from computational complexity. On the negative side, the protocol is not efficient in the sense that the computation of the two legal parties uses more space than the space allowed to the adversary.