RSAthresholdsignature.pdf资源-CSDN文库

RSA门限签名

英语论文

需积分: 9 45 浏览量 2020-06-21 10:29:50 上传评论 1 收藏 144KB PDF 举报

资源推荐

资源详情

资源评论

Practical Threshold Signatures

Victor Shoup

IBM Zurich Research Lab, S¨aumerstr. 4, 8803 R¨uschlikon, Switzerland

sho@zurich.ibm.com

Abstract. We present an RSA threshold signature scheme. The scheme

enjoys the following properties:

1. it is unforgeable and robust in the random oracle model, assuming

the RSA problem is hard;

2. signature share generation and veriﬁcation is completely non-inter-

active;

3. the size of an individual signature share is bounded by a constant

times the size of the RSA modulus.

1 Introduction

A k out of l threshold signature scheme is a protocol that allows any subset of k

players out of l to generate a signature, but that disallows the creation of a valid

signature if fewer than k players participate in the protocol. This non-forgeability

property should hold even if some subset of less than k players are corrupted

and work together. For a threshold scheme to be useful when some players are

corrupted, it should should also be robust, meaning that corrupted players should

not be able to prevent uncorrupted players from generating signatures.

The notion of a threshold signature scheme has been extensively studied.

However, all previously proposed schemes suﬀer from at least one of the following

problems:

1. the scheme has no rigorous security proof, even in the random oracle model;

2. signature share generation and/or veriﬁcation is interactive, moreover re-

quiring a synchronous communications network;

3. the size of an individual signature share blows up linearly in the number of

players.

To correct this situation, we present a new threshold RSA signature scheme

that enjoys the following properties:

1. it is unforgeable and robust in the random oracle model, assuming the RSA

problem is hard;

2. signature share generation and veriﬁcation is completely non-interactive;

3. the size of an individual signature share is bounded by a small constant times

the size of the RSA modulus.

210 Victor Shoup

We stress that the resulting signature is a completely standard “hash and

invert” RSA signature, in the sense that the format of the public key and veriﬁ-

cation algorithm are the same as for ordinary RSA signatures. We do, however,

place some restrictions on the key; namely, the public exponent must be a prime

exceeding l, and the modulus must be the product of two “strong” primes.

Our scheme is exceedingly simple, and it is truly amazing that such a scheme

has apparently not been previously proposed and analyzed.

We also consider a more reﬁned notion of a threshold signature scheme, where

there is one threshold t for the maximum number of corrupt players, and another

threshold k for the minimum quarum size. The fact that a particular message

has been signed means that at least k − t uncorrupted players have authorized

the signature.

Previous investigations into threshold signature schemes have always as-

sumed (explicitly or implicitly) that k = t + 1. We also investigate the more

general setting where k ≥ t + 1. This generalization is useful in situations where

the uncorrupted parties do not necessarily agree on what they are signing, but

one wants to be able to prove that a large number of them have authorized

a particular signature. In particular, threshold signatures with k = l − t and

t < l/3 can be exploited to reduce the sizes of the messages sent in Byzantine

agreement protocols in an asynchronous network. This is explored in detail in

[CKS00].

The application to asynchronous Byzantine agreement was actually our orig-

inal motivation for studying this problem, and is the main reason for our require-

ment that the signing protocol is non-interactive. Almost all previous work on

threshold signatures assumes a model with a synchronous network, and where all

players somehow simultaneously agree to start the signing protocol on a given

message. Clearly, we can not work in such a model if we want to implement

asynchronous Byzantine agreement.

We stress that our notion of a “dual-parameter” threshold scheme provides

stronger security guarantees than single parameter threshold schemes, and such

schemes are in fact more challenging to construct and to analyze. Our notion of

a dual-parameter threshold scheme should not be confused with a weaker notion

that sometimes appears in the threshold cryptography literature (e.g., [MS95]).

For this weaker notion, there is a parameter k

> t such that the reconstruction

algorithm requires k

shares, but the security guarantee is lost if just a single

honest party reveals a share. In our notion, no security is lost unless k − t honest

parties reveal their shares.

We work with a “static corruption model”: the adversary must choose which

players to corrupt at the very beginning the attack. This is in line with previ-

ous investigations into threshold signatures, which also (explicitly or implicitly)

assume static corruptions.

Our basic scheme, Protocol 1, can be proven secure when k = t + 1 in the

random oracle model under the RSA assumption.

Practical Threshold Signatures 211

