New circular quantum secret sharing for remote agents

This study presents a novel circular quantum secret sharing (QSS) protocol based on the controlled-NOT (CNOT) gate for remote agents. A CNOT gate is able to entangle a Bell state and several single photons to form a multi-particle GHZ state. Using this technique, the proposed QSS scheme is designed in purpose to be congenitally free from the Trojan horse attacks. Moreover, for each shared bit among n party, the qubit efficiency has reached ${\frac{1}{2n+1}}$ , which is the best among the current circular QSS??s.     

Quantum secret sharing with continuous variable graph state

In this paper, we study several physically feasible quantum secret sharing (QSS) schemes using continuous variable graph state (CVGS). Their implementation protocols are given, and the estimation error formulae are derived. Then, we present a variety of results on the theory of QSS with CVGS. Any $(k,n)$ threshold protocol of the three specific schemes satisfying $\frac{n}{2}<k\le n$ , where $n$ denotes the total number of players and $k$ denotes the minimum number of players who can collaboratively access the secret, can be implemented by certain weighted CVGS. The quantum secret is absolutely confidential to any player group with number less than threshold. Besides, the effect of finite squeezing to these results is properly considered. In the end, the duality between two specific schemes is investigated.     

Secure multiparty quantum secret sharing with the collective eavesdropping-check character

Combining the block transmission in Long and Liu (Phys Rev A 65:032302, 2002) and the double operations in Lin et al. (Opt Commun 282:4455, 2009), we propose a secure multiparty quantum secret sharing protocol with the collective eavesdropping-check character. In this protocol, only the boss needs to prepare Bell states and perform Bell state measurements, and all agents only perform local operations, which makes this protocol more feasible with the current technique. Incidentally, we show that the other half of secret messages in Lin et al. protocol (Opt Commun 282:4455, 2009) may also be eavesdropped.     

Comment on “High-dimensional deterministic multiparty quantum secret sharing without unitary operations”

Recently, a high-dimensional deterministic multiparty quantum secret sharing (DMQSS) scheme was proposed (Liu ZH et al in Quantum Inf Process 1–11 2011). However, we show that the scheme is vulnerable to a specific kind of collusion attack. In the worst case, ${\left\lfloor n/2\right\rfloor+1}$ agents can collude elaborately to reveal the dealer’s secret without the help of the other agents. We present the attack strategy in details and also give two possible improvements to resist the proposed collision attack.     

Highly efficient remote preparation of an arbitrary three-qubit state via a four-qubit cluster state and an EPR state

An efficient protocol for remotely preparing an arbitrary three-qubit state is devised with a four-qubit cluster state and an Einstein–Podolsky–Rosen state as the shared quantum resource. Using an appropriate set of eight-qubit mutually orthogonal measurement basis, the remote three-qubit preparation is successfully completed with the probability of ${\frac{1}{8}}$ in general case. Then to achieve our concerns of improving the probability of this protocol, some special ensembles of three-qubit states are minutely investigated. As a result, it is shown that the total probability of the RSP protocol, in these particular cases, can be improved to ${\frac{1}{4}}$ and ${\frac{1}{2}}$ , respectively, or even that the RSP protocol can be realized with unit success probability.     

Dynamic quantum secret sharing

Based on the entanglement swapping of EPR pairs, a dynamic quantum secret sharing (QSS) scheme is proposed. The scheme has the following dynamic properties. Without modifying the secret shares of old agents, (1) an agent can join or leave the QSS; (2) two QSSs (m parties in the first QSS and n parties in the second QSS) can be integrated into an (m + n)-party QSS. Compared with the existing QSS schemes, the proposed dynamic QSS is more flexible in practical applications.     

Improvements on “multiparty quantum key agreement with single particles”

Recently, Liu et al. (Quantum Inf Process 12: 1797–1805, 2013) proposed a secure multiparty quantum key agreement (MQKA) protocol with single particles. Their protocol allows N parties to negotiate a secret session key in such away that (1) outside eavesdroppers cannot gain the session key without introducing any errors; (2) the session key cannot be determined by any non-trivial subset of the participants. However, the particle efficiency of their protocol is only $\frac{1}{(k+1)N(N-1)}$ . In this paper, we show that the efficiency of the MQKA protocol can be improved to $\frac{1}{N(k+1)}$ by introducing two additional unitary operations. Since, in some scenarios, the secret keys are confidential, neither party is willing to divulge any of the contents to the other. Therefore, in our protocol, no participant can learn anything more than its prescribed output, i.e., the secret keys of the participants can be kept secret during the protocol instead of being exposed to others, thus, the privacy of the protocol is also improved. Furthermore, we explicitly show the scheme is secure.     

