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

2005 | Book

ECRYPT: The Cryptographic Research Challenges for the Next Decade Read chapter Read first chapter

Security in Communication Networks

4th International Conference, SCN 2004, Amalfi, Italy, September 8-10, 2004, Revised Selected Papers

Editors: Carlo Blundo, Stelvio Cimato

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 4th International Conference on Security in Communication Networks 2004 (SCN2004)washeldatthe“DioceseHall”oftheArchdioceseofAmal?-Cavade’ Tirreni and the “Armorial Bearings Hall” of the Archbishop Palace in Amal?, Italy, on September 8–10, 2004. Previous conferences also took place in Amal? in 1996, 1999 and 2002. The conference aimed at bringing together researchers in the ?elds of cr- tography and security in communication networks to foster cooperation and the exchange of ideas. The main topics included all technical aspects of data security, including: anonymity,authentication,blockciphers,complexity-basedcryptography,cry- analysis, digital signatures, distributed cryptography, hash functions, identi?- tion,implementations,keydistribution,privacy,publickeyencryption,threshold cryptography, and zero knowledge. The Program Committee, consisting of 21 members, considered 79 papers and selected 26 for presentation; one of them was withdrawn by the authors. These papers were selected on the basis of originality, quality and relevance to cryptography and security in communication networks. Due to the high number of submissions, paper selection was a di?cult and challenging task, and many good submissions had to be rejected. Each subm- sion was refereed by at least three reviewers and some had four reports or more. We are very grateful to all the program committee members, who devoted much e?ort and valuable time to read and select the papers. In addition, we gratefully acknowledge the help of colleagues who reviewed submissions in their areas of expertise. They are all listed on page VII and we apologize for any inadvertent omissions. These proceedings include the revised versions of the 26 accepted papers andtheabstractoftheinvitedtalkbyBartPreneel(ECRYPT:theCryptographic Research Challenges for the Next Decade).

Table of Contents

Frontmatter

Invited Talk

ECRYPT: The Cryptographic Research Challenges for the Next Decade
Abstract
In the past thirty years, cryptology has evolved from a secret art to a modern science. Weaker algorithms and algorithms with short keys are disappearing, political controls of cryptography have been reduced, and secure cryptography is becoming more and more a commodity. Moreover, implementations are being becoming more secure as well. This progress may lead to the belief that the cryptography problem is “solved.” However, this article discusses some of the challenging problems ahead in the area of cryptographic algorithms and protocols. We also explain how the ECRYPT Network of Excellence (www.ecrypt.eu.org) tries to address some of the challenges by bringing together 250 European researchers in the area of cryptology and the related area of watermarking.
B. Preneel

Reduction of Security/Primitives

