多信道数据碎片化传输安全性证明

摘要

基于信息数据碎片化的多道隔离传输，是在信息传输过程中保证其安全性的常用方法之一，但其缺乏可证明安全性理论和测评方法。本文形式化地定义了一个多道碎片化传输系统，包括数据的加密、碎片切分多道传输和重组功能。从多信道传输过程中数据泄露概率分析，定义多道碎片化传输技术的可证明安全等级。建立一套多信道数据碎片化传输的安全等级评估方法，从理论角度对于安全等级评估方法的有效性加以验证，为多信道数据碎片化传输技术的实现提供理论指导，同时为多信道数据碎片化传输系统的安全评测提供借鉴。该方法也适用于数据碎片化存储及传输相关领域的安全性分析。

关键词

网络安全; 可证明安全性; 多信道传输系统; 碎片化技术

为实现大数据量的通信，多信道技术已经得到广泛应用，这些技术包括多输入多输出(Multiple-In Multiple-Out，MIMO)、利用光的轨迹角动量(Orbital Angular Momentum，OAM)进行多路复用和通过OAM进行直接调制等^[1]。然而，随着攻击方式日益多样和系统结构越发复杂，使用传统方法保护信息可能代价高昂，需要新的视角和新的理论基础。

目前，已有大量研究通过对传输与存储的数据进行分片，以求获得更高的传输效率及安全性。文献[2]提出了基于数据分片多径传输(Data Fragmentation Multipath Transmission，DFMT)的安全自由空间光通信系统，将消息切分为碎片，通过不同的信道随机传输，但是并未阐述如何进行碎片切分。802.11提供了一种高效的分片方案^[3]，旨在减少信道错误对于完整性的影响，但其缺点在于分片的大小固定，造成传输效率降低。在多信道传输的前提下，文献[4]建议将信息进行分段，以便截获少量片段的攻击者不能够获得任何有效信息。现有的数据碎片化技术旨在增强数据操作过程，减少处理时间，优化存储，增加操作灵活性，促进数据分发和传输，但没有专门设计数据安全的思想^[5]。可证明安全是目前多数安全协议的设计手段，定义合适的安全目标、建立适当的敌手模型是讨论可证明安全性的前提条件^[6]。在建立敌手模型时，将碎片化传输过程中的攻击者根据实际攻击类型划分为协作与非协作两类。信息熵由Shannon在文献[7]中提出，作为其拓展，Hastad 等在文献[8]中使用不可区分性对于伪熵进行定义。根据伪熵与伪随机性的关系和不可预测性与伪随机性等价^[9]，将方案的安全目标定义为敌手通过已知信息预测出其他信道信息的概率，并且分析它们之间的强弱关系。

现有研究表明，给定一个随机序列，将其切分为$k$个不同的随机序列，而不损失每个碎片的熵，此任务困难的程度等价于猜测k位的停机问题^[10]，考虑这个问题的弱化版本，即对于伪熵可加性的研究。熵描述了序列的信息量，通过对比整体序列的熵与其片段的熵，可以获知不同片段信息之间的独立关系，即通过某一片段信息无法预测剩余片段信息，那么是否能够通过伪熵的可加性判断此类问题。已知碎片化方案的安全目标通过信息的不可预测性进行定义，提出碎片化技术三级安全标准，利用伪熵的可加性对于前2级进行定义，最高级则使用伪随机性定义，并从理论角度对其有效性进行验证。

本文提出了一个碎片化系统，系统能够实现对于已加密数据的切分和重组功能。根据实际攻击类型将攻击者分为协作与非协作2类，提出了隔离安全性的定义，以敌手通过已知信息预测其他信道信息的概率大小区分隔离安全的强弱。提出3级碎片化技术安全评估等级，并对其有效性进行测评。

1 基础知识

一个从非负整数映射到非负实数的函数$\epsilon (n)$，若对于任意整数$c\ge \mathrm{1}$，均存在$n_{\mathrm{0}}>\mathrm{0}$，使得对于所有$n>n_{\mathrm{0}}$都有$\epsilon (n)<\mathrm{1}/n^c$，称其为可忽略函数。

设$X$和$Y$是取值在有限集合$S$中的随机变量，定义$X$和$Y$的统计距离为：

$$\mathrm{D}\mathrm{i}\mathrm{s}\mathrm{t}(X,Y)=\frac{\mathrm{1}}{\mathrm{2}}\sum _{s\in S}|\mathrm{P}\mathrm{r}[X=s]-\mathrm{P}\mathrm{r}[Y=s]|$$

