Existence of 3-round zero-knowledge proof systems for NP

This paper considers the existence of 3-round zero-knowledge proof systems for NP. Whether there exist 3-round non-black-box zero-knowledge proof systems for NP language is an open problem. By introducing a new interactive proof model, we construct a 3-round zero-knowledge proof system for graph 3-coloring under standard assumptions. Our protocol is a non-black-box zero-knowledge proof because we adopt a special strategy to prove the zero-knowledge property. Consequently, our construction shows the existence of 3-round non-black-box zero-knowledge proof for all languages in NP under the DDH assumption.     

Memorizable interactive proof and zero-knowledge proof systems

Interactive proof and zero-knowledge proof systems are two important concepts in cryptography and complexity theory. In the past two decades, a great number of interactive proof and zero-knowledge proof protocols have been designed and applied in practice. In this paper, a simple memorizable zero-knowledge protocol is proposed for graph non-isomorphism problem, based on the memorizable interactive proof system,which is extended from the original definition of interactive proof and is more applicable in reality.     

Broadcast protocols for distributed systems

An innovative approach is presented to the design of fault-tolerant distributed systems that avoids the several rounds of message exchange required by current protocols for consensus agreement. The approach is based on broadcast communication over a local area network, such as an Ethernet or a token ring, and on two novel protocols, the Trans protocol, which provides efficient reliable broadcast communication, and the Total protocol, which with high probability promptly places a total order on messages and achieves distributed agreement even in the presence of fail-stop, omission, timing, and communication faults. Reliable distributed operations, such as locking, update, and commitment, typically require only a single broadcast message rather than the several tens of messages required by current algorithms     

Mutual authentication protocols for RFID systems

With the availability of low-cost radio frequency identification (RFID) tags, security becomes an increasing concern.However, such tags do not permit complex eryptographic functions due to their computational, communications, and storage limitations.In this paper, we investigate the security issues and requirements of RFID systems, and propose ultra-light weight and light weight protocols for low-cost RFID tags. The proposed protocols has been applied to a supply chain management system.     

Commit protocols for externalized-commit heterogeneous database systems

In designing a heterogeneous database systems, one of the main technical challenges is developing techniques for ensuring global commit. That is, guaranteeing that a transaction spanning multiple individual database management systems (DBMSs) either commits at all the participating DBMSs or at none of them. Previous work in this area typically assumes that the participating DBMSs do not provide a mechanism for interacting with their commit facilities. While this is true in many cases, in practice there are systems which support a programmatic interface to their commit protocols. We refer to database systems offering such facilities asexternalized commit DBMSs.The focus of this paper is on commit protocols for these systems. We propose two new commit protocols for externalized commit DBMSs. The first may be used to obtain global commit in heterogeneous database systems composed of DBMSs with different 2-phase commit protocols (e.g., centralized and linear). The second protocol is more general, and ensures global commit even if the participating DBMSs employ 3-phase commit protocols. The more general protocol also preserves database autonomy, since it does not block a DBMS upon failure of another system. We describe both protocols in detail and prove their correctness. Recommended by: M. RusinkiewiczThis work was partially supported by an IBM Research Initiation Grant.     

Finite-time consensus protocols for multi-dimensional multi-agent systems

A finite-time consensus protocol is proposed for multi-dimensional multi-agent systems, using direction-preserving signum controls. Filippov solutions and nonsmooth analysis techniques are adopted to handle discontinuities. Sufficient and necessary conditions are provided to guarantee infinite-time convergence and boundedness of the solutions. It turns out that the number of agents which have continuous control law plays an essential role in finite-time convergence. In addition, it is shown that the unit balls introduced by ?p norms, where p∈[1,∞], are invariant for the closed loop.     

Termination detection protocols for mobile distributed systems

This paper studies a fundamental problem, the termination detection problem, in distributed systems. Under a wireless network environment, we show how to handle the host mobility and disconnection problems. In particular, when some distributed processes are temporarily disconnected, we show how to capture a weakly terminated state where silence has been reached only by those currently connected processes. A user may desire to know such a state to tell whether the mobile distributed system is still running or is silent because some processes are disconnected. Our protocol tries to exploit the network hierarchy by combining two existing protocols together. It employs the weight-throwing scheme on the wired network side, and the diffusion-based scheme on each wireless cell. Such a hybrid protocol can better pave the gaps of computation and communication capability between static and mobile hosts, thus more scalable to larger distributed systems. Analysis and simulation results are also presented     

On consensus protocols for high-order multiagent systems

In this paper, the static consensus problem and the dynamic consensus problem are considered for a class of high-order multiagent systems. With the proposed consensus protocols, necessary and sufficient conditions for the consensus problems are obtained. For the static consensus protocol, the desired consensus speed can be achieved by adjusting feedback gains. Simulations show the effectiveness of the proposed consensus protocols.     

Quantum dialogue protocols immune to collective noise

