Click here to start

Table of contents

The channel coding theorem and the security of binary randomization

Context: Theory of variable privacy

Randomization: binary-valued

Protocol as channel

Attacks on randomization - repeating the question

Error

Is the following an attack?

Theorem: Channel codes are DRQS attacks and vice versa

What kind of information transfer do DRQS attacks provide?

Shannon (1948) Channel Coding (“second”) Theorem Existence result; tight upper bound on transmission efficiency

Existence of reliable DRQS attacks

Types of attacks

Theorem: The rate of a reliable PRQS attack is tightly bounded above by protocol capacity

Theorem: Lower bound on total queries for arbitrarily small error

We have shown that

Why our approach is so powerful

This work was influenced by conversations with

Author: