基于逆序二叉樹的高效可分電子現金系統

張江霄 郭 華② 李舟軍

?

基于逆序二叉樹的高效可分電子現金系統

張江霄*①郭 華①②李舟軍①

①(北京航空航天大學軟件開發環境國家重點實驗室 北京 100191)②(中國科學院信息工程研究所信息安全國家重點實驗室 北京 100093)

針對于Izabachene等人(2012)在標準模型下構建的可分電子現金系統花費協議和存款協議效率低的問題，該文利用Groth-Sahai(GS)證明系統和累加器原理，首次提出了逆序二叉樹構建法，并在標準模型下構建了一個高效的可分電子現金系統。與現有系統相比，新系統在構建二叉樹時可以并行計算二叉樹葉子節點的序列號和在花費協議中可以直接證明用戶花費路徑的正確性，從而保證花費協議中用戶的計算量是常量；新系統在安全性上不僅具有弱不可誣陷性，同時也具有強不可誣陷性；最后在標準模型下給出了系統的安全性證明，證明了該系統具有不可偽造性、匿名性、不可重復花費性和不可誣陷性。

可分電子現金系統；標準模型；逆序二叉樹；有限累加器；Groth-Sahai (GS)證明

1 引言

電子現金系統一般由3個協議組成：取款協議、花費協議和存款協議，用戶通過取款協議取出所需的電子現金，然后利用花費協議向商家進行花費，最后商家通過存款協議把電子現金存入銀行。其中電子現金的可分性允許用戶花費小于或等于用戶所取的任意面額的電子現金，從而提高了用戶的花費效率。因此，可分電子現金系統變得越來越重要。

本文針對標準模型下可分電子現金系統花費協議和存款協議效率低的問題，首先提出了一個逆序二叉樹構建法，從而減少了花費協議和存款協議中商家和銀行的計算量，解決了存款協議效率低的公開問題；然后基于累加器原理，采用常量累加器證明的方法，提高了花費協議中證明用戶花費正確性的效率；同時，新系統兼具弱不可誣陷性和強不可誣陷性[10]。

本文內容組織如下：第2節給出基本定義；第3節介紹逆序二叉樹構建法；第4節構造可分電子現金系統；第5節對新協議和已有的協議進行比較；第6節給出新系統安全性的形式化證明；第7節總結全文。

2 基本定義

定義4 GS證明[14]在標準模型下給出了有關雙線性群中等式的非交互式零知識證明，它適合多種雙線性群中群元素關系的等式，包括雙線性乘積等式、多標量乘法等式和二次等式等，本文只使用基于SXDH假設下的雙線性乘積等式。

定義5 有限累加器[15]最多可以累加有限個元素，同時存在一個證據，可以證明該元素被累加到累加值中，任何人無法證明一個沒有累加的元素被累加到累加值中。

3 逆序二叉樹構建法

圖1 4層二叉樹示例

4 可分電子現金的構造

4.1 基本參數

4.2 安全屬性

本文所構造的可分電子現金具有不可偽造性、匿名性、不可重復花費性和不可誣陷性。為了描述安全屬性，首先引入幾個算法：

(4)不可誣陷性 不可誣陷性包括弱不可誣陷性和強不可誣陷性[10]。具體定義如下：

4.3 取款協議

4.4 花費協議

4.5 驗證協議

在商家接受到郵件后，驗證電子現金的正確性和新鮮性，如果都通過驗證，商家就給用戶發送商品。具體協議如下：

4.6存款協議

銀行收到商家電子現金后，按照圖2 進行驗證。

如果用戶對同一電子現金或者相關的電子現金發生了重復花費。銀行通過式(1)分以下3種情況計算重復花費用戶的公鑰：

圖2 存款協議驗證

5 效率分析

表1協議計算效率和安全模型的比較

二叉樹生成計算量()取款協議()(個)花費協議()()存款協議安全模型安全性質 文獻[4]70隨機預言機模型 文獻[6]080標準模型 新協議28標準模型

6 安全證明

定理1如果SP簽名是不可偽造的，并且有限累加器的累加具有有限性，則新協議是不可偽造的；如果Groth-Sahai證明具有零知識性，且DDH問題是困難的，則新協議具有匿名性；如果SP簽名是不可偽造的，則新協議具有不可重復花費性；如果Groth-Sahai證明具有零知識性，并且一對多離散對數問題[13]是困難的，則新協議具有不可誣陷性(包括弱不可誣陷性和強不可誣陷性)。

7 結論

本文針對Izabachene等人在標準模型下構建的可分電子現金系統花費協議和存款協議效率低的問題，提出了一個逆序二叉樹構建法，同時利用Groth-Sahai證明系統和累加器原理，在標準模型下，構建了一個高效的離線可分電子現金系統。新系統在二叉樹構建和花費協議上均優于現有的系統。最后在標準模型下給出了可分電子現金系統的安全性證明，而且新的協議在安全性上，不僅具有弱不可誣陷性，也具有強不可誣陷性。

