Search

The scalable video coding extension of H.264/AVC standard specifies the usage of layered scalable bit streams to achieve temporal, spatial and quality scalability. The inter-layer redundancies are exploited in addition to spatial and temporal predictions to obtain a better coding efficiency. The addition of inter-layer modes increases the computational complexity of the mode decision process in the enhancement layer. We propose a fast mode decision algorithm based on spatiograms for reducing the computational overhead during the encoding process. Our algorithm is based on constructing spatiograms for the macroblocks and comparing them to find the similarity of the macroblocks. This similarity measure is used to evaluate only a subset of modes leading to reduction in coding time. Our experiment results show that the time saving is around 29% to 67% based on the video sequence with a quality loss between 0 to -0.04dB and bit rate increase in the range -0.21% to 0.94%. The quality loss and the bit rate increase from our proposed algorithm is extremely insignificant when compared to the original JSVM 9.8 reference implementation. [ABSTRACT FROM AUTHOR]

Certificateless cryptography introduced by Al-Riyami and Paterson eliminates the key escrow problem inherent in identity based cryptosystems. Even though building practical identity based signcryption schemes without bilinear pairing are considered to be almost impossible, it will be interesting to explore possibilities of constructing such systems in other settings like certificateless cryptography. Often for practical systems, bilinear pairings are considered to induce computational overhead. Signcryption is a powerful primitive that offers both confidentiality and authenticity to noteworthy messages. Though some prior attempts were made for designing certificateless signcryption schemes, almost all the known ones have security weaknesses. Specifically, in this paper we demonstrate the security weakness of the schemes in [2], [1] and [6]. We also present the first provably secure certificateless signcryption scheme without bilinear pairing and prove it in the random oracle model. [ABSTRACT FROM AUTHOR]

Sanitizable signatures provide several security features which are useful in many scenarios including military and medical applications. Sanitizable signatures allow a semi-trusted party to update some part of the digitally signed document without interacting with the original signer. Such schemes, where the verifier cannot identify whether the message has been sanitized, are said to possess strong transparency. In this paper, we have described the first efficient and provably secure sanitizable signature scheme having strong transparency under the standard model. [ABSTRACT FROM AUTHOR]

Signcryption is a cryptographic primitive that fulfills both the functions of digital signature and public key encryption in a single step, at a cost significantly lower than that is required by the traditional signature-then-encrypt approach. Threshold involved with signcryption is used where the sender or receiver side has a group of members. Threshold Signcryption comes into picture when a message to be sent needs the authentication of a particular number of members in an organization, whereas threshold unsigncryption is used where until a given number of members join, a particular message cannot be decrypted. In this paper we show that three of the threshold signcryption schemes reported in the literature, lack confidentiality under the stronger notion of insider security. We also propose an improved scheme and give the formal proof of security in new stronger security model. [ABSTRACT FROM AUTHOR]

We propose an efficient statistically secure asynchronous multiparty computation (AMPC) protocol with optimal fault tolerance; i.e., with n = 3t + 1, where n is the total number of parties and t is the number of parties that can be under the influence of a Byzantine (active) adversary ]> having unbounded computing power. Our protocol privately communicates ]> bits per multiplication gate and involves a negligible error probability of 2 − Ώ(Κ), where Κ is the error parameter. As far as our knowledge is concerned, the only known statistically secure AMPC protocol with n = 3t + 1 is due to [7], which privately communicates Ώ(n11Κ4) bits and A-casts Ώ(n11Κ2 log(n)) bits per multiplication gate. Here A-cast is an asynchronous broadcast primitive, which allows a party to send some information to all other parties identically. Thus our AMPC protocol shows significant improvement in communication complexity over the AMPC protocol of [7]. [ABSTRACT FROM AUTHOR]

Denial of Service (DoS) vulnerabilities are one of the major concerns in today΄s internet. Client-puzzles offer a good mechanism to defend servers against DoS attacks. In this paper, we introduce the notion of hidden puzzle difficulty, where the attacker cannot determine the difficulty of the puzzle without expending a minimal amount of computational resource. We propose three concrete puzzles that satisfy this requirement. Using game theory, we show that a defense mechanism is more effective when it uses a hidden difficulty puzzle. Based on the concept of Nash equilibrium, we develop suitable defense mechanisms that are better than the existing ones. [ABSTRACT FROM AUTHOR]

Often authentication and confidentiality are required as simultaneous key requirements in many cryptographic applications. The cryptographic primitive called signcryption effectively implements the same and while most of the public key based systems are appropriate for small messages, hybrid encryption (KEM-DEM) provides an efficient and practical way to securely communicate very large messages. The concept of certificateless hybrid signcryption has evolved by combining the ideas of signcryption based on tag-KEM and certificateless cryptography. Recently, Lippold et al. [14] proposed a certificateless KEM in the standard model and the first certificateless hybrid signcryption scheme was proposed by Fagen Li et al. [16]. In this paper, we show that [14] is not Type-I CCA secure and [16] is existentially forgeable. We also propose an improved certificateless hybrid signcryption scheme and formally prove the security of the improved scheme against both adaptive chosen ciphertext attack and existential forgery in the appropriate security model for certificateless hybrid signcryption. [ABSTRACT FROM AUTHOR]