Relationships Between Diffie-Hellman and “Index Oracles”
Abstract
The Computational Diffie-Hellman problem and its decisional variant are at the heart of many cryptographic applications. Yet, their exact computational power and their relationship to the Discrete Logarithm problem and the Decision Diffie-Hellman problem (DDH) is not fully understood in all settings. In order to extend the current understanding of the problem we introduce a new decision problem that we call the Jacobi Discrete Logarithm problem. We argue that this is a natural problem and we analyze it in groups in which Decision Diffie-Hellman (DDH) is believed to be intractable. In short, the JDL problem is to return the Jacobi symbol of the exponent x in g x . We show that JDL is random self-reducible and that it lies in between the Computational Diffie-Hellman (CDH) problem and DDH. Our analysis involves the notion of a powering oracle. Maurer and Wolf showed that a squaring oracle that returns \(g^{u^2}\) on input g u is actually equivalent to a DH oracle. It is weaker in the sense that it can be posed as a specialized DH oracle that need only respond correctly when u = v. In this paper we extend the study of the relationships between Diffie-Hellman and oracles for problems which manipulate or give partial information about the index of their input. We do so by presenting a reduction that shows that a powering oracle that responds with \(g^{u^a} mod P\) when given g u for an unknown a that is poly-logarithmic in p, is equivalent to DH. Technically, our reduction utilizes the inverse of a particular type of Vandermonde matrix. This inverse matrix has recursively defined entries. Implications for large values of a are also given.
Adam Young, Moti Yung
On the Security Notions for Public-Key Encryption Schemes
Abstract
In this paper, we revisit the security notions for public-key encryption, and namely indistinguishability. We indeed achieve the surprising result that no decryption query before receiving the challenge ciphertext can be replaced by queries (whatever the number is) after having received the challenge, and vice-versa. This remark leads to a stricter and more complex hierarchy for security notions in the public-key setting: the (i,j)-IND level, in which an adversary can ask at most i (j resp.) queries before (after resp.) receiving the challenge. Excepted the trivial implications, all the other relations are strict gaps, with no polynomial reduction (under the assumption that IND-CCA2 secure encryption schemes exist.) Similarly, we define different levels for non-malleability (denoted (i,j)-NM.)
Duong Hieu Phan, David Pointcheval
Efficient Unconditional Oblivious Transfer from Almost Any Noisy Channel
Abstract
Oblivious transfer (OT) is a cryptographic primitive of central importance, in particular in two- and multi-party computation. There exist various protocols for different variants of OT, but any such realization from scratch can be broken in principle by at least one of the two involved parties if she has sufficient computing power—and the same even holds when the parties are connected by a quantum channel. We show that, on the other hand, if noise—which is inherently present in any physical communication channel—is taken into account, then OT can be realized in an unconditionally secure way for both parties, i.e., even against dishonest players with unlimited computing power. We give the exact condition under which a general noisy channel allows for realizing OT and show that only “trivial” channels, for which OT is obviously impossible to achieve, have to be excluded. Moreover, our realization of OT is efficient: For a security parameter α > 0—an upper bound on the probability that the protocol fails in any way—the required number of uses of the noisy channel is of order O(log(1/ α)2 + ε) for any ε > 0.
Claude Crépeau, Kirill Morozov, Stefan Wolf

Signature Schemes

A Provably Secure Short Transitive Signature Scheme from Bilinear Group Pairs
Abstract
We present a realization of the transitive signature scheme based on the algebraic properties of bilinear group pairs. The scheme is proven secure, i.e. transitively unforgeable under adaptive chosen message attack, assuming hardness of the computational co-Diffie-Hellman problem in bilinear group pairs and the security of the underlying standard signature scheme under known message attack. Our scheme mostly conforms to previously designed schemes of Micali-Rivest and Bellare-Neven in structure; yet there are two contributions: firstly, we take advantage of bilinear group pairs which were previously used by Boneh, Lynn, and Shacham to build short signature schemes. Secondly, we show that a slight modification in previous definitions of the transitive signature relaxes the security requirement for the underlying standard signature from being secure under chosen message attack to being secure under known message attack; thus shorter and more efficient signatures can be chosen for the underlying standard signature. These two facts eventually yield to short transitive signatures with respect to both node and edge signature size.
Siamak Fayyaz Shahandashti, Mahmoud Salmasizadeh, Javad Mohajeri
Group Signatures with Separate and Distributed Authorities
Abstract
We propose a new group signature scheme that simultaneously provides the following two properties : (1) the membership authority is able to add a user but not to identify an actual signer, while the tracing authority is able to identify the actual signer but not to add a user, (2) for further decentralization, these two authorities are respectively distributed among multiple entities in a manner efficient enough for practical applications. Previous group signature schemes have only offered one or the other of these two properties. Further, we formalize the security properties.
Jun Furukawa, Shoko Yonezawa
Threshold Cryptography in Mobile Ad Hoc Networks
Abstract
The area of Threshold Cryptography investigates the design and analysis of protocols that distribute, in wired networks, cryptographic actions usually performed by a single party into multi-party variants, where the original action is successfully performed only if at least a certain threshold of the participants are available and not corrupted. As of today, several examples of threshold cryptographic protocols (e.g., signatures, public-key cryptosystems, zero-knowledge protocols, etc.) are being investigated in the Cryptography literature.
We note that the impact of the Threshold Cryptography paradigm is of even greater importance to study the security of other types of communication networks, such as Mobile Ad Hoc Networks, where the existence and availability of trusted authorities is severely limited by intrinsic network features, and problems such as avoiding a “single point of failure”, or, more generally, “service availability”, become crucial.
In this paper we formalize, investigate and present satisfactory solutions for the general problem of Threshold Cryptography in Mobile Ad Hoc Networks. Although we restrict our study to the cryptographic operation of digital signatures schemes, our definitional approaches can be extended to most other cryptographic actions studied in Threshold Cryptography.
Giovanni Di Crescenzo, Gonzalo Arce, Renwei Ge

