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

Edge Eavesdropping Games Read chapter Read first chapter

Security and Cryptography for Networks

5th International Conference, SCN 2006, Maiori, Italy, September 6-8, 2006. Proceedings

Editors: Roberto De Prisco, Moti Yung

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

About this book

The Conference on Security and Cryptography for Networks 2006 (SCN 2006) was held in Maiori, Italy, on September 6-8, 2006. The conference was the ?fth in the SCN series, and this year marked a change in its name (the former name was Security in Communication Networks). The name change meant to better describe the scope of the conference while preserving the SCN acronym. This year for the ?rst time we had the proceedings volume ready at the conference. We feel thatthe SCN conferencehas maturedandthat it has becomea tradition to hold it regularly in the beautiful setting of the Amal?tan coast as a biennial event. Theconferencebroughttogetherresearchersinthe?eldsofcryptographyand security in order to foster the extension of cooperation and exchange of ideas among them, aiming at assuring safety and trustworthiness of communication networks. The topics covered by the conference this year included: foundations of distributed systems security, signatures schemes, block ciphers, anonymity, e-commerce, public key encryption and key exchange, secret sharing, symmetric and public key cryptanalysis, randomness, authentication. The international Program Committee consisted of 24 members who are top experts in the conference ?elds. We received 81 submissions amongst which 24 papers were selected for presentation at the conference. These proceedings - clude the extended abstract versions of the 24 accepted papers and the short abstract of the invited talk by Ivan Damg? ard.

Table of Contents

Frontmatter

Distributed Systems Security: Foundations

Edge Eavesdropping Games
Abstract
Motivated by the proactive security problem, we study the question of maintaining secrecy against a mobile eavesdropper that can eavesdrop to a bounded number of communication channels in each round of the protocol. We characterize the networks in which secrecy can be maintained against an adversary that can eavesdrop to t channels in each round. Using this characterization, we analyze the number of eavesdropped channels that complete graphs can withhold while maintaining secrecy.
Amos Beimel, Matthew Franklin
Universally Composable Simultaneous Broadcast
Abstract
Simultaneous Broadcast protocols allow different parties to broadcast values in parallel while guaranteeing mutual independence of the broadcast values. The problem of simultaneous broadcast was suggested by Chor et al. (FOCS 1985) who proposed a linear-round solution, and later improved by Chor and Rabin (PODC 1987) and Gennaro (IEEE Trans. on Parallel and Distributed Systems 2000). The most efficient solution, in terms of round complexity, is the one due to Gennaro, which is in the common random string model. This construction has constant round complexity but is not very practical, as it requires generic zero-knowledge proofs, non-interactive zero-knowledge proofs of knowledge, and commitment schemes. All the mentioned solutions were proven secure under security definitions with weak or no composition guarantees – only sequential composition for the initial construction by Chor et al.
In this work, we explore the problem of Simultaneous Broadcast under Universally Composable (UC) security (Canetti 2001). We give a definition of Simultaneous Broadcast in this framework, which is shown to imply all past definitions. We also show this notion can be achieved by a computationally efficient, constant-round construction (building on the verifiable secret sharing scheme of Cramer et al. at Eurocrypt 1999), which is secure under an honest majority. Our results rely on (and benefit from) capturing synchronous communication as a functionality within the UC model, as suggested by Canetti (IACR eprint 2005). Indeed, we show that this approach of modeling synchronous communication can lead to better understanding of where synchronicity is needed, and also simpler constructions and proofs.
Alejandro Hevia

Signature Schemes Variants

