基于新假设的高效身份基签名方案

### 基于新假设的高效身份基签名方案 在多变量二次（MQ）环境中，身份基签名（IBS）方案的研究一直是密码学领域的重要方向。本文将详细介绍一种基于新假设的高效IBS方案，包括其正确性、安全性论证以及相关问题的复杂度分析。 #### 方案正确性 根据构造可知，$\tilde{P} = \tilde{F} \circ \tilde{T}$。对于所有$z \in F^d$，有$\tilde{P}_z = \tilde{F}_z \circ \tilde{T}_z$。由于$R_z$是非奇异的，所以$\tilde{P}_z = \tilde{F}_z \circ \tilde{T}_z = F_z \circ T_z$。通过对$R_z$的选择，$F_z$将是油醋（oil-and-vinegar）类型。并且，对于所有满足$z = H(id, tok_{id})$的身份$id \in U$，$\tilde{T}_z$始终是非奇异的。因此，$(\tilde{P}_z, (F_z, T_z))$是一个有效的UOV密钥对。方案的正确性可由加盐UOV签名的正确性得出。 #### 安全性论证 在随机预言模型下，我们论证了所提出的IBS构造在$\nu$-PWMQ问题下的安全性。 ##### 定理1 如果$\nu_{ext}$-PWMQ问题是难解的，那么所提出的IBS在经典随机预言模型下是EUF-ID-CMA安全的，其中$\nu_{ext}$是密钥提取查询的数量。 证明过程中，我们假设有一个量子PPT敌手$A$能够破坏签名方案的EUF-ID-CMA安全性。模拟器$S$会得到一个$\nu_{ext}$-PWMQ问题的实例$D := \{\tilde{P}, (z, SK_z)_{z \in V}, z^*, y^*\}$，其目标是找到$x^* \in F^n$，使得$\tilde{P}_{z^*}(x^*) = y^*$。我们将哈希函数$H$和$H_{uov}$都视为随机预言。 敌手$A$对$H$和$H_{uov}$进行的预言查询数量分别为$\nu_{id}$和$\nu_{uov}$。$Q_{ext}$用于存储密钥提取预言中涉及的身份 - 令牌对，$Q_{tok}$用于存储签名预言中每个身份的令牌信息。初始时，$Q_{ext} = \varnothing$且$Q_{tok} = \varnothing$。敌手$A$进行的签名查询数量为$\nu_s$。 模拟器$S$维护两个列表$List_{id}$和$List_{uov}$，分别用于记录$(id||tok, H(id||tok))$和$(m||r, H_{uov}(m||r))$的形式。模拟器$S$随机选择$(i^*, j^*) \overset{U}{\leftarrow} [\nu_{id} + \nu_s] \times [\nu_{uov} + \nu_s]$作为伪造身份$id^*$和消息$m^*$的猜测。 身份空间$U$根据一个偏置硬币（正面概率为$\lambda$）被划分为两个不相交的集合$U_{\lambda}$和$U \setminus U_{\lambda}$。决策一个身份$id$是否属于$U_{\lambda}$的方法是：先抛掷偏置硬币，当且仅当结果为正面时，将$id$分配给$U_{\lambda}$。在模拟过程中，回答密钥提取和签名预言查询的策略如下： 1. **密钥提取查询**：如果$id \in U_{\lambda}$，则中止。 2. **签名查询**： - 如果$id \in U_{\lambda}$，则通过操纵$H_{uov}$预言来回答查询，如同加盐UOV证明中所做的那样。 - 否则，使用相应的秘密密钥运行原始签名算法来回答查询。 模拟器$S$以如下方式回答所有可能以任意顺序出现的预言查询： - **哈希预言（$H$）**： 1. 检查$(id_i||tok_i, *) \in List_{id}$。 - 如果是，则返回$H(id_i||tok_i)$。 - 否则： - 如果$i = i^*$，则设置$List_{id} := List_{id} \cup \{(id_i||tok_i, z^*)\}$并返回$z^*$。 - 否则，随机选择$z_i \overset{U}{\leftarrow} F^d$，设置$List_{id} := List_{id} \cup \{(id_i||tok_i, z_i)\}$并返回$z_i$。 - **密钥提取预言**： 1. 检查$id \notin U_{\lambda}$。 - 如果是，则执行以下步骤： - 随机选择$tok \overset{U}{\leftarrow} TokSpace$。 - 如果$(id||tok, *) \in List_{id}$，则中止。 - 否则，从$V$中选择$z$，设置$List_{id} := List_{id} \cup \{(id||tok, z)\}$，$V := V \setminus \{z\}$，$Q_{ext} := Q_{ext} \cup \{id||tok\}$，并返回密钥$SK_{id} := (tok, SK_z)$。 - 否则，中止。 - **哈希预言（$H_{uov}$）**： 1. 检查$(m_j||r_j, *) \in List_{uov}$。 - 如果是，则返回$H_{uov}(m_j||r_j)$。 - 否则： - 如果$j = j^*$，则设置$List_{uov} := List_{uov} \cup \{(m_j||r_j, y^*)\}$并返回$y^*$。 - 否则，随机选择$y_j \overset{U}{\leftarrow} F^m$，设置$List_{uov} := List_{uov} \cup \{(m_j||r_j, y_j)\}$并返回$y_j$。 - **签名预言**：