(1)

同样地，

$$\mathrm{D}\mathrm{i}\mathrm{s}\mathrm{t}(X,Y)=\underset{S\text{'}\subset S}{\mathrm{m}\mathrm{a}\mathrm{x}}|\mathrm{P}\mathrm{r}[X\in S\text{'}]-\mathrm{P}\mathrm{r}[Y\in S\mathrm{\text{'}}]|$$

(2)

$\mathrm{若}\mathrm{D}\mathrm{i}\mathrm{s}\mathrm{t}(X,Y)\le \epsilon$，称$X$和$Y$是$\epsilon$-close的。

设$X=\{X_n{\}}_{n\ge \mathrm{0}}\mathrm{与}Y=\{Y_n{\}}_{n\ge \mathrm{0}}$为随机变量序列，对于每个$n>\mathrm{0}$，$X_n$和$Y_n$取有限集合$S_n$中的值。如果$\mathrm{D}\mathrm{i}\mathrm{s}\mathrm{t}(X,Y)$是可忽略的，则称$X$和$Y$是统计不可区分的(statistic indistinguishable)。出于计算目的，通常将集合$S_n$编码为多项式长度的位串。对于任意输出0或1的概率算法$A$，将$A$(关于$X$和$Y$)的优势(advantage)定义为函数：

$$\mathrm{D}\mathrm{i}\mathrm{s}{\mathrm{t}}_A^{X,Y}(n)=\left|\mathrm{P}\mathrm{r}[A({\mathrm{1}}^n,X_n)=\mathrm{1}]-\mathrm{P}\mathrm{r}[A({\mathrm{1}}^n,Y_n)=\mathrm{1}]\right|$$

(3)

如果对于所有概率多项式时间算法$A,\mathrm{D}\mathrm{i}\mathrm{s}{\mathrm{t}}_A^{X,Y}(n)$可忽略，则说$X$和$Y$是计算不可区分的(computational indistinguishable)。

若存在分布$X=\{X_n{\}}_{n\ge \mathrm{0}}$与均匀分布$\mathit{𝒰}=\{{\mathit{𝒰}}_n{\}}_{n\ge \mathrm{0}}$，对于所有概率多项式时间算法$A$,$\mathrm{D}\mathrm{i}\mathrm{s}{\mathrm{t}}_A^{X,\mathit{𝒰}}(n)$可忽略，则称分布$X=\{X_n{\}}_{n\ge \mathrm{0}}$是伪随机的(pseudo-random)。

$$\mathrm{D}\mathrm{i}\mathrm{s}{\mathrm{t}}_A^{X,\mathit{𝒰}}(n)=\left|\mathrm{P}\mathrm{r}\left[A\left({\mathrm{1}}^n,X_n\right)=\mathrm{1}\right]-\mathrm{P}\mathrm{r}\left[A\left({\mathrm{1}}^n,{\mathit{𝒰}}_n\right)=\mathrm{1}\right]\right|$$

(4)

定义$s$是不可预测的，若对于任意概率多项式时间算法$A$和任意正整数$n$，存在可忽略函数$\epsilon (n)$满足：

$$\left|\mathrm{P}\mathrm{r}\left[A\left(s\left[\mathrm{1}\right]‖s\left[\mathrm{2}\right]‖\dots ‖s\left[n-\mathrm{1}\right]\right)=\mathrm{s}\left[n\right]\right]-\frac{\mathrm{1}}{\mathrm{2}}\right|\le \epsilon (n)$$

(5)

分布族$D=\{D_n{\}}_{n\ge \mathrm{0}}$是伪随机的，当且仅当对任意字符串$s\leftarrow D_n$，均是不可预测(unpredictable)的。

YAO Andrew C在文献[9]中证明了不可预测性(unpredictability)和伪随机性对于位序列是等价的。若一个多项式时间算法$G:{\{\mathrm{0,1}\}}^n\to {\{\mathrm{0,1}\}}^{l(n)}$为伪随机数生成器，当且仅当$\forall n:l(n)>n$且$\{G(U_n{)\}}_{n\in \mathit{\mathbb{N}}}$是一个伪随机分布序列。

根据Shannon在文献[7]中提出的信息熵(entropy)概念，设$x$为事件$\mathit{𝕏}$的离散随机变量，$x$发生的概率函数为$p(x)=\mathrm{P}\mathrm{r}\{X=x\},x\in \mathit{𝕏}$。离散随机变量$X$的信息熵$H\left(X\right)$定义为：

$$H\left(X\right)=-\sum _{x\in \mathit{𝕏}}p(x)logp(x)$$

(6)

作为信息熵的推广，Hastad等^[8]使用不可区分性定义了伪熵(pseudo-entropy)，假设存在2个分布$X=\{X_n{\}}_{n\ge \mathrm{0}}$和$Y=\{Y_n{\}}_{n\ge \mathrm{0}}$，分布$X$的熵为$n$。如果对于任意概率多项式时间算法$A$，$\mathrm{D}\mathrm{i}\mathrm{s}{\mathrm{t}}_A^{X,Y}(n)$可忽略，则不存在多项式区分算法能够区分分布$X$和$Y$，$X$的伪熵为$n$。

2 碎片化技术形式化描述

在数据外包的背景下，加密与数据碎片化的联合使用第一次被Aggarwal等提出^[11]，提议通过在2个独立的数据库服务器上拆分信息和在必要时加密信息从而保证隐私要求。但此提议的主要限制在于，数据隐私依赖于2个服务器之间完全没有通信，在现实环境中，这个假设过于强大，并且服务器与用户之间的勾结很容易造成隐私被侵犯。Ciriani^[12]提出的解决方案克服了Aggarwal等方案的局限性，首先将信息分割为不同片段，然后进行数据存储，最后将加密密钥提供给需要访问信息的授权用户。当前关注数据碎片的安全性方面最先进的方法依赖加密来确保数据的机密性^[5]。故将碎片化技术形式化地抽象为数据的加密与切分重组过程，加密过程保证信息的机密性，碎片化过程专注于在单点数据泄漏的情况下限制对整体安全性的影响。

定义1   数据碎片化方案。设有3个概率多项式时间的图灵机组成一个碎片化非对称密钥加密方案$\Psi =<\mathrm{G}\mathrm{e}\mathrm{n},\mathrm{F}\mathrm{r}\mathrm{a},\mathrm{R}\mathrm{e}\mathrm{c}>,$其中$\mathrm{F}\mathrm{r}\mathrm{a},\mathrm{R}\mathrm{e}\mathrm{c}$分别为碎片化算法和碎片重组算法，$\mathrm{G}\mathrm{e}\mathrm{n}$表示密钥生成算法，满足：

$\mathrm{F}\mathrm{r}\mathrm{a}$和$\mathrm{R}\mathrm{e}\mathrm{c}$利用密钥生成算法$\mathrm{G}\mathrm{e}\mathrm{n}$和安全参数$\lambda$生成了密钥$k$：

$$\mathrm{G}\mathrm{e}\mathrm{n}:({\mathrm{1}}^{\lambda })⟼k$$

(7)

$\mathrm{F}\mathrm{r}\mathrm{a}$利用加密密钥$k$和消息$c\in {\{\mathrm{0,1}\}}^{*}$作为输入，输出碎片化后的密文$(c_{\mathrm{1}},c_{\mathrm{2}},···,c_l)$：

$$\mathrm{F}\mathrm{r}\mathrm{a}:(k,{\mathrm{1}}^{l}c)⟼(c_{\mathrm{1}},c_{\mathrm{2}},···,c_l)$$

(8)

$\mathrm{R}\mathrm{e}\mathrm{c}$利用解密密钥$k$和碎片化密文$(c_{\mathrm{1}},c_{\mathrm{2}},···,c_l)\in {\{\mathrm{0,1}\}}^{*}$作为输入，输出原始数据$c$：

$$\mathrm{R}\mathrm{e}\mathrm{c}:[k,\left(c_{\mathrm{1}},c_{\mathrm{2}},···,c_l\right)]⟼c$$

(9)

一个碎片化系统是正确的，如果对任意原始数据$c\in {\{\mathrm{0,1}\}}^{*}$，经过加密后的待传输数据$c$再通过解密后应当与原始数据输入相同，即：

$$\mathrm{R}\mathrm{e}{\mathrm{c}}_k\left(\mathrm{F}\mathrm{r}{\mathrm{a}}_k\left({\mathrm{1}}^l,c\right)\right)=c$$

(10)

或

$$\mathrm{P}\mathrm{r}\left[\mathrm{R}\mathrm{e}{\mathrm{c}}_k(\mathrm{F}\mathrm{r}{\mathrm{a}}_k({\mathrm{1}}^l,c))\right]=\mathrm{1}$$

(11)

简记第$i$个碎片的碎片化算法$\mathrm{F}\mathrm{r}{\mathrm{a}}_{k,i}:c⟼c_i$，给定$i,k\in \mathit{\mathbb{N}}$，定义分布$\mathrm{F}\mathrm{r}{\mathrm{a}}_{k,i}(·)$的熵(entropy)为$H\left(\mathrm{F}\mathrm{r}{\mathrm{a}}_{k,i}\right)=H\left(c_i\right)$。碎片化算法的伪熵(pseudo-entropy)$PH\left(\mathrm{F}\mathrm{r}{\mathrm{a}}_{k,i}\right)=PH\left(c_i\right)\ge h$，如果存在一个分布$F$，满足$H\left(F\right)=h$，$\mathrm{则}\mathrm{F}\mathrm{r}{\mathrm{a}}_i$和$F$不可区分，即：

$$\left|\mathrm{P}\mathrm{r}[\mathrm{𝒟}(\mathrm{F}\mathrm{r}{\mathrm{a}}_{k,i}(c))=\mathrm{1}]-\mathrm{P}\mathrm{r}[\mathrm{𝒟}(F(c))=\mathrm{1}]\right|\le \epsilon (\lambda$$)

(12)

同理，说碎片化算法的伪熵$PH\left(\mathrm{F}\mathrm{r}{\mathrm{a}}_{k,i}\right)<h$，如果对任意满足$H\left(F\right)=h$的函数$F$，$\mathrm{F}\mathrm{r}{\mathrm{a}}_i$和$F$是可区分的，即存在正整数$c$和一个多项式时间的区分器$\mathrm{𝒟}$，使得：

$$\left|\mathrm{P}\mathrm{r}[\mathrm{𝒟}(\mathrm{F}\mathrm{r}{\mathrm{a}}_{k,i}(c))=\mathrm{1}]-\mathrm{P}\mathrm{r}[\mathrm{𝒟}(F(c))=\mathrm{1}]\right|>{\lambda }^{-c}$$

(13)

显然有$PH\left(c_i\right)\ge H\left(c_i\right)$成立，因为概率分布和自身一定是不可区分的。并且根据定义，若$\mathrm{F}\mathrm{r}{\mathrm{a}}_{k,i}$是伪随机的，那么其伪熵达到最大值，即$PH\left(c_i\right)=n$。

考虑到敌手的实际攻击方式，故将攻击者划分为2类：一类为可协作攻击者；另一类则为不可协作攻击者。另外考虑到截获片段的攻击者通过获得的片段计算剩余数据的能力，即在单点数据泄漏的情况下对整体安全性的影响，提出以任意攻击者通过以获取信息计算出其他任意信道上数据的概率为度量，以此界定信道隔离安全的强弱。

定义2   多信道的隔离可证明安全。对于一个$l$-信道数据传输上的碎片化方案$\Psi =<\mathrm{G}\mathrm{e}\mathrm{n},\mathrm{F}\mathrm{r}\mathrm{a},\mathrm{R}\mathrm{e}\mathrm{c}>$，设信道中的数据分别为$(c_{\mathrm{1}},c_{\mathrm{2}},\cdots ,c_l)$，假设每个信道监听者$A_i$只能够获取对应信道的全部数据$c_i$。定义监听者的可协作性：

1) 可协作攻击者：攻击者间可以分享监听到的数据；

2) 不可协作攻击者：攻击者间不可分享监听到的数据；

3) 进而定义攻击者的获取目标，即信道隔离安全的强弱。

