基于近似最大公因多项式问题的公钥密码方案

研究了有限域F2上有随机噪声的一组多项式的近似最大公因式问题,提出了基于近似最大公因多项式问题的公钥密码方案。证明了方案的正确性并归约证明了方案的安全性等价于求解近似最大公因式问题,同时讨论了对于该方案可能的攻击方式。通过与现有公钥系统比较,该方案的安全性和可靠性较高,运算速度较快。     

基于k-ary消减的快速最大公约数算法

最大公约数(GCD)算法中,对于输入B和C,利用Sorenson的右移k-ary消减思想提出一个算法用于寻找整数x和y,使得x和y满足Bx-Cy在二进制表示下低比特位部分为0,即Bx-Cy=0(mod 2^e),其中e是常数正整数。利用该算法能够右移较多比特并大规模降低循环次数。再结合模算法,提出了快速GCD算法,其输入规模为n比特时最差复杂度仍然是O(n²),但最好的情况下复杂度能达到O(nlog²n log logn)。实验数据表明,对于20万以上比特规模的输入,快速GCD算法比Binary GCD算法速度快;对100万比特规模的输入,快速GCD算法速度是Binary GCD算法的两倍。     

求多个数的最大公约数的算法设计

在求两个数的最大公约数算法的基础上,研究了求多个数的最大公约数的算法,并利用C语言实现了枚举法、辗转相除法和更相减损术三种算法的程序设计。     

A note on the Wolovich method of extraction of a greatest common divisor of two polynomial matrices

In this note, a modification of the Wolovich method of extraction of a greatest common divisor of two noncoprime polynomial matrices is proposed, which demands less computational operations and requires dealing with matrices of lower dimensions. The modified method allows us to establish the whole class of greatest common divisors of the given pair of polynomial matrices.     

Authenticated semi-quantum key distribution protocol using Bell states

This study presents the first authenticated semi-quantum key distribution (ASQKD) protocols without using authenticated classical channels. By pre-sharing a master secret key between two communicants, a sender with advanced quantum devices can transmit a working key to a receiver, who can merely perform classical operations. The idea of ASQKD enables establishment of a key hierarchy in security systems that also eases the key management problem. The proposed protocols are free from several well-known attacks     

Cancellations in multivariable continuous-time and discrete-time feedback systems treated by greatest common divisor extraction

This correspondence considers a multivariable system with proper rational matrix transfer functions G0and Gfin the forward and feedback branches, respectively. It develops a strictly algebraic procedure to obtain polynomials whose zeros are the poles of the matrix transfer functions from input to output (Hy), and from input to error (He). G0and Gfare given in the polynomial matrix factored formN_{0}D_{0}^{-1}andD_{f}^{-1}N_{f}. The role of the assumption det [I + G_{f}(infty)G_{0}(infty)] neq 0and the relation between the zeros of det [I + G_{f}G_{0}] and the poles of Hyand Heare indicated. The implications for stability analysis of continuous-time as well as discrete-time systems are stressed.     

Approximate greatest common divisor of many polynomials, generalised resultants, and strength of approximation

The computation of the greatest common divisor (GCD) of many polynomials is a nongeneric problem. Techniques defining “approximate GCD” solutions have been defined, but the proper definition of the “approximate” GCD, and the way we can measure the strength of the approximation has remained open. This paper uses recent results on the representation of the GCD of many polynomials, in terms of factorisation of generalised resultants, to define the notion of “approximate GCD” and define the strength of any given approximation by solving an optimisation problem. The newly established framework is used to evaluate the performance of alternative procedures which have been used for defining approximate GCDs.     

Minors of Bezout matrices,subresultants and the parameterization of the degree of the polynomial greatest common divisor

The main purpose of this article is to present algorithms to parameterize the degree of the greatest common divisor of two polynomials with parametric coefficients: these algorithms are based on the fact that the principal minors of the Bezout matrices provide the principal subresultant sequence. When coefficients depend on parameters, these algorithms show a better behaviour than the classical ones.     

Matrix pencil methodologies for computing the greatest common divisor of polynomials: hybrid algorithms and their performance

