о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999Vol.36No.7P.853-858



t,nзթʶ
̷ġн
ժҪ(t,n)зеթʶһҪ.һЧĻƽʣթʶ𷽰ʱѶ൱ڷֽĳ˻Ѷ.ʹõϣҶԹԸ豣ֹ֤ıݺĳĳԱ.չܵ.ͨChang-HwangС.
ؼʣթʶ, з, ƽʣ, ֵܷ
ţTP309TP918
CHEATER IDENTIFICATION IN (t,n) THRESHOLD SCHEME
TAN Kai-Jun
(Department of Electronic Engineering Shanghai Jiaotong University, Shanghai 200030)
ZHU Hong-Wen
(Department of Electronic Engineering Shanghai Jiaotong University, Shanghai 200030)
GU Shang-Jie
(Department of Electronic Engineering Shanghai Jiaotong University, Shanghai 200030)
AbstractCheating detection is a very important issue for (t,n) threshold schemes. An efficient cheater detection scheme based on quadratic residues is proposed in this paper. The attack is as difficult as factoring the product of two large prime numbers. The scheme doesn't need any one-way hash function. The integrity guarantee is given to the public parameters, which can prevent a conspirator from falsely accusing any specific members. It can be easily expanded to the multi-secret sharing scheme. The quantity of communication is smaller than that in Chang-Hwang scheme.
Key wordscheater identification, threshold scheme, quadratic residues, secret shares
1
зҪĳܲᶪʧ𻵻޸.(t,n)зǽһֳܷnݷֵӦĳԱеκtԱԻָܣtǲе.ʵкܶҪõ(t,n)зĳȫţһչ򿪱չĿΪһȫŵĸ߼Աзnڴ򿪱չʱnеt໥Эָһʽ(t,n)з.
Shamir1ݺBlakley21979(t,n)з⣬˺оо.зУһؼǰеĳԱڻָʱʽӵеֵܷ.ֻּһ״̬ʵĳĿĶʽһٷֵƭĳԱ.TompaWoll3ָƭԼĲȫ.ʶթĳԱ(t,n)зʵһҪ.ڹȥļвйⷽо38.թʶȷеָթߣթֻܲǷթթʶթϵͳİȫʵ.ף3ݡ5еķթ⣬ף6ݡ8еթʶ.
Wu-Wu6ԼHang-Chang-Yang7ݶϣİȫԣȻף9Harnķϣǻһѭ򵥺ĸԣȻڿʼʱƺѷʱƣᷢǺĳЩĹ.оMD5ѽӽͨɹıԵ10.ף8Chang-HwangǻƽʣѧģȻթʶ֤Уļܼ򵥣ʼʱļȴСҪɺܶⲻչܵ.ʵУһܱʾͲܱʹãӦɵĹֵܷȫԲòٷµܣԱ֤ȫǶܷƵصݣ1618.ļ(ͨĴС)֤ϵͳԺʵ.Chang-HwangУƵĿֹĳĳԱ.
Wu-Wu6ݺChang-Hwang8ݵһ͵(t,n)зթʶ𷽰.
2صķ
2.1Wu-Wu
Wu-Wuթʶ𷽰Ӧκ(t,n)з.ֵSDCѽֵܷsi(i=1,2,,n)Աui(i=1,2,,n).SDCѡһpһϣh(.)乫ҼһֵT

tԱʱִͨ²ʶթԱ
1: еtԱʽǵֵܷ㣺
2: ÿԱujĵʽǷ

