基于多離散對(duì)數(shù)問(wèn)題的公鑰密碼

付向群 鮑皖蘇 史建紅 李發(fā)達(dá)

?

基于多離散對(duì)數(shù)問(wèn)題的公鑰密碼

付向群 鮑皖蘇*史建紅 李發(fā)達(dá)

(信息工程大學(xué) 鄭州 450004)

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

密碼學(xué)；離散對(duì)數(shù)問(wèn)題；公鑰密碼；量子計(jì)算

1 引言

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

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

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

2 多離散對(duì)數(shù)問(wèn)題的經(jīng)典計(jì)算復(fù)雜性

多離散對(duì)數(shù)問(wèn)題實(shí)質(zhì)上是通過(guò)多個(gè)離散對(duì)數(shù)問(wèn)題復(fù)合在一起，以此來(lái)增加問(wèn)題的困難性，因此，在經(jīng)典計(jì)算機(jī)上，多離散對(duì)數(shù)問(wèn)題的求解難度至少等價(jià)于離散對(duì)數(shù)問(wèn)題，亦即該問(wèn)題是一個(gè)困難問(wèn)題。下面分析多離散對(duì)數(shù)問(wèn)題的經(jīng)典計(jì)算復(fù)雜性。

2.1 窮盡攻擊

2.2 離散對(duì)數(shù)問(wèn)題的數(shù)域篩法

步驟3 用構(gòu)造的多個(gè)線性關(guān)系式組成線性方程組，進(jìn)而通過(guò)解方程組求出因子基；

3 多離散對(duì)數(shù)問(wèn)題的量子計(jì)算復(fù)雜性

在現(xiàn)有公開(kāi)文獻(xiàn)中，大部分多項(xiàng)式時(shí)間量子計(jì)算算法都能歸約為隱含子群?jiǎn)栴}量子計(jì)算算法，是一個(gè)通用的量子計(jì)算算法，而其它多項(xiàng)式時(shí)間量子計(jì)算算法均需要依據(jù)所求問(wèn)題具有特殊的性質(zhì)，才能使得算法以很大的概率求出問(wèn)題的解，例如Pell方程量子計(jì)算算法[15]，該算法是依據(jù)Pell方程的所有解可由其中一個(gè)解全部生成。因此，本文主要分析隱含子群?jiǎn)栴}量子計(jì)算算法是否適用于求解多離散對(duì)數(shù)問(wèn)題。

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

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

無(wú)解。

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

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

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

表1 值

4 基于多離散對(duì)數(shù)問(wèn)題的公鑰密碼

量子計(jì)算算法的出現(xiàn)，對(duì)現(xiàn)代密碼產(chǎn)生了重要的影響，設(shè)計(jì)抗量子計(jì)算攻擊的密碼算法成為研究的熱點(diǎn)，為此本文設(shè)計(jì)了基于多離散對(duì)數(shù)問(wèn)題的公鑰密碼算法。

4.1 基于多離散對(duì)數(shù)問(wèn)題的公鑰密碼算法

4.1.1用戶B選取參數(shù)并生成密鑰

4.1.2用戶A加密

4.1.3用戶B脫密

4.2 正確性分析

亦即

因此，基于多離散對(duì)數(shù)問(wèn)題的公鑰密碼的脫密原理是正確的。

4.3 安全性分析

4.4 數(shù)據(jù)量分析

由用戶的加密過(guò)程可以看出，密文長(zhǎng)度是明文長(zhǎng)度的4倍。

綜上分析可知，基于多離散對(duì)數(shù)問(wèn)題的公鑰密碼算法可以抵抗現(xiàn)有隱含子群?jiǎn)栴}量子計(jì)算算法攻擊，公私鑰的數(shù)據(jù)量小，而且與基于離散對(duì)數(shù)問(wèn)題的公鑰密碼算法相比，其被攻破的難度更難。在算法的加脫密過(guò)程中，算法只需要用到乘法運(yùn)算，因此，算法易于實(shí)現(xiàn)。

5 結(jié)束語(yǔ)

本文給出了多離散對(duì)數(shù)問(wèn)題的定義，給出了其抵抗現(xiàn)有隱含子群?jiǎn)栴}量子計(jì)算算法攻擊的必要條件，并基于該問(wèn)題設(shè)計(jì)了公鑰密碼，該算法可以抵抗現(xiàn)有的經(jīng)典攻擊方法，且可以抵抗現(xiàn)有隱含子群?jiǎn)栴}量子計(jì)算算法攻擊。然而本文沒(méi)有給出多離散對(duì)數(shù)問(wèn)題抵抗現(xiàn)有隱含子群?jiǎn)栴}量子計(jì)算算法攻擊的充分條件，如何給出該充分條件有待進(jìn)一步研究與探索。

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

[2] 李凱, 黃曉英, 滕吉紅, 等. 一種基于Einstein-Podolsky- Rosen(EPR)序列的量子安全通信協(xié)議[J]. 電子與信息學(xué)報(bào), 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] 易運(yùn)暉, 朱暢華, 裴昌幸, 等. 偏振旋轉(zhuǎn)的量子私有信息檢索方案[J]. 電子與信息學(xué)報(bào), 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] 王保倉(cāng), 韋永壯, 胡予濮. 基于隨機(jī)背包的公鑰密碼[J]. 電子與信息學(xué)報(bào), 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īng)國(guó). 兩種背包型的公鑰密碼算法的安全性分析[J]. 電子與信息學(xué)報(bào), 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] 魯曉彬, 鮑皖蘇, 李發(fā)達(dá), 等. 基于MI和TPM混合的多變量數(shù)字簽名方案[J]. 電子學(xué)報(bào), 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] 葉茂, 胡學(xué)先, 劉文芬. 基于格的三方口令認(rèn)證密鑰交換協(xié)議[J]. 電子與信息學(xué)報(bào), 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問(wèn)題的無(wú)證書(shū)全同態(tài)加密體制[J]. 電子與信息學(xué)報(bào), 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] 潘承洞, 潘承彪. 初等數(shù)論[M]. 第2版, 北京: 北京大學(xué)出版社, 2003: 155-190.

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

付向群： 男，1985年生，博士生，研究方向?yàn)榱孔用艽a與量子計(jì)算.

鮑皖蘇： 男，1966年生，博士生導(dǎo)師，教授，研究方向?yàn)榱孔用艽a、序列密碼、公鑰密碼.

史建紅： 男，1975年生，碩士生導(dǎo)師，副教授，研究方向?yàn)榱孔用艽a、量子協(xié)議、公鑰密碼.

李發(fā)達(dá)： 男，1989年生，碩士生，研究方向?yàn)榱孔佑?jì)算.

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改回

國(guó)家973計(jì)劃項(xiàng)目(2013CB338002)資助課題