Zero knowledge proofs from ring-LWE

ISCAS OpenIR

	Zero knowledge proofs from ring-LWE
	Xie, Xiang (1); Xue, Rui (2); Wang, Minqian (1)
	2013
Conference Name	12th International Conference on Cryptology and Network Security, CANS 2013
Pages	57-73
Conference Date	November 20, 2013 - November 22, 2013
Conference Place	Paraty, Brazil
Indexed Type	EI
Publish Place	Springer Verlag, Tiergartenstrasse 17, Heidelberg, D-69121, Germany
ISSN	3029743
ISBN	9783319029368
Department	(1) Trusted Computing and Information Assurance Laboratory, Institute of Software, Chinese Academy of Sciences, China; (2) State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, China
English Abstract	Zero-Knowledge proof is a very basic and important primitive, which allows a prover to prove some statement without revealing anything else. Very recently, Jain et al. proposed very efficient zero-knowledge proofs to prove any polynomial relations on bits, based on the Learning Parity with Noise (LPN) problem (Asiacrypt'12). In this work, we extend analogous constructions whose security is based on the Ring Learning with Errors (RLWE) problem by adapting the techniques presented by Ling et al. (PKC'13). Specifically, we show a simple zero-knowledge proof of knowledge (Σ-protocol) for committed values, and prove any polynomial relations in the underlying ring. I.e. proving committed ring elements m, m1 , ..., mt satisfying m = f (m 1 , ..., mt) for any polynomial f. Comparing to other existing Σ-protocols, the extracted witness (error vector) has length only small constant times than the one possessed by the prover. When representing ring element as elements in &Zdbl;q, our protocol has amortized communication complexity O˜(λ·\|f\|) with exponentially small soundness in security parameter λ, where \|f\| is the size of the circuit in &Zdbl;q computing f. © Springer International Publishing 2013.; Zero-Knowledge proof is a very basic and important primitive, which allows a prover to prove some statement without revealing anything else. Very recently, Jain et al. proposed very efficient zero-knowledge proofs to prove any polynomial relations on bits, based on the Learning Parity with Noise (LPN) problem (Asiacrypt'12). In this work, we extend analogous constructions whose security is based on the Ring Learning with Errors (RLWE) problem by adapting the techniques presented by Ling et al. (PKC'13). Specifically, we show a simple zero-knowledge proof of knowledge (Σ-protocol) for committed values, and prove any polynomial relations in the underlying ring. I.e. proving committed ring elements m, m1 , ..., mt satisfying m = f (m 1 , ..., mt) for any polynomial f. Comparing to other existing Σ-protocols, the extracted witness (error vector) has length only small constant times than the one possessed by the prover. When representing ring element as elements in &Zdbl;q, our protocol has amortized communication complexity O˜(λ·\|f\|) with exponentially small soundness in security parameter λ, where \|f\| is the size of the circuit in &Zdbl;q computing f. © Springer International Publishing 2013.
Language	英语
Content Type	会议论文
URI	http://ir.iscas.ac.cn/handle/311060/16690
Collection	中国科学院软件研究所
Recommended Citation GB/T 7714	Xie, Xiang ,Xue, Rui ,Wang, Minqian . Zero knowledge proofs from ring-LWE[C]. Springer Verlag, Tiergartenstrasse 17, Heidelberg, D-69121, Germany,2013:57-73.

Files in This Item:
There are no files associated with this item.

If you have any objections to this item, please fill out the form below and the administrator will contact you as soon as possible.
Content:
Email：	*
Institution:
Verification Code:	Refresh

Any comments and suggestions are welcomed.
Title:	*
Content:
Email：	*
Verification Code:	Refresh

中国科学院软件研究所机构知识库