基于多離散對數問題的公鑰密碼

付向群 鮑皖蘇 史建紅 李發達

?

基于多離散對數問題的公鑰密碼

付向群 鮑皖蘇*史建紅 李發達

(信息工程大學 鄭州 450004)

該文首先定義了多離散對數問題，給出了現有隱含子群問題量子計算算法不適用于求解該問題的必要條件，且該問題在經典計算模式下，其困難性比離散對數問題難，用于求解有限域上離散對數問題的數域篩法不適用于求解多離散對數問題。然后設計了基于多離散對數問題的公鑰密碼，其安全性依賴于多離散對數問題，且公私鑰的數據量小，分析了算法參數的選取原則，證明了算法脫密原理的正確性，算法在每次加密時需要隨機選取一個數，使得算法對同一個明文加密所得的密文不一定相同。

密碼學；離散對數問題；公鑰密碼；量子計算

1 引言

信息安全主要依賴于密碼算法，為了達到該目的，密碼算法應當滿足：密碼體制能夠抵抗現有的各種可能攻擊方法；算法的安全性依賴于密鑰且易于實現。因此，密鑰在密碼算法中起到重要的作用。文獻[1]提出公鑰密碼思想，有效解決了密鑰分配問題。

公鑰密碼能否抵抗量子計算攻擊，在于安全性依賴的數學難題能否抵抗量子計算攻擊。目前，學者普遍認為，基于NPC問題的公鑰密碼體制可以抵抗現有條件下量子計算攻擊，一般指的是抵抗現有隱含子群問題量子計算算法，主要有基于糾錯編碼的公鑰密碼體制、基于辮群的公鑰密碼體制、基于多變量方程組的公鑰密碼體制、基于格的公鑰密碼體制。基于糾錯編碼的公鑰密碼體制的密鑰量大，不具有實用性；基于辮群、多變量方程組的安全性受到質疑，不能達到理想的安全強度；如果基于格的公鑰密碼體制所使用的格是一些具有特殊性質的格，其安全強度不夠，易于受到攻擊，比如Ajtai設計的AD公鑰密碼體制[12]。由此可以看出，抵抗現有條件下量子計算攻擊的公鑰密碼都存在一些缺陷，要么存在密鑰量大，不實用的缺陷，要么安全性受到學者們的質疑，因此，給出一個密鑰量小、安全性高且能抵抗現有條件下量子計算攻擊的公鑰密碼，值得進一步研究與探索。

本文首先定義了多離散對數問題，給出了該問題存在多項式時間量子計算算法的條件，進一步給出了該問題可以抵抗現有隱含子群問題量子計算算法攻擊的條件，且該問題在經典計算機上的難度至少相當于離散對數問題，因此，只要該問題選擇合適的參數，就可以抵抗現有隱含子群問題量子計算算法攻擊以及現有的經典攻擊方法。然后設計了基于多離散對數問題的公鑰密碼，其安全性建立在多離散對數問題的基礎上，可以抵抗現有的攻擊方法，并分析了該算法選取的參數的存在性與選取原則，該公鑰密碼可以抵抗現有隱含子群問題量子計算算法的攻擊以及求解有限域上離散對數問題的數域篩法，而且其公私鑰的數據量小，該算法在每次加密時，均要選擇一個隨機數，以此來達到對同一個明文加密所得密文不一定相同的目的，并證明了算法脫密原理的正確性。

2 多離散對數問題的經典計算復雜性

多離散對數問題實質上是通過多個離散對數問題復合在一起，以此來增加問題的困難性，因此，在經典計算機上，多離散對數問題的求解難度至少等價于離散對數問題，亦即該問題是一個困難問題。下面分析多離散對數問題的經典計算復雜性。

2.1 窮盡攻擊

2.2 離散對數問題的數域篩法

步驟3 用構造的多個線性關系式組成線性方程組，進而通過解方程組求出因子基；