Comment on “Dynamic quantum secret sharing”

Hsu et al. (Quantum Inf Process 12:331–344,2013) proposed a dynamic quantum secret sharing (DQSS) protocol using the entanglement swapping of Bell states for an agent to easily join (or leave) the system. In 2013, Wang and Li (Quantum Inf Process 12(5):1991–1997, 2013) proposed a collusion attack on Hsu et al.’s DQSS protocol. Nevertheless, this study points out a new security issue on Hsu et al.’s DQSS protocol regarding to the honesty of a revoked agent. Without considering this issue, the DQSS protocol could be failed to provide secret sharing function.     

Asynchronous Byzantine Agreement with optimal resilience

We present an efficient, optimally-resilient Asynchronous Byzantine Agreement (ABA) protocol involving $n = 3t+1$ parties over a completely asynchronous network, tolerating a computationally unbounded Byzantine adversary, capable of corrupting at most $t$ out of the $n$ parties. In comparison with the best known optimally-resilient ABA protocols of Canetti and Rabin (STOC 1993) and Abraham et al. (PODC 2008), our protocol is significantly more efficient in terms of the communication complexity. Our ABA protocol is built on a new statistical asynchronous verifiable secret sharing (AVSS) protocol with optimal resilience. Our AVSS protocol significantly improves the communication complexity of the only known statistical and optimally-resilient AVSS protocol of Canetti et al. Our AVSS protocol is further built on an asynchronous primitive called asynchronous weak commitment (AWC), while the AVSS of Canetti et al. is built on the primitive called asynchronous weak secret sharing (AWSS). We observe that AWC has weaker requirements than AWSS and hence it can be designed more efficiently than AWSS. The common coin primitive is one of the most important building blocks for the construction of an ABA protocol. In this paper, we extend the existing common coin protocol to make it compatible with our new AVSS protocol that shares multiple secrets simultaneously. As a byproduct, our new common coin protocol is more communication efficient than all the existing common coin protocols.     

Fault tolerance in distributed systems using fused state machines

Replication is a standard technique for fault tolerance in distributed systems modeled as deterministic finite state machines (DFSMs or machines). To correct \(f\) crash or \(\lfloor f/2 \rfloor \) Byzantine faults among \(n\) different machines, replication requires \(nf\) backup machines. We present a solution called fusion that requires just \(f\) backup machines. First, we build a framework for fault tolerance in DFSMs based on the notion of Hamming distances. We introduce the concept of an ( \(f\) , \(m\) )-fusion, which is a set of \(m\) backup machines that can correct \(f\) crash faults or \(\lfloor f/2 \rfloor \) Byzantine faults among a given set of machines. Second, we present an algorithm to generate an ( \(f\) , \(f\) )-fusion for a given set of machines. We ensure that our backups are efficient in terms of the size of their state and event sets. Third, we use locality sensitive hashing for the detection and correction of faults that incurs almost the same overhead as that for replication. We detect Byzantine faults with time complexity \(O(n f)\) on average while we correct crash and Byzantine faults with time complexity \(O(n \rho f)\) with high probability, where \(\rho \) is the average state reduction achieved by fusion. Finally, our evaluation of fusion on the widely used MCNC’91 benchmarks for DFSMs shows that the average state space savings in fusion (over replication) is 38 % (range 0–99 %). To demonstrate the practical use of fusion, we describe its potential application to two areas: sensor networks and the MapReduce framework. In the case of sensor networks a fusion-based solution can lead to significantly fewer sensor-nodes than a replication-based solution. For the MapReduce framework, fusion can reduce the number of map-tasks compared to replication. Hence, fusion results in considerable savings in state space and other resources such as the power needed to run the backups.     

Derandomized Parallel Repetition Theorems for Free Games

