中文版 | English
CSpace
A multi-key SMC protocol and multi-key FHE based on some-are-errorless LWE
Wang, Huiyong1; Feng, Yong2; Ding, Yong3; Tang, Shijie4
2019-03-01
摘要We study the hardness of learning with errors (LWE) problem with some equation constraints (LWEn,l,q,, some-are-errorless LWE). Previously, it was proved that LWE with one equation (first-is-errorless LWE) can be made as hard as the standard LWEn,q,, given a large lattice dimension n. We show that the some-are-errorless LWE problem can also be made equivalently hard as long as n is big enough and n >> l (A similar conclusion was given using fuzzy extrators by Fuller). A second work in this paper is to construct a multi-key secure multi-party computation (SMC) protocol, whose security relies on LWE and the some-are-errorless LWE problem in semi-honest and semi-malicious environments assuming the common random string model. We study the Gentry-Sahai-Waters (GSW13) fully homomorphic encryption (FHE) scheme and its key homomorphism, which is essential for the construction of our multi-key SMC protocol. The proposed protocol naturally constitutes a multi-key FHE scheme in the same settings. Finally, we show the excellence of the proposed SMC protocol in time and space complexity by comparisons with existing relative schemes.
关键词LWE FHE Key homomorphism SMC
DOI10.1007/s00500-017-2896-9
发表期刊SOFT COMPUTING
ISSN1432-7643
卷号23期号:5页码:1735-1744
通讯作者Ding, Yong(stone_dingy@126.com)
收录类别SCI
WOS记录号WOS:000459315900020
语种英语