Anonymity and Privacy

Designated Verifier Signatures: Anonymity and Efficient Construction from Any Bilinear Map
Abstract
The concept of Designated Verifier Signatures (DVS) was introduced by Jakobsson, Sako and Impagliazzo at Eurocrypt’96. These signatures are intended to a specific verifier, who is the only one able to check their validity. In this context, we formalize the notion of privacy of signer’s identity which captures the strong designated verifier property investigated in their paper. We propose a variant of the pairing-based DVS scheme introduced at Asiacrypt’03 by Steinfeld, Bull, Wang and Pieprzyk. Contrary to their proposal, our new scheme can be used with any admissible bilinear map, especially with the low cost pairings and achieves the new anonymity property (in the random oracle model). Moreover, the unforgeability is tightly related to the Gap-Bilinear Diffie-Hellman assumption, in the random oracle model and the signature length is around 75% smaller than the original proposal.
Fabien Laguillaumie, Damien Vergnaud
Group Signatures: Better Efficiency and New Theoretical Aspects
Abstract
A group signature scheme allows members of a group to anonymously sign messages. To counter misuse, the anonymity can be revoked by the so-called group manager.
This paper contributes two results to the area of group signatures. First, we improve the state-of-the-art scheme by Ateniese et al. by an order of magnitude. Our new scheme satisfies the recent security definition by Bellare et al. Second, and of a more theoretical nature, we study the Bellare et al. definitions and show that their notion of full-anonymity may require stronger assumptions than what is needed to achieve a relaxed but reasonable notion of anonymity.
Jan Camenisch, Jens Groth
Efficient Blind Signatures Without Random Oracles
Abstract
The only known blind signature scheme that is secure in the standard model [19] is based on general results about multi-party computation, and thus it is extremely inefficient. The main result of this paper is the first provably secure blind signature scheme which is also efficient. We develop our construction as follows. In the first step, which is a significant result on its own, we devise and prove the security of a new variant for the Cramer-Shoup-Fischlin signature scheme. We are able to show that for generating signatures, instead of using randomly chosen prime exponents one can securely use randomly chosen odd integer exponents which significantly simplifies the signature generating process. We obtain our blind signing function as a secure and efficient two-party computation that cleverly exploits its algebraic properties and those of the Paillier encryption scheme. The security of the resulting signing protocol relies on the Strong RSA assumption and the hardness of decisional composite residuosity; we stress that it does not rely on the existence of random oracles.
Jan Camenisch, Maciej Koprowski, Bodgan Warinschi

Authentication and Identification

Minimalist Cryptography for Low-Cost RFID Tags (Extended Abstract)
Abstract
A radio-frequency identification (RFID) tag is a small, inexpensive microchip that emits an identifier in response to a query from a nearby reader. The price of these tags promises to drop to the range of $0.05 per unit in the next several years, offering a viable and powerful replacement for barcodes.
The challenge in providing security for low-cost RFID tags is that they are computationally weak devices, unable to perform even basic symmetric-key cryptographic operations. Security researchers often therefore assume that good privacy protection in RFID tags is unattainable. In this paper, we explore a notion of minimalist cryptography suitable for RFID tags. We consider the type of security obtainable in RFID devices with a small amount of rewritable memory, but very limited computing capability. Our aim is to show that standard cryptography is not necessary as a starting point for improving security of very weak RFID devices. Our contribution is twofold:
1
We propose a new security model for authentication and privacy in RFID tags. This model takes into account the natural computational limitations and the likely attack scenarios for RFID tags in real-world settings. It represents a useful divergence from standard cryptographic security modeling, and thus a new basis for practical formalization of minimal security requirements for low-cost RFID-tag security.
 
2
We describe a protocol that provably achieves the properties of authentication and privacy in RFID tags in our proposed model, and in a good practical sense. It involves no computationally intensive cryptographic operations, and relatively little storage.
 