Relations Among Security Notions for Undeniable Signature Schemes
Abstract
In this paper, we conduct a thorough study among various notions of security of undeniable signature schemes and establish some relationships among them. We focus on two adversarial goals which are unforgeability and invisibility and two attacks which are chosen message attack and full attack. In particular,we show that unforgeability against chosen message attack is equivalent to unforgeability against full attack, and invisibility against chosen message attack is equivalent to invisibility against full attack. We also present an undeniable signature scheme whose unforgeability is based on the factoring assumption and whose invisibility is based on the composite decision Diffie-Hellman assumption.
Kaoru Kurosawa, Swee-Huay Heng
Concurrent Blind Signatures Without Random Oracles
Abstract
We present a blind signature scheme that is efficient and provably secure without random oracles under concurrent attacks utilizing only four moves of short communication. The scheme is based on elliptic curve groups for which a bilinear map exists and on extractable and equivocal commitments. The unforgeability of the employed signature scheme is guaranteed by the LRSW assumption while the blindness property of our scheme is guaranteed by the Decisional Linear Diffie-Hellman assumption. We prove our construction secure under the above assumptions as well as Paillier’s DCR assumption in the concurrent attack model of Juels, Luby and Ostrovsky from Crypto ’97 using a common reference string. Our construction is the first efficient construction for blind signatures in such a concurrent model without random oracles. We present two variants of our basic protocol: first, a blind signature scheme where blindness still holds even if the public-key generation is maliciously controlled; second, a blind signature scheme that incorporates a “public-tagging” mechanism. This latter variant of our scheme gives rise to a partially blind signature with essentially the same efficiency and security properties as our basic scheme.
Aggelos Kiayias, Hong-Sheng Zhou
Universal Designated Verifier Signatures Without Random Oracles or Non-black Box Assumptions
Abstract
Universal designated verifier signatures (UDVS) were introduced in 2003 by Steinfeld et al. to allow signature holders to monitor the verification of a given signature in the sense that any plain signature can be publicly turned into a signature which is only verifiable by some specific designated verifier. Privacy issues, like non-dissemination of digital certificates, are the main motivations to study such primitives. In this paper, we propose two fairly efficient UDVS schemes which are secure (in terms of unforgeability and anonymity) in the standard model (i.e. without random oracles). Their security relies on algorithmic assumptions which are much more classical than assumptions involved in the two only known UDVS schemes in standard model to date. The latter schemes, put forth by Zhang et al. in 2005 and Vergnaud in 2006, rely on the Strong Diffie-Hellman assumption and the strange-looking knowledge of exponent assumption (KEA). Our schemes are obtained from Waters’s signature and they do not need the KEA assumption. They are also the first random oracle-free constructions with the anonymity property.
Fabien Laguillaumie, Benoît Libert, Jean-Jacques Quisquater

Block Ciphers Analysis

Understanding Two-Round Differentials in AES
Abstract
In this paper we study the probability of differentials and characteristics over 2 rounds of the AES with the objective to understand how the components of the AES round transformation interact in this respect. We extend and correct the analysis of the differential properties of the multiplicative inverse in GF(2 n ) given in [9]. We study the number of characteristics with EDP >0 whose probability adds up to the probability of a differential and derive formulas that allow to produce a close estimate of this number for any differential. We use the properties discovered in our study to explain the differentials with the maximum EDP values and describe the impact of the linear transformation in the AES S-box in this respect.
Joan Daemen, Vincent Rijmen
Related-Key Attacks on the Full-Round Cobra-F64a and Cobra-F64b
Abstract
Cobra-F64a and Cobra-F64b, designed for firmware-oriented applications, are 64-bit Data-dependent Permutation based block ciphers with 128 key bits, which consist of 16 and 20 rounds, respectively. In this paper, we investigate their security against related-key attacks. Our investigation shows that the full 16-round Cobra-F64a can be broken by our related-key rectangle attack and that the full 20-round Cobra-F64b can be broken by our related-key differential attack.
Jiqiang Lu, Changhoon Lee, Jongsung Kim

Anonymity and E-Commerce