Raz’s parallel repetition theorem (SIAM J Comput 27(3):763–803, 1998) together with improvements of Holenstein (STOC, pp 411–419, 2007) shows that for any two-prover one-round game with value at most ${1- \epsilon}$ 1 - ? (for ${\epsilon \leq 1/2}$ ? ≤ 1 / 2 ), the value of the game repeated n times in parallel on independent inputs is at most ${(1- \epsilon)^{\Omega(\frac{\epsilon^2 n}{\ell})}}$ ( 1 - ? ) Ω ( ? 2 n ? ) , where ? is the answer length of the game. For free games (which are games in which the inputs to the two players are uniform and independent), the constant 2 can be replaced with 1 by a result of Barak et al. (APPROX-RANDOM, pp 352–365, 2009). Consequently, ${n=O(\frac{t \ell}{\epsilon})}$ n = O ( t ? ? ) repetitions suffice to reduce the value of a free game from ${1- \epsilon}$ 1 - ? to ${(1- \epsilon)^t}$ ( 1 - ? ) t , and denoting the input length of the game by m, it follows that ${nm=O(\frac{t \ell m}{\epsilon})}$ n m = O ( t ? m ? ) random bits can be used to prepare n independent inputs for the parallel repetition game. In this paper, we prove a derandomized version of the parallel repetition theorem for free games and show that O(t(m + ?)) random bits can be used to generate correlated inputs, such that the value of the parallel repetition game on these inputs has the same behavior. That is, it is possible to reduce the value from ${1- \epsilon}$ 1 - ? to ${(1- \epsilon)^t}$ ( 1 - ? ) t while only multiplying the randomness complexity by O(t) when m = O(?). Our technique uses strong extractors to “derandomize” a lemma of Raz and can be also used to derandomize a parallel repetition theorem of Parnafes et al. (STOC, pp 363–372, 1997) for communication games in the special case that the game is free.     

Cryptanalysis of a multi-party quantum key agreement protocol with single particles

Recently, Sun et al. (Quantum Inf Process 12:3411–3420, 2013) presented an efficient multi-party quantum key agreement (QKA) protocol by employing single particles and unitary operations. The aim of this protocol is to fairly and securely negotiate a secret session key among \(N\) parties with a high qubit efficiency. In addition, the authors claimed that no participant can learn anything more than his/her prescribed output in this protocol, i.e., the sub-secret keys of the participants can be kept secret during the protocol. However, here we point out that the sub-secret of a participant in Sun et al.’s protocol can be eavesdropped by the two participants next to him/her. Moreover, a certain number of dishonest participants can fully determine the final shared key in this protocol. Finally, we discuss the factors that should be considered when designing a really fair and secure QKA protocol.     

Fast flooding over Manhattan

We consider a Mobile Ad-hoc NETwork (MANET) formed by $n$ agents that move at speed $\text{ v}$ according to the Manhattan Random-Waypoint model over a square region of side length $L$ . This model has stationary properties that strongly depart from the well-studied Random-Walk model and that are typical in scenarios of vehicular traffic in urban zones. For instance, the resulting stationary (agent) spatial probability distribution is far to be uniform: the average density over the “central zone” is asymptotically higher than that over the “Suburb”. Agents exchange data if and only if they are at (Euclidean) distance at most $R$ within each other. We study the flooding time of this MANET: the number of time steps required to broadcast a message from one source agent to all agents of the network in the stationary phase. We prove the first asymptotical upper bound on the flooding time. This bound holds with high probability, it is a decreasing function of $R$ and $\text{ v}$ , and it is tight for a wide and relevant range of the network parameters (i.e. $L, R$ and $\text{ v}$ ). A consequence of our result is that flooding over the sparse and highly-disconnected Suburb can be as fast as flooding over the dense and connected central zone. This property holds even when $R$ is exponentially below the connectivity threshold of the MANET and the speed $\text{ v}$ is very low.     

On the security of AUTH, a provably secure authentication protocol based on the subspace LPN problem

At the 2011 Eurocrypt, Kiltz et al., in their best paper price awarded paper, proposed an ultra-lightweight authentication protocol, called $AUTH$ . While the new protocol is supported by a delicate security proof based on the conjectured hardness of the learning parity with noise problem, this security proof does not include man-in-the-middle attacks. In this paper, we show that $AUTH$ is weak against MIM adversaries by introducing a very efficient key recovery MIM attack that has only linear complexity with respect to the length of the secret key.     

Complexity of Rational and Irrational Nash Equilibria