信道隔离安全：任意攻击者$A_k$的优势

$$Ad{v}_{\Psi ,A_k}(\lambda )=\left|\mathrm{P}\mathrm{r}\left[A_k\left(c_k\right)=c_i\right]-\mathrm{1}/{\mathrm{2}}^{H(c_i)}\right|$$

(14)

表示计算出其他任意信道上的数据的概率与$\mathrm{1}/{\mathrm{2}}^{H(c_i)}$的差。其中$H(c_i)$是指数据$c_i$的信息熵。

若对于任意攻击者，其优势可忽略，则称其是信道隔离安全。强信道隔离安全：任意攻击者$A_k$的优势

$$Ad{v}_{\Psi ,A_k}(\lambda )=\left|\mathrm{P}\mathrm{r}\left[A_k\left(c_k\right)=c_i\right]-\mathrm{1}/{\mathrm{2}}^{|c_i|}\right|$$

(15)

表示计算出其他任意信道上的数据的概率与$\mathrm{1}/{\mathrm{2}}^{|c_i|}$的差。其中$|c_i|$表示数据$c_i$的长度。若对于任意攻击者，其优势可以忽略，则称其是信道强隔离安全。

一个$l$-信道数据传输在不可协作攻击下是(强)安全的，如果满足对于任意常数$p=\mathrm{1}/{\mathrm{2}}^{H\left(c_i\right)}$（$p=\mathrm{1}/{\mathrm{2}}^{\left|c_i\right|}$），任意非空信道数据$c_i$和任意攻击者$A_k$($k\ne i$)，均有：

