Secure Information Exchange for

Omniscience

Chung Chan (CityU)

Joint work with Navin Kashyap (IISc), Praneeth Kumar Vippathalla, (IISc) and Qiaoqiao Zhou (CUHK)

Audio slides: https://www.cs.cityu.edu.hk/~ccha23/isit2020

Secure information exchange

Formulation

Public

info.

\mathsf{F}_0
\mathsf{F}_1
\mathsf{F}
\mathsf{Z}_0

Private

info.

\mathsf{Z}_1
\mathsf{Z}_V
\mathsf{Z}_0^n:=(\mathsf{Z}_{0}^{(1)},\mathsf{Z}_{0}^{(2)},\dots,\mathsf{Z}_{0}^{(n)}) \text{ i.i.d.\ as }\mathsf{Z}_0
\mathsf{Z}_1^n
0
1

Network

Nodes

V

Target

info.

\mathsf{Y}_0
\mathsf{Y}_1
\mathsf{Y}_V

Censored

info.

\mathsf{X}_V
\mathsf{X}_0
\mathsf{X}_1

Interactive Public discussion

\frac{1}{n} I(\mathsf{F} \wedge \mathsf{Y}_{0}^n|\mathsf{Z}_{0}^n) \to u_{0} (\text{utility})
\frac{1}{n} I(\mathsf{F} \wedge \mathsf{Y}_{1}^n|\mathsf{Z}_{1}^n) \to u_{1}
\frac{1}{n} I(\mathsf{F} \wedge \mathsf{X}_{0}^n|\mathsf{Z}_{0}^n) \to l_{0} (\text{leakage})
\frac{1}{n} I(\mathsf{F} \wedge \mathsf{X}_{1}^n|\mathsf{Z}_{1}^n) \to l_{1}
\frac{1}{n} H(\mathsf{F}_{0})\to r_{0}\\(\text{discussion rate})
\frac{1}{n} H(\mathsf{F}_{1})\to r_{1}

Characterize \(\mathcal{R}:=\operatorname{closure}\{\text{$(u_V,\ell_V,r_V)$ achievable by some $\mathsf{F}$}\}\) given source \(P_{\mathsf{X}_V,\mathsf{Y}_V,\mathsf{Z}_V}\).

Related problems

  • Private information extraction problem [Asoodeh et al 19]
    • \( V =\{1,2\}\)
    • \( \mathsf{Z}_1 = (\mathsf{X}_2, \mathsf{Y}_2)\)  and \(\mathsf{X}_1\), \(\mathsf{Y}_1\), \(\mathsf{Z}_2\) are null
  • Information bottleneck [Tishby et al 99]
    • \( V =\{1,2\}\)
    • \(\mathsf{X}_1\), \(\mathsf{Y}_1\), \(\mathsf{X}_2\) and \(\mathsf{Z}_2\) are null

By restricting the source model, the problem reduces to:

Secure omniscience

A special scenario of secure information exchange

\frac{1}{n} I(\mathsf{F} \wedge \mathsf{X}_{\text{w}}^n|\mathsf{Z}_{\text{w}}^n) \to \ell_{\text{w}} \text{ (leakage)}
\mathsf{X}_{\text{w}}=\mathsf{Z}_U \text{ (censored info.)}
U
1
\text{w}
\text{wiretapper}
\text{users}
\mathsf{F}_1
\mathsf{F}
\text{unlimited } r_1
\mathsf{Z}_1
\mathsf{Z}_U
\mathsf{Z}_{\text{w}}

Characterize \(R_{\text{L}}:=\inf\{ \ell_{\text{w}}|(u_V,\ell_V,r_V)\in \mathcal{R},u_i=H(\mathsf{Z}_V|\mathsf{Z}_i)\,\forall i\in A\}\).

u_{1} = H(\mathsf{Z}_U|\mathsf{Z}_1) \text{ (omniscience)}
\text{helpers in } U\backslash A
\text{no target info.}
\text{active users in } A
h
\mathsf{Z}_h
\mathsf{F}_h
\text{unlimited } r_h

Example

With uniformly random and independent bits: \(\mathsf{X}_a,\mathsf{X}_b, \mathsf{X}_c\), 

\(R_L = 0\)

