After sifting, two key-exchange stations A and B hold keys key_a and key_b of the same length that should be equal. A spy who measures qubits on the way leaves errors, so the stations sacrifice a few positions: they announce the bits at the positions in sample in public and count the mismatches, the sample positions i where key_a[i] != key_b[i].
The rule:
- If
sampleis empty, abort: an unchecked key is never trusted. - Otherwise abort when the error rate in percent is greater than
max_percent, that is when100 * mismatches > max_percent * len(sample). A rate exactly equal tomax_percentkeeps the key. - When they keep it, the announced bits are no longer secret: the final key is
key_awith every sample position removed, the other bits in their original order.
Write check_key(key_a, key_b, sample, max_percent) that returns ("abort", "") or ("keep", final_key).
Examples
Input: key_a = "1011001110", key_b = "1011001010", sample = [0, 2, 5, 9], max_percent = 11
Output: ('keep', '010111')
Explanation: the keys differ only at position 7, which is not in the sample:
0 mismatches. Removing positions 0, 2, 5, 9 leaves positions 1, 3, 4, 6, 7, 8.
Input: key_a = "1011001110", key_b = "1001001110", sample = [9, 2, 5, 0], max_percent = 25
Output: ('keep', '010111')
Explanation: 1 mismatch (position 2) in 4 is exactly 25 percent: not greater, so keep.
Input: key_a = "1011001110", key_b = "1001101110", sample = [2, 4, 6, 8], max_percent = 25
Output: ('abort', '')
Explanation: 2 mismatches in 4 is 50 percent.
Constraints
0 <= len(key_a) == len(key_b) <= 10**5; the positions insampleare distinct and in any order
Goals
- Estimate the error rate of a sifted key from a public sample of positions
- Apply an abort rule with an exact treatment of ties
- Remove the revealed positions from the final key