Link-flooding attacks (LFAs) are a new type of distributed denial-of-service (DDoS) attacks that can substantially damage network connectivity. LFAs flows are seemingly legitimate at the origin. But their cumulative volume at critical links causes congestion. We propose RL-Shield, a reinforcement learning based defense system against LFAs. It mitigates LFAs and, at the same time, effectively forwards data traffic in the network. RL-Shield introduces a new detection algorithm for monitoring IP behaviors using the Dirichlet distribution and Bayesian statistics. It monitors the interplay of LFAs and traffic engineering and identifies source IPs that persistently react to re-routing events. The detection algorithm controls two reinforcement learning based routing algorithms that use a hop-by-hop technique to connect related node pairs.We evaluate RL-Shield on various network topologies by simulating several attack strategies. The simulation results demonstrate the effectiveness and high-accuracy of RL-Shield.

Modern botnets are progressively migrating to P2P network to resist against take-down attempts. In addition, new botnets use randomization in their behavior to evade detection. In this paper, we propose a new method for detecting stealthy P2P bots. We formulate the problem as a re-identification problem. This opens the possibility of powerful instantiations of detection algorithms to address the botnet detection problem. We also use a nontrivial feature selection technique to discover the best feature pairs for conducting comparison between two flows. We use real-world botnet data to evaluate the performance of Monsieur Poirot and compare it with existing flow-based algorithms. Monsieur Poirot is robust towards injection of noise in the communication patterns. The experimental results show that Monsieur Poirot is able to identify P2P bots with an average TPR of 98.65% and an average FPR of 0.21%.

An efficient protocol for establishing secret keys for neighboring nodes in a wireless network is presented in this paper. The security of the key generated by our protocol is based on the unpredictability of the noises in binary symmetric communication channels. The two nodes which try to establish a common secret key receive messages from a common source of random bit strings. Due to noises in the communication channel, the messages received by them, and most importantly the messages received by the eavesdropper, are not the same. We show that the two nodes can modify their messages in an efficient way to obtain a common string which contains enough uncertainty to the eavesdropper. Then, a secure universal hash function is applied to compute a secret key for extracting randomness from the common string. We prove that the probability for the eavesdropper to know the value of the key is negligible. One advantage of our proposed protocol is that the secret key rate is better than the known scheme in other models, such as the bounded storage model. Furthermore, our proposed protocol needs only to perform exclusive-or operations and compute hash values. Thus, it is a computationally light-weight protocol and suitable for devices with limited computing resources, such as sensors in sensor networks.

In cloud storage reliability management, a conflict occurs between the cloud storage provider (CSP) and users. The CSP considers the storage overhead as it adopts a replication mechanism to achieve data reliability. Users incur an auditing cost for verifying CSP’s reliability through remote data integrity checking. Both the CSP and users would like to spend a lower cost on the data reliability management. However, if one side decides to reduce his cost, such as, reducing stored copies for each datum, the data reliability would become lower. The opposite side would face a conflict that he has to increase his cost on the data reliability, such as, increasing auditing frequency. These conflicting situations may lead to an unsatisfied state of the data reliability if users and CSP arbitrarily make decisions according their own preferences. In this paper, we describe a game-theoretic analysis to design optimal strategies for users and the CSP. We present two cases of the user-CSP game: the strategic game and Bayesian game. We determine the Nash Equilibrium (NE) and Bayesian Nash Equilibrium (BNE) to get stable solutions for these games. In the numerical study, we use the pricing strategy adopted by Amazon S3 to explain our analysis. We analyze the effect of the parameter setting with replica number n, data sensitive level, and punishment on the NE and BNE. Our results show that if a user wants to store important data in the CSP, he should choose the [Formula: see text] strategy for [Formula: see text] in the mild punishment and [Formula: see text] in the severe punishment. According to these results, a user can determine whether to pay for auditing by the pricing tags, and the CSP can formulate appropriate policies for reliability of storage.