Verifiable Secret Sharing (VSS) is a fundamental primitive used in many distributed cryptographic tasks, such as Multiparty Computation (MPC) and Byzantine Agreement (BA). It is a two phase (sharing, reconstruction) protocol. The VSS and MPC protocols are carried out among n parties, where t out of n parties can be under the influence of a Byzantine (active) adversary, having unbounded computing power. It is well known that protocols for perfectly secure VSS and perfectly secure MPC exist in an asynchronous network iff n ≥ 4t + 1. Hence, we call any perfectly secure VSS (MPC) protocol designed over an asynchronous network with n = 4t + 1 as optimally resilient VSS (MPC) protocol. A secret is d-shared among the parties if there exists a random degree-d polynomial whose constant term is the secret and each honest party possesses a distinct point on the degree-d polynomial. Typically VSS is used as a primary tool to generate t-sharing of secret(s). In this paper, we present an optimally resilient, perfectly secure Asynchronous VSS (AVSS) protocol that can generate d-sharing of a secret for any d, where t ≤ d ≤ 2t. This is the first optimally resilient, perfectly secure AVSS of its kind in the literature. Specifically, our AVSS can generate d-sharing of ℓ ≥ 1 secrets from ]> concurrently, with a communication cost of ]> bits, where ]> is a finite field. Communication complexity wise, the best known optimally resilient, perfectly secure AVSS is reported in [2]. The protocol of [2] can generate t-sharing of ℓ secrets concurrently, with the same communication complexity as our AVSS. However, the AVSS of [2] and [4] (the only known optimally resilient perfectly secure AVSS, other than [2]) does not generate d-sharing, for any d > t. Interpreting in a different way, we may also say that our AVSS shares ℓ(d + 1 − t) secrets simultaneously with a communication cost of ]> bits. Putting d = 2t (the maximum value of d), we notice that the amortized cost of sharing a single secret using our AVSS is only ]> bits. This is a clear improvement over the AVSS of [2] whose amortized cost of sharing a single secret is ]> bits. As an interesting application of our AVSS, we propose a new optimally resilient, perfectly secureAsynchronous Multiparty Computation (AMPC) protocol that communicates ]> bits per multiplication gate. The best known optimally resilient perfectly secure AMPC is due to [2], which communicates ]> bits per multiplication gate. Thus our AMPC improves the communication complexity of the best known AMPC of [2] by a factor of Ώ(n). [ABSTRACT FROM AUTHOR]

We consider the round complexity of a basic cryptographic task: verifiable secret sharing (VSS). This well-studied primitive provides a good ˵test case″ for our understanding of round complexity in general; moreover, VSS is important in its own right as a central building block for, e.g., Byzantine agreement and secure multi-party computation. The round complexity of perfect VSS was settled by Gennaro et al. (STOC 2001) and Fitzi et al. (TCC 2006). In a surprising result, Patra et al. (Crypto 2009) recently showed that if a negligible probability of error is allowed, the previous bounds no longer apply. We settle the key questions left open by their work, and in particular determine the exact round complexity of statistical VSS with optimal threshold. Let n denote the number of parties, at most t of whom are malicious. Their work showed that 2-round statistical VSS is impossible for t ≥ n/3. We show that 3-round statistical VSS is possible iff t < n/2. We also give an efficient 4-round protocol for t < n/2. [ABSTRACT FROM AUTHOR]

Broadcast (BC) is considered as the most fundamental primitive for fault-tolerant distributed computing and cryptographic protocols. An important and practical variant of BC is Asynchronous BC (known as A-cast). An A-cast protocol enables a specific party called sender (possibly corrupted) to send some message identically to a set of parties despite the presence of an adversary who may corrupt some of the parties in a malicious manner. Though the existing protocol for A-cast is designed for a single bit message, in real life applications typically A-cast is invoked on long message (whose size can be in gigabytes) rather than on single bit. Therefore, it is important to design efficient multi-valued A-cast protocols (i.e protocols with long message) which extract several advantages offered by directly dealing with long messages and are far better than multiple invocations to existing protocols for single bit. In this paper, we design highly efficient, communication optimal, optimally resilient multi-valued A-cast protocol for long messages, based on access to the existing A-cast protocol for short messages. Our protocol also provides better communication complexity than existing protocol for A-cast. [ABSTRACT FROM AUTHOR]

Treewidth and pathwidth are important graph parameters that represent how close the graph is to trees and paths respectively. We calculate treewidth and pathwidth on parameterized chordal and threshold graphs. We define a chordal + 1v graph as a graph that can be made into a chordal graph by removing a vertex. We give polynomial time algorithms for computing the treewidth of a chordal + 1v graph, pathwidth of a threshold + 1v graph and a threshold + 2e graph. The mixed search number of a graph is the minimum number of cops required to capture a single robber, who is hiding in the graph. We apply the algorithm to compute the pathwidth in order to compute the mixed search number of a threshold + 1v graph. [ABSTRACT FROM AUTHOR]