A=U
1
\text{w}
2
3
\mathsf{Z}_U
\mathsf{X}_a^n,\mathsf{X}_b^n
\mathsf{X}_b^n,\mathsf{X}_c^n
\mathsf{X}_a^n+\mathsf{X}_b^n+\mathsf{X}_c^n
\mathsf{X}_a^n+\mathsf{X}_b^n,\mathsf{X}_b^n+\mathsf{X}_c^n
\mathsf{X}_a^n+\mathsf{X}_b^n
\mathsf{X}_b^n+\mathsf{X}_c^n
\begin{aligned} \ell_{\text{w}} = \limsup_{n\to \infty} \frac1{n} I(\underbrace{\mathsf{F}}_{=\mathsf{Z}_{\text{w}}^n}\wedge \mathsf{Z}_U^n|\mathsf{Z}_{\text{w}}^n) = 0 \end{aligned}
\mathsf{X}_a^n+\mathsf{X}_b^n,\mathsf{X}_b^n+\mathsf{X}_c^n
\mathsf{X}_a
\mathsf{X}_b
\mathsf{X}_c
\mathsf{Z}_{\text{w}}
\mathsf{Z}_1
\mathsf{Z}_2
\mathsf{Z}_3
\mathsf{F}_1
\mathsf{F}_2
\mathsf{F}

Communication for Omniscience

[Csiszar and Narayan 04]

\frac{1}{n} I(\mathsf{F} \wedge \mathsf{X}_{\text{w}}^n|\mathsf{Z}_{\text{w}}^n) \to \ell_{\text{w}} \text{ (leakage)}
\mathsf{X}_{\text{w}}=\mathsf{Z}_U \text{ (censored info.)}
U
1
\text{w}
\text{wiretapper}
\text{users}
\mathsf{F}_0
\mathsf{F}
\text{unlimited } r_1
\mathsf{Z}_0
\mathsf{Z}_U
\mathsf{Z}_{\text{w}}

Characterize \(R_{\text{CO}}:=\inf\{ \sum_{i\in U} r_i|(u_V,\ell_V,r_V)\in \mathcal{R},u_i=H(\mathsf{Z}_V|\mathsf{Z}_i)\,\forall i\in A\}\).

u_{1} = H(\mathsf{Z}_U|\mathsf{Z}_1) \text{ (omniscience)}
\text{helpers in } U\backslash A
\text{no target info.}
\text{active users in } A
h
\mathsf{Z}_h
\mathsf{F}_h
\text{unlimited } r_h

Minimum leakage vs minimum discussion rate

From [Csiszar and Narayan 04],

$$R_{\text{CO}} = \min \left\{\left.\sum\nolimits_{i=1}^3 r_i\right| r_1+r_2 \geq 0, r_1+r_3 \geq 1, r_2+r_3 \geq 1\right\}$$

Claim: Any scheme with \((r_1,r_2,r_3)=(0,0,1)\) cannot have \(R_{\text{L}} = 0\)

\begin{aligned} A &:=\{1,2\} \subseteq U:=\{1,2,3\} \\ \mathsf{Z}_{\text{w}} &:= (\mathsf{X}_a+ \mathsf{X}_b, \mathsf{X}_b+ \mathsf{X}_c)\\ \mathsf{Z}_1 &:= (\mathsf{X}_a,\mathsf{X}_b) \\ \mathsf{Z}_2 &:= (\mathsf{X}_b, \mathsf{X}_c)\\ \mathsf{Z}_3 & := (\mathsf{X}_a+ \mathsf{X}_b+ \mathsf{X}_c) \end{aligned}

Proposition \(R_{\text{L}}\) and  \(R_{\text{CO}}\) are not simultaneously achievable in general.

\(\mathsf{F}=\mathsf{F}_3=\mathsf{Z}_3^n\)

\(R_{\text{CO}}\)-achieving scheme:

\(\ell_{\text{w}} =H(\mathsf{Z}_3|\mathsf{Z}_{\text{w}})=1\geq 0=R_{\text{L}}\)

Proposition  \(R_{\text{L}}=R_{\text{CO}}\) if \(\mathsf{Z}_{\text{w}}\) is null.

\(=1\) solved uniquely by \((r_1,r_2,r_3)=(0,0,1)\)

\begin{aligned} \ell_{\text{w}} = \limsup_{n\to \infty} \frac1{n} \underbrace{I(\mathsf{F}\wedge \mathsf{Z}_U^n|\mathsf{Z}_{\text{w}}^n)}_{\mathrlap{=I(\mathsf{F}\wedge \mathsf{Z}_U^n)=H(\mathsf{F})}} \end{aligned}

Main Results

Lower bound on minimum leakage

Theorem 1 For the secure omniscience scenario with \(|A| \geq 2\), 

$$\begin{aligned} R_{\text{L}} &\geq H(\mathsf{Z}_U|\mathsf{Z}_{\text{w}}) - C_{\text{S}}\\ &\geq R_{\text{CO}}(\mathsf{Z}_U|\mathsf{W}) - I(\mathsf{Z}_U \wedge \mathsf{Z}_{\text{w}} | \mathsf{W}) \end{aligned}$$

