【密码学原语介绍】PPRF（可穿孔伪随机函数）

【密码学原语介绍】PPRF（可穿孔伪随机函数）

引用

CSDN

1.

https://blog.csdn.net/ATFWUS/article/details/138577537

在现代密码学中，伪随机函数（PRF）是构建各种加密协议和系统的基石。然而，在某些应用场景中，如密钥管理和权限控制，我们需要更为灵活的PRF，能够允许在不影响整体系统安全性的前提下，动态地调整其行为。这种需求催生了穿孔伪随机函数（PPRF）的发展。

PPRF介绍

PPRF是一种支持“穿孔”操作的伪随机函数。这种穿孔操作能将原始的PRF密钥k转化为一个新的“穿孔”密钥k*，穿孔密钥在一组特定的结合S⊆{0,1}m(λ)上失效，但保持以下特性：

• 功能保持性：对于所有不在集合S中的x'，有Fk(x')=Fk*(x')，即穿孔操作不影响不在S中点的函数行为。
• 穿孔点的伪随机性：对于所有在S中的x，以及任何有权访问k的多项式时间敌手，Fk(x)的值在计算上与随机数无法区分。换句话说，对于S集合中的点，虽然PRF在这些点上的行为被“遗忘”，但外部观察者无法从k*得出任何关于Fk(x)的原始输出信息。

灵感来源

PPRF的概念源于Goldreich, Goldwasser, 和Micali在1986年的工作，他们提出了基于树的PRF结构。在这种结构中，通过一种长度加倍的伪随机生成器（PRG），PRF能够在树的形态中展开，其中每个节点的密钥由其父节点密钥经过PRG处理得到。这样的结构特别适合于密钥的层次化管理和高效的查询处理。

其构造核心思想是：G:{0,1}λ→{0,1}2λ是一个扩充双倍长度的伪随机数生成器，G(s)=G0(s)∣∣G1(s)，其中G0(s)和G1(s)分别是G(s)输出的的前一半和后一半，则一个伪随机函数定义为Fk(⋅)：

Fk(x)=Gxm(λ)(Gxm(λ)−1(...(Gx1(k))))

其中x1x2...xm(λ)是输入x的二进制表示，m是一个多项式，k←R{0,1}λ。

PPRF的核心思想

上述的PRF树可以用来构造一个可穿孔的PRF，给定一个基于树的PRFF，密钥k，和希望穿孔的点x，设Px是沿着第x个叶子节点到PRF树的根的路径的节点的集合。我们可以设置穿孔的keyk*={Nx}，Nx是Px中每个节点的相邻的节点的集合。

例如，如图所示，在穿孔x=2这个节点后（图中k10表示），产生的穿孔keyk*={k0,k1}。新的key对应于从k10到k的路径的相邻节点，使用Fk*，除了x=2之外，其余所有节点均可正常使用。

应用场景

PPRF在多种场合显示出其独特的用途，尤其是在需要细粒度访问控制的密钥管理系统中。例如，PPRF可以用于创建一个动态的访问控制列表，其中某些特定的密钥可以被临时地禁用，而不影响系统中其他部分的安全性和功能性。此外，PPRF也适用于构建可撤销的加密系统和进行密钥轮换，这在处理大规模分布式系统中的加密密钥时尤为重要。

与常规PRF相比，PPRF提供了更高的灵活性和更细的控制力。常规PRF通常是静态的，一旦设定，其输出行为不会改变。而PPRF则允许管理员根据需要动态地修改PRF的行为，这种能力在需要严格安全控制的环境下极为宝贵。

简单实现

注意，此处的实现仅帮助理解pprf的运行逻辑，生产中请使用专门封装好的pprf组件。

from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
from cryptography.hazmat.backends import default_backend
import os

class PPRFNode:
    def __init__(self, key=None):
        # 如果未提供密钥，则生成一个随机的 32 字节密钥
        self.key = key if key else os.urandom(32)
        # 初始化左右子节点为 None
        self.left = None
        self.right = None

class PPRF:
    def __init__(self):
        # 创建根节点
        self.root = PPRFNode()
        self.backend = default_backend()

    def aes_prg(self, key, index):
        """ 使用 AES-ECB 作为长度加倍的 PRG """
        cipher = Cipher(algorithms.AES(key), modes.ECB(), backend=self.backend)
        encryptor = cipher.encryptor()
        block = bytearray(16)
        block[0] = index
        result = encryptor.update(bytes(block)) + encryptor.finalize()
        return result

    def evaluate(self, node, path, depth=0):
        # 如果达到了路径的末端，返回节点的密钥
        if depth == len(path):
            return node.key
        # 根据路径决定向左还是向右
        direction = int(path[depth])
        if direction == 0:
            if node.left is None:
                node.left = PPRFNode(self.aes_prg(node.key, 0)[:32])
            return self.evaluate(node.left, path, depth + 1)
        else:
            if node.right is None:
                node.right = PPRFNode(self.aes_prg(node.key, 1)[:32])
            return self.evaluate(node.right, path, depth + 1)

    def puncture(self, node, path, depth=0):
        # 如果到达了需要被穿孔的节点
        if depth == len(path):
            node.key = None  # 清除密钥，使其成为内部节点
            return
        # 递归地向下穿孔
        direction = int(path[depth])
        if direction == 0:
            if node.left is None:
                node.left = PPRFNode(self.aes_prg(node.key, 0)[:32])
            self.puncture(node.left, path, depth + 1)
            # 将当前节点的密钥设置为未被穿孔路径的子节点的密钥
            node.key = self.aes_prg(node.key, 1)[:32]
        else:
            if node.right is None:
                node.right = PPRFNode(self.aes_prg(node.key, 1)[:32])
            self.puncture(node.right, path, depth + 1)
            # 将当前节点的密钥设置为未被穿孔路径的子节点的密钥
            node.key = self.aes_prg(node.key, 0)[:32]

def binary_representation(x, length):
    # 生成二进制表示
    return bin(x)[2:].zfill(length)

# 使用示例
pprf = PPRF()
path = binary_representation(6, 3)  # 例如：深度为 3 的路径 6 的二进制表示
print("在穿孔前评估 PPRF，路径为:", path)
output = pprf.evaluate(pprf.root, path)
print("输出:", output.hex() if output else "无输出，节点已被穿孔")
pprf.puncture(pprf.root, path)
print("在路径", path, "处进行穿孔")
# 尝试再次评估同一路径
try:
    output = pprf.evaluate(pprf.root, path)
    print("尝试评估被穿孔的路径:", output.hex() if output else "无输出，节点已被穿孔")
except Exception as e:
    print(str(e))

参考

[1] Ratliff Z, Goh W, Wieland A, et al. Holepunch: Fast, Secure File Deletion with Crash Consistency[J]. Cryptology ePrint Archive, 2023.