ThresholdandMulti-signatureSchemesfromLinearHashFunctions

# Threshold and Multi-signature Schemes from Linear Hash Functions ## 1. Introduction Linear hash functions offer a new perspective for constructing threshold and multi - signature schemes. We first define a function $\Phi(x) := x + u(B)z^{\ast}$, where $z^{\ast} \in D$ and $u(B) \in S^q$ are defined by the following claim. ### 1.1 Claim 2 There exists $z^{\ast} \in D$ such that $F(z^{\ast}) = 0$ and for any matrix $A \in S^{\ell\times q}$ where $0 < \ell < q$, there exists a vector $u(A) \in S^q$ and $i \in [q]$ such that $Au(A) = 0 \land \exists i \in [q] : u(A)_i z^{\ast} \neq 0$. **Proof**: Since $F$ is not a monomorphism from $D$ to $R$, there exists a non - zero element $z^{\ast} \in D$ such that $F(z^{\ast}) = 0$. As $S$ is a field and $A$ has rank at most $\ell < q$, there exists a non - zero vector $u(A) \in S^q$ such that $Au(A) = 0$. Also, since $u(A)$ is non - zero, there exists $i \in [q]$ such that $u(A)_i \neq 0$, and since $S$ is a field and $z^{\ast} \neq 0$, we have $u(A)_i z^{\ast} \neq 0$. ### 1.2 Analysis of $\Phi$ - **Execution identity**: For simplicity, let $u = u(B)$. The executions of $A$ given $(par, x)$ and $(par, \Phi(x))$ are identical. Since $F(\Phi(x)) = F(x)+u\cdot F(z^{\ast}) = F(x)$, the challenges output by $Chal$ are the same. For the $j$ - th query to $PI$, if the prior views of $A$ are identical, $A$ makes the same query. Also, $A$ receives the same value from $PI$ in both executions. By induction, the views of $A$ are identical, so $\Phi(x) \in W_A$ and $\Phi$ is a map from $W_A$ to $W_A$. - **Winning condition**: It is clear that $x \in W_B \vee \Phi(x) \in W_B$. Since the executions of $A$ given $x$ and $\Phi(x)$ are identical, and there exists $i \in [q]$ such that $u_iz^{\ast} \neq 0$, either $y_i \neq x_i$ or $y_i \neq x_i + u_i\cdot z^{\ast}$, meaning $WIN_B$ occurs either in the execution given $x$ or $\Phi(x)$. - **Bijection proof**: Since the domain and range of $\Phi$ are $W_A$ (a finite set), it suffices to show $\Phi$ is an injection. For any $x_1,x_2 \in W_A$ such that $\Phi(x_1)=\Phi(x_2)$, the executions of $A$ given $x_1$ and $x_2$ are identical, so the query matrix $B$ is the same. Then $\Phi(x_1)=x_1 + uz^{\ast}$ and $\Phi(x_2)=x_2 + uz^{\ast}$, which implies $x_1 = x_2$. So $\Phi$ is an injection. ## 2. Schemes Based on Linear Hash Functions A cyclic group $G$ of prime size $p$ with generator $g$ can be related to a linear hash function described by $(S, D, R, F)$. Here, $R$ corresponds to the group $G$, the pre - image under $F$ corresponds to the discrete logarithm to base $g$, and $S$ corresponds to the field of scalar $\mathbb{Z}_p$. The $AOMPR$ game is analogous to the $AOMDL$ game, suggesting a way to transform $AOMDL$ - secure schemes into $AOMPR$ - secure schemes based on linear hash functions. ### 2.1 Multi - signatures #### 2.1.1 MuSig2 Overview MuSig2 is a two - round multi - signature scheme with key aggregation, and the first signing round is message - independent. #### 2.1.2 Syntax A two - round multi - signature scheme with key aggregation is a tuple of algorithms $MS=(Setup, KeyGen, KeyAgg, PreSign, PreAgg, Sign, SignAgg, Ver)$: | Algorithm | Function | | --- | --- | | $Setup(1^{\kappa})$ | Returns a system parameter $par$ | | $KeyGen()$ | Returns a pair of secret and public keys $(sk, pk)$ | | $KeyAgg(L)$ | Takes a multiset of public keys $L$ (size at most $2^{\kappa}$) and returns an aggregate public key $apk$ | | $PreSign()$ | Each signer runs this to get $(pp, st)$ | | $PreAgg(\{pp_1,\cdots,pp_n\})$ | Aggregator runs this to get $app$ | | $Sign(st, app, sk, pk, m, L)$ | Signer runs this to get $out$ | | $SignAgg(\{out_1,\cdots,out_n\})$ | Aggregator runs this to get the signature $\sigma$ | | $Ver(apk, m, \sigma)$ | Verifies if $\sigma$ is valid for $apk$ and $m$ | The signing protocol for $n$ signers to sign a message $m$ is as follows: ```mermaid graph LR classDef startend fill:#F5EBFF,stroke:#BE8FED,stroke - width:2px classDef process fill:#E5F6FF,stroke:#73A6FF,stroke - width:2px A([Start]):::startend --> B(Each signer: <br ```

最低0.47元/天解锁专栏

赠100次下载

继续阅读点击查看下一篇

400次会员资源下载次数

300万+ 优质博客文章

1000万+ 优质下载资源

1000万+ 优质文库回答

复制全文

ThresholdandMulti-signatureSchemesfromLinearHashFunctions

相关推荐

专栏目录

ThresholdandMulti-signatureSchemesfromLinearHashFunctions

相关推荐

2025年大模型推理缓存策略-基础卷（含答案及解析）.docx

基于混合整数二阶锥规划的高比例清洁能源配电网重构技术研究 注意：标题的长度应保持在合适的范围内，并直接根据您的文字内容进行概括提炼。 需求响应

新电音助手v2.0（百万网红都在使用的自动修音软件）

netty-codec-memcache-4.1.121.Final.jar中文-英文对照文档.zip

用于ONNX中Segment Anythin 2（SAM2）模型的Python脚本，ONNX-SAM2-Segment-Anything.zip

张泽耀_tensorrt sahi yolo 目标检测.zip

2025年大模型评估指标体系专项试题-基础卷（含答案及解析）.docx

json-path-2.7.0.jar中文-英文对照文档.zip

netty-resolver-dns-4.1.121.Final.jar中文-英文对照文档.zip

在移动机器人上通过与Mono VINS的传感器融合改进YOLO检测_Improved YOLO detection by

软考考点之死锁资源数计算银行家算法

张量，约洛夫，约洛夫_tensorrt5, yolov4, yolov3,yolov3-tniy,yolov3-tniy

专栏目录

最新推荐

具有多重时滞和不确定参数的CRDNNs的无源性与同步性研究

OpenVX：跨平台高效编程的秘诀

HNPU-V1：自适应DNN训练处理器的技术解析与性能评估

语音情感识别：预加重滤波器与清音影响分析

网络数据上的无监督机器学习

言语节奏与大脑定时模式：探索神经机制与应用

自适应复杂网络结构中的同步现象解析

利用大数据进行高效机器学习

计算机视觉中的概率图模型：不完整数据下的贝叶斯网络学习

SSH连接与操作全解析

基于混合整数二阶锥规划的高比例清洁能源配电网重构技术研究注意：标题的长度应保持在合适的范围内，并直接根据您的文字内容进行概括提炼。需求响应