2
$\begingroup$

There is a paper: U. M. Maurer, Secret key agreement by public discussion from common information, IEEE Trans. Inf. Theory, 39(3) 733-742 of 1993, with an IMHO fairly impressive title but having apparently for some unknown reasons been hithertofore ignored in the common textbooks on modern cryptography. The material there is way above my humble knowledge, hence my request: Could some experts kindly give a sketch of the main idea of the paper such that one could get at least a certain rough comprehension of it? Are there good open-source implementations of that key agreement scheme?

$\endgroup$

3 Answers 3

1
$\begingroup$

Maurer is likely making unrealistic assumptions about noise. The following excerpt is from the paper's conclusion:

The paper suggests the following conclusion for the implementation of cryptographic systems on given noisy communication channels. Such channels should not be converted into error-free channels by means of error-correcting codes, followed by a cryptographic protocol based on error-free channels because this design strategy would imply that Shannon's pessimistic inequality (2) applies and therefore perfect secrecy cannot be achieved unless an impractically large amount of shared secret key is available. Instead, cryptographic coding and error-control coding should be combined, resulting in a system achieving virtually perfect secrecy, with a (short) secret key being required only for authentication.

The author hopes that this paper and a subsequent paper on practical implementations will help to move perfect secrecy closer to being practical.

I'm not an expert either, but have an interest in new and unconventional cryptography. With research papers I find it helpful as a first pass to read the abstract and conclusion. Whatever claims made in the conclusion can then be referenced by going back in the paper. In this paper, the reliance on noise and error coding seemed both its strength and weakness.

What happens if an attacker can manipulate the noise/signal of the system? If they were able to reduce the noise of a channel, wouldn't an attacker be able to derive too much information about the cryptography from the coding? Here's a hypothetical attack: attacker Eve deliberately injects noise into a system, making system seem much noisier than it actually is, which the two communicating parties Alice and Bob then derive their probabilistic models from, but when Alice and Bob start exchanging data, Eve removes the noise.

By comparison Diffie-Hellman is a simpler overall scheme that makes no assumption about the underlying communications channel.

$\endgroup$
2
  • $\begingroup$ As layman, I can't argue withj you at all. But there seem to be indications of much work being done on the noise issue following that seminal paper and even attempts of patent applications. $\endgroup$ Mar 6, 2016 at 12:05
  • $\begingroup$ Personally I feel cryptographic patents hinder their wider adoption. See ECC patents. It is possible identity-based encryption would be much better known and adopted if not for the patent centric commercialization surrounding it. $\endgroup$
    – HTLee
    Mar 6, 2016 at 20:47
1
$\begingroup$

The other answers provide a few pieces of the picture. Here, I will try to give the broad view tying it together.

Maurer's protocol is today known also as advantage distillation. The paper is about information-theoretic security which is generally considered expensive, in the sense that it is equivalent to using one-time pad. Furthermore, the problem with classical (non-quantum) information-theoretic security is that an assumption about the noise of the eavesdropper Eve needs to be made. That said, here is why Maurer's result is important.

Standard information-theoretic security uses only forward communication, analog to forward error correction. In this case, it is proven that the optimal strategy is to error correct the channel to Bob, what Maurer calls "creating an error free channel", and then, if the channel to the eavesdropper is still noisy, perform privacy amplification. However, this works only when the channel to Eve is worse than the channel to Bob. To put this into perspective, if the communication is the one the cell phone tower (Alice) to your cell phone (Bob), the assumptions is equivalent to assuming that Eve is further away from the tower than you are; it cannot be in the middle. This is not a realistic assumption; if you are being targeted, getting in the middle is a fairly easy thing to do, and this argument is valid for pretty much any communication scenario.

Then enters two way communication. In Maurer's protocol, Bob is allowed to give feedback that Alice can use to improve the secrecy rates, as intuitively well explained by @{Meler Lawler}. Suddenly, a positive rate can be achieved even if Eve has a better channel as long as Eve has some noise. In the cell tower example, we are saying that we can achieve a positive rate even if Eve is closer to the tower as long as she is not tapped into the tower itself, we still need to make an assumption about a minimum distance of Eve from the tower. Of course, in this example, this assumption is still not realistic, even if stronger. However, Maurer argues that there are scenario where this assumption is reasonable, for example when Alice is a satellite in orbit. With this assumption, you can protect from any Eavesdropper that does not have the ability to travel to the satellite.

However, most communication does not travel via satellite. Even more, in most communications the assumption that Eve does not have a perfect or almost perfect eavesdrop is unrealistic (like for the example of the cell tower), and thus information-theoretic security cannot be used. This is why practical cryptography is based on the much more reasonable, even if unproven, computational assumptions. In computational crypto, the eavesdropper is assumed to have a perfect copy of the communication. Furthermore, computational crypto allows for keys much much shorter than the message, which is crucial for the majority of today's communication.

A final comment about quantum key distribution (QKD). Quantum mechanics allows to prove that the channel to the eavesdropper has a certain amount of noise (or more precisely, given the amount of noise to Bob, we can bound the information at Eve), thus making information-theoretic security realistic. However, it is still information-theoretic security and thus expensive. QKD and computational crypto (post-quantum) thus solve to disjoint problems: use QKD if your message is short/one-time but requires timeless security, use computational crypto if you have long/recurrent messages which secrecy has an expiry date (eg, messages making appointments which are not sensitive any more after the appointment has taken place).

$\endgroup$
0
$\begingroup$

The gist of it is, Alice is sharing a password with Bob over walkie-talkie with terrible static. Sometimes Bob has to ask Alice to repeat the last character. But Alice will never comply with Eve's requests for repeats. So Bob gets to learn the entire password while Eve does not.

This is because occasionally Eve will be unsure of the last character, while Bob will have heard it perfectly.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.