QQ客服 官方微博 反馈留言

	Zero knowledge proofs from ring-LWE
	Xie, Xiang (1) ; Xue, Rui (2) ; Wang, Minqian (1)
	2013
会议名称	12th International Conference on Cryptology and Network Security, CANS 2013
会议日期	November 20, 2013 - November 22, 2013
会议地点	Paraty, Brazil
页码	57-73
中文摘要	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.
收录类别	EI
会议录出版地	Springer Verlag, Tiergartenstrasse 17, Heidelberg, D-69121, Germany
语种	英语
ISSN号	3029743
ISBN号	9783319029368
内容类型	会议论文
源URL	[http://ir.iscas.ac.cn/handle/311060/16690]
专题	软件研究所_软件所图书馆_会议论文
推荐引用方式 GB/T 7714	Xie, Xiang ,Xue, Rui ,Wang, Minqian . Zero knowledge proofs from ring-LWE[C]. 见:12th International Conference on Cryptology and Network Security, CANS 2013. Paraty, Brazil. November 20, 2013 - November 22, 2013.

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。