We introduce two new natural decision problems, denoted as ? RATIONAL NASH and ? IRRATIONAL NASH, pertinent to the rationality and irrationality, respectively, of Nash equilibria for (finite) strategic games. These problems ask, given a strategic game, whether or not it admits (i) a rational Nash equilibrium where all probabilities are rational numbers, and (ii) an irrational Nash equilibrium where at least one probability is irrational, respectively. We are interested here in the complexities of ? RATIONAL NASH and ? IRRATIONAL NASH. Towards this end, we study two other decision problems, denoted as NASH-EQUIVALENCE and NASH-REDUCTION, pertinent to some mutual properties of the sets of Nash equilibria of two given strategic games with the same number of players. The problem NASH-EQUIVALENCE asks whether or not the two sets of Nash equilibria coincide; we identify a restriction of its complementary problem that witnesses ? RATIONAL NASH. The problem NASH-REDUCTION asks whether or not there is a so called Nash reduction: a suitable map between corresponding strategy sets of players that yields a Nash equilibrium of the former game from a Nash equilibrium of the latter game; we identify a restriction of NASH-REDUCTION that witnesses ? IRRATIONAL NASH. As our main result, we provide two distinct reductions to simultaneously show that (i) NASH-EQUIVALENCE is co- $\mathcal{NP}$ -hard and ? RATIONAL NASH is $\mathcal{NP}$ -hard, and (ii) NASH-REDUCTION and ? IRRATIONAL NASH are both $\mathcal{NP}$ -hard, respectively. The reductions significantly extend techniques previously employed by Conitzer and Sandholm (Proceedings of the 18th Joint Conference on Artificial Intelligence, pp. 765–771, 2003; Games Econ. Behav. 63(2), 621–641, 2008).     

Finding peculiar compositions of two frequent strings with background texts

We consider mining unusual patterns from a set  \(T\) of target texts. A typical method outputs unusual patterns if their observed frequencies are far from their expectation estimated under an assumed probabilistic model. However, it is difficult for the method to deal with the zero frequency and thus it suffers from data sparseness. We employ another set  \(B\) of background texts to define a composition  \(xy\) to be peculiar if both \(x\) and  \(y\) are more frequent in  \(B\) than in  \(T\) and conversely \(xy\) is more frequent in  \(T\) . \(xy\) is unusual because \(x\) and  \(y\) are infrequent in  \(T\) while \(xy\) is unexpectedly frequent compared to  \(xy\) in  \(B\) . To find frequent subpatterns and infrequent patterns simultaneously, we develop a fast algorithm using the suffix tree and show that it scales almost linearly under practical settings of parameters. Experiments using DNA sequences show that found peculiar compositions basically appear in rRNA while patterns found by an existing method seem not to relate to specific biological functions. We also show that discovered patterns have similar lengths at which the distribution of frequencies of fixed length substrings begins to skew. This fact explains why our method can find long peculiar compositions.     

Extending the alternating-offers protocol in the presence of competition: models and theoretical analysis

The automation of bargaining is receiving a lot of attention in artificial intelligence research. Indeed, considering that bargaining is the most common form of economic transaction, its automation could lead software agents to reach more effective agreements. In the present paper we focus on the best-known bargaining protocol, i.e., the alternating-offers protocol. It provides an elegant mechanism whereby a buyer and a seller can bilaterally bargain. Although this protocol and its refinements have been studied extensively, no work up to the present provides an adequate model for bargaining in electronic markets. A result of these settings means that multiple buyers are in competition with each other for the purchase of a good from the same seller while, analogously, multiple sellers are in competition with each other for the sale of a good to the same buyer. The study of these settings is of paramount importance, as they will be commonplace in real-world applications. In the present paper we provide a model that extends the alternating-offers protocol to include competition among agents.¹ Our game theoretical analysis shows that the proposed model is satisfactory: it effectively captures the competition among agents, equilibrium strategies are efficiently computable, and the equilibrium outcome is unique. The main results we achieve are the following. 1) With m buyers and n sellers and when the outside option (i.e., the possibility of leaving a negotiation to start a new one) is inhibited, we show that it can be reduced to a problem of matching and that can be addressed by using the Gale-Shapley’s stable marriage algorithm. The equilibrium outcome is unique and can be computed in $O(l \cdot m\cdot n \cdot \overline T + (m+n)^2)$ , where l is the number of the issues and $\overline{T}$ is the maximum length of the bargaining. 2) With m buyers and one seller and when the seller can exploit the outside option, we show that agents’ equilibrium strategies can be computed in $O(l \cdot m \cdot \overline{T})$ and may be not unique. However, we show that a simple refinement of the agents’ utility functions leads to equilibrium uniqueness.     

