CryptoDB

C. Pandu Rangan

Publications

Year
Venue
Title
2015
JOFC
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2010
EPRINT
Recently, a certificateless signcryption scheme in the standard model was proposed by Liu et al. in \cite{LiuHZM10}. Another certificateless signcryption scheme in the standard model was proposed by Xie et al. in \cite{WZ09}. Here, we show that the scheme in \cite{LiuHZM10} and \cite{WZ09} are not secure against Type-I adversary.
2010
EPRINT
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 veri fer 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.
2010
ASIACRYPT
2010
EPRINT
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 \geq 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 secret for any d, where t \leq d \leq 2t. This is the first optimally resilient, perfectly secure AVSS of its kind in the literature. Specifically, our AVSS can generate d-sharing of \ell \geq 1 secrets from F concurrently, with a communication cost of O(\ell n^2 \log{|F|}) bits, where F is a finite field. Communication complexity wise, the best known optimally resilient, perfectly secure AVSS is reported in [BH07]. The protocol of [BH07] can generate t-sharing of \ell secrets concurrently, with the same communication complexity as our AVSS. However, the AVSS of [BH07] and [BCG93] (the only known optimally resilient perfectly secure AVSS, other than [BH07]) does not generate d-sharing, for any d > t. Interpreting in a different way, we may also say that our AVSS shares \ell(d+1 -t) secrets simultaneously with a communication cost of O(\ell n^2 \log{|F|}) 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 O(n \log{|F|}) bits. This is a clear improvement over the AVSS of [BH07] whose amortized cost of sharing a single secret is O(n^2 \log{|F|}) bits. As an interesting application of our AVSS, we propose a new optimally resilient, perfectly secure Asynchronous Multiparty Computation (AMPC) protocol that communicates O(n^2 \log|F|) bits per multiplication gate. The best known optimally resilient perfectly secure AMPC is due to [BH07], which communicates O(n^3 \log|F|) bits per multiplication gate. Thus our AMPC improves the communication complexity of the best known AMPC of [BH07] by a factor of \Omega(n).
2010
EPRINT
Consider the situation where a low power device with limited computational power has to perform cryptographic operation in order to do secure communication to the base station where the computational power is not limited. The most obvious way is to split each and every cryptographic operations into resource consuming, heavy operations (which are performed when the device is idle) and the fast light weight operations (which are executed on the fly). This concept is called online/offline cryptography. In this paper, we show the security weakness of an identity based online offline encryption scheme proposed in ACNS 09 by Liu et al. \cite{LiuZ09}. The scheme in \cite{LiuZ09} is the first identity based online offline encryption scheme in the random oracle model, in which the message and recipient are not known during the offline phase. We show that this scheme is not CCA secure. We show the weakness in the security proof of CCA secure online/offline encryption system proposed by Chow et al. in \cite{Chow10}. We propose a new provably secure identity based online offline encryption scheme in which the message and receiver are not known during the offline phase. Since all the CCA secure identity based online/offline encryption schemes are shown to have weakness, ours is the first provably secure scheme with the aforementioned properties.
2010
EPRINT
A common problem in many markets is that competing firms cannot plan joint business strategies which are socially beneficial, as each firm has its own preferable business strategy which would yield higher profits for it and lower profits for the others. The solution to this problem becomes complex because each firm need not stick to its commitment to follow the pre-designated strategy. Game theory suggests to us a way to enforce this commitment, as when every player chooses his actions according to his observation of the value of a common public signal and, assuming that the others do not deviate, no player is willing to deviate from his recommended strategy. The players do not deviate from their recommended strategy as playing them would yield them a much higher expected pay-off than playing individually. The common public channel can be a trusted external mediator which may send each player his recommended strategy. This mediator can be simulated by a cryptographic protocol, which all the players agree to implement. This problem of suggesting the protocol is known as the \textit{Correlated Element Selection Problem}. The first two-player protocol was proposed by Dodis et. al\cite{dhr00} in Crypto 2000. The extension of the two-player protocol to an $n$-player protocol is highly prone to collusions, as two firms can collude and cheat the rest of the firms. The main contribution of the paper is the first $n$-player collusion free protocol for the \textit{correlated element selection problem} that does not use hardware primitives. We assume that players are honest but curious.
2010
EPRINT
Signcryption as a single cryptographic primitive offers both confidentiality and authentication simultaneously. Generally in signcryption schemes, the message is hidden and thus the validity of the ciphertext can be verified only after unsigncrypting the ciphertext. Thus, a third party will not be able to verify whether the ciphertext is valid or not. Signcryption schemes that allow any user to verify the validity of the ciphertext without the knowledge of the message are called public verifiable signcryption schemes. Third Party verifiable signcryption schemes allow the receiver to convince a third party, by providing some additional information along with the signcryption other than his private key with/without exposing the message. In this paper, we show the security weaknesses in three existing schemes \cite{BaoD98}, \cite{TsoOO08} and \cite{ChowYHC03}. The schemes in \cite{BaoD98} and \cite{TsoOO08} are in the Public Key Infrastructure (PKI) setting and the scheme in \cite{ChowYHC03} is in the identity based setting. More specifically, \cite{TsoOO08} is based on elliptic curve digital signature algorithm (ECDSA). We also, provide a new identity based signcryption scheme that provides public verifiability and third party verification. We formally prove the security of the newly proposed scheme in the random oracle model.
2010
EPRINT
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.
2010
EPRINT
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.
2010
EPRINT
Online/Offline signcryption is a cryptographic primitive where the signcryption process is divided into two phases - online and offline phase. Most of the computations are carried out offline (where the message and the receiver identity are unavailable). The online phase does not require any heavy computations like pairing, multiplication on elliptic curves and is very efficient. To the best of our knowledge there exists three online/offline signcryption schemes in the literature : we propose various attacks on all the existing schemes. Then, we give the first efficient and provably secure identity based online/offline signcryption scheme. We formally prove the security of the new scheme in the random oracle model \cite{BellareR93}. The main advantage of the new scheme is, it does not require the knowledge of message or receiver during the offline phase. This property is very useful since it is not required to pre-compute offline signcryption for different receivers based on the anticipated receivers during the offline phase. Hence, any value generated during the offline phase can be used during the online phase to signcrypt the message to a receiver during the online phase. This helps in reducing the number of values stored during the offline phase. To the best of our knowledge, the scheme in this paper is the first provably secure scheme with this property.
2010
EPRINT
Certificateless cryptography, introduced by Al-Riyami and Paterson eliminates the key escrow problem inherent in identity based cryptosystem. In this paper, we present two novel and completely different RSA based adaptive chosen ciphertext secure (CCA2) certificateless encryption schemes. The new schemes are efficient when compared to other existing certificatless encryption schemes that are based on the costly bilinear pairing operation and are quite comparable with the certificateless encryption scheme based on multiplicative groups (without bilinear pairing) by Sun et al. \cite{SZB07} and the RSA based CPA secure certificateless encryption scheme by Lai et al. \cite{LDLK09}. We consider a slightly stronger security model than the ones considered in \cite{LDLK09} and \cite{SZB07} to prove the security of our schemes.
2010
EPRINT
An identity based signature allows users to sign their documents using their private keys and the signature can be verified by any user by using the identity of the signer and public parameters of the system. This allows secure communication between the users without any exchange of certificates. An aggregate signature scheme is a digital signature scheme which allows aggregation of different signatures by different users on different messages. An aggregate signature on $n$ messages $m_{i}$ by $n$ users $U_{i}$ convinces the verifier that each user $U_{i}$ has signed the corresponding message $m_{i}$. The primary objective of the aggregate signature scheme is to achieve both computational and communication efficiency. Here we discuss two identity based aggregate signature schemes. The first aggregate scheme IBAS-1 uses a variation of light weight Schnorr based signature. IBAS-1 does not involve any pairing operations in signature verification. IBAS-1 is computationally efficient since it avoids the costlier operation in elliptic curve groups(pairings). Also because of the light weight property of IBAS-1, it is much suitable for practice. The second aggregate signature scheme IBAS-2, which also has Schnorr type key construct, achieves full aggregation of signatures without agreeing on common randomness and without having any kind of interaction among all the signers. IBAS-2 achieves communication efficiency. But the computational complexity of IBAS-2 is higher than the IBAS-1 because it involves bilinear pairing.
2009
CRYPTO
2009
EPRINT
Secure multiparty computation (MPC) allows a set of $n$ parties to securely compute an agreed function, even if up to $t$ parties are under the control of an adversary. In this paper, we propose a new Asynchronous secure multiparty computation (AMPC) protocol that provides information theoretic security with $n = 4t+1$, where $t$ out of $n$ parties can be under the influence of a Byzantine (active) adversary ${\cal A}_t$ having unbounded computing power. Our protocol communicates O(n^2 \log|{\mathbb F}|) bits per multiplication and involves a negligible error probability of $2^{-\Omega(\kappa)}$, where $\kappa$ is the error parameter and ${\mathbb F}$ is the field over which the computation is carried out. The best known information theoretically secure AMPC with $n=4t+1$ communicates O(n^3 \log|{\mathbb F}|) bits per multiplication and does not involve any error probability in computation. Though a negligible error probability is involved, our AMPC protocol provides the best communication complexity among all the known AMPC protocols providing information theoretic security. Moreover, the communication complexity of our AMPC is same as the communication complexity of the best known AMPC protocol with cryptographic assumptions. As a tool for our AMPC protocol, we propose a new method of efficiently generating (t,2t)-sharing of multiple secrets concurrently in asynchronous setting, which is of independent interest.
2008
EPRINT
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. In ACISP 2007 Srinathan et. al. has proved that the connectivity requirement for PSMT protocols is same for both static and mobile adversary thus showing that mobility of the adversary has no effect on the possibility of PSMT (also PRMT) protocols. Similarly in CRYPTO 2004, Srinathan et. al. has shown that the lower bound on the communication complexity of any multiphase PSMT protocol is same for static and mobile adversary. The authors have also designed a $O(t)$ phase (A phase is a send from S to R or R to S or both) protocol satisfying this bound where $t$ is the maximum number of nodes corrupted by the Byzantine adversary. In this work, we design a three phase bit optimal PSMT protocol using a novel technique, whose communication complexity matches the lower bound proved in CRYPTO 2004 and thus significantly reducing the number of phases from $O(t)$ to three. Further using our novel technique, 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 optimal PRMT and PSMT protocols against mobile Byzantine adversary. We also characterize PSMT protocols in directed networks tolerating mobile adversary. All the existing PRMT and PSMT protocols abstracts the paths between S and R as wires, neglecting the intermediate nodes in the paths. However, this causes significant over estimation in the communication complexity as well as round complexity (Round is different from phase. Round is a send from one node to its immediate neighbor in the network} of protocols. Here, we consider the underlying paths as a whole instead of abstracting them as wires and derive a tight bound on the number of rounds required to achieve reliable communication from S to R tolerating a mobile adversary with arbitrary roaming speed (By roaming speed we mean the speed with which the adversary changes the set of corrupted node). We show how our constant phase PRMT and PSMT protocols can be easily adapted to design round optimal and bit optimal PRMT and PSMT protocols provided the network is given as a collection of vertex disjoint paths.
2008
EPRINT
In this work we focus on two basic secure distributed computation tasks- Probabilistic Weak Secret Sharing (PWSS) and Probabilistic Verifiable Secret Sharing (PVSS). PVSS allows a dealer to share a secret among several players in a way that would later allow a unique reconstruction of the secret with negligible error probability. PWSS is slightly weaker version of PVSS where the dealer can choose not to disclose his secret later. Both of them are well-studied problems. While PVSS is used as a building block in every general probabilistic secure multiparty computation, PWSS can be used as a building block for PVSS protocols. Both these problems can be parameterized by the number of players ($n$) and the fault tolerance threshold ($t$) which bounds the total number of malicious (Byzantine) players having {\it unbounded computing power}. We focus on the standard {\it secure channel model}, where all players have access to secure point-to-point channels and a common broadcast medium. We show the following for PVSS: (a) 1-round PVSS is possible iff $t=1$ and $n>3$ (b) 2-round PVSS is possible if $n>3t$ (c) 4-round PVSS is possible if $n>2t$. For the PWSS we show the following: (a) 1-round PWSS is possible iff $n>3t$ and (b) 3-round PWSS is possible if $n>2t$. All our protocols are {\it efficient}. Comparing our results with the existing trade-off results for perfect (zero error probability) VSS and WSS, we find that probabilistically relaxing the conditions of VSS/WSS helps to increase fault tolerance significantly.
2008
EPRINT
We study the interplay of network connectivity and the issues related to the possibility, feasibility and optimality for {\it unconditionally reliable message transmission} (URMT) and {\it unconditionally secure message transmission} (USMT) in an undirected {\it synchronous} network, under the influence of an adaptive {\it mixed} adversary ${\mathcal A}_{(t_b,t_o,t_f,t_p)}$, who has {\it unbounded computing power} and can corrupt $t_b$, $t_o$, $t_f$ and $t_p$ nodes in the network in Byzantine, {\it omission}, {\it fail-stop} and passive fashion respectively. In URMT problem, a sender {\bf S} and a receiver {\bf R} are part of a distributed network, where {\bf S} and {\bf R} are connected by intermediate nodes, of which at most $t_b, t_o, t_f$ and $t_p$ nodes can be under the control of ${\mathcal A}_{(t_b,t_o,t_f,t_p)}$. {\bf S} wants to send a message $m$ which is a sequence of $\ell$ field elements from a finite field ${\mathbb F}$ to {\bf R}. The challenge is to design a protocol, such that after interacting in phases\footnote{A phase is a send from {\bf S} to {\bf R} or viceversa.} as per the protocol, {\bf R} should output $m' = m$ with probability at least $1 - \delta$, where $0 < \delta < \frac{1}{2}$. Moreover, this should happen, irrespective of the adversary strategy of ${\mathcal A}_{(t_b,t_o,t_f,t_p)}$. The USMT problem has an additional requirement that ${\mathcal A}_{(t_b,t_o,t_f,t_p)}$ should not know anything about $m$ in {\it information theoretic} sense. In this paper, we answer the following in context of URMT and USMT: (a) {\sc Possibility:} when is a protocol possible in a given network? (b) {\sc Feasibility:} Once the existence of a protocol is ensured then does there exists a polynomial time protocol on the given network? (c) {\sc Optimality: } Given a message of specific length, what is the minimum communication complexity (lower bound) needed by any protocol to transmit the message and how to design a protocol whose total communication complexity matches the lower bound on the communication complexity? Finally we also show that {\it allowing a negligible error probability significantly helps in the possibility, feasibility and optimality of both reliable and secure message transmission protocols.} To design our protocols, we propose several new techniques which are of independent interest.
2008
EPRINT
Signcryption is a cryptographic primitive that aims at providing confidentiality and authentication simultaneously. Recently in May 2008, a scheme for identity based threshold signcryption was proposed by Fagen Li and Yong Yu. They have proved the confidentiality of their scheme and have also claimed the unforgeability without providing satisfactory proof. In this paper, we show that in their signcryption scheme the secret key of the sender is exposed(total break) to the clerk during sincryption and hence insecure in the presence of malicious clerks. Further, we propose a corrected version of the scheme and formally prove its security under the existing security model for signcryption.
2008
EPRINT
In this work, we initiate the study of round complexity of {\it unconditionally secure weak secret sharing} (UWSS) and {\it unconditionally secure verifiable secret sharing} (UVSS) \footnote{In the literature, these problems are also called as statistical WSS and statistical VSS \cite{GennaroVSSSTOC01} respectively.} in the presence of an {\it all powerful} $t$-active adversary. Specifically, we show the following for UVSS: (a) 1-round UVSS is possible iff $t=1$ and $n>3$, (b) 2-round UVSS is possible if $n>3t$ and (c) 5-round {\it efficient} UVSS is possible if $n>2t$. For UWSS we show the following: (a) 1-round UWSS is possible iff $n>3t$ and (b) 3-round UWSS is possible if $n>2t$. Comparing our results with existing results for trade-off between fault tolerance and round complexity of perfect (zero error) VSS and WSS \cite{GennaroVSSSTOC01,FitziVSSTCC06,KatzVSSICALP2008}, we find that probabilistically relaxing the conditions of VSS/WSS helps to increase fault tolerance significantly.
2008
EPRINT
2008
EPRINT
In ATC 2007, an identity-based signcryption scheme for multiple receivers was proposed by Yu et al. They prove confidentiality of their scheme and also claim unforgeability without any proof. In this paper, we show that their signcryption scheme is insecure by demonstrating a universal forgeability attack - anyone can generate a valid signcrypted ciphertext on any message on behalf of any legal user for any set of legal receivers without knowing the secret keys of the legal users. Further, we propose a corrected version of their scheme and formally prove its security (confidentiality and unforgeability) under the existing security model for signcryption. We also analyze the efficiency of the corrected scheme by comparing it with existing signcryption schemes for multiple receivers.
2008
EPRINT
Multi-Power RSA [1] is a fast variant of RSA [2] with a small decryption time, making it attractive for implementation on lightweight cryptographic devices such as smart cards. Hensel Lifting is a key component in the implementation of fast Multi-Power RSA Decryption. However, it is found that a naive implementation of this algorithm is vulnerable to a host of side channel attacks, some of them powerful enough to entirely break the cryptosystem by providing a factorisation of the public modulus $N$. We propose here a secure (under reasonable assumptions) implementation of the Hensel Lifting algorithm. We then use this algorithm to obtain a secure implementation of Multi-Power RSA Decryption.
2008
EPRINT
In the problem of perfectly reliable message transmission} (PRMT), a sender {\bf S} and a receiver {\bf R} are connected by $n$ bidirectional synchronous channels. A mixed adversary ${\mathcal A}_{(t_b,t_f,t_p)}$ with {\it infinite computing power} controls $t_b, t_f$ and $t_p$ channels in Byzantine, fail-stop and passive fashion respectively. Inspite of the presence of ${\mathcal A}_{(t_b,t_f,t_p)}$, {\bf S} wants to reliably send a message $m$ to {\bf R}, using some protocol, without sharing any key with {\bf R} beforehand. After interacting in phases\footnote{A phase is a send from {\bf S} to {\bf R} or vice-versa} as per the protocol, {\bf R} should output $m' = m$, without any error. In the problem of {\it perfectly secure message transmission} (PSMT), there is an additional constraint that ${\mathcal A}_{(t_b,t_f,t_p)}$ should not know {\it any} information about $m$ in {\it information theoretic} sense. The adversary can be either static\footnote{A static adversary corrupts the same set of channels in each phase of the protocol. The choice of the channel to corrupt is decided before the beginning of the protocol.} or mobile.\footnote{A mobile adversary can corrupt different set of channels in different phases of the protocol.} The {\it connectivity requirement}, {\it phase complexity} and {\it communication complexity} are three important parameters of any interactive PRMT/PSMT protocol and are well studied in the literature when the channels are controlled by a static/mobile Byzantine adversary. However, when the channels are controlled by mixed adversary ${\mathcal A}_{(t_b,t_f,t_p)}$ , we encounter several surprising consequences. In this paper, we study the problem of PRMT and PSMT tolerating "static/mobile mixed adversary". 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 mobile mixed adversary is more than its static mixed counterpart. This is interesting because against only "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, mobile mixed adversary is more powerful than its static counterpart. As our second contribution, we design a four phase communication optimal PSMT protocol tolerating "static mixed adversary". Comparing this with the existing three phase communication optimal PSMT protocol against "static Byzantine adversary", we find that additional one phase is enough to design communication optimal protocol against 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 in PSMT. To show that our bound is tight, we also present a worst case nine phase communication optimal PSMT protocol tolerating 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.
2008
EPRINT
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. [4] 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 in [4].
2008
EPRINT
In this paper, we re-visit the problem of {\it unconditionally reliable message transmission} (URMT) and {\it unconditionally secure message transmission} (USMT) in a {\it directed network} under the presence of a threshold adaptive Byzantine adversary, having {\it unbounded computing power}. Desmedt et.al \cite{Desmedt} have given the necessary and sufficient condition for the existence of URMT and USMT protocols in directed networks. Though their protocols are efficient, they are not communication optimal. In this paper, we prove for the first time the lower bound on the communication complexity of URMT and USMT protocols in directed networks. Moreover, we show that our bounds are tight by giving efficient communication optimal URMT and USMT protocols, whose communication complexity satisfies our proven lower bounds.
2008
EPRINT
Confidentiality and authenticity are two of the most fundamental problems in cryptography. Many applications require both confidentiality and authenticity, and hence an efficient way to get both together was very desirable. In 1997, Zheng proposed the notion of signcryption'', a single primitive which provides both confidentiality and authenticity in a way that's more efficient than signing and encrypting separately. Proxy re-encryption is a primitive that allows a semi-trusted entity called the proxy'' to convert ciphertexts addressed to a delegator'' to those that can be decrypted by a delegatee'', by using some special information given by the delegator, called the rekey''. In this work, we propose the notion of signcryption with proxy re-encryption (SCPRE), and motivate the same. We define security models for SCPRE, and also propose a concrete unidirectional, non-interactive identity-based SCPRE construction. We also provide complete proofs of security for the scheme in the security models defined. We finally provide directions for further research in this area.
2008
EPRINT
Group Key Management (GKM) solves the problem of efficiently establishing and managing secure communication in dynamic groups. Many GKM schemes that have been proposed so far have been broken, as they cite ambiguous arguments and lack formal proofs. In fact, no concrete framework and security model for GKM exists in literature. This paper addresses this serious problem by providing firm foundations for Group Key Management. We provide a generalized framework for centralized GKM along with a formal security model and strong definitions for the security properties that dynamic groups demand. We also show a generic construction of a centralized GKM scheme from any given multi-receiver ID-based Key Encapsulation Mechanism (mID-KEM). By doing so, we unify two concepts that are significantly different in terms of what they achieve. Our construction is simple and efficient. We prove that the resulting GKM inherits the security of the underlying mID-KEM up to CCA security. We also illustrate our general conversion using the mID-KEM proposed in 2007 by Delerablée.
2008
EPRINT
The recent attack on Apple iTunes Digital Rights Management \cite{SJ05} 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 \cite{SJ05}. 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 \cite{MM03}. 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 \cite{CH07}\cite{SXC08}.
2008
EPRINT
This paper puts forward new efficient constructions for Multi-Receiver Signcryption in the Identity-based setting. We consider a scenario where a user wants to securely send a message to a dynamically changing subset of the receivers in such a way that non-members of the of this subset cannot learn the message. The obvious solution is to transmit an individually signcrypted message to every member of the subset. This requires a very long transmission (the number of receivers times the length of the message) and high computation cost. Another simple solution is to provide every possible subset of receivers with a key. This requires every user to store a huge number of keys. In this case, the storage efficiency is compromised. The goal of this paper is to provide solutions which are efficient in all three measures i.e. transmission length, storage of keys and computation at both ends. We propose three new schemes that achieve both confidentiality and authenticity simultaneously in this setting and are the most efficient schemes to date, in the parameters described above. The first construction achieves optimal computational and storage cost. The second construction achieves much lesser transmission length than the previous scheme (down to a ratio of one-third), while still maintaining optimal storage cost. The third scheme breaks the barrier of ciphertext length of linear order in the number of receivers, and achieves constant sized ciphertext, independent of the size of the receiver set. This is the first Multi-receiver Signcryption scheme to do so. We support all three schemes with security proofs under a precisely defined formal security model.
2008
EPRINT
We study the problem of unconditionally reliable message transmission (URMT), where two non-faulty players, the sender S and the 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-\delta)$ for arbitrarily small $\delta > 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. Working out a direct characterization of URMT over directed hypergraphs tolerating threshold mixed adversary is highly un-intuitive. So we first propose a novel technique, which takes as input a directed hypergraph and a threshold mixed adversary on that hypergraph and outputs a corresponding digraph, along with a non-threshold mixed adversary, such that URMT over the hypergraph tolerating the threshold mixed adversary is possible iff a special type of URMT is possible over the obtained digraph, tolerating the corresponding non-threshold mixed adversary}. Thus characterization of URMT over directed hypergraph tolerating threshold mixed adversary reduces to characterizing special type of a URMT over arbitrary digraph tolerating non-threshold mixed adversary. We then characterize URMT in arbitrary digraphs tolerating non-threshold mixed adversary and modify it to obtain the characterization for special type of URMT over digraphs tolerating non-threshold mixed adversary. This completes the characterization of URMT over the original hypergraph. Surprisingly, our results indicate that even passive corruption, in collusion with active faults, substantially affects the reliability of URMT protocols! This is interesting because it is a general belief that passive corruption (eavesdropping) does not affect reliable communication.
2008
EPRINT
We propose an efficient information theoretic 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 ${\cal A}_t$ having unbounded computing power. Our protocol communicates O(n^5 \kappa)$bits per multiplication and involves a negligible error probability of$2^{- O(\kappa)}$, where$\kappa$is the error parameter. As far as our knowledge is concerned, the only known AMPC protocol with$n = 3t+1$providing information theoretic security with negligible error probability is due to \cite{BenOrPODC94AsynchronousMPC}, which communicates$\Omega(n^{11} \kappa^4)$bits and A-Casts$\Omega(n^{11} \kappa^2 \log(n))$bits per multiplication. Here A-Cast is an asynchronous broadcast primitive, which allows a party to send the same information to all other parties identically. Thus our AMPC protocol shows significant improvement in communication complexity over the AMPC protocol of \cite{BenOrPODC94AsynchronousMPC}. As a tool for our AMPC protocol, we introduce a new asynchronous primitive called Asynchronous Complete Verifiable Secret Sharing (ACVSS), which is first of its kind and is of independent interest. For designing our ACVSS, we employ a new asynchronous verifiable secret sharing (AVSS) protocol which is better than all known communication-efficient AVSS protocols with$n=3t+1$. 2008 EPRINT In this paper, we re-visit the problem of {\it perfectly reliable message transmission} (PRMT) and {\it perfectly secure message transmission}(PSMT) in a {\it directed network} under the presence of a threshold adaptive Byzantine adversary, having {\it unbounded computing power}. Desmedt et.al have given the necessary and sufficient condition for the existence of PSMT protocols in directed networks. In this paper, we first show that the necessary and sufficient condition (characterization) given by Desmedt et.al does not hold for two phase\footnote{A phase is a send from sender to receiver or vice-versa.} PSMT protocols. Hence we provide a different necessary and sufficient condition for two phase PSMT in directed networks. We also derive the lower bound on communication complexity of two phase PSMT and show that our lower bound is {\it asymptotically tight} by designing a two phase PSMT protocol whose communication complexity satisfies the lower bound. Though the characterization for three or more phase PSMT is resolved by the result of Desmedt et. al, the lower bound on communication complexity for the same has not been investigated yet. Here we derive the lower bound on the communication complexity of three or more phase PSMT in directed networks and show that our lower bound is {\it asymptotically tight} by designing {\it communication optimal} PSMT protocols. Finally, we characterize the class of directed networks over which communication optimal PRMT or PRMT with constant factor overhead is possible. By communication optimal PRMT or PRMT with constant factor overhead, we mean that the PRMT protocol is able to send$\ell$field elements by communicating$O(\ell)$field elements from a finite field$\mathbb F$. To design our protocols, we use several techniques, which are of independent interest. 2008 EPRINT In this paper, we re-visit the problem of {\it unconditionally secure message transmission} (USMT) from a sender {\bf S} to a receiver {\bf R}, who are part of a distributed synchronous network, modeled as an {\it arbitrary} directed graph. Some of the intermediate nodes between {\bf S} and {\bf R} can be under the control of the adversary having {\it unbounded} computing power. Desmedt and Wang \cite{Desmedt} 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 {\bf S} and {\bf 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 \cite{Desmedt} does not hold good for {\it arbitrary} directed networks, where the intermediate nodes perform some computation, beside acting as message forwarding nodes. We then give the {\it true} characterization of USMT in arbitrary directed networks. As far our knowledge is concerned, this is the first ever {\it true} characterization of USMT in arbitrary directed networks. 2008 EPRINT Consider a completely asynchronous network consisting of n parties where every two parties are connected by a private channel. An adversary A_t with unbounded computing power actively controls at most t < n / 3 parties in Byzantine fashion. In these settings, we say that \pi is a$t$-resilient,$(1-\epsilon)$-terminating Asynchronous Byzantine Agreement (ABA) protocol, if$\pi$satisfies all the properties of Byzantine Agreement (BA) in asynchronous settings tolerating A_t and terminates (i.e every honest party terminates$\pi$) with probability at least$(1-\epsilon)$. In this work, we present a new$t$-resilient,$(1-\epsilon)$-terminating ABA protocol which privately communicates O(C n^{5} \kappa) bits and A-casts O(C n^{5} \kappa) bits, where$\epsilon = 2^{-O(\kappa)$and C is the expected running time of the protocol. Here A-Cast is a primitive in asynchronous world, allowing a party to send the same value to all the other parties. Hence A-Cast in asynchronous world is the parallel notion of broadcast in synchronous world. 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-\epsilon)$-terminating ABA protocol of \cite{CanettiSTOC93} in the same settings, which privately communicates O(C n^{11} \kappa^{4}) bits and A-casts O(C n^{11} \kappa^2 \log(n)) bits, where$\epsilon = 2^{-O(\kappa)} and C = O(1). So our ABA achieves a huge gain in communication complexity in comparison to the ABA of \cite{CanettiSTOC93}, while keeping all other properties in place. In another landmark work, in PODC 2008, Abraham et. al \cite{DolevAsynchronousBAPODC2008} proposed a $t$-resilient, $1$-terminating (called as almost-surely terminating in \cite{DolevAsynchronousBAPODC2008}) ABA protocol which communicates O(C n^{6} \log{n}) bits and A-casts O(C n^{6} \log{n}) bits. But ABA protocol of Abraham et. al. takes polynomial (C = O(n^2)) expected time to terminate. Hence the merits of our ABA protocol over the ABA of Abraham et. al. are: (i) For any \kappa < n^3 \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 \kappa), whereas ABA of Abraham et. al. takes polynomial expected time. However, it should be noted that our ABA is only $(1-\epsilon)$-terminating whereas ABA of Abraham et al. is almost-surely terminating. 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 \cite{CanettiSTOC93,DolevAsynchronousBAPODC2008}. For designing our ABA protocol, we present a novel and simple asynchronous verifiable secret sharing (AVSS) protocol which significantly improves the communication complexity of the only known AVSS protocol of \cite{CanettiSTOC93} in the same settings. We believe that our AVSS can be used in many other applications for improving communication complexity and hence is of independent interest.
2008
EPRINT
In this paper, we re-visit the problem of unconditionally secure multiparty set intersection in information theoretic model. Li et.al \cite{LiSetMPCACNS07} have proposed a protocol for $n$-party set intersection problem, which provides unconditional security when $t < \frac{n}{3}$ players are corrupted by an active adversary having {\it unbounded computing power}. Moreover, they have claimed that their protocol takes six rounds of communication and incurs a communication complexity of ${\cal O}(n^4m^2)$, where each player has a set of size $m$. However, we show that the round complexity and communication complexity of the protocol in \cite{LiSetMPCACNS07} is much more than what is claimed in \cite{LiSetMPCACNS07}. We then propose a {\it novel} unconditionally secure protocol for multiparty set intersection problem with $n > 3t$ players, which significantly improves the "actual" round and communication complexity (as shown in this paper) of the protocol given in \cite{LiSetMPCACNS07}. To design our protocol, we use several tools which are of independent interest.
2006
TCC
2004
CRYPTO
2002
ASIACRYPT

Asiacrypt 2008
PKC 2007
FSE 2004