Abstract In cloud storage, a data owner can store his data in a cloud and authorize some users to access his data. Since the data are outsourced to the cloud, the authorized users should check the data to assure integrity. The data owner does not allow unauthorized users to check integrity of his data. There are many private and public integrity check schemes. Nevertheless, this paper concerns the verification key spread problem. Delegated integrity check deals with the verification key spread problem and provides effective management of verifiers. A data owner can delegate a verifier to check his data and revoke the right of the verifier later. The verifier cannot re-delegate his integrity check capability to someone else. Delegated integrity check guarantees that only the delegated verifier can check integrity of data. This paper provides the model of delegated integrity check, an application scenario of personal health records, and two delegated integrity check schemes for hierarchical cloud data. The first scheme allows a verifier to check data possession of a storage server. The second scheme allows a verifier to check data retrievability from a storage server. The schemes achieve proof unforgeability, proof indistinguishability and delegation key unforgeability in the random oracle model.

In the application of cloud storage, a user no longer possesses his files in his local depository. Thus, he is concerned about the security of the stored files. Data confidentiality and data robustness are the main security issues. For data confidentiality, the user can first encrypt files and then store the encrypted files in a cloud storage. For data robustness, there are two concerns: service failure, and service corruption. We are concerned about data robustness in cloud storage services. Lin and Tzeng proposed a secure erasure code-based storage system with multiple key servers recently. Their system supports a repair mechanism, where a new storage server can compute a new ciphertext from the ciphertexts obtained from the remaining storage servers. Their system considers data confidentiality in the cloud, and data robustness against storage server failure. In this paper, we propose an integrity check scheme for their system to enhance data robustness against storage server corruption, which returns tampered ciphertexts. With our integrity check scheme, their storage system can deal with not only the problem of storage server failure, but also the problem of storage server corruption. The challenging part of our work is to have homomorphic integrity tags. New integrity tags can be computed from old integrity tags by storage servers without involvement of the user's secret key or backup servers. We prove the security of our integrity check scheme formally, and establish the parameters for achieving an overwhelming probability of a successful data retrieval.

Cloud-based security services become popular in protection against security attacks for resource-constrained end-user devices. With abundant hardware at the cloud and strong support by security professionals, cloud-based security services can provide better protection than traditional security moni toring agents. However, security services usually involve the inspection of private system states or user behavior, which should not be disclosed to an untrusted entity, such as a cloud service provider. Maintaining end-user privacy and allowing security services to work on the cloud seem contradictory. In this paper, we present a framework for building privacy-preserving cloud-based security services. The framework consists of an architecture for building cloud-based security services and a technique, called private signature filtering, to preserve end-user privacy. The framework supports security monitoring signatures whose correspondence with end-user device queries can be established through conjunction of keywords and numeric value ranges. The framework also allows a trusted middle layer to do a part of the security monitoring computation for the end-user device to reduce the computation overhead on the end-user device. We implement two prototype systems for the cloud-based network intrusion service and the cloud-based malicious URL detection service, to verify effectiveness of our design. The experimental results show that the framework can indeed ensure end-user privacy with acceptable performance overhead in a practical cloud-based security service setting.

Data sharing is an important functionality in cloud storage. In this paper, we show how to securely, efficiently, and flexibly share data with others in cloud storage. We describe new public-key cryptosystems that produce constant-size ciphertexts such that efficient delegation of decryption rights for any set of ciphertexts are possible. The novelty is that one can aggregate any set of secret keys and make them as compact as a single key, but encompassing the power of all the keys being aggregated. In other words, the secret key holder can release a constant-size aggregate key for flexible choices of ciphertext set in cloud storage, but the other encrypted files outside the set remain confidential. This compact aggregate key can be conveniently sent to others or be stored in a smart card with very limited secure storage. We provide formal security analysis of our schemes in the standard model. We also describe other application of our schemes. In particular, our schemes give the first public-key patient-controlled encryption for flexible hierarchy, which was yet to be known.

With the increasing popularity of cloud computing, Hadoop has become a widely used open source cloud computing framework for large scale data processing. However, few studies have been done to enhance data confidentiality of Hadoop against storage servers. In this paper, we address the data confidentiality issue by integrating hybrid encryption schemes and the Hadoop distributed file system (HDFS). We propose and implement two integrations, HDFS-RSA and HDFS-Pairing, as extensions of HDFS. Experiments are conducted to demonstrate the performance overhead of HDFS-RSA and HDFS-Pairing. Our integrations provide alternatives toward achieving data confidentiality for Hadoop.

