Cryptanalytic results on ‘Dual CRT’ and ‘Common Prime’ RSA

In this paper we study weaknesses of two variants of RSA: Dual RSA and Common Prime RSA. Several schemes under the framework of Dual RSA have been proposed by Sun et al. (IEEE Trans Inf Theory 53(8):2922–2933, 2007). We here concentrate on the Dual CRT-RSA scheme and present certain range of parameters where it is insecure. As a corollary of our work, we prove that the Dual Generalized Rebalanced-RSA (Scheme III of Sun et al.) can be efficiently broken for a significant region where the scheme has been claimed to be secure. Next we consider the Common Prime RSA as proposed by Wiener (IEEE Trans. Inf. Theory 36:553–558, 1990). We present new range of parameters in Common Prime RSA where it is not secure. We use lattice based techniques for the attacks.     

Small secret exponent attack on RSA variant with modulus N=p^rq

We consider an RSA variant with Modulus \(N=p^rq\) . This variant is known as Prime Power RSA. In PKC 2004, May proved when decryption exponent \(d<N^{ \frac{r}{(r+1)^2}}\) or \(d< N^{\left( \frac{r-1}{r+1}\right) ^2}\) , one can factor \(N\) in polynomial time. In this paper, we improve this bound when \(r \le 5\) . We provide detailed experimental results to justify our claim.     

Anonymous and leakage resilient IBE and IPE

We construct identity-based encryption and inner product encryption schemes under the decision linear assumption. Their private user keys are leakage-resilient in several scenarios. In particular,

• In the bounded memory leakage model (Akavia et al., TCC, vol. 5444, pp. 474–495, 2009), our basic schemes reach the maximum-possible leakage rate \(1-o(1)\).
• In the continual memory leakage model (Brakerski et al., Overcoming the hole in the bucket: public-key cryptography resilient to continual memory leakage, 2010; Dodis et al., Cryptography against continuous memory attacks, 2010), variants of the above schemes enjoy leakage rate at least \(\frac{1}{2} -o(1)\). Among the results, we improve upon the work of Brakerski et al. by presenting adaptively secure IBE schemes.

In addition, we prove that our IBE schemes are anonymous under the DLIN assumption, so that ciphertexts leaks no information on the corresponding identities. Similarly, attributes in IPE are proved computationally hidden in the corresponding ciphertexts.

     

Multivariate public key cryptosystems from diophantine equations

Wang et al. introduced in (A medium-field multivariate public-key encryption scheme. Topics in Cryptology—CTRSA 2006: The Cryptographers’ Track at the RSA Conference, 2006) a multivariate public key cryptosystem, called MFE cryptosystem, and it is appealing as it is based on a simple polynomial identity. Their system, however, was subsequently broken by Ding et al. in (High order linearization equation (hole) attack on multivariate public key cryptosystems. Public key cryptography—PKC 2007: 10th international conference on practice and theory in public-key cryptography, 2007a, ?-Invertible cycles for multivariate quadratic public key cryptography. Public key cryptography—PKC 2007: 10th international conference on practice and theory in public-key cryptography, 2007b). Inspired by their work, we present a more general framework for multivariate public key cryptosystems, which combines ideas from both triangular and oil-vinegar schemes. Within this framework, we propose a new public key cryptosystem based on a solution of a Diophantine equation over polynomial rings.     

A Note on Variable Exponent Hörmander Spaces

In this paper we introduce the variable exponent Hörmander spaces and we study some of their properties. In particular, it is shown that ${{(\mathcal{B}_{p_{(\cdot)}}^{c}(\Omega))^{\prime}}}$ is isomorphic to ${{\mathcal{B}^{loc}_{\widetilde{p^\prime(\cdot)}(\Omega)}}}$ (Ω open set in ${{\mathbb{R}^n, p? > 1}}$ and the Hardy–Littlewood maximal operator M is bounded in ${L_p(\cdot))}$ extending a Hörmander’s result to our context. As a consequence, a number of results on sequence space representations of variable exponent Hörmander spaces are given.     

A characterization for truncated cauchy random variables with nonzero skewness parameter

Soltani and Shirvani (Comput Stat 25:155–161, 2010) provided a characterization and a simulation method for truncated stable random variables when the characteristic exponent $\alpha \ne 1 $ , and left the case $\alpha =1$ open. The case of $\alpha =1$ is treated in this article.     

