qkd_key_rate.protocols.classical.cascade module

Classes to perform a Cascade error correction protocol.

The Cascade error correction protocol can be used to correct errors in sifted bit strings. Errors are detected by calculating the parity between bitstrings of the two parties. The protocol first divides the messages in different blocks sizes and repeats this a number of passes times where the block size is doubled each pass. An error is detected and corrected when the parity for a block is odd. In case the parity for a block is even, it is still possible that (an even number of) errors exist. These errors can be detected in the next pass, when the block size is doubled and the message is shuffled. Given enough passes, all errors are expected to be corrected. However, the required communication of this protocol is high.

Typical usage example:

import numpy as np

from tno.quantum.communication.qkd_key_rate.base import Message, ParityStrategy, Permutations
from tno.quantum.communication.qkd_key_rate.protocols.classical.cascade import (
    CascadeCorrector,
    CascadeReceiver,
    CascadeSender,
)

message_length = 100000
error_rate = 0.05
input_message = Message([int(np.random.rand() > 0.5) for _ in range(message_length)])
error_message = Message(
    [x if np.random.rand() > error_rate else 1 - x for x in input_message]
)

number_of_passes = 8
sampling_fraction = 0.34
permutations = Permutations.random_permutation(
    number_of_passes=number_of_passes, message_size=message_length
)
parity_strategy = ParityStrategy(
    error_rate=error_rate,
    sampling_fraction=sampling_fraction,
    number_of_passes=number_of_passes,
)

alice = CascadeSender(message=input_message, permutations=permutations)
bob = CascadeReceiver(
    message=error_message,
    permutations=permutations,
    parity_strategy=parity_strategy,
)

corrector = CascadeCorrector(alice=alice, bob=bob)
summary = corrector.correct_errors()
class qkd_key_rate.protocols.classical.cascade.CascadeCorrector(alice, bob)[source]

Bases: Corrector

Cascade corrector

summary()[source]
Calculate a summary object for the error correction
  • original message

  • corrected message

  • error rate (before and after correction)

  • number_of_exposed_bits

  • key_reconciliation_rate

  • protocol specific parameters

Return type:

CascadeCorrectorOutput

class qkd_key_rate.protocols.classical.cascade.CascadeCorrectorOutput(input_alice, output_alice, input_bob, output_bob, input_error, output_error, output_length, number_of_exposed_bits, key_reconciliation_rate, number_of_communication_rounds, number_of_passes, switch_after_pass, sampling_fraction)[source]

Bases: CorrectorOutputBase

Data class for Cascade Corrector output

number_of_passes: int
sampling_fraction: float
switch_after_pass: int
class qkd_key_rate.protocols.classical.cascade.CascadeReceiver(message, permutations, parity_strategy, name=None)[source]

Bases: CascadeSender, ReceiverBase

This class encodes all functions only available to the receiver.

The receiver is assumed to have a string with errors and is thus assumed to correct the errors.

__init__(message, permutations, parity_strategy, name=None)[source]
Parameters:
  • message (Message) – Input message of the sender party

  • permutations (Permutations) – List containing permutations for each Cascade pass

  • name (Optional[str]) – Name of the receiver party

check_match_of_parities(alice, current_pass, current_block, block_size)[source]

Checks if the parity strings of alice and bob match.

This requires communication between the two parties. The parities of multiple blocks can be combined in a single message.

Parameters:
  • current_pass (int) – Index of current pass

  • current_block (int) – Index of current block

  • alice (CascadeSender) – The sending party

Return type:

bool

Returns:

Boolean if the parity strings of alice and bob match

correct_errors(alice)[source]

This is the main routine Errors in the strings alice and bob are found and corrected

An upper bound on the number of communications is estimated. This is however a loose upper bound. The cascade-routine makes it difficult to give tighter bounds

Parameters:

alice (SenderBase) – The sending party to correct errors with

Return type:

None

do_cascade(current_pass, current_block, block_size, alice, size_blocks_parities)[source]

Apply the Cascade error correction technique.

This routine corrects errors in previous passes that become apparent later. It is recursively used as long as new errors are found.

Parameters:
  • current_pass (int) – Index of current pass

  • current_block (int) – Index of current block

  • block_size (int) – Size of current block

  • alice (CascadeSender) – The sending party

  • size_blocks_parities (Tuple[Tuple[int, int], ...]) – For each pass the size of the block and number of blocks

Return type:

None

get_block_index(index, block_size, index_pass)[source]

Returns the block index corresponding to a certain index in a certain pass

Parameters:
  • index (int) – Index of a certain bit

  • block_size (int) – Size of current block

  • index_pass (int) – Index of the current pass

Return type:

int

Returns:

The block index corresponding to a certain bit index in a certain pass

get_error_index(index_block, index_pass, block_size, alice)[source]

Recursively checks the parity of half of the block of both parties.

Parameters:
  • index_block (int) – Index of the block in which we expect an error

  • index_pass (int) – Index of the current pass

  • block_size (int) – Size of current block

  • alice (CascadeSender) – The sending party

Return type:

int

Returns:

The position index of an error

get_error_rate()[source]

Gives the error rate, based on the found errors.

Return type:

float

get_prior_error_rate(alice, index_start=0, index_finish=None)[source]

Determine the initial error rate. This function is mainly for debugging purposes. Usually, the considered bits are private and this value cannot be computed.

Parameters:
  • alice (CascadeSender) – The sending party

  • index_start (int) – Start index of the message

  • index_finish (Optional[int]) – End index of the message

Return type:

float

Returns:

Initial error rate

class qkd_key_rate.protocols.classical.cascade.CascadeSender(message, permutations, name=None)[source]

Bases: SenderBase

This class encodes all functions available to both sender and receiver for the Cascade protocol.

__init__(message, permutations, name=None)[source]
Parameters:
  • message (Message) – Input message of the sender party

  • permutations (Permutations) – List containing permutations for each Cascade pass

  • name (Optional[str]) – Name of the sender party

build_parity_string(block_size, pass_number)[source]

Built a string of parities for the given block size.

Parameters:
  • block_size (int) – Message block size

  • pass_number (int) – Cascade permutation number

Return type:

None

get_parity(index_start, index_end, pass_number)[source]

Get the parity of a specific message block, taking into account the permutation applied in that specific pass.

Parameters:
  • index_start (int) – Start index of the message

  • index_end (int) – End index of the message

  • pass_number (int) – Cascade pass number

Return type:

int

Returns:

Parity of substring