The computation of the greatest common divisor (GCD) of several polynomials is a problem that emerges in many fields of applications. The GCD computation has a non-generic nature and thus its numerical computation is a hard problem. In this paper we examine the family of matrix pencil methods for GCD computation and investigate their performance as far as their complexity, error analysis and their effectiveness for evaluating approximate solutions. The relative merits of the various variants of such methods are examined for the different cases of sets of polynomials with varying number of elements and degree. The developed algorithms combine symbolical and numerical programming and this is what we define here as hybrid computations. The combination of numerical operations with symbolical programming can improve the nature of the methods and guarantees the stability of the algorithm. Furthermore, it emphasizes the significance of hybrid computations in complex problems such as the computation of GCD. All methods are tested thoroughly for several sets of polynomials and the results are presented in tables.     

Cryptanalysis on authenticated semi-quantum key distribution protocol using Bell states

Recently, Yu et al. (Quantum Inf Process 13(6):1457–1465, 2014) proposed the first semi-quantum scheme without the need of a classical channel to generate a secret key, while employing a “master key” and the entanglement properties of Bell states. This study points out a vulnerability that allows a malicious person to recover a partial master key and to launch a successful Man-In-The-Middle attack. Accordingly, we present the most likely leakage information scenarios where an outside attacker affects the security of the proposed protocol.     

Two methods for the calculation of the degree of an approximate greatest common divisor of two inexact polynomials

The calculation of the degree d of an approximate greatest common divisor of two inexact polynomials f(y) and g(y) reduces to the determination of the rank loss of a resultant matrix, the entries of which are functions of the coefficients of f(y) and g(y). This paper considers this issue by describing two methods to calculate d, such that knowledge of the noise level imposed on the coefficients of f(y) and g(y) is not assumed. One method uses the residual of a linear algebraic equation whose coefficient matrix and right hand side vector are derived from the Sylvester resultant matrix S(f,g), and the other method uses the first principal angle between a line and a hyperplane, the equations of which are calculated from S(f,g). Computational results on inexact polynomials whose exact forms have multiple roots of high degree are shown and very good results are obtained. These results are compared with the rank loss of S(f,g) for the calculation of d, and it is shown that this method yields incorrect results for these examples.     

具有双向身份认证功能的量子密钥分发协议

提出了一种具有身份认证功能的量子密钥分发协议。该协议利用Bell态纠缠交换特性、Bell基测量和按位异或运算,可以高效完成通信双方的身份认证;身份认证完成后,通信双方对手中粒子进行Pauli操作,能得到与对方拥有一样的Bell态粒子;通信双方按照约定的编码规则,得到相同二进制字符串作为密钥。分析表明,提出的密钥分发协议过程简单、操作容易实现,协议的安全性也能得到保证。     

面向边缘计算的隐私保护密钥分配协议

针对边缘计算多应用场景下的隐私保护问题,提出两种基于策略的密钥分配协议,所提出的协议基于约束伪随机函数的概念分别实现了轻量高效和灵活细粒度的策略选择.具体来说,基于GGM伪随机数生成器,构建前缀谓词策略的密钥分配协议,该协议可有效支持轻量高效的密钥分配,适用于单一网络环境下设备资源受限的应用场景.在此基础上,基于多线性...     

Security of a single-state semi-quantum key distribution protocol

Semi-quantum key distribution protocols are allowed to set up a secure secret key between two users. Compared with their full quantum counterparts, one of the two users is restricted to perform some “classical” or “semi-quantum” operations, which potentially makes them easily realizable by using less quantum resource. However, the semi-quantum key distribution protocols mainly rely on a two-way quantum channel. The eavesdropper has two opportunities to intercept the quantum states transmitted in the quantum communication stage. It may allow the eavesdropper to get more information and make the security analysis more complicated. In the past ten years, many semi-quantum key distribution protocols have been proposed and proved to be robust. However, there are few works concerning their unconditional security. It is doubted that how secure the semi-quantum ones are and how much noise they can tolerate to establish a secure secret key. In this paper, we prove the unconditional security of a single-state semi-quantum key distribution protocol proposed by Zou et al. (Phys Rev A 79:052312, 2009). We present a complete proof from information theory aspect by deriving a lower bound of the protocol’s key rate in the asymptotic scenario. Using this bound, we figure out an error threshold value such that for all error rates that are less than this threshold value, the secure secret key can be established between the legitimate users definitely. Otherwise, the users should abort the protocol. We make an illustration of the protocol under the circumstance that the reverse quantum channel is a depolarizing one with parameter q. Additionally, we compare the error threshold value with some full quantum protocols and several existing semi-quantum ones whose unconditional security proofs have been provided recently.     