With the rapid development of the Internet, many commercial and network-based services, such as pay-TV and on-line games, have become popular. To control access to these services for legal members only, a common way is to use a cryptographic key to protect the communication and disclose the key only to the group of legal members. The group key management (GKM) is for a group manager to maintain a common cryptographic (group) key for a dynamic group of legal members through a network channel. A GKM scheme can also be used to provide communication privacy and transmitted message integrity. In this paper, we first demonstrate a collusion attack against Chen, et al.'s concrete RSA-based GKM scheme [1]. Then, we propose an efficient and provably-secure GKM scheme using the key derivation method. Our GKM scheme has some attractive features. Firstly, the proposed scheme are very efficient since the key derivation method uses simple keyed hash plus XOR operations. Secondly, the proposed scheme have an efficient rekey mechanism for a member who may become off-line and miss group key updates in his off-line period. Finally, the proposed scheme can be proved secure based on the pseudorandom function family assumption and one-way property of a hash function.

A cloud storage system, consisting of a collection of storage servers, provides long-term storage services over the Internet. Storing data in a third party's cloud system causes serious concern over data confidentiality. General encryption schemes protect data confidentiality, but also limit the functionality of the storage system because a few operations are supported over encrypted data. Constructing a secure storage system that supports multiple functions is challenging when the storage system is distributed and has no central authority. We propose a threshold proxy re-encryption scheme and integrate it with a decentralized erasure code such that a secure distributed storage system is formulated. The distributed storage system not only supports secure and robust data storage and retrieval, but also lets a user forward his data in the storage servers to another user without retrieving the data back. The main technical contribution is that the proxy re-encryption scheme supports encoding operations over encrypted messages as well as forwarding operations over encoded and encrypted messages. Our method fully integrates encrypting, encoding, and forwarding. We analyze and suggest suitable parameters for the number of copies of a message dispatched to storage servers and the number of storage servers queried by a key server. These parameters allow more flexible adjustment between the number of storage servers and robustness.

Pay-TV has become a popular subscribed-based service in recent years. To prevent unauthorized access from non-paid users over a broadcast channel, the TV server usually encrypts TV programs into ciphertexts such that only the legal members can decrypt them. The way of maintaining the common decryption key of a TV program to a dynamic subscription group of members is called the group key management. In this paper, we propose a secure and efficient tree-based group key management scheme that is very suitable for Pay-TV systems. In addition to possessing the advantages of the former tree-based scheme, such as O(log N) communication cost for each group key update and O(log N) secret keys for each member, our scheme has two distinct features, where N is the total number of members. (1) Each member only needs to decrypt one ciphertext or compute one hash value to get the group key from the rekey messages for each member leaving/joining. (2) To handle the key update for reconnected members who have missed the group key updates in his off-line period of time, the server only needs to store O(N) public tokens on the bulletin and each off-line member only needs O(log N) decryptions for getting the newest group key, which are independent of the number of group key updates. In Pay-TV systems, these features not only minimize the delay time for each group key update, but also let the system more practical even if the key update frequency is very high, such as, the Pay-Per-View TV service. Finally, we have a discussion of applying our GKM scheme to a multi-program service.

The group key management is for a group manager to maintain a consistent group key for a dynamic group of members through a broadcast channel. In this paper we propose a group key management scheme based on a meta proxy re-encryption (PRE) scheme. In particular, we propose an RSA-based PRE scheme with special properties. It is the first RSA-based PRE scheme for group key management and has the desired properties of uni-directionality and multi-hop. In our group key management scheme, each group member holds just one secret auxiliary key and logN public auxiliary keys. The size of rekey messages for each group key update remains O(logN). Additionally, our scheme has some distinct features. Firstly, the size of the key update history is a constant O(N) no matter how many times of group key updates occur. Secondly, the computation time of computing the newest group key from the key update history is always O(logN) no matter how many group key updates are missed. This feature provides a practical solution for group key update when members go offline from time to time. Finally, the proposed scheme is immune to the collusion attack of other members.