3 多離散對數問題的量子計算復雜性

在現有公開文獻中，大部分多項式時間量子計算算法都能歸約為隱含子群問題量子計算算法，是一個通用的量子計算算法，而其它多項式時間量子計算算法均需要依據所求問題具有特殊的性質，才能使得算法以很大的概率求出問題的解，例如Pell方程量子計算算法[15]，該算法是依據Pell方程的所有解可由其中一個解全部生成。因此，本文主要分析隱含子群問題量子計算算法是否適用于求解多離散對數問題。

引理1[16]一次同余式組

證明 要證明定理成立，只需證明一次同余式組

無解。

如果一次同余式組式(1)有解，那么對任意的一次同余式組

無解，矛盾，亦即式(1)無解。 證畢

證明 由引理1易得推論1。 證畢

表1 值

4 基于多離散對數問題的公鑰密碼

量子計算算法的出現，對現代密碼產生了重要的影響，設計抗量子計算攻擊的密碼算法成為研究的熱點，為此本文設計了基于多離散對數問題的公鑰密碼算法。

4.1 基于多離散對數問題的公鑰密碼算法

4.1.1用戶B選取參數并生成密鑰

4.1.2用戶A加密

4.1.3用戶B脫密

4.2 正確性分析

亦即

因此，基于多離散對數問題的公鑰密碼的脫密原理是正確的。

4.3 安全性分析

4.4 數據量分析

由用戶的加密過程可以看出，密文長度是明文長度的4倍。

綜上分析可知，基于多離散對數問題的公鑰密碼算法可以抵抗現有隱含子群問題量子計算算法攻擊，公私鑰的數據量小，而且與基于離散對數問題的公鑰密碼算法相比，其被攻破的難度更難。在算法的加脫密過程中，算法只需要用到乘法運算，因此，算法易于實現。

5 結束語

本文給出了多離散對數問題的定義，給出了其抵抗現有隱含子群問題量子計算算法攻擊的必要條件，并基于該問題設計了公鑰密碼，該算法可以抵抗現有的經典攻擊方法，且可以抵抗現有隱含子群問題量子計算算法攻擊。然而本文沒有給出多離散對數問題抵抗現有隱含子群問題量子計算算法攻擊的充分條件，如何給出該充分條件有待進一步研究與探索。

[1] Diffie W and Hellman M E. New directions on cryptography [J]., 1976, IT-22(6): 644-654.

[2] 李凱, 黃曉英, 滕吉紅, 等. 一種基于Einstein-Podolsky- Rosen(EPR)序列的量子安全通信協議[J]. 電子與信息學報, 2012, 34(8): 1917-1922.

Li Kai, Huang Xiao-ying, Teng Ji-hong,.. A quantum secure direct communication scheme based on Einstein- Podolsky-Rosen (EPR) sequence[J].&, 2012, 34(8): 1917-1922.

[3] 易運暉, 朱暢華, 裴昌幸, 等. 偏振旋轉的量子私有信息檢索方案[J]. 電子與信息學報, 2012, 34(10): 2353-2357.

Yi Yun-hui, Zhu Chang-hua, Pei Chang-xing,.. Quantum private information retrieval based on polarization rotation[J].&, 2012, 34(10): 2353-2357.

[4] Fu Xiang-qun, Bao Wan-su, Zhou Chun,..-bit semiclassical quantum Fourier transform[J]., 2012, 57(1): 119-124.

[5] Shor P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer [J]., 1997, 26(5): 1484-1509.

[6] Grover L K. A fast quantum mechanics algorithm for database search[C]. Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of computing, Philadelphia, 1996: 212-219.

[7] 王保倉, 韋永壯, 胡予濮. 基于隨機背包的公鑰密碼[J]. 電子與信息學報, 2010, 32(7): 1580-1584.

Wang Bao-cang, Wei Yong-zhuang, and Hu Yu-pu. Public key cryptosystem using random knapsacks[J].&, 2010, 32(7): 1580-1584.

