Search

The binary linear feedback shift register sequences of degree n and maximum period p = 2n − 1 (the m-sequences) are useful in numerous applications because, although deterministic, they satisfy a number of interesting "randomness properties". An important open question is whether a binary sequence of period p = 2n − 1 with both the span-n property and the two-level correlation property must be an m-sequence. There is a direct correspondence between m-sequences of degree n and primitive polynomials of degree n over GF(2). Several conjectures are presented about primitive polynomials with a bounded number of terms. [ABSTRACT FROM AUTHOR]

The filter generator consists of a linear feedback shift register (LFSR) and a Boolean filtering function that combines some bits from the shift register to create a key stream. A new attack on the filter generator has recently been described by Rønjom and Helleseth [6]. This paper gives an alternative and extended attack to reconstruct the initial state of the LFSR using the underlying subspace structure of the filter sequence. This improved attack provides further insight and more flexibility in performing the attack by Rønjom and Helleseth. The main improvements are that this attack does not use the coefficient sequences that were fundamental in the previous attack and also works in the unlikely cases when the original attack needed some modifications. [ABSTRACT FROM AUTHOR]

Any span n sequences can be regarded as filtering sequences. From this observation, new randomness criteria for span n sequences are proposed. It is proved that the feedback function of a span n sequence can be represented as a composition of its trace representation, or equivalently, its discrete Fourier transform, and a permutation from the state space of the sequence to the multiplicative group of the finite field GF(2n), and vice versa. Significant enhancements for randomness of span n sequences, so that de Bruijn sequences, are illustrated by some examples. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the existence of modular sonar sequences of length v and mod v where v is a product of twin primes. For v = 3·5 = 15, we have found some old and new examples by exhaustive search. However, the very next case v = 5·7 = 35 is completely open, in that neither we know (have) an example, nor we prove the nonexistence. We describe simply some approach to locate a single example of modular sonar sequences of length 35 and mod 35, assuming (or hoping) that one exists. [ABSTRACT FROM AUTHOR]

In this short note we introduce two new sequences defined using the sum of digits in the representation of an integer in a certain base. A connection to Niven numbers is proposed and some results are proven. [ABSTRACT FROM AUTHOR]

The filter generator is an important building block in many stream ciphers. The generator consists of a linear feedback shift register (LFSR) of length n and a Boolean filtering function of degree d that combines bits from the shift register and creates an output bit zt at any time t. A new attack on stream ciphers based on linear shift registers has recently been described by the authors in [3]. This attack is modified to stream ciphers based on any linear shift register and not only for LFSRs. The focal point of this paper is to present a linear description of the filter generator in terms of matrices. The filter generator is viewed entirely in terms of powers of a unique linear operator T together with a vector representing the filtering function. It is proved that T embodies the coefficient sequences described in [3]. Thus, interesting properties of the vector space (e.g. the dimension of the equation systems) generated by the filter generator can be analysed using theory of cyclic vector spaces, which very elegantly complements analysis in terms of the roots of the LFSR. [ABSTRACT FROM AUTHOR]

Two wideband physical-layer multiple access techniques for mobile telephony and data are compared: CDMA, which in one of several manifestations has been chosen for virtually all third generation cellular systems, and OFDM with MIMO, which seems to be the most favored for a future generation. We compare the Shannon capacities of the two and conclude that with appropriate processing CDMA and OFDM capacities are similar but that the latter may more effectively be combined with MIMO antennas to provide higher capacities. [ABSTRACT FROM AUTHOR]

We explore a connection between permutation polynomials of the form xrf(x(q − 1)/l) and cyclotomic mapping permutation polynomials over finite fields. As an application, we characterize a class of permutation binomials in terms of generalized Lucas sequences. [ABSTRACT FROM AUTHOR]