Ari Juels
On the Key Exposure Problem in Chameleon Hashes
Abstract
Chameleon signatures were introduced by Krawczyk and Rabin, being non-interactive signature schemes that provide non-transferability. However, that first construction employs a chameleon hash that suffers from a key exposure problem: The non-transferability property requires willingness of the recipient in consequentially exposing a secret key, and therefore invalidating all signatures issued to the same recipient’s public key. To address this key-revocation issue, and its attending problems of key redistribution, storage of state information, and greater need for interaction, an identity-based scheme was proposed in [1], while a fully key-exposure free construction, based on the elliptic curves with pairings, appeared later in [7].
Herein we provide several constructions of exposure-free chameleon hash functions based on different cryptographic assumptions, such as the RSA and the discrete logarithm assumptions. One of the schemes is a novel construction that relies on a single trapdoor and therefore may potentially be realized over a large set of cryptographic groups (where the discrete logarithm is hard).
Giuseppe Ateniese, Breno de Medeiros

Zero Knowledge

Identity-Based Zero-Knowledge
Abstract
We introduce and define the notion of identity-based zero-knowledge, concentrating on the non-interactive setting. In this setting, our notion allows any prover to widely disseminate a proof of a statement while protecting the prover from plagiarism in the following sense: although proofs are transferable (i.e., publicly verifiable), they are also bound to the identity of the prover in a way which is recognizable to any verifier. Furthermore, an adversary is unable to change this identity (i.e., to claim the proof as his own, or to otherwise change the authorship), unless he could have proved the statement on his own.
While we view the primary contribution of this work as a formal definition of the above notion, we also explore the relation of this notion to that of non-malleable (non-interactive) zero-knowledge. On the one hand, we show that these two notions are incomparable: that is, there are proof systems which are non-malleable but not identity-based, and vice versa. On the other hand, we show that a proof system of either type essentially implies a proof system of the other type.
Jonathan Katz, Rafail Ostrovsky, Michael O. Rabin

Public Key Cryptosystems

A Robust Multisignature Scheme with Applications to Acknowledgement Aggregation
Abstract
A multicast communication source often needs to securely verify which multicast group members have received a message, but verification of individually signed acknowledgments from each member would impose a significant computation and communication cost. As pointed out by Nicolosi and Mazieres [NM04], such cost is minimized if the intermediate nodes along the multicast distribution tree aggregate the individual signatures generated by the multicast receivers into a single multisignature.
While the solution of [NM04], based on a multisignature scheme of Boldyreva [Bol03], relied on so-called “Gap Diffie-Hellman” groups, we propose a solution using a multisignature scheme which is secure under just the discrete logarithm assumption. However, unlike the previously known discrete-log based multisignature scheme of Micali et al. [MOR01a], our multisignature scheme is robust, which allows for an efficient multisignature generation even in the presence of (possibly malicious) node and communication failures.
Claude Castelluccia, Stanisław Jarecki, Jihye Kim, Gene Tsudik
Efficient Key Encapsulation to Multiple Parties
Abstract
We present the notion of an mKEM, which is a Key Encapsulation Mechanism (KEM) which takes multiple public keys as input. This has applications where one wishes to encrypt a single large document to a set of multiple recipients, as when one sends an encrypted email to more than one person. We present a security definition and show that the naive approach to implementing an mKEM is secure under this definition. We then go on to present a more efficient construction of an mKEM, which is secure in the random oracle model.
N. P. Smart
Improved Signcryption from q-Diffie-Hellman Problems
Abstract
This paper proposes a new public key authenticated encryption (signcryption) scheme based on the hardness of q-Diffie-Hellman problems in Gap Diffie-Hellman groups. This new scheme is quite efficient: the signcryption operation has almost the same cost as an El Gamal encryption while the reverse operation only requires one pairing evaluation and three exponentiations. The scheme’s chosen-ciphertext security is shown to be related to the hardness of the q-Diffie-Hellman Inversion (q–DHI) problem in the random oracle model while its unforgeability is proved under the q-Strong Diffie-Hellman assumption (q-SDH). It also provides detachable signatures that are unlinkable to the original anonymous ciphertext. We also show that most of the sender’s workload can be computed offline. Our construction is based on a signature scheme independently studied by Boneh-Boyen and Zhang et al. in 2004.
Benoît Libert, Jean-Jacques Quisquater

Distributed Cryptography

