用Python实战模拟Garbled Circuit：从零理解密码学中的隐私保护魔法

密码学常被视作高深莫测的领域，充斥着数学公式和抽象概念。但今天，我们要用Python代码撕开这层神秘面纱，亲手构建一个简化版的Garbled Circuit（混淆电路）——这个支撑着安全多方计算的核心技术。不同于教科书式的理论讲解，我们将通过可运行的代码和实时变量观察，让"混淆"的过程变得触手可及。

想象这样一个场景：Alice和Bob想计算他们是否都同意某个商业提案（逻辑与运算），但谁也不愿透露自己的真实态度。这正是混淆电路要解决的经典问题。下面，我们不仅会用代码模拟整个流程，还会在Jupyter Notebook中逐步打印关键变量，让你亲眼见证隐私如何在不暴露输入的情况下被保护。

1. 环境准备与基础概念

在开始编码前，我们需要明确几个核心概念。Garbled Circuit本质上是一种加密的布尔电路，它通过三个关键步骤实现隐私保护：

1. 电路混淆 ：将原始真值表转换为随机化的加密版本
2. 输入替换 ：用随机标签代替实际输入值
3. 安全解密 ：只有正确的输入组合才能解密出有效结果

让我们先准备好Python环境。这个实验只需要标准库，无需额外安装包：

import random
from hashlib import sha256
from itertools import product

# 设置随机种子保证可复现性
random.seed(42)

2. 构建基础与门电路

我们从最简单的逻辑与门开始。一个标准的与门真值表如下：

X	Y	Output
0	0	0
0	1	0
1	0	0
1	1	1

在混淆电路中，Alice需要将这个表转换为加密形式。以下是分步实现：

def generate_wire_labels():
    """生成每条线的随机标签"""
    return {
        'X0': random.getrandbits(128),
        'X1': random.getrandbits(128),
        'Y0': random.getrandbits(128),
        'Y1': random.getrandbits(128),
        'Z0': random.getrandbits(128),
        'Z1': random.getrandbits(128)
    }

labels = generate_wire_labels()
print("Wire Labels:", {k: hex(v)[:10]+'...' for k,v in labels.items()})

输出示例：

Wire Labels: {
    'X0': '0x23ab6e8...', 
    'X1': '0x7c5d3f9...',
    'Y0': '0x1a4e2b8...',
    'Y1': '0x5f6c9d1...',
    'Z0': '0x3e8a7b2...',
    'Z1': '0x9c1d5f4...'
}

3. 创建混淆表的核心算法

接下来是最关键的混淆过程。我们需要：

1. 用标签替换原始值
2. 对输出进行双重加密
3. 随机打乱行顺序

def encrypt(key1, key2, message):
    """模拟对称加密（实际应用中应使用AES等安全算法）"""
    combined = f"{key1}|{key2}|{message}".encode()
    return int.from_bytes(sha256(combined).digest(), 'big') & 0xFFFFFFFF

def create_garbled_table(labels):
    table = []
    # 原始真值表的所有可能输入组合
    for x_val, y_val in product([0,1], [0,1]):
        input_labels = (labels[f'X{x_val}'], labels[f'Y{y_val}'])
        output_label = labels[f'Z{x_val & y_val}']
        # 用输入标签作为密钥加密输出标签
        encrypted = encrypt(input_labels[0], input_labels[1], output_label)
        table.append(encrypted)
    
    # 打乱行顺序（混淆的关键步骤）
    random.shuffle(table)
    return table

garbled_table = create_garbled_table(labels)
print("Garbled Table:", [hex(x)[:10]+'...' for x in garbled_table])

4. 模拟不经意传输（OT）协议

OT协议允许Bob获取自己的输入标签，同时不让Alice知道他的选择。这里我们简化实现：

def oblivious_transfer(alice_messages, bob_choice):
    """简化版1-out-of-2 OT协议"""
    assert len(alice_messages) == 2
    return alice_messages[bob_choice]

# Alice提供Y0和Y1标签
alice_y_labels = [labels['Y0'], labels['Y1']]

# Bob的私密输入（假设为1）
bob_secret_input = 1
bob_received_label = oblivious_transfer(alice_y_labels, bob_secret_input)
print(f"Bob received: {hex(bob_received_label)[:10]}...")

5. 完整流程模拟与结果解密

现在让我们把各个部分串联起来，模拟完整的计算流程：

def evaluate_garbled_circuit(garbled_table, x_label, y_label):
    """尝试用给定标签解密混淆表"""
    for entry in garbled_table:
        # 尝试解密（对称加密的逆操作相同）
        decrypted = encrypt(x_label, y_label, entry)
        if decrypted in [labels['Z0'], labels['Z1']]:
            return decrypted
    raise ValueError("No valid decryption found")

# Alice的私密输入（假设为0）
alice_secret_input = 0
alice_sent_label = labels[f'X{alice_secret_input}']

# Bob现在有：
# - Alice发送的X标签
# - 通过OT获取的Y标签
# - 混淆表
bob_computed_z_label = evaluate_garbled_circuit(
    garbled_table,
    alice_sent_label,
    bob_received_label
)

# Alice知道标签到真实值的映射
result_mapping = {labels['Z0']: 0, labels['Z1']: 1}
final_result = result_mapping[bob_computed_z_label]

print(f"Computed result: {final_result} (should be {alice_secret_input & bob_secret_input})")

6. 安全特性分析与实际应用思考

通过这个简化实现，我们可以直观看到混淆电路如何保护隐私：

1. 输入保密性 ：

   • Alice只看到 X0 标签，无法推断原始值
   • Bob通过OT获取标签，Alice不知道他的选择

2. 电路保密性 ：

   • 打乱的加密表隐藏了逻辑关系
   • 只有正确输入组合才能解密有效输出

3. 结果正确性 ：

   • 最终结果与明文计算一致
   • 只有Alice知道如何解释输出标签

在实际应用中（如隐私保护机器学习），这些技术可以：

• 让医院在不共享原始数据的情况下联合训练模型
• 实现加密的推荐系统，保护用户历史行为
• 构建安全的电子投票系统

# 扩展思考：如何验证电路未被篡改？
# 可以添加MAC（消息认证码）校验
def generate_mac(key, message):
    return sha256(f"{key}|{message}".encode()).hexdigest()[:16]

# Alice为每个标签生成MAC并发送给Bob
macs = {k: generate_mac("secret_key", v) for k,v in labels.items()}

7. 性能优化与进阶方向

虽然我们的实现为了教学目的做了简化，但真实场景需要考虑：

1. 加密强度 ：

   • 使用AES等工业级加密算法
   • 增加盐值(salt)防止彩虹表攻击

2. 通信优化 ：

   • 采用点函数混淆(point-and-permute)技术
   • 使用固定密钥推导减少传输数据量

3. 电路优化 ：

   • 逻辑门拓扑排序减少中间结果
   • 批处理相似操作

# 进阶：Free XOR技术优化
# 让XOR门无需加密表
def setup_free_xor(delta):
    """设置全局差异值用于XOR门优化"""
    return delta

# XOR门计算只需简单异或
def evaluate_xor_gate(a_label, b_label, delta):
    return a_label ^ b_label ^ delta

这个Python实现虽然简单，却完整展现了混淆电路的核心思想。当你运行代码并观察中间变量时，会清晰看到：原始输入如何被随机标签替代，加密表如何隐藏逻辑关系，以及最终结果如何被正确还原——这正是现代密码学保护数据隐私的魔法所在。