Search

In this paper, we start with a discussion of discrete Gaussian measures on lattices. Several results of Banaszczyk are analyzed, a simple form of uncertainty principle for discrete Gaussian measure is formulated. In the second part of the paper we prove two new bounds for the smoothing parameter of lattices. Under the natural assumption that $$\varepsilon$$ is suitably small, we obtain two estimations of the smoothing parameter

Koblitz curves have been an important subject of consideration for both theoretical andpractical interests. The window $\tau$ -adic algorithm of Solinas (window $\tau$ NAF) is the most powerful method for computing point multiplication for Koblitz curves.Pre-computation plays an important role in improving the performance of point multiplication. In this paper, the concept of optimal pre-computation for window $\tau$ NAF is formulated. In this setting, an optimal pre-computation has some mathematically natural and clean forms, and requires $2^{w-2}-1$ point additions and two evaluations of the Frobenius map $\tau$ , where $w$ is the window width. One of the main results of this paper is to construct an optimal pre-computation scheme for each window width $w$ from $4$ to $15$ (more than practical needs).These pre-computations can be easily incorporated into implementations of window $\tau$ NAF. The ideas in the paper can also be used to construct other suitable pre-computations. This paper includes a discussion of coefficient sets for window $\tau$ NAF and the divisibility by powers of $\tau$ through different approaches. Some issues of implementation are also discussed.

In estimating frequencies given that the signal waveforms are undersampled multiple times, Xia et al. proposed to use a generalized version of Chinese remainder Theorem (CRT), where the moduli are \(M_1, M_2, \ldots , M_k\) which are not necessarily pairwise coprime. If the errors of the corrupted remainders are within \(\tau = \displaystyle \max _{1\le i\le k} \min _{{\mathop {j\ne i}\limits ^{1\le j\le k}}} \frac{\gcd (M_i,M_j)}{4}\), their schemes can be used to construct an approximation of the solution to the generalized CRT with an error smaller than \(\tau \). Accurately finding the quotients is a critical ingredient in their approach. In this paper, we shall start with a faithful historical account of the generalized CRT. We then present two treatments of the problem of solving generalized CRT with erroneous remainders. The first treatment follows the route of Wang and Xia to find the quotients, but with a simplified process. The second treatment considers a simplified model of generalized CRT and takes a different approach by working on the corrupted remainders directly. This approach also reveals some useful information about the remainders by inspecting extreme values of the erroneous remainders modulo \(4\tau \). Both of our treatments produce efficient algorithms with essentially optimal performance. Finally, this paper constructs a counterexample to prove the sharpness of the error bound \(\tau \).

This paper considers efficient scalar multiplication of elliptic curves over binary fields with a twofold purpose. Firstly, we derive the most efficient 3P formula in \(\lambda \)-projective coordinates and 5P formula in both affine and \(\lambda \)-projective coordinates. Secondly, extensive experiments have been conducted to test various multi-base scalar multiplication methods (e.g., greedy, ternary/binary, multi-base NAF, and tree-based) by integrating our fast formulas. The experiments show that our 3P and 5P formulas had an important role in speeding up the greedy, the ternary/binary, the multi-base NAF, and the tree-based methods over the NAF method. We also establish an efficient 3P formula for Koblitz curves and use it to construct an improved set for the optimal pre-computation of window TNAF.

In CRYPTO 2009, Lyubashevsky and Micciancio presented reductions BDD 1 / 2 γ (Bounded Distance Decoding Problem) ≤ uSVP γ (Unique Shortest Vector Problem) ≤ BDD 1 / γ , and posed an open problem whether the reduction gap can be closed. This paper concerns bounded distance decoding (BDD) problems for lattices with large λ 2 -gap. In the presence of larger λ 2 -gap, better reductions from BDD to uSVP and exact SVP are obtained. Some result can be regarded as a partial solution to the open problem. For some parameters, a better reduction from BDD to uSVP is given.An open problem proposed by Lyubashevsky and Micciancio is partially solved.This paper also improves a previous reduction from BDD to exact SVP.

Inspired by an interesting idea of Cai and Zhang, we formulate and prove the convex k-sparse decomposition of vectors that is invariant with respect to the l 1 norm. This result fits well in discussing compressed sensing problems under the Restricted Isometry property, but we believe it also has independent interest. As an application, a simple derivation of the RIP recovery condition δ k +θ k,k

This paper concerns the hardness of approximating the closest vector in a lattice with preprocessing in l 1 norm, and gives a polynomial time algorithm for GapCVPPγ in l 1 norm with gap γ = O(n/logn). The gap is smaller than that obtained by simply generalizing the approach given by Aharonov and Regev. The main technical ingredient used in this paper is the discrete Laplace distribution on lattices which may be of independent interest.