One of the most important research areas in coding theory is weight enumeration. This is a large subject, but the basic problem is easily stated: determine or estimate the weight enumerator (B0..., Bn) for an (n,k) binary linear code, specified by a (n − k) ×n parity-check matrix $\mathcal{H}$ with entries from GF(2). Here $$B_i = \# \{c \in {GF(2)}^n: \mathcal{H}c^T = 0, {\mathop{\rm wt}}(c = i)\},$$ where ${\mathop{\rm wt}}(c)$ is the weight of the vector c. If the number of codewords is large, the logarithmic weight enumerator, i.e., $$ ({1 \over n}\log B_0, \ldots, {1 \over n}\log B_n)$$ is more convenient. If a code belongs to a family of codes which share similar properties, the log-weight enumerator may approach a limiting function called the spectral shape: $${1 \over n} \log\left(B_{\lfloor\theta n\rfloor}\right)\rightarrow E(\theta), \qquad 0 < \theta <1.$$ In modern coding theory, $\mathcal{H}$ is usually very large and very sparse, e.g., the row and column sums are bounded as n → ∞. The corresponding codes are called low density parity-check codes. Often we are faced with large collections, or ensembles, of long LDPC codes, which share similar properties, in which case it may be difficult to find the spectral shape of an individual member of the ensemble, but relatively easy to calculate the ensemble average. [ABSTRACT FROM AUTHOR]

Single-track Gray codes are cyclic Gray codes with codewords of length n, such that all the n tracks which correspond to the n distinct coordinates of the codewords are cyclic shifts of the first track. These codes have advantages over conventional Gray codes in certain quantization and coding applications. We survey the main results on this problem, their connections to sequence design, and discuss some of the interesting open problems. [ABSTRACT FROM AUTHOR]

We study the asymptotic behavior of stream cipher security measures associated with algebraic feedback shift registers and feedback based on the ring $\mathbb Z [\sqrt{-2}]$. For non-periodic sequences we consider normalized $\sqrt{2}$-adic complexity and study the set of accumulation points for a fixed sequence. The the set of accumulation points is a closed subinterval of the real closed interval [0,1]. We see that this interval is of the form [B,1 − B] "most" of the time, and that all such intervals occur for some sequence. [ABSTRACT FROM AUTHOR]

SQ(n) is the maximum number of patterns that can sit on the n×n board where each pattern consists of n nonattacking Queens placed symmetrically around the center. Each square of the board has at most one Queen. Q(n) is the same except that "placed symmetrically around the center" is not required. [ABSTRACT FROM AUTHOR]

In phase-encoded optical CDMA (OCDMA) spreading is achieved by encoding the phase of signal spectrum. Here, a mathematical model for the output signal of a phase-encoded OCDMA system is first derived. This is shown to lead to a performance metric for the design of spreading sequences for asynchronous transmission. Generalized bent functions are used to construct a family of efficient phase-encoding sequences. It is shown how M-ary modulation of these spreading sequences is possible. The problem of designing efficient phase-encoded sequences is then related to the problem of minimizing PMEPR (peak-to-mean envelope power ratio) in an OFDM communication system. [ABSTRACT FROM AUTHOR]

Digital watermarking applications require constructions of double-periodic matrices with good correlations. More specifically we need as many matrix sequences as possible with both good auto- and cross-correlation. Furthermore it is necessary to have double-periodic sequences with as many dots as possible. We have written this paper with the specific intention of providing a theoretical framework for constructions for digital watermarking applications. In this paper we present a method that increases the number of sequences, and another that increases the number of ones keeping the correlation good and double-periodic. Finally we combine both methods producing families of double-periodic arrays with good correlation and many dots. The method of increasing the number of sequences is due to Moreno, Omrani and Maric. The method to increase the number of dots was started by Nguyen, Lázló and Massey, developed by Moreno, Zhang, Kumar and Zinoviev, and further developed by Tirkel and Hall. The very nice application to digital watermarking is due to Tirkel and Hall. Finally we obtain two new constructions of Optical Orthogonal Codes: Construction A which produces codes with parameters $(n, \omega, \lambda) =(p(p-1), {{p^2 - 1} \over {2}}, [{p(p+1) \over 4}])$ and Construction B which produces families of code with parameters $(n, \omega, \lambda) = (p^2(p-1), {{p^2 - 1} \over {2}}, [{p(p+1) \over 4}])$ and family size p + 1. [ABSTRACT FROM AUTHOR]

