A no-summoning theorem in relativistic quantum theory

Alice gives Bob an unknown localized physical state at some point P. At some point Q in the causal future of P, Alice will ask Bob for the state back. Bob knows this, but does not know at which point Q until the request is made. Bob can satisfy Alice’s summons, with arbitrarily short delay, for a quantum state in Galilean space-time or a classical state in Minkowski space-time. However, given an unknown quantum state in Minkowski space-time, he cannot generally fulfil her summons. This no-summoning theorem is a fundamental feature of, and intrinsic to, relativistic quantum theory. It follows from the no-signalling principle and the no-cloning theorem, but not from either alone.     

Quantum secure two-party computation for set intersection with rational players

Recently, Shi et al. (Phys Rev A 92:022309, 2015) proposed quantum oblivious set member decision protocol where two legitimate parties, namely Alice and Bob, play a game. Alice has a secret k, and Bob has a set \(\{k_1,k_2,\ldots k_n\}\). The game is designed towards testing if the secret k is a member of the set possessed by Bob without revealing the identity of k. The output of the game will be either “Yes” (bit 1) or “No” (bit 0) and is generated at Bob’s place. Bob does not know the identity of k, and Alice does not know any element of the set. In a subsequent work (Shi et al in Quant Inf Process 15:363–371, 2016), the authors proposed a quantum scheme for private set intersection (PSI) where the client (Alice) gets the intersected elements with the help of a server (Bob) and the server knows nothing. In the present draft, we extended the game to compute the intersection of two computationally indistinguishable sets X and Y possessed by Alice and Bob, respectively. We consider Alice and Bob as rational players, i.e. they are neither “good” nor “bad”. They participate in the game towards maximizing their utilities. We prove that in this rational setting, the strategy profile ((cooperate, abort), (cooperate, abort)) is a strict Nash equilibrium. If ((cooperate, abort), (cooperate, abort)) is strict Nash, then fairness and correctness of the protocol are guaranteed.     

Hybrid authentication based on noisy channels

We consider a cryptographic scenario where some center broadcasts a random binary string to Alice, Bob and Eve over binary symmetric channels with bit error probabilities e _A, e _B and e _E respectively. Alice and Bob share no secret key initially, and their goal is to generate, after public discussion, a common information-theoretically secure key facing an active eavesdropper Eve. Under the condition e _AE and e _BE, code authentication (CA) can be used as part of a public discussion protocol to solve this problem. This authentication exploits parts of substrings received by Alice and Bob from the broadcasting center as authenticators to messages transmitted in a public discussion. Unfortunately, it happens to be ineffective because it produces a key of small length. We propose a hybrid authentication (HA) that combines both keyless code authentication and key authentication based on an almost strong universal class of hash functions. We prove a theorem that allows estimation of the performance evaluation of hybrid authentication. The selection algorithm for the main HA parameters, given security and reliability thresholds, is presented in detail.     

When is a monoid a group? the Church-Rosser case is tractable

The following question is shown to be tractable: given a finite monadic Church-Rosser Thue system T and a finite set A, is the submonoid generated by A (of the monoid presented by T) a group?     

A note on a special one-rule semi-Thue system

We show that the special semi-Thue system S₁ = {(abba, λ)} has no equivalent finite semi-Thue system which is uniquely terminating, i.e. canonical. This gives another example of a Thue system with a decidable word problem, but solving it using a canonical string rewriting system is possible only by introducing new additional symbols. In contrast to the example obtained recently by Kapur and Narendran (1984) this system presents a monoid which is in fact a group.     

Proxy re-encryption with keyword search

We introduce a new cryptographic primitive, called proxy re-encryption with keyword search, which is motivated by the following scenario in email systems: Charlie sends an encrypted email, which contains some keywords, such as “urgent”, to Alice under Alice’s public key, and Alice delegates her decryption rights to Bob via her mail server. The desired situations are: (1) Bob can decrypt mails delegated from Alice by using only his private key, (2) Bob’s mail gateway, with a trapdoor from Bob, can test whether the email delegated from Alice contains some keywords, such as “urgent”, (3) Alice and Bob do not wish to give the mail server or mail gateway the access to the content of emails.The function of proxy re-encryption with keyword search (PRES) is the combination of proxy re-encryption (PRE) and public key encryption with keyword search (PEKS). However, a PRES scheme cannot be obtained by directly combining those two schemes, since the resulting scheme is no longer proven secure in our security model. In this paper, a concrete construction is proposed, which is proven secure in the random oracle model, based on the modified Decisional Bilinear Diffie-Hellman assumption.     

