Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2006 | Book

Concrete Chosen-Ciphertext Secure Encryption from Subgroup Membership Problems Read chapter Read first chapter

Cryptology and Network Security

5th International Conference, CANS 2006, Suzhou, China, December 8-10, 2006. Proceedings

Editors: David Pointcheval, Yi Mu, Kefei Chen

Publisher: Springer Berlin Heidelberg

Book Series : Lecture Notes in Computer Science

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

Table of Contents

Frontmatter

Encryption

Concrete Chosen-Ciphertext Secure Encryption from Subgroup Membership Problems
Abstract
Using three previously studied subgroup membership problems, we obtain new concrete encryption schemes secure against adaptive chosen-ciphertext attack in the standard model, from the Cramer-Shoup and Kurosawa-Desmedt constructions. The schemes obtained are quite efficient. In fact, the Cramer-Shoup derived schemes are more efficient than the previous schemes from this construction, including the Cramer-Shoup cryptosystem, when long messages are considered. The hybrid variants are even more efficient, with a smaller number of exponentiations and a shorter ciphertext than the Kurosawa-Desmedt Decisional Diffie-Hellman based scheme.
Jaimee Brown, Juan Manuel González Nieto, Colin Boyd
Efficient Identity-Based Encryption with Tight Security Reduction
Abstract
In a famous paper at Crypto’01, Boneh and Franklin proposed the first fully functional identity-based encryption scheme (IBE), around fifteen years after the concept was introduced by Shamir. Their scheme achieves chosen-ciphertext security (i.e., secure in the sense of IND-ID-CCA); however, the security reduction is far from being tight.
In this paper, we present an efficient variant of the Boneh-Franklin scheme that achieves a tight security reduction. Our scheme is basically an IBE scheme under two keys, one of which is randomly chosen and given to the user. It can be viewed as a continuation of an idea introduced by Katz and Wang; however, unlike the Katz-Wang variant, our scheme is quite efficient, as its ciphertext size is roughly comparable to that of the original full Boneh-Franklin scheme. The security of our scheme can be based on either the gap bilinear Diffie-Hellman (GBDH) or the decisional bilinear Diffie-Hellman (DBDH) assumptions.
Nuttapong Attrapadung, Jun Furukawa, Takeshi Gomi, Goichiro Hanaoka, Hideki Imai, Rui Zhang

Key Exchange

A Diffie-Hellman Key Exchange Protocol Without Random Oracles
Abstract
The MQV protocol of Law, Menezes, Qu, Slinas and Vanstone has been regarded as the most efficient authenticated Diffie-Hellman key exchange protocol, and standardized by many organizations including the US NSA. In Crypto 2005, Hugo Krawczyk showed vulnerabilities of MQV to several attacks and suggested a hashed variant of MQV, called HMQV, which provides the same superb performance of MQV and provable security in the random oracle model. In this paper we suggest an efficient authenticated Diffie-Hellman key exchange protocol providing the same functionalities and security of HMQV without random oracles. There exist some provably secure key exchange schemes using signatures in the standard model, but all of the schemes do not provide the same level of security of HMQV. So far there are no authenticated Diffie-Hellman protocols which are proven secure in the standard model and achieve the same level of security goals of HMQV efficiently yet. Dispensing of random oracles in our protocol does not require any expensive signature and encryption schemes.
Ik Rae Jeong, Jeong Ok Kwon, Dong Hoon Lee
Authenticated Group Key Agreement for Multicast
Abstract
Secure multicast communication provides an efficient way to deliver data to a large group of recipients. Scalability, efficiency and authenticity are the key challenges for secure multicast. In this paper, we propose a novel group key agreement scheme called logical identity hierarchy(LIH) for multicast to support secure communications for large and dynamic groups, which is based on bilinear pairing. Compared with the previous tree-based schemes, LIH provides dual authentication between group controller(GC) and group members and hierarchical authentication among group members. GC and all the users do not need to execute any encryption/decryption process during the rekeying operation. Moreover, in LIH, the group members can be stateless receivers, who do not need to update their state during the protocol execution. Using a public board, GC does not need to multicast any rekeying message when a user joins/leaves the communication group. Security analysis shows that LIH satisfies both backward secrecy and forward secrecy.
Liming Wang, Chuan-Kun Wu
Authenticated and Communication Efficient Group Key Agreement for Clustered Ad Hoc Networks
Abstract
Common group key agreement protocols are not applicable in ad hoc networks because the dynamic and multi-hop nature. Clustering is a method by which nodes are hierarchically organized based on their relative proximity to one another. Driven by this insight, a hierarchical key agreement protocol is proposed to weaken the 1-hop assumption in common group key agreement protocols. We employ Joux’s tripartite protocol and a generalized Diffie-Hellman protocol as the basic building block for group key agreement. The protocol can handle efficiently the dynamic events in ad hoc networks. Moreover, in order to authenticate the messages, a provable ID-based signature scheme is presented. The analysis results indicate that the proposed protocol is secure in withstanding many common attacks and is extremely efficient and feasible to ad hoc networks with large size.
Hongsong Shi, Mingxing He, Zhiguang Qin