In a distributed computing environment a faulty node could lead other nodes in the system to behave in a faulty manor. An initial set of faults could make all the nodes in the system become faulty. Such a set is called an irreversible dynamo. This is modelled as spreading a message among individuals V in a community ]> where E represents the acquaintance relation. A particular individual will believe a message if some of the individual΄s acquaintances believe the same and forward the believed messages to its neighbours. We are interested in finding the minimum set of initial individuals to be considered as convinced, called the min-seed, such that every individual in the community is finally convinced. We solve for min-seed on some special classes of graphs and then give an upper bound on the cardinality of the min-seed for arbitrary undirected graphs. We consider some interesting variants of the problem and analyse their complexities and give some approximate algorithms. [ABSTRACT FROM AUTHOR]

We re-visit the problem of perfectly secure message transmission (PSMT) in a directed network under the presence of a threshold adaptive Byzantine adversary, having unbounded computing power. Specifically, we derive the lower bounds on communication complexity of (a) two phase PSMT protocols and (b) three or more phase PSMT protocols in directed networks. Moreover, we show that our lower bounds are asymptotically tight, by designing communication optimal PSMT protocols in directed networks, which are first of their kind. We re-visit the problem of perfectly reliable message transmission (PRMT) as well. Any PRMT protocol that sends a message containing ℓ field elements by communicating ]> field elements, is referred as communication optimal PRMT or PRMT with constant factor overhead. Here, we characterize the class of directed networks over which communication optimal PRMT or PRMT with constant factor overhead is possible. Moreover, we design a communication optimal PRMT over a directed network that satisfies the conditions stated in our characterization. [ABSTRACT FROM AUTHOR]

In the recent past composability has emerged as a key requirement for various distributed protocols. It is not enough for a protocol to be robust when it runs in isolation or in a ˵stand-alone″ setting but it should be robust even in an environment where several copies of the same protocol or other protocol(s) are running simultaneously. In this work, we investigate the composability for protocols that tolerate a bounded adversary modeled as a probabilistic polynomial time Turing machine. We examine composability of protocols for two fundamental problems in distributed computing - reliable unicast and reliable broadcast. We show that any composable protocol – for reliable unicast tolerating an adversary, that corrupts up to any t nodes, requires 2t + 1 connectivity and for reliable broadcast tolerating an adversary, that corrupts up to any t nodes, requires n > 3t and 2t + 1 connectivity. [ABSTRACT FROM AUTHOR]

We present a new statistical asynchronous verifiable secret sharing (AVSS) protocol with optimal resilience; i.e. with n = 3t + 1, where n is the total number of participating parties and t is the maximum number of parties that can be under the control of a computationally unbounded active adversary ]> . Our protocol privately communicates ]> bits and A-casts ]> bits to simultaneously share ℓ ≥ 1 elements from a finite field ]> , where Κ is the error parameter. There are only two known statistical AVSS protocols with n = 3t + 1, reported in [11] and [26]. The AVSS protocol of [11] requires a private communication of ]> bits and A-cast of ]> bits to share a single element from ]> . Thus our AVSS protocol shows a significant improvement in communication complexity over the AVSS of [11]. The AVSS protocol of [26] requires a private communication of ]> bits and A-cast of ]> bits to share ℓ ≥ 1 elements. However, the shared element(s) may be ]> . Thus our AVSS is better than the AVSS of [26] due to two reasons: (a) The A-cast communication of our AVSS is independent of the number of secrets i.e. ℓ; (b) Our AVSS makes sure that the shared value(s) always belong to ]> . Using our AVSS, we design a new primitive called Asynchronous Complete Secret Sharing (ACSS) which is an essential building block of asynchronous multiparty computation (AMPC). Using our ACSS scheme, we can design a statistical AMPC with optimal resilience; i.e., with n = 3t + 1, that privately communicates ]> bits per multiplication gate. This will significantly improve the only known statistical AMPC of [8] with n = 3t + 1, which privately communicates Ώ(n11Κ4) bits and A-cast Ώ(n11Κ2 log(n)) bits per multiplication gate. [ABSTRACT FROM AUTHOR]