This work proposes two quantum dialogue protocols, each of which is robust against one of the following two kinds of collective noise: collective-dephasing noise and collective-rotation noise. Both quantum dialogue protocols are constructed from four-qubit DF states that consist of two Bell states. The receiver simply performs two Bell state measurements to obtain the secret message. Moreover, the proposed protocols are free from information leakage because some shared private quantum states are established in the new protocols to allow the legitimate users to exchange their secret messages securely.     

NP问题的最优轮复杂性知识的零知识证明

NP问题已有的知识的(黑箱)零知识证明都是非常数轮的,因此,在标准的复杂性假设下,NP问题是否存在常数轮的(黑箱)知识的零知识证明是一个有意义的问题.本文对该问题进行了研究,在一定的假设下给出了HC问题的两个常数轮知识的零知识证明系统.根据Katz最近的研究结果,在多项式分层不坍塌的条件下,本文基于claw-free陷门置换给出的HC问题的5轮知识的零知识证明系统具有最优的轮复杂性.     

Round-optimal zero-knowledge proofs of knowledge for NP

It is well known that all the known black-box zero-knowledge proofs of knowledge for NP are nonconstant-round.Whether there exit constant-round black-box zero-knowledge proofs of knowledge for all NP languages under certain standard assumptions is an open problem.This paper focuses on the problem and gives a positive answer by presenting two constructions of constant-round(black-box) zero-knowledge proofs of knowledge for the HC(hamiltonian cycle) problem.By the recent result of Katz,our second construction which relies on the existence of claw-free functions has optimal round complexity(5-round) assuming the polynomial hierarchy does not collapse.     

具有随机协议网络化系统的H_∞滤波

本文研究了一类具有随机介质访问协议网络化系统的H∞滤波问题.将传感器和滤波器的通信过程描述为一个马尔可夫链,进而将滤波误差系统建模成一个马尔可夫跳变系统.然后,运用李雅普诺夫方法和线性矩阵不等式技术,给出了滤波误差系统随机稳定且具有给定H∞性能的一个充分条件,并基于该条件给出了H∞滤波器的设计方法.最后的数值算例验证了本文方法的有效性.     

Secure and private search protocols for RFID systems

In many real world applications, there is a need to search for RFID tagged items. In this paper, we propose a set of protocols for secure and private search for tags based on their identities or certain criteria they must satisfy. When RFID enabled systems become pervasive in our life, tag search becomes crucial. Surprisingly, the problem of RFID search has not been widely addressed in the literature. We analyzed the privacy and security features of the proposed tag search protocols, and concluded that our protocols provide tag identity privacy, tag source location privacy, and tag-reader communication privacy. For the first time, we propose a formal method to securely search RFID tags which satisfy certain search criteria.     

免疫集体噪声的量子密钥协商协议

针对目前免疫集体噪声的量子密钥协商协议的量子比特效率偏低问题,基于逻辑Bell态提出了两个新的量子密钥协商协议,它们分别免疫集体退相位噪声和集体旋转噪声。两个协议利用幺正变换和延迟测量技术,确保了协议双方能公平地建立一个共享密钥。安全性分析证明了这两个协议能抵抗参与者攻击和相关外部攻击。与已有免疫集体噪声的量子密钥协商协议比较,发现新协议有较高的量子比特效率。     

Quantum correlations for bipartite continuous-variable systems

Two quantum correlations Q and \(Q_\mathcal P\) for \((m+n)\)-mode continuous-variable systems are introduced in terms of average distance between the reduced states under the local Gaussian positive operator-valued measurements, and analytical formulas of these quantum correlations for bipartite Gaussian states are provided. It is shown that the product states do not contain these quantum correlations, and conversely, all \((m+n)\)-mode Gaussian states with zero quantum correlations are product states. Generally, \(Q\ge Q_{\mathcal P}\), but for the symmetric two-mode squeezed thermal states, these quantum correlations are the same and a computable formula is given. In addition, Q is compared with Gaussian geometric discord for symmetric squeezed thermal states.     

Distributed systems and their protocols

Several models have been developed to assist with the design and understanding of distributed systems. The client-server model is used here to develop a set of requirements to be met by protocol sets used within a distributed system. An architecture within which protocols may be implemented to meet the requirements developed is proposed. A number of key requirements are reviewed and areas requiring further development identified.     

Finite-time consensus for multi-agent systems via nonlinear control protocols

This paper investigates the fnite-time consensus problem of multi-agent systems with single and double integrator dynamics,respectively.Some novel nonlinear protocols are constructed for frst-order and second-order leader-follower multi-agent systems,respectively.Based on the fnite-time control technique,the graph theory and Lyapunov direct method,some theoretical results are proposed to ensure that the states of all the follower agents can converge to its leader agent s state in fnite time.Finally,some simulation results are presented to illustrate the efectiveness of our theoretical results.