Two functions Δ and Δ_{$b$}, of interest in combinatorial geometry and the theory of linear programming, are defined and studied. Δ($d, n$) is the maximum diameter of convex polyhedra of dimension$d$with$n$faces of dimension$d$−1; similarly, Δ_{$b$}($d,n$) is the maximum diameter of bounded polyhedra of dimension$d$with$n$faces of dimension$d$−1. The diameter of a polyhedron$P$is the smallest integer$l$such that any two vertices of$P$can be joined by a path of$l$or fewer edges of$P$. It is shown that the bounded$d$-step conjecture, i.e. Δ_{$b$}$(d,2d)=d$, is true for$d$≤5. It is also shown that the general$d$-step conjecture, i.e. Δ($d, 2d$)≤$d$, of significance in linear programming, is false for$d$≥4. A number of other specific values and bounds for Δ and Δ_{$b$}are presented.

No abstract uploaded!

No abstract uploaded!

In this paper, we introduce a new provably secure ephemeral-only RLWE+Rounding-based key exchange protocol and a proper approach to more accurately estimate the security level of the RLWE problem with only one sample. Since our scheme is an ephemeral-only key exchange, it generates only one RLWE sample from protocol execution. We carefully analyze how to estimate the practical security of the RLWE problem with only one sample, which we call the ONE-sample RLWE problem. Our approach is different from existing approaches that are based on estimation with multiple RLWE samples. Though our analysis is based on some recently developed techniques in Darmstadt, our type of practical security estimate was never done before and it produces security estimates substantial different from the estimates before based on multiple RLWE samples. We show that the new design improves the security and reduce the communication cost of the protocol simultaneously by using one RLWE+Rounding sample technique. We also present two parameter choices ensuring 2^{−60} key exchange failure probability which cover security of AES-128/192/256 with concrete security analysis and implementation. We believe that our construction is secure, simple, efficient and elegant with wide application prospects.

No abstract uploaded!