Abstract The concept of Proxy Re‐Encryption (PRE) was introduced by Blaze, Bleumer and Strauss at Eurocrypt in 1998. In this concept, a semi‐trusted proxy user acquires a re‐encryption key from the delegator. Then the proxy can easily convert the encrypted message under Alice's public key into an encrypted message under Bob's public key, without knowing the content of the message. For a unidirectional PRE, a master secret security (MSS) has been proposed as another security requirement by Ateniese et al. MSS provides security to the secret key of the delegator from computation by association with a malicious delegatee and dishonest proxy. In this study, first we have shown that Aono et al.'s scheme is not secure under the MSS model. Second, we have designed a unidirectional PRE scheme, based on Aono et al.'s study, and proved its security under the MSS model. In Table 2, we have shown that our scheme is more efficient in terms of computational and communication costs. Third, we have constructed a lattice‐based unidirectional PRE + scheme, similar to the scheme proposed by Wang et al. In this scheme the encryptor itself works as the delegator.

Using graph clustering, we improve accuracy of Kronecker social networks which are protected by differential privacy. Ensuring the differential privacy implicates addition of marginal changes to the network and publishing the modified network data. In many cases, it induces a large gap between the original network and the modified graph statistics, such that very little useful information can be inferred from the published graph. We use the fact that network structures in all graph clusters are similar, to improve the utility of the publication methods based on Kronecker graphs. Instead of anonymizing the social network as a whole, we anonymize each cluster of the network separately, and combine the sanitized results thereafter. We justify why this idea provides an anonymized social network with high utility and also prove that our output social network ensures rigorous differential privacy guarantees. Our experimental results show that our mechanism exhibits good agreement of the structural properties with the real graphs, and outperforms the existing anonymization techniques for certain utility measures.

Abstract The indistinguishability of ciphertext under the chosen ciphertext attack (IND‐CCA2) is often considered to offer the strongest security notion for a public key encryption system. Nowadays, because of the availability of powerful malwares, an adversary is able to obtain “more” information than what he could obtain in the CCA2 security model. In order to realistically model the threats posed by such malwares, we need to empower the adversary to obtain additional information. This paper initiates a research to counter malwares such as RAM scrapers and extend the CCA2 model with oracles providing additional information to capture the effect of RAM scrapers precisely. We call this more stronger security notion as glass box decryption. After discussing the new kind of attack/threat and the related oracle, we show that almost all CCA2 secure systems are vulnerable to this kind of attack. We then propose a new system that offers security against glass box decryption and provide the formal security proof for the new system in the standard model. Copyright © 2016 John Wiley & Sons, Ltd.

Since the discovery of identity based cryptography, a number of identity based encryption schemes were reported in the literature. Although a few schemes were proposed after its introduction, the first efficient identity based encryption scheme was proposed by Dan Boneh and Matthew K. Franklin in 2001. This encryption scheme uses Weil pairing on elliptic curves during both encryption and decryption process. In this paper, we propose a new identity based encryption scheme and prove its security in the random oracle model. There are two highlighting features in our scheme. First, it does not employ bilinear pairing computation during the encryption process. Second, our scheme does not require full domain hashing, which makes our scheme more practical and efficiently implementable. Moreover, we prove the security of our scheme by reducing it to the well known Computational Bilinear Diffie-Hellman problem. We first prove the security of our scheme in weaker security notion i.e. we prove our scheme to be IND-CPA secure. Then using Fujisaki Okamoto transformation, we convert our scheme to IND-CCA secure version.

Designing efficient key agreement protocols is a fundamental cryptographic problem. In this paper, we first define a security model for key agreement in certificateless cryptography that is an extension of earlier models. We note that the existing pairing free protocols are not secure in our model. We design an efficient pairing-free, single round protocol that is secure in our model based on the hardness assumption of the Computational Diffie Hellman (CDH) problem. We also observe that previously existing pairing-free protocols were secure based on much stronger assumptions such as the hardness of the Gap Diffie Hellman problem. We use a restriction of our scheme to design an efficient pairing-free single round identity based key agreement protocol that is secure in the id-CK+ model based on the hardness assumption of the CDH problem. Additionally, both our schemes satisfy several other security properties such as forward secrecy, resistance to reflection attacks etc.