Degenerate U- and V-statistics under ergodicity: asymptotics, bootstrap and applications in statistics

We derive the asymptotic distributions of degenerate $U$ - and $V$ -statistics of stationary and ergodic random variables. Statistics of these types naturally appear as approximations of test statistics. Since the limit variables are of complicated structure, typically depending on unknown parameters, quantiles can hardly be obtained directly. Therefore, we prove a general result on the consistency of model-based bootstrap methods for $U$ - and $V$ -statistics under easily verifiable conditions. Three applications to hypothesis testing are presented. Finally, the finite sample behavior of the bootstrap-based tests is illustrated by a simulation study.     

Bounding the exponent of a verbal subgroup

We deal with the following conjecture. If \(w\) is a group word and \(G\) is a finite group in which any nilpotent subgroup generated by \(w\) -values has exponent dividing \(e\) , then the exponent of the verbal subgroup \(w(G)\) is bounded in terms of \(e\) and \(w\) only. We show that this is true in the case where \(w\) is either the \(n\text{ th }\) Engel word or the word \([x^n,y_1,y_2,\ldots ,y_k]\) (Theorem A). Further, we show that for any positive integer \(e\) there exists a number \(k=k(e)\) such that if \(w\) is a word and \(G\) is a finite group in which any nilpotent subgroup generated by products of \(k\) values of the word \(w\) has exponent dividing \(e\) , then the exponent of the verbal subgroup \(w(G)\) is bounded in terms of \(e\) and \(w\) only (Theorem B).     

Calculus of the Exponent of Kurdyka–Łojasiewicz Inequality and Its Applications to Linear Convergence of First-Order Methods

In this paper, we study the Kurdyka–?ojasiewicz (KL) exponent, an important quantity for analyzing the convergence rate of first-order methods. Specifically, we develop various calculus rules to deduce the KL exponent of new (possibly nonconvex and nonsmooth) functions formed from functions with known KL exponents. In addition, we show that the well-studied Luo–Tseng error bound together with a mild assumption on the separation of stationary values implies that the KL exponent is \(\frac{1}{2}\). The Luo–Tseng error bound is known to hold for a large class of concrete structured optimization problems, and thus we deduce the KL exponent of a large class of functions whose exponents were previously unknown. Building upon this and the calculus rules, we are then able to show that for many convex or nonconvex optimization models for applications such as sparse recovery, their objective function’s KL exponent is \(\frac{1}{2}\). This includes the least squares problem with smoothly clipped absolute deviation regularization or minimax concave penalty regularization and the logistic regression problem with \(\ell _1\) regularization. Since many existing local convergence rate analysis for first-order methods in the nonconvex scenario relies on the KL exponent, our results enable us to obtain explicit convergence rate for various first-order methods when they are applied to a large variety of practical optimization models. Finally, we further illustrate how our results can be applied to establishing local linear convergence of the proximal gradient algorithm and the inertial proximal algorithm with constant step sizes for some specific models that arise in sparse recovery.     

On ideals with the Rees property

A homogeneous ideal I of a polynomial ring S is said to have the Rees property if, for any homogeneous ideal ${J \subset S}$ which contains I, the number of generators of J is smaller than or equal to that of I. A homogeneous ideal ${I \subset S}$ is said to be ${\mathfrak{m}}$ -full if ${\mathfrak{m}I:y=I}$ for some ${y \in \mathfrak{m}}$ , where ${\mathfrak{m}}$ is the graded maximal ideal of ${S}$ . It was proved by one of the authors that ${\mathfrak{m}}$ -full ideals have the Rees property and that the converse holds in a polynomial ring with two variables. In this note, we give examples of ideals which have the Rees property but are not ${\mathfrak{m}}$ -full in a polynomial ring with more than two variables. To prove this result, we also show that every Artinian monomial almost complete intersection in three variables has the Sperner property.     

A non-parametric Bayesian approach to decompounding from high frequency data