In information theoretic model, unconditionally secure multiparty computation (UMPC) allows a set of n parties to securely compute an agreed function f, even upto t < n/2 parties are under the control of an active adversary having unbounded computing power. The bound on the resilience/fault tolerance (i.e t < n/2 ) is optimal, as long as each party is connected with every other party by a secure channel and a common physical broadcast channel is available to the parties and a negligible error probability of ]> (for some security parameter Κ) is allowed in the computation. Any UMPC protocol designed under the above settings is called as optimally resilient UMPC protocol. In this paper, we propose an optimally resilient UMPC protocol with n = 2t + 1, which requires only ]> rounds, where ]> is the multiplicative depth of the arithmetic circuit representing f. To the best of our knowledge, our protocol is the first UMPC protocol with optimal resilience, to attain a round complexity that is independent of n. When ]> is constant, then our protocol requires only constant number of rounds. Our protocol is to be compared with the most round efficient, optimally resilient, UMPC protocol of [16] that requires ]> rounds in the same settings as ours. Thus our UMPC significantly reduces the round complexity of [16]. Moreover, our UMPC protocol requires the same communication complexity as that of [16]. As a tool for designing our UMPC protocol, we propose a new and robust multiplication protocol to generate t-sharing of the product of two t-shared secrets. As an interesting, practically-on-demand MPC problem, we present a protocol for unconditionally secure multiparty set intersection (UMPSI) with optimal resilience; i.e., with n = 2t + 1, having a negligible error probability in correctness. This protocol adapts the techniques used in our proposed general UMPC protocol. The protocol takes constant number rounds, incurs a private communication of ]> bits and broadcasts ]> bits, where each party has a set of size m. To the best of our knowledge, this is the first ever UMPSI protocol with n = 2t + 1. This solves an open problem posed in [15] and [17], urging to design an UMPSI protocol with n = 2t + 1. Our UMPSI protocol is to be compared with the best known UMPSI protocol of [17] with n = 3t + 1 (i.e., non-optimal resilience), which takes constant number rounds, incurs a private communication of ]> bits and broadcasts ]> bits. So even though the communication complexity of our UMPSI protocol is slightly larger than that of [17], our UMPSI protocol significantly improves the resilience of UMPSI protocol of [17]; i.e., from t < n / 3 to t < n / 2. [ABSTRACT FROM AUTHOR]

An identity-based signature scheme allows any pair of users to communicate securely and to verify each others signatures without exchanging public key certificates. For achieving both confidentiality and authenticity simultaneously, signcryption schemes are used. An aggregate signature scheme is a digital signature scheme that supports aggregation of individual signatures. Given n signatures on n distinct messages signed by n distinct users, it is possible to aggregate all these signatures into a single signature. This signature will convince the verifier that all the n signers have signed the corresponding n messages. In this paper, we introduce the concept of aggregate signcryption which achieves confidentiality, authentication and aggregation efficiently. This helps in improving the communication and the computation efficiency. Also, we extend the scheme to achieve public verifiability with very efficient aggregate verification, that uses fixed number of pairings. [ABSTRACT FROM AUTHOR]

Signcryption is a cryptographic primitive that provides authentication and confidentiality simultaneously in a single logical step. It is often required that multiple senders have to signcrypt a single message to a certain receiver. Obviously, it is inefficient to signcrypt the messages separately. An efficient alternative is to go for multi-signcryption. The concept of multi-signcryption is similar to that of multi-signatures with the added property - confidentiality. Recently, Jianhong et al. proposed an identity based multi-signcryption scheme. They claimed that their scheme is secure against adaptive chosen ciphertext attack and it is existentially unforgeable. In this paper, we show that their scheme is not secure against chosen plaintext attack and is existentially forgeable, we also provide a fix for the scheme and prove formally that the improved scheme is secure against both adaptive chosen ciphertext attack and existential forgery. [ABSTRACT FROM AUTHOR]

In applications like wireless content distribution, a central authority needs to deliver encrypted data to a large number of recipients in such a way that only a privileged subset of users can decrypt it. In addition, to avert junk content or spam, subscribers must have source authentication with respect to their broadcasters. The limited memory and computational power of mobile devices, coupled with escalating costs of wireless bandwidth make efficiency a major concern. Broadcast signcryption, which enables the broadcaster to simultaneously encrypt and sign the content meant for a specific set of users in a single logical step, provides the most efficient solution to this dual problem of confidentiality and authentication. It is arguably most efficiently implemented in the ID-based setting because of its well known advantages. Only three IBBSC schemes exist in literature, one of which has already been shown to be flawed and its security leaks fixed. In this paper, we show that the remaining two – Mu et al.΄s scheme and Li et al.΄s scheme are also flawed. Specifically, we show that while Mu et al.΄s scheme is insecure with respect to unforgeability, Li et al.΄s scheme can be totally broken (with respect to both unforgeability and confidentiality). Following this, we propose a new IBBSC scheme and formally prove its security under the strongest existing security models for broadcast signcryption (IND-CCA2 and EUF-CMA). [ABSTRACT FROM AUTHOR]

A core path of a graph is a path P in G that minimizes d(P) = ]> . In this paper, we study the location of core path of specified length in special classes of graphs. Further, we extend our study to the problem of locating a core path of specified length under the condition that some existing facilities are already located (known as conditional core path of a graph). We study both the problems stated above in vertex weighted bipartite permutation graphs, threshold graphs and proper interval graphs and give polynomial time algorithms for the core path and conditional core path problem in these classes. We also establish the NP-Completeness of the above problems in the same classes of graphs when arbitrary positive weights are assigned to edges. [ABSTRACT FROM AUTHOR]

