基于格的可證安全的簽名方案研究.pdf

1、現(xiàn)代密碼學(xué)以很多數(shù)學(xué)工具為基礎(chǔ)，格是現(xiàn)代密碼學(xué)中極具吸引力的一種數(shù)學(xué)工具?；诟竦拿艽a研究近年來(lái)發(fā)展很快，現(xiàn)在幾乎已經(jīng)涉及了各種密碼領(lǐng)域，如基本公鑰加密、基本簽名、群環(huán)簽名、基于身份的加密、基于屬性的加密，甚至于半同態(tài)或全同態(tài)加密。
　　格密碼的興起源于量子計(jì)算機(jī)概念的逐步成熟。在量子計(jì)算機(jī)上，基于傳統(tǒng)困難問(wèn)題，如大整數(shù)分解問(wèn)題、離散對(duì)數(shù)問(wèn)題、橢圓曲線問(wèn)題等，構(gòu)造的密碼方案，其安全性將受到嚴(yán)峻的挑戰(zhàn)。因?yàn)樵诹孔佑?jì)算模型下，可以同時(shí)

2、進(jìn)行指數(shù)級(jí)別的運(yùn)算，也就是說(shuō)，傳統(tǒng)計(jì)算模型需要指數(shù)時(shí)間完成的運(yùn)算，量子計(jì)算模型只需要多項(xiàng)式時(shí)間。這是因?yàn)橐粋€(gè)量子比特可以同時(shí)具有多種狀態(tài)，而不像電子比特只能具有兩種狀態(tài)。
　　基于格理論構(gòu)造的密碼方案極具吸引力，其原因是多方面的。首先，從理論上來(lái)說(shuō)，格密碼基于最壞情況困難問(wèn)題假設(shè)，這比基于數(shù)論平均情況困難問(wèn)題的假設(shè)要弱，也就是說(shuō)安全性保障更強(qiáng);并且，部分規(guī)約屬于量子規(guī)約，使得格密碼在某些困難問(wèn)題假設(shè)下可以抵抗量子攻擊。其次，在實(shí)現(xiàn)

3、方面，格密碼的基本運(yùn)算只有矩陣和向量的模乘運(yùn)算，而模數(shù)通常是小素整數(shù)，運(yùn)算非常簡(jiǎn)單，不需要“大數(shù)”函數(shù)庫(kù)的支持;另外，由于格結(jié)構(gòu)的規(guī)整性和運(yùn)算特點(diǎn)，很容易構(gòu)造并行算法，事實(shí)上，格規(guī)約和格取樣算法都有了GPU并行實(shí)現(xiàn)。
　　本文的選題來(lái)源于格密碼領(lǐng)域中的簽名部分。在本文中，我們構(gòu)造了兩種簽名方案，并分別在不同模型下、不同敵手能力下證明了其安全性，一種是在隨機(jī)預(yù)示模型下，另一種在標(biāo)準(zhǔn)模型下。
　　首先，我們使用格基代理技術(shù)，借鑒

4、“分享校驗(yàn)子”思想，暨分享消息，實(shí)現(xiàn)了門(mén)限簽名，并在隨機(jī)預(yù)示模型下，證明其在適應(yīng)性選擇消息攻擊下具有存在性不可偽造性。具體地，我們用格基代理算法，將“權(quán)力”代理給多個(gè)參與方，以實(shí)現(xiàn)“權(quán)力”的分散;用Shamir秘密分享算法分享待簽名的消息，以實(shí)現(xiàn)門(mén)限機(jī)制。我們采用的格基代理算法，不會(huì)增加格的維度，從而可以很容易地合并各個(gè)簽名分享。
　　然后，我們考慮另一種格簽名模式，不同于前者將消息散列為校驗(yàn)子，后者把消息散列為隨機(jī)格矩陣，校驗(yàn)子

5、置為隨機(jī)向量或零向量，再通過(guò)取樣算法得到簽名。我們使用可容許哈希函數(shù)技術(shù)消除證明過(guò)程中的隨機(jī)預(yù)示，在標(biāo)準(zhǔn)模型下，證明其滿(mǎn)足適應(yīng)性選擇消息攻擊下的存在性不可偽造性。
　　本文的創(chuàng)新點(diǎn)主要有:
　　用格做構(gòu)造工具，方案具有天然的抗量子攻擊特性;
　　用分享消息的方式，配合格代理算法實(shí)現(xiàn)門(mén)限簽名;
　　把可容許哈希函數(shù)應(yīng)用到簽名方案上，消除隨機(jī)預(yù)示。
　　本文未實(shí)現(xiàn)的方面有:在門(mén)限簽名中，沒(méi)有消除可信第三方，目前