A motivation for this paper is to find a practical mechanism for generating permutations of a finite set of consecutive positive integers so that the resultant spacings between originally consecutive numbers i and i + i, are now different for each i. This is equivalent to finding complete Latin squares. The ordered set of spacings in such a permutation is called a sequencing. The set of partial sums of the terms in a sequencing is called a directed terrace. For lack of standard terminology, the associated permutations here are called quick trickles. This paper concerns methods of finding such sequencings, in part by finding constraints on their existence, so that search time can be substantially reduced. A second approach is to represent a quick trickle permutation as a directed graph. The sequencings then are represented by chords of different lengths. Various methods can be used to rearrange the chords and obtain additional sequencings and groups of quick trickle permutations. It is well known that complete Latin squares of size n ×n can be found if n is even but not if n is odd. This is equivalent to saying that the group of integers (1, 2, 3,..., n) under the operation of multiplication mod n is sequenceable if and only if n is even. A more general concept is introduced which is termed quasi-sequenceable. This applies to both even and odd sizes. The application to block encryption, or the so-called substitution permutation system is briefly described. The net result is interround mixing, deterministically generated under key control, and quickly replaceable with a new pattern of equal merit. Currently, typical block encryption systems use algorithms which are fixed and publicly known. The motivation here is to develop block encryption systems using algorithms which are variable, secret, generated and periodically changed by the key. [ABSTRACT FROM AUTHOR]

In this paper, for a positive odd integer n, a new family of binary sequences with 2n + 1 sequences of length 2n − 1 taking three level nontrivial correlations − 1 and − 1±2(n + 1)/2 is presented, whose correlation distribution is the same as that of the well-known Gold sequences. This family may be considered as a new class of Gold-like sequences. [ABSTRACT FROM AUTHOR]

Considered are quadratic p-ary bent functions having the form $f(x)={\rm Tr}_n(a x^{p^j+1})$. Described is the general Gold-like class of bent functions that covers all the previously known monomial quadratic cases. Obtained is the exact value of the Walsh transform coefficients for a bent function in this class. In particular, presented is an explicit expressions for a dual of a monomial quadratic bent function which is a bent functions on its own. This gives new examples of generalized bent functions not previously reported in the literature. The paper is the follow-up to Helleseth-Kholosha 2006. [ABSTRACT FROM AUTHOR]

The perfect binary sequence of period 4 − ‘0111' (or cyclic shifts of itself or its complement) − has the optimal periodic autocorrelation function where all out-of-phase values are zero. Not surprisingly, it is also the Barker sequence of length 4 where all out-of-phase aperiodic autocorrelation values have the magnitudes of at most one. From these observations, the applications of the sequence for low periodic and aperiodic autocorrelations are studied. First, the perfect sequence is discussed for binary sequences with optimal periodic autocorrelation. New binary sequences of period N = 4(2m − 1), m = 2k with optimal periodic autocorrelation are presented, which are obtained by a slight modification of product sequences of binary m-sequences and the perfect sequence. Then, it is observed that a product sequence of the Legendre and the perfect sequences has not only the optimal periodic but also the good aperiodic autocorrelations with the asymptotic merit factor 6. Moreover, if the product sequences replace Legendre sequences in Borwein, Choi, Jedwab (BCJ) sequences, or equivalently Kristiansen-Parker sequences (simply BCJ-KP sequences), numerical results show that the resulting sequences have the same asymptotic merit factor as the BCJ-KP sequences. [ABSTRACT FROM AUTHOR]

Let n be a positive integer. A nonzero element γ of the finite field F of order q = 2n is said to be "strongly primitive" if every element (aγ + b)/(cγ + d), with a,b,c,d in {0,1} and ad − bc not zero, is primitive in the usual sense. We show that the number N of such strongly primitive elements is asymptotic to θθ′·q where θ is the product of (1 − 1/p) over all primes p dividing (q − 1) and θ′ is the product of (1 − 2/p) over the same set. Using this result and the accompanying error estimates, with some computer assistance for small n, we deduce the existence of such strongly primitive elements for all n except n = 1, 4, 6. This extends earlier work on Golomb's conjecture concerning the simultaneous primitivity of γ and γ + 1. We also discuss analogous questions concerning strong primitivity for other finite fields. [ABSTRACT FROM AUTHOR]

Bent functions $f:\mathbb{F}_2^m\rightarrow \mathbb{F}_2$ achieve largest distance to all linear functions. Equivalently, their spectrum with respect to the Hadamard-Walsh transform is flat (i.e. all spectral values have the same absolute value). That is equivalent to saying that the function f has optimum periodic autocorrelation properties. Negaperiodic correlation properties of f are related to another unitary transform called the nega-Hadamard transform. A function is called negabent if the spectrum under the nega-Hadamard transform is flat. In this paper, we consider functions f which are simultaneously bent and negabent, i.e. which have optimum periodic and negaperiodic properties. Several constructions and classifications are presented. [ABSTRACT FROM AUTHOR]