This paper discusses new bounds for restricted isometry constants in compressed sensing. Let Φ be an n × p real matrix and A; be a positive integer with k ≤ n. One of the main results of this paper shows that if the restricted isometry constant δk of Φ satisfies δk

This paper concerns the RSA system with private CRT-exponents. Since Chinese remainder representation provides efficiency in computation, such system is of some practical significance. In this paper, an existing attack to small private CRT-exponents is analyzed. It is indicated that this attack makes nice use of lattice in RSA analysis, but some argument does not hold in general. Several counterexamples are constructed. Refinements and more precise statements of the attack are given.

This article considers sparse signal recovery in the presence of noise. A mutual incoherence condition which was previously used for exact recovery in the noiseless case is shown to be sufficient for stable recovery in the noisy case. Furthermore, the condition is proved to be sharp. A specific counterexample is given. In addition, an oracle inequality is derived under the mutual incoherence condition in the case of Gaussian noise.

In this paper, we present a concise and coherent analysis of the constrained ?1 minimization method for stable recovering of high-dimensional sparse signals both in the noiseless case and noisy case. The analysis is surprisingly simple and elementary, while leads to strong results. In particular, it is shown that the sparse recovery problem can be solved via ?1 minimization under weaker conditions than what is known in the literature. A key technical tool is an elementary inequality, called Shifting Inequality, which, for a given nonnegative decreasing sequence, bounds the ?2 norm of a subsequence in terms of the ?1 norm of another subsequence by shifting the elements to the upper end.

A Steiner star for a set P of n points in R^d connects an arbitrary point in R^d to all points of P, while a star connects one of the points in P to the remaining n-1 points of P. All connections are realized by straight line segments. Let the length of a graph be the total Euclidean length of its edges. Fekete and Meijer showed that the minimum star is at most 2 times longer than the minimum Steiner star for any finite point configuration in R^d. The supremum of the ratio between the two lengths, over all finite point configurations in R^d, is called the star Steiner ratio in R^d. It is conjectured that this ratio is 4/@p=1.2732... in the plane and 4/3=1.3333... in three dimensions. Here we give upper bounds of 1.3631 in the plane, and 1.3833 in 3-space. These estimates yield improved upper bounds on the maximum ratios between the minimum star and the maximum matching in two and three dimensions. We also verify that the conjectured bound 4/@p in the plane holds in two special cases. Our method exploits the connection with the classical problem of estimating the maximum sum of pairwise distances among n points on the unit sphere, first studied by Laszlo Fejes Toth. It is quite general and yields the first nontrivial estimates below 2 on the star Steiner ratios in arbitrary dimensions. We show, however, that the star Steiner ratio in R^d tends to 2 as d goes to infinity. As it turns out, our estimates are related to the classical infinite Wallis product: @[email protected]?"n"="1^~(4n^24n^2-1)[email protected][email protected][email protected][email protected][email protected][email protected][email protected]?89....

The problem of linking the structure of a finite linear dynamical system with its dynamics is well understood when the phase space is a vector space over a finite field. The cycle structure of such a system can be described by the elementary divisors of the linear function, and the problem of determining whether the system is a fixed point system can be answered by computing and factoring the system's characteristic polynomial and minimal polynomial. It has become clear recently that the study of finite linear dynamical systems must be extended to embrace finite rings. The difficulty of dealing with an arbitrary finite commutative ring is that it lacks of unique factorization. In this paper, an efficient algorithm is provided for analyzing the cycle structure of a linear dynamical system over a finite commutative ring. In particular, for a given commutative ring $R$ such that $|R|=q$, where $q$ is a positive integer, the algorithm determines whether a given linear system over $R^n$ is a fixed point system or not in time $O(n^3\log(n\log(q)))$., To appear in Journal of Algebra (Computational Section). Code for the algorithm is available upon request

In his seminal papers, Koblitz proposed curves for cryptographic use. For fast operations on these curves, these papers also initiated a study of the radix-τ expansion of integers in the number fields and . The (window) nonadjacent form of τ -expansion of integers in was first investigated by Solinas. For integers in , the nonadjacent form and the window nonadjacent form of the τ -expansion were studied. These are used for efficient point multiplications on Koblitz curves. In this paper, we complete the picture by producing the (window) nonadjacent radix-τ expansions for integers in all Euclidean imaginary quadratic number fields.

The window τ-adic algorithm of Solinas [Efficient arithmetic on Koblitz curves, Designs, Codes and Cryptography 19 (2000) 195] is the most powerful method for computing point multiplication for Koblitz curves. In this note, the existence of a more general window τ-adic form for each element in Z[τ] is obtained. In particular, this provides a proof of the termination of Solinas algorithm.

