
We present some new families of (L ×T, w, l) (2D) wavelength/time optical orthogonal codes (2DOOCs) with l = 1,2. Such codes are used in optical codedivision multiple access (OCDMA) systems for supporting many simultaneous users. All families presented are either optimal with respect to the Johnson bound (Joptimal) or are asymptotically optimal. The constructions are based on certain pointsets in finite projective spaces of dimension k over GF(q) denoted PG(k,q). Exploiting this framework we establish that all 2DOOCs constructed are in fact maximal (in that no new codeword may be added to the original whereby code cardinality is increased).
The distance enumerator of an errorcorrecting code is a polynomial which "counts" the number of codewords from a fixed word w. (For linear codes, this is often called the weight enumerator.) We consider the situation where the code is a group of permutations (where the codewords are permutations written in list form, and with the usual Hamming distance), in which case the distance enumerator is related to a more wellknown polynomial, the cycle index.
This is joint work with J. P. Dixon (London/Sydney).
Much of our knowledge and insight into function field (from a computational perspective) comes from extending what has been learned in the number field case to this new setting. While this can work in positive characteristic, things tend to go awry when the characteristic of the field divides the degree of the extension. The simplest example of this is elliptic and hyperelliptic function fields in characteristic two. In this situation, while many things become more complicated, they are still manageable enough because they are relatively well behaved. By doing something as innocuous as looking at cubic function fields in characteristic three, even calculating the most mundane invariant becomes problematic.
In this talk, we highlight some of the challenges in this area and some successes. We also highlight a class of curves that could be (in some sense) considered an analogue of hyperelliptic curves in characteristic two.
This is joint work with Jonathan Webster.
High genus hyperelliptic curves are of cryptographic interest in the context of the Weil descent method for solving the elliptic curve discrete logarithm problem (ECDLP). Weil descent allows one to reduce the ECDLP on some elliptic curves defined over a characteristic 2 finite field of composite degree to an instance of the hyperelliptic curve discrete logarithm problem (HCDLP) defined over a smaller field. Under certain circumstances, the resulting instance of the HCDLP can be solved in subexponential time using index calculus algorithms. In this talk, we describe recent improvements to an algorithm for solving the usual HCDLP on an imaginary hyperelliptic curve, and the infrastructure discrete logarithm problem on a high genus real hyperelliptic curve. In the imaginary case, we obtain a significant improvement in practice, allowing us to solve an instance of the ECDLP on an elliptic curve defined over F_{2155} via Weil descent. In the real case, we obtain an algorithm with improved asymptotic complexity, as well as numerical results from the first implementation of any index calculus algorithm for solving the infrastructure discrete logarithm problem.
The recent advent of nonstandard discrete logarithm based assumptions has led to a proliferation of cryptographic protocols for which no proof of equivalence between the security of the protocol and the underlying hard problem is known. One of the prototypical examples of this phenomenon is the BonehBoyen short signature scheme, whose security to date has not been proven to be equivalent to the Strong DiffieHellman (SDH) problem upon which it is based. The results which we present here provide for the first time a proof that the BonehBoyen signature scheme is equivalent to the SDH problem. Using Cheon's algorithm for solving the SDH problem, we obtain an algorithm that in most cases recovers the private key in the BonehBoyen signature scheme in less time than it takes to solve the discrete logarithm problem, given sufficiently many messagesignature pairs.
We look at message recognition protocols (MRPs) and prove that there is a onetoone correspondence between noninteractive MRPs and digital signature schemes with message recovery. Further, we look at an existing recognition protocol and point out its inability to recover in case of a specific adversarial disruption. We improve this protocol by suggesting a variant which is equipped with a resynchronization process. Moreover, another variant of the protocol is proposed which selfrecovers in case of an intrusion. Finally, we propose a new design for message recognition in ad hoc networks which does not make use of hash chains. This new design uses random passwords that are being refreshed in each session, as opposed to precomputed elements of a hash chain.
We shall discuss a fast streambased hash function developed with Nikolajs Volkovs.
Spacetime coding has been developed for use in multiple antenna wireless communications to achieve high rate and reliable data transmission. In this talk, we will present a new design of spacetime Hamiltonian constellations from group codes. These group codes include cyclic groups, permutation codes variant II and finite reflection groups.
This is joint work with Ali Miri and Monica Nevins (University of Ottawa).
We consider the problem of a center broadcasting an encrypted message to a group of users such that some subset is considered revoked and should not be able to obtain the content of the broadcasted message even if all revoked users collaborate. Various encryption schemes have been proposed to solve this problem which arises, for example, with payTV and satellite communications.
In one class of proposed schemes the center distributes a unique combination of keys to each user who decrypts the message individually. If keys cannot be updated once distributed the receivers are called stateless. Several key distribution schemes use a balanced binary tree structure. Some examples that we consider are the complete subtree scheme (CST), introduced independently by Wallner, Harder and Agee (1998), and Wong, Gouda and Lam (1998), the subsetdifference scheme (SD), introduced by Naor, Naor and Lotspiech (2003), and the layered subsetdifference scheme (LSD) by Halevy and Shamir (2002).
Park and Blake (2006) give generating functions that entail the exact mean number of encryptions for the above key distribution schemes. We extend their results by showing that the distribution of the number of encryptions is asymptotically normal.
This is joint work with C. Eagle, Z. Gao, M. Omar, and B. Richmond.
In 2000, Forney (IEEE Trans. Inform. Theory 46, 830850) defined the concept of capacity achieving of lattices on AWGN channels. By introducing cosetcodes, he proved the existence of such lattices and called them "sphere bound achieving".
Lowdensity paritycheck (LDPC) codes (Gallager, 1963) have a very good performance under iterative decoding algorithm. In 2006, Sadeghi et. al. (IEEE Trans. Inform. Theory 52, 44814495) introduced LDPC Lattices. Construction D¢ (Bos and Convey, Mathematika 29(1982), 171180) converts a set of parity checks defined by a family of nested code into congruences for a lattice. This type of construction is applied to LDPC codes to generate LDPC lattices.
In this talk we show that this type of lattices are capable of sphere bound achieving, that is, for AWGN channel with noise variance per dimension s^{2}, there exists a lattice with volume V of large enough dimension n such that the error probability is small whenever s^{2} < [(V^{[ 2/(n)]})/(2pe)].
Although, data is very valuable in every organization, it must be processed in order to be useful. Data mining is a collection of techniques which find patterns and associations in raw data, classify or cluster the items according to their attributes. Nowadays, related data is normally distributed among two or more parties in different configurations, and mining can be done in an accurate and useful way for all parties involved, on all data collections. However, privacy is often crucial in different scenarios, and organizations involved do not want to disclose their own private information to each other. Therefore, standard algorithms of data mining must be modified, or new protocols have to be designed to preserve the privacy of the parties. In the last decade, PrivacyPreserving Data Mining has received increase attention from researchers in computer science, and many protocols and techniques have been presented for different data mining methods, each of which has a level of security, efficiency and accuracy. However, there are still many open problems in this field of study in terms of security and efficiency such as developing privacypreserving protocols for public channels and incremental algorithms, preventing sensitivity and collusion attack, reducing intermediate outputs, and balancing the distribution of the final results. In this talk we shortly review the background, present some solutions, and discuss possible future directions in this area.
Algebraic geometers and cryptographers are very familiar with what we like to call the "imaginary" model of a hyperelliptic curve. Another less familiar description of such a curve is the socalled "real" model; the terminology stems from the analogy to real and imaginary quadratic number fields. Structurally and arithmetically, the real model behaves quite differently from its imaginary counterpart. While divisor addition with subsequent reduction ("giant steps") is still essentially the same, the real model no longer allows for efficiently computable unique representation of elements in the Jacobian via reduced representatives. However, the real model exhibits a socalled infrastructure, with an additional much faster operation ("baby steps"). We present the real model of a hyperelliptic curve and its twofold baby step giant step divisor arithmetic. We also indicate how to use these algorithms for potential cryptographic and number theoretic applications.
I would like to highlight the principal features of a new factoring algorithm still in preparation. In particular, I believe that this algorithm runs in subexponential time. However, unlike previous leading subexponentialtime factoring algorithms related to the Quadratic Sieve, this one does not use "Fermattype" equalities.
Rather, to factor x, it finds a nontrivial relation between O(x^{e}) values of a carefully chosen multiplicative function related to s(n) = å_{d  n} d. Lfunctions come to the rescue in finding this relation and the functional equation plays a crucial role.
We present a method for computing pth roots using a polynomial basis over finite fields F_{q} of odd characteristic p, p ³ 5, by taking advantage of a binomial reduction polynomial. For a finite field extension F_{qm} of F_{q} our method requires p 1 scalar multiplications of elements in F_{qm} by elements in F_{q}. In addition, our method requires at most (p1)ém/p ù additions in the extension field. In certain cases, these additions are not required. If z is a root of the irreducible reduction polynomial, then the number of terms in the polynomial basis expansion of z^{1/p}, defined as the Hamming weight of z^{1/p} or wt(z^{1/p}), is directly related to the computational cost of the pth root computation. We find that wt(z^{1/p}) = 1 in all cases using binomials. We also give conditions on which degrees m admit an irreducible binomial over F_{q}.