Constant-Size Dynamic k-TAA
Abstract
k-times anonymous authentication (k-TAA) schemes allow members of a group to be authenticated anonymously by application providers for a bounded number of times. Dynamic k-TAA allows application providers to independently grant or revoke users from their own access group so as to provide better control over their clients. In terms of time and space complexity, existing dynamic k-TAA schemes are of complexities O(k), where k is the allowed number of authentication. In this paper, we construct a dynamic k-TAA scheme with space and time complexities of O(log(k)). We also outline how to construct dynamic k-TAA scheme with a constant proving effort. Public key size of this variant, however, is O(k).
We then construct an ordinary k-TAA scheme from the dynamic scheme. We also describe a trade-off between efficiency and setup freeness of AP, in which AP does not need to hold any secret while maintaining control over their clients.
To build our system, we modify the short group signature scheme into a signature scheme and provide efficient protocols that allow one to prove in zero-knowledge the knowledge of a signature and to obtain a signature on a committed block of messages. We prove that the signature scheme is secure in the standard model under the q-SDH assumption.
Finally, we show that our dynamic k-TAA scheme, constructed from bilinear pairing, is secure in the random oracle model.
Man Ho Au, Willy Susilo, Yi Mu
On Secure Orders in the Presence of Faults
Abstract
We present specifications and provably-secure protocol, for fully automated resolution of disputes between a provider of digital goods and services, and its customers. Disputes may involve the timely receipt of orders and goods, due to communication failures and malicious faults, as well as disputes on the fitness of the goods to the order. Our design is a part of a layered architecture for secure e-commerce applications [1], with precise yet general-purpose interfaces, agreements and validation functions (e.g. automatically resolving disputes on quality or fitness of goods). The modular design of the protocol and specifications, allows usage as an underlying service to different e-commerce, e-banking and other distributed systems. Our protocol operates efficiently, reliably and securely under realistic failure and delay conditions.
Amir Herzberg, Igal Yoffe
Balancing Accountability and Privacy Using E-Cash (Extended Abstract)
Abstract
In an electronic cash (e-cash) system, a user can withdraw coins from the bank, and then spend each coin anonymously and unlinkably. For some applications, it is desirable to set a limit on the dollar amounts of anonymous transactions. For example, governments require that large transactions be reported for tax purposes. In this work, we present the first e-cash system that makes this possible without a trusted party. In our system, a user’s anonymity is guaranteed so long as she does not: (1) double-spend a coin, or (2) exceed the publicly-known spending limit with any merchant. The spending limit may vary with the merchant. Violation of either condition can be detected, and can (optionally) lead to identification of the user and discovery of her other activities. While it is possible to balance accountability and privacy this way using e-cash, this is impossible to do using regular cash.
Our scheme is based on our recent compact e-cash system. It is secure under the same complexity assumptions in the random-oracle model. We inherit its efficiency: 2ℓ coins can be stored in O(ℓ+k) bits and the complexity of the withdrawal and spend protocols is O(ℓ+k), where k is the security parameter.
Jan Camenisch, Susan Hohenberger, Anna Lysyanskaya

Public Key Encryption and Key Exchange

About the Security of MTI/C0 and MQV
Abstract
The main application of cryptography is the establishment of secure channels. The most classical way to achieve this goal is definitely the use of variants of the signed Diffie-Hellman protocol. It applies a signature algorithm on the flows of the basic Diffie-Hellman key exchange, in order to achieve authentication. However, signature-less authenticated key exchange have numerous advantages, and namely from the efficiency point of view. They are thus well-suited for some constrained environments. On the other hand, this efficiency comes at the cost of some uncertainty about the actual security.
This paper focuses on the two most famous signature-less authenticated key exchange protocols, MTI/C0 and MQV. While the formal security of MTI/C0 has never been studied, results for the plain MQV protocol are still debated. We point out algorithmic assumptions on which some security proofs can be built in the random oracle model. The stress is put on implementation aspects that must be properly dealt with in order to obtain the expected security.
Some formalizations about authenticated key exchange, and the generic model, are of independent interest.
Sébastien Kunz-Jacques, David Pointcheval
Chosen-Ciphertext Secure Threshold Identity-Based Key Encapsulation Without Random Oracles
Abstract
We describe the first identity-based key encapsulation mechanism with threshold key delegation and decapsulation that is secure in the standard model against chosen-ciphertext (CCA2) attacks. Our scheme is unconditionally consistent and proved secure under the Bilinear Decisional Diffie-Hellman assumption.
David Galindo, Eike Kiltz
A New Key Exchange Protocol Based on MQV Assuming Public Computations
Abstract
Designing authenticated key exchange algorithms is a problem well understood in cryptography: there are established security models, and proposals proved secure in these models. However, models currently used assume that a honest entity involved in a key exchange is trusted as a whole. In many practical contexts, the entity is divided in an authentication device storing a private key and having low computing power, and a computing device, that performs part of the computations required by protocol runs. The computing device might be a PC connected to the Internet, and the authenticating device a smart card. In that case as well in many others, a compromise of the computing device is to be expected. We therefore propose a variant of the MQV and HMQV key exchange protocols secure in that context, unlike the original protocols. The security claim is supported by a proof in a model derived from the Canetti-Krawczyk one, which takes into account more general rogue behaviours of the computing device.
Sébastien Kunz-Jacques, David Pointcheval

Secret Sharing