In the PSMT problem, a sender S and a receiver R are part of a distributed network and connected through n node disjoint paths, also called as wires among which at most t are controlled by an all powerful Byzantine adversary ]> . S has a message m, which S intends to send to R. The challenge is to design a protocol, such that at the end, R should correctly output m without any error (perfect reliability) and ]> should not get any information about m, what so ever, in information theoretic sense (perfect security). The problem of USMT is same as PSMT, except that R should output m with a small probability of error. Sayeed et al. [15] have given a PSMT protocol in an asynchronous network tolerating ]> , where S and R are connected by n = 2t + 1 wires. However, we show that their protocol does not provide perfect security. We then prove that in an asynchronous network, if all the n wires are directed from S to R, then any PSMT protocol tolerating ]> is possible iff n > 3t. Surprisingly, we further prove that even if all the n wires are bi-directional, then any PSMT protocol in asynchronous network tolerating ]> is possible iff n > 3t. This is quite interesting because for synchronous networks, by the results of Dolev et al. [6] , if all the wires are unidirectional (directed from S to R), then PSMT tolerating ]> is possible iff n > 3t, where as if all the wires are bi-directional then PSMT tolerating ]> is possible iff n > 2t. This shows that synchrony of the network affects the connectivity requirement for PSMT protocols. However, we show that n > 2t wires are necessary and sufficient for the existence of any USMT protocol in asynchronous network tolerating ]> , irrespective of whether the n wires are unidirectional from S to R or the n wires are bi-directional. [ABSTRACT FROM AUTHOR]

This work deals with the problem of fault-tolerant communication over networks, some of whose nodes are corrupted by a centralized byzantine adversary. The extant literature΄s perspective of the problem of reliable communication, especially in networks whose topology is known, is that of a simple problem to which even some naive solutions (like message-flooding etc.) turn out to be reasonably efficient. In this paper, we give an example of a directed graph and a non threshold adversary structure, which will require every protocol for perfect reliable unicast to transmit exponential number of bits in order to reliably transmit a single bit. [ABSTRACT FROM AUTHOR]

We re-visit the problem of secure multiparty set intersection (MPSI) in information theoretic settings. In [15], Li et.al have proposed a protocol for MPSI with n = 3t + 1 parties, that provides information theoretic security, when t out of those n parties are corrupted by an active adversary having unbounded computing power. In [15], the authors have claimed that their protocol takes six rounds of communication and communicates ]> field elements, where each party has a set containing m field elements. However, we show that the round and communication complexity of the protocol in [15] is much more than what is claimed in [15]. We then propose a novel information theoretically secure protocol for MPSI with n ≥ 3t + 1, which significantly improves the ″actual″ round and communication complexity of the protocol of [15]. Our protocols employ several tools which are of independent interest. [ABSTRACT FROM AUTHOR]

The round complexity of interactive protocols is one of their most important complexity measures. In this work we prove that existing lower bounds for the round complexity of VSS can be circumvented by introducing a negligible probability of error in the reconstruction phase. Previous results show matching lower and upper bounds of three rounds for VSS, with n = 3t + 1, where the reconstruction of the secrets always succeeds, i.e. with probability 1. In contrast we show that with a negligible probability of error in the reconstruction phase: 1 There exists an efficient 2-round VSS protocol for n = 3t + 1. If we assume that the adversary is non-rushing then we can achieve a 1-round reconstruction phase. 1 There exists an efficient 1-round VSS for t = 1 and n > 3. 1 We prove that our results are optimal both in resilience and number of sharing rounds by showing: 1 There does not exist a 2-round WSS (and hence VSS) for n ≤ 3t. 1 There does not exist a 1-round VSS protocol for t ≥ 2 and n ≥ 4. [ABSTRACT FROM AUTHOR]

Let G = (V, E) be the given graph and GR = (VR,ER) and GC = (VC,EC) be the sub graphs of G such that VR ∩ VC = ⵁ and VR = VC= V. GC is referred to as the cops region and GR is called as the robber region. Initially a robber is placed at some vertex of VR and the cops are placed at some vertices of VC. The robber and cops may move from their current vertices to one of their neighbours. While a cop can move only within the cops region, the robber may move to any neighbour. The robber and cops move alternatively. A vertex v ϵ VC is said to be attacked if the current turn is the robber΄s turn, the robber is at vertex u where u ϵ VR, (u,v) ϵ E and no cop is present at v. The guarding problem is to find the minimum number of cops required to guard the graph GC from the robber΄s attack. We first prove that the decision version of this problem when GR is an arbitrary undirected graph is PSPACE-hard. We also prove that the complexity of the decision version of the guarding problem when GR is a wheel graph is NP-hard. We then present approximation algorithms if GR is a star graph, a clique and a wheel graph with approximation ratios H(n1), 2 H(n1) and ]> respectively, where ]> and n1 = ǀ VR ǀ. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of Perfectly Reliable Message Transmission (PRMT) and Perfectly Secure Message Transmission (PSMT) between two nodes S and R in an undirected synchronous network, a part of which is under the influence of an all powerful mobile Byzantine adversary. We design a three phase bit optimal PSMT protocol tolerating mobile adversary, whose communication complexity matches the existing lower bound on the communication complexity of any multi phase PSMT protocol, tolerating mobile adversary. This significantly reduces the phase complexity of the existing O(t) phase bit optimal PSMT protocol tolerating mobile adversary, where t denotes the number of nodes corrupted by the mobile adversary. Furthermore, we design a three phase bit optimal PRMT protocol which achieves reliability with constant factor overhead against a mobile adversary. These are the first ever constant phase bit optimal PRMT and PSMT protocols against mobile Byzantine adversary. We also characterize PSMT protocols in directed networks tolerating mobile adversary. Finally, we derive tight bound on the number of rounds required to achieve reliable communication from S to R tolerating a mobile adversary with arbitrary roaming speed.Finally, we show how our constant phase PRMT and PSMT protocols can be adapted to design round optimal and bit optimal PRMT and PSMT protocols, provided the network is given as collection of vertex disjoint paths. [ABSTRACT FROM AUTHOR]