$$\left|\mathrm{P}\mathrm{r}\left[A_k\left(c_k\right)=c_i\right]-p\right|\le \epsilon \left(\lambda \right)$$

(16)

称一个$l$-信道数据传输在可协作攻击下是(强)安全的，如果满足对于任意常数$p=\mathrm{1}/{\mathrm{2}}^{H\left(c_i\right)}$（$p=\mathrm{1}/{\mathrm{2}}^{\left|c_i\right|}$），任意非空信道数据$c_i$和任意攻击者$A_k$（$k\ne i$），均有：

$$\left|\mathrm{P}\mathrm{r}\left[A_k\left(c_{-\mathrm{1}}\right)=c_i\right]-p\right|\le \epsilon \left(\lambda \right)$$

(17)

其中$c_{-\mathrm{1}}=\left(c_{\mathrm{1}},c_{\mathrm{2}},\cdots ,c_{i-\mathrm{1}},c_{i+\mathrm{1}},\cdots ,c_l\right)$。

若一个多信道安全传输是隔离安全的，则称其为多信道隔离安全传输。

3 安全等级定义及安全性证明

注意到，对熵的可加性研究已有定论，故对其弱化版本，即伪熵的可加性研究产生了兴趣，将碎片化方案安全评估等级分为安全、强安全和伪随机级别，前两级由伪熵的可加性进行定义，根据第2节所定义的安全目标和敌手模型，对于所提出的安全评估等级的有效性进行了验证。