Eine Anwendung des Brouwerschen Fixpunktsatzes in der Intervallarithmetik der Matrizen

A theorem is proved by means of Brouwer's theorem which allows to decide whether a given interval matrix [S] has the inclusion property relative to the unknown inverseA ^?1 of a known matrixA. It is demonstrated in which cases the theorem may be used and how to choose [S] in these cases.     

Nest sets and relativized closure properties

A nest set is the language generated by a context-free grammar whose rules are $\text{A → aB}\text{a}\text{?}\text{C}$ or A → ? (where a, ā are paired terminal symbols, and A, B, C are nonterminal symbols). They can be seen as the one-dimensional expressions of the recognizable sets of binary trees. We study their closure properties under relativized operations with respect to the Dyck set, which is the maximum set in the class. The operations considered are relativized versions of AFL operations, quotient, direct product, shuffle product, and some others. As an application we prove various closure properties of generalized parenthesis languages.     

Undecidable questions related to Church-Rosser Thue systems

The following four properties are shown undecidable for finite Thue systems S: Is S equivalent to a finite Church-Rosser (respectively: almost confluent, preperfect) system? Does S generate a Church-Rosser congruence?     

Cyclic quantum teleportation

We propose a scheme of cyclic quantum teleportation for three unknown qubits using six-qubit maximally entangled state as the quantum channel. Suppose there are three observers Alice, Bob and Charlie, each of them has been given a quantum system such as a photon or spin-\(\frac{1}{2}\) particle, prepared in state unknown to them. We show how to implement the cyclic quantum teleportation where Alice can transfer her single-qubit state of qubit a to Bob, Bob can transfer his single-qubit state of qubit b to Charlie and Charlie can also transfer his single-qubit state of qubit c to Alice. We can also implement the cyclic quantum teleportation with \(N\geqslant 3\) observers by constructing a 2N-qubit maximally entangled state as the quantum channel. By changing the quantum channel, we can change the direction of teleportation. Therefore, our scheme can realize teleportation in quantum information networks with N observers in different directions, and the security of our scheme is also investigated at the end of the paper.     

On extending de Bruijn sequences

We give a complete proof of the following theorem:Every de Bruijn sequence of order n in at least three symbols can be extended to a de Bruijn sequence of order n+1. Every de Bruijn sequence of order n in two symbols can not be extended to order n+1, but it can be extended to order n+2.     

Choosing,Agreeing, and Eliminating in Communication Complexity

We consider several questions inspired by the direct-sum problem in (two-party) communication complexity. In all questions, there are k fixed Boolean functions f ₁,…,f _k and each of Alice and Bob has k inputs, x ₁,…,x _k and y ₁,…,y _k , respectively. In the eliminate problem, Alice and Bob should output a vector σ₁,…,σ _k such that f _i (x _i , y _i ) ≠ σ _i for at least one i (i.e., their goal is to eliminate one of the 2 ^k output vectors); in the choose problem, Alice and Bob should return (i, f _i (x _i , y _i )), for some i (i.e., they choose one instance to solve), and in the agree problem they should return f _i (x _i , y _i ), for some i (i.e., if all the k Boolean values agree then this must be the output). The question, in each of the three cases, is whether one can do better than solving one (say, the first) instance. We study these three problems and prove various positive and negative results. In particular, we prove that the randomized communication complexity of eliminate, of k instances of the same function f, is characterized by the randomized communication complexity of solving one instance of f.     

On some generalizations of the Thue–Morse morphism

In 1912, the Norwegian mathematician Axel Thue was the first to describe an overlap-free binary infinite word. This word was generated by a morphism which is called, since the works of Morse, the Thue–Morse morphism. Here, we present two generalizations of the Thue–Morse morphism in the case of alphabets with more than two letters. The extension of the characteristic properties of the word of Thue to the words generated by these morphisms is considered. One of these generalizations corresponds to the construction of Prouhet and a link with the Arshon words is given. In particular, we prove that if n is an even number then the n-letter Arshon word is generated by morphism.     