Recursive protocol for group-oriented authentication with key distribution

The authors propose a recursive protocol for group-oriented authentication with key exchange, in which a group of n entities can authenticate with each other and share a group session key. The proposed protocol has the following characteristics: First, it requires O(n) rounds of messages, O(log n) completion time, O(log n) waiting time, and O(n log n) communication overhead in average for the completion of the recursion. Second, it not only meets the five principles suggested by Diffie et al. [Diffie, W., van Oorschot, P.C., Wiener, M.J., 1992. Authentication and authenticated key exchange. Designs, Codes, and Cryptography 2 (2), 107-125] on the design of a secure key exchange protocol, but also achieves the properties of nondisclosure, independency, and integrity addressed by Janson and Tsudik [Janson, P., Tsudik, G., 1995. Secure and minimal protocols for authenticated key distribution. Computer Communications 18 (9), 645-653] for the authentication of the group session key. Third, we describe the beliefs of trustworthy entities involved in our authentication protocol and the evolution of these beliefs as a consequence of communication by using BAN logic. Finally, it is practical and efficient, because only one-way hash function and exclusive-or (XOR) operations are used in implementation.     

An novel three-party authenticated key exchange protocol using one-time key

Three-party authenticated key exchange protocol (3PAKE) is an important cryptographic technique for secure communication which allows two parties to agree a new secure session key with the help of a trusted server. In this paper, we propose a new three-party authenticated key exchange protocol which aims to achieve more efficiency with the same security level of other existing 3PAKE protocols. Security analysis and formal verification using AVISPA tools show that the proposed protocol is secure against various known attacks. Comparing with other typical 3PAKE protocols, the proposed protocol is more efficient with less computation complexity.     

A practical protocol for three-party authenticated quantum key distribution

Recently, Hwang et al. proposed two three-party authenticated quantum key distribution protocols for two communicating parties to establish a session key via a trusted center. They also showed their protocols were secure by using random oracle model. However, their protocols were designed to run in an ideal world. In this paper, we present a more practical protocol by considering some issues, which have not been addressed in their protocols. These issues include (1) session key consistence, (2) online guessing attack, and (3) noise in quantum channels. To deal with these issues, we use error correction code and key evolution. We also give a formal proof for the security of our protocols by using standard reduction, instead of the random oracle model.     

基于BB84的多用户量子密钥分发协议

BB84协议是目前最接近实用化的量子密钥分发(QKD)协议。点对点的量子密钥分发系统已经可以商用,但现有的多用户量子密钥分发协议都是采用量子纠缠、量子存储等技术手段进行密钥分发,在现有的技术条件下只能停留在理论阶段,离工程应用还有较长的距离。该文提出了一种基于BB84的多用户量子密钥分发协议,将计算机通信技术应用到量子保密通信中,实现一对多的量子通信网络的量子密钥分发,并从理论和实验结果两方面分析其可行性。     

基于高维纠缠态的量子密钥分发协议

为了提高量子密钥分发的效率和安全性,利用高维Hilbert空间中的Bell态和Hadamard门设计了一种量子密钥分发协议。首先通过量子态的动态演变验证了三维Bell纠缠态在Z基和X基下具有不同的表示特性,然后以此为基础进行协议设计,其中利用Z基测量来检测窃听,利用X基测量来产生密钥。安全性分析表明,该协议可以抵抗截获重发、纠缠附加粒子和特洛伊木马三种常见的攻击。最后将协议与其他方案进行了比较,该协议在保证量子比特效率50%的基础上,安全性也有所提升。