安全多方計算若干問題的研究

1、中文摘要中文摘要安全多方計算( S e c u r e M u l t i —p a r t y C o m p u t a t i o n ，S M C ) 最早是由A C ．y n D 提出，簡單地描述如下：設(shè)P = { 最，B ，．．．R ) 是n 個參與者的集合，他們想要通過相互傳遞信息的方式安全地計算某個給定函數(shù)，( z ·，x 2 ?．，x n ) = ( Y l ，耽，．．．，‰) ，其中函數(shù)，的釓個輸入( z

2、1 ，z 2 ，．．．，z n ) 分別由n 個參與者B ，島，．．．R 秘密地掌握而不被其他人知道，在計算結(jié)束后要求最，島，．．．R 分別得到Y(jié) 1 ，拋，．．．，‰，這里的安全主要指參與者只@ = 1 ，2 ?．，n ) 得不到關(guān)于參與者弓的％和Y j ( J = 1 ，2 ，．．．，i 一1 ，i + 1 ，．．．，釓) 的任何信息‰和犰隱含信息除外) 。S M C 是電子選舉、電子拍賣以及門限簽名等諸多應(yīng)用得以實現(xiàn)的重要密碼學(xué)基

3、礎(chǔ)。．9 M C 協(xié)議涉及到許多的底層密碼協(xié)議，目前提出的方案使用到了秘密共享、公鑰和私鑰加密、同態(tài)加密以及不經(jīng)意傳輸?shù)戎T多常用的算法和安全協(xié)議。最近幾年人們對于多方保密計算進(jìn)行了廣泛而深入的研究，針對的問題包括保密比較兩個數(shù)的大小、保密的數(shù)據(jù)挖掘、保密的數(shù)據(jù)庫查詢、保密拍賣、保密的科學(xué)計算、保密的統(tǒng)計分析、保密的幾何計算等。本文的工作主要有：1 ．定義了帶有不經(jīng)意第三方的兩方保密比較協(xié)議的安全性，并在此基礎(chǔ)上分析了秦靜等人基于由一隱性

4、假設(shè)和同態(tài)公鑰加密的兩方保密比較協(xié)議的安全性、正確性及公平性；2 ．提出了一個基于對稱加密的帶有不經(jīng)意第三方的兩方保密比較協(xié)議，并在安全模型下證明了該協(xié)議的安全性；對秦靜等人的保密比較協(xié)議和基于對稱加密的比較協(xié)議，從通信復(fù)雜度、計算復(fù)雜度及安全性等方面分析和比較，前者更具有理論價值，而后者更具有實際應(yīng)用價值；3 ．提出了一個用R S A 密碼體制和不經(jīng)意傳輸來解決保密排序協(xié)議的解決方案，該方案與多次使用A C ．Y a o 的協(xié)議相比，

5、在安全性、公平性及效率上都有提高。關(guān)鍵詞：密碼學(xué)；安全多方計算o ，保密比較；保密排序lI I I I I I IR i l l I I I I IL I I I II $ 1 1 1 IY 2 i 2 4 9 4 0黑龍江大學(xué)碩士學(xué)位論文A b s t r a c tS e c u r eM u l t i —p a r t yC o m p u t a t i o nf i r s t p u tf o r w a r db yA

6、．C ．Y a o ，s i m p l yd e s c r i b e da s f o l l o w s ：P = ( R ，B ，．．．R ) i sas e t o fnp a r t i c i p a n t s ，t h e yw a n tt os e c u r e l yc o m p u t e ag i v e n f u n c t i o nf ( x l ，X 2 ' ．．．，z n ) = (

7、 Y l ，Y 2 ' ．．．，‰) b yt r a n s m i s s i o no fi n f o r m a t i o n e a c h o t h e r ．T h e 仡i n p u t so ff u n c t i o nf a r ep r o v i d e d b y 禮p a r t i c i p a n t ss e p a r a t e l y ．R e q u r i n g R ，

8、馬，．．．R o b t a i nY l ，Y 2 ，．．．，‰s e p a r a t e l y a f t e r c o m p u t a t i o n ，s e c u r i t ym a i n l ym e a n s t h a t 只( i = 1 ，2 ，．．．，n ) c a nn o tg e ta n y t h i n g a b o u t i n f o r m a t i o n兢a n d

9、瓠0 = 1 ，2 ，．．．，i 一1 ，i + 1 ，．．．，n ) e x c e p tt h ei n f o r m a t i o ni m p l i e db y 筑a n d 璣．SM ci s e l e c t r o n i ce l e c t i o n s ，e l e c t r o n i c a u c t i o na n dt h r e s h o l ds i g n a t u r e la

