A new threshold proxy signature scheme from bilinear pairings

~~A new threshold proxy signature scheme from bilinear pairings~~     

基于bilinear pairings的签名方案

近来bilinear pairings如weil配对或Tate配对和非奇异椭圆曲线在加密技术中有着广泛的应用。利用椭圆曲线上的weil配对的双线性性质构造了一个新的数字签名方案和一个盲签名方案,并对它们的安全性和应用前景做了分析。这种方案是建立在目前还没有有效攻击方法的有限域上非奇异椭圆曲线离故对数问题之上的,所以是安全的,并且具有一定的实用价值。     

Efficient Tate pairing computation using double-base chains

Pairing-based cryptosystems have developed very fast in the last few years. The efficiencies of these cryptosystems depend on the computation of the bilinear pairings, In this paper, a new efficient algorithm based on double-base chains for computing the Tate pairing is proposed for odd characteristic p 〉 3. The inherent sparseness of double-base number system reduces the computational cost for computing the Tate pairing evidently. The new algorithm is 9% faster than the previous fastest method for the embedding degree k = 6.     

Implementation of Cryptosystems Based on Tate Pairing

Tate pairings over elliptic curves are important in cryptography since they can be used to construct efficient identity-based cryptosystems, and their implementation dominantly determines the efficiencies of the cryptosystems. In this paper, the implementation of a cryptosystem is provided based on the Tate pairing over a supersingular elliptic curve of MOV degree 3. The implementation is primarily designed to re-use low-level codes developed in implementation of usual elliptic curve cryptosystems. The paper studies how to construct the underlying ground field and its extension to accelerate the finite field arithmetic, and presents a technique to speedup the time-consuming powering in the Tate pairing algorithm.     

椭圆曲线Tate对的压缩

利用有限域包含的循环群之间的映射,给出了特征为素数p,MOV次数为3的超奇异椭圆曲线上的一类Tate对的两种有效压缩方法,它们分别将Tate对的值从6logp比特长的串压缩到3logp和2logp比特长.两种压缩方法的实现均使用原有Tate对的优化算法的代码,不需要针对压缩对编写新的实现代码,而且两种压缩对的实现均保持原有Tate对的实现速度.     

一种不含双线性对的无证书有序多重签名方案*

提出了一种不含双线性对的无证书有序多重签名方案,即结合不含双线对运算的无证书签名和有序多重签名的思想。与一般无证书数字签名体制不同的是,不含双线性对运算的无证书密码体制没有复杂的双线性对运算,且在计算效率方面具有明显的优势。最后对方案进行安全分析,能抵抗替换公钥攻击,安全性较高。     

Aircrew pairings with possible repetitions of the same flight number

A crew pairing is a sequence of flights, connections and rests that starts and ends at a crew base and is assigned to a single crew. The crew pairing problem consists of determining a minimum cost set of feasible crew pairings such that each flight is covered exactly once and side constraints are satisfied. Traditionally, this problem has been solved in the industry by a heuristic three-phase approach that solves sequentially a daily, a weekly, and a monthly problem. This approach prohibits or strongly penalizes the repetition of the same flight number in a pairing. In this paper, we highlight two weaknesses of the three-phase approach and propose alternative solution approaches that exploit flight number repetitions in pairings. First, when the flight schedule is irregular, we show that better quality solutions can be obtained in less computational time if the first two phases are skipped and the monthly problem is solved directly using a rolling horizon approach based on column generation. Second, for completely regular flight schedules, we show that better quality solutions can be derived by skipping the daily problem phase and solving the weekly problem directly.     

Efficient identity-based threshold decryption scheme from bilinear pairings

Using Shamir’s secret sharing scheme to indirectly share the identity-based private key in the form of a pairing group element, we propose an efficient identity-based threshold decryption scheme from pairings and prove its security in the random oracle model. This new paring-based scheme features a few improvements compared with other schemes in the literature. The two most noticeable features are its efficiency, by drastically reducing the number of pairing computations, and the ability it gives the user to share the identity-based private key without requiring any access to a private key generator. With the ability it gives the user to share the identity-based private key, our ID-based threshold decryption (IBTD) scheme, the second of its kind, is significantly more efficient than the first scheme, which was developed by Baek and Zheng, at the expense of a slightly increased ciphertext length. In fact, our IBTD scheme tries to use as few bilinear pairings as possible, especially without depending on the suite of Baek–Zheng secret sharing tools based on pairings.     