Erasure code based distributed storage systems provide data robustness by storing encoded-fragments over servers. To maintain data robustness, a repair mechanism recovers a storage system from server failures by repairing encoded-fragments. For decentralized erasure code based storage systems, we propose a decentralized repair mechanism. Our mechanism has the following features. Firstly, an encoded- fragment is replenished by a combination of a number u of encoded-fragments that are randomly chosen. Secondly, the number u depends on the number of the available encoded- fragments and is independent of the pattern of missing encoded-fragments. Thirdly, multiple encoded-fragments are simultaneously replenished in parallel. We measure the communication cost in terms of the number u of required network connections for replenishing an encoded-fragment. We then conducted a numerical analysis by using traces of real systems. We find that our requirement on u is smaller than that from existing methods. Both theoretical and numerical results show that our decentralized repair mechanism outperforms existing ones in terms of the communication cost under the same consideration of efficiency cost for storage.

Reducing distortion between the cover object and the stego object is an important issue for steganography. The tree-based parity check method is very efficient for hiding a message on image data due to its simplicity. Based on this approach, we propose a majority vote strategy that results in least distortion for finding a stego object. The lower embedding efficiency of our method is better than that of previous works when the hidden message length is relatively large.

An(n,d) permutation array (PA) is a subset ofSnwith the property that the distance (under some metric) between any two permutations in the array is at leastd. They became popular recently for communication over power lines. Motivated by an application to flash memories, in this paper, the metric used is the Chebyshev metric. A number of different constructions are given, as well as bounds on the size of such PA.

Distributed networked storage systems provide the storage service on the Internet. We address the privacy issue of the distributed networked storage system. It is desired that data stored in the system remain private even if all storage servers in the system are compromised. The major challenge of designing these distributed networked storage systems is to provide a better privacy guarantee while maintaining the distributed structure. To achieve this goal, we introduce secure decentralized erasure code, which combines a threshold public key encryption scheme and a variant of the decentralized erasure code. Our secure distributed networked storage system constructed by the secure decentralized erasure code is decentralized, robust, private, and with low storage cost.

In this paper we re-examine the attacking scenario about wireless sensor networks. It is generally assumed that the adversary picks up all radio communications of sensor nodes without any loss and stores the eavesdropped messages for later use. We suggest that in some situations the adversary may not be able to pick up all radio communications of sensor nodes. Therefore, we propose the storage-bounded adversary model for wireless sensor networks, in which the adversary's storage is bounded. We propose two key establishment schemes for establishing shared keys for neighboring sensor nodes in the storage-bounded adversary model. The first scheme needs special beacon nodes for broadcasting random bits. In the second scheme, some sensor nodes play the role of beacon nodes. Our results are theoretical in some sense. Nevertheless, we can adjust them for realistic consideration.

An (n, d) permutation array (PA) is a subset of Snwith the property that the distance (under any distance metric, such as Hamming) between any two permutations in the array is at least d, which becomes popular recently for communication over power line. We use l∞-norm to measure the distance between permutations, and give a construction of permutation arrays under l∞-norm together with efficient encoding and decoding algorithms. This construction is the first of its kind.

Visual cryptography (VC) is a method of encrypting a secret image into shares such that stacking a sufficient number of shares reveals the secret image. Shares are usually presented in transparencies. Each participant holds a transparency. Most of the previous research work on VC focuses on improving two parameters: pixel expansion and contrast. In this paper, we studied the cheating problem in VC and extended VC. We considered the attacks of malicious adversaries who may deviate from the scheme in any way. We presented three cheating methods and applied them on attacking existent VC or extended VC schemes. We improved one cheat-preventing scheme. We proposed a generic method that converts a VCS to another VCS that has the property of cheating prevention. The overhead of the conversion is near optimal in both contrast degression and pixel expansion.

We consider the security problem for retrieving data from a web site (or a large database system) via Internet. Consider the situation that a user visits a web site to get information. He wants to retain anonymity of his identity, while the web site would like to authenticate the user's identity. We proposed an anonymous authentication scheme to provide a solution for these two seemingly conflicting requirements. Our anonymous authentication scheme is based on cryptographic techniques. Together with a novel time-dependent hierarchical key assignment scheme, we proposed a data access system that has the following distinct features simultaneously: (1) anonymous authentication, (2) cryptographic access control, (3) saving on-line encryption time, and (4) a flexible subscription system.

We study the problem of deterministically extracting almost perfect random bits from multiple weakly random sources that are mutually independent. With two independent sources, we have an explicit extractor which can extract a number of random bits that matches the best construction currently known, via the generalized leftover hash lemma. We also extend our construction to extract randomness from more independent sources. One nice feature is that the extractor still works even with all but one source exposed. Finally, we apply our extractor for a cryptographic task in which a group of parties wants to agree on a secret key for group communication over an insecure channel, without using ideal local randomness.