Ideal Secret Sharing Schemes Whose Minimal Qualified Subsets Have at Most Three Participants
Abstract
One of the main open problems in secret sharing is the characterization of the access structures of ideal secret sharing schemes. As a consequence of the results by Brickell and Davenport, every one of those access structures is related in a certain way to a unique matroid. We study this open problem for access structures with rank three, that is, structures whose minimal qualified subsets have at most three participants. We prove that all access structures with rank three that are related to matroids with rank greater than three are ideal. After the results in this paper, the only open problem in the characterization of the ideal access structures with rank three is to characterize the matroids with rank three that can be represented by an ideal secret sharing scheme.
Jaume Martí-Farré, Carles Padró
Cheating Immune (2,n)-Threshold Visual Secret Sharing
Abstract
Cheating in secret sharing has been considered in several papers. Recently cheating in visual cryptography has been considered in [10], where (2,n)-threshold visual cryptography schemes are provided. In this paper we provide new (2,n)-threshold visual cryptography schemes. Our model is different from the one considered in [10]; in particular we aim at constructing cheating immune schemes without the use of extra information, like additional shares or images as done in [10]. We have provided a formal definition of cheating which requires that a group of cheaters be able to deterministically force a honest participant to reconstruct a wrong secret. The (2,n)-threshold schemes that we provide do not allow such cheating, regardless of the number of cheaters.
Roberto De Prisco, Alfredo De Santis
Rational Secret Sharing, Revisited
Abstract
We consider the problem of secret sharing among n rational players. This problem was introduced by Halpern and Teague (STOC 2004), who claim that a solution is impossible for n=2 but show a solution for the case n≥3. Contrary to their claim, we show a protocol for rational secret sharing among n=2 players; our protocol extends to the case n≥3, where it is simpler than the Halpern-Teague solution and also offers a number of other advantages. We also show how to avoid the continual involvement of the dealer, in either our own protocol or that of Halpern and Teague.
Our techniques extend to the case of rational players trying to securely compute an arbitrary function, under certain assumptions on the utilities of the players.
S. Dov Gordon, Jonathan Katz

Symmetric Key Cryptanalysis and Randomness

On the Security of HMAC and NMAC Based on HAVAL, MD4, MD5, SHA-0 and SHA-1 (Extended Abstract)
Abstract
HMAC is a widely used message authentication code and a pseudorandom function generator based on cryptographic hash functions such as MD5 and SHA-1. It has been standardized by ANSI, IETF, ISO and NIST. HMAC is proved to be secure as long as the compression function of the underlying hash function is a pseudorandom function. In this paper we devise two new distinguishers of the structure of HMAC, called differential and rectangle distinguishers, and use them to discuss the security of HMAC based on HAVAL, MD4, MD5, SHA-0 and SHA-1. We show how to distinguish HMAC with reduced or full versions of these cryptographic hash functions from a random function or from HMAC with a random function. We also show how to use our differential distinguisher to devise a forgery attack on HMAC. Our distinguishing and forgery attacks can also be mounted on NMAC based on HAVAL, MD4, MD5, SHA-0 and SHA-1.
Jongsung Kim, Alex Biryukov, Bart Preneel, Seokhie Hong
Distinguishing Stream Ciphers with Convolutional Filters
Abstract
This paper presents a new type of distinguisher for the shrinking generator and the alternating-step generator with known feedback polynomial and for the multiplexor generator. For the former the distinguisher is more efficient than existing ones and for the latter it results in a complete breakdown of security. The distinguisher is conceptually very simple and lends itself to theoretical analysis leading to reliable predictions of its probability of success.
Joan Daemen, Gilles Van Assche
On Statistical Testing of Random Numbers Generators
Abstract
Maurer’s test is nowadays a basic statistical tool for testing physical random number generators in cryptographic applications. Based on a statistical analysis of this test we propose simple and effective methods for its improvement. These methods are related to the m – spacing technique common in goodness-of-fit problems and the L – leave out method used for a noise reduction in the final Maurer test statistic. We also show that the spacing distribution test represents a serious competitor for Maurer’s test in the case when the random number generator is governed by a Markov chain with a long memory.
F. El Haje, Y. Golubev, P. -Y. Liardet, Y. Teglia

Applied Authentication