Authentication and Signatures

Efficient Mutual Data Authentication Using Manually Authenticated Strings
Abstract
Solutions for an easy and secure setup of a wireless connection between two devices are urgently needed for WLAN, Wireless USB, Bluetooth and similar standards for short range wireless communication. All such key exchange protocols employ data authentication as an unavoidable subtask. As a solution, we propose an asymptotically optimal protocol family for data authentication that uses short manually authenticated out-of-band messages. Compared to previous articles by Vaudenay and Pasini the results of this paper are more general and based on weaker security assumptions. In addition to providing security proofs for our protocols, we focus also on implementation details and propose practically secure and efficient sub-primitives for applications.
Sven Laur, Kaisa Nyberg
Achieving Multicast Stream Authentication Using MDS Codes
Abstract
We address the multicast stream authentication problem when the communication channel is under the control of an opponent who can drop, reorder or inject data. In such a network model, packet overhead and computing efficiency are important parameters to be taken into account when designing a multicast authentication protocol. Our construction will exhibit three main advantages. First, our packet overhead will only be a few hashes long. Second, we will exhibit a number of signature verifications to be performed by the receivers which will turn to be O(1). Third, every receiver will still be able to recover all the data packets emitted by the sender despite losses and injections occurred during the transmission of information.
Christophe Tartary, Huaxiong Wang
Shorter Verifier-Local Revocation Group Signatures from Bilinear Maps
Abstract
We propose a new computational complexity assumption from bilinear map, based on which we construct Verifier-Local Revocation group signatures with shorter lengths than previous ones.
Sujing Zhou, Dongdai Lin

Proxy Signatures

Security Model of Proxy-Multi Signature Schemes
Abstract
In a proxy multi-signature scheme, a designated proxy signer can generate the signature on behalf of a group of original signers. Although some work has been done in proxy-multi signature schemes, until now there is no formalized definition and security model for them. In this paper, we will give the formal definition and a security model of proxy-multi signature scheme. We also constructed a proxy-multi signature scheme based on the BLS short signature scheme and proved its security in our security model.
Feng Cao, Zhenfu Cao
Efficient ID-Based One-Time Proxy Signature and Its Application in E-Cheque
Abstract
To put restrictions on signing capability of the proxy signer, the notion of one-time proxy signature was put forth by Kim et al. in 2001. Today, to our best knowledge, although plenty of one-time proxy signature schemes have been proposed, no ID-based one-time proxy signature (IBOTPS) has yet been presented. Therefore, in this paper, to fill this void, we first formalize the security notions for IBOTPS, and propose the first efficient IBOTPS scheme based on the bilinear pairings and provide the formal security proofs in the random oracle model. Also, we consider an application of the proposed scheme in E-cheque scenarios.
Rongxing Lu, Zhenfu Cao, Xiaolei Dong

Cryptanalysis

Side Channel Attacks and Countermeasures on Pairing Based Cryptosystems over Binary Fields
Abstract
Pairings on elliptic curves have been used as cryptographic primitives for the development of new applications such as identity based schemes. For the practical applications, it is crucial to provide efficient and secure implementations of the pairings. There have been several works on efficient implementations of the pairings. However, the research for secure implementations of the pairings has not been thoroughly investigated. In this paper, we investigate vulnerability of the pairing used in some pairing based protocols against side channel attacks. We propose an efficient algorithm secure against such side channel attacks of the eta pairing using randomized projective coordinate systems for the pairing computation.
Tae Hyun Kim, Tsuyoshi Takagi, Dong-Guk Han, Ho Won Kim, Jongin Lim
Improved Collision Attack on Reduced Round Camellia
Abstract
Camellia is a 128-bit block cipher which has been selected as an international standard by ISO/IEC and a European encryption standard by the NESSIE project. Wu Wenling presented the collision attack on reduced-round Camellia in 2004, the 128-bit key of 6 rounds Camellia can be recovered with 210 chosen plaintexts and 215 encryptions. The improved collision attack on 6 rounds Camellia which based on four 4-round distinguishers is presented in this paper. This attack requires less than 210.6 chosen plaintexts and 211.5 encryptions.
Guan Jie, Zhang Zhongya
Stealing Secrets with SSL/TLS and SSH – Kleptographic Attacks
Abstract
We present very simple kleptographic attacks on SSL/TLS and SSH protocols. They enable a party, which has slightly manipulated the code of a cryptographic library, to steal secrets of the user. According to the scenario of the kleptographic attacks the secrets can be stolen only by a party having a secret key not included in the manipulated code. The attacker needs only to record transmissions. The messages transmitted are indistinguishable from the not manipulated ones (even for somebody that knows the kleptocode inserted). Therefore, detection of infected nodes based on communication analysis is much harder than in the case of classical subliminal channels.
The problems are caused by certain design features of SSL/TLS and SSH protocols that make them vulnerable for a kleptographic attack. We propose changes of these protocols that make them immune against this threat while all previous security features remain preserved.
Zbigniew Gołȩbiewski, Mirosław Kutyłowski, Filip Zagórski