The filter generator is an important building block in many stream ciphers. We present here an attack that recovers the initial state of the hidden LFSR by detecting the positions where the inputs of the filtering function are equal to zero. This attack requires the precomputation of low weight multiples of the LFSR generating polynomial. By a careful analysis, we show that the attack complexity is among the best known and work for almost all cryptographic filtering functions. [ABSTRACT FROM AUTHOR]

We present optimized FPGA implementations of three tweakable enciphering schemes, namely, HCH, HCTR and EME using AES-128 as the underlying block cipher. We report performance timings and hardware resources occupied by these three modes when using a fully pipelined AES core and a sequential AES design. Our experimental results suggest that in terms of area HCTR, HCH and HCHfp (a variant of HCH) require more area than EME. However, HCTR performs the best in terms of speed followed by HCHfp, EME and HCH. [ABSTRACT FROM AUTHOR]

Linear Feedback Shift Registers (LFSRs) are used as building blocks for many stream ciphers, wherein, an n-degree primitive connection polynomial is used as a feedback function to realize an n-bit LFSR. This paper shows that such LFSRs are susceptible to power analysis based Side Channel Attacks (SCA). The major contribution of this paper is the observation that the state of an n-bit LFSR can be determined by making O(n) power measurements. Interestingly, neither the primitive polynomial nor the value of n be known to the adversary launching the proposed attack. The paper also proposes a simple countermeasure for the SCA that uses n additional flipflops. [ABSTRACT FROM AUTHOR]

For an iterated hash, it is expected that, the hash transform inherits all the cryptographic properties of its compression function. This means that the cryptanalytic validation task can be confined to the compression function. Bellare and Ristenpart [3] introduced a notion Multi-Property preserving (MPP) to characterize the goal. In their paper, the MPP was collision resistance preserving (CR-pr), pseudo random function preserving (PRF-pr) and pseudo random oracle preserving (PRO-pr). The probability distribution of hash transform influences the randomness and adversary's advantage on collision finding, we expect that the hash transform is almost uniformly distributed and this property is inherited from its compression function and call it Almost-Uniform Distribution preserving (AUD-pr). However, AUD-pr is not always true for MD-strengthening Merkle-Damgård [7,12] transform. It is proved that the distribution of Merkle-Damgård transform is not only influenced by output distribution of compression function, but also influenced by the iteration times. Then, we recommend a new construction and give proofs of satisfying MPP that is CR-pr, PRO-pr, PRF-pr and AUD-pr. [ABSTRACT FROM AUTHOR]

Gate level masking is one of the most popular countermeasures against Differential Power Attack (DPA). The present paper proposes a masking technique for AND gates, which are then used to build a balanced and masked multiplier in GF(2n). The circuits are shown to be computationally secure and have no glitches which are dependent on unmasked data. Finally, the masked multiplier in GF(24) is used to implement a masked AES S-Box in GF(24)2. Power measurements are taken to support the claim of random power consumption. [ABSTRACT FROM AUTHOR]

Okeya has established that HMAC/NMAC implementations based on only Matyas-Meyer-Oseas (MMO) PGV scheme and his two refined PGV schemes are secure against side channel DPA attacks when the block cipher in these constructions is secure against these attacks. The significant result of Okeya's analysis is that the implementations of HMAC/NMAC with the Davies-Meyer (DM) compression function based hash functions such as SHA-1 are vulnerable to DPA attacks. In this paper, first we show a partial key recovery attack on NMAC/HMAC based on Okeya's two refined PGV schemes by taking practical constraints into consideration. Next, we propose new hybrid NMAC/HMAC schemes for security against side channel attacks assuming that their underlying block cipher is ideal. We show a hybrid NMAC/HMAC proposal which can be instantiated with DM and a slight variant to it allowing NMAC/HMAC to use hash functions such as SHA-1. We then show that M-NMAC, MDx-MAC and a variant of the envelope MAC scheme based on DM with an ideal block cipher are secure against DPA attacks. [ABSTRACT FROM AUTHOR]