We present another scheme, Protocol 2, for use in the more general setting

k ≥ t + 1. Protocol 2 can be be proven secure—again, in the random oracle

model—when k = t + 1 under the RSA assumption, and when k > t + 1 under

an additional assumption, namely, an appropriate variant of the Decision Diﬃe-

Hellman assumption.

As already mentioned, our proofs of security are valid in the so-called “ran-

dom oracle model,” where cryptographic hash functions are replaced by a ran-

dom oracle. This model was used informally by Fiat and Shamir [FS87], and

later was rigorously formalized and more fully exploited in Bellare and Rogaway

[BR93], and thereafter used in numerous papers.

For Protocol 1, we only need random oracles for robustness, if we assume that

ordinary RSA signatures are secure. In fact, Gennaro et al. [GJKR96a] present a

non-interactive share veriﬁcation scheme that can be analyzed without resorting

to random oracles. One could use their veriﬁcation scheme in place of the one

we suggest, thus avoiding random oracles in the analysis, but this would have

certain practical drawbacks, requiring a special relationship between the sender

and recipient of a share of a signature. Alternatively, one could use a simple

interactive share veriﬁcation scheme. The resulting signature scheme would no

longer be truly non-interactive, but it would still not require any coordination

or synchronization among the players. We do not explore these alternatives in

any detail here, as they are quite straightforward.

The analysis of Protocol 2 makes use of the random oracle model in a more

fundamental way. Since this seemed inevitable, we took several liberties in the

design of Protocol 2, so that it is actually a bit simpler and more eﬃcient than

Protocol 1. Thus, even if k = t + 1, Protocol 2 may be an attractive practical

alternative to Protocol 1.

We view a proof of security in the random oracle model as a heuristic argu-

ment that provides strong evidence that a system cannot be broken. All things

being equal, a proof of security in the random oracle model is not as good as

a proof of security in the “real world,” but is much better than no proof at

all. Anyway, it does not seem unreasonable to use the random oracle model,

since that is the only way we know of to justify the security of ordinary RSA

signatures.

Previous Work

Desmedt [Des87] introduces the more general notion of threshold signatures.

Desmedt and Frankel [DF89] present a non-robust threshold ElGamal scheme

[ElG85] based on “secret sharing,” [Sha79] i.e., polynomial interpolation over

a ﬁnite ﬁeld. Their scheme has small share size, but requires synchronized in-

teraction. Harn [Har94] presents a robust threshold ElGamal scheme with small

share size, but again requires synchronized interaction. It seems that the security

of both of the above schemes can be rigorously analyzed in a satisfactory way,

although neither paper does this. Gennaro et al. [GJKR96b] present a robust

threshold DSS scheme with small share size that again requires synchronized

interaction; they also give a rigorous security analysis.

剩余13页未读，继续阅读

评论收藏

内容反馈

区块链之美

粉丝: 590
资源: 4

RSA threshold signature.pdf

最新资源

RSA threshold signature.pdf

threshold-signatures：ECDSA的阈值签名方案

论文研究-一种基于RSA安全可行的（t，n）门限签名方案.pdf

分布式无中心授权的属性基可变门限环签名.pdf

spring-security-rsa-1.0.10.RELEASE-API文档-中文版.zip

RSA case studies.pdf

easy-rsa-2.2.2.tar.gz

PyPI 官网下载 | rsa-3.4.1.tar.gz

RSA依赖jar.zip

spring-security-rsa-1.0.10.RELEASE-API文档-中英对照版.zip

easy-rsa.tar.gz

spring-security-rsa-1.0.3.RELEASE.jar

PKCS #1 v2.2 RSA Cryptography Standard.pdf

rsa_sign.c.zip_rsa_rsa sign_rsa sign_rsa signature

RSA算法描述.pdf

RSA_FINAL.rar_RSA素数_visual c_大素数生成

C#实现RSA加密算法.pdf

easy-rsa-2.2.0.tar.gz

基于Montgomery模乘的RSA加密处理器.pdf

Web端RSA加密机密库包含RSA.js Barrett.js BigInt.js JavaScript文件，直接解压即可使用

Postman利用forgeJS实现RSA加解密.zip

PyPI 官网下载 | rsa-3.1.tar.gz

rsa.pack.js

RSA加密算法.ppt

RSA算法实验报告.pdf

轩禹CTF_RSA工具3.6.1.zip

RSA-csharp.rar

论文研究-基于Smartphone的服务器辅助RSA密钥生成.pdf

最新资源