No abstract uploaded!

No abstract uploaded!

No abstract uploaded!

In this paper we study the support recovery problem for single index models Y=f(X⊺β,ε), where f is an unknown link function, X∼Np(0,𝕀p) and β is an s-sparse unit vector such that βi∈{±1s√,0}. In particular, we look into the performance of two computationally inexpensive algorithms: (a) the diagonal thresholding sliced inverse regression (DT-SIR) introduced by Lin et al. (2015); and (b) a semi-definite programming (SDP) approach inspired by Amini & Wainwright (2008). When s=O(p1−δ) for some δ>0, we demonstrate that both procedures can succeed in recovering the support of β as long as the rescaled sample size κ=nslog(p−s) is larger than a certain critical threshold. On the other hand, when κ is smaller than a critical value, any algorithm fails to recover the support with probability at least 12 asymptotically. In other words, we demonstrate that both DT-SIR and the SDP approach are optimal (up to a scalar) for recovering the support of β in terms of sample size. We provide extensive simulations, as well as a real dataset application to help verify our theoretical observations.

LWE/RLWE-based cryptosystems require sampling error term from discrete Gaussian distribution. However, some existing samplers are somehow slow under certain circumstances therefore efficiency of such schemes is restricted. In this paper, we introduce a more efficient discretized Gaussian sampler based on ziggurat sampling algorithm. We also analyze statistical quality of our sampler to prove that it can be adopted in LWE/RLWE-based cryptosystems. Compared with ziggurat-based sampler by Buchmann et al. related samplers by Peikert, Ducas et al. and Knuth-Yao, our sampler achieves more than 2x speedup when standard deviation is large. This can benefit constructions rely on noise flooding (e.g., homomorphic encryption). We also present two applications: First, we use our sampler to optimize the RLWE-based authenticated key exchange (AKE) protocol by Zhang et al. We achieve 1.14x speedup on total runtime of this protocol over major parameter choices. Second, we give practical post-quantum Transport Layer Security (TLS) ciphersuite. Our ciphersuite inherits advantages from TLS and the optimized AKE protocol. Performance of our proof-of-concept implementation is close to TLS v1.2 ciphersuites and one post-quantum TLS construction.