定义3   碎片化方案安全评估等级。设$\Psi =<\mathrm{G}\mathrm{e}\mathrm{n},\mathrm{F}\mathrm{r}\mathrm{a},\mathrm{R}\mathrm{e}\mathrm{c}>\mathrm{是一}\mathrm{个碎}\mathrm{片化}\mathrm{系统}$，$k$为由密钥生成算法$\mathrm{G}\mathrm{e}\mathrm{n}$生成的密钥。称$\Psi$是安全的，若对于任意的数据$c\in {\{\mathrm{0,1}\}}^{*}$，任意正整数$i,j\in \mathit{\mathbb{N}}$，$(i\ne j)$，有：

$$PH\left(c_i\right)+PH\left(c_j\right)=PH\left(c_i\Vert c_j\right)$$

(18)

称$\Psi$是强安全的，若对于任意的数据$c\in {\{\mathrm{0,1}\}}^{*}$，有：

$${\displaystyle \sum _{i=\mathrm{1}}^l}PH(c_i)=PH\left(\mathrm{F}\mathrm{r}{\mathrm{a}}_k(c)\right)=PH\left(c_{\mathrm{1}}\Vert c_{\mathrm{2}}\Vert \cdots \Vert c_l\right)$$

(19)

安全碎片化系统的定义使用伪熵来刻画，要求不同碎片拼接以后的伪熵，不比每个碎片的伪熵求和小。对于任意2个分布族$X,Y$，满足：

$$PH\left(X\right)+PH\left(Y\right)\ge PH\left(X\Vert Y\right)$$

(20)

若存在分布$Z$与$X\Vert Y$不可区分，且满足$H\left(Z\right)=PH\left(X\Vert Y\right)$，注意到仅仅有可忽略概率下$\mathrm{分布}Z$的样本长度和分布$X\Vert Y$的不相等。令$Z=Z_X\Vert Z_Y$，那么$H\left(Z\right)=H\left(Z_X\Vert Z_Y\right)\le H\left(Z_X\right)+H\left(Z_Y\right)$。显然有$X$与$Z_X$不可区分，而$Y$与$Z_Y$不可区分。从而

$$PH\left(X\Vert Y\right)=H\left(Z\right)\le H\left(Z_X\right)+H\left(Z_Y\right)\le PH\left(X\right)+PH\left(Y\right)$$

(21)

因此安全碎片化方案要求碎片化的过程不增加伪熵。

定理1   若一个碎片化系统$\Psi$是强安全的，那么一定是安全的。

需要证明若：

