Byzantine Agreement

Functionality Description

Byzantine agreementTemplate:Cn is about reaching agreement in a network of $n$ players out of which $t$ players may be faulty. Each player starts with an input bit $b_{i}$ and the goal is for all correct players to output the same bit $d$ agreement, under the constraint that $d=b_{i}$ at least for some node $i$ validity. The hardness of this task depends on the failure model of the faulty (sometimes called adversary) players. In Byzantine agreement, the faulty players are assumed to show the most severe form of failure known as Byzantine failures. In this model, faulty players behave arbitrarily, can collude and even act maliciously trying to prevent correct players from reaching agreement. Byzantine agreement is an important problem in classical distributed systems, used to guarantee consistency amongst distributed data structures.

Tags: Quantum Enhanced Classical Functionality, Multi Party Protocols, Specific Task, consensus task, failure-resilient distributed computing.

Protocols

• BB84 Quantum Key Distribution: Prepare and Measure Network Stage
• Device Independent Quantum Key Distribution:Entanglement Distribution Network Stage

Device-Independent Quantum Key Distribution (DI-QKD) has better security guarantees than BB84 QKD.

Properties

A quantum key distribution protocol is secure if it is correct and secret. Correctness is the statement that Sender and Receiver share the same string of bits, namely the secret key, at the end of the protocol. Secrecy is the statement that the eavesdropper is totally ignorant about the final key.

• Correctness A QKD protocol is $\epsilon _{\rm {corr}}$-correct if the probability that the final key of Sender differs from the final key of Receiver, is smaller than $\epsilon _{\rm {corr}}$

• Secrecy A QKD protocol is $\epsilon _{\rm {sec}}$-secret if for every input state it holds that

${\frac {1}{2}}{\|{\rho _{K_{A}E}}-{\tau _{K_{A}}\otimes \rho _{E}}\|}_{1}\leq \epsilon _{\rm {sec}},$ where $\tau _{K_{A}}={\frac {1}{|K_{A}|}}\sum _{k}|{k}\rangle \langle {k}|_{A}$ is the maximally mixed state in the space of strings $K_{A}$, and ${\|\cdot \|}_{1}$ is the trace norm.

• A protocol implements a $(n,\epsilon _{\rm {corr}},\epsilon _{\rm {sec}},\ell )$-QKD if with $n$ rounds it generates an $\epsilon _{\rm {corr}}$-correct and $\epsilon _{\rm {sec}}$-secret key of size $\ell$ bits.

Further Information

The security definition presented here, are proven to be sufficient to guarantee universal composability for standard QKD in (2). For device-independent quantum key distribution, attacks presented in (1) show that security can be compromised if the same devices are used to implement another instance of the protocol.

1. PR (2014) discusses security of various QKD schemes composed in other cryptographic protocols.
2. BCK (2013) Analyses device independent QKD

*contributed by Bas Dirke, Victoria Lipinska, Glaucia Murta and Jeremy Ribeiro