The nonadjacent form method of Koblitz [Advances in Cryptology (CRYPTO'98), in: Lecture Notes in Comput. Sci., vol. 1462, 1998, pp. 327–337] is an efficient algorithm for point multiplication on a family of supersingular curves over a finite field of characteristic 3. In this paper, a further discussion of the method is given. A window nonadjacent form method is proposed and its validity is proved. Efficient reduction and pre-computations are given. Analysis shows that more than 30% of saving can be achieved.

It is known that for an amenable locally compact group G, 0 is not in the weak closure of {A(g): g E G} of VN(G). In this paper, it is proved that the converse of this is true. In other words, if G is a non-amenable locally compact group, then 0 is in the weak closure of {A(g): g E G}. This answers several questions of Ulger. Applications to the algebra C,; (G) and the dual of the reduced group C*-algebra are obtained.

According to an old result of Turán, any ( n + 1)-subset of {1, 2, ..., 2 n } contains a pair of divisible numbers. Ciurea et al. have recently considered a natural algorithmic variant of this classic mathematical result: if the subset is not known, and it is only accessible via a membership oracle, what is the minimum number of questions necessary to identify one such divisible pair? They showed a 4/3 n -- O (1) lower bound and also designed an algorithm which they conjectured asks no more than 4/3 n + O (1) queries, and therefore would be optimal. We reanalyze the proposed algorithm and prove that it comes close to the conjectured value, in asking no more than (4/3 + 5/108) n + O (1) queries; this corrects an error in the old analysis.

For a locally compact group G G and 1 > p > ∞ 1>p>\infty , let A p ( G ) A_{p}(G) be the Herz–Figà-Talamanca algebra and B p ( G ) B_{p}(G) the Herz-Schur multipliers of G G , and M A p ( G ) MA_{p}(G) the multipliers of A p ( G ) A_{p}(G) . Let W ( G ) W(G) be the algebra of continuous weakly almost periodic functions on G G . In this paper, we show that (1), if G G is a noncompact nilpotent group or a noncompact [IN]-group, then W ( G ) / B p ( G ) − W(G)/B_{p}(G)^{-} contains a linear isometric copy of l ∞ ( N ) l^{\infty }({\mathbb {N}}) ; (2), for a noncommutative free group F , B p ( F ) F, B_{p}(F) is a proper subset of M A p ( F ) ∩ W ( F ) {MA_{p}(F)\cap {W(F)}} .

The class of Fourier matrices is of special importance in compressed sensing (CS). This paper concerns deterministic construction of compressed sensing matrices from Fourier matrices. By using Katz' character sum estimation, we are able to design a deterministic procedure to select rows from a Fourier matrix to form a good compressed sensing matrix for sparse recovery. The sparsity bound in our construction is similar to that of binary CS matrices constructed by DeVore which greatly improves previous results for CS matrices from Fourier matrices. Our approach also provides more flexibilities in terms of the dimension of CS matrices. As a consequence, our construction yields an approximately mutually unbiased bases from Fourier matrices which is of particular interest to quantum information theory. This paper also contains a useful improvement to Katz' character sum estimation for quadratic extensions, with an elementary and transparent proof. Some numerical examples are included., 17 pages

In this paper, it is shown that for every discrete group G and 1 > p > ∞ , A p ( G ) ⋅ P M p ( G ) 1 > p > \infty ,{A_p}(G) \cdot P{M_p}(G) is closed in P M p ( G ) P{M_p}(G) if and only if G is amenable.

This paper considers constrained lscr1 minimization methods in a unified framework for the recovery of high-dimensional sparse signals in three settings: noiseless, bounded error, and Gaussian noise. Both lscr1 minimization with an lscrinfin constraint (Dantzig selector) and lscr1 minimization under an llscr2 constraint are considered. The results of this paper improve the existing results in the literature by weakening the conditions and tightening the error bounds. The improvement on the conditions shows that signals with larger support can be recovered accurately. In particular, our results illustrate the relationship between lscr1 minimization with an llscr2 constraint and lscr1 minimization with an lscrinfin constraint. This paper also establishes connections between restricted isometry property and the mutual incoherence property. Some results of Candes, Romberg, and Tao (2006), Candes and Tao (2007), and Donoho, Elad, and Temlyakov (2006) are extended.

In this paper, some issues concerning the Chinese remaindering representation are discussed. A new converting method, which is an efficient probabilistic algorithm based on a recent result of von zur Gathen and Shparlinski [J. von zur Gathen, I. Shparlinski, GCD of random linear forms, Algorithmica 46 (2006) 137-148], is described. An efficient refinement of the NC^1 division algorithm of Chiu, Davida and Litow [A. Chiu, G. Davida, B. Litow, Division in logspace-uniform NC^1, Theoret. Informatics Appl. 35 (2001) 259-275] is given, where the number of moduli is reduced by a factor of logn.

Some relations between dense languages and their semidiscrete disjunctive sublanguages are considered. Several decompositions of dense languages into disjunctive components are established. As an application, it is shown that every language is either the disjoint union or the intersection of two disjunctive languages.