On space complexity of self-stabilizing leader election in mediated population protocol

Chatzigiannakis et al. (Lect Notes Comput Sci 5734:56–76, 2009) extended the Population Protocol (PP) of Angluin et al. (2004) and introduced the Mediated Population Protocol (MPP) by introducing an extra memory on every agent-to-agent communication link (i.e., edge), in order to model more powerful networks of mobile agents with limited resources. For a general distributed system of autonomous agents, Leader Election (LE) plays a key role in their efficient coordination. A Self-Stabilizing (SS) protocol has ideal properties required for distributed systems of huge numbers of not highly reliable agents typically modeled by PP or MPP; it does not require any initialization and tolerates a finite number of transient failures. Cai et al. (2009) showed that for a system of $n$ agents, any PP for SS-LE requires at least $n$ agent-states, and gave a PP with $n$ agent-states for SS-LE. In this paper, we show, for a system of $n$ agents, any MPP for SS-LE with 2 edge-states (i.e., 1 bit memory) on every edge requires at least $(1/2) \lg {n}$ agent-states, and give an MPP for SS-LE with $(2/3)n$ agent-states and 2 edge-states on every edge. Furthermore, we show that a constant number of edge-states on every edge do not help in designing an MPP for SS-LE with a constant number of agent-states, and that there is no MPP for SS-LE with 2 agent-states, regardless of the number of edge-states; the edge-state is not a complete alternative of the agent-state, although it can help in reducing the number of agent-states, when solving SS-LE.     

Using agent- and organisation-oriented programming to develop a team of agents for a competitive game

The multi-agent programming contest uses a cow-herding scenario where two teams of cooperative agents compete for resources against each other. We developed such a team of agents using two well-known platforms, one based on a logic-based agent-oriented programming language, called Jason, and the other based on an organisational model, called $\mathcal{M}$ oise. While there is significant research on both agent programming and agent organisations, this was one of the first applications of a combined approach where we can program deliberative agents and organise them using a sophisticated organisational model. In this paper, we describe and discuss our contribution to the multi-agent contest using this combination of agent and organisation programming.     

Characterization of quantum circulant networks having perfect state transfer

In this paper we answer the question of when circulant quantum spin networks with nearest-neighbor couplings can give perfect state transfer. The network is described by a circulant graph G, which is characterized by its circulant adjacency matrix A. Formally, we say that there exists a perfect state transfer (PST) between vertices ${a,b\in V(G)}$ if |F(τ) _ab | = 1, for some positive real number τ, where F(t) = exp(i At). Saxena et al. (Int J Quantum Inf 5:417–430, 2007) proved that |F(τ) _aa | = 1 for some ${a\in V(G)}$ and ${\tau\in \mathbb {R}^+}$ if and only if all eigenvalues of G are integer (that is, the graph is integral). The integral circulant graph ICG _n (D) has the vertex set Z _n = {0, 1, 2, . . . , n ? 1} and vertices a and b are adjacent if ${\gcd(a-b,n)\in D}$ , where ${D \subseteq \{d : d \mid n, \ 1 \leq d < n\}}$ . These graphs are highly symmetric and have important applications in chemical graph theory. We show that ICG _n (D) has PST if and only if ${n\in 4\mathbb {N}}$ and ${D=\widetilde{D_3} \cup D_2\cup 2D_2\cup 4D_2\cup \{n/2^a\}}$ , where ${\widetilde{D_3}=\{d\in D\ |\ n/d\in 8\mathbb {N}\}, D_2= \{d\in D\ |\ n/d\in 8\mathbb {N}+4\}{\setminus}\{n/4\}}$ and ${a\in\{1,2\}}$ . We have thus answered the question of complete characterization of perfect state transfer in integral circulant graphs raised in Angeles-Canul et al. (Quantum Inf Comput 10(3&4):0325–0342, 2010). Furthermore, we also calculate perfect quantum communication distance (distance between vertices where PST occurs) and describe the spectra of integral circulant graphs having PST. We conclude by giving a closed form expression calculating the number of integral circulant graphs of a given order having PST.