Public-Key Encryption from Homogeneous CLWE

被引：1

作者：

Bogdanov, Andrej ^{[1
]}

Noval, Miguel Cueto ^{[2
]}

Hoffmann, Charlotte ^{[2
]}

Rosen, Alon ^{[3
,4
]}

机构：

[1] Chinese Univ Hong Kong, Hong Kong, Peoples R China

[2] IST Austria, Klosterneuburg, Austria

[3] Bocconi Univ, Milan, Italy

[4] Reichman Univ, Herzliyya, Israel

来源：

THEORY OF CRYPTOGRAPHY, TCC 2022, PT II | 2022年 / 13748卷

关键词：

Public-key encryption; Continuous Learning with Errors; Statistical Zero-Knowledge; Hypercontractivity; Statistical-computational gaps; Discrete Gaussian Sampling;

D O I：

10.1007/978-3-031-22365-5_20

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The homogeneous continuous LWE (hCLWE) problem is to distinguish samples of a specific high-dimensional Gaussian mixture from standard normal samples. It was shown to be at least as hard as Learning with Errors, but no reduction in the other direction is currently known. We present four new public-key encryption schemes based on the hardness of hCLWE, with varying tradeoffs between decryption and security errors, and different discretization techniques. Our schemes yield a polynomial-time algorithm for solving hCLWE using a Statistical Zero-Knowledge oracle.

引用

页码：565 / 592

页数：28

共 26 条

[1] Ajtai M, 1997, P 20 9 ANN ACM S THE, P284, DOI DOI 10.1145/258533.258604
[2] More on average case vs approximation complexity
Alekhnovich, M
[J]. 44TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2003, : 298 - 307
[3] Applebaum B, 2010, ACM S THEORY COMPUT, P171
[4] POLYNOMIAL LEARNING OF DISTRIBUTION FAMILIES
Belkin, Mikhail
Sinha, Kaushik
[J]. SIAM JOURNAL ON COMPUTING, 2015, 44 (04) : 889 - 911
[5] Berthet Q., 2013, C LEARN THEOR, P1046
[6] Bogdanov A., 2022, 2022093 CRYPT EPRINT
[7] Brennan M, 2020, PR MACH LEARN RES, V125
[8] Continuous LWE
Bruna, Joan
Regev, Oded
Song, Min Jae
Tang, Yi
[J]. STOC '21: PROCEEDINGS OF THE 53RD ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2021, : 694 - 707
[9] Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures (Extended Abstract)
Diakonikolas, Ilias
Kane, Daniel M.
Stewart, Alistair
[J]. 2017 IEEE 58TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2017, : 73 - 84
[10] Dwork C, 2004, LECT NOTES COMPUT SC, V3027, P342

← 1 2 3 →