In this paper, we propose a round efficient unconditionally secure multiparty computation (UMPC) protocol in information theoretic model with n > 2t players, in the absence of any physical broadcast channel. Our protocol communicates ]> field elements per multiplication and requires ]> rounds, even if up to t players are under the control of an active adversary having unbounded computing power, where ]> denotes the multiplicative depth of the circuit representing the function to be computed securely. In the absence of a physical broadcast channel and with n > 2t players, the best known UMPC protocol with minimum number of rounds, requires ]> rounds and communicates ]> field elements per multiplication. On the other hand, the best known UMPC protocol with minimum communication complexity requires communication overhead of ]> field elements per multiplication, but has a round complexity of ]> rounds. Hence our UMPC protocol is the most round efficient protocol so far and ranks second according to communication complexity. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of perfectly reliable message transmission (PRMT) and perfectly secure message transmission (PSMT) between a sender S and a receiver R in an undirected synchronous network, tolerating a mixed adversary, where the adversary can be either static or mobile. The connectivity requirement, phase complexity and communication complexity are three important parameters of any interactive PRMT/PSMT protocol and are well studied in the literature in the presence of a static/mobile Byzantine adversary. However, in the presence of a mixed adversary, we encounter several surprising consequences. In this paper, we prove that even though the connectivity requirement for PRMT is same against both static and mobile mixed adversary, the lower bound on communication complexity for PRMT tolerating a mobile mixed adversary is more than its static mixed counterpart. This is interesting because against a ″Byzantine adversary″, the connectivity requirement and the lower bound on the communication complexity of PRMT protocols are same for both static and mobile case. Thus our result shows that for PRMT, a mobile mixed adversary is more powerful than its static counterpart. As our second contribution, we design a four phase communication optimal PSMT protocol tolerating a ″static mixed adversary″. Comparing this with the existing three phase communication optimal PSMT protocol against a ″static Byzantine adversary″, we find that additional one phase is enough to design communication optimal protocol against a static mixed adversary. Finally, we show that the connectivity requirement and lower bound on communication complexity of any PSMT protocol is same against both static and mobile mixed adversary, thus proving that mobility of the adversary has no effect on PSMT. To show that our bound is tight, we also present a worst case nine phase communication optimal PSMT protocol tolerating a mobile mixed adversary which is first of it΄s kind. This also shows that the mobility of the adversary does not hinder to design constant phase communication optimal PSMT protocol. In our protocols, we have used new techniques which can be effectively used against both static and mobile mixed adversary and are of independent interest. [ABSTRACT FROM AUTHOR]

We study the problem of unconditionally reliable message transmission (URMT), where a sender S and a receiver R are part of a synchronous network modeled as a directed hypergraph, a part of which may be under the influence of an adversary having unbounded computing power. S intends to transmit a message m to R, such that R should correctly obtain S΄s message with probability at least (1 − δ) for arbitrarily small δ> 0. However, unlike most of the literature on this problem, we assume the adversary modeling the faults is threshold mixed, and can corrupt different set of nodes in Byzantine, passive and fail-stop fashion simultaneously. The main contribution of this work is the complete characterization of URMT in directed hypergraph tolerating such an adversary, which is done for the first time in the literature. [ABSTRACT FROM AUTHOR]

In this paper, we design URMT and USMT protocols which are communication optimal in amortized sense and first of their kind. [ABSTRACT FROM AUTHOR]

This paper introduces the Repeated Rational Secret Sharing problem. We borrow the notion of rational secret sharing from Halpern and Teague[1], where players prefer to get the secret than not to get the secret and with lower preference, prefer that as few of the other players get the secret. We introduce the concept of repeated games in the rational secret sharing problem for the first time, which enables the possibility of a deterministic protocol for solving this problem. This is the first approach in this direction to the best of our knowledge. We extend the results for the mixed model (synchronous) where at most t players can be malicious. We also propose the first asynchronous protocol for rational secret sharing. [ABSTRACT FROM AUTHOR]