ʽôԱujǳʵģһթ.
÷İȫҪϣh(.)Ϊκ˿ɸݹֵT(ujnԱеһsjİȫȫh(.).ף8ָ߿ɸıTΪT䣺
T=T-bp2(j-1)-p<b<p,b0.
T䣬ԱujʹʽȷsjҲͨʽļ⣬TûԱ֤.
2.2Chang-Hwang
Chang-Hwang8ƽʣඨΪѧ,Ӧκ(t,n)з.ֵSDCѽֵܷsi(i=1,2,,n)Աui(i=1,2,,n).SDCѡpqN=pq(p+1)mod4=0,(q+1)mod4=0,NıسΪ512.Ȼ4Բ(,1),(,£1),(,ã1),(,ң1),ЦQRpQRq,¡QRpQNRq,áQNRpQRq,ҡQNRpQNRq,ΡΣ11modN,Ρʣ£ãң.QRpQRqֱʾģpqƽʣļϣQNRpQNRqֱʾģpqķƽʣļ.ƽʣͷƽʣĽܿɲμף8.SDѡnصdi(i=1,2,,n),di>si,ȻSDCsi,N,£ã㹫T͸Աαֵ.
1siBiʹBiQRpQRq
IfsiQRpQRqthen Bi=si mod N,index1=00䣻
IfsiQRpQNRqthen Bi=si mod N,index1=01䣻
IfsiQNRpQRqthen Bi=si mod N,index1=10䣻
IfsiQNRpQNRqthen Bi=si mod N,index1=11䣻
2BiģNƽxiʹBi=x2i(modN);
3hi=xiindex1,СǱشӷ
413ƵḶ́diCiʹCiQRpQRqCiģNƽyiri=yiindex2
5s*i=siyi.йʣඨnʽĹֵTnʽΪTs*imoddi(i=1,2,,n).
SDC(T,N,1£1ã1ң1)(hi,di,ri)ǳԱuiαֵܷ.
nеtԱҪʱǸԳʽԼαֵܷ(hi,di,ri)ĳԱֵ֤ȷ.ȴriеõyiindex2ȡdiy2i2(modN)(Ц2Ǹindex2ֵȡ1£1ã1ң1еĳһֵ).didiôuiΪթߣ֤.hiеõxiindex1㣬ʽsix2i1(modN)(Ц1Ǹindex1ֵȡ1£1ã1ң1еĳһֵ)ôuiΪʵģΪթ.թͬʱҲֵָܷsi.
ChangHwangָWu-WuTûԱֹ֤ıݺĳĳԱǵķȴ.ʵϣChang-HwangTȻܱı䣬1£1ã1ң1Ȼ.Ʃĳ˽1Ϊcôһαֵܷindex2=00ĳԱ޷֤ͨԸ÷ƵĿֹıݺĳĳԱ.
3ķ
ΪǰַڹԵ⣬ԱķԴ.ڳ֮ǰȼ򵥽ܻɢľϢָǩ.NybergRueppelһĻɢľϢָǩ11ݣף12иͨõķ.ϢָǩĻص֤ʽΪָϢ.ȻϢбӽһЩϢڻָϢ֮󣬽ϢǷص.򵥽Nyberg-Rueppel.
ѡpqq|p-1.ѡGF(p)еĵһqԪg.ǩAѡxAyAֱΪ˽Կ͹Կ.ǩϢΪm (mѱϢ).Aѡһkrg-km(modp)sk-rxA(modq)(r,s)AmǩBǩ󽫼mgsyrAr(modp)mԣ(p,q,g)ǹ.
ķҲӦκ(t,n)з.ֵSDCѽֵܷsi(i=1,2,,n)Աui(i=,1,2,,n).ҲҪõƽʣඨйصѧɲμף8.ϵͳѴNyberg-RueppelǩĲSDC˽Կ͹ԿֱxSDCySDC.潫׶ܱķ.
3.1ʼ׶
SDCִ²ϵͳĲ
1:ѡp1q1㣬N=p1q1(p1+1)mod4=0(q1+1)mod4=0,NıسΪ512.siʣ1,N-1,i=1,2,,n
2:ÿԱsi(i=1,2,,n)㣺his2i(modN)
3:ѡһգЦ>hi(i=1,2,,n)乫
4:
5:TΪҪǩϢϢSDCTǩ(r,s).
3.2׶
nԱеtָͬ.ʧһģΪui(i=1,2,,t)ǽ²裺
1:֤ǩ(r,s)ȷԣָTgsyrAr(modp)Ƿԣ
2: ui(i=1,2,,t)ʽǵֵܷsi
3:ÿui(i=1,2,,t)ȼ㣬֤hi?s2i(modN)ʽʾuiʽȷֵܷթ.
4
4.1ȷԷ
Nyberg-RueppelǩTǩԼ֤ʱٻTֵȷԵḶ́Բμף11.Ҫ׶ʱ3ȷ.

У
P=h11-i++hi-1գ1,
Q=hi+1++ann-i.
Ϊ>hi(i=1,2,,n)У

ԣ0P1

ͨϹ̣֤˷ȷ.
4.2ȫԷ
Wu-WuİȫǻڵϣȻף9зǻһѭļ򵥺ĸԣȻڿʼʱƺѷʱƣᷢǺĳЩĹWu-Wuǲȫ.ȴǻƽʣඨʹͨʽ׻hiǱhiģNƽsi.ȻѰģNƽ൱ڷֽĳ˻Ѷȣ13.
ף8ָWu-WuУ߿ɸıTҲTûԱ֤ʹԱʽȷsiҲ޷ͨ.Chang-HwangͬйԵ.ԱTǩ֤ԣҲǱ޷ıֵT.
κγԱʽϲȷsi̵֤Ĳ3.ԱuiʽȷķֵsiΪ˲̵֤Ĳ3޸TΪT䣬ʹãTSDCǩκ޷޸.
4.3㸴Ӷȷ 
Ҫõ͵ļ㣬һһ㣬һڵ.Obʾʱ临Ӷȣף14УAhoָһ˳ʱ临ӶOb(blogbloglogb)bǲıس.ģݳļΪģpģˣģpĳҪģpģˣ15ݣڷУg1modpȼò.Աڳʼ׶ΣҪļΪOb(nblogbloglogb)(T)+O(n)ģN(hi)+ģpĳ˷(Tǩ).֤ʱҪļΪOb(2tblogbloglogb)(hi)+O(t)ģN(s2i)+)ģpĳ˷(֤Tǩ).ʵϱҪļڶTǩ֤Ḷ́ǩֻΪ˱֤TԣWu-WuԼChang-Hwangȱ.Wu-WuԼChang-Hwangļμף8.Chang-HwangҪŵ֤ʱļСSDCгʼʱļС.żӲķչԱļҲǺܴģԽѳԱĸЧΪSDCļǲƵ.Chang-HwangҲԹԱôļ󳬹ķ.
4.4ͨ
Chang-HwangĳʼУSDCܹ3nlog2NbitϢ֤УtԱ͵ܵϢΪ3tlog2Nbit.ķʼУSDCܹ2log2pbit֤УtԱ͵ܵϢΪtlog2Nbit(NsiʱѡС).ԱͨChang-HwangС.
4.5չ
Chang-HwangȻթʶ֤Уļܼ򵥣ʼʱļȴܴ󣬶ɵĲҲ϶࣬ⲻչܵ.ʵУһܱʾͲܱʹãӦɵĹֵܷȫԲòٷµܣԱ֤ȫ.ļ(ͨĴС)֤ϵͳԺʵ.ĳʼ̽Ϊ򵥣ֻҪɲǩ֤ʱ漰ĲҲ.ԱӦõܵ1618.
5
зҪĳܲᶪʧ𻵻޸ģӦںܶೡϣǸ÷ҪȷʹãҪթʶ.һЧĻƽʣඨթʶ𷽰йѶ൱ڷֽĳ˻.ʹõϣҶԹԸ豣֤ĻֹıݺĳĳԱ.չܵͨҲС.
Ŀ̷ Ů19726ʿооΪϢȫѧ.
ģ У193911ϺӹϵϯѧңʿʦСΪͨCSCW簲ȫ. 
нܣ У19406ϺӹϵڣʿʦоΪͨATM.
߼飺̷Ů19726ʿооΪסȫѧ
ģУ193911ϺӹϵϯѧңʿʦоΪͨCSSW簲ȫ
нܣУ19406ϺӹϵڣʿʦоΪͨATM
ߵλ̷(ϺͨѧӹϵϺ200030)
(ϺͨѧӹϵϺ200030)
н(ϺͨѧӹϵϺ200030)
οף
1Shamir A. How to share a secret. Comm ACM, 1979, 22(11): 612613
2Blakley G R. Safeguarding cryptographic keys. In: Proc AFIPS 1979 Natl Comput Conf, New York, 1979. 313317
3Tompa M, Woll H. How to share a secret with cheaters. J Crypt, 1988, 1: 133138
4Brickell E F, Stinton D R. The detection of cheaters in threshold schemes. In: Advances in Cryptology-Crypto '88, Berlin: Springer-Verlag, 1988. 20172018
5Su H M, Shieh S P. Construction of dynamic threshold schemes. Electron Lett, 1994, 30(24): 20232024
6Wu T C, Wu T S. Cheating detection and cheater identification in secret sharing schemes. IEE Peoc E Comput Digit Tech, 1995, 142(5): 367369
7Hwang S J, Chang C C, Yang W P. New cheater identification in threshold schemes. National Chung Hsing University, TaiChung, Technical Report of the Institute of Computer and Information Science, 1995
8Chang C C, Hwang R J. Efficient cheater identification method for threshold schemes. IEE peoc E Comput Digit Tech, 1997, 144(1): 2327
9Harn L. Digital signature for Diffie-Hellman public keys without using a one-way function. Electron Lett, 1997, 33(2): 125126
10Dobbertin H. The status of MD5 after a recent attack. CryptoBytes, 1996, 2(2): 16
11Nyberg K, Rueppel R A. A new signature scheme based on the DSA giving message recovery. In: 1st ACM Conference on Computer and Communications Security, Fairfax, USA, 1993
12Nyberg K, Rueppel R A. Message recovery for signature schemes on the discrete logarithm. In: Pre-proceeding of Eurocrypt94, Perugia, Italy, 1994. 175190
13Rabin M O. Digitized signatures and public-key functions as intractable as factorization. MIT Laboratory Technical Report: LCS/TR-212, 1979
14Aho A V, Hopcroft J E, Ullman J D. The Design and Analysis of Computer Algorithms. Reading, MA: Addison-Wesley, 1974
15Pohlig S C, Hellman M E. An improved algotithms over GF(p) and its cryptographic significance. IEEE Transactions on Information Theory, 1978, IT-24(1): 106110
16He J, Dawson E. Multisecret-sharing scheme based on one-way function. Electron Lett, 1995, 31(2): 9394
17Harn L. Comment: Multistage secret sharing based on one-way function. Electron Lett, 1995, 31(4): 262
18He J, Dawson E. Multistage secret sharing based on one-way function. Electron Lett, 1995, 31(19): 15911592
ոڣ1998-10-15
޸ڣ1999-01-18