Feedback with Carry Shift Registers (FCSRs) are a promising alternative to LFSRs in the design of stream ciphers. The previous constructions based on FCSRs were dedicated to hardware applications [3]. In this paper, we will describe X-FCSR a family of software oriented stream ciphers using FCSRs. The core of the system is composed of two 256-bits FCSRs. We propose two versions: X-FCSR-128 and X-FCSR-256 which output respectively 128 and 256 bits at each iteration. We study the resistance of our design against several cryptanalyses. These stream ciphers achieve a high throughput and are suitable for software applications (6.3 cycles/byte). [ABSTRACT FROM AUTHOR]

Non-trivial lower bounds on the linear complexity are derived for a sequence obtained by performing k or fewer operations on a single period of a periodic sequence over $\mathbb{F}_q$. An operation is a substitution, an insertion, or a deletion of a symbol. The bounds derived are similar to those previously established for either k substitutions, k insertions, or k deletions within a single period. The bounds are useful when T/2k < L < T/k, where L is the linear complexity of the original sequence and T is its period. [ABSTRACT FROM AUTHOR]

In a recent paper [10], Mishra and Dimitrov have proposed a window-based Elliptic Curve (EC) scalar multiplication using double-base number representation. Their methods were rather heuristic. In this paper, given the window lengths w2 and w3 for the bases 2 and 3, we first show how to fix the number of windows, ρ, and then obtain a Double Base Number System (DBNS) representation of the scalar n suitable for window-based EC scalar multiplication. Using the DBNS representation, we obtain our first algorithm that uses a small table of precomputed EC points. We then modify this algorithm to obtain a faster algorithm by reducing the number of EC additions at the cost of storing a larger number of precomputed points in a table. Explicit constructions of the tables are also given. [ABSTRACT FROM AUTHOR]

Public-key encryption schemes with searchable keywords are useful to delegate searching capabilities on encrypted data to a third party, who does not hold the entire secret key, but only an appropriate token which allows searching operations but preserves data privacy. Such notion was previously proved to imply identity-based public-key encryption [5] and to be equivalent to anonymous (or key-private) identity-based encryption which are useful for fully-private communication. So far all presented public-key encryption with keyword search (PEKS) schemes were based on bilinear forms and finding a PEKS that is not based on bilinear forms has been an open problem since the notion of PEKS was first introduced in [5]. We construct a public-key encryption scheme with keyword search based on a variant of the quadratic residuosity problem. We obtain our scheme using a non-trivial transformation of Cocks' identity-based encryption scheme [9]. Thus we show that the primitive of PEKS can be based on additional intractability assumptions which is a conventional desiderata about all cryptographic primitives. [ABSTRACT FROM AUTHOR]

In this paper, we present a computationally efficient password authenticated key exchange protocol based on quadratic residues. The protocol, called QR-CEKE, is derived from the protocol QR-EKE, a previously published password authenticated key exchange protocol based on quadratic residues. The computational time for the client, however, is significant reduced in the protocol QR-CEKE. In comparison with QR-EKE, the protocol QR-CEKE is more suitable to an imbalanced computing environment where a low-end client device communicates with a powerful server over a broadband network. Based on number-theoretic techniques, we show that the computationally efficient password authenticated key exchange protocol is secure against residue attacks, a special type of off-line dictionary attack against password-authenticated key exchange protocols based on factorization. We also provide a formal security analysis of QR-CEKE under the factoring assumption and the random oracle model. [ABSTRACT FROM AUTHOR]

Saarinen recently proposed a chosen IV statistical attack, called the d-monomial test, and used it to find weaknesses in several proposed stream ciphers. In this paper we generalize this idea and propose a framework for chosen IV statistical attacks using a polynomial description. We propose a few new statistical attacks, apply them on some existing stream cipher proposals, and give some conclusions regarding the strength of their IV initialization. In particular, we experimentally detected statistical weaknesses in some state bits of Grain-128 with full IV initialization as well as in the keystream of Trivium using an initialization reduced to 736 rounds from 1152 rounds. We also propose some stronger alternative initialization schemes with respect to these statistical attacks. [ABSTRACT FROM AUTHOR]