[8] 韓立東, 劉明潔, 畢經國. 兩種背包型的公鑰密碼算法的安全性分析[J]. 電子與信息學報, 2010, 32(6): 1485-1488.

Han Li-dong, Liu Ming-jie, and Bi Jing-guo. Security analysis of two knapsack-type public key cryptosystems[J].&, 2010, 32(6): 1485-1488.

[9] 魯曉彬, 鮑皖蘇, 李發達, 等. 基于MI和TPM混合的多變量數字簽名方案[J]. 電子學報, 2012, 40(10): 2021-2025.

Lu Xiao-bin, Bao Wan-su, Li Fa-da,.. A MPKC signature scheme based on mixing of MI and TPM[J]., 2012, 40(10): 2021-2025.

[10] 葉茂, 胡學先, 劉文芬. 基于格的三方口令認證密鑰交換協議[J]. 電子與信息學報, 2013, 35(6): 1376-1381.

Ye Mao, Hu Xue-xian, and Liu Wen-fen. Password authenticated key exchange protocol in the three party setting based on lattices[J].&, 2013, 35(6): 1376-1381.

[11] 光焱, 顧純祥, 祝躍飛, 等. 一種基于LWE問題的無證書全同態加密體制[J]. 電子與信息學報, 2013, 35(4): 988-993.

Guang Yan, Gu Chun-xiang, Zhu Yue-fei,.. Certificateless fully homomorphic encryption based on LWE problem[J].&, 2013, 35(4): 988-993.

[12] Ajtai M. Generating hard instances of lattice problems[C]. Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, 1996: 1-32.

[13] Menezes A J, Oorschot P C V, and Vanstone S A. Handbook of Applied Cryptography[M]. Canda: CRC Press LLC, 1997: 103-104.

[14] Gordon D M. Discrete Logarithms in GF(P) using the number field sieve[J]., 1993, 6(1): 124-138.

[15] Hallgren S. Polynomial-time Quantum algorithm for Pell’s equation and the principal Ideal problem[C]. Proceedings of the 34th Annual ACM Symposium on Theory of Computation, New York, 2002: 653-658.

[16] 潘承洞, 潘承彪. 初等數論[M]. 第2版, 北京: 北京大學出版社, 2003: 155-190.

Pan Cheng-dong and Pan Cheng-biao. Elementary Number Theory[M]. Second Edition, Beijing: Peking University Press, 2003: 155-190.

付向群： 男，1985年生，博士生，研究方向為量子密碼與量子計算.

鮑皖蘇： 男，1966年生，博士生導師，教授，研究方向為量子密碼、序列密碼、公鑰密碼.

史建紅： 男，1975年生，碩士生導師，副教授，研究方向為量子密碼、量子協議、公鑰密碼.

李發達： 男，1989年生，碩士生，研究方向為量子計算.

Public-key Cryptograph Based on the Multi-discrete Logarithm Problem

Fu Xiang-qun Bao Wan-su Shi Jian-hong Li Fa-da

(Information Engineering University, Zhengzhou 450004, China)

In this paper, the multi-discrete logarithm problem is formally defined, and the necessary conditions of resistance to the quantum algorithm for the hidden subgroup problem are given. It is more difficult than the discrete logarithm problem. And the number field sieve for the discrete logarithm problem is not suitable for addressing it. Furthermore, the public-key cryptograph is designed against the problem, of which the key amount is small. This paper analyses the principles of parameter selection and proves the correctness of the decryption works. It is critical that different random integersare

to the encrypt different messages.

Cryptography; Discrete logarithm problem; Public-key cryptograph; Quantum computation

TN918.1

A

1009-5896(2014)06-1423-05

10.3724/SP.J.1146.2013.01324

鮑皖蘇 2010thzz@sina.com

2013-08-28收到，2013-12-13改回

國家973計劃項目(2013CB338002)資助課題