$${\displaystyle \sum _{i=\mathrm{1}}^l}PH(c_i)=PH\left(\mathrm{F}\mathrm{r}{\mathrm{a}}_k(c)\right)$$

(22)

成立，那么对任意$i,j\in \mathit{\mathbb{N}}$，$(i\ne j)$，有：

$$PH\left(c_i\right)+PH\left(c_j\right)=PH\left(c_i\Vert c_j\right)$$

(23)

不妨设

$$PH\left(c_{\mathrm{1}}\right)+PH\left(c_{\mathrm{2}}\right)>PH\left(c_{\mathrm{1}}\Vert c_{\mathrm{2}}\right)$$

(24)

那么$$PH\left(\mathrm{F}\mathrm{r}{\mathrm{a}}_k(c)\right)\le PH\left(c_{\mathrm{1}}\Vert c_{\mathrm{2}}\right)+{\displaystyle \sum _{i=\mathrm{3}}^l}PH(c_i)<{\displaystyle \sum _{i=\mathrm{1}}^l}PH(c_i)$$

(25)

给出一个更强的碎片化方案$\Psi$定义，利用伪随机性来刻画。事实上，不需要也不一定保证碎片中出现冗余的字段，哪怕在计算上是可以简单找到的，但各个碎片出现冗余字段并不一定影响其信道隔离安全性。

定义4   伪随机性碎片化方案。设$\Psi =<\mathrm{G}\mathrm{e}\mathrm{n},\mathrm{F}\mathrm{r}\mathrm{a},\mathrm{R}\mathrm{e}\mathrm{c}>\mathrm{是一}\mathrm{个碎}\mathrm{片化}\mathrm{系统}$，设$k$为密钥生成器$\mathrm{G}\mathrm{e}\mathrm{n}$生成的密钥，对于任意的数据$c\in {\{\mathrm{0,1}\}}^{*}$，若$\mathrm{F}\mathrm{r}{\mathrm{a}}_k(c)$是伪随机的，则称$\Psi$是伪随机的。

定理2   若一个碎片化方案$\Psi$是伪随机的，则$\Psi$是强安全的。

证明：若一个碎片化系统$\Psi$是伪随机的，根据定义，其伪熵$PH\left(\mathrm{F}\mathrm{r}{\mathrm{a}}_k(c)\right)=\left|\mathrm{F}\mathrm{r}{\mathrm{a}}_k(c)\right|$。又由于一个伪随机串的子串也是伪随机的，有$PH\left(c_i\right)=|c_i|$，因此：

$$PH\left(\mathrm{F}\mathrm{r}{\mathrm{a}}_k(c)\right)={\displaystyle \sum _{i=\mathrm{1}}^l}PH(c_i)$$

(26)

即该碎片化系统是强安全的。

注意到若一个串是伪随机的，那么将该串各比特位做一个随机置换也是伪随机的，因此碎片在各信道的分配不影响其安全性。

方案实现的安全目标和敌手的攻击方式定义了一个密码方案的安全性，将隔离安全与强隔离安全作为方案所需要实现的安全目标，将协作攻击与非协作攻击作为敌手的攻击方式，接下来将对碎片化方案的3个安全级别进行证明。

定理3   若一个多信道的碎片化系统是安全的，则该多信道数据传输在非协助攻击下是隔离安全的。

证明：考虑$l-$多信道，设第$i$信道中存在一个监听者为$A_i$，$i\in (\mathrm{1,2},···,l)$。假设$A_i$只能获取所在信道上的所有数据，记作$c_i$，其中$\mathrm{F}\mathrm{r}{\mathrm{a}}_k({\mathrm{1}}^l,c)\to (c_{\mathrm{1}},c_{\mathrm{2}},···,c_l)$。

由于碎片化系统$\Psi$是安全的，即对于任意的数据$c\in {\{\mathrm{0,1}\}}^{*}$和任意正整数$i,j\in \mathit{\mathbb{N}}$，有：

$$PH\left(c_i,c_j\right)=PH\left(c_i\right)+PH\left(c_j\right)$$

(27)

那么存在分布族$Z=X_Z\Vert Y_Z$，满足：

$$H\left(Z\right)=H\left(X_Z\Vert Y_Z\right)$$，$$H\left(X_Z\right)=PH\left(c_i\right)$$，$$H\left(Y_Z\right)=PH\left(c_j\right)$$

(28)

并且$c_i$与$X_Z$不可区分，$c_j$与$X_Y$不可区分，$c_i\Vert c_j$与$Z$不可区分。