There has been a wide ranging discussion on the contents copyright protection in digital contents distribution systems. Fiat and Tassa proposed the framework of dynamic traitor tracing. Their framework requires dynamic computation transactions according to the real-time responses of the pirate, and it presumes real-time observation of contents redistribution and therefore cannot be simply utilized in an application where such an assumption is not valid. In this paper, we propose a new scheme that not only provides the advantages of dynamic traitor tracing schemes but also overcomes their problems. [ABSTRACT FROM AUTHOR]

SMS4 is a 128-bit block cipher which is used in the WAPI standard in China for protecting wireless transmission data. Due to the nature that the functions deployed in the round transformations of SMS4 operate on two different fields GF(28) and GF(2), it is difficult to analyze this cipher algebraically. In this paper we describe a new block cipher called ESMS4, which uses only algebraic operations over GF(28). The new cipher is an extension of SMS4 in the sense that SMS4 can be embedded into ESMS4 with restricted plaintext space and key spaces. Thus, the SMS4 cipher can be investigated through this embedding over GF(28). Based on this new cipher, we represent the SMS4 cipher with an overdetermined, sparse multivariate quadratic equation system over GF(28). Furthermore, we estimate the computational complexity of the XSL algorithm for solving the equation system and find that the complexity is 277 when solving the whole system of equations. [ABSTRACT FROM AUTHOR]

We present a proxy cryptosystem based on a certificate-based encryption scheme. The proposed scheme inherits the merits of certificate-based encryption systems: no-key-escrow and implicit certification. In addition, the proposed scheme allows the proxy's decryption power to be revoked even during the valid period of the proxy key without changing the original decryptor's public information. Few proxy schemes have this property, and ours is more efficient than the existing ones. We show that our proposal is IND-CBPd-Rev-CCA secure under the bilinear Diffie-Hellman assumption in the random oracle model. [ABSTRACT FROM AUTHOR]

For elliptic curve based cryptosystems, the discrete logarithm problem must be hard to solve. But even when this is true from a mathematical point of view, side-channel attacks could be used to reveal information about the key if proper countermeasures are not used. In this paper, we study the difficulty of the discrete logarithm problem when partial information about the key is revealed by side channel attacks. We provide algorithms to solve the discrete logarithm problem for generic groups with partial knowledge of the key which are considerably better than using a square-root attack on the whole key or doing an exhaustive search using the extra information, under two different scenarios. In the first scenario, we assume that a sequence of contiguous bits of the key is revealed. In the second scenario, we assume that partial information on the "Square and Multiply Chain" is revealed. [ABSTRACT FROM AUTHOR]

To construct a suitable and secure proxy re-signature scheme is not an easy job, up to now, there exist only three schemes, one is proposed by Blaze et al. [6] at EUROCRYPT 1998, and the others are proposed by Ateniese and Hohenberger [2] at ACM CCS 2005. However, none of these schemes is proved in the standard model (i.e., do not rely on the random oracle heuristic). In this paper, based on Waters' approach [20], we first propose a multi-use bidirectional proxy re-signature scheme, denoted as Smb, which is existentially unforgeable in the standard model. And then, we extend Smb to be a multi-use bidirectional ID-based proxy re-signature scheme, denoted by Sid − mb, which is also existentially unforgeable in the standard model. Both of these two proposed schemes are computationally efficient, and their security bases on the Computational Diffie-Hellman (CDH) assumption. [ABSTRACT FROM AUTHOR]

We study a tweakable blockcipher for arbitrarily long message (also called a tweakable enciphering scheme) that consists of a universal hash function and an expansion, a keyed function with short input and long output. Such schemes, called HCTR and HCH, have been recently proposed. They used (a variant of) the counter mode of a blockcipher for the expansion. We provide a security proof of a structure that underlies HCTR and HCH. We prove that the expansion can be instantiated with any function secure against Known-plaintext attacks (KPAs), which is called a weak pseudorandom function (WPRF). As an application of our proof, we provide efficient blockcipher-based schemes comparable to HCH and HCTR. For the double-block-length case, our result is an interesting extension of previous attempts to build a double-block-length cryptographic permutation using WPRF. [ABSTRACT FROM AUTHOR]

Transitive signature is an interesting primitive due to Micali and Rivest. During the past years, many constructions of transitive signatures have been proposed based on various assumptions. In this paper, we provide the first construction of transitive signature schemes by using braid groups. In the random oracle model, our proposals are proved to be transitively unforgeable against adaptively chosen message attack under the assumption of the intractability of one-more matching conjugate problem (OM-MCP) over braid groups. Moreover, the proposed schemes are invulnerable to currently known quantum attacks. [ABSTRACT FROM AUTHOR]

