Hi all,
tomorrow's meeting is at the usual time and place. We'll hear from
Gilles Brassard regarding « Key Establishment à la Merkle in a Quantum
World ».
Here's the abstract of his talk:
In 1974, Ralph Merkle proposed the first unclassified scheme for secure
communications over insecure channels. When legitimate communicating
parties are willing to spend an amount of effort proportional to some
parameter N, an eavesdropper cannot break into their communication without
expending an effort proportional to N^2, which is quadratically more than
the legitimate effort. However, Merkle's original scheme becomes completely
insecure against a quantum adversary. Can its security be restored (at
least partially) if the legitimate parties are also allowed to use quantum
computation? We give two novel key agreement schemes in the spirit of
Merkle's. The first one requires an effort proportional to N^{5/3} to be
broken by a quantum adversary. In the second scheme, the legitimate parties
are purely classical, yet it cannot be broken by a quantum eavesdropper who
is not willing to work significantly harder than the legitimate parties,
making it the first provably secure post-quantum cryptographic scheme in
the random oracle model. In these schemes, as opposed to quantum key
distribution, all communication is classical. No prior knowledge of
cryptography will be assumed.
Joint work with Peter Høyer, Kassem Kalach, Marc Kaplan, Sophie Laplante
and Louis Salvail.
Best,
-joe