Communication with secrecy constraints

Publisher Website
Google Scholar
Abstract
Let x, y, z be finite sets, X,Y random variables uniformly distributed over x×y, f a function from x×y to Z and 0≤ε&le1. A person PX knows X and a person PY knows Y and they want to exchange X and Y. An eavesdropper who knows their protocol listens to their communication in order to obtain information about f(X, Y). PX and PY want to ensure that for every value (x,y) of (X,Y) the eavesdropper's a priori and a posteriori probabilities of {f(X,Y)&equil;j} are ε-close for all j. Therefore, they encrypt some of the transmitted bits. The problem is to find a protocol that minimizes the number of bits encrypted in the worst case. Two kinds of protocols are considered: deterministic and randomized. For deterministic protocols it is shown that for all x,y, Boolean f (|Z|&equil;2) and ε>0, there exists a protocol that requires no more than 2• log(1/ε) + 16 bits. An example where log(1/ε) − 1 bits must be encrypted is given. For K valued functions (|Z|&equil;K) it is shown that at most CK(ε) bits must be encrypted (independent of x, y and f ). The results are extended to N persons communicating over a broadcast channel. The proofs rely on results concerning partitions of K valued matrices. For randomized Protocols it is shown that for all x,y Boolean f, and all possible joint distributions of X,Y (not only uniform), total secrecy (ε&equil;0) can be achieved using only two secret bits.

This publication has 0 references indexed in Scilit: