Page 265 - 《软件学报》2021年第10期

刘镇 等:安全随机数部分重用及在多接收方签密的应用 3237

and multi-receiver signcryption scheme with the re-use of partial randomness can effectively save bandwidth and computation, and it
provides a general construction method for multi-message to multi-receiver signcryption.
Key words: signcryption; multi-receiver; re-use of partial randomness; provable security; quantum attack resistance
1 引 言

1.1 研究背景
在通信领域中会经常遇到一个用户向多个用户发送消息的场景,这里面又可分为两种情况:一种情况发送
的消息是相同的,我们称为单消息多接收方(single message to multi receivers,简称 SM-MR)通信;另一种情况发
送的消息是不同的,我们称为多消息多接收方(multi messages to multi receivers,简称 MM-MR)通信.MM-MR 可
以看作是多用户通信的一般场景,而 SM-MR 则可以看作是一种特殊的 MM-MR 通信.在 MM-MR 通信中,消息
的传输通常是以广播的方式进行的,因此在构造 MM-MR 通信方案时,在不影响通信内容的前提下有效降低通
信量,对系统性能的提升具有重要意义.
信息安全问题是通信系统需要考虑的一个重要内容,为了保护信息的机密性和完整性,最常用的方法是使
用密码技术.要实现多用户环境下的密码通信,最直接的方法是将一对一的标准密码方案独立使用多次,这种方
[1]
法虽然简单,但是多消息多用户通信可能存在内部敌手,此时一些方案可能不安全.例如,Håstad 发现,独立使用
[3]
[2]
RSA 方案用于多接收方就有可能泄露信息.Baudron 等人 和 Bellare 等人 分别对多接收方加密的安全条件进
行了证明,他们指出:如果基础方案是不可区分性安全的,那么独立使用多次的方案也是不可区分性安全的.该
结果可以用来检验多接收方密码方案的安全性,但没有考虑到系统通信性能的优化.这种直接方式构造的多接
收方密码方案,会带来系统通信量 N(设接收方个数为 N)倍的增长.
公钥密码方案为了满足特定的安全性,都会引入一些随机数,于是需要增加一些冗余信息来辅助解密,而这
些冗余信息造成了密文的膨胀.如果在构造多接收方密码方案多次执行标准密码方案过程中适当地重用一些
随机数,就可以有效降低系统的开销,节约通信和计算量.然而,随机数对方案的安全性至关重要,重用随机数可
能导致方案产生严重的安全问题,因此,研究满足何种条件时在构造多接收方密码方案多次执行标准密码方案
重用随机数才安全,是一项具有实用意义的工作.

1.2 相关工作
[4]
[5]
为了提高多接收方加密方案的计算和通信效率,Kurosawa 提出了随机数重用的概念,并基于 ElGamal 和
[6]
Cramer-Shoup 方案+构造了随机数重用的多接收方加密方案.例如,发送方 S 想要用 EIGamal 加密发送消息 m i
给接收方 R i ,其中,R i 的公钥为 PK  i g i x (i  1,2,..., ).N 最直接的方式是独立随机选择 N 个随机数(r 1 ,r 2 ,…,r N ),对
i r
i=1,2,…,N,分别计算接收方 R i 的密文 c  (g m g x i i r ), 最后将密文 C=(c 1 ,c 2 ,…,c N )广播给接收方.而 Kurosawa 的
,
i
i
r
随机数重用方式是只选择一个随机数 r,计算密文 C  (g m g 1 xr ,m g 2 x r ,...,m g x N r ) 并广播给接收方,两者密文量
,
N
2
1
对比如图 1 所示.与直接构造的多接收方加密方案相比,系统的通信和计算开销节省了将近一半.
直接方式: S R=(R 1,...,R N)
重用随机数
方式: S R=(R 1,...,R N)
Fig.1 Comperision of ciphertex size for multi-receivers encryption
between naive construction and randomness re-use construction
图 1 直接方式与随机数重用方式构造的多接收方加密方案密文量对比

通常,随机数对系统的安全性至关重要,随机数重用可能会导致严重的安全问题.但是,Kurosawa 指出:在某
些情况下,随机数重用并不会影响系统的安全性.Bellare 等人 [7,8] 系统地研究了随机数重用相关理论及其在构造