Implementation

Bitslice Implementation of AES
Abstract
Network applications need to be fast and at the same time provide security. In order to minimize the overhead of the security algorithm on the performance of the application, the speeds of encryption and decryption of the algorithm are critical. To obtain maximum performance from the algorithm, efficient techniques for its implementation must be used and the implementation must be tuned for the specific hardware on which it is running.
Bitslice is a non-conventional but efficient way to implement DES in software. It involves breaking down of DES into logical bit operations so that N parallel encryptions are possible on a single N-bit microprocessor. This results in tremendous throughput. AES is a symmetric block cipher introduced by NIST as a replacement for DES. It is rapidly becoming popular due to its good security features, efficiency, performance and simplicity. In this paper we present an implementation of AES using the bitslice technique. We analyze the impact of the architecture of the microprocessor on the performance of bitslice AES. We consider three processors; the Intel Pentium 4, the AMD Athlon 64 and the Intel Core 2. We optimize the implementation to best utilize the superscalar architecture and SIMD instruction set present in the processors.
Chester Rebeiro, David Selvakumar, A. S. L. Devi
A Fast Algorithm for Determining the Linear Complexity of Periodic Sequences over GF(3)
Abstract
A fast algorithm is derived for determining the linear complexity and the minimal polynomial of periodic sequences over GF(3) with period 3 n p m , where p is a prime number, and 3 is a primitive root modulo p 2 . The algorithm presented here generalizes the fast algorithm to determine the linear complexity of a sequence over GF(q) with period p m , where p is a prime, q is a prime and a primitive root modulo p 2.
Jianqin Zhou, Qiang Zheng

Steganalysis and Watermarking

Steganalysis Based on Differential Statistics
Abstract
Differential statistics were proposed in this paper to disclose the existence of hidden data in grayscale raw images. Meanwhile, differential statistics were utilized to improve the algorithm introduced by Fridrich to attack steganographic schemes in grayscale JPEG images. In raw images, to describe the correlation between data and their spatial positions, co-occurrence matrix based on intensities of adjacent pixels was adopted and the use of co-occurrence matrix was extended to high-order differentiations. The COMs (center of mass) of HCFs (histogram character function) were calculated from these statistics to form a 30-dimensional feature vector for steganalysis. For JPEG files, differential statistics were collected from boundaries of DCT blocks in their decompressed images. The COM of HCF was computed for each of these differential statistics and statistics from DCT domain so that a 28-dimensional feature vector can be extracted from a JPEG image. Two blindly steganalytic algorithms were constructed based on Support Vector Machine and the two kinds of feature vectors respectively. The presented methods demonstrate higher detecting rates with lower false positives than known schemes.
Zugen Liu, Lingdi Ping, Jian Chen, Jimin Wang, Xuezeng Pan
Watermarking Essential Data Structures for Copyright Protection
Abstract
Software watermarking is a new research area that aims at providing copyright protection for commercial software. It minimizes software piracy by hiding copyright signatures inside the program code or its runtime state. Prior proposals hide the watermarks in dummy data structures, e.g., linked lists and graphs that are created during the execution of the hosting software for this reason. This makes it vulnerable to subtractive attacks, because the attacker can remove the data structure without altering the operation or the semantic of the software program. In this regard, we argue that hiding watermarks in one or more data structures that are used by the program would make the watermark more robust because removing the watermark would alter the semantic and the operations of the underlying software. However, the challenge is that the insertion of the watermark should have a minimal effect on the operations and performance of the data structure.
This paper proposes a novel method for watermarking R-tree data structure and its variants. The proposed watermarking scheme takes advantage of the redundancy in the way the entries within R-tree nodes are ordered. R-trees do not require ordering the entries in a specific way. Node entries are re-ordered in a way to map the watermark. The new order is calculated relative to a “secret” initial order, known only to the software owner, using a technique based on a numbering system that uses variable radix and factorial base. The addition of the watermark in the R-tree data structure neither affects the performance nor increases the size of the R-tree. The paper provides a threat model and analysis to show that the watermarked R-trees are robust and can withstand various types of attacks.
Qutaiba Albluwi, Ibrahim Kamel