Human navigation has been a topic of interest in spatial cognition from the past few decades. It has been experimentally observed that humans accomplish the task of way-finding a destination in an unknown environment by recognizing landmarks. Investigations using network analytic techniques reveal that humans, when asked to way-find their destination, learn the top ranked nodes of a network. In this paper we report a study simulating the strategy used by humans to recognize the centers of a network. We show that the paths obtained from our simulation has the same properties as the paths obtained in human based experiment. The simulation thus performed leads to a novel way of pathfinding in a network. We discuss the performance of our method and compare it with the existing techniques to find a path between a pair of nodes in a network.

The current paper is an investigation towards understanding the navigational performance of humans on a network when the 'landmark' nodes are blocked. We observe that humans learn to cope up, despite the continued introduction of blockages in the network. The experiment proposed involves the task of navigating on a word network based on a puzzle called the word morph. We introduce blockages in the network and report an incremental improvement in performance with respect to time. We explain this phenomenon by analyzing the evolution of the knowledge in the human participants of the underlying network as more and more landmarks are removed. We hypothesize that humans learn the bare essentials to navigate unless we introduce blockages in the network which would whence enforce upon them the need to explore newer ways of navigating. We draw a parallel to human problem solving and postulate that obstacles are catalysts for humans to innovate techniques to solve a restricted variant of a familiar problem.

Perfectly reliable message transmission (PRMT) is one of the fundamental problems in distributed computing. It allows a sender to reliably transmit a message to a receiver in an unreliable network, even in the presence of a computationally unbounded adversary. In this article, we study the inherent trade-off between the three important parameters of the PRMT protocols, namely, the network connectivity ( n ), the round complexity ( r ), and the communication complexity by considering the following generic question (which can be considered as the holy grail problem) in the context of the PRMT protocols. Given an n -connected network, a message of size ℓ (to be reliably communicated) and a limit c for the total communication allowed between the sender and the receiver, what is the minimum number of communication rounds required by a PRMT protocol to send the message, such that the communication complexity of the protocol is O( c )? We answer this interesting question by deriving a nontrivial lower bound on the round complexity. Moreover, we show that the lower bound is tight in the amortized sense, by designing a PRMT protocol whose round complexity matches the lower bound. The lower bound is the first of its kind, that simultaneously captures the inherent tradeoff between the three important parameters of a PRMT protocol.

We propose a new algorithm for improving the coding efficiency of bit-depth scalable video coding. While coding the enhancement layers in bit-depth scalable coding under scalable video coding framework, we apply a correction to the error residuals generated after the inverse tone mapping process. The correction factor is towards reducing the residual values close to zero and this leads to reduction in bitrate. While decoding, we compensate for the correction applied, by applying a filter based on laplacian kernel to the reconstructed high bit-depth images. The application of the laplacian filter helps in improving the quality (PSNR). We have implemented our algorithm in JSVM 8.12 reference software and performed experiments on different SVT and VIPER video sequences. Our results on an average, show a overall savings in bitrate (BDBR) of about 3.97% and a quality (BDPSNR) improvement of 0.19dB, when compared to existing JSVM 8.12 implementation.

A proxy signature scheme is a variant of digital signature scheme in which a signer delegates his signing rights to another person called proxy signer, so that the proxy signer can generate the signature of the actual signer in his absence. Self Proxy Signature (SPS) is a type of proxy signature wherein, the original signer delegates the signing rights to himself (Self Delegation), there by generating temporary public and private key pairs for himself. Thus, in SPS the user can prevent the exposure of his private key from repeated use. In this paper, we propose the first identity based self proxy signature scheme. We give a generic scheme and a concrete instantiation in the identity based setting. We have defined the appropriate security model for the same and proved both the generic and identity based schemes in the defined security model.

