Cipher Maps：当范畴论遇上 Oblivious Computing

发布: 1周前 (2026年1月7日 GMT+8 16:42)

7 min read

原文: Dev.to

Source: Dev.to

很抱歉，我无法直接访问外部链接获取文章内容。请您将需要翻译的文本粘贴在这里，我会按照要求把它翻译成简体中文并保留原有的格式。

引言

如果我们能够在加密数据上进行计算 同时保持代数结构 会怎样？
不是通过昂贵的同态加密，而是通过一个统一以下内容的原则性数学框架：

隐匿计算
伯努利类型（统计近似）
范畴抽象

我最近关于 cipher maps 和 algebraic cipher types 的工作正是探讨这一想法。

Source: …

核心思想：密码函子

一个 cipher functor cA 将一个幺半群

[ (S,\ *,\ e) ]

提升为一个 cipher monoid

[ (cA(S),\ \oplus,\ \hat e) ]

Latent space (real monoid)   : (S, *, e)
          ↓ cA (cipher functor)
Cipher space (encrypted)    : (cA(S), ⊕, ê)

关键属性

属性	描述
结构保持	`cA(x * y) ≈ cA(x) ⊕ cA(y)`（在受控近似范围内）
隐私	对密文的操作不会泄露底层数值的任何信息
可组合性	密码操作的组合方式与基底幺半群中的组合方式相对应
近似性	结果是近似的，但伴随可证明的误差界限

这些属性为 oblivious computing 提供了一套 类型系统：相较于临时的加密方案，我们得到的是能够保持代数结构的原则化构造。

为什么这很重要

正式的隐私保证 已经内置于类型中。
误差界限 来源于伯努利类型理论。
可组合的抽象 使我们能够从已验证的组件构建复杂的隐蔽流水线。

示例说明

基底幺半群	密码提升	得到的隐匿结构
((\mathbb{N}, +, 0))	`cA`	隐匿计数器
((\mathcal{P}(U), \cup, \varnothing))	`cA`	基于哈希的隐匿集合（类似布隆过滤器）
((\mathbb{N}^U, \oplus, \mathbf{0}))	`cA`	具隐私的 Count‑Min 草图

(Links: Algebraic Cipher Types, Cipher Maps)

统一框架

本文 统一了三个主要方向：

Algebraic cipher types – 类别基础
Bernoulli types – 统计近似理论
Oblivious function approximation – 实用算法

Cipher Maps as Morphisms

Objects – 密码类型（加密/隐匿数据结构）
Morphisms – 同时保持代数结构和统计属性的函数

Morphisms 的组合提供了构建复杂隐匿计算的原则化方法，同时能够跟踪误差传播。

关键贡献：Oblivious Bernoulli 映射

Oblivious Bernoulli 映射 是一个函数

[ f : cA(S) \to cA(T) ]

它：

在加密/不可知的输入上操作
产生加密/不可知的输出
具有可证明的误差界（来源于 Bernoulli‑type 理论）
保持范畴结构（来源于 cipher functors）

实际结果

从普通函数 f : S → T 开始。
将其提升为密码映射 cA(f) : cA(S) → cA(T)。
获得 自动的隐私保证 和 形式化的误差界。
在跟踪误差传播的同时组合多个密码映射。

为什么要使用抽象数学？

类别理论概念	对盲计算的好处
函子性 `cA(f ∘ g) = cA(f) ∘ cA(g)`	安全组合是免费的
自然变换	在盲表示之间的通用转换
极限 / 上余极限	系统化构造复合盲类型
单体结构	盲计算的并行组合

没有这些抽象，每个新的盲算法都需要定制的安全证明。

Concrete Instantiation: Cipher‑Trapdoor‑Sets

Base monoid – powerset ((\mathcal{P}(U), \cup, \varnothing))
Cipher functor – hash‑based Bernoulli maps

结果: Hash‑Based Oblivious Sets (HBOS)，即配备了以下功能的 Bloom 过滤器：

Formal privacy semantics → 形式化隐私语义
Compositional error bounds → 组合误差界限
Type‑safe set operations (union, intersection, etc.) → 类型安全的集合操作（并集、交集等）

Applications in the Wild

数据库操作符 – 在 oblivious data 上进行 join、project、select（隐藏访问模式）
聚合查询 – SUM、COUNT、AVG 提升到适当的 monoids
梯度聚合 – oblivious types 使得在没有可信聚合器的情况下实现差分隐私
流式分析 – 对 streaming monoids 的 cipher 映射提供常量内存、可证明私密的 pipelines

实现概述 (C++)

// Pseudocode sketch
template <typename T>
class CipherFunctor {
public:
    using Cipher = ObliviousBernoulli;

    // Lift a clear value into the cipher domain
    Cipher lift(const T& value);

    // Approximate inverse (decrypt/approximate)
    T approximate_inverse(const Cipher& cipher) const;

    // Monoidal operation on ciphertexts
    Cipher combine(const Cipher& a, const Cipher& b) const;
};

使用现代模板元编程实现，该设计旨在实现零开销抽象。

研究方向

方向	未解问题
更高范畴	在密码范畴之间的函子？
依赖类型	在类型系统中编码隐私/准确性权衡？
效应系统	使用密码映射跟踪信息流？
编译器集成	自动将常规代码提升为隐匿版本？

展望

我们正处于一个拐点：

隐私法规 需要无感计算。
规模推动我们采用近似算法。
复杂性 需要组合抽象。

Cipher maps 提供构建这些系统的数学基础——将 “临时加密 + 希望” 转化为 原则性构造、自动隐私 和 组合安全。