基于不经意排序的MPC稀疏矩阵乘法：突破隐私计算内存墙

1. 项目概述与核心挑战在隐私保护机器学习Privacy-Preserving Machine Learning, PPML的实际落地过程中我们常常会遇到一个看似矛盾的现象理论上基于安全多方计算Multi-Party Computation, MPC的加密协议能够完美地在不暴露任何一方原始数据的前提下完成联合计算但当我们试图将其应用于推荐系统、自然语言处理或基因组学这类真实业务场景时系统往往会因为内存不足或网络通信量过大而直接崩溃。问题的根源往往不在于MPC协议本身而在于我们处理的数据形态——稀疏数据。所谓稀疏数据指的是数据矩阵中绝大部分元素为零的数据集。想象一下一个拥有百万用户和十万商品的电商平台用户-商品交互矩阵每个用户平均只购买或浏览过几十个商品那么这个矩阵中非零元素的比例可能连万分之一都不到。在明文计算中我们早已习惯使用SciPy的csr_matrix或coo_matrix来高效存储和计算这类数据。然而一旦进入MPC的加密世界所有数据都被秘密共享Secret-Shared为看似随机的分片数据的稀疏性这一关键结构信息对计算方而言是完全隐藏的。此时如果我们仍机械地套用为密集数据设计的通用矩阵乘法协议就相当于要求计算方在不知道哪些位置是零的情况下对每一个可能的矩阵元素位置都执行一次昂贵的加密乘法操作。这不仅会产生海量O(n³)级别的通信开销更致命的是为了在内存中临时存储这些“全尺寸”的中间密文矩阵所需的内存空间会迅速膨胀到TB甚至PB级别使得计算完全不可行。因此设计专门针对秘密共享稀疏矩阵的乘法算法不是一个“锦上添花”的优化而是将MPC技术应用于广阔的真实稀疏数据场景的“生死线”。这项工作需要在不泄露数据具体位置的前提下让计算方能够“感知”到稀疏结构从而跳过对零值的无效计算。这就像蒙着眼睛在布满障碍物的房间里高效行走你需要一套特殊的规则协议来感知和规避障碍零值而不是盲目地触碰每一个点。2. 稀疏数据在MPC中的表示与核心思路2.1 从明文稀疏格式到密文表示在明文计算中稀疏矩阵有多种存储格式如坐标列表COO、压缩稀疏行CSR、压缩稀疏列CSC等。COO格式最简单它用三个列表分别存储所有非零元素的行索引、列索引和值。CSR格式则按行压缩能更快地进行行操作。然而在MPC环境中格式的选择需要格外小心。CSR格式依赖于行指针数组在执行查找操作如“获取第i行的所有非零元”时需要根据行索引访问指针数组再跳转到值数组的特定位置。这种随机访问模式在MPC中代价极高因为每次访问都可能触发一次需要多方交互的“不经意读取”协议。因此在设计的初期我们就排除了CSR/CSC这类需要高效随机访问的格式。我们选择了最直观的坐标列表COO格式的密文变体。具体来说一个秘密共享的稀疏矩阵[[X]]被表示为一个列表列表中的每个元素是一个三元组([[i]], [[j]], [[v]])其中[[i]]和[[j]]是行、列坐标的秘密共享值[[v]]是对应位置非零值的秘密共享值。所有零值被完全忽略不参与存储和传输。这种表示法天然去除了零值将存储和计算复杂度从矩阵维度n x m降到了非零元数量nnz(X)。注意这里存在一个关键的安全与效率权衡。坐标([[i]], [[j]])本身也是加密的这保护了非零元的位置隐私。但这也意味着计算方无法直接“知道”哪些坐标需要相乘。我们后续的所有算法其核心智慧都围绕着如何在不暴露坐标具体值的情况下让具有相同坐标的元素能够“相遇”并完成乘法。2.2 算法核心直觉基于不经意排序的“聚合”既然计算方不能直接看到坐标如何让两个稀疏向量中坐标相同的非零元配对呢核心思路是利用不经意排序。假设有两个稀疏向量[[x]]和[[y]]我们将它们的所有非零元三元组合并到一个大列表中。然后我们对这个大列表按照坐标值进行不经意排序。不经意排序协议能保证输出一个按坐标值有序的列表但参与排序的各方在整个过程中都无法得知具体的坐标值大小和顺序。排序之后所有具有相同坐标的三元组会在列表中相邻排列。接下来我们让列表中的每个元素与它的下一个元素进行比较同样是在密文状态下比较坐标是否相等。如果相等则将它们的值相乘并将结果累加到一个总和变量中如果不相等则什么也不做。由于比较和乘法都在密文上进行计算方只知道他们在执行操作但不知道具体是哪些坐标匹配上了。这个过程听起来简单但扩展到矩阵与向量、矩阵与矩阵的乘法时挑战才真正开始。矩阵乘法的本质是“行与列的点积”。在稀疏场景下我们需要让矩阵X第i行的所有非零元与矩阵Y第j列的所有非零元根据它们共同的列索引对X和行索引对Y进行匹配和相乘。这要求我们的算法能进行更复杂的多键排序和聚合。3. 安全稀疏矩阵乘法算法详解3.1 基础构件不经意排序与不经意洗牌在深入算法前必须理解两个关键的MPC原语它们是实现高效稀疏运算的基石不经意排序给定一个秘密共享的列表[[L]]不经意排序协议能输出一个按特定密钥如坐标排序的新列表[[L]]但任何参与方都无法得知输入列表的顺序、输出列表的顺序以及元素之间的相对大小关系。常见的实现基于排序网络或基数排序。其通信复杂度为O(m log m)其中m是列表长度。不经意洗牌将秘密共享的列表[[L]]随机打乱输出一个随机排列的列表[[L_perm]]且排列本身也是秘密的。这常用于隐藏数据访问模式。一个经典的实现方法是为每个列表元素生成一个随机的秘密共享密钥然后根据这个密钥对列表进行不经意排序。我们的算法严重依赖这两个操作。排序是为了让相同坐标的元素相邻以便聚合洗牌则常用于后续步骤比如在聚合完成后我们需要移除那些因为聚合而变成“空位”占位符的列表项同时不暴露哪些位置被移除了即不暴露聚合发生的次数和位置。这时我们会先不经意地洗牌整个列表然后公开地检查每个位置是否为占位符并删除之。由于列表顺序已被打乱公开删除操作不会泄露任何关于原始数据分布的信息。3.2 算法一稀疏矩阵-向量乘法我们以矩阵[[X]]n x m乘以向量[[y]]m x 1为例。假设我们已知每个矩阵行的非零元数量这是一个必要的公开知识后文会讨论如何以隐私保护的方式获取。算法步骤拆解构造扩展列表将矩阵[[X]]的所有非零元三元组([[i]], [[j]], [[v_x]])放入一个列表。对于向量[[y]]的每个非零元([[j]], [[v_y]])我们将其转换为一个特殊的三元组([[⊥]], [[j]], [[v_y]])其中[[⊥]]是一个特殊的、小于任何有效行索引的标记值。然后将这些向量三元组也加入列表。这样列表中就混合了矩阵的行元素和向量的列元素。键排序对整个列表进行排序先按第二项列坐标j排序再按第一项行坐标i或⊥排序。排序后列表的局部结构会是对于某个列坐标j首先出现的是标记为⊥的向量元素v_y紧接着是所有矩阵中列坐标为j的非零元(i, j, v_x)。扫描与乘法顺序扫描排序后的列表。我们维护一个“前一个向量元素”的缓存。当扫描到一个矩阵元素时我们检查它的列坐标是否等于缓存中向量元素的列坐标密文比较。如果相等则计算[[v_x]] * [[v_y]]并将这个乘积临时存储在该矩阵元素的位置上覆盖原值如果不相等则将该矩阵元素的值置零。当扫描到一个新的向量元素标记为⊥时我们更新缓存。聚合行结果经过上一步每个矩阵非零元位置都存储了它与向量对应元素的乘积或零。接下来我们移除列表中的向量元素它们已完成任务。然后我们对剩余列表现在每个元素是([[i]], [[j]], [[product]])按行坐标i排序。排序后所有行坐标相同的元素会相邻。行内聚合与清理再次扫描列表将行坐标相邻且相等的元素的product值相加合并为一个结果元素。合并后被合并的前一个位置会留下一个占位符。最后我们使用“不经意洗牌后公开删除占位符”的技巧清理列表输出最终的结果稀疏向量。复杂度分析通信/计算O((nnz(X) nnz(y)) * log(nnz(X) nnz(y)))。主要开销来自两次排序。存储O(nnz(X) nnz(y))远小于密集算法所需的O(n*m)。与密集算法对比在诚实多数假设下最新的密集矩阵-向量乘法通信复杂度可达O(n)看似比我们的对数因子更优。但关键在于内存。对于一个100万x10万的矩阵即使稀疏度99.9%密集表示需要约800GB内存假设8字节浮点数而我们的稀疏表示仅需约800MB。当密集表示无法装入内存时再低的通信复杂度也毫无意义。3.3 算法二稀疏矩阵-矩阵乘法我们重点讨论机器学习中常见的操作计算X^T * X例如协方差矩阵。假设已知矩阵[[X]]每列的非零元数量以及矩阵[[Y]]这里Y X每行的非零元数量。算法核心洞察朴素的三重循环对每个输出元素(i, j)计算X的第i行与X的第j列的点积在稀疏场景下效率极低因为它需要为每个输出点积都遍历一次数据。我们的算法受高性能计算中优化密集矩阵乘法的思想启发改变循环次序优先遍历共享的维度。对于X^T * X计算Z[i][j] Σ_k (X[k][i] * X[k][j])。高效的思路是对于每一个中间索引k取出X的第k列的所有非零元(i, val_i)以及X的第k行的所有非零元(j, val_j)生成所有可能的乘积对(i, j, val_i * val_j)。然后我们将所有k产生的乘积对合并到一个巨大的列表中。算法步骤拆解生成所有标量乘积对遍历每一个中间维度k从1到m。利用公开的每行/每列非零元数量信息我们可以直接定位到X的第k列向量X(:, k)和第k行向量X(k, :)在密文形式下。对这两个稀疏向量中的每一对非零元(i, val_i)和(j, val_j)计算乘积[[p]] [[val_i]] * [[val_j]]并生成一个结果三元组([[i]], [[j]], [[p]])将其加入全局列表[[Z]]。这一步生成了所有必要的部分积。聚合所有部分积现在全局列表[[Z]]包含了所有k对应的(i, j, p)。最终结果矩阵中(i, j)位置的值就是列表中所有行列为(i, j)的p之和。因此我们对[[Z]]按(i, j)字典序进行不经意排序。合并相同坐标扫描排序后的列表将坐标相邻且完全相等的三元组的值相加合并为一个三元组并用占位符标记被合并的位置。这一步与矩阵-向量乘法中的聚合步骤类似。清理占位符使用不经意洗牌后公开删除的方法移除所有占位符得到最终的、以COO格式存储的稀疏结果矩阵[[Z]]。复杂度与优势分析通信/计算O(MinMult * log(MinMult))其中MinMult Σ_k (nnz(X(:,k)) * nnz(X(k,:)))。MinMult是完成该矩阵乘法所必须的标量乘法次数是任何算法包括明文最优算法的理论下界。我们的算法仅增加了一个对数因子这在MPC环境下是可接受的巨大胜利。对比密集算法在诚实多数下最好的密集矩阵乘法通信复杂度为O(n*p)输出矩阵大小。对于X^T * Xn x n即O(n²)。而我们的稀疏算法复杂度取决于MinMult。在极端稀疏例如每行/每列只有常数个非零元的情况下MinMult可低至O(n)比密集算法优一个数量级。在真实数据集中MinMult通常远小于n²。4. 公开知识、隐私权衡与优化技巧任何高效的稀疏MPC算法都无法回避一个事实需要一些关于稀疏结构的公开知识。我们的算法需要知道每个矩阵行或列的非零元数量。这听起来像是一个隐私泄露但我们需要在现实约束下理性看待。4.1 为什么公开知识是必要的效率与隐私之间存在根本性的权衡。稀疏算法的所有性能增益减少通信、计算、存储都直接来源于我们知道“哪里是零可以跳过”。如果连“有多少非零元”都完全保密那么在最坏情况下为了隐藏真实数量算法必须假设所有位置都可能是非零元从而退化到密集算法的复杂度。因此要求行/列的非零元数量作为公开知识是一个为了获得可行性而做出的最小化、结构化的信息暴露。4.2 公开知识从何而来如何最小化在实际的隐私保护机器学习流程中这个公开知识通常可以通过一个预处理阶段以相对安全的方式获得数据探索与建模阶段在正式启动加密训练之前数据所有方通常会进行明文的数据探索性分析EDA以了解数据特征、选择模型。在这个阶段统计行/列的非零元数量是常规操作。我们可以设计一个轻量级的MPC协议让各方在不暴露具体哪些行/列稀疏的情况下安全地聚合计算出这些计数。例如各方可以本地计算自己数据块的行计数然后通过安全的聚合求和协议得到全局计数。利用现实世界数据的特性现实世界的稀疏数据有一个关键特性数据维度越大稀疏度往往越高。例如一个拥有10万商品的推荐系统其用户-商品矩阵的稀疏度可能高达99.99%。这意味着即使我们公开了“每行大约有10个非零元”这样的统计信息攻击者也无法精确推断出单个用户的行为因为可能的非零位置组合仍然是天文数字。公开的是聚合的统计特征而非个体敏感信息。差分隐私注入为了进一步降低风险在公开行/列计数之前可以为其加入经过校准的拉普拉斯噪声使其满足差分隐私。只要噪声的尺度控制得当它对后续稀疏乘算法的整体效率影响微乎其微因为算法复杂度是对数级依赖于数量而噪声是加性常数却能严格量化地保护个体数据贡献的隐私。4.3 一个实用的优化技巧预计算坐标的比特分解在我们的算法中最昂贵的操作之一是经意排序而其成本与待排序元素的比特长度有关。坐标i,j通常是32位或64位整数。在不经意排序特别是基数排序中需要对这些整数的每一个比特位进行多轮比较和交换操作。一个显著的优化是让数据所有方在秘密共享数据之前就本地完成坐标的比特分解。也就是说对于每个非零元坐标(i, j)数据所有方不是共享一个整数[[i]]而是共享一个比特数组[[i_b0]], [[i_b1]], ..., [[i_b31]]对于32位整数。这样计算方在后续的不经意排序中可以直接对这些秘密共享的比特进行操作省去了昂贵的在线比特分解协议。虽然这增加了初始共享的通信量约32倍但这是一次性的开销。考虑到后续排序操作会被反复执行尤其是在迭代的机器学习训练中并且稀疏表示本身已经将数据量减少了成百上千倍这种用一次性的、固定系数的开销换取核心操作数量级加速的策略在实践中是非常划算的。5. 实战场景、性能对比与避坑指南5.1 实验设置与基准对比我们在一个模拟的三方诚实多数MPC环境中使用MP-SPDZ框架的思想实现了上述算法。测试矩阵规模从1k x 1k到100k x 100k稀疏度分别为99% 99.9% 99.99%。我们对比了密集基线基于Shamir秘密共享的经典矩阵乘法协议。我们的稀疏算法实现了矩阵-向量和矩阵-矩阵乘法。核心结论可视化模拟数据通信开销对于小规模如10k维且稀疏度一般99%的矩阵密集算法可能仍有优势。但当稀疏度达到99.9%或维度超过50k我们的稀疏算法通信量开始显著低于密集算法优势可达数十到数百倍。内存墙这是最关键的图表。密集算法的内存消耗曲线随着矩阵维度平方级增长很快突破实验机器的内存上限比如在20k x 20k矩阵时并在图中以“内存溢出”标记终止。而我们的稀疏算法三条曲线对应不同稀疏度则平缓得多在相同维度下内存占用低数个数量级能够轻松处理维度大得多的矩阵。真实数据集验证我们在BookCrossing书籍评分34万本书99.998%稀疏度和MovieLens-10M电影评分99.5%稀疏度数据集上测试了一个简单的隐私保护协同过滤子程序涉及稀疏矩阵-向量乘。使用密集算法在实验环境中甚至无法将密文矩阵载入内存。而使用我们的稀疏算法整个计算过程在几分钟内完成通信量在可接受的GB级别。5.2 典型应用场景与实现要点场景一隐私保护的实时推荐在联邦推荐场景中服务器持有加密的用户-物品交互矩阵[[X]]。当一个用户发起请求时其加密的偏好向量[[y]]被发送到服务器。服务器需要计算[[X]] * [[y]]得到为用户推荐的物品得分向量。实现要点用户偏好向量[[y]]通常也非常稀疏用户只对少数物品有显式反馈。直接使用我们的稀疏矩阵-向量乘法算法。服务器端需要预先知道矩阵[[X]]的每行非零元数量这可以在模型初始化阶段通过安全聚合获得。避坑指南注意在线计算延迟。虽然通信量大幅降低但不经意排序的轮数复杂度可能成为延迟瓶颈。对于实时性要求极高的场景可以考虑将矩阵[[X]]按行分块并行计算多个块与向量的乘积最后聚合结果。场景二加密数据集上的特征协方差计算在纵向联邦学习中各方拥有同一批样本的不同特征需要联合计算特征之间的协方差矩阵X^T * X用于后续的PCA或模型训练。实现要点这正是我们稀疏矩阵-矩阵乘法算法的典型用例。各方先本地计算自己特征矩阵的加密形式并安全地聚合出行/列非零元计数公开知识。然后联合执行算法5。避坑指南MinMult的计算量可能仍然很大。如果X的某些列非常稠密即“热门特征”会导致该列对应的nnz(X(:,k))很大从而使MinMult膨胀。在实际部署前建议对数据进行探查对极端稠密的特征考虑进行降维或单独处理。5.3 常见问题与调试心得问题算法在聚合步骤后输出结果中似乎有重复坐标或值不正确。排查思路这几乎总是由排序的不稳定性或比较逻辑错误引起的。首先确保你的不经意排序协议是稳定排序吗如果不是具有相同坐标的元素在排序后可能不连续导致聚合失败。其次仔细检查密文相等比较的实现。在有限域或环上a b通常通过计算(a - b)是否为零来判断但要注意处理数据溢出和环的大小。建议在开发阶段构造一个极小的测试用例如3x3矩阵并在“调试模式”下运行——即暂时用明文模拟秘密共享流程打印出每一步中间列表的状态与手工计算的结果对比。问题公开的行/列非零元数量被恶意方篡改会导致什么后果后果分析如果攻击者故意夸大某行的非零元数量算法会为该行分配更多的计算和存储资源但实际处理的是空数据或填充数据造成资源浪费和结果错误如果填充值不是零。如果攻击者少报数量则可能导致真正的非零元在预处理阶段被错误截断造成数据丢失和计算结果错误。防御建议在安全聚合行/列计数时采用具有恶意安全性的聚合协议。此外可以在算法开始时增加一个轻量级的“完整性检查”各方在提交数据后可以随机抽样少量行要求数据所有方公开这些行的非零元坐标和值的承诺如哈希由计算方验证其数量是否与公布的统计信息一致。虽然不能完全防止作弊但能大大提高作弊被发现的概率。问题如何选择不经意排序的具体协议基数排序还是排序网络选择心得这需要在轮数复杂度和通信量之间权衡。排序网络如Batcher奇偶归并排序的电路深度是O(log² n)轮数较多但每轮的操作简单且可并行化总通信量相对固定。基数排序的轮数更少约为O(k)k是元素比特长度但每轮需要处理整个列表通信量可能更大。在我们的稀疏乘法中待排序列表的长度nnz可能很大百万级但元素坐标的比特长度相对固定如32位。我的经验是在广域网高延迟环境下优先选择轮数少的基数排序在局域网低延迟或更关注总通信量的环境下排序网络可能更优。最好根据你的网络环境和具体库的实现效率进行基准测试。问题算法中大量使用了密文比较和条件选择如何优化其性能优化技巧密文比较[a] [b]或[a] [b]是MPC中最昂贵的操作之一。一个关键的优化是“批量比较”。我们的算法中很多比较是独立且可以并行执行的例如排序网络中的大量比较器。一定要利用MPC框架提供的批量操作接口将成千上万个比较操作打包成一个批次提交这能极大减少网络往返次数和协议开销。此外对于相等比较如果是在算术秘密共享上可以利用(a-b)*r的随机化技巧其中r是随机数通过一次乘法打开结果来判断是否为零这比通用的比特分解比较要快。6. 总结与未来展望将MPC应用于稀疏数据不是简单地将明文稀疏算法“加密化”它需要重新设计算法原语以在不泄露数据模式的前提下利用稀疏性。文详述的基于不经意排序的稀疏矩阵乘法框架通过巧妙地组织数据流和聚合计算在保护数据位置隐私的同时实现了通信和存储开销与非零元数量近乎线性的关系突破了密集算法固有的“内存墙”。从工程实践角度看成功部署此类算法的关键在于三点一是理解并接受必要的公开知识通过安全的统计发布或差分隐私来管理风险二是精细实现核心原语特别是批量化的不经意排序和比较操作三是紧密结合业务数据特征真实世界数据的稀疏度往往随规模增大而增高这恰恰放大了稀疏算法的优势。我个人在实现和调试这些协议的过程中最深的一点体会是隐私保护系统的性能优化往往来自于对数据本身结构的深刻理解而非单纯密码学原语的堆砌。稀疏矩阵乘法只是一个起点未来还有更多挑战例如如何设计支持动态稀疏模式非零元位置随时间变化的高效协议如何将稀疏优化与随机梯度下降等迭代算法的其他优化如梯度压缩结合以及如何为更复杂的稀疏张量运算设计专用协议。这条路还很长但每解决一个这样的问题我们就离让隐私计算技术无缝支撑大规模现实应用的目标更近一步。