for any random variable \(\mathsf{W}\) satisfying the Markov condition \(I(\mathsf{W}\wedge \mathsf{Z}_U | \mathsf{Z}_{\text{w}})=0\).

$$\limsup_{n\to \infty} \frac1n I(\mathsf{K}\wedge \mathsf{F},\mathsf{Z}_{\text{w}}^n)=0\kern8em\text{(secrecy)}$$

$$\limsup_{n\to \infty}\frac1n H(\mathsf{K}|\mathsf{Z}_i^n,\mathsf{F})=0 \quad \forall i\in A \qquad\text{(recoverability)}$$

Definition (Multiterminal secret key agreement [Csiszar and Narayan 04]) 

C_{\text{S}}:=\sup\limits_{\mathsf{K},\mathsf{F}} \frac1nH(\mathsf{K}) \text{ s.t.}

Proof Idea

For the first lower bound, similar to an argument in [Csiszar and Narayan 04], $$C_{\text{S}}\geq H(\mathsf{Z}_U|\mathsf{Z}_{\text{w}})-R_{\text{L}}$$ by privacy amplication after secure omniscience.

The second lower bound follows from $$C_{\text{S}}\leq H(\mathsf{Z}_U|\mathsf{W}) - R_{\text{CO}}(\mathsf{Z}_U|\mathsf{W}),$$ an upper bound on \(C_{\text{S}}\) in [Csiszar and Narayan 04].

Theorem 1 For the secure omniscience scenario with \(|A| \geq 2\),

$$\begin{aligned} R_L &\geq H(\mathsf{Z}_U|\mathsf{Z}_{\text{w}}) - C_{\text{S}}\\ &\geq R_{\text{CO}}(\mathsf{Z}_U|\mathsf{W}) - I(\mathsf{Z}_U \wedge \mathsf{Z}_{\text{w}} | \mathsf{W}) \end{aligned}$$

for any random variable \(\mathsf{W}\) satisfying the Markov condition \(I(\mathsf{W}\wedge \mathsf{Z}_U | \mathsf{Z}_{\text{w}})=0\).

Example

\begin{aligned} A&=U:=\{1,2,3,4\} \\ \mathsf{Z}_{\text{w}} &:= \mathsf{X}_a+ \mathsf{X}_b + \mathsf{X}_c\\ \mathsf{Z}_1 &:= \mathsf{X}_a\\ \mathsf{Z}_2 &:= (\mathsf{X}_a,\mathsf{X}_b)\\ \mathsf{Z}_3 &:= (\mathsf{X}_b,\mathsf{X}_c)\\ \mathsf{Z}_4 &:= \mathsf{X}_c \end{aligned}

Is the lower bound achievable?

\(\because\) user 1 is active

\begin{aligned} R_{\text{L}} &\geq \underbrace{H(\mathsf{Z}_U|\mathsf{Z}_{\text{w}})}_{\kern-1em \mathrlap{ \begin{aligned}&=H(\mathsf{X}_{a},\mathsf{X}_{b},\mathsf{X}_{c}|\mathsf{X}_{a}+\mathsf{X}_{b}+\mathsf{X}_{c})\\ &= 2 \end{aligned}} } - \overbrace{C_{\text{S}}}^{\mathllap{ 1\geq\kern 0em }}\\ &= 2-1=1 \end{aligned}
C_{\text{S}}\leq H(\mathsf{Z}_1) =1

by Theorem 1

Theorem 1 For the secure omniscience scenario with \(|A| \geq 2\),

$$\begin{aligned} R_L &\geq H(\mathsf{Z}_U|\mathsf{Z}_{\text{w}}) - C_{\text{S}}\\ &\geq R_{\text{CO}}(\mathsf{Z}_U|\mathsf{W}) - I(\mathsf{Z}_U \wedge \mathsf{Z}_{\text{w}} | \mathsf{W}) \end{aligned}$$

for any random variable \(\mathsf{W}\) satisfying the Markov condition \(I(\mathsf{W}\wedge \mathsf{Z}_U | \mathsf{Z}_{\text{w}})=0\).

Main Results

Upper bound on minimum leakage

U
1
\text{w}
\mathsf{F}'_1
\mathsf{F}'
\mathsf{Z}_1
\mathsf{Z}_U
\mathsf{Z}_1^m
\mathsf{Z}_{\text{w}}
\mathsf{Z}_{\text{w}}^m

Theorem 2 For the secure omniscience scenario, 