Integrating data mining techniques into database systems has gained popularity and its significance is well recognized. However, the performance of SQL based data mining is known to fall behind specialized implementations. Reasons for this are among others the prohibitive nature of the cost associated with extracting knowledge as well as the lack of suitable declarative query language support. Recent studies have found that for association rule mining and sequential pattern mining with carefully tuned SQL formulations it is possible to achieve performance comparable to systems that cache the data in files outside the DBMS. However, most of the previous pattern mining methods follow the method of Apriori, which still encounters problems when a sequential database is large and/or when sequential patterns to be mined are numerous and long. In this paper, we present a novel SQL based approach that we recently proposed, called Prospad (PROjection Sequential PAttern Discovery). Prospad fundamentally differs from an Apriori-like candidate set generation-and-test approach. This approach is a pattern growth-based approach without candidate generation. It grows longer patterns from shorter ones by successively projecting the sequential table into subsequential tables. Since a projected table for a sequential pattern i contains all and only necessary information for mining the sequential patterns that can grow from i, the size of the projected table usually reduces quickly as mining proceeds to longer patterns. Moreover, a depth first approach is used to facilitate the projecting process in order to avoid creating and dropping costs of temporary tables. [ABSTRACT FROM AUTHOR]

Ontologies are an important technology for the Semantic Web. In different areas ontologies have already been developed and many of these ontologies contain overlapping information. Often we would therefore want to be able to use multiple ontologies. To obtain good results, we need to find the relationships between terms in the different ontologies, i.e. we need to align them. Currently, there exist a number of systems that support users in aligning ontologies, but not many comparative evaluations have been performed and there exists little support to perform such evaluations. However, the study of the properties, the evaluation and comparison of the alignment strategies and their combinations, would give us valuable insight in how the strategies could be used in the best way. In this paper we propose the KitAMO framework for comparative evaluation of ontology alignment strategies and their combinations and present our current implementation. We evaluate the implementation with respect to performance. We also illustrate how the system can be used to evaluate and compare alignment strategies and their combinations in terms of performance and quality of the proposed alignments. Further, we show how the results can be analyzed to obtain deeper insights into the properties of the strategies. [ABSTRACT FROM AUTHOR]

The Semantic Web envisions a world-wide distributed architecture where computational resources will easily inter-operate to coordinate complex tasks such as query answering. Semantic marking up of web resources using ontologies is expected to provide the necessary glue for making this vision work. Using ontology languages, (communities of) users will build their own ontologies in order to describe their own data. Adding semantic mappings between those ontologies, in order to semantically relate the data to share, gives rise to the Semantic Web: data on the web that are annotated by ontologies networked together by mappings. In this vision, the Semantic Web is a huge semantic peer data management system. In this paper, we describe the SomeRDFS peer data management systems that promote a "simple is beautiful" vision of the Semantic Web based on data annotated by RDFS ontologies. [ABSTRACT FROM AUTHOR]

A data warehouse (DW) is a database that integrates data from external data sources (EDSs) for the purpose of advanced analysis. EDSs are production systems that often change not only their contents but also their structures. The evolution of EDSs has to be reflected in a DW that integrates the sources. Traditional DW systems offer a limited support for the evolution of their structures. Our solution to this problem is based on a multiversion data warehouse (MVDW). Such a DW is composed of the sequence of persistent versions, each of which describes a schema and data within a given time period. The management of the MVDW requires a metadata model that is much more complex than in traditional data warehouses. In our approach and prototype MVDW system, the metadata model contains data structures that support: (1) monitoring EDSs with respect to content and structural changes, (2) automatic generation of processes monitoring EDSs, (3) applying discovered EDS changes to a selected DW version, (4) describing the structure of every DW version, (5) querying multiple DW versions at the same time and presenting the results coming from multiple versions. [ABSTRACT FROM AUTHOR]

The goal of Model Management is the development of new technologies and mechanisms to support the integration, evolution and matching of data models at the conceptual and logical design level. Such tasks are to be performed by means of a set of model management operators which work on models and their elements, without being restricted to a particular metamodel (e.g. the relational or UML metamodel). We propose that generic model management should employ a generic metamodel (GMM) which serves as an abstraction of particular metamodels and preserves as much of the original features of modeling constructs as possible. A naive generalization of the elements of concrete metamodels in generic metaclasses would lose some of the specific features of the metamodels, or yield a prohibitive number of metaclasses in the GMM. To avoid these problems, we propose the Generic Role based MetamodelGeRoMe in which each model element is decorated with a set of role objects that represent specific properties of the model element. Roles may be added to or removed from elements at any time, which enables a very flexible and dynamic yet accurate definition of models. Roles expose to operators different views on the same model element. Thus, operators concentrate on features which affect their functionality but may remain agnostic about other features. Consequently, these operators can use polymorphism and have to be implemented only once using GeRoMe, and not for each specific metamodel. We verified our results by implementing GeRoMe and a selection of model management operators using our metadata system ConceptBase. [ABSTRACT FROM AUTHOR]