This paper analyzes the best speeds that can be obtained for single-scalar multiplication with variable base point by combining a huge range of options: many choices of coordinate systems and formulas for individual group operations, including new formulas for tripling on Edwards curves;double-base chains with many different doubling/tripling ratios, including standard base-2 chains as an extreme case;many precomputation strategies, going beyond Dimitrov, Imbert, Mishra (Asiacrypt 2005) and Doche and Imbert (Indocrypt 2006). The analysis takes account of speedups such as S - M tradeoffs and includes recent advances such as inverted Edwards coordinates. The main conclusions are as follows. Optimized precomputations and triplings save time for single-scalar multiplication in Jacobian coordinates, Hessian curves, and tripling-oriented Doche/Icart/Kohel curves. However, even faster single-scalar multiplication is possible in Jacobi intersections, Edwards curves, extended Jacobi-quartic coordinates, and inverted Edwards coordinates, thanks to extremely fast doublings and additions; there is no evidence that double-base chains are worthwhile for the fastest curves. Inverted Edwards coordinates are the speed leader. [ABSTRACT FROM AUTHOR]

Cryptographic embedded systems are vulnerable to Differential Power Analysis (DPA). In particular, the S-boxes of a block cipher are known to be the most sensitive parts with respect to this very kind of attack. While many sound countermeasures have been proposed to withstand this weakness, most of them are too costly to be adopted in real-life implementations of cryptographic algorithms. In this paper, we focus on a widely adopted lightweight variation on the well-known Duplication Method. While it is known that this design is vulnerable to higher-order DPA attacks, we show that it can also be efficiently broken by first-order DPA attacks. Finally, we point out ad hoc costless countermeasures that circumvent our attacks. [ABSTRACT FROM AUTHOR]

We study the interplay of network connectivity and the issues related to feasibility and optimality for probabilistic perfectly reliable message transmission (PPRMT) and probabilistic perfectly secure message transmission (PPSMT) in a synchronous network under the influence of a mixed adversary who possesses unbounded computing power and can corrupt different set of nodes in Byzantine, omission, failstop and passive fashion simultaneously. Our results show that that randomness helps in the possibility of multiphase PPSMT and significantly improves the lower bound on communication complexity for both PPRMT and PPSMT protocols!! [ABSTRACT FROM AUTHOR]

This paper is on efficient implementation techniques of Elliptic Curve Cryptography. In particular, we improve timings for Jacobi-quartic (3M+4S) and Hessian (7M+1S or 3M+6S) doubling operations. We provide a faster mixed-addition (7M+3S+1d) on modified Jacobi-quartic coordinates. We introduce tripling formulae for Jacobi-quartic (4M+11S+2d), Jacobi-intersection (4M+10S+5d or 7M+7S+3d), Edwards (9M+4S) and Hessian (8M+6S+1d) forms. We show that Hessian tripling costs 6M+4C+1d for Hessian curves defined over a field of characteristic 3. We discuss an alternative way of choosing the base point in successive squaring based scalar multiplication algorithms. Using this technique, we improve the latest mixed-addition formulae for Jacobi-intersection (10M+2S+1d), Hessian (5M+6S) and Edwards (9M+1S+ 1d+4a) forms. We discuss the significance of these optimizations for elliptic curve cryptography. [ABSTRACT FROM AUTHOR]

Double base number systems (DBNS) provide an elegant way to represent numbers. These representations also have many interesting and useful properties, which have been exploited to find many applications in Cryptography and Signal Processing. In the current article we present a scheme to represent numbers in double (and multi-) base format by combinatorial objects like graphs and diagraphs. The combinatorial representation leads to proof of some interesting results about the double and multibase representation of integers. These proofs are based on simple combinatorial arguments. In this article we have provided a graph theoretic proof of the recurrence relation satisfied by the number of double base representations of a given integer. The result has been further generalized to more than 2 bases. Also, we have uncovered some interesting properties of the sequence representing the number of double base representation of a positive integer n. It is expected that the combinatorial representation can serve as a tool for a better understanding of the double (and multi-) base number systems. [ABSTRACT FROM AUTHOR]