Given a sample from a discretely observed compound Poisson process, we consider non-parametric estimation of the density \(f_0\) of its jump sizes, as well as of its intensity \(\lambda _0.\) We take a Bayesian approach to the problem and specify the prior on \(f_0\) as the Dirichlet location mixture of normal densities. An independent prior for \(\lambda _0\) is assumed to be compactly supported and to possess a positive density with respect to the Lebesgue measure. We show that under suitable assumptions the posterior contracts around the pair \((\lambda _0,\,f_0)\) at essentially (up to a logarithmic factor) the \(\sqrt{n\Delta }\)-rate, where n is the number of observations and \(\Delta \) is the mesh size at which the process is sampled. The emphasis is on high frequency data, \(\Delta \rightarrow 0,\) but the obtained results are also valid for fixed \(\Delta .\) In either case we assume that \(n\Delta \rightarrow \infty .\) Our main result implies existence of Bayesian point estimates converging (in the frequentist sense, in probability) to \((\lambda _0,\,f_0)\) at the same rate. We also discuss a practical implementation of our approach. The computational problem is dealt with by inclusion of auxiliary variables and we develop a Markov chain Monte Carlo algorithm that samples from the joint distribution of the unknown parameters in the mixture density and the introduced auxiliary variables. Numerical examples illustrate the feasibility of this approach.     

Hochschild Homology Invariants of Külshammer Type of Derived Categories

For a perfect field k of characteristic p > 0 and for a finite dimensional symmetric k-algebra A Külshammer studied a sequence of ideals of the centre of A using the p-power map on degree 0 Hochschild homology. In joint work with Bessenrodt and Holm we removed the condition to be symmetric by passing through the trivial extension algebra. If A is symmetric, then the dual to the Külshammer ideal structure was generalised to higher Hochschild homology in earlier work [23 Zimmermann , A. ( 2007 ). Fine Hochschild invariants of derived categories for symmetric algebras . Journal of Algebra 308 : 350 – 367 . [Google Scholar]]. In the present article we follow this program and propose an analogue of the dual to the Külshammer ideal structure on the degree m Hochschild homology theory also to not necessarily symmetric algebras.     

Decomposable and indecomposable algebras of degree 8 and exponent 2

We study the decomposition of central simple algebras of exponent 2 into tensor products of quaternion algebras. We consider in particular decompositions in which one of the quaternion algebras contains a given quadratic extension. Let $B$ be a biquaternion algebra over $F(\sqrt{a})$ with trivial corestriction. A degree 3 cohomological invariant is defined and we show that it determines whether $B$ has a descent to $F$ . This invariant is used to give examples of indecomposable algebras of degree $8$ and exponent 2 over a field of 2-cohomological dimension 3 and over a field $\mathbb M(t)$ where the $u$ -invariant of $\mathbb M$ is $8$ and $t$ is an indeterminate. The construction of these indecomposable algebras uses Chow group computations provided by Merkurjev in “Appendix”.     

Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function

In this paper we develop a randomized block-coordinate descent method for minimizing the sum of a smooth and a simple nonsmooth block-separable convex function and prove that it obtains an $\varepsilon $ -accurate solution with probability at least $1-\rho $ in at most $O((n/\varepsilon ) \log (1/\rho ))$ iterations, where $n$ is the number of blocks. This extends recent results of Nesterov (SIAM J Optim 22(2): 341–362, 2012), which cover the smooth case, to composite minimization, while at the same time improving the complexity by the factor of 4 and removing $\varepsilon $ from the logarithmic term. More importantly, in contrast with the aforementioned work in which the author achieves the results by applying the method to a regularized version of the objective function with an unknown scaling factor, we show that this is not necessary, thus achieving first true iteration complexity bounds. For strongly convex functions the method converges linearly. In the smooth case we also allow for arbitrary probability vectors and non-Euclidean norms. Finally, we demonstrate numerically that the algorithm is able to solve huge-scale $\ell _1$ -regularized least squares problems with a billion variables.     

Wellposedness of second order backward SDEs

We provide an existence and uniqueness theory for an extension of backward SDEs to the second order. While standard Backward SDEs are naturally connected to semilinear PDEs, our second order extension is connected to fully nonlinear PDEs, as suggested in Cheridito et?al. (Commun. Pure Appl. Math. 60(7):1081–1110, 2007). In particular, we provide a fully nonlinear extension of the Feynman–Kac formula. Unlike (Cheridito et?al. in Commun. Pure Appl. Math. 60(7):1081–1110, 2007), the alternative formulation of this paper insists that the equation must hold under a non-dominated family of mutually singular probability measures. The key argument is a stochastic representation, suggested by the optimal control interpretation, and analyzed in the accompanying paper (Soner et?al. in Dual Formulation of Second Order Target Problems. arXiv:1003.6050, 2009).     