Signcryption is a cryptographic primitive that provides confidentiality and authenticity simultaneously at a cost significantly lower than that of the naive combination of encrypting and signing the message. Threshold signcryption is used when a message to be sent needs the authentication of a certain number of members in an organisation, and until and unless a given number of members (known as the threshold) join the signcyption process, a particular message cannot be signcrypted. Threshold unsigncryption is used when this constraint is applicable during the unsigncryption process. In this work, we cryptanalyze two threshold unsigncryption schemes. We show that both these schemes do not meet the stringent requirements of insider security and propose attacks on both confidentiality and unforgeability. We also propose an improved identity based threshold unsigncryption scheme and give the formal proof of security in a new stronger security model.

We design a three phase communication optimal perfectly secure message transmission (OPSMT) protocol tolerating a computationally unbounded mobile mixed adversary. This improves the nine phase OPSMT protocol of [2].

In [7], the authors presented a novel perfect (i.e error-free Asynchronous Verifiable Secret Sharing (AVSS) protocol and using the AVSS, they designed a perfect Asynchronous Multiparty Computation (AMPC) protocol that provides the best known communication complexity in the literature. In this paper, we show another important application of the AVSS in [7] by applying it to design an efficient Asynchronous Byzantine Agreement (ABA) protocol with n = 4t + 1, where n denotes the number of parties involved in the execution ABA and t denotes the maximum number of parties that can be corrupted by an active unbounded powerful adversary. Our ABA protocol attains a communication complexity that is significantly better than that of the only known existing ABA of [4] with n = 4t + 1, while keeping all other properties in place.

In this paper, we re-visit the problem of unconditionally secure message transmission (USMT) from a sender S to a receiver R, who are part of a distributed synchronous network, modeled as an arbitrary directed graph. Some of the intermediate nodes between S and R can be under the control of an adversary having unbounded computing power. Desmedt and Wang [4] have given the characterization of USMT in directed networks. However, in their model, the underlying network is abstracted as directed node disjoint paths (also called as wires/channels) between S and R, where the intermediate nodes are oblivious, message passing nodes and perform no other computation. In this work, we first show that the characterization of USMT given by Desmedt et.al [4] does not hold good for arbitrary directed networks, where the intermediate nodes can perform some computation, beside acting as message forwarding nodes. We then give the characterization of USMT in arbitrary directed networks, considering the entire network as a whole. As far our knowledge is concerned, this is the first ever characterization of USMT in arbitrary directed networks.

Consider a completely asynchronous network consisting of n parties where every two parties are connected by a private channel. An adversary At with unbounded computing power actively controls at most t = ([n/3] − 1) out of n parties in Byzantine fashion. In this setting, we say that π is a t-resilient, (1 − ε)-terminating Asynchronous Byzantine Agreement (ABA) protocol, if π satisfies all the properties of Byzantine Agreement (BA) in asynchronous settings tolerating At and terminates (i.e every honest party terminates π with probability at least (1 − ε). In this work, we present a new t-resilient, (1 − ε)-terminating ABA protocol which privately communicates O(Cn6 κ) bits and A-casts1 O(Cn6 κ) bits, where ε = 2−Ω(κ) and C is the expected running time of the protocol. Moreover, conditioned on the event that our ABA protocol terminates, it does so in constant expected time; i.e., C = O(1). Our ABA protocol is to be compared with the only known t-resilient, (1 − ε)-terminating ABA protocol of [5] in the same settings, which privately communicates O(Cn11 κ4) bits and A-casts O(Cn11 κ2 log(n)) bits, where ε = 2−Ω(κ) and C = O(1). So our ABA achieves a huge gain in communication complexity in comparison to the ABA of [5], while keeping all other properties in place. In another landmark work, in PODC 2008, Abraham et. al [1] proposed a t-resilient, 1-terminating (called as almost-surely terminating in [1]) ABA protocol which privately communicates O(Cn6 log n) bits and A-casts O(Cn6 log n) bits. But ABA protocol of Abraham et. al. takes polynomial (C = O(n2)) expected time to terminate. Hence the merits of our ABA protocol over the ABA of Abraham et. al. are: (i) For any κ < n2 log n, our ABA is better in terms of communication complexity (ii) conditioned on the event that our ABA protocol terminates, it does so in constant expected time (the constant is independent of n, t and κ), whereas ABA of Abraham et. al. takes polynomial expected time. Summing up, in a practical scenario where a faster and communication efficient ABA protocol is required, our ABA fits the bill better than ABA protocols of [5, 1].

No abstract available.

The recent attack on Apple iTunes Digital Rights Management [17] has brought to light the usefulness of proxy re-encryption schemes for Digital Rights Management. It is known that the use of proxy re-encryption would have prevented the attack in [17]. With this utility in mind and with the added requirement of non-repudiation, we propose the first ever signcryption scheme with proxy re-encryption that does not involve bilinear maps. Our scheme is called RSA-TBOS-PRE and is based on the RSA-TBOS signcryption scheme of Mao and Malone-Lee [7]. We adapt various models available in the literature concerning authenticity, unforgeability and non-repudiation and propose a signature non-repudiation model suitable for signcryption schemes with proxy re-encryption. We show the non-repudiability of our scheme in this model. We also introduce and define a new security notion of Weak-IND-CCA2, a slightly weakened adaptation of the IND-CCA2 security model for signcryption schemes and prove that RSA-TBOS-PRE is secure in this model. Our scheme is Weak-IND-CCA2 secure, unidirectional, extensible to multi-use and does not use bilinear maps. This represents significant progress towards solving the open problem of designing an IND-CCA2 secure, unidirectional, multi-use scheme not using bilinear maps proposed in [15][12].

We consider the rational secret sharing problem introduced by Halpern and Teague[3], 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. The impossibility of a deterministic protocol for rational secret sharing is proved by Halpern and Teague[3]. The impossibility result is based on the fact that a rational player always chooses a dominating strategy and so there is no incentive for a player to send his secret share. This rational behavior makes secret sharing impossible, but there is an interesting way by which we can force rational players to cooperate for achieving successful secret sharing. A rational player may be deterred from exploiting his short term advantage by the threat of punishment that reduces his long term payoff. This can be captured by the repeated interaction of players. Hence, we study rational secret sharing in a scenario, where players interact repeatedly in several rounds which enables the possibility of secret sharing among rational players. In our model, the dealer, instead of sending shares, forms polynomials of the secret shares and sends points on that polynomial (say subshares) to the players. The dealer constructs polynomials in a manner that the degrees of polynomials used differ by at most one and each player is not aware of the degree of polynomial employed for others. The players distribute shares in terms of subshares. We show a surprising result on the deterministic protocol for rational secret sharing problem in synchronous model. This is the first protocol that achieves rational secret sharing in a reasonable model to the best of our knowledge.

In this paper, we study the inherent tradeoff between the network connectivity, phase complexity and communication complexity of perfectly reliable message transmission (PRMT) problem in undirected synchronous network, tolerating a mixed adversary A(tb,tf), who has unbounded computing power and can corrupt tb and tf nodes in the network in Byzantine and fail-stop fashion respectively.

No abstract available.

Broadcast signcryption enables the broadcaster to simultaneously encrypt and sign the content meant for a specific set of users in a single logical step. It provides a very efficient solution to the dual problem of achieving confidentiality and authentication during content distribution. Among other alternatives, ID-based schemes are arguably the best suited for its implementation in wireless ad-hoc networks because of the unique advantage that they provide - any unique, publicly available parameter of a user can be his public key, which eliminates the need for a complex public key infrastructure. In 2004, Bohio et al. proposed an ID-based broadcast signcryption (IBBSC) scheme which achieves constant ciphertext size. They claim that their scheme provides both message authentication and confidentiality, but do not give formal proofs. In this paper, we demonstrate how a legitimate user of the scheme can forge a valid signcrypted ciphertext, as if generated by the broadcaster. Moreover, we show that their scheme is not IND-CCA secure. Following this, we propose a fix for Bohio et al.'s scheme, and formally prove its security under the strongest existing security models for broadcast signcryption (IND-CCA2 and EUF-CMA). While fixing the scheme, we also improve its efficiency by reducing the ciphertext size to two elements compared to three.

We introduce a data structure for program execution under a limited oblivious execution model. For fully oblivious execution along the lines of Goldreich and Ostrovsky [2], one transforms a given program into a one that has totally random looking execution, based on some cryptographic assumptions and the existence of secure hardware. Totally random memory access patterns do not respect the locality of reference in programs to which the programs generally owe their efficiency. We propose a model that limits the obliviousness so as to enable efficient execution of the program; here the adversary marks a variable and tries to produce a list of candidate locations where it may be stored in after $T$-steps ofexecution. We propose a randomized algorithm based on splay trees,and prove a lower bound on such lists.

No abstract available.

In the perfectly secure message transmission (PSMT) problem, two synchronized non-faulty players (or processors), the Sender S and the Receiver R are connected by n wires (each of which facilitates 2-way communication); S has a message, represented by a sequence oft elements from a finite field, that he wishes to send to R; after exchanging messages in phases R should correctly obtain S 's message, while an adversary listening on and actively controlling any set of t (or less) wires should have no information about S 's message. Similarly, in the problem of perfect reliable message transmission (PRMT), the receiver R should correctly obtain S's message, in spite of the adversary actively controlling any set oft (or less) wires.

We provide a complete characterization of directed networks in which probabilistic reliable communication is possible. We also outline a round optimal protocol for the same.

Consider a network in which a collection of source nodes maintain and periodically update data objects for a collection of sink nodes, each of which periodically accesses the data originating from some specified subset of the source nodes. We consider the task of efficiently relaying the dynamically changing data objects to the sinks from their sources of interest. Our focus is on the following "push-pull" approach for this data dissemination problem. Whenever a data object is updated, its source relays the update to a designated subset of nodes, its push set; similarly, whenever a sink requires an update, it propagates its query to a designated subset of nodes, its pull set. The push and pull sets need to be chosen such that every pull set of a sink intersects the push sets of all its sources of interest. We study the problem of choosing push sets and pull sets to minimize total global communication while satisfying all communication requirements.We formulate and study several variants of the above data dissemination problem, that take into account different paradigms for routing between sources (resp., sinks) and their push sets (resp., pull sets) -- multicast, unicast, and controlled broadcast -- as well as the aggregability of the data objects. Under the multicast model, we present an optimal polynomial time algorithm for tree networks, which yields a randomized O(log n)-approximation algorithm for n-node general networks, for which the problem is hard to approximate within a constant factor. Under the unicast model, we present a randomized O(log n)-approximation algorithm for non-metric costs and a matching hardness result. For metric costs, we present an O(1)-approximation and matching hardness result for the case where the interests of any two sinks are either disjoint or identical. Finally, under the controlled broadcast model, we present optimal polynomial-time algorithms.While our optimization problems have been formulated in the context of data communication in networks, our problems also have applications to network design and multicommodity facility location and are of independent interest.

No abstract available.

Consider a synchronous network of n players, each with a local input. The goal of distributed consensus is to globally agree on one of the valid inputs even if some non-trivial subset of the players are faulty. By valid input, we mean the input of any non-faulty player. Extant results in Byzantine agreement literature capture the behaviour of faulty players in an "all-or-nothing" fashion. For instance, a (Byzantine) faulty player is completely unconstrained and could behave differently with different players. This leads to a gross underestimation of the achievable fault-tolerance. In this work, we propose a fault-model that considerably improves the estimation of fault-tolerance and helps capture real-life scenarios better. For instance, if two (honest) players were part of the same LAN (which is essentially a broadcast network), it is impossible for a external faulty player to behave differently with these two players (though the faulty player may behave with "equal" malice with both these players!). Among our results, we introduce the sectional fault-model that is more general and can capture practical scenarios not captured by any extant model. We provide a complete characterization of the tolerable faults and present efficient protocols to achieve consensus. We remark that the results of this paper strictly generalize the extant characterizations of fault-tolerance. For example, consider a network of four players P1, P2, P3 and P4, under the corrupting influence of a Byzantine adversary given by the adversary structure A = {(P1, P2), (P2, P3), (P4)}. Agreement is impossible in such a scenario, since the three sets from A cover the player set. However, it would be evident from our results that consensus in the above scenario was indeed possible if (and only if) the players P1, P3 and P4 belonged to a single LAN in the network!

No abstract available.

We study the interplay of network connectivity and perfectly secure message transmission under the corrupting influence of generalized Byzantine adversaries. It is known that in the threshold adversary model, where the Byzantine adversary can corrupt upto any t among the n players (nodes), perfectly secure communication among any pair of players is possible if and only if the underlying synchronous network is (2t + 1)-connected. Strictly generalizing these results to the non-threshold setting, we show that perfectly secure communication among any pair of players is possible if and only if the union of no two sets in the adversary structure is a vertex cutset of the synchronous network. The computation and communication complexities of the transmission protocol are polynomial in the size of the network and the maximal basis of the adversary structure.

Given a set S of n points in R/sup D/, D/spl ges/2. Each point p/spl isin/S is assigned a color c(p) chosen from a fixed color set. The All-Nearest-Foreign-Neighbors Problem (ANFNP) is to find for each point p/spl isin/S its nearest foreign neighbors, i.e. the set of all points in S/{p} that are closest to p among the points in S with a color different from c(p). We introduce the Well Separated Color Decomposition (WSCD) which gives an optimal O(log n) parallel algorithm to solve the AMFNP, for fixed dimension D/spl ges/2 and fixed L/sup t/-metric d/sub t/, 1/spl les/t/spl les//spl infin/. The WSCD is based upon the Well Separated Pair Decomposition (Callahan et al., 1992). The ANFNP finds extensive applications in VLSI design and verification for two dimensions, and in traffic-control systems and Geographic Information Systems for D>2 dimensions. To the best of our knowledge, this is the only known optimal parallel algorithm for the ANFNP.

Given a biconnected graph G with n vertices, m edges and a vertex r, the centering of a spanning tree problem asks for a spanning tree T of G with the given vertex r as center of T. In this paper we present an O(m) message complexity and O(n) time complexity distributed algorithm for centering a spanning tree of a biconnected graph.

Abstract Given an undirected graph, The feedback vertex set problem is to find a set of vertices of minimum cardinality such that removing the vertices in this set makes the graph acyclic. This problem is known to be NP‐hard on general graphs. An O ( n 6 ) algorithm for this problem on permutation graphs is known. in this paper, we give an O ( n 4 ) algorithm for this problem on cocomparability graphs. Our result improves the time complexity of the algorithm and enlarges the class of graphs on which this problem is polynomial time‐solvable.

The treewidth of a graph is one of the most important graph-theoretic parameters from the algorithmic point of view. However, computing the treewidth and constructing a corresponding tree-decomposition for a general graph is NP-complete. This paper presents an algorithm for computing the treewidth and constructing a corresponding tree-decomposition for circular-arc graphs in $O( n^3 )$ time.

Abstract We present an O(n2) time‐optimal algorithm for solving the unweighted all‐pair shortest path problem on interval graphs, an important subclass of perfect graphs. An interesting structure called the neighborhood tree is studied and used in the algorithm. This tree is formed by identifying the successive neighborhoods of the vertex labeled last in the graph according to the IG‐ordering.