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

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

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

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

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

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