Lightweight Email Signatures (Extended Abstract)
Abstract
We present Lightweight Email Signatures (LES), a simple cryptographic architecture for authenticating email. LES is an extension of DKIM, the recent IETF effort to standardize domain-based email signatures. LES shares DKIM’s ease of deployment: they both use the DNS to distribute a single public key for each domain. Importantly, LES supports common uses of email that DKIM jeopardizes: multiple email personalities, firewalled ISPs, incoming-only email forwarding services, and other common uses that often require sending email via a third-party SMTP server. In addition, LES does not require DKIM’s implied intra-domain mechanism for authenticating users when they send email.
LES provides these features using identity-based signatures. Each domain authority generates a master keypair, publishes the public component in the DNS, and stores the private component securely. Using this private component, the authority delivers to each of its users, via email, an individual secret key whose identity string corresponds to the user’s email address. A sender then signs messages using this individual secret key. A recipient verifies such a signature by querying the appropriate master public key from the DNS, computing the sender’s public key, and verifying the signature accordingly. As an added bonus, the widespread availability of user-level public keys enables deniable authentication, such as ring signatures. Thus, LES provides email authentication with optional repudiability.
We built a LES prototype to determine its practicality. Basic user tests show that the system is relatively easy to use, and that cryptographic performance, even when using deniable authentication, is well within acceptable range.
Ben Adida, David Chau, Susan Hohenberger, Ronald L. Rivest
Shoehorning Security into the EPC Tag Standard
Abstract
The EPCglobal Class-1 Generation-2 UHF tag standard is certain to become the de facto worldwide specification for inexpensive RFID tags. Because of its sharp focus on simple “license plate” tags, it supports only the most rudimentary of security and privacy features, and essentially none of the cryptographic techniques that underpin authentication and privacy-protection in higher-powered computational devices. To support more-sophisticated applications, the drafters of this standard envisioned the re-use of the basic air interface and command set in higher-class standards. We propose ways to incorporate mainstream cryptographic functionality into the Class-1 Gen-2 standard. Our techniques circumvene the intended modes of operation of the standard, but adhere closely enough to preserve formal compliance. For this reason, we use the term shoehorning to describe our layering of new security functionality on the standard.
Daniel V. Bailey, Ari Juels
Proof-Carrying Proxy Certificates
Abstract
The term proxy certificate is used to describe a certificate that is issued by an end user for the purpose of delegating responsibility to another user so that the latter can perform certain actions on behalf of the former. Such certificates have been suggested for use in a number of applications, particularly in distributed computing environments where delegation of rights is common. In this paper, we present a new concept called proof-carrying proxy certificates. Our approach allows to combine the verification of the validity of the proxy certificate and the authorization decision making in an elegant way that enhances the privacy of the end user. In contrast with standard proxy certificates that are generated using standard (public-key) signature schemes, the proposed certificates are generated using a signature scheme for which the validity of a generated signature proves the compliance of the signer with a credential-based policy. We present a concrete realization of our approach using bilinear pairings over elliptic curves and we prove its security under adapted attack models.
Walid Bagga, Stefano Crosta, Refik Molva

Public Key Related Cryptanalysis

Cryptanalysis of Rainbow
Abstract
Rainbow is a fast asymmetric multivariate signature algorithm proposed by J. Ding and D. Schmidt in [5]. This paper presents a cryptanalysis of Rainbow which enables an attacker provided with the public key to recover an equivalent representation of the secret key, thus allowing her to efficiently forge a signature of any message. For the set of parameter values recommended by the authors of Rainbow in order to achieve a security level strictly higher than 280, the complexity of our attack is less than 271 operations. This is 240 times less than the complexity of the best known attack used by the authors to dimension their system.
Olivier Billet, Henri Gilbert
An Improved LPN Algorithm
Abstract
HB +  is a shared-key authentication protocol, proposed by Juels and Weis at Crypto 2005, using prior work of Hopper and Blum. Its very low computational cost makes it attractive for low-cost devices such as radio-frequency identification(RFID) tags. Juels and Weis gave a security proof, relying on the hardness of the “learning parity with noise” (LPN) problem. Here, we improve the previous best known algorithm proposed by Blum, Kalai, and Wasserman for solving the LPN problem. This new algorithm yields an attack for HB +  in the detection-based model with work factor 252.
Éric Levieil, Pierre-Alain Fouque

Invited Talk

Theory and Practice of Multiparty Computation
Abstract
This is a short summary of the invited talk given by the author at the SCN conference.
Ivan Damgård
Backmatter
Metadata
Title
Security and Cryptography for Networks
Editors
Roberto De Prisco
Moti Yung
Copyright Year
2006
Publisher
Springer Berlin Heidelberg
Electronic ISBN
978-3-540-38081-8
Print ISBN
978-3-540-38080-1
DOI
https://doi.org/10.1007/11832072

Premium Partner

    Image Credits