Boolean Functions and Stream Ciphers

A Note of Perfect Nonlinear Functions
Abstract
Perfect nonlinear functions are of importance in cryptography. By using Galois rings and investigating the character values of corresponding relative difference sets, we construct a perfect nonlinear function from \(\mathbb{Z}^{n}_{p_{2}}\) to \(\mathbb{Z}^{m}_{p_{2}}\) where 2m is possibly larger than the largest divisor of n. Meanwhile we prove that there exists a perfect nonlinear function from \(\mathbb{Z}^{2}_{2_{p}}\) to \(\mathbb{Z}_{2_{p}}\) if and only if p=2, and that there doesn’t exist a perfect nonlinear function from \(\mathbb{Z}^{2n}_{2k_{l}}\) to \(\mathbb{Z}^{m}_{2k_{l}}\) if m>n and l(l is odd) is self-conjugate modulo 2 k (k≥1) .
Xiyong Zhang, Hua Guo, Jinjiang Yuan
Chaotic Keystream Generator Using Coupled NDFs with Parameter Perturbing
Abstract
Chaotic cryptology has been widely investigated recently. This paper analyzes the security pitfalls existing in digital chaotic stream ciphers, which work on the well characterized one-dimensional(1-D) chaotic systems. As a practical solution to these problems caused by 1-D chaotic systems, a chaotic keystream generator using nonlinear digital filters with n-D uniform distribution is proposed. To improve system security further and overcome the effects of finite wordlength, the coupling method with parameter perturbing is considered. Detailed theoretical analyses show that it has perfect cryptographic properties, and can be used to construct stream ciphers with higher security than other 1-D chaotic ciphers. Finally, some numeric experiments are made and the experimental results coincide well with the theoretical analyses.
Xiaomin Wang, Jiashu Zhang, Wenfang Zhang

Intrusion Detection

Cooperative Intrusion Detection for Web Applications
Abstract
This contribution involves cooperative information systems, and more precisely interorganizational systems (IOS). Indeed, experience of real enterprises shows that most IOS interoperate today over the Web. To “ensure” security of these IOS on the Web (in particular, security of the applications they are made of), various hardware and software protection can be employed. Our work falls into the field of intrusion detection, and covers more precisely intrusion detection for Web applications. Several misuse-based intrusion detection systems (IDSs) were developed recently for Web applications, whereas, to our knowledge, only one anomaly-based Web IDS exists and works effectively to date. This one was unfortunately conceived disregarding any kind of cooperation. In previous work, we improved it to gain in sensitivity and specificity. This paper describes a cooperation feature added to the IDS, so that it is able to perform an alarm correlation with other detectors, allowing coo-perative intrusion detection, as well as an event correlation to detect distributed attacks. The first experiments in real environment show encouraging results.
Nathalie Dagorn
Finding TCP Packet Round-Trip Time for Intrusion Detection: Algorithm and Analysis
Abstract
Most network intruders launch their attacks through stepping-stones to reduce the risks of being discovered. To uncover such intrusions, one prevalent, challenging, and critical way is to detect a long interactive connection chain. TCP packet round-trip time (RTT) can be used to estimate the length of a connection chain. In this paper, we propose a Standard Deviation-Based Clustering (SDC) Algorithm to find RTTs. SDC takes advantage of the fact that the distribution of RTTs is concentrated on a small range to find RTTs. It outperforms other approaches in terms of packet matching-rate and matching-accuracy. We derive an upper-bound of the probability of making an incorrect selection of RTT through SDC. This paper includes some experimental results to compare SDC with other algorithms and discusses its restrictions as well.
Jianhua Yang, Byong Lee, Yongzhong Zhang
Smart Architecture for High-Speed Intrusion Detection and Prevention Systems
Abstract
The overall performance of an intrusion protection system depends not only on the packet header classification and pattern matching, but also on the post-operative determination of correlative patterns of matched rules. An increasing number of patterns associated with a rule heighten the importance of correlative pattern matching. This work proposes a TCAM-based smart architecture that supports both deep pattern-matching and correlative pattern-matching. The proposed architecture overcomes the difficulties in implementing TCAM when the patterns are very deep and the rules for packet payload involve many patterns whose positions lie within a range. A real case payload is simulated using a Snort 2.3 rule set and simulation results demonstrate the feasibility of the proposed architecture in supporting a high-speed and robust intrusion detection and prevention system.
Chih-Chiang Wu, Sung-Hua Wen, Nen-Fu Huang
A Multi-agent Cooperative Model and System for Integrated Security Monitoring
Abstract
The increasing complexity of various network threats has made the integration and cooperation of multiple security monitoring technologies necessary in network security defense. However, most existing works have focused on certain special monitoring technologies such as intrusion detection, and studies on integrated security monitoring system are quite insufficient. In this paper, a novel formal model called MCSM (Multi-agent Cooperation model for Security Monitoring based on knowledge) is proposed. In MCSM, the integrated security monitoring is modeled as a FSA (Finite State Automata) with multiple agents, and a general knowledge structure for multiple agents is constructed. We have successfully developed an IMS (Integrated Monitoring System) called ACT-BroSA (Broad-spectrum security Scan and Analysis system) based on MCSM. Results of experiments show that the integrated monitoring capability is significantly improved.
Xianxian Li, Lijun Liu