Classifications have been used for centuries with the goal of cataloguing and searching large sets of objects. In the early days it was mainly books; lately it has also become Web pages, pictures and any kind of digital resources. Classifications describe their contents using natural language labels, an approach which has proved very effective in manual classification. However natural language labels show their limitations when one tries to automate the process, as they make it very hard to reason about classifications and their contents. In this paper we introduce the novel notion of Formal Classification, as a graph structure where labels are written in a propositional concept language. Formal Classifications turn out to be some form of lightweight ontologies. This, in turn, allows us to reason about them, to associate to each node a normal form formula which univocally describes its contents, and to reduce document classification and query answering to reasoning about subsumption. [ABSTRACT FROM AUTHOR]

A viable ontology engineering methodology requires supporting domain experts in gradually building and managing increasingly complex versions of ontological elements and their converging and diverging interrelationships. Contexts are necessary to formalise and reason about such a dynamic wealth of knowledge. However, context dependencies introduce many complexities. In this article, we introduce a formal framework for supporting context dependency management processes, based on the DOGMA framework and methodology for scalable ontology engineering. Key notions are a set of context dependency operators, which can be combined to manage complex context dependencies like articulation, application, specialisation, and revision dependencies. In turn, these dependencies can be used in context-driven ontology engineering processes tailored to the specific requirements of collaborative communities. This is illustrated by a real-world case of interorganisational competency ontology engineering. [ABSTRACT FROM AUTHOR]

This paper describes a theoretical framework for inducing knowledge from incomplete data sets. The general framework can be used with any formalism based on a lattice structure. It is illustrated within two formalisms: the attribute-value formalism and Sowa's conceptual graphs. The induction engine is based on a non-supervised algorithm called default clustering which uses the concept of stereotype and the new notion of default subsumption, inspired by the default logic theory. A validation using artificial data sets and an application concerning the extraction of stereotypes from newspaper articles are given at the end of the paper. [ABSTRACT FROM AUTHOR]

In this paper we propose the use of non-persistent CSMA as an anti-collision procedure for RFID active tags. Current proposals for both passive and active tags are based on the framed slotted ALOHA protocol, which does not scale well requiring additional procedures for frame length adaptation. However, active RFID devices already include carrier sense capabilities with no additional cost and, thus, CSMA may be employed seamlessly. Nevertheless, selecting the contention micro-slots of CSMA in the classical way (i.e., with a uniform distribution and an exponential back-off algorithm) does not result in an efficient identification process, as we will demonstrate. Fortunately, better choices can be found. Recently, an optimal distribution for the selection of micro-slots for event-driven sensor networks has been computed, as well as a practical implementation: the Sift distribution. In this work we propose the application of the quasi-optimal Sift distribution along with CSMA for active tag identification. By means of an analytical study, we evaluate the average time needed for identification with this mechanism and compare it with the current ISO 18000-7 and EPC "Gen 2" standard. The results reveal that the Sift-based non-persistent CSMA outperforms both of them. Moreover, it also scales much better, without the need for further adaptation mechanisms. [ABSTRACT FROM AUTHOR]

This paper presents a CDMA closed-loop power control (CLPC) using channel prediction in time-varying mobile fading channels. The proposed CLPC that relies on least square (LS) or least mean square (LMS) based autoregressive (AR) low-rate prediction provides a particularly robust performance for large loop delays, especially in the presence of channel estimation errors. As the mobility increases the proposed CLPC reduces mean-square error (MSE) further than conventional CLPCs. The Monte-Carlo simulation results demonstrate the superiority of the proposed CLPC over conventional nonpredictive and predictive CLPCs. [ABSTRACT FROM AUTHOR]

Cognitive radio (CR) has been proposed as an effective technology for flexible use of the radio spectrum. The interference among primary users and CR users, however, becomes a critical problem when they are operating nearby using adjacent frequency channels with different transmission powers. In this paper, a CR-based bandwidth sharing architecture is proposed, which can effectively suppress adjacent channel interference (ACI) between them. This new approach is characterized by the adaptive frequency spreading, and the adaptive time spreading with power control for the subcarriers near the borders of the CR user's spectrum. The frequency spreading scheme provides with extra power gain against ACI, whereas the time spreading with power control guarantees the minimal interference to primary users from CR users. By computer simulation, it has been proved that the proposed system outperforms the conventional OFDM systems in both throughput and BER performance. [ABSTRACT FROM AUTHOR]

Under dynamic time division duplexing (D-TDD) architecture in OFDM cellular systems, the inter-BS and inter-MS interference is inevitable during the cross time slot (CTS) period, and this interference seriously degrades the wireless access system performance. To mitigate such interference, we propose a region and time partitioning D-TDD architecture for OFDM systems. Each time slot in the CTS period is split into several minislots, and then each cell is divided into as many regions as the number of minislots per time slot. We then assign each minislot only to the users in its corresponding region. On top of such architecture, which inherently separates interfering entities farther from each other, we design a robust time slot allocation scheme considering the channel status of each mobile station. By computer simulation, it has been verified that the proposed scheme outperforms conventional time slot allocation methods in both the outage probability and the bandwidth efficiency. [ABSTRACT FROM AUTHOR]