The Antipode of a Braided Dual Quasi-Hopf Algebra is Bijective

We show that the antipode of a braided dual quasi-Hopf algebra is inner, and, a fortiori, bijective. This improves a result of Li [10 Li , J. Q. ( 2006 ). Dual quasi-Hopf algebras and antipodes . Algebra Colloquium 13 : 111 – 118 .[Crossref] , [Google Scholar]].     

Gowers $$U_3$$ norm of some classes of bent Boolean functions

The Gowers \(U_3\) norm of a Boolean function is a measure of its resistance to quadratic approximations. It is known that smaller the Gowers \(U_3\) norm for a Boolean function larger is its resistance to quadratic approximations. Here, we compute Gowers \(U_3\) norms for some classes of Maiorana–McFarland bent functions. In particular, we explicitly determine the value of the Gowers \(U_3\) norm of Maiorana–McFarland bent functions obtained by using APN permutations. We prove that this value is always smaller than the Gowers \(U_3\) norms of Maiorana–McFarland bent functions obtained by using differentially \(\delta \)-uniform permutations, for all \(\delta \ge 4\). We also compute the Gowers \(U_3\) norms for a class of cubic monomial functions, not necessarily bent, and show that for \(n=6\), these norm values are less than that of Maiorana–McFarland bent functions. Further, we computationally show that there exist 6-variable functions in this class which are not bent but achieve the maximum second-order nonlinearity for 6 variables.     

Exponents of polar codes using algebraic geometric code kernels

Reed–Solomon and BCH codes were considered as kernels of polar codes by Mori and Tanaka (IEEE Information Theory Workshop, 2010, pp 1–5) and Korada et al. (IEEE Trans Inform Theory 56(12):6253–6264, 2010) to create polar codes with large exponents. Mori and Tanaka showed that Reed–Solomon codes over the finite field \(\mathbb {F}_q\) with \(q\) elements give the best possible exponent among all codes of length \(l \le q\) . They also stated that a Hermitian code over \(\mathbb {F}_{2^r}\) with \(r \ge 4\) , a simple algebraic geometric code, gives a larger exponent than the Reed–Solomon matrix over the same field. In this paper, we expand on these ideas by employing more general algebraic geometric (AG) codes to produce kernels of polar codes. Lower bounds on the exponents are given for kernels from general AG codes, Hermitian codes, and Suzuki codes. We demonstrate that both Hermitian and Suzuki kernels have larger exponents than Reed–Solomon codes over the same field, for \(q \ge 3\) ; however, the larger exponents are at the expense of larger kernel matrices. Comparing kernels of the same size, though over different fields, we see that Reed–Solomon kernels have larger exponents than both Hermitian and Suzuki kernels. These results indicate a tradeoff between the exponent, kernel matrix size, and field size.     

A note on “Reducing the number of binary variables in cutting stock problems”

This study proposes a deterministic model to solve the two-dimensional cutting stock problem (2DCSP) using a much smaller number of binary variables and thereby reducing the complexity of 2DCSP. Expressing a 2DCSP with $m$ stocks and $n$ cutting rectangles requires $2n^{2}+n(m+1)$ binary variables in the traditional model. In contrast, the proposed model uses $n^{2}+n\lceil {\log _2 m}\rceil $ binary variables to express the 2DCSP. Experimental results showed that the proposed model is more efficient than the existing model.     

Regularity of harmonic maps from polyhedra to CAT(1) spaces

We determine regularity results for energy minimizing maps from an n-dimensional Riemannian polyhedral complex X into a CAT(1) space. Provided that the metric on X is Lipschitz regular, we prove Hölder regularity with Hölder constant and exponent dependent on the total energy of the map and the metric on the domain. Moreover, at points away from the \((n-2)\)-skeleton, we improve the regularity to locally Lipschitz. Finally, for points \(x \in X^{(k)}\) with \(k \le n-2\), we demonstrate that the Hölder exponent depends on geometric and combinatorial data of the link of \(x \in X\).