10、 n dm a n y o t h e ra p p l i c a t i o n st ot h e r e a l i z a t i o no fi m p o r t a n tc r y p t o g r a p h yb a s i s ．S M Cp r o t o c o l i n v o l v e sm a n y o ft h e g r o u n d f l o o r o ft h e p a s s

11、w o r da g r e e m e n t ，a tp r e s e n t t h ep r o p o s e ds o l u t i o n su s et os e c r e ts h a r i n g ，p u b l i ca n d p r i v a t ek e y e n c r y p t i o n ，h o m o -m o r p h i s m s e n c r y p t i o na n

12、 dc a s u a lt r a n s m i s s i o n ，a n dm a n y o t h e r c o I I n 3 2 0 na l g o r i t h ma n d s e c u r i t ya g r e e m e n t ．I nr e c e n ty e a r s ，p e o p l ef o rm u l t i —p a r t yc o m p u t a t i o nm a

13、 d ee x t e n s i v e a n di n - d e p t hr e s e a r c ho nt h ep r o b l e m s i n c l u d i n g c o n f i d e n t i a l i t y i st h e s i z eo ft h e t w oN u m b e r s ，c o n f i d e n t i a ld a t am i n i n g ，c o

14、 n f i d e n t i a ld a t a b a s eq u e r y , c o n f i -d e n t i a la u c t i o n ，c o n f i d e n t i a ls c i e n t i f i c c o m p u t i n g ，c o n f i d e n t i a ls t a t i s t i c a la n a l y s i s ，c o n f i d

15、 e n t i a lg e o m e t r i cc a l c u l a t i o n s ，e t c ．T h e m a i nj o b o ft h i s p a p e r i sa sf o l l o w i n g ：1 ．T h e s e c u r i t yd e f i n i t i o n o fp r i v a t e l yc o m p a r ei n f o r m a t i

16、 o n p r o t o c o lw i t h a no b v i o u st h i r dp a r t yi s g i v e n ．W ea n l y s et h es a f e t y , a c c u r a c ya n df a i r n e s so fQ I NJ i n g ’Sp r o t o c o l w h i c h b a s e d o n 巾一b i n d i n g a

17、 s s u m p t i o n a n dh o m o m o r p h i c e n c r y p t i o n ；2 ．W ep r o p o s ea ne f f i c i e n t p r o t o c o lb a s e do ns y m m e t r i ce n c r y p t i o n ．C o m m u -n i c a t i o nc o m p l e x i t y ,

18、c o m p u t a t i o n a lc o m p l e x i t y , a n ds e c u r i t yo ft h e p r o t o c o lb a s e do n 巾一h i n d i n ga s s u m p t i o na n dQ I N J i n g ’Sp r o t o c o lb a s e d o ns y m m e t r i ce n c r y p t i

19、o nw e r ea n a l y z e da n d c o m p a r e d ，t h ef o m e ri sm o r e t h e o r e t i c a lw h i l e t h e l a t t e ri sm o r ep r a c t i c a l ；3 ．W ep r o p o s e a p r o t o c o lb a s e do n R S A h o m o m o r

20、p h i c e n c r y p t i o na n d O T p r o -t o c o lt os o l v es e c r e ts e q u e n c i n gp r o b l e m ．T h i sp r o t o c o ls a t i s f ys a f e t y , f a i r n e s sa n de f f i c i e n c yc o m p a r i n gu s i