The Data Encryption Standard (DES) is a 64-bit block cipher. Despite its short key size of 56 bits, DES continues to be used to protect financial transactions valued at billions of Euros. In this paper, we investigate the strength of DES against attacks that use a limited number of plaintexts and ciphertexts. By mounting meet-in-the-middle attacks on reduced-round DES, we find that up to 6-round DES is susceptible to this kind of attacks. The results of this paper lead to a better understanding on the way DES can be used. [ABSTRACT FROM AUTHOR]

In this paper, we study the security of AES-192 against related-key differential-linear cryptanalysis, which is the first attempt using this technique. Among our results, we present two variant attacks on 7-round AES-192 and one attack on 8 rounds using a 5-round related-key differential-linear distinguisher. One key point of the construction of the distinguisher is the special property of MC operation of AES. Compared with the best known results of related-key impossible differential attacks and related-key rectangle attacks on AES-192, the results presented in this paper are not better than them, but the work is a new attempt, and we hope further work may be done to derive better results in the future. [ABSTRACT FROM AUTHOR]

We study the security of elliptic curve Diffie-Hellman secret keys in the presence of oracles that provide partial information on the value of the key. Unlike the corresponding problem for finite fields, little is known about this problem, and in the case of elliptic curves the difficulty of representing large point multiplications in an algebraic manner leads to new obstacles that are not present in the case of finite fields. To circumvent this obstruction, we introduce a small multiplier version of the hidden number problem, and we use its properties to analyze the security of certain Diffie-Hellman bits. We suggest new character sum conjectures that guarantee the uniqueness of solutions to the hidden number problem, and provide some evidence in support of the conjectures by showing that they hold on average in certain cases. We also present a Gröbner basis algorithm for solving the hidden number problem and recovering the Diffie-Hellman secret key when the elliptic curve is defined over a constant degree extension field and the oracle is a coordinate function in the polynomial basis. [ABSTRACT FROM AUTHOR]

Secret sharing is a basic fundamental cryptographic task. Motivated by the virtual automata abstraction and swarm computing, we investigate an extension of the k-secret sharing scheme, in which the secret components are changed on the fly, independently and without (internal) communication, as a reaction to a global external trigger. The changes are made while maintaining the requirement that k or more secret shares may reveal the secret and no k − 1 or fewer reveal the secret. The application considered is a swarm of mobile processes, each maintaining a share of the secret which may change according to common outside inputs e.g., inputs received by sensors attached to the process. The proposed schemes support addition and removal of processes from the swarm as well as corruption of a small portion of the processes in the swarm. [ABSTRACT FROM AUTHOR]

The stream cipher TPypy has been designed by Biham and Seberry in January 2007 as the strongest member of the Py-family ciphers, after weaknesses in the other members Py, Pypy, Py6 were discovered. One main contribution of the paper is the detection of related-key weaknesses in the Py-family of ciphers including the strongest member TPypy. Under related keys, we show a distinguishing attack on TPypy with data complexity 2192.3 which is lower than the previous best known attack on the cipher by a factor of 288. It is shown that the above attack also works on the other members TPy, Pypy and Py. A second contribution of the paper is design and analysis of two fast ciphers RCR-64 and RCR-32 which are derived from the TPy and the TPypy respectively. The performances of the RCR-64 and the RCR-32 are 2.7 cycles/byte and 4.45 cycles/byte on Pentium III (note that the speeds of the ciphers Py, Pypy and RC4 are 2.8, 4.58 and 7.3 cycles/byte). Based on our security analysis, we conjecture that no attacks lower than brute force are possible on the RCR ciphers. [ABSTRACT FROM AUTHOR]

In this paper, we prove that for any polynomial function f of fixed degree without multiple roots, the probability that all the (f(x + 1), f(x + 2)..., f(x + κ)) are quadratic non-residue is $\approx \frac{1}{2^\kappa}$. In particular for f(x) = x3 + ax + b corresponding to the elliptic curve y2 = x3 + ax + b, it implies that the quadratic residues (f(x + 1), f(x + 2)... in a finite field are sufficiently randomly distributed. Using this result we describe an efficient implementation of El-Gamal Cryptosystem. that requires efficient computation of a mapping between plain-texts and the points on the elliptic curve. [ABSTRACT FROM AUTHOR]