Elliptic Curve Pseudorandom Sequence Generators
CORR 1998-53
Thomas A. Berson, Guang Gong, and D.R. Stinson
Abstract
In this paper, we introduce a new approach to the generation of binary sequences by applying trace functions to elliptic curves over \(GF(2^m)\) $GF(2^m)$. We call these sequences elliptic curve pseudorandom sequences (EC-Sequence). We will show their periods, distribution of zeros and ones, and linear spans. This research has uncovered a class of EC-sequences, generated by super-singular curves, which has half period as a lower bound for their linear spans. In comparison to de Bruijn sequences with the same parameters, EC-sequences can be constructed algebraically and can be generated efficiently in software or hardware by means used for implementation of elliptic curve public-key cryptosystems.
Better Random Walks for Pollard's Rho Method
CORR 1998-52
Edlyn Teske
Abstract
We consider Pollard's rho method for discrete logarithm computation. In the analysis of its running time, the crucial assumption is made that a random walk in the underlying group is simulated. We show that this assumption does not exactly hold for the walk originally suggested by Pollard. We study alternative walks that can be efficiently applied to compute discrete logarithms. We introduce a class of walks that, in experiments, lead to the same performance as expected in this random case. We show that this holds for arbitrarily large prime group orders, under a much weaker assumption than before
Approximating the Complexity Measure of Vavasis-Ye Algorithm is NP-Hard
CORR 1998-51
Levent Tuncel
Abstract
Given an $m \times n$ integer matrix \(A\) of full row rank, we consider the problem of computing the maximum of \(\|B^{-1}A\|_2\) where \(B\) varies over all bases of \(A\). This quantity appears in various places in the mathematical programming literature. More recently, logarithm of this number was the determining factor in the complexity bound of Vavasis and Ye's primal-dual interior-point algorithm. We prove that the problem of approximating this maximum norm, even within an exponential (in the dimension of \(A\).) factor, is NP-hard. Our proof is based on a closely related result of L. Khachiyan (On the complexity of approximating extremal determinants in matrices, Journal of Complexity 11 (1995) 138--153).
Bibliography on Secret Sharing Schemes
CORR 1998-50
D.R. Stinson and R. Wei
Abstract
In the late 1980's, Gus Simmons compiled a bibliography of papers on secret sharing schemes. As far as we know, the most recent version of his bibliography was published in his book Contemporary Cryptology in 1992. At that time he had a list of 68 papers. We are not aware if Gus has continued to maintain his bibliography, but we felt it would be useful to creat an up-to-date bibliography and make it available on the WWW. This is the postscript version of the bibliography. The html version can be found at Bibliography on Secret Sharing Schemes. The current version of this bibliography has 216 entries.
In general, we are including papers that are published or accepted for publication in conference proceedings and journals (but not unpublished technical reports, preprints or dissertations). We would appreciate knowing of any errors in this list, as well as any papers that should be added, updates to unpublished papers, etc.
Bibliography on Authentication Codes
CORR 1998-49
D.R. Stinson and R. Wei
Abstract
We felt it would be useful to create an up-to-date bibliography on authentication codes and make it available on the WWW. This is a postscript version of the bibliography. The html version can be found at Bibliography on Authentication Codes. By "authentication codes" we mean Simmons-type codes that provide unconditional security against substitution and impersonation frauds. Thus, we do not consider related concepts such as MACs, MDCs or signature schemes.
The current version of this bibliography has 127 entries.
In general, we are including papers that are published or accepted for publication in conference proceedings and journals (but not unpublished technical reports or dissertations). We would appreciate knowing of any errors in this list, as well as any papers that should be added, updates to unpublished papers, etc.
Probabilistic analysis of two complexity measures for linear programming problems
CORR 1998-48
M.J. Todd, Levent Tuncel, and Yinyu Ye
Abstract
This note provides a probabilistic analysis of \(\bar{\chi}_A\), a condition number used in the linear programming algorithm of Vavasis and Ye [14] whose running time depends only on the constraint matrix \(A \in {\Bbb R}^{m \times n}\). We show that if \(A\) is a standard Gaussian matrix, then \(E(ln \bar{\chi}_A) = 0(\min \{m ln n, n \})\). Thus, the expected running time of linear programming is bounded by a polynomial in \(m\) and \(n\) for any right-hand side and objective coefficient vectors when \(A\) is randomly generated in this way. We show that the same bound holds for \(E(ln \sigma (A))\), where \(\sigma (A)\) is another condition number of \(A\) arising in complexity analyses of linear programming problems.
The number of ramified coverings of the sphere by the torus and surfaces of higher genera
CORR 1998-47
I.P. Goulden, D.M. Jackson, and A. Vainshtein
Abstract
We obtain an explicit expression for the number of ramified coverings of the sphere by the torus with given ramification type for a small number of ramification points, and conjecture this to be true for an arbitrary number of ramification points. In addition, the conjecture is proved for simple coverings of the sphere by the torus. We obtain corresponding expressions for surfaces of higher genera for small number of ramification points, and conjecture the general form for the number in terms of a symmetric polynomial that appears to be new. The approach involves the analysis of the action of a transposition to derive a system of linear partial differential equations that give the generating series for the desired numbers.
Absolute Irreducibility of Polynomials via Newton Polytopes
CORR 1998-46
Shuhong Gao
Conical open mapping theorems and regularity
CORR 1998-45
Heinz H. Bauschke and Jonathan M. Borwein
Abstract
Suppose $T$ is a continuous linear operator between two Hilbert spaces \(X\) and \(Y\) and let \(K\) be a closed convex nonempty cone in \(X\). We investigate the possible existence of \(\delta > 0\) such that \(\delta B_Y \cap T(K) \subseteq T(B_X \cap K)\), where \(B_X, B_Y\) denote the closed unit balls in \(X\) and \(Y\) respectively. This property, which we call openness relative to \(K\), is a generalization of the classical openness of linear operators. We relate relative openness to Jameson's prerpty \(G\), to the strong conical hull intersection property, to bounded linear regularity, and to metric regularity. Our results allow a simple construction of two closed convex cones that have the strong conical hull intersection property but fail to be boundedly linearly regular.
Algebras Related to Matroids Represented in Characteristic Zero
CORR 1998-44
David G. Wagner
Abstract
Let $k$ be a field of characteristic zero. We consider graded subalgebras $A$ of $k[x_1, \cdots , x_m]/(x_1^2, \cdots x^2_m)$ generated by $d$ linearly independent linear forms. Representations of matroids over $k$ provide a natural description of the structure of these algebras. In return, the numerical properties of the Hilbert function of $A$ yield some information about the Tutte polynomial of the corresponding matroid.
Some Observations on all-or-nothing transforms
CORR 1998-43
Doug Stinson
Abstract
In this short note, we study all-or-nothing transforms, which were recently proposed by Rivest as a mode of operation for block ciphers. We study transforms of this type that provide unconditional security. A simple construction for linear transforms is given, and some existence and non-existence results for general transforms are derived from a combinatorial characterization of these objects.
Unknown Key-Share Attacks on the Station-to-Station (STS) Protocol
CORR 1998-42
Simon Blake-Wilson and Alfred Menezes
Abstract
This note presents some new unknown key-share attacks on STS-MAC, the version of the STS key agreement protocol which uses a MAC algorithm to provide key confirmation. Various methods are considered for presenting the attacks.
Hadamard Transforms of Three-Term Sequences
CORR 1998-41
Guang Gong nd Solomon W. Golomb
Abstract
Certain three-term sequences of period $2^n - 1$ are conjectured to have the two-level autocorrelation property. In this note, a formula involving Hadamard transforms of three-term sequences is presented. Its validity has been verified by computer on the range of $5 \leq n \leq 23$.
Approximating multiroot 3-outconnected subgraphs
CORR 1998-40
Zeev Nutov
Abstract
We consider the following problem: given a set of $q$ root vertices $\{ r_1,r_2, \ldots , r_q\}$ of an undirected graph with costs on its edges, and associated integers $\{k_1, k_2, \ldots , k_q\}$ in the range $\{1, \ldots , k\}$, find the cheapest subgraph such that for every $i=1, \ldots , q$ there are $k_i$ internally vertex disjoint paths from $r_i$ to any other vertex. For $k \geq 2$ this problem is known to be NP-hard. It generalizes the problem of finding a minimum cost $k$-vertex connected spanning subgraph and has practical applications. The best known algorithm for this problem has approximation ratio $2q$, where $q$ can be as large as $k-1$, and (for a general instance of the problem) for no value of $k \geq 2$ a better approximation algorithm is known.
We consider the case of small requirements $r_i \in \{ 1, 2, 3 \}$; these arise often in applications, as in practical networks the connectivity requirements are usually rather small. For this case we give an algorithm with approximation ration $3 \frac{1}{3}$. This improves the best previously known approximation ratio $4$. In the case we have an initial graph which is 2-connected, our algorithm achieves approximation ratio 2; this result is comparable with the best known for the problem of augmenting a 2-connected graph to a 3-connected one, as 2 is also the best known approximation ratio for the latter problem.
Our algorithm also implies a $2(k- \frac{4}{3})$-approximation algorithm for arbitrary $k$, which is a slight improvement over the previously best known approximation ratio $2(k-1)$.
FISH and I
CORR 1998-39
W.T. Tutte
Abstract
Professor Tutte, FRS, is a Distinguished Professor Emeritus and an Adjunt Professor in the Combinatorics and Optimization (C and O) department at the University of Waterloo. He worked from 1941 to 1945 in the British cryptanalytic headquarters at Bletchley Park, the most successful intelligence agency in world history. His work, which combined elements of statistics and combinatorics, was instrumental in the breaking of FISH, a series of codes that were used by the German command for encrypting communications between the highest authorities. Subsequent cryptanalytic work on FISH included the development of Colossus, the world's first electronic computer. This paper is a transcript of Professor Tutte's lecture on June 19, 1998 at the opening cermony of the Centre for Applied Cryptographic Research (CACR) at the University of Waterloo.
Periodic Binary Sequences with the "Trinomial Property"
CORR 1998-38
Solomon W. Golomb and Guang Gong
Abstract
Periodic binary sequences with the "trinomial property" are considered. Some necessary and sufficient conditions for "trinomial pairs" of a nonlinear sequence of period $2^n-1$ as well as classifications for trinomial pairs are derived. Complete searches have been done for $3 \leq n \leq 17$. All trinomial pairs found on this range are listed.
Cyclic Inequivalence of Cascaded GMW-Sequences
CORR 1998-37
Solomon W. Golomb, Guang Gong, and Zong Duo Dai
Abstract
Cascaded GMW sequences have two-level autocorrelation functions, which have important applications in communications and cryptology. In this paper, we consider the cascaded GMW sequences corresponding to a fixed finite chain of finite fields, and study the problem of how to determine all these different cascaded GMW sequences without repetition, and the problem of whether the different cascaded GMW sequences are cyclically inequivalent. By introducing the so-called restricted integer systems (RISs), it is proved that all the cascaded GMW sequences can be determined by means of the RISs, and the sequences determined by different RISs are different. Moreover, different cascaded GMW sequences are cyclically inequivalent.
Transform Domain Analysis of DES
CORR 1998-36
Guang Gong and Solomon W. Golomb
Abstract
DES can be regarded as a nonlinear feedback shift register (NLFSR) with input. From this point of view, the tools for pseudo-random sequence analysis are applied to the $S$-boxes in DES. The properties of the $S$-boxes of DES under Fourier transform, Hadamard transform, extended Hadamard transform and Avalanche transform are investigated. Two important results about the $S$-boxes of DES are found. The first result is that nearly two-thirds of the total 32 functions from $GF(2^6)$ to $GF(2)$ which are associated with the 8 $S$-boxes of DES have the maximal linear span 63, and the other one-third have linear span greater then or equal to 57. The second result is that for all $S$-boxes, the distances of the $S$-boxes approximated by monomial functions has the same distribution as for the $S$-boxes approximated by linear functions. Some new criteria for the design of permutation functions for use in block cipher algorithms are discussed.
Graph Rigidity via Euclidean Distance Matrices
CORR 1998-35
Abdo Y. Alfakih
Abstract
Let $G=(V,E, \omega)$ be an incomplete graph with node set $V$, edge set $E$, and nonnegative weight $\omega_{ij}$'s on the edges. Let each edge $(v_i, v_j)$ be viewed as a rigid bar, of length $\omega_{ij} $, which can rotate freely around its end nodes. A realization of a graph $G$ is an assignment of coordinates, in some Euclidean space, to each node of $G$. In this paper, we consider the problem of determining whether or not a given realization of a graph $G$ is rigid. We show that each realization of $G$ can be represented as a point in a compact convex set $\Omega \subset \cal{R}^{\bar{m}}$; and that a generic realization of $G$ is rigid if and only if its corresponding point is a vertex of $\Omega$, i.e., an extreme point with full dimensional normal cone.
Discretization and Localization in Successive Convex Relaxation Methods for Nonconvex Quadratic Optimization Problems
CORR 1998-34
Masakazu Kojima and Levent Tuncel
Abstract
Based on the authors' previous work which established theoretical foundations of two, conceptual, successive convex relaxation methods, i.e., the SSDP (Successive Semidefinite Programming) Relaxation Method and the SSILP (Successive Semi-Infinite Linear Programming) Relaxation Method, this paper proposes their implementable variants for general quadratic optimization problems. These problems have a linear objective function $c^Tx$ to be maximized over a nonconvex compact feasible region $F$ described by a finite number of quadratic inequalities. We introduce two new techniques, "discretization" and "localization", into the SSDP and SSILP Relaxation Methods. The discretization technique makes it possible to approximate an infinite number of semi-infinite SDPs (or semi-infinite LPs) which appeared at each iteration of the original methods by a finite number of standard SDPs (or standard LPs) with a finite number of linear inequality constraints. We establish:
The localization technique is for the cases where we are only interested in upper bounds on the optimal objective value (for a fixed objective function vector $c$) but not in a global approximation of the convex hull of $F$. This technique allows us to generate a convex relaxation of $F$ that is accurate only in certain directions in a neighborhood of the objective direction $c$. This cuts off redundant work to make the convex relaxation accurate in unnecessary directions. We establish:
- Given any open convex set $U$ containing $F$, an implementable discretization of the SSDP (or SSILP) Relaxation Method generates a compact convex set $C$ such that $F \subseteq C \subseteq U$ in a finite number of iterations.
- Given any positive number $\epsilon$, an implementable localization-discretization of the SSDP (or SSILP) Relaxation Method generates an upper bound of the objective values within $\epsilon$ of their maximum in a finite number of iterations.
Metric regularity, strong CHIP, and CHIP are distinct properties
CORR 1998-33
Heinz H. Bauschke, Jonathan M. Borwein, and Paul Tseng
Abstract
Metric regularity, the strong conical hull intersection property (strong CHIP), and the conical hull intersection property (CHIP) are properties of a collection of finitely many closed convex intersecting sets in Euclidean space. It was shown recently that these properties are fundamental in several branches of convex optimization, including convex feasibility problems, error bounds, Fenchel duality, and constrained approximation. It was known that regularity implies strong CHIP, which in turn implies CHIP; moreover, the three properties always hold for subspaces. The question whether or not converse implications are true for general convex sets was open.
Show that - even for convex cones - the converse implications need not hold by constructing counter-examples in $R^4$.
Presolving for Semidefinite Programs Without Constraint Qualifications
CORR 1998-32
Gerald Gruber, Serge Kruk, Franz Rendl, and Henry Wolkowicz
Abstract
Presolving for linear programming is an essential ingredient in many commercial packages. This step eliminates redundant constraints and identically zero variables, and it identifies possible infeasibility and unboundedness. In semidefinite programming, identically zero variables corresponds to lack of a constraint qualification which can result in both theoretical and numerical difficulties. A nonzero duality gap can exist which nullifies the elegant and powerful duality theory. Small perturbations can result in infeasibility and/or large perturbations in solutions. Such problems fall into the class of ill-posed problems.
It is interesting to note that classes of problems where constraint qualifications fail arise from semidefinite programming relaxations of hard combinatorial problems. We look at several such classes and present two approaches to find regularized solutions. Some preliminary numerical results are included.
Strong Duality for a Trust-Region Type Relaxation of the Quadratic Assignment Problem
CORR 1998-31
Kurt Anstreicher, Xin Chen, Henry Wolkowicz, and dYa-Xiang Yuan
Abstract
Lagrangian duality underlies many efficient algorithms for convex minimization problems. A key ingredient is strong duality. Lagrangian relaxation also provides lower bounds for nonconvex problems, where the quality of the lower bound depends on the duality gap. Quadratically constrained quadratic programs (QQPs) provide important examples of nonconvex programs. For the simple case of one quadratic constraint (the trust region subproblem) strong duality holds. In addition, necessary and sufficient (strengthened) second order optimality conditions exist. However, these duality results already fail for the two trust region subproblem.
Surprisingly, there are classes of more complex, nonconvex QQPs where strong duality holds. One example is the special case of orthogonality constraints, which arise naturally in relaxation for the quadratic assignment problem (QAP). In this paper we show that strong duality also holds for a relaxation of QAP where the orthogonality constraint is replaced by a semidefinite inequality constraint. Using this strong duality result, the semidefinite duality, we develop new trust-region type necessary and sufficient optimality conditions for these problems. Our proof of strong duality introduces and uses a generalization of the Hoffman-Wielandt inequality.
On a Conjecture of Lovasz Concerning Bricks
CORR 1998-30
Marcelo H. Carvalho, Claudio L. Lucchesi, and U.S.R. Murty
Abstract
In 1987, Lovasz conjectured that every brick $G$ different from $K_4, \bar{C}_6$, and the Petersen graph has an edge $e$ such that $G - e$ is a matching covered graph with exactly one brick. Lovasz and Vempala announced a proof of this conjecture in 1994. Their paper is under preparation. We present here an independent proof of their theorem. We shall in fact prove that if $G$ is any brick different from $K_4$ and $\bar{C}_6$ and does not have the Petersen graph as its underlying simple graph, then it has an edge $e$ such that $G-e$ is a matching covered graph with exactly one brick, with the additional property that the underlying simple graph of that one brick is different from the Petersen graph. Our proof involves establishing an interesting new property of the Petersen graph.
Hyperbolic Polynomials and Convex Analysis
CORR 1998-29
Heinz H. Bauschke, Osman Guler, Adrian S. Lewis, and Hristo S. Sendov
Abstract
A homogeneous polynomial $p(x)$ is hyperbolic with respect to a given vector $d$ if the real polynomial $\mapsto p(x+td)$ has all real roots for all vectors $x$. We show that any symmetric convex function of these roots is a convex function of $x$, generalizing a fundamental result of Garding. Consequently we are able to prove a number of deep results about hyperbolic polynomials with ease. In particular, our result subsumes von Neumann's characterization of unitarily invariant matrix norms, and Davis's characterization of convex functions of the eigenvalues of Hermitian matrices. We then develop various convex-analytic tools for such symmetric functions, of interest in interior-point methods for optimization problems posed over related cones.
Voronoi's Algorithm in Purely Cubic Congruence Function Fields of Unit Rank 1
CORR 1998-28
Renate Scheidler and Adreas Stein
Abstract
The first part of this paper classifies all purely cubic function fields over a finite field of characteristic not equal to $3$. In the remainder, we describe a method for computing the fundamental unit and regulator of a purely cubic congruence function field of unit rank 1 and characteristic at least $5$. The technique is based on Voronoi's algorithm for generating a chain of successive minima in a multiplicative cubic lattice which is used for calculating the fundamental unit and regulator of a purely cubic number field.
Contrast Optimal Threshold Visual Cryptography Schemes
CORR 1998-27
Carlo Blundo, Paolo D'Arco, Alfredo De Santis, and Douglas R. Stinson
Abstract
A $(k,n)$-threshold visual cryptography scheme ($(k,n)$-threshold VCS, for short) is a method to encode a secret image SI into $n$ shadow images called shares such that any $k$ or more shares enable the "visual" recovery of the secret image, but by inspecting less that $k$ share one cannot gain any information on the secret image. The "visual" recovery consists of xeroxing the shares onto transparencies, and then stacking them. Any $k$ shares will reveal the secret image without any cryptographic computation.
In this paper we analyze the contrast of the reconstructed image for $(k,n)$-threshold VCS. We define a canonical form for $(k,n)$-threshold VCS and we also provide a characterization of $(k,n)$-threshold VCS. We completely characterize contrast optimal $(n-1,n)$-threshold VCS in canonical form. Moreover, for $n \geq 4$, we provide, a contrast optimal $(3,n)$-threshold VCS in canonical form. We first describe a family of $(3,n)$-threshold VCS achieving various values of contrast and pixel expansion. Then, we prove an upper bound on the contrast of any $(3,n)$-threshold VCS and show that a scheme in the described family has optimal contrast. Finally, for $k = 4,5$ we present two schemes with contrast asymptotically equal to $1/64$ and $1/256$, respectively.
Key Preassigned Traceability Schemes for Broadcast Encryption (Extended Abstract)
CORR 1998-26
D.R. Stinson and R. Wei
Extended Capabilities for Visual Cryptography
CORR 1998-25
Giuseppe Ateniese, Carlo Blundo, Alfredo De Santis, and Douglas R. Stinson
Abstract
An extended visual cryptography scheme, EVCS for short, for an access structure $(\Gamma_{Qual}, \Gamma_{Forb})$ on a set of $n$ participants, is a technique to encode $n$ images in such a way that when we stack together the transparencies associated to participants in any set $X \in \Gamma_{Qual}$ we get the secret message with no trace of the original images, but any $X \in \Gamma_{Forb}$ has no information on the shared image. Moreover, after the original images are encoded they are still meaningful, that is, any user will recognize the image on his transparency.
The main contributions of this paper are the following:
- A trade-off between the contrast of the reconstructed image and the contrast of the image on each transparency for $(k,k)$-threshold EVCS (in a $(k,k)$-threshold EVCS the image is visible if and only if $k$ transparencies are stacked together). This yields a necessary and sufficient condition for the existence of $(k,k)$-threshold EVCS for the values of such contrasts. In case a scheme exists we explicitly construct it.
- A general technique to implement extended visual cryptography schemes, which uses hypergraph colourings. This technique yields $(k,k)$-threshold EVCS which are optimal with respect to the pixel expansion. Finally, we discuss some applications of this technique to various interesting classes of access structures by using relevant results from the theory of hypergraph colourings.
On Lagrangian Relaxation of Quadratic Matrix Constraints
CORR 1998-24
Kurt Austreicher and Henry Wolkowicz
Monotonicity of Primal-Dual Interior-Point Algorithms for Semidefinite Programming Problems
CORR 1998-23
Masakazu Kojima and Levent Tuncel
Abstract
We present primal-dual interior-point algorithms with polynomial iteration bounds to find approximate solutions of semidefinite programming problems. Our algorithms achieve the current best iteration bounds and, in every iteration of our algorithms, primal and dual objective values are strictly improved.
Modular Bose-Mesner Algebras
CORR 1998-22
C.D. Godsil
Abstract
We study the Bose-Mesner algebra of an association scheme over a finite field. We see that these algebras provide a common treatment for the theory of cyclic codes, abelian difference sets and some of the theory of modular representations of group algebras. We give a simple condition for these algebras to be semisimple, and study its implications.
Galois Theory of Association Schemes
CORR 1998-21
C.D. Godsil
Abstract
We use Galois theory to determine subschemes of association schemes with irrational eigenvalues.
Generalized Hamming Schemes
CORR 1998-20
C.D. Godsil
Abstract
We introduce a class of association schemes that generalizes the Hamming scheme. We derive generating functions for their eigenvalues, and use these to obtain a version of MacWilliams theorem.
Shared Generation of Shared RSA Keys
CORR 1998-19
Simon Blackburn, Simon Blake-Wilson, Mike Burmester, and Steven Galbraith
An algebraic matching algorithm
CORR 1998-18
James F. Geelen
Abstract
Tutte introduced a $V$ by $V$ skew-symmetric matrix $T=(t_{ij})$, called the Tutte matrix, associated with a simple graph $G=(V,E)$. He associates an indeterminate $z_e$ with each $e \in E$, then defines $t_{ij} = \pm z_e$ when $ij = e \in E$, and $t_{ij} = 0$ otherwise. The rank of the Tutte matrix is exactly twice the size of a maximum matching of $G$. Using linear algebra and ideas from the Gallai-Edmonds decomposition, we describe a very simple yet efficient algorithm that replaces the indeterminates with constants without losing rank. Hence, by computing the rank of the resulting matrix, we can efficiently compute the size of a maximum matching of a graph.
Maximum rank matrix completion
CORR 1998-17
James F. Geelen
Abstract
The maximum rank completion problem is the problem of, given a partial matrix (that is, a matrix where we are only given some of the entries), fill in the unknown entries in such a way as to maximize the rank. Applications include bipartite matching and matroid intersection for linearly represented matroids. We describe an algorithm that finds a maximum rank completion by perturbing an arbitrary completion in a greedy way.
The Gauss-Newton Direction in Semidefinite Programming
CORR 1998-16
Serge Kruk, Masakazu Muramatsu, Franz Rendl, Robert J. Banderbei, and Henry Wolkowicz
Abstract
Primal-dual interior-point methods have proven to be very successful for both linear programming (LP) and, more recently, for semidefinite programming (SDP) problems. Many of the techniques that have been so successful for LP have been extended to SDP. In fact, interior point methods are currently the only successful techniques for SDP.
We present a new paradigm for deriving these methods: 1) using the optimality conditions from the dual log-barrier problem, we obtain primal feasibility, dual feasibility, and perturbed complementary slackness equations; 2) the perturbed complementary slackness condition is quite nonlinear, so we modify this condition to obtain a bilinear condition, i.e. a condition that is less nonlinear; 3) we now find a search direction by applying the Gauss-Newton method to the least squares problem for these optimality conditions; equivalently we find the least squares solution of the linearized perturbed optimality conditions.
In the case of LP, the Gauss-Newton direction for the least squares problem is equivalent to the Newton direction applied to solving the modified (square) nonliner system of optimality conditions. Though this paradigm does not directly provide a new search direction for linear programming, it does provide a new approach for convergence proofs as well as motivation for step lengths larger than one.
However, there is one major difference between LP and SDP that raises several interesting questions. That difference is the form of the perturbed complementarity condition used in the optimality conditions. In LP this condition is modified to be $ZX - \mu I = 0$. The primal matrix $X$ and the dual slack matrix $Z$ are diagonal in LP but may only be symmetric in SDP; this results in $ZX$ not being symmetric in general, i.e. the optimality conditions in the SDP case end up as an overdetermined system of nonlinear equations.
There have been various approaches which modify the complementarity condition so that the linearization of the optimality conditions are "square", i.e. map between the same spaces. These approaches can have several drawbacks, e.g. numerical instability near the optimum and lack of positive definiteness after symmetrization. Our least squares approach requires no symmetrization and does not suffer from these drawbacks. We concentrate on solving the overdetermined, system in the best way possible. In particular, we use Gauss-Newton type methods. This leads to numerically stable as well as excellent search directions which lead to the central path. Though the numerical efficient calculation of the Gauss-Newton direction is still an open question, we present a preliminary "top down" elimination approach that is competitive time-wise and empirical evidence suggests that it is often more robust than other directions currently in use.
Improving the Parallelized Pollard Lambda Search on Binary Anomalous Curves
CORR 1998-15
Robert Gallant, Robert Lambert, and Scott Vanstone
Abstract
The best algorithm known for finding logarithms on an elliptic curve $(E)$ is the (parallelized) Pollard lambda collision search. We show how to apply a Pollard lambda search on a set of equivalence classes derived from $E$, which requires fewer iterations than the standard approach. In the case of binary anomalous curves over $F_{2}m$, the algorithm speeds up the standard algorithm by a factor $sqrt{2m}$.
III-conditioned convex processes and linear inequalities
CORR 1998-14
A.S. Lewis
Abstract
We prove the smallest possible norm of a linear perturbation making a closed convex process nonsurjective is the inverse of the norm of the inverse process. This generalizes the fundamental property of the condition number of a linear map. We then apply this result to strengthen a theorem of Renegar measuring the size of perturbation necessary to make an inequality system inconsistent
Nonsmooth Duality, Sandwhich and Squeeze Theorems
CORR 1998-13
A.S. Lewis and R.E. Lucchetti
Abstract
Given a nonlinear function $h$ separating a convex and a concave function, we provide various conditions under which there exists an affine separating function whose graph is somewhere almost parallel to the graph of $h$. Such results blend Fenchel duality with a variational principle, and are closely related to the Clarke-Ledyaev mean value inequality.
On the Embedding of Weighted Graphs in Euclidean Spaces
CORR 1998-12
Abdo Y. Alfakih and Henry Wolkowicz
Abstract
Given an incomplete edge-weighted graph, $G=(V,E. \omega), G$ is said to be embeddable in ${\cal R}^r$, or $r$-embeddable, if the vertices of $G$ can be mapped to points in ${\cal R}^r$ such that every two adjacent vertices $v_i, v_j$ of $G$ are mapped to points $x^i, x^j \in {\cal R}^r$ whose Euclidean distance is equal to the weight of the edge $(v_i, v_j)$. Barvinok [3] proved that if $G$ is $r$-embeddable for some $r$, then it is $r^*$-embeddable where $r^*= \lfloor ( \sqrt{8|E|+1} - 1)/2 \rfloor$. In this paper we provide a constructive proof of this result by presenting an algorithm to construct such an $r^*$-embedding.
Lidskii's theorem via nonsmooth analysis
CORR 1998-11
A.S. Lewis
Abstract
Lidskii's theorem on eigenvalue perturbation is proved via a nonsmooth mean value theorem.
Multivariate Asymptotics for Products of Large Powers with Applications to Lagrange Inversion
CORR 1998-10
Edward A. Bender and L. Bruce Richmond
Abstract
An asymptotic estimate is given for the coefficients of products of large powers of generating functions. This theorem and another local limit theorem which is useful for conditioning are applied to various combinatorial enumeration problems that involve multivariate Lagrange inversion.
A Multivariate Lagrange Inversion Formula for Asymptotic Calculations
CORR 1998-09
Edward A. Bender and L. Bruce Richmond
Abstract
The determinant that is present in traditional formulations of multivariate Lagrange inversion causes difficulties when one attempts to obtain asymptotic information. We obtain an alternate formulation as a sum of terms, thereby avoiding this difficulty. Unfortunately, our formulation involves a sum over trees and contains $(d+1)^{d-1}$ terms in contrast to the $d!$ terms of the determinantal form. Thus it is likely to prove useful only for asymptotic purposes.
On the Asymptotics of Partitions
CORR 1998-08
J.P. Bell and L.B. Richmond
Abstract
Given a positive integer $m$, we give necessary and sufficient conditions on a set of positive integers $A$ such that for any integers $i$ and $j$ one has that the number of partitions of $n$ into parts from $A$ and in which the number of parts used is congruent to $i$ mod $m$ is asymptotic to the number of partitions of $n$ into parts from $A$ and in which the number of parts used is congruent to $j$ mod $m$, as $n$ goes to infinity. We also give quite general conditions under which the number of partitions of $n$ into distinct parts from $A$ and in which the number of parts used is congruent to $i$ mod $m$ is asymptotic to the number of partitions of $n$ into distinct parts from $A$ and the number of parts used is congruent to $j$ mod $m$.
Polynomials with Odd Orthogonal Multiplicity
CORR 1998-07
Alan G.B. Lauder
Abstract
Let the orthogonal multiplicity of a monic-polynomial $g$ over a field ${F\!\!\!F}$ be the number of polynomials $f$ over ${F\!\!\!F}$, coprime to $g$ and of degree less than that of $g$, such that all the partial quotients of the continued fraction expansion of $f/g$ are of degree $1$. Polynomials with positive orthogonal multiplicity arise in stream cipher theory, part of cryptography, as the minimal polynomials of the initial segments of sequences which have perfect linear complexity profiles. This paper focuses on polynomials which have odd orthogonal multiplicity; such polynomials are characterized and a lower bound on their orthogonal multiplicity is given. A special case of a conjecture on rational functions over the finite field of two elements with partial quotients of degree $1$ or $2$ in their continued fraction expansion is also proved.
Cones of Matrices and Successive Convex Relaxations of Nonconvex Sets
CORR 1998-06
Masakazu Kojima and Levent Tuncel
Abstract
Let $F$ be a compact subset of the $n$-dimensional Euclidean space $R^n$ represented by (finitely or infinitely many) quadratic inequalities. We propose two methods, one based on successive semidefinite programming (SDP) relaxations and the other on successive linear programming (LP) relaxations. Each of our methods generates a sequence of compact convex subsets $C_k$ of $R^n (k=1, 2, \ldots)$ such that
(a) the convex hull of $F \subseteq C_{k+1} \subseteq C_k$ (monotonicity),
(b) \cap^{k*}_{k=1} C_k = \emptyset$ for some finite number $k*$ if $F=\emptyset$ (detecting infeasibility),
(c) $\cap^{\infty}_{k=1} C_k =$ the convex hull of $F$ otherwise (asymptotic convergence).
Our methods are extensions of the corresponding Lovasz-Schrijver lift-and-project procedures with the use of SDP or LP relaxation applied to general QPs (quadratic programs) with infinitely many quadratic inequality constraints. Utilizing descriptions of sets based on cones of matrices and their duals, we establish the exact equivalence of the SDP relaxation and the semi-infinite convex QP relaxation proposed originally by Fujie-Kojima. Using this equivalence, we investigate some fundamental features of the two methods including (a), (b) and (c) above.
An Efficient Protocol for Authenticated Key Agreement
CORR 1998-05
Laurie Law, Alfred Menezes, Minghua Qu, Jerry Solinas, and Scott Vanstone
Abstract
This paper proposes a new and efficient two-pass protocol for authenticated key agreement in the asymmetric (public-key) setting. The protocol is based on Diffie-Hellman key agreement and can be modified to work in an arbitrary finite group and, in particular, elliptic curve groups. Two modifications of this protocol are also presented: a one-pass authenticated key agreement protocol suitable for environments where only one entity is on-line, and a three-pass protocol in which key confirmation is additionally provided. The protocols are currently under consideration for standardization in ANSI X9.42 [2], ANSI X9.63 [4] and IEEE P1363 [18].
Pseudo-Linear Programming
CORR 1998-04
Serge Kruk and Henry Wolkowicz
Abstract
This short note revisits an algorithm previously sketched by Mathis and Mathis, Siam Review 1995, and used to solve a nonlinear hospital fee optimization problem. An analysis of the problem structure reveals how the Simplex algorithm, viewed under the correct light, can be the driving force behind a successful algorithm for a nonlinear problem.
Improved Approximation Algorithms for Finding Optimum k-Vertex Connected Spanning Subgraphs
CORR 1998-03
Zeev Nutov
Abstract
We consider the following problem: given an integer $k$ and a graph with a nonnegative cost function on its edges, find its minimum weight $k$-vertex connected spanning subgraph. For $k>1$, this problem is known to be NP-hard.
For an arbitrary $k$, the best known approximation algorithm is due to Ravi and Williamson which achieves the approximation ratio $2H(k)$, where $H(k) = 1 + \frac{1}{2} + \ldots + \frac{1}{k}$ is the $k$th Harmonic number. Dinitz and Nutov gave a better approximation algorithm for $k \leq 5$. In this paper we show how these two algorithms can be combined to achieve a slightly better approximation guarantee of $2[H(k-3)+ \frac{3}{k}] < 2H(k) - \frac{6}{k(k-1)}$ for all $k \geq 6$. For $k = 6,7$ we show even better algorithms with approximation ratios $4 \frac{1}{2},5$, improving $4 \frac{9}{10}, 5 \frac{13}{70}$, respectively.
Our results are based on the following property of $k$-out-connected digraphs (a digraph is called $k$-out-connected from $r$ if there exist $k$ internally disjoint paths from $r$ to every other vertex). We show that, any weighted digraph $D$ which is $k$-out-connected from a vertex $r$ of outdegree $k$, has, for any $l \leq k$, a spanning subdigraph $D'$ which is $l$-out connected from $r$, the outdegree of $r$ in $D'$ is exactly $l$, and the weight of $D'$ is at most $\frac{l}{k}$ the weight of $D$.
We also present an approximation algorithm for $k=4$, which has the same approximation ratio as the best previously known one, but is $O(n)$ times faster.
An Application of Ramp Schemes to Broadcast Encryption
CORR 1998-02
D.R. Stinson and R. Wei
Secure Frameproof Codes, Key Distribution Patterns, Group Testing Algorithms and Related Structures
CORR 1998-01
D.R. Stinson, Tran van Trung, and R. Wei
Abstract
Frameproof codes were introduced by Boneh and Shaw as a method of "digital fingerprinting" which prevents a coalition of a specified size c from framing a user not in the coalition. Stinson and Wei then gave a combinatorial formulation of the problem in terms of certain types of extremal set systems.
In this paper, we study frameproof codes that provide a certain (weak) form of traceability. We extend our combinatorial formulation to address this stronger requirement, and show that the problem is solved by using (i,j)-separating systems, as defined by Friedman, Graham and Ullman. Using constructions based on perfect hash families, we give the first efficient explicit constructions for these objects for general vlaues of i and j. We also review nonconstructive existence results that are based on probabilistic arguments.
Then we look at two other, related concepts, namely key distribution patterns and non-adaptive group testing algorithms. We again approach these problems from the point of view of extremal set systems, and we describe a natural common setting in which these two problems are complementary special cases. This approach also demonstrates a close relationship between these two problems and frameproof codes. Explicit constructions are given, and some non-constructive existence results are reviewed. In the case of the key distribution patterns, our explicit constructions are the most efficient ones known.