Colored Visual Cryptography Without Color Darkening
Abstract
Visual cryptography schemes allow the encoding of a secret image into shares, in the form of transparencies, which are distributed to the participants. The shares are such that only qualified subsets of participants can visually recover the secret image by superimposing the transparencies.
In this paper we study colored visual cryptography schemes. Most of previous work on colored visual cryptography allows the superposition of pixels having the same color assuming that the resulting pixel still has the same color. This is not what happens in reality since when superimposing two pixels of the same color one gets a darker version of that color, which effectively is a different color. Superimposing many pixels of the same color might result in a so dark version of the color that the resulting pixel might be not distinguishable from a black pixel.
Thus we propose a model where the reconstruction has to guarantee that the reconstructed secret pixel has the same color of the original one and not a darker version of it. We give a construction of c-color (k,n)-threshold visual cryptography schemes. Since we have to guarantee the reconstruction of the exact original color, in many cases our schemes have a bigger pixel expansion than previous ones. However, for the case of k = n, we get a smaller pixel expansion when compared with schemes that to do not guarantee the exact reconstruction of the original color. We also prove that, in the model introduced in this paper, our schemes for k = n have optimal pixel expansion.
S. Cimato, R. De Prisco, A. De Santis
On the Size of Monotone Span Programs
Abstract
Span programs provide a linear algebraic model of computation. Monotone span programs (MSP) correspond to linear secret sharing schemes. This paper studies the properties of monotone span programs related to their size. Using the results of van Dijk (connecting codes and MSPs) and a construction for a dual monotone span program proposed by Cramer and Fehr we prove a non-trivial upper bound for the size of monotone span programs. By combining the concept of critical families with the dual monotone span program construction of Cramer and Fehr we improve the known lower bound with a constant factor, showing that the lower bound for the size of monotone span programs should be approximately twice as large. Finally, we extend the result of van Dijk showing that for any MSP there exists a dual MSP such that the corresponding codes are dual.
Ventzislav Nikov, Svetla Nikova, Bart Preneel
Universally Composable DKG with Linear Number of Exponentiations
Abstract
Until now no distributed discrete-logarithm key generation (DKG) protocol is known to be universally composable. We extend Feldman’s verifiable secret sharing scheme to construct such a protocol. Our result holds for static adversaries corrupting a minority of the parties under the Decision Diffie-Hellman assumption in a weak common random string model in which the simulator does not choose the common random string.
Our protocol is optimistic. If all parties behave honestly, each party computes O(3.5k) exponentiations, and otherwise each party computes O(k 2) exponentiations, where k is the number of parties. In previous constructions each party always computes Ω(k 2) exponentiations.
Douglas Wikström

Cryptanalysis of Public Key Cryptosystems

An Algebraic Approach to NTRU (q = 2 n ) via Witt Vectors and Overdetermined Systems of Nonlinear Equations
Abstract
We use the theory of Witt vectors to develop an algebraic approach for studying the NTRU primitive with q parameter equal to a power of two. This results in a system of nonlinear algebraic equations over \(\mathbb{F}_{2}\) having many symmetries, which is reminiscent of the approach of Courtois, Murphy, Pieprzyk, Robshaw and others for studying the structure of block ciphers such as the AES. We study whether this approach to NTRU provides any immediate security threat and conclude that under the most favourable assumptions, the method is of asymptotic interest but is completely impractical at current or likely future parameter sizes.
J. H. Silverman, N. P. Smart, F. Vercauteren
Efficient Cryptanalysis of RSE(2)PKC and RSSE(2)PKC
Abstract
In this paper, we study the new class step-wise Triangular Schemes (STS) of public key cryptosystems (PKC) based on multivariate quadratic polynomials. In these schemes, we have m the number of equations, n the number of variables, L the number of steps/layers, r the number of equations/variables per step, and q the size of the underlying field. We present two attacks on the STS class by exploiting the chain of the kernels of the private key polynomials. The first attack is an inversion attack which computes the message/signature for given ciphertext/message in O(mn 3 Lq r + n 2 Lrq r ), the second is a structural attack which recovers an equivalent version of the secret key in O(mn 3 Lq r + mn 4) operations. Since the legitimate user has workload q r for decrypting/computing a signature, the attacks presented in this paper are very efficient. As an application, we show that two special instances of STS, namely RSE(2)PKC and RSSE(2)PKC, recently proposed by Kasahara and Sakai, are insecure.
Christopher Wolf, An Braeken, Bart Preneel

Cryptanalysis

