Byzantine Agreement

Functionality Description

Byzantine agreementTemplate:Cn is about reaching agreement in a network of $n$ players out of which Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{1}{2}{\|{\rho_{K_AE}}-{\tau_{K_A}\otimes \rho_E}\|}_1\leq \epsilon_{\rm sec},} where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tau_{K_A}=\frac{1}{|K_A|}\sum_{k}|{k}\rangle\langle{k}|_A} is the maximally mixed state in the space of strings Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_A} , and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {\|\cdot \|}_1} is the trace norm.

• A protocol implements a Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n,\epsilon_{\rm corr},\epsilon_{\rm sec},\ell)} -QKD if with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} rounds it generates an Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon_{\rm corr}} -correct and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon_{\rm sec}} -secret key of size Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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