Catálogo de publicaciones - libros

We consider the following problem in a stream model: Given a sequence wich each  ∈ [] = {1,...,} and  > , find a in the sequence, i.e., find some  =  =  with  ≠  by using limited bits of memory and passes over the input sequence. In one an algorithm reads the input sequence in the order , , ..., . Since  > , a duplicate exists by the pigeonhole principle. Muthukrishnan [Mu05a], [Mu05b] has posed the following question for the case where  =  + 1: For  = (log), is there a solution with a number of passes? We have described the problem generalizing Muthukrishnan’s question by taking the sequence length  as a parameter. We give a negative answer to the original question by showing the following: Assume that  =  + 1. A streaming algorithm with (log) space requires (log/loglog) passes; a -pass streaming algorithm requires () space. We also consider the following problem of : Assuming that  < , find  ∈ [] such that  ≠  for 1 ≤  ≤ . The same lower bound applies for the missing-item finding problem. The proof is a simple reduction to the communication complexity of a . We also consider -pass algorithms and exactly determine the minimum space required. Interesting open questions such as the following remain. For the number of passes of algorithms using (log) space, show an (1) lower bound (or an (1) upper bound) for: (1) duplicate finding for  = 2, (2) missing-item finding for  = 2, and (3) the case where we allow Las-Vegas type randomization for  =  + 1.

In this paper, we introduce and study two new search models on digraphs: the directed searching and mixed directed searching. In these two search models, both searchers and intruders must follow the edge directions when they move along edges. We prove the monotonicity of both search models, and we show that both directed and mixed directed search problems are NP-complete.

Standard identity-based cryptosystems typically rely on the assumption that secret keys are kept perfectly secure. However, in practice, there are two threats to the key security in identity-based cryptosystems. One inherent problem is key escrow, that is, the Key Generation Center (KGC) always knows a user’s secret key and the malicious KGC can impersonate the user. Meanwhile, another threat is that a user’s secret key may be exposed to an adversary in an insecure device, and key exposure typically means that security is entirely lost. At present, there is no solution that can simultaneously solve both of above problems. In this paper, we first present a secure key issuing and updating model for identity-based cryptosystems. Our suggestion is an intermediate between the identity-based key insulation and distributing authorities approach, and can simultaneously solve both key escrow and key exposure problems. We formalize the definition and security notion of the corresponding encryption scheme (IBKUE) and signature scheme (IBKUS), and then propose an IBKUE scheme based on Boneh-Franklin’s scheme [2] and an IBKUS scheme based on Cha-Cheon’s scheme [9]. Both of the schemes are secure in the remaining time periods against an adversary who compromises the KGC and obtains a user’s secret key for the time periods of its choice. All the schemes in this paper are provably secure in the random oracle model.

The efficient computation of the Tate pairing is a crucial factor to realize cryptographic applications practically. To compute the Tate pairing, two kinds of costs on the scalar multiplications and Miller’s line functions of elliptic curves should be considered. In the present paper, encapsulated scalar multiplications and line functions are discussed. Some simplified formulas and improved algorithms to compute , , , , and etc., are presented from given points and on the elliptic curve.

Some blind signature schemes have been constructed from some underlying signature schemes, which are efficient and provably secure in the random oracle. To the best of authors’ knowledge, a problem still remains: does the security of the original signature scheme, by itself, imply the security of the blind version? In this paper, we answer the question. We show if the blind factors in the blind version come from hash functions, the design of blind signature scheme can be validated in random oracle model if the original scheme is provably secure. We propose a blind version of Schnorr signature scheme and reduce the security of the proposed scheme to the security of ECDLP. What’s more, the complexity of this reduction is polynomial in all suitable parameters in the random oracle.

This paper proposes a new public key encryption scheme. It is based on the difficulty of deducing and from and  = · · in a specific monoid (,·) which is noncommutative. So we select and do research work on the certain monoid which is formed by all the × matrices over finite field under multiplication. By the cryptographic properties of an “ergodic matrix”, we propose a hard problem based on the ergodic matrices over , and use it construct a public key encryption scheme.

In pairing-based cryptosystems, radix- signed-digit representations are used to speed up point multiplication over supersingular elliptic curves or hyper-elliptic curves in characteristic . We propose a left-to-right radix- signed-digit recoding algorithm, which can obtain a new signed-digit representation from left to right. It is proved that its average non-zero density is asymptotically , which is reduced by 20%-50% compared with the previous left-to-right radix- signed-digit representations. The proposed algorithm can be applied to efficient implementations of pairing-based cryptosystems over supersingular elliptic curves or hyper-elliptic curves.

Sacks [14] showed that every computably enumerable (c.e.) degree ≥ 0 has a c.e. splitting. Hence, relativising, every c.e. degree has a splitting above each proper predecessor (by ’splitting’ we understand ’nontrivial splitting’). Arslanov [1] showed that 0’ has a d.c.e. splitting above each c.e. a < 0’. On the other hand, Lachlan [9] proved the existence of a c.e. a > 0 which has no c.e. splitting above some proper c.e. predecessor, and Harrington [8] showed that one could take a = 0’. Splitting and nonsplitting techniques have had a number of consequences for definability and elementary equivalence in the degrees below 0’.

The strong weak truth table (sw) reducibility was suggested by Downey, Hirschfeldt and LaForte as a measure of relative randomness. In this paper, in order to discuss the structure of sw-degrees further, we introduce the definition of sw-cuppable for c.e. reals. For c.e reals, it is natural to conclude that there exist sw-cuppable c.e. reals. The main result of this paper is that there exists an sw-cuppable strongly c.e. real.

In this paper, we propose a new decision problem, called the concurrently enabled transition set problem, which is proved to be NP-complete by reduction from the independent set problem. Then, we present a polynomial-time algorithm for the maximal concurrently enabled transition set problem, and prove that some special subproblems are in P by the proposed algorithm.