一种门限的双线性基盲签名方案

提出了一种新型的门限盲签名方案,称为基于双线性映射的门限盲签名方案。该方案使用椭圆曲线上的Weil对和Shamir的秘密分享方法来构造,并分析了新方案的正确性和安全性,分析结果表明,在双线性Diffie-Hellman难题下,参与者能方便地产生个体盲签名,公开验证者可通过验证公式决定是否接受发送方计算出的门限盲签名。而任何攻击者不能伪造个体盲签名,即使已知所有参与者的秘密值也无法伪造门限盲签名。     

高效不含双线性对的基于证书签名方案

目前大多数基于证书密码体制的数字签名方案都使用双线性对构造, 计算开销较大、计算效率低, 因此有必要研究更安全、更高效的基于证书签名方案。基于离散对数难题和分叉引理, 提出了一个不含双线性对运算的基于证书数字签名方案, 并在随机预言模型下证明了方案的安全性, 分析了方案的效率。分析表明, 方案可以抵抗用户伪造攻击和CA伪造攻击, 抵抗公钥替换攻击, 并且计算效率较高, 适合应用于移动通信等计算能力和带宽受限的领域。     

基于双线性对的代理签名

双线性映射作为一种构建密码体制的新工具,在密码学领域中引起了普遍的关注,并在数字签名中得到应用。在代理签名方案中,代理签名人可以代表原始签名人生成签名;在代理多签名方案中,一个代理签名人可以同时代表多个原始签名人在文件上签名。利用椭圆曲线上的Weil配对的双线性性质构造了一个代理数字签名方案和一个代理多签名方案,并对它们的正确性和安全性做了分析。在代理多签名方案中,代理签名的长度均独立于原始签名人的个数,其验证也与一般的代理签名类似。     

Chosen-ciphertext secure bidirectional proxy re-encryption schemes without pairings

Proxy re-encryption (PRE) is a useful primitive that allows a semi-trusted proxy to transform a ciphertext encrypted under one key into an encryption of the same plaintext under another key. A PRE scheme is bidirectional if the proxy is able to transform ciphertexts in both directions. In ACM CCS’07, Canetti and Hohenberger presented a bidirectional PRE scheme with chosen-ciphertext security, which captures the indistinguishability of ciphertexts even if the adversary has access to the standard decryption oracle as well as a re-encryption oracle and a re-encryption key oracle. They also left an important open problem to come up with a chosen-ciphertext secure PRE scheme without pairings. To resolve this problem, we propose a bidirectional PRE scheme without pairings, and prove its chosen-ciphertext security under the computational Diffie-Hellman assumption in the random oracle model. Based on this scheme, we further present a non-transitive bidirectional PRE scheme, in which the proxy alone cannot re-delegate the decryption rights.     

基于身份的签名方案

分析了现有的基于身份的签名方案,发现在这些方案中签名者都必须绝对信任可信中心机构(TA)。由于签名者用于签名的密钥是由TA生成的,TA可以伪造签名者的签名。基于此,引入多个TA,提出了一种新的基于身份的签名方案,并对该方案进行定性分析。在本方案中,如果能确保至少一个TA是诚实可信的,那么就可以确保本方案的安全性,使得本方案可以应用于公开环境中。     

Enhancements of authenticated multiple key exchange protocol based on bilinear pairings

Lee et al. [4] proposed two new authenticated multiple key exchange protocols based on Elliptic Curve Cryptography (ECC) and bilinear pairings. In this paper, we show an impersonation attack on their pairing-based authenticated key exchange protocol. We demonstrate that any attacker can impersonate an entity to share multiple session keys with another entity of his/her choice by using only the public key of the victim. Moreover, their protocol fails to provide perfect forward secrecy, despite of their claim to the contrary. Thus, we propose a simple modification to the original protocol which avoids our attack.     