[1] Canard S and Gouget A. Divisible e-cash systems can be truly anonymous[C]. The 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques’07, Barcelona, 2007: 482-497.

[2] Au M H, Susilo W, and Mu Y. Practical anonymous divisible e-cash from bounded accumulators[C]. Proceedings of Financial Cryptography and Data Security’08, Cozumel, 2008: 287-301.

[3] 劉文遠, 張江霄, 胡慶華, 等. 可直接計算的高效的可分電子現金系統[J]. 電子學報, 2009, 37(2): 367-371.

Liu W, Zhang J X, Hu Q H,.. Divisible e-cash system with direct computation and efficiency[J]., 2009, 37(2): 367-371.

[4] Canard S and Gouget A. Multiple denominations in e-cash with compact transaction data[C]. Proceedings of Financial Cryptography and Data Security’10, Tenerife, 2010: 82-97.

[5] Goldwasser S and Tauman Y. On the (In) security of the Fiat-Shamir paradigm[C]. The 44th Symposium on Foundations of Computer Science, Cambridge, 2003: 102-115.

[6] Izabachene M and Libert B. Divisible e-cash in the standard model[C]. Proceedings of Pairing-Based Cryptography- Paring’12, Cologne, 2012: 314-332.

[7] Zhang J X, Li Zh J, and Guo H. Anonymous transferable conditional e-cash[C]. Proceedings of Security and Privacy in Communication Networks’12, Padua, 2013: 45-60.

[8] Liu J W, Liu J H, and Qiu X F. A proxy blind signature scheme and an off-line electronic cash scheme[J]., 2013, 18(2): 117-125.

[9] Blazy O, Canard S, Fuchsbauer G,.. Achieving optimal anonymity in transferable e-cash with a judge[C]. The 4th International Conference on Cryptology in Africa’11, Dakar, 2011: 206-223.

[10] Rosenberg B. Handbook of Financial Cryptography and Security[M]. London: Chapman & Hall, 2010: 19-20.

[11] Groth J and Sahai A. Efficient non-interactive proof systems for bilinear groups[C]. The 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques’08, Istanbul, 2008: 415-432.

[12] Abe M, Groth J, Haralambiev K,.. Optimal structure-preserving signatures in asymmetric bilinear groups[C]. The 31th Annual Conference on Advances in Cryptology’11, Santa Barbara, 2011: 649-666.

[13] Bresson E, Monnerat J, and Vergnaud D. Separation results on the “one-more” computational problems[C]. Proceedings of the Cryptographer’s Track at the RSA’08, San Francisco, 2008: 71-87.

[14] Fuchsbauer G. Commuting signatures and verifiable encryption[C]. The 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques’11, Tallinn, 2011: 224-245.

[15] Camenisch J, Kohlweiss M, and Soriente C. An accumulator based on bilinear maps and efficient revocation for anonymous credentials[C]. The 12th International Conference on Practice and Theory in Public Key Cryptography’09, Irvine, 2009: 481-500.

[16] Abe M, Fuchsbauer G, Groth J,. Structure-preserving signatures and commitments to group elements[C]. The 30th Annual Cryptology Conference’10, Santa Barbara, 2010: 209-236.

張江霄： 男，1983年生，博士生，研究方向為密碼學和電子現金.

郭 華： 女，1981年生，講師，研究方向為信息安全.

李舟軍： 男，1963年生，博士生導師，研究方向為密碼學和數據挖掘.

Efficient Divisible E-cash System Based on Reverse Binary Tree

Zhang Jiang-xiao①Guo Hua①②Li Zhou-jun①

①(,,100191,)②(,,,100093,)

There exist some defects such as low efficiency in the spending protocol and deposit protocol of the proposed by Izabachene. (2012) divisible E-cash system based on the standard model. Using the Groth-Sahai (GS) proof system and accumulator, this paper proposes a reverse binary tree algorithm and designs an efficient divisible E-cash system under the standard model. The new system can calculate simultaneously the series number of the leaf nodes of the binary tree in the process of the binary tree construction. A user can prove the correctness of spending path directly, thus the computation load of user is constant in the spending protocol. The new system achieves both the weak exculpability and the strong exculpability. Finally, the security proof of the system is given in the standard model which includes unforgeability, anonymity, identification of double spender and exculpability.

Divisible E-cash system; Standard model; Reverse binary tree; Bounded accumulator; Groth-Sahai

TP393

A

1009-5896(2014)01-0022-05

10.3724/SP.J.1146.2013.00466

2013-04-09收到，2013-10-08改回

國家自然科學基金 (60973105, 90718017, 61170189, 61300172)，軟件開發環境國家重點實驗室自主研究課題(SKLSDE-2011ZX-03, SKLSDE-2012ZX-11)和博士點基金(20111102130003, 20121102120017)資助課題

張江霄 orange_0092008@live.cn