Disponibility and Reliability

Detecting DDoS Attacks Based on Multi-stream Fused HMM in Source-End Network
Abstract
DDoS (Distributed Denial-of-Service) attacks detection system deployed in source-end network is superior in detection and prevention than that in victim network, because it can perceive and throttle attacks before data flow to Internet. However, the current existed works in source-end network lead to a high false-positive rate and false-negative rate for the reason that they are based on single-feature, and they couldn’t synthesize multi-features simultaneously. This paper proposes a novel approach using Multi-stream Fused Hidden Markov Model (MF-HMM) on source-end DDoS detection for integrating multi-features simultaneously. The multi-features include the S-D-P feature, TCP header Flags, and IP header ID field. Through experiments, we compared our original approach based on multiple detection feature with other main algorithms (such as CUSUM and HMM) based on single-feature. The results present that our approach effectively reduces false-positive rate and false-negative rate, and improve the precision of detection.
Jian Kang, Yuan Zhang, Jiu-bin Ju
An Immune-Based Model for Service Survivability
Abstract
In order to enhance service survivability, an immune-based model for service survivability, referred to as ISSM, is presented. In the model, the concepts and formal definitions of self, nonself, immunocyte, diversity system, and etc., are given; the antibody concentration and the dynamic change process of host status are described. Building on the relationship between the antibody concentration and the state of an illness in the human immune system, the systemic service capability and the service risk are calculated quantitatively. Based on the differences of the immune system among individuals, a service survivability algorithm, dynamic service migration algorithm, is put forth. Simulation results show that the model is real-time and adaptive, thus providing an effective solution for service survivability.
Jinquan Zeng, Xiaojie Liu, Tao Li, Feixian Sun, Lingxi Peng, Caiming Liu
X2BT Trusted Reputation System: A Robust Mechanism for P2P Networks
Abstract
Over the past few years, Peer-to-Peer (P2P) networks have grown extensively and dramatically changed large-scale file transfer. One of the most popular P2P network is the BitTorrent system. BitTorrent can efficiently distribute large files by optimizing the use of network bandwidth and providing scalability. Due to the open and anonymous nature of P2P systems BitTorrent also provides an ideal environment for distribution of malicious, low quality, or doctored information. A number of reputation systems, including P2PRep with its successors XRep and X 2 Rep, had been proposed to address security weaknesses of Gnutella P2P file sharing networks. Although it has been claimed that these methods are also applicable to the other file sharing networks, it is not clear how to achieve this task. Moreover, some of the shortcomings of these reputation systems such as online-polling only and cold-start may be exploited by malicious attackers. In this paper, we propose a reputation system, called X 2BT Rep, which is an extension of the X 2 Rep and for BitTorrent network. We show that the proposed system improves the security and the quality of information distributed over P2P networks.
Lan Yu, Willy Susilo, Rei Safavi-Naini
Backmatter
Metadata
Title
Cryptology and Network Security
Editors
David Pointcheval
Yi Mu
Kefei Chen
Copyright Year
2006
Publisher
Springer Berlin Heidelberg
Electronic ISBN
978-3-540-49463-8
Print ISBN
978-3-540-49462-1
DOI
https://doi.org/10.1007/11935070

Premium Partner

    Image Credits