基于身份的代理签名方案

通过对现有的基于身份的签名方案进行分析,发现在这些方案中签名者都必需绝对信任可信中心机构（TA）。由于签名者用于签名的密钥是由TA生成的,TA可以伪造任何签名者的签名。基于此,引入多个TA,解决了TA伪造攻击问题,提出了一种新的基于身份的代理签名方案,并对该方案进行了定性分析。在方案中,如果能确保至少一个TA是诚实可信的,那么就可以确保方案的安全性,使得方案可以应用于公开环境中。     

基于双线性对的无证书聚合签密方案

签密是一种能在一个逻辑步骤内同时提供消息的机密性和消息源认证性的密码原语。针对目前基于双线性对的无证书聚合签密(CLASC)方案效率较低的问题,提出了一种新的基于双线性对的无证书聚合签密方案。在该方案中,任何用户均可作为聚合者发起签密协议。用户生成签密密文后,密文被发送给聚合者进行聚合。安全性分析证明了该方案在随机预言模型下满足不可伪造性和保密性。对比结果表明所提方案仅要求每位签密者进行一次对运算,能够提高计算效率,有利于对实时性要求较高的应用。     

基于身份和Weil对的聚合签名方案

提出了一种基于身份和Weil对的聚合签名方案。方案中密钥生成中心负责系统公、私钥的生成,消息的分配和签名者公、私钥的生成。签名者是具有某种特殊身份的个体,并且这种身份是唯一的,这一身份是签名者从密钥生成中心获得签名私钥的唯一凭证。每个签名者只负责对某一段消息的签名,总的签名由签名聚合者结合每位签名者的单个签名生成。这样就避免了暴露整个消息给所有的签名者,这一特性在某些对消息保密要求性较高的场合得以广泛应用。该方案在签名时用到了双线性映射,从而减少了验证时的对运算。     

一个基于Weil配对的数字签名方案的安全性分析和改进

介绍了一个基于Weil配对的数字签名方案的一种攻击方法：生日攻击。并对原方案作了改进，改进后的方案能完全抵抗生日攻击。     

Solving a robust airline crew pairing problem with column generation

In this study, we solve a robust version of the airline crew pairing problem. Our concept of robustness was partially shaped during our discussions with small local airlines in Turkey which may have to add a set of extra flights into their schedule at short notice during operation. Thus, robustness in this case is related to the ability of accommodating these extra flights at the time of operation by disrupting the original plans as minimally as possible. We focus on the crew pairing aspect of robustness and prescribe that the planned crew pairings incorporate a number of predefined recovery solutions for each potential extra flight. These solutions are implemented only if necessary for recovery purposes and involve either inserting an extra flight into an existing pairing or partially swapping the flights in two existing pairings in order to cover an extra flight. The resulting mathematical programming model follows the conventional set covering formulation of the airline crew pairing problem typically solved by column generation with an additional complication. The model includes constraints that depend on the columns due to the robustness consideration and grows not only column-wise but also row-wise as new columns are generated. To solve this difficult model, we propose a row and column generation approach. This approach requires a set of modifications to the multi-label shortest path problem for pricing out new columns (pairings) and various mechanisms to handle the simultaneous increase in the number of rows and columns in the restricted master problem during column generation. We conduct computational experiments on a set of real instances compiled from local airlines in Turkey.     

An integer programming approach to generating airline crew pairings

The ability to generate crew pairings quickly is essential to solving the airline crew scheduling problem. Although techniques for doing so are well-established, they are also highly customized and require significant implementation efforts. This greatly impedes researchers studying important problems such as robust planning, integrated planning, and automated recovery, all of which also require the generating of crew pairings. As an alternative, we present an integer programming (IP) approach to generating crew pairings, which can be solved via traditional methods such as branch-and-bound using off-the-shelf commercial solvers. This greatly facilitates the prototyping and testing of new research ideas. In addition, we suggest that our modeling approach, which uses both connection variables and marker variables to capture the non-linear cost function and constraints of the crew scheduling problem, can be applicable in other scheduling contexts as well. Computational results using data from a major US hub-and-spoke carrier demonstrate the performance of our approach.