以往证明在使用了安全的碎片化系统$\Psi$下，对于任意$i\in \left\{\mathrm{1,2},···,l\right\}$，$A_i$无法获知其他的非空数据$c_j(j\ne i)$，即：

$$\mathrm{P}\mathrm{r}\left[A_i\left(c_i\right)=c_j\right]\le \frac{\mathrm{1}}{{\mathrm{2}}^{PH(c_j)}}+\epsilon (\lambda )\le \frac{\mathrm{1}}{{\mathrm{2}}^{H(c_j)}}+\epsilon (\lambda )$$

(29)

使用反证法，若结论不成立，则存在算法$B$和多项式$p(·)$使得：

$$\mathrm{P}\mathrm{r}\left[B\left(c_i\right)=c_j\right]=\frac{\mathrm{1}}{{\mathrm{2}}^{PH\left(c_j\right)}}+\frac{\mathrm{1}}{p(\lambda )}$$

(30)

那么可以利用算法$B$构造区分器$\mathit{𝒟}$。设对于输入$x\Vert y$，若$B\left(x\right)=y$，则$\mathit{𝒟}$输出1，否则输出0。那么

$$\mathrm{P}\mathrm{r}\left[\mathit{𝒟}\left(X_Z\Vert Y_Z\right)=\mathrm{1}\right]\le \frac{\mathrm{1}}{{\mathrm{2}}^{H(Y_Z)}}$$

(31)

此时对任意可忽略函数$\epsilon \left(·\right)$，都有：

$$\left|\mathrm{P}\mathrm{r}\left[\mathit{𝒟}\left(c_i\Vert c_j\right)=\mathrm{1}\right]-\mathrm{P}\mathrm{r}\left[\mathit{𝒟}\left(X_Z\Vert Y_Z\right)=\mathrm{1}\right]\right|=\left|\frac{\mathrm{1}}{{\mathrm{2}}^{PH\left(c_j\right)}}+\frac{\mathrm{1}}{p\left(\lambda \right)}-\frac{\mathrm{1}}{{\mathrm{2}}^{H\left(Y_Z\right)}}\right|=\frac{\mathrm{1}}{p(\lambda )}$$

(32)

并非可忽略，这与假设矛盾。

定理4的证明本质上与定理3的证明相同。

定理4   若一个多信道的碎片化系统是强安全的，则该多信道数据传输在协作攻击下是隔离安全的。

证明：考虑$l-$多信道，设第$i$信道中存在一个监听者为$A_i$，$i\in (\mathrm{1,2},···,l)$。假设$A_i$只能获得所在信道上的所有数据，记作$c_i$，其中$c_{-i}=c_{\mathrm{1}}\Vert c_{\mathrm{2}}\Vert ···\Vert c_{i-\mathrm{1}}\Vert c_{i+\mathrm{1}}\Vert ···\Vert c_l$且$(c_{\mathrm{1}},c_{\mathrm{2}},···,c_l)\leftarrow \mathrm{F}\mathrm{r}{\mathrm{a}}_k({\mathrm{1}}^l,c)$。

由于碎片化系统$\Psi$是强安全的，即对于任意的数据$c\in {\{\mathrm{0,1}\}}^{*}$和任意正整数$i,j\in \mathit{\mathbb{N}}$，有：

$$PH\left(c_{-i}\Vert c_j\right)=PH\left(c_{-i},c_j\right)=PH\left(c_{-i}\right)+PH\left(c_j\right)$$

(33)

那么存在分布族$Z=X_Z\Vert Y_Z$，满足：

$$H\left(Z\right)=H\left(X_Z,Y_Z\right)$$，$$H\left(X_Z\right)=PH\left(c_{-i}\right)$$，$$H\left(Y_Z\right)=PH\left(c_j\right)$$

(34)

并且$c_i$与$X_Z$不可区分，$c_j$与$X_Y$不可区分，$c_i\Vert c_j$与$Z$不可区分。

要证明在使用了强安全的碎片化系统$\Psi$下，对于任意$i\in \left\{\mathrm{1,2},···,l\right\}$，$A_i$无法获知其他的非空数据$c_j(j\ne i)$，

$$\mathrm{P}\mathrm{r}\left[A_i\left(c_{-i}\right)=c_j\right]\le \frac{\mathrm{1}}{{\mathrm{2}}^{PH(c_j)}}+\epsilon (\lambda )\le \frac{\mathrm{1}}{{\mathrm{2}}^{H(c_j)}}+\epsilon (\lambda )$$

