Blind signature and ring signature schemes: Rehabilitation and attack

Blind signature and ring signature are two signature schemes with privacy concern. Zhang [Jianhong Zhang, Linkability analysis of some blind signature schemes, In International Conference on Computational Intelligence and Security 2006, IEEE, vol. 2, 2006, pp. 1367–1370, (Available at http://dx.doi.org/10.1109/ICCIAS.2006.295283.)] analyzed the unlinkability of Zhang and Kim [Fangguo Zhang, Kwangjo Kim, ID-based blind signature and ring signature from pairings, in: Yuliang Zheng (Ed.), Advances in Cryptology — ASIACRYPT 2002, 8th International Conference on the Theory and Application of Cryptology and Information Security, Queenstown, New Zealand, December 1–5, 2002, Proceedings, Lecture Notes in Computer Science, vol. 2501, Springer, 2002, pp. 533–547], Huang et al. [Zhenjie Huang, Kefei Chen, Yumin Wang, Efficient identity-based signatures and blind signatures, in: Yvo Desmedt, Huaxiong Wang, Yi Mu, Yongqing Li (Eds.), Cryptology and Network Security, 4th International Conference, CANS 2005, Xiamen, China, December 14–16, 2005, Proceedings, Lecture Notes in Computer Science, vol. 3810, Springer, 2005, pp. 120–133] and Wu et al. [Qianhong Wu, Willy Susilo, Yi Mu, Fangguo Zhang, Efficient partially blind signatures with provable security, in: Osvaldo Gervasi, Marina L. Gavrilova, (Eds.), Computational Science and Its Applications — ICCSA 2007, International Conference, Kuala Lumpur, Malaysia, August 26–29, 2007. Proceedings. Part III, Lecture Notes in Computer Science, vol. 4707, Springer, 2007, pp. 1096–1105] and claimed that they are indeed linkable. On the other hand, Gamage et al. [Chandana Gamage, Ben Gras, Bruno Crispo, Andrew S. Tanenbaum, An identity-based ring signature scheme with enhanced privacy, Securecomm and Workshops 2006, IEEE, 2006, pp. 1–5, (Available at http://dx.doi.org/10.1109/SECCOMW.2006.359554)] claimed that the scheme of Chow et al. [Sherman S.M. Chow, Siu-Ming Yiu, Lucas Chi Kwong Hui, Efficient identity based ring signature, in: John Ioannidis, Angelos D. Keromytis, Moti Yung (Eds.), Applied Cryptography and Network Security, Third International Conference, ACNS 2005, New York, NY, USA, June 7–10, 2005, Proceedings, Lecture Notes in Computer Science, vol. 3531, 2005, pp. 499–512] is vulnerable to key exposure attack. This paper shows that all these claims are incorrect. Furthermore, we show that the scheme proposed by Gamage et al. [Chandana Gamage, Ben Gras, Bruno Crispo, Andrew S. Tanenbaum, An identity-based ring signature scheme with enhanced privacy, Securecomm and Workshops 2006, IEEE, 2006, pp. 1–5, (Available at http://dx.doi.org/10.1109/SECCOMW.2006.359554)] which aimed to provide enhanced privacy actually has privacy level reduced. We hope this work can pinpoint the standard one should use when analyzing the unlinkability of blind signatures and the anonymity of ring signatures.     

Unconditional secure conference key distribution schemes with disenrollment capability

A conference key distribution scheme with disenrollment capability is a method to distribute pieces of information among a set of users in such a way that each group of them can compute a common key to be used for secure communication. In such a scheme any user can be disenrolled. After each disenrollment, although the disenrolled user reveals his private information, the security of the scheme remains unchanged. The scheme is unconditional secure if any adversary coalition has no information on the common key even though it has access to an infinite computational power.

In this paper we model the problem of unconditionally secure conference key distribution schemes with disenrollment capability using an information theoretical framework. We prove tight lower bounds on the size of information each user in the scheme has to keep secret.     

Flaws in some self-healing key distribution schemes with revocation

Dutta and Mukhopadhyay have recently proposed some very efficient self-healing key distribution schemes with revocation. The parameters of these schemes contradict some results (lower bounds) presented by Blundo et al. In this paper different attacks against the schemes of Dutta and Mukhopadhyay are explained: one of them can be easily avoided with a slight modification in the schemes, but the other one is really serious.     

Multicast key distribution schemes based on Stinson-Van Trung designs

The efficiency characteristics of multicast key distribution schemes based on (v, b, r, λ)-designs are investigated. The stability and connectivity of such designs are estimated. These estimates generalize and enhance the well-known estimates for the efficiency characteristics of multicast key distribution schemes based on incomplete block designs. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 100–111, May–June 2007.     

Generalized Beimel-Chor schemes for broadcast encryption and interactive key distribution

In 1993, Beimel and Chor presented an unconditionally secure interactive protocol which allows a subset of users in a network to establish a common key. This scheme made use of a key predistribution scheme due to Blom. In this paper, we describe some variations and generalizations of the Beimel-Chor scheme, including broadcast encryption schemes as well as interactive key distribution schemes. Our constructions use the key predistribution scheme of Blundo et al., which is a generalization of the Blom scheme. We obtain families of schemes in which the amount of secret information held by the network users can be traded off against the amount of information that needs to be broadcast. We also consider lower bounds for protocols of these types, using the concept of entropy as our main tool. Some of our schemes are optimal (or close to optimal) with respect to the bounds we prove.     

Improvements of authenticated encryption schemes with message linkages for message flows

Recently, Tseng et al. proposed two authenticated encryption schemes (basic scheme and generalized scheme) with message linkages, which are efficient in terms of the communication and computation costs in comparison with all the previously proposed schemes. The basic authenticated encryption scheme suited for only after receiving the entire signature blocks, the recipient can then recover the message blocks. In order to allow the receiver to perform the receiving and the recovering processes simultaneously according to application requirements and the transmission efficiency of the network, the generalized authenticated encryption scheme was then proposed. In this paper, we show that both Tseng et al.’s authenticated encryption schemes do not achieve integrity and authentication. Improvements are then proposed to repair the weaknesses.     

对两类无证书签名方案的密码学分析

对Xu等提出的无证书签名方案和Fan的无证书代理签名方案进行了安全性分析,指出Xu的签名方案是可以普遍伪造的。而Fan的代理签名方案中,原始签名人在授权过程中泄露了自己的私钥,且该代理签名不能抵抗公钥替换攻击,即任何人（没有代理私钥）只要替换了原始签名人和代理签名人的公钥就可以伪造代理签名人的代理签名。     

A comparison of two chromosome representation schemes used in solving a family-based scheduling problem

Meta-heuristic algorithms have been widely used in solving scheduling problems; previous studies focused on enhancing existing algorithmic mechanisms. This study advocates a new perspective—developing new chromosome (solution) representation schemes may improve the performance of existing meta-heuristic algorithms. In the context of a scheduling problem, known as permutation manufacturing-cell flow shop (PMFS), we compare the effectiveness of two chromosome representation schemes (S_old and S_new) while they are embedded in a meta-heuristic algorithm to solve the PMFS scheduling problem. Two existing meta-heuristic algorithms, genetic algorithm (GA) and ant colony optimization (ACO), are tested. Denote a tested meta-heuristic algorithm by X_Y, where X represents an algorithmic mechanism and Y represents a chromosome representation. Experiment results indicate that GA_ S_new outperforms GA_S_old, and ACO_S_new also outperforms ACO_S_old. These findings reveal the importance of developing new chromosome representations in the application of meta-heuristic algorithms.     

Secure proxy signature schemes from the Weil pairing

A proxy signature scheme is a method which allows an original signer to delegate his signing authority to a designated person, called a proxy signer. Up to now, most of proxy signature schemes are based on the discrete logarithm problem. In this paper, we propose a proxy signature scheme and a threshold proxy signature scheme from the Weil pairing, and also provide a security proof.     

Collaborative systems: solving the vocabulary problem

Vocabulary differences have created difficulties for on-line information retrieval systems and are even more of a problem in computer-supported cooperative work (CSCW), where collaborators with different backgrounds engage in the exchange of ideas and information. We have investigated two questions related to the vocabulary problem in CSCW. First, what are the nature and characteristics of the vocabulary problem in collaboration, and are they different from those observed in information retrieval or in human-computer interactions research? Second, how can computer technologies and information systems be designed to help alleviate the vocabulary problem and foster seamless collaboration? We examine the vocabulary problem in CSCW and suggest a robust algorithmic solution to the problem     

一种求解多维背包问题的混合分布估计算法

针对多维背包问题（MKP）,提出一种基于分布估计算法的混合求解算法,该算法基于优势种群构建概率模型,并基于概率模型采样产生新个体;同时,提出一种基于MKP问题信息的修复机制,有效修复采样后种群中的不可行解．另外,设计了一种自适应的局部搜索操作,以增强算法的局部搜索能力,基于标准测试集的仿真结果和算法比较验证了所提出的混合算法的有效性和鲁棒性．     

一些代理签名方案的进一步改进

对两个不需要安全信道的代理签名方案进行了分析,发现它们并不满足不可伪造性。在[4]中不能抵抗原始签名人改变攻击,在[5]中原始签名人可以伪造一个有效的代理签名。提出一个改进的强代理签名方案,新方案在不增加计算复杂性的前提下,保证了签名的安全性,同时代理授权过程中仍然保持不需要安全信道。     

可证明安全数字签名方案的密码学分析

为了克服基于身份密码体制的密钥托管问题和基于无证书密码体制的公钥替换问题, 研究者提出了基于证书密码体制的概念。针对李志敏等人提出的基于证书的签名方案提出分析, 证明其不满足不可伪造性; 针对黄茹芬等人提出的基于证书盲签名方案提出分析, 结果表明它不能抵抗公钥替换攻击; 对何俊杰提出的基于身份的部分盲签名方案提出分析, 指出它不能抵抗窜改协商公共信息攻击。     

基于身份数字签名方案的通用可组合安全性

在通用可组合安全性框架下定义了基于身份的数字签名方案的通用可组合安全性。证明了基于身份数字签名方案的通用可组合安全性与传统的安全性——在选择消息和选择身份攻击下的不可存在性伪造——之间的等价性。这一结果表明基于身份的数字签名方案可以作为安全的密码原语用于构建更复杂的密码协议。     

一个无证书代理盲签名方案的改进

无证书公钥系统克服了传统基于证书公钥系统中的证书管理问题和基于身份公钥系统中的密钥托管问题,是目前的研究热点之一。对陈虎等人新近提出的一个无证书代理盲签名方案进行了安全性分析,发现该签名方案存在严重的安全缺陷,即不诚实的用户能够恢复出代理签名人的代理私钥,从而能做代理签名人所能做的任何事情。最后,给出了一个克服该攻击的改进方法,并且改进后方案的安全性仍然是基于CDH问题。     

两个无证书代理签名方案的密码学分析

针对最近提出的两个无证书代理签名方案及其改进方案,从密码学的角度对其安全性进行了研究,指出其存在相同的安全性缺陷,即攻击者能够实施公钥替换攻击,从而能伪造出有效签名,并分析了存在公钥替换攻击的正确性及原因.同时,也指出了另外一个缺陷即攻击者可以假冒原始签名人将任何消息的代理签名权委托给任何代理人.实验结果表明,该方案的设计并不满足数字签名方案所需的安全性要求.最后,给出了克服各种攻击的改进措施.     

Reexamining the security of fair quantum blind signature schemes

In this paper, we reexamined the security of fair quantum blind signature protocols and found there exists a secure leakage caused by the reuse of signing key. To illustrate it, a new attack strategy is proposed based on unambiguous set discrimination of quantum state. In this attack, the attacker can forge a valid signature for any message when he owns three signatures. Finally, a feasible improved method is proposed to solve this problem.     

求解RCPSP问题的带分布估计的差异演化算法

提出一种带分布估计的差异演化算法（DEED）用于求解资源受限项目调度问题（RCPSP）。该算法基于差异演化（DE）算法,利用分布估计算法（EDA）能够获得问题解空间的全局信息以及变量间的相互联系,以指导算法搜索过程,并对最优解的分布进行预测。DEED算法充分利用DE收敛速度快和EDA全局搜索优点。经标准问题库（PSPLIB）的单模式问题集验证,并与当前流行的算法进行比较,表明了DEED算法的有效性。     

A hybrid estimation of distribution algorithm for solving the resource-constrained project scheduling problem

In this paper, a hybrid estimation of distribution algorithm (HEDA) is proposed to solve the resource-constrained project scheduling problem (RCPSP). In the HEDA, the individuals are encoded based on the extended active list (EAL) and decoded by serial schedule generation scheme (SGS), and a novel probability model updating mechanism is proposed for well sampling the promising searching region. To further improve the searching quality, a Forward-Backward iteration (FBI) and a permutation based local search method (PBLS) are incorporated into the EDA based search to enhance the exploitation ability. Simulation results based on benchmarks and comparisons with some existing algorithms demonstrate the effectiveness of the proposed HEDA.