We study the distance measures between two probability distributions via two different distance metrics, a new metric induced from Jensen-Shannon divergence, and the well known L/sub 1/ metric. We show that several important results and constructions in computational complexity under the L/sub 1/ metric carry over to the new metric, such as Yao's next-bit predictor, the existence of extractors, the leftover hash lemma, and the construction of expander graph based extractor. Finally, we show that the useful parity lemma in studying pseudorandomness does not hold in the new metric.

We propose efficient and secure (string) oblivious transfer (OT/sup 1//sub n/) schemes for any n/spl ges/2. We build our OT/sup 1//sub n/ scheme from fundamental cryptographic techniques directly. The receiver's choice is unconditionally secure and the secrecy of the unchosen secrets is based on the hardness of the decisional Diffie-Hellman problem. Some schemes achieve optimal efficiency in terms of the number of rounds and the total number of exchanged messages for the case that the receiver's choice is unconditionally secure. The distinct feature of our scheme is that the system-wide parameters are independent of n and universally usable, that is, all possible receivers and senders use the same parameters and need no trapdoors specific to each of them. We extend our OT/sup 1//sub n/ schemes to distributed oblivious transfer schemes. Our distributed OT/sup 1//sub n/ schemes take full advantage of the research results of secret sharing. For applications, we present a method of transforming any (single-database) PIR protocol into a symmetric PIR protocol by slightly increasing the communication cost only.

When a group of people want to communicate securely over an open network, they run a conference-key protocol to establish a common conference key K such that all their communications thereafter are encrypted with the key K. In this paper, we propose a provably secure fault-tolerant conference-key agreement protocol under the authenticated broadcast channel model. We show that a passive adversary gets zero knowledge about the conference key established by the honest participants under the assumption of a variant Diffie-Hellman (1976) decision problem. We also show that the honest participants can agree on a common conference key no matter how many participants are malicious. Furthermore, we show that even if the broadcast channel is not authenticated, our protocol is secure against impersonators under the random oracle model.

The cryptographic key assignment problem is to assign cryptographic keys to a set of partially ordered classes so that the cryptographic key of a higher class can be used to derive the cryptographic key of a lower class. In this paper, we propose a time-bound cryptographic key assignment scheme in which the cryptographic keys of a class are different for each time period, that is, the cryptographic key of class C/sub i/ at time t is K/sub i, t./ Key derivation is constrained not only by the class relation, but also the time period. In our scheme, each user holds some secret parameters whose number is independent of the number of the classes in the hierarchy and the total time periods. We present two novel applications of our scheme. One is to broadcast data to authorized users in a multilevel-security way and the other is to construct a flexible cryptographic key backup system.

Two probabilistic automata are equivalent if for any string x, the two automata accept x with equal probability. This paper presents an $O((n_1 + n_2 )^4 )$ algorithm for determining whether two probabilistic automata $U_1 $ and $U_2 $ are equivalent, where $n_1 $ and $n_2 $ are the number of states in $U_1 $ and $U_2 $, respectively.This improves the best previous result, which showed that the problem was in $coNP$. The existence of this algorithm implies that the covering and equivalence problems for uninitiated probabilistic automata are also polynomial-time solvable. The algorithm used to determine the equivalence of probabilistic automata can also solve the path equivalence problem for nondeterministic finite automata without $\lambda $-transitions and the equivalence problem for unambiguous finite automata in polynomial time. This paper studies the approximate equivalence (or $\delta $-equivalence) problem for probabilistic automata. An algorithm for the approximate equivalence problem for positive probabilistic automata is given.

It is proved that the equivalence problem for probabilistic automata is solvable in time O((n/sub 1/+n/sub 2/)/sup 4/), where n/sub 1/ and n/sub 2/ are numbers of states of two given probabilistic automata. This result improves the best previous upper bound of coNP. The algorithm has some interesting applications, for example, to the covering and equivalence problems for uninitiated probabilistic automata, the equivalence and containment problems for unambiguous nondeterministic finite automata, and the path-equivalence problem for nondeterministic finite automata. Using the same technique, a polynomial-time algorithm for learning probabilistic automata is developed. The learning protocol is learning by means of queries.>