$$R_{\text{L}} \leq \frac{1}{m} [ R_{\text{CO}}(\mathsf{Z}_U^m|\mathsf{F}') + I(\mathsf{Z}_U^m \wedge \mathsf{F}' | \mathsf{Z}_{\text{w}}^m) ] \leq R_{\text{CO}}$$

where \(\mathsf{F}'\) is a public discussion for block length \(m\geq 1\).

Proof idea

Theorem 2 For the secure omniscience scenario, 

$$R_{\text{L}} \leq \frac{1}{m} [ R_{\text{CO}}(\mathsf{Z}_U^m|\mathsf{F}') + I(\mathsf{Z}_U^m \wedge \mathsf{F}' | \mathsf{Z}_{\text{w}}^m) ] \leq R_{\text{CO}}$$

where \(\mathsf{F}'\) is a public discussion for block length \(m\geq 1\).

by setting \(m=1\) and \(\mathsf{F}'\) to null

concat.

\(\frac{n}{m}\) blocks

\begin{aligned} \ell''_{\text{w}} &\leq m \ell'_{\text{w}} + \sum\nolimits_{i\in U} r''_i \end{aligned}
\ell'_{\text{w}} = \limsup\limits_{m\to \infty} \frac{1}{m} I(\mathsf{Z}_U^m \wedge \mathsf{F}' | \mathsf{Z}_{\text{w}}^m)

How to attain omniscience?

U
1
\text{w}
\mathsf{F}'_1
\mathsf{F}'
\mathsf{Z}_1
\mathsf{Z}_U
\mathsf{Z}_1^m
\mathsf{Z}_{\text{w}}
\mathsf{Z}_{\text{w}}^m
U
1
\text{w}
\mathsf{Z}_1^m,\mathsf{F}'
\mathsf{Z}_U
\mathsf{Z}_1^n,{\mathsf{F}'}^{\frac{n}{m}}
\mathsf{Z}_{\text{w}}
\mathsf{Z}_{\text{w}}^n,{\mathsf{F}'}^{\frac{n}{m}}
\mathsf{F}''_1
\mathsf{F}''
r''_1

Omniscience possible with \(\sum_{i\in U} r''_i = R_{\text{CO}}(\mathsf{Z}_U^m|\mathsf{F}')\).

Example

\begin{aligned} A&=U:=\{1,2,3,4\} \\ \mathsf{Z}_{\text{w}} &:= \mathsf{X}_a+ \mathsf{X}_b + \mathsf{X}_c\\ \mathsf{Z}_1 &:= \mathsf{X}_a\\ \mathsf{Z}_2 &:= (\mathsf{X}_a,\mathsf{X}_b)\\ \mathsf{Z}_3 &:= (\mathsf{X}_b,\mathsf{X}_c)\\ \mathsf{Z}_4 &:= \mathsf{X}_c \end{aligned}

Do the upper and lower bounds match in general?

\begin{aligned} R_{\text{L}} &\geq 1 \end{aligned}

by Theorem 1

N.b., \(F'\) already achieves omniscience, so \(R_{\text{CO}}(\mathsf{Z}_U^m|\mathsf{F}')=0\).

\begin{aligned} R_{\text{L}} &\leq 1 \end{aligned}

by Theorem 2

\(m=1\) does not work but \(m=2\) works.

\begin{aligned} \mathsf{F}'_2 &= \overbrace{\begin{bmatrix} \mathsf{X}_{a}^{(1)}\\ \mathsf{X}_{a}^{(2)}\end{bmatrix}}^{\mathsf{X}_a^m} + \overbrace{\begin{bmatrix} 1 & 1\\ 1 & 0\end{bmatrix}}^{\boldsymbol{M}:=} \overbrace{\begin{bmatrix} \mathsf{X}_{b}^{(1)}\\ \mathsf{X}_{b}^{(2)}\end{bmatrix}}^{\mathsf{X}_b^m}\\ \mathsf{F}'_3 &= \mathsf{X}_c^m + (\boldsymbol{M}+\boldsymbol{I})\mathsf{X}_b^m \end{aligned}

Try

Theorem 2 For the secure omniscience scenario, 

$$R_{\text{L}} \leq \frac{1}{m} [ R_{\text{CO}}(\mathsf{Z}_U^m|\mathsf{F}') + I(\mathsf{Z}_U^m \wedge \mathsf{F}' | \mathsf{Z}_{\text{w}}^m) ] \leq R_{\text{CO}}$$

where \(\mathsf{F}'\) is a public discussion for block length \(m\geq 1\).

Main Results

Tightness of the upper and lower bounds

Theorem 3 For any finite linear source with two users, i.e., \(A=U=\{1,2\}\),

$$R_{\text{L}} = H(\mathsf{Z}_1,\mathsf{Z}_2|\mathsf{Z}_{\text{w}}) - I(\mathsf{Z}_1\wedge \mathsf{Z}_2|\mathsf{G})$$

where \(\mathsf{G}\) is the maximum common function of \(\mathsf{Z}_{\text{w}}\) and \(\mathsf{Z}_1\), i.e., the unique solution to $$J_{\text{GK}}(\mathsf{Z}_{\text{w}} \wedge \mathsf{Z}_1) :=\max\limits_{\mathsf{G}: H(\mathsf{G}|\mathsf{Z}_{\text{w}})=H(\mathsf{G}|\mathsf{Z}_1)=0} H(\mathsf{G}). $$

Theorem 1 With \(|A| \geq 2\),

$$R_L \geq H(\mathsf{Z}_U|\mathsf{Z}_{\text{w}}) - C_{\text{S}} $$

for any \(\mathsf{W}\) with \(I(\mathsf{W}\wedge \mathsf{Z}_U | \mathsf{Z}_{\text{w}})=0\).

Proof of \(\geq\)

  • Choose \(\mathsf{W}=\mathsf{G}\), and
  • substitute \(C_{\text{S}}=I(\mathsf{Z}_1\wedge \mathsf{Z}_2|\mathsf{G})\).

Proof of \(\leq\)

  • Choose \(m=1\), and
  • \(\mathsf{F}'\) to align with \(\mathsf{Z}_{\text{w}}\).

Theorem 2

$$R_{\text{L}} \leq \frac{1}{m} [ R_{\text{CO}}(\mathsf{Z}_U^m|\mathsf{F}') + I(\mathsf{Z}_U^m \wedge \mathsf{F}' | \mathsf{Z}_{\text{w}}^m) ]$$

with discussion \(\mathsf{F}'\)  for block length \(m\geq 1\).

Bounds do not match in general

\begin{aligned} A&:=\{1,2\} \subseteq U:=\{1,2,3\} \\ \mathsf{Z}_{\text{w}} &:= \mathsf{X}_a+ \mathsf{X}_b\\ \mathsf{Z}_1 &= \mathsf{Z}_2 := \mathsf{X}_a \\ \mathsf{Z}_3 &:= \mathsf{X}_b \end{aligned}

Claim Minimum leakage is \(R_L \geq 1.\)

\(\mathsf{F} =\mathsf{F}_3=\mathsf{X}_b^n\)

\(\ell_{\text{w}} =1\)

Optimal scheme:

\(R_{\text{L}} \geq H(\mathsf{Z}_U|\mathsf{Z}_{\text{w}}) - C_{\text{S}} = 1-1=0\)

\(C_{\text{S}}\leq H(\mathsf{Z}_1) =1\)

Proposition The lower bound on \(R_{\text{L}}\) is loose.

Theorem 1 With \(|A| \geq 2\),

$$R_L \geq H(\mathsf{Z}_U|\mathsf{Z}_{\text{w}}) - C_{\text{S}} $$

for any \(\mathsf{W}\) with \(I(\mathsf{W}\wedge \mathsf{Z}_U | \mathsf{Z}_{\text{w}})=0\).

Extensions and challenges

  • Tightness for hypergraphical sources can be proved.
  • More explicit characterization \(R_{\text{L}}\) using graph entropy is possible.
  • Lower bound can be improved for the counter-example.
  • \(R_{\text{L}}\) remains unknown for finite linear sources.
  • \(R_{\text{L}}\) for secure linear function computation, extending [Tyagi et. al 11].

References

I. Csiszár and P. Narayan, “Secrecy capacities for multiple terminals,” IEEE Transactions on Information Theory, vol. 50, no. 12, pp. 3047–3061, Dec. 2004.
A. Gohari and V. Anantharam, “Information-theoretic key agreement of multiple terminals—Part I,” IEEE Transactions on Information Theory, vol. 56, no. 8, pp. 3973 –3996, Aug. 2010.
S. Asoodeh, M. Diaz, F. Alajaji, and T. Linder, “Estimation efficiency under privacy constraints,” IEEE Transactions on Information Theory, vol. 65, no. 3, pp. 1512–1534, March 2019.
N. Tishby, F. C. Pereira, and W. Bialek, “The information bottleneck method,” in Thirty-Seventh Annual Allerton Conference on Communication, Control, and Computing, Sep. 1999.

H. Tyagi, P. Narayan, and P. Gupta, “When is a function securely computable?” IEEE Transactions on Information Theory, vol. 57, no. 10, pp. 6337–6350, 2011.