Semantic security for the McEliece cryptosystem without random oracles

In this paper, we formally prove that padding the plaintext with a random bit-string provides the semantic security against chosen plaintext attack (IND-CPA) for the McEliece (and its dual, the Niederreiter) cryptosystems under the standard assumptions. Such padding has recently been used by Suzuki, Kobara and Imai in the context of RFID security. Our proof relies on the technical result by Katz and Shin from Eurocrypt ’05 showing “pseudorandomness” implied by the learning parity with noise (LPN) problem. We do not need the random oracles as opposed to the known generic constructions which, on the other hand, provide a stronger protection as compared to our scheme—against (adaptive) chosen ciphertext attack, i.e., IND-CCA(2). In order to show that the padded version of the cryptosystem remains practical, we provide some estimates for suitable key sizes together with corresponding workload required for successful attack.     

On the completeness of a metric related to the Bergman metric

We study the completeness of a metric which is related to the Bergman metric of a bounded domain (sometimes called the Burbea metric or Fuks metric). We provide a criterion for its completeness in the spirit of the Kobayashi criterion for the completeness of the Bergman metric. In particular we prove that in hyperconvex domains our metric is complete.     

On analogs of the Hellinger metric

Translated from:Problemy Ustoichivosti Stokhasticheskikh Modelei, Trudy Seminara, 1989, pp. 55–59.     

On the metric dimension of HDN

The concept of metric basis is useful for robot navigation. In graph G, a robot is aware of its current location by sending signals to obtain the distances between itself and the landmarks in G. Its position is determined uniquely in G if it knows its distances to sufficiently many landmarks. The metric basis of G is defined as the minimum set of landmarks such that all other vertices in G can be uniquely determined and the metric dimension of G is defined as the cardinality of the minimum set of landmarks. The major contribution of this paper is that we have partly solved the open problem proposed by Manuel et al. [9], by proving that the metric dimension of $\text{HDN1}(n)$ and $\text{HDN2}(n)$ are either 3 or 4. However, the problem of finding the exact metric dimension of HDN networks is still open.     

On the non-Archimedean metric Mahler measure

Recently, Dubickas and Smyth constructed and examined the metric Mahler measure and the metric naïve height on the multiplicative group of algebraic numbers. We give a non-Archimedean version of the metric Mahler measure, denoted M_∞, and prove that M_∞(α)=1 if and only if α is a root of unity. We further show that M_∞ defines a projective height on as a vector space over Q. Finally, we demonstrate how to compute M_∞(α) when α is a surd.     

On the apollonian metric of domains in

We study the apollonian metric considered for sets in ? _n by Beardon in 1995. This metric was first introduced for plane Jordan domains by Barbilian in 1934. For a special class of plane domains Beardon showed that conformal apollonian isometries are Möbius transformations. We give here a proof of Beardon's result without conformality assumption. We show that the apollonian metric of a domain D is either conformal at every point of D, at only one point of D or at no point of D. We also present a suprising relation between convex bodies of constant width and the apollonian metric.     

On the curvature of contact metric manifolds

Some results on Ricci-symmetric contact metric manifolds are obtained. Second order parallel tensors and vector fields keeping curvature tensor invariant are characterized on a class of contact manifolds. Conformally flat contact manifolds are studied assuming certain curvature conditions. Finally some results onk-nullity distribution of contact manifolds are obtained.     

On the geometry of metric measure spaces

We introduce and analyze lower (Ricci) curvature bounds  ⩾ K for metric measure spaces . Our definition is based on convexity properties of the relative entropy regarded as a function on the L ₂-Wasserstein space of probability measures on the metric space . Among others, we show that  ⩾ K implies estimates for the volume growth of concentric balls. For Riemannian manifolds,  ⩾ K if and only if  ⩾ K for all . The crucial point is that our lower curvature bounds are stable under an appropriate notion of D-convergence of metric measure spaces. We define a complete and separable length metric D on the family of all isomorphism classes of normalized metric measure spaces. The metric D has a natural interpretation, based on the concept of optimal mass transportation. We also prove that the family of normalized metric measure spaces with doubling constant ⩽ C is closed under D-convergence. Moreover, the family of normalized metric measure spaces with doubling constant ⩽ C and diameter ⩽ L is compact under D-convergence.     

On the metrizability of cone metric spaces

We have shown in this paper that a (complete) cone metric space (X,E,P,d) is indeed (completely) metrizable for a suitable metric D. Moreover, given any finite number of contractions f₁,…,fn on the cone metric space (X,E,P,d), D can be defined in such a way that these functions become also contractions on (X,D).     

On the metric dimension of incidence graphs

A resolving set for a graph $\Gamma$ is a collection of vertices $S$, chosen so that for each vertex $v$, the list of distances from $v$ to the members of $S$ uniquely specifies $v$. The metric dimension$\mu \left(\Gamma \right)$ is the smallest size of a resolving set for $\Gamma$. We consider the metric dimension of two families of incidence graphs: incidence graphs of symmetric designs, and incidence graphs of symmetric transversal designs (i.e. symmetric nets). These graphs are the bipartite distance-regular graphs of diameter 3, and the bipartite, antipodal distance-regular graphs of diameter 4, respectively. In each case, we use the probabilistic method in the manner used by Babai to obtain bounds on the metric dimension of strongly regular graphs, and are able to show that $\mu \left(\Gamma \right)=O(\sqrt{n}logn)$ (where $n$ is the number of vertices).     

On the variation of a metric and its application

Some of the variation formulas of a metric were derived in the literatures by using the local coordinates system, In this paper, We give the first and the second variation formulas of the Riemannian curvature tensor, Ricci curvature tensor and scalar curvature of a metric by using the moving frame method. We establish a relation between the variation of the volume of a metric and that of a submanifold. We find that the latter is a consequence of the former. Finally we give an application of these formulas to the variations of heat invariants. We prove that a conformally flat metric g is a critical point of the third heat invariant functional for a compact 4-dimensional manifold M, then （M, g） is either scalar flat or a space form.     

On compactification of metric spaces

Iff:X →X* is a homeomorphism of a metric separable spaceX into a compact metric spaceX* such thatf(X)=X*, then the pair (f,X*) is called a metric compactification ofX. An absoluteG _δ-space (F _σ-space)X is said to be of the first kind, if there exists a metric compactification (f,X*) ofX such that , whereG _i are sets open inX* and dim[Fr(G _i)]<dimX. (Fr(G _i) being the boundary ofG _i and dimX — the dimension ofX). An absoluteG _δ-space (F _σ-space), which is not of the first kind, is said to be of the second kind. In the present paper spaces which are both absoluteG _δ andF _σ-spaces of the second kind are constructed for any positive finite dimension, a problem related to one of A. Lelek in [11] is solved, and a sufficient condition onX is given under which dim [X* −f(X)]≧k, for any metric compactification (f,X*) ofX, wherek≦dimX is a given number. This research has been sponsored by the U.S. Navy through the Office of Naval Research under contract No. 62558-3315.     

On metric spaces and local extrema

The main aim of this paper is to give a positive answer to a question of Behrends, Geschke and Natkaniec regarding the existence of a connected metric space and a non-constant real-valued continuous function on it for which every point is a local extremum. Moreover we show that real-valued continuous functions on connected spaces such that every family of pairwise disjoint non-empty open sets is of size <|R| are constant provided that every point is a local extremum.