(35)

使用反证法，若结论不成立，则存在算法$B$和多项式$p(·)$使得：

$$\mathrm{P}\mathrm{r}\left[B\left(c_{-i}\right)=c_j\right]=\frac{\mathrm{1}}{{\mathrm{2}}^{PH\left(c_j\right)}}+\frac{\mathrm{1}}{p(\lambda )}$$

(36)

那么可以利用算法$B$构造区分器$\mathit{𝒟}$。设对于输入$x\Vert y$，若$B\left(x\right)=y$，则$\mathit{𝒟}$输出1，否则输出0。那么：

$$\mathrm{P}\mathrm{r}\left[\mathit{𝒟}\left(X_Z\Vert Y_Z\right)=\mathrm{1}\right]\le \frac{\mathrm{1}}{{\mathrm{2}}^{H(Y_Z)}}$$

(37)

此时对任意可忽略函数$\epsilon \left(·\right)$，都有：

$$\left|\mathrm{P}\mathrm{r}\left[\mathit{𝒟}\left(c_{-i}\Vert c_j\right)=\mathrm{1}\right]-\mathrm{P}\mathrm{r}\left[\mathit{𝒟}\left(X_Z\Vert Y_Z\right)=\mathrm{1}\right]\right|=\left|\frac{\mathrm{1}}{{\mathrm{2}}^{PH\left(c_j\right)}}+\frac{\mathrm{1}}{p\left(\lambda \right)}-\frac{\mathrm{1}}{{\mathrm{2}}^{H\left(Y_Z\right)}}\right|=\frac{\mathrm{1}}{p(\lambda )}$$

(38)

并非可忽略的，这与假设矛盾。

基于伪随机性与不可预测性的等价性定理，若一个碎片化系统是伪随机的，那么攻击者在已知部分碎片条件下是不能预测其他碎片的。

定理5   若一个多信道的碎片化系统是伪随机的，则该多信道数据传输在协助攻击下是强隔离安全的。

证明：考虑$l-$多信道，设第$i$信道中存在一个监听者为$A_i$，$i\in (\mathrm{1,2},···,l)$。假设$A_i$只能获取所在信道上的所有数据，记作$c_i$。要证明在使用了安全的碎片化系统$\Psi$下，对于任意$i\in \left\{\mathrm{1,2},···,l\right\}$，$A_i$无法获知其他信道传输的非空数据$c_j(j\ne i)$，即：

$$\mathrm{P}\mathrm{r}\left[A_i\left(c_{-i}\right)=c_j\right]\le \frac{\mathrm{1}}{{\mathrm{2}}^{PH(c_j)}}+\epsilon (\lambda )$$

(39)

其中$c_{-i}=c_{\mathrm{1}}\Vert c_{\mathrm{2}}\Vert ···\Vert c_{i-\mathrm{1}}\Vert c_{i+\mathrm{1}}\Vert ···\Vert c_l$且$(c_{\mathrm{1}},c_{\mathrm{2}},···,c_l)\leftarrow \mathrm{F}\mathrm{r}{\mathrm{a}}_k({\mathrm{1}}^l,c)$。

由于碎片化系统$\Psi$是伪随机的，即对于任意的数据$c\in {\{\mathrm{0,1}\}}^{*}$和任意正整数$i,j\in \mathit{\mathbb{N}}$，有$c_{\mathrm{1}}\Vert c_{\mathrm{2}}\Vert ···\Vert c_l$是伪随机的，那么$PH\left(c_{-i}\right)=|c_{-i}|$且$PH\left(c_j\right)=|c_j|$，得到：

$$\mathrm{P}\mathrm{r}\left[A_i\left(c_{-i}\right)=c_j\right]\le \frac{\mathrm{1}}{{\mathrm{2}}^{\left|c_j\right|}}+\epsilon (\lambda )$$

(40)

4 结论

攻击方式的多样化与系统的复杂化给碎片化系统的安全性评估带来了一定的挑战。碎片化技术侧重于在单点数据泄漏的情况下限制对整体安全性的影响，根据实际攻击类型划分敌手能力，以敌手通过已知信息预测其他信道信息的概率大小区分隔离安全的强弱。提出3级碎片化技术安全评估等级，并加以有效性验证，建立一套多信道数据碎片化传输的安全等级评估指导方法。该方法也适用于数据碎片化存储和传输相关领域的安全性分析，对于数据碎片化技术的安全性评估和系统设计具有较大的实用价值和现实意义。