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]