The Decimated Sample Based Improved Algebraic Attacks on the Nonlinear Filters
Abstract
This paper proposes an improved approach for cryptanalysis of keystream generators based on a composition of a linear finite state machine (LFSM) and nonlinear mapping. The main feature of the proposed approach is that it is based on identification and selection for further processing certain suitable positions in the given sample so that only the decimated sample elements are relevant for the attacking. In a number of scenarios this yields a significant gain in the performance sometimes at the expense of a longer sample required or/and the pre-processing cost. The proposed approach employs novel methods for constructing the underlying overdefined system of equations relevant for the attacks and solving the system under a set of the hypothesis. Oppositely to the previously reported methods, the proposed ones also identify and use certain characteristics of the LFSM state-transition matrix in order to reduce the nonlinearity of the system. The novel construction of the equations yields a possibility for the trade-off between the required sample, pre-processing and processing complexity of the cryptanalysis. The pre-processing phase of the developed algorithm for cryptanalysis yields a collection of the output bit positions which are suitable for reducing the equations nonlinearity. The processing phase employs the output bits from the identified collection and it includes an exhaustive search over a subset of the secret key bits.
Miodrag J. Mihaljević, Hideki Imai
Non-randomness of the Full 4 and 5-Pass HAVAL
Abstract
HAVAL is a cryptographic hash function proposed in 1992 by Zheng, Pieprzyk and Seberry. Its structure is quite similar to other widely used hash functions such as MD5 and SHA-1. The specification of HAVAL includes a security parameter: the number of passes (that is, the number of times that a particular word of the message is used in the computation) which can be chosen equal to 3, 4 or 5. In this paper we cryptanalyze the compression functions of the 4-pass and the 5-pass HAVAL using differential cryptanalysis. We show that each of these two functions can be distinguished from a truly random function.
Hirotaka Yoshida, Alex Biryukov, Christophe De Cannière, Joseph Lano, Bart Preneel

Email Security

Controlling Spam by Secure Internet Content Selection
Abstract
Unsolicited and undesirable e-mail (spam) is a growing problem for Internet users and service providers. We present the Secure Internet Content Selection (SICS) protocol, an efficient cryptographic mechanism for spam-control, based on allocation of responsibility (liability). With SICS, e-mail is sent with a content label, and a cryptographic protocol ensures labels are authentic and penalizes falsely labeled e-mail (spam). The protocol supports trusted senders (penalized by loss of trust) and unknown senders (penalized financially). The recipient can determine the compensation amount for falsely labeled e-mail (spam). SICS is practical, with negligible overhead, gradual adoption path, and use of existing relationships; it is also flexible and appropriate for most scenarios, including deployment by end users and/or ISPs and support for privacy (including encrypted e-mail) and legitimate, properly labeled commercial e-mail. SICS improves on other crypto-based proposals for spam controls, and complements non-cryptographic spam controls.
Amir Herzberg

Key Distribution and Feedback Shift Registers

On Session Identifiers in Provably Secure Protocols
Abstract
We examine the role of session identifiers (SIDs) in security proofs for key establishment protocols. After reviewing the practical importance of SIDs we use as a case study the three-party server-based key distribution (3PKD) protocol of Bellare and Rogaway, proven secure in 1995. We show incidentally that the partnership function used in the existing security proof is flawed. There seems to be no way to define a SID for the 3PKD protocol that will preserve the proof of security. A small change to the protocol allows a natural definition for a SID and we prove that the new protocol is secure using this SID to define partnering.
Kim-Kwang Raymond Choo, Colin Boyd, Yvonne Hitchcock, Greg Maitland
How to Embed Short Cycles into Large Nonlinear Feedback-Shift Registers
Abstract
We construct nonlinear feedback shift registers with short cycles. Our method is to embed nonlinear feedback shift registers with small state spaces into nonlinear feedback shift registers with large state spaces. Algebraic analysis of our embedding indicates that detecting the embedded ‘small’ feedback shift register in the large feedback register is infeasible without additional information. As an application we propose a low-cost group-identification scheme.
Le Van Ly, Werner Schindler
Backmatter
Metadata
Title
Security in Communication Networks
Editors
Carlo Blundo
Stelvio Cimato
Copyright Year
2005
Publisher
Springer Berlin Heidelberg
Electronic ISBN
978-3-540-30598-9
Print ISBN
978-3-540-24301-4
DOI
https://doi.org/10.1007/b105083

Premium Partner

    Image Credits