A convergence theorem for the fuzzy subspace clustering (FSC) algorithm

We establish the convergence of the fuzzy subspace clustering (FSC) algorithm by applying Zangwill's convergence theorem. We show that the iteration sequence produced by the FSC algorithm terminates at a point in the solution set S or there is a subsequence converging to a point in S. In addition, we present experimental results that illustrate the convergence properties of the FSC algorithm in various scenarios.     

Elimination of single productions and merging nonterminal symbols of LR(1) grammars

Aho and Ullman give an algorithm in [1] for eliminating reductions of the form A → B, where A and B are nonterminals, from a set of LR(k) parsing tables, thus increasing the speed of the parser and reducing its size. We present a modification of their algorithm and show that after reductions by A → B have been eliminated, the symbols A and B can be equated and the associated columns of the parsing table merged, further reducing the size of the parser. The new set of tables parses according to an “abridged” grammar with fewer nonterminal symbols than the original. Finally, we give an algorithm which for certain LR(1) grammars constructs a set of LR(1) tables with no reductions by single productions, directly from the grammar.     

On lower bounds for the complexity of polynomials and their multiples

We prove a theorem giving arbitrarily long explicit sequences of algebraic numbers such that any nonzero polynomial f(X) satisfying has nonscalar complexity for some positive constant C independent of s. A similar result is shown for rapidly growing rational sequences. Received: April 6 1999.     

Cyclic joint remote state preparation in noisy environment

We propose a scheme of cyclic joint remote state preparation for three sides, which takes advantage of three GHZ states to compose product state as quantum channel. Suppose there are six legitimate participants, says Alice, Bob, Charlie, David, Emma and Fred in the scheme. It can be shown that Alice and David can remotely prepare a single-qubit state on Bob’s side; meanwhile, Bob and Emma can remotely prepare a desired quantum state on Charlie’s side, and Charlie and Fred can also remotely prepare a single-qubit state on Alice’s side at the same time. Further, it can be achieved in the opposite direction of the cycle by changing the quantum channel. Based on it, we generalize this protocol to \(N (N\ge 3)\) sides utilizing three multi-qubit GHZ-type states as quantum channel. Therefore, the scheme can achieve cyclic joint remote state preparation, which remotely prepares N states in quantum network with N-party, simultaneously. In addition, we consider that the effect of amplitude-damping noise of the initial states is prepared in four different laboratory. Clearly, we use fidelity to describe how much information has been lost in the cyclic process. Our investigation about the effect of noise shows that the preparing of the initial state in different laboratories will affect the loss of information.     

On reduced thue systems

The following problem is shown to be undecidable: Given a reduced finite Thue systemS over an alphabet Σ with |Σ| = 2, isS equivalent to a finite Church-Rosser system?     

Synchronized E0L forms

We turn once more to the study of E0L forms by focussing on synchronized E0L forms. We show that there are complete propagating synchro-E0L forms in contrast to the situation for E0L forms. Turning to the syntax analysis of synchro-E0L form families, we are lead into the study of ambiguity in E0L systems. We show that there are languages which are n-CF-ambiguous, for arbitrarily large values of n ? 1, but which are E0L-unambiguous. Finally we characterize when synchro-{S, a}-forms are complete and also characterize when short synchro-{S, A, a}-forms are complete, where A is a terminal-like nonterminal. These results are also in contrast with E0L forms, where even short {S, a}-forms have only a restricted characterization with respect to completeness.     

Asymmetric quantum dialogue in noisy environment

A notion of asymmetric quantum dialogue (AQD) is introduced. Conventional protocols of quantum dialogue are essentially symmetric as the users (Alice and Bob) can encode the same amount of classical information. In contrast, the proposed scheme for AQD provides different amount of communication powers to Alice and Bob. The proposed scheme offers an architecture, where the entangled state to be used and the encoding scheme to be shared between Alice and Bob depend on the amount of classical information they want to exchange with each other. The general structure for the AQD scheme has been obtained using a group theoretic structure of the operators introduced in Shukla et al. (Phys Lett A 377:518, 2013). The effect of different types of noises (e.g., amplitude damping and phase damping noise) on the proposed scheme is investigated, and it is shown that the proposed scheme for AQD is robust and it uses an optimized amount of quantum resources.