基于DAA的輕量級多商家多重息票系統

柳欣，徐秋亮，張波

（1. 山東青年政治學院信息工程學院，山東 濟南 250103；2. 山東省高校信息安全與智能控制重點實驗室（山東青年政治學院），山東 濟南 250103；3. 山東大學計算機科學與技術學院，山東 濟南 250101；4. 濟南大學信息科學與工程學院，山東 濟南 250022）

基于DAA的輕量級多商家多重息票系統

柳欣1,2，徐秋亮3，張波4

（1. 山東青年政治學院信息工程學院，山東 濟南 250103；2. 山東省高校信息安全與智能控制重點實驗室（山東青年政治學院），山東 濟南 250103；3. 山東大學計算機科學與技術學院，山東 濟南 250101；4. 濟南大學信息科學與工程學院，山東 濟南 250022）

基于Brickell等的DAA（direct anonymous attestation）方案提出一個支持多商家環境的多重息票系統。新系統將多重息票中的關鍵元素與抗篡改的TPM（trusted platform module）芯片進行綁定，從而能更有效地阻止用戶的共享行為。新系統的構造過程使用了Chow等的服務器輔助簽名驗證技術、Yang等的自盲化證書技術以及Peng等的區間證明技術，使用戶在息票發布和兌換協議中均無需執行低效的對運算。相對于多個同類系統，新系統同時滿足多個較理想的性質，而且與ARM TrustZone平臺上的移動支付框架兼容。此外，新系統在通信和運算耗費方面具有明顯優勢。

多重息票；直接匿名證明；服務器輔助簽名驗證；區間證明；不可分割性

1 引言

息票（coupon）是一種傳統的廣告和促銷手段。目前，電子息票（e-coupon）已在電子商務領域得到廣泛應用，且能有效解決傳統紙質息票的環境污染問題[1]。此外，還提出了移動息票[2]（m-coupon）和多重息票[3～9]（MC, multi-coupon）的概念。其中，MC可視為包含k張可獨立兌換息票的集合，它有助于商家與客戶建立長期的購買關系，形成穩定的購買群體。出于安全性的考慮，多重息票系統（MCS,multi-coupon system）必須滿足以下性質。為了保護商家利益，不允許顧客使用偽造的MC進行兌換，也不允許多名顧客對同一張MC進行分割使用。同時，為了保護顧客的隱私，應當確保顧客交易過程的機密性和同一名顧客的多個交易間的無關聯性。

2005年，Chen等[3]提出MCS的安全模型，同時設計了一個實例化的系統。然而，該系統的最大缺點是息票發布和兌換階段的復雜度線性依賴于MC的價值。此后，文獻[4]提出了通信和運算復雜度均獨立于MC價值的改進系統。但是，該系統的弱點是要求將k作為系統的固定參數。2007年，Chen等[5]指出已有系統[3,4]僅滿足弱不可分割性（weak unsplittability），即只要客戶 U1、U2間存在完全信任關系，就可以通過復制操作實現對MC的分割使用。為此，Chen等構造了滿足強不可分割性（strong unsplittability）的改進系統，即只要客戶U1、U2相互信任且U1承諾在共享使用MC后與U2執行某種交互，就能確保U2可以繼續使用MC。由于要求顧客以固定順序進行兌換，因此 Chen等的系統仍無法滿足實際應用的需要。文獻[6]指出，已有的MCS僅考慮了單一商家的情況。為了實現客戶友好性質，應當將此類系統推廣至更具有一般性的環境，即允許不同類型的商家構成聯合體，當獲得由任何一個商家頒發的MC之后，顧客可以向聯合體中的其他商家進行兌換。為此，文獻[6]提出第一個支持多商家環境的MCS，且無需限制兌換順序。需要指出的是，文獻[6]系統的缺點是聯合體的公/私鑰對是在商家間共享的，一旦某個商家退出聯合體，將為 MCS帶來安全隱患。此外，聯合體是以靜態方式創建的，并未考慮商家的動態加入問題。最近，文獻[7,8]提出多個滿足額外性質的改進系統，如支持批量兌換、息票發布子協議滿足并發安全性等。但是，這些系統[7,8]并不支持多商家環境。2015年，Hinarejos等[9]提出一個輕量級的多商家多重息票系統。然而，該系統的用戶匿名性是借助群簽名技術實現的，因此僅實現了較低的匿名性等級，即使客戶保持誠實，也必須期望MC的發布者不與商家進行合謀。盡管采用群簽名技術有利于通過揭示身份而實現對惡意用戶的懲罰，但是最新的隱私增強匿名認證技術提倡采取“拒絕為欺詐用戶提供服務而非損害其隱私”的寬容做法[10,11]。此外，該系統僅滿足弱不可分割性。在文獻[12]中，Canard等指出MC可用于為病人開具藥物處方，并提出允許用戶分割使用MC的系統。本文認為，文獻[12]系統與上述系統[3～9]的應用目標并不一致。

從實際角度考慮，MCS應當同時滿足以下性質：1)支持多商家應用環境，從而拓寬MC的使用范圍，提高其兌換率；2)支持息票對象[5,6]的概念，即利用息票對象表示息票代表的商品或服務，因為不同商家提供的兌換服務是不同的；3)為顧客提供一定的靈活性，即允許顧客與發布者共同協商MC的價值以及商品類型；4)滿足更強的不可分割性，因為已有系統[3～9]的不可分割性都是基于純軟件技術實現的，這種方式僅能為用戶的共享行為設置障礙，而無法真正地阻止這種行為；5)系統的執行過程應當盡量避免用戶執行低效的密碼運算。已有系統[3～9]要求顧客執行RSA群上的模指數運算或者對運算。然而，這2類運算并不適合于移動設備[13～15]。

直接匿名證明（DAA, direct anonymous attestation）[16～19]是一類由可信計算組織（TCG, trusted computing group）提出的匿名證書系統，且適用于配置了專用安全芯片TPM（trusted platform module）的計算平臺。DAA方案最初用于解決可信計算平臺遠程身份證明中的隱私保護問題[20]。當前，此類方案在眾多應用系統的設計中同樣得到廣泛采用[19]。需要指出的是，標準的匿名證書系統（如文獻[21]）往往難以杜絕用戶復制和共享證書的行為。為此，Cesena等[18]利用DAA技術構造了可以阻止此類行為的匿名認證方案。

本文基于 Brickell DAA方案[16]提出一個改進的MCS。該系統具有以下的顯著特點：1)商家間無需共享秘密信息，當某個商家離開聯合體時，不會帶來安全性問題；2)用戶在息票發布和息票兌換協議中均無需執行對運算，因此本文 MCS在某種程度上是“輕量級的”；3)本文系統在新定義的多商家MCS模型下滿足可證安全；4)在效率方面，本文系統的通信和運算耗費較已有系統有明顯優勢；5)本文MCS與Pirker等[22]的基于ARM TrustZone技術的移動支付框架相兼容，因為TPM端與Host端分別對應于 TrustZone系統的 Secure World環境和Normal World環境。

2 多商家多重息票系統的定義及安全模型

2.1 多商家多重息票系統的定義

本文MCS定義是在文獻[9]定義基礎上修改得到的。具體地，多商家環境下的 MCS可視為由以下算法/協議構成的集合，即Setup、Affiliation、Disaffiliation、Issue、Redeem和Claim。其中，Setup算法用于產生系統參數以及為發布者I產生公/私鑰對。商家V通過與I執行Affiliation算法加入到聯合體Fed中，且可以在今后通過與I執行Disaffiliation算法離開聯合體。用戶U利用Issue協議向發布者I申請MC，且MC中的每張息票都是可以獨立兌換的。當希望獲得某類商品或服務時，U通過執行Redeem協議向聯合體Fed中的某個商家V兌換MC中的一張息票。此后，V通過Claim協議向I證明自己為U提供了兌換服務，從而要求后者向自己支付費用。在本文模型下，安全的 MCS應當滿足如下安全性質。

1) 正確性：若誠實的用戶U與發布者I執行Issue協議，并且獲得由I提供的MC，則U總是能利用MC中未曾使用的息票向聯合體Fed中的商家V兌換商品或服務，且V總是能向I證明這個事實，使后者向自己支付相應的費用。

2) 不可偽造性：由惡意用戶構成的聯合與誠實商家V執行的兌換次數不能超過他們通過執行Issue協議而取得的合法息票數量之和。同時，由惡意商家構成的聯合無法向I做出虛假聲明，即聲明的兌換次數超過他們實際為誠實用戶提供兌換服務的次數。

3) 無關聯性：好奇的商家V無法對用戶U執行Issue協議和Redeem協議的行為進行關聯，也無法對該用戶2次執行Redeem協議的行為進行關聯。

4) 可聲明性：若誠實的商家V為用戶U兌換了某張息票，則他總是能向I證明這個事實。

5) 不可分割性：用戶U1無法與另一個用戶U2分割使用自己的MC。

2.2 多商家多重息票系統的安全模型

在文獻[9]中，Hinarejos等提出一個MCS安全模型。但是，Hinarejos等[9]要求的防止息票重復兌換性質完全可以由不可偽造性所蘊含。此外，Hinarejos等將無關聯性實驗分為2個模式，即分別在“由惡意商家構成聯合”與“由惡意商家和發布者構成聯合”2種情況下進行分析。本文認為無需再對這2種情況進行細分，因為若MCS在后一種情況下滿足無關聯性，則在前一種情況下同樣滿足無關聯性。為此，本文結合文獻[6,9]的安全模型定義提出更為簡潔的 MCS安全模型。在本節的描述中，符號Adv與B分別表示安全性實驗中的攻擊者與歸約算法，U、V、I分別表示誠實用戶、商家以及發布者，分別表示惡意（或被攻破的）用戶、商家以及發布者，表示部分被攻破的用戶，即的host部分已經被攻破，但TPM部分仍然保持誠實。表1對Adv與B在不同安全性質實驗中充當的角色進行了總結。

表1 Adv與B在不同安全性質實驗中充當的角色

2.2.1 不可偽造性實驗

該實驗的執行過程分為以下2個模式。

1) 模式1

② 交互：B為Adv提供以下的預言服務。

散列詢問：當Adv提出關于散列函數Hi的詢問M，B向Adv返回。

Issue詢問：當Adv請求獲得一張MC，則B以I的身份與Adv執行Issue協議。

Semi-Issue詢問：當Adv請求獲得一張 MC，則B以部分被攻破用戶的 TPM 的身份與Adv聯合執行同I的Issue協議。

Redeem詢問：當Adv請求向V兌換一張對象為ob的息票，則B以V的身份與Adv執行Redeem協議。

Semi-Redeem詢問：當Adv請求向V兌換一張對象為ob的息票，則B以部分被攻破用戶的 TPM的身份與Adv聯合執行同V的Redeem協議。

Corrupt詢問：當Adv請求攻破U，則B向Adv返回U的私鑰，同時將U標記為被攻破的用戶。

③ 結束：Adv輸出ob*。若同時滿足以下條件，則判定Adv在實驗中獲勝，即Adv向B兌換的“具有息票對象ob*”的息票數量大于它通過與B執行Issue協議而獲得的“具有息票對象ob*”的息票數量。

2) 模式2

① 初始化：B執行模式 1中描述的初始化操作。此外，B定義計數器CtrR，用于統計已經為誠實用戶執行的兌換次數。

② 交互：B為Adv提供以下的預言服務。

散列詢問：描述方式同模式1。

Issue詢問：當Adv請求為U發布一張MC，則B以I的身份與U執行Issue協議。

Redeem詢問：當Adv請求為U兌換一張對象為ob的息票，則B以U的身份與Adv執行Redeem協議。

③ 結束：最終，Adv輸出由Redeem協議副本構成的列表Ltrans，并且請求I為Ltrans中所含的交易支付費用，B以I的身份與Adv執行Claim協議。若Claim協議執行成功且滿足則判定Adv在實驗中獲勝。

2.2.2 無關聯性實驗

該實驗的具體過程分為以下階段。

1) 初始化：B執行不可偽造性實驗中描述初始化操作，并且向Adv提供

2) 交互：B為Adv提供以下的預言服務。

散列詢問：描述過程同不可偽造性實驗（模式 1）。

Issue詢問：B以U的身份與Adv執行Issue協議，并且獲得由Adv提供的MC。

Redeem詢問：B以U的身份與Adv執行Redeem協議。

Corrupt詢問：當Adv請求攻破U，則B將U標記為被攻破的用戶。

4) 結束：Adv輸出猜測結果b，若b=c，則判定Adv在實驗中獲勝。

2.2.3 可聲明性實驗

該實驗的具體過程分為以下階段。

1) 初始化：B執行無關聯性實驗中描述的初始化操作。

2) 交互：B為Adv提供以下的預言服務。散列詢問：描述過程同不可偽造性實驗。

Redeem詢問：當Adv請求向V兌換一張對象為ob的息票，B以V的身份與Adv執行Redeem協議。

3) 結束：最終，Adv請求向V兌換一張對象為ob*的息票，若滿足以下條件，則判定Adv在實驗中獲勝，即：①B與Adv成功執行Redeem協議并且獲得對應的交易副本trans*；②當B以trans*為輸入與Adv執行Claim協議時，該協議總是失敗，即B無法證明自己為用戶提供兌換服務這個事實。

2.2.4 不可分割性實驗

該實驗的具體過程分為以下階段。

1) 初始化：B執行不可偽造性實驗（模式1）中描述的初始化操作。

2) 交互：B為Adv提供以下的預言服務。

散列詢問：描述過程同不可偽造性實驗（模式 1）。

Issue詢問：描述過程同不可偽造性實驗（模式 1）。

Semi-Issue詢問：描述過程同不可偽造性實驗（模式1）。

Redeem詢問：描述過程同不可偽造性實驗（模式 1）。

Semi-Redeem詢問：描述過程同不可偽造性實驗（模式1）。

3) 結束：Adv輸出MC*。若同時滿足以下條件，則判定Adv在實驗中獲勝，即：①MC*是有效的；②MC*的剩余價值大于0；③當B以MC*為輸入執行Redeem協議時，該協議總是失敗，這表明Adv已經將MC*的剩余價值轉移至其他的MC′，即實現了對MC*的分割使用。

3 預備知識

令G1、G2、GT分別為素數p階循環群，滿足。令?表示雙線性映射，使G1×。令表示素數p階循環群，滿足

3.1 復雜性假設

q-SDH（q-strong Diffie-Hellman）假設[23]：對于任何的PPT（probabilistic polynomial time）算法A，定義概率

y-DDHI（decisional Diffie-Hellman inversion）假設[12]。對于任何的PPT算法A，定義概率

G1-DDH（G1- decisional Diffie-Hellman）假設[19]：對于任何的PPT算法A，定義概率

G1-DDH假設表明是可以忽略的。

3.2 BBS+簽名方案

3.3 自盲化證書技術

最近，Yang等[24]提出了旨在減輕用戶端運算耗費的自盲化證書技術。為了證明掌握 BBS+方案簽名(A,e,s)，證明者選取f∈Zp，計算A′=Af,，其中，于是，證明掌握秘密元素，使驗證等式成立，等價于證明掌握秘密元素使關系成立。此外，要求驗證者額外驗證等式是否成立以及是否滿足

3.4 Peng-Yi區間證明技術

本文系統的構造過程要求使用 Peng等[25]的關于秘密元素j屬于公開集合[1,Ji]的準確區間證明協議，記為。其基本思想是首先將目標證明等價為，其中。然后，計算秘密元素j?1關于底數的表達式，滿足，從而將關于的證明約化為l個關于的更為簡單的證明。現在，證明進一步等價于證明

3.5 對委托運算協議與服務器輔助簽名驗證技術

委托運算技術有利于用戶將繁重的運算任務委托給不可信的服務器，且此類運算模式特別適合于當前的云計算應用環境。對委托運算（pairing delegation）協議是一種委托計算技術，使用戶端無需再執行昂貴的對運算。Canard等[15]指出，對委托運算協議應當滿足完備性、可驗證性和保密性。

服務器輔助簽名驗證（SASV, server-aided signature verification）技術的目標是幫助用戶將數字簽名驗證過程中涉及的對運算任務委托給服務器。最近，Chow等[14]提出了一般性的SASV框架，且允許將任何對委托運算協議作為該框架的底層模塊。此類技術要求滿足以下性質：1)適應性選擇消息與驗證攻擊下的存在的不可偽造性；2)合謀的適應性選擇驗證攻擊下的可靠性。

4 對本文系統的描述

4.1 本文系統的設計思想

4.2 具體描述

4.2.1 系統中的參與方

在本文系統中，共涉及以下參與方，即由TPM和主機host構成的用戶U，由多個商家構成的聯合體

4.2.2 系統建立（Setup）

以安全參數1λ作為輸入，I執行下列步驟。

6) 創建公共數據庫DB，并且為DB創建任意的標準數字簽名方案SIG下的公/私鑰對，用于為向DB中寫入重復檢測標簽的商家產生收據。創建廢除列表BL，以及列表AL、ADL。

4.2.3 商家加入聯合體（Affiliation）

希望加入Fed的商家V與I簽署商業合作協議，其內容包括：規定V支持兌換的商品或服務類型，I承諾為V提供兌換服務而支付費用等。然后，I為V分配身份標識idV，執行AL←AL∪

4.2.4 息票發布（Issue）

該協議由U（host+TPM）和I共同執行。假設TPM 已經與I建立起可信信道[16]。為了提高在線運算效率，假設TPM已事先選取，并計算，具體步驟如下。

上述的cnt是TPM內部計數器。本文允許用戶通過多次執行當前協議而獲得多個MC，且假設在每次執行當前協議時，cnt的取值不變。

4)I驗證nI。對于每個sk′∈BL，I驗證是否滿足若滿足，則計算，驗證是否滿足。若不滿足，則選取e, s∈RZp，計算向TPM發送

5) TPM向host發送(F1,mid,cre)，host驗證cre是否為關于的有效 BBS+簽名，即是否滿足驗證等式

為了提高驗證效率，host利用 Chow 等[14]的SASV技術進行驗證，具體過程如下。

4.2.5 息票兌換（Redeem）

4) 若V接收到收據（receipt），則利用PKDB驗證receipt的有效性，然后，V為用戶提供所請求的類型obi的服務，并且保存交易副本。相反，若V接收到的是出錯信息，則拒絕為U提供兌換服務。

4.2.6 聲明（Claim）當V已經積累了由若干兌換交易副本構成的列表，且希望向I索取費用，則與I執行以下步驟。

2) I檢查是否滿足idV∈AL，若滿足，則對于Ltrans中的每個交易副本，I執行如下檢查：①驗證知識簽名π的有效性；②驗證是否滿足S∈DB；③驗證receipt的有效性。若上述檢查都通過，則I為V支付費用。相反，若滿足S?DB或receipt驗證失敗，則判定V進行欺詐。

4.2.7 商家退出聯合體（Disaffiliation）

5 知識簽名π的實現過程

為了便于理解，本文將π的執行過程分成2個子簽名π1、π2進行描述。

5.1 子簽名π1的實現過程

在π1的構造過程中，本文采用Yang等[24]的自盲化證書技術對 Au等[23]的關于“掌握有效BBS+方案簽名”的方法進行了優化。π1的最終形式為

π1的具體產生過程如下。

2) host在[1,Ji]中選取未使用過的序號j，計算重復檢測標簽，選取 rs∈RZp，計算，選取，計算。對于，選取，計算

5) host在Zp上計算

π1的驗證過程如下。

5.2 子簽名π2的實現過程

根據3.4節可知，可以利用Peng等[25]的小區間準確區間證明技術將轉換為

3) 將π2細化為如下形式

π2的驗證過程如下。

2)采用π2產生過程中的方式計算系數，計算。計算驗證是否滿足

5.3 子簽名π1與π2的合成

知識簽名π是通過對子簽名π1、π2執行并行合成而得到的。最終的合成結果為

在驗證過程中，驗證者需要根據5.1節和5.2節的方式計算且最終的驗證等式為

6 安全性分析

證明 限于篇幅，省略了正確性的證明過程。

1) 不可偽造性。當前實驗分為以下2個模式。

散列詢問：根據文獻[16]的結論，無需將散列函數H1、H3視為隨機預言機，因為它們都是內部函數。因此，B只需提供對函數H2、H4的模擬，即對于Adv提出的詢問，B返回在Zp上隨機選取的元素作為應答，同時確保所提供的應答滿足一致性。

顯然

Corrupt詢問：當Adv請求攻破用戶Ui，若Ui在Reg的對應表目中的標識位滿足c=0，則B向Adv返回Ui的私鑰ski，設置Adv在當前實驗中獲勝的條件是，使。根據底層區間證明協議[25]的可靠性以及偽隨機函數[26]的抗碰撞性，Adv不可能實現對MC的透支使用，也不可能利用使用過的重復檢測標簽S執行兌換而不被發覺。因此，若Adv在實驗中獲勝，則它必然在某次兌換過程中成功實現了對BBS+簽名方案實例的偽造攻擊。于是，B可以利用上述的重繞技術提取出關于秘密元組(sk**,的 BBS+方案簽名Reg且sk**?BL，即違背了q-SDH假設。

② 模式2。B執行當前實驗模式2下的初始化操作，并且定義計數器CtrR。在當前實驗中，B為Adv提供以下的預言服務。

散列詢問：描述方式同模式1。

Issue詢問：當Adv請求為U發布一張MC，則B自行模擬I與U執行Issue協議的過程。

Redeem詢問：當Adv要求為用戶U兌換一張對象為obi的息票，B以U的身份與Adv執行Redeem協議。若該協議執行成功，則B設置

最終，Adv輸出由Redeem協議副本構成的列表Ltrans，若Ltrans中的每個副本都能通過Claim協議的驗證過程且滿足則表明，且該副本并非通過與B執行Redeem協議而獲得的。此時，B對Adv執行重繞，必然能從π*中提取出關于秘密元組的 BBS+方案簽名即違背了q-SDH假設。

散列詢問：描述過程同不可偽造性實驗（模式1）。

情況 1：若滿足i=i*，B設置 F1=v且自己并不掌握B采用以下方式模擬Issue協議，即選取，選取，計算，設置

無論屬于哪種情況，當Issue協議結束后，B均需執行以下操作。

④若i=i*，則設置，其中，符號“*”表示未知元素。否則，設置

情況1：若滿足i=i*，則B采用模擬方式產生知識簽名π。

情況2：若i≠i*，則B以誠實方式產生知識簽名π。

Corrupt詢問：當Adv請求攻破用戶Ui，若，則B運行失敗；否則，B采用不可偽造性實驗（模式1）中的方式模擬當前詢問。

①B以Uc的身份與執行Redeem協議，并且在該協議中向兌換第α0張MC中的第β0張息票。在該協議中，B選取r∈RZp，設置且采用當前實驗Redeem詢問中的技術模擬產生知識簽名π。

②B以U1?c的身份與執行Redeem協議，并且在該協議中向兌換第α1張MC中的第β1張息票。在該協議中，B以誠實方式產生知識簽名π。

最終，Adv輸出對挑戰比特c的猜測結果b。若滿足b=c，則B判定z為群G1上的隨機元素，否則，B判定z=uab成立，從而攻破了群G1上的DDH假設。

注意，Adv同樣無法在當前實驗中借助U0, U1在兌換過程中產生的重復檢測標簽S對它們進行分辨。因為，根據文獻[13]結論，在群上的y-DDHI假設下，元素S與上的隨機元素是不可分辨的。

3) 可聲明性。B執行可聲明性實驗的初始化操作，并且采用可聲明性實驗中定義的方式回答Adv提出的散列詢問和Redeem詢問。由于Claim算法中的驗證操作是V在Redeem協議中執行的驗證操作的子集，因此，Adv將無法在該實驗中獲勝。

4) 不可分割性。B執行不可分割性實驗的初始化操作。此外，B創建計數器，該計數器的取值代表了第i張MC的剩余價值，其中N表示Adv提出的Issue詢問次數上界。B創建一維數組，其中，用于存儲為Adv發布的第i張MC。在實驗中，B為Adv提供以下的預言服務。

散列詢問：描述過程同不可偽造性實驗（模式1）。

Issue詢問：假設B已經為Adv發布了i?1張MC。當Adv提出詢問B利用重繞技術提取出秘密知識B為Adv產生crei=。B 設置

Semi-Issue詢問：假設B已經為Adv發布了i? 1張MC。當Adv提出詢問(J1,?,Jn)，B自行選取，為Adv產生。B設置

Redeem詢問：B以V的身份與Adv執行Redeem協議，并且通過對Adv執行重繞而提取出秘密知識。B根據mid在數組中進行查找而判定Adv使用的是哪張MC。假設滿足B設置

Semi-Redeem詢問：B的模擬過程同不可偽造性實驗（模式1）。

最終，Adv輸出某張MC*的序列號mid*，滿足，B根據計數器的取值而判定的剩余價值是否大于零。若是，則B以為輸入執行Redeem協議。顯然，該協議總是能執行成功。由于用戶因滿足而無法通過Redeem協議的驗證過程，同時用戶的host部分不掌握TPM私鑰，因而無法實現對MC*的分割使用，即Adv將無法在當前實驗中獲勝。

盡管對委托運算協議[14,15]有利于減輕用戶的運算負擔，但是在現實應用中無法確保提供委托運算服務的服務器一定保持誠實。由于對Φ的調用發生在用戶端host對證書進行驗證的環節，因此，需要對定理 1證明過程中涉及“由歸約算法B充當誠實用戶且由攻擊者Adv充當惡意參與方”的攻擊場景進行重新討論，即需要對不可偽造性實驗（模式2）和無關聯性實驗進行重新討論。同時，在本節假設Adv總是與提供對運算服務的惡意服務器（記為）進行合謀。

引理 1 在不可偽造性實驗（模式 2）中，即使攻擊者Adv與惡意服務器進行合謀，也無助于它在該實驗中獲勝。

證明 除了定理1中描述的執行過程，當前實驗還可以以下方式執行。B設置列表Lcre，用于保存以誠實方式產生的用戶證書。在實驗執行過程中，B為Adv提供以下的預言服務。

采用類似的技術，可以證明以下3個引理。

引理 2 在不可偽造性實驗（模式 2）中，即使攻擊者Adv與惡意服務器進行合謀，也無法使誠實用戶接受錯誤的委托運算結果。

引理 3 在無關聯性實驗中，即使攻擊者Adv與惡意服務器進行合謀，也無法使誠實用戶在服務器輔助驗證和標準驗證2種模式下獲得不一致的驗證結果。

引理 4 在無關聯性實驗中，即使攻擊者Adv與惡意服務器進行合謀，也無法實現對誠實用戶進行分辨。

定理 2 只要底層 BBS+簽名方案在適應性選擇消息攻擊下滿足存在的不可偽造性，同時底層對委托運算協議Φ滿足完備性、可驗證性和保密性，則在引入底層協議Φ后，本文MCS仍然是安全的。

證明 在不可偽造性實驗（模式 2）和無關聯性實驗中，歸約算法B以誠實用戶身份與Adv和惡意服務器的聯合進行交互。盡管B在執行交互過程中需要將對運算的任務委托給，但引理1～引理4表明，委托運算過程并不會有助于Adv在這2個實驗中獲勝。綜上得出，在引入底層對委托運算協議Φ后，本文MCS仍然是安全的。

7 本文系統的性能分析

表2為本文系統與已有系統的主要性質對比。在發布協議中，表2中的所有系統在本質上均要求用戶與商家（或發布者）執行一次或多次盲簽名協議。其中，文獻[5,6]系統要求執行的盲簽名輪次與MC的價值k呈線性關系，而其他系統僅需執行 1次盲簽名發布協議。在表2中，本文系統、文獻[7]的方案 2以及文獻[9,12]系統均支持息票對象的概念，因而允許用戶利用1張MC兌換多種類型的商品或服務，而其他的系統僅允許兌換一種類型的商品或服務。早期的系統[3,4]要求將MC的價值k作為系統的固定參數，因而影響了其實用性，此后的系統均支持用戶與發布者（或商家）協商k的取值。需要指出的是，本文系統和文獻[6,9]系統均考慮了多商家聯合經營的模式，因此滿足更好的客戶友好性質。如前所述，文獻[3～9]系統都是利用純軟件的方法來確保多重息票的不可分割性，本文系統則借助 TPM 芯片實現了最強的不可分割性。此外，文獻[12]系統是目前唯一支持對多重息票進行分割使用的系統。在匿名性方面，文獻[9]系統因構造過程使用了群簽名技術而實現了最弱的匿名性。

表2 本文系統與已有系統的主要性質比較

表3 本文系統與已有系統的通信耗費比較

表3和表4對本文系統與表2所列其他系統（文獻[12]系統除外）進行了通信耗費和運算耗費的詳細比較。所采用的具體方法如下。

1) 文獻[3,5,6]系統都是在 RSA 群上構造的，本文選取了相同的安全參數[30]。文獻[4]系統和本文系統都是在雙線性群對12(G, G)上構造的，本文同樣選取了相同的參數。此外，文獻[7～9]系統的構造過程同時使用了RSA群與雙線性群對。在比較中，本文用符號|G1|、|GT|分別表示群G1和目標群GT上的元素長度，表示有限域Zp上的元素長度，表示 RSA群上的元素長度。根據文獻[24]的結論，當在MNT曲線上實現群對且以 80 bit安全性為目標時，滿足

表4 本文系統與已有系統的運算耗費比較

2) 在運算耗費的分析中，本文并未對多指數運算與單指數運算進行區分，因為在對指數運算過程進行優化的情況下，這2種運算的耗費是接近的[24]。用符號P表示執行1次對運算的耗費，用和分別表示在群G1、G2、GT和Zn上執行1次指數運算的耗費。可以做出如下的估算，即此外，本文認為在文獻[7]系統中，用戶和商家需要執行群G1上指數長度為30 bit的小指數運算。根據“指數長度為x bit特的指數運算相當于1.5x次乘法”的結論[31]得出，1次群G1上的標準指數運算相當于 5次此類的小指數運算。最終，本文將G1、G2、GT和Zn上的指數運算以及小指數運算都估算為G1上的指數運算。

3) 在本文系統中，特定參數n表示MC支持兌換的服務類型種類，Ji表示第i類對象的數量。為了便于比較，本文假設用戶在所有系統中僅申請一種類型的服務，于是n=1。同時，假設每張MC的價值均為50。不失一般性，對于本文系統，假設滿足J1=50。此外，在本文系統的息票兌換協議中，底層的區間證明協議要求在以為底數的編碼系統中對未使用過的息票序號進行分解。在文獻[7]系統中，同樣要求在u(ugt;2)進制下對MC的已兌換次數進行分解。此處選取

4) 在本文系統的息票發布協議中，用戶需要調用底層的對委托運算協議實現對 BBS+方案簽名的服務器輔助驗證。為此，本文使用了文獻[15]中的PVPV（public variable point and public variable point）類型協議。用戶每次調用該協議的運算耗費約為

5) 在本文系統的Issue和Redeem協議中，發布者（或商家）還需要根據底層DAA方案的列表BL驗證用戶的 TPM 私鑰是否因泄露而被廢除，而參與比較的其他系統并未考慮這個問題。為了比較的公平，表4的運算耗費比較中并未統計執行此項檢查的耗費。此外，用符號“*”和“**”對本文系統中TPM端和host端的運算耗費分別進行標記。

作為總結，本文系統實現了表2列舉的所有重要性質。在通信耗費方面，本文系統僅次于最高效的文獻[4]系統。在發布協議的運算耗費方面，本文系統接近于高效的文獻[3,9]系統，且本文系統在兌換協議用戶端的運算耗費方面是最高效的。

8 結束語

針對已有多重息票系統未能較好解決防止惡意用戶對多重息票進行分割使用的現實問題，本文提出了基于DAA的輕量級多商家多重息票系統。相對于已有系統，本文系統不僅實現了支持兌換不同類型的服務、允許用戶與發布者協商兌換次數和適合于多商家環境等實用性質，而且滿足最強等級的不可分割性。此外，本文系統不要求用戶執行任何的對運算，而且與Pirker等的移動支付框架相兼容。效率分析表明，本文系統在運算和通信耗費方面較已有系統具有明顯優勢。今后將進一步優化用戶端（特別是TPM）的運算效率，考慮所設計的系統與下一代TPM 2.0標準的兼容問題等。

[1] CHANG C C, SUN C Y. A secure and efficient authentication scheme for e-coupon systems[J]. Wireless Personal Communications, 2014,77(4): 2981-2996.

[2] HSUEH S C, CHEN J M. Sharing secure m-coupons for peer-generated targeting via eWOM communications[J]. Electronic Commerce Research and Applications, 2010, 9(4): 283-293.

[3] CHEN L, ENZMANN M, SADEGHI A R, et al. A privacy-protecting coupon system[C]//The 9th International Conference on Financial Cryptography and Data Security. Roseau, 2005: 93-108.

[4] NGUYEN L. Privacy-protecting coupon system revisited[C]//The 10th International Conference on Financial Cryptography and Data Security.Anguilla, British West Indies, 2006: 266-280.

[5] CHEN L, ESCALANTE A, L?HR H, et al. A privacy-protecting multi-coupon scheme with stronger protection against splitting[C]//The 11th International Conference on Financial Cryptography and Data Security. Scarborough, Trinidad and Tobago, 2008: 29-44.

[6] L?HR H. Privacy-preserving protocols and applications for trusted platforms[D]. Bochum: Ruhr-Universit, 2012.

[7] 柳欣, 徐秋亮. 實用的強不可分割多重息票方案[J]. 計算機研究與發展, 2012,49(12): 2575-2590.LIU X, XU Q L. Practical multi-coupon systems with strong unsplittability[J]. Journal of Computer Research and Development, 2012,49(12): 2575-2590.

[8] 柳欣, 徐秋亮. 并發安全的緊湊多重息票方案[J].電子學報,2012,40(5): 877-882.LIU X, XU Q L. Compact multi-coupon systems with concurrent security[J]. Acta Electronica Sinica, 2012, 40(5):877-882.

[9] HINAREJOS M F, ISERN-DEYà A P, FERRER-GOMILA J L, et al.MC-2D: an efficient and scalable multicoupon scheme[J]. The Computer Journal, 2015, 58(4): 758-778.

[10] WANG W J, FENG D G, QIN Y, et al. ExBLACR: extending BLACR system[C]//The 19th Australasian Conference on Information Security and Privacy. Wollongong, NSW, Australia, 2014:397-412.

[11] XI L, FENG D G. FARB: fast anonymous reputation-based blacklisting without TTPs[C]//The 13th Workshop on Privacy in the Electronic Society. Scottsdale, Arizona, USA, 2014:139-148.

[12] CANARD S, GOUGET A, HUFSCHMITT E. A handy multi-coupon system[C]//The 4th International Conference Applied Cryptography and Network Security. Singapore, 2006: 66-81.

[13] ISERNS-DEYà A P, HUGUET-ROTGER L, PAYERAS-CAPELLà M M, et al. On the practicability of using group signatures on mobile devices: implementation and performance analysis on the android platform[J]. International Journal of Information Security, 2014,(8): 1-11.

[14] CHOW S S M, AU M H, SUSILO W. Server-aided signatures verification secure against collusion attack[J]. Information Security Technical Report, 2013, 17(3): 46-57.

[15] CANARD S, DEVIGNE J, SANDERS O. Delegating a pairing can be both secure and efficient[C]//The 12th International Conference on Applied Cryptography and Network Security. Lausanne, Switzerland,2014: 549-565.

[16] BRICKELL E, LI J T. A pairing-based DAA scheme further reducing TPM resources[C]//The 3rd International Conference on Trust and Trustworthy Computing. Berlin, Germany, 2010: 181-195.

[17] 楊波, 馮登國, 秦宇, 等. 基于可信移動平臺的直接匿名證明方案研究[J]. 計算機研究與發展, 2014,51(7):1436-1445.YANG B, FENG D G, QIN Y, et al. Research on direct anonymous attestation scheme on trusted mobile platform[J]. Journal of Computer Research and Development, 2014, 51(7): 1436-1445.

[18] CESENA E, L?HR H, RAMUNNO G, et al. Anonymous authentication with TLS and DAA[C]//The 3rd International Conference on Trust and Trustworthy Computing. Berlin, Germany, 2010: 47-62.

[19] CHEN L. A DAA scheme requiring less TPM resources[C]//The 5th International Conference on Information Security and Cryptology.Beijing, China, 2010: 350-365.

[20] 張倩穎, 馮登國, 趙世軍. 基于可信芯片的平臺身份證明方案研究[J]. 通信學報,2014,35(8):95-106.ZHANG Q Y, FENG D G, ZHAO S J. Research of platform identity attestation based on trusted chip[J]. Journal on Communications,2014,35(8):95-106.

[21] BALDIMTSI F, LYSYANSKAYA A. Anonymous credentials light[C]//2013 ACM SIGSAC conference on Computer amp; Communications Security. Berlin, Germany, 2013:1087-1098.

[22] PIRKER M, SLAMANIG D. A framework for privacy-preserving mobile payment on security enhanced arm trustzone platforms[C]//Proceedings in 2012 IEEE 11th International Conference on Trust,Security and Privacy in Computing and Communications. Liverpool,UK, 2012: 1155-1160.

[23] AU M H, SUSILO W, MU Y, et al. Constant-size dynamic k-times anonymous authentication[J]. IEEE Systems Journal, 2013, 7(2):249-261.

[24] YANG Y, DING X, LU H, et al. Self-blindable credential: towards lightweight anonymous entity authentication[EB/OL]. https://eprint.iacr.org/2013/207.pdf.

[25] PENG K, YI L. Studying a range proof technique-exception and optimization[C]//The 6th International Conference on Cryptology in Africa. Cairo, Egypt, 2013: 328-341.

[26] DODIS Y, YAMPOLSKIY A. A verifiable random function with short proofs and keys[C]//The 8th International Workshop on Theory and Practice in Public Key Cryptography. Les Diablerets, Switzerland,2005: 416-431

[27] SCOTT M. Unbalancing pairing-based key exchange protocols[EB/OL].https://eprint.iacr.org/2013/688.pdf.

[28] AU M H, SUSILO W, YIU S M. Event-oriented k-times revocable-iff-linked group signatures[C]//The 11th Australasian Conference on Information Security and Privacy. Melbourne, Australia, 2006:223-234.

[29] PENG K. A general, flexible and efficient proof of inclusion and exclusion[C]//Cryptographers’ Track at the RSA Conference 2011. San Francisco, CA, USA, 2011: 33-48.

[30] CAMENISCH J, LYSYANSKAYA A. A signature scheme with efficient protocols[C]//The 3rd International Conference on Security in Communication Networks. Amalfi, Italy, 2002: 268-289.

[31] PENG K, BOYD C, DAWSON E. Batch zero knowledge proof and verification and its applications[J]. ACM Transactions on Information and System Security, 2007, 10(2): 1-28.

Lightweight multi-coupon system for multi-merchant environments with DAA

LIU Xin1,2, XU Qiu-liang3, ZHANG Bo4
（1. School of Information Engineering, Shandong Youth University of Political Science, Jinan 250103, China;2. Key Laboratory of Information Security and Intelligent Control in Universities of Shandong(Shandong Youth University of Political Science), Jinan 250103, China;3. School of Computer Science and Technology, Shandong University, Jinan 250101, China;4. School of Information Science and Engineering, University of Jinan, Jinan 250022, China）

A multi-coupon system for multi-merchant environments was proposed by extending the DAA (direct anonymous attestation) scheme of Brickell etc. The new system bound the key elements in multi-coupon with the tamper-resistant TPM（trusted platform module）chip, so that it could prevent users from sharing behavior more effectively.By using the server-aided signature verification of Chow etc, the self-blindable credential technique of Yang etc, and range proof of Peng etc, the new system does not require customers to perform expensive pairing operations in the issue protocol and the redeem protocol. Compared with previous similar systems, the new system simultaneously satisfies several ideal properties and it is compatible with the mobile payment framework on the ARM TrustZone platform. Moreover,it has obvious advantages in aspects of communication and computation costs.

multi-coupon, direct anonymous attestation, server-aided signature verification, range proof, unsplittability

s: The National Natural Science Foundation of China(No. 61173139), Shandong Provincial Natural Science Foundation(No.ZR2015FL023, No.ZR2014FL011),The Project of Shandong Province Higher Educational Science and Technology Program(No.J14LN61), The Doctoral Research Start-up Funding Project of Shandong Youth University of Political Science (No.14A007)

TN918.2

A

10.11959/j.issn.1000-436x.2016175

2015-09-24；

2016-07-07

國家自然科學基金資助項目（No.61173139）；山東省自然科學基金資助項目（No.ZR2015FL023, No.ZR2014FL011）；山東省高等學校科技計劃資助項目（No.J14LN61）；山東青年政治學院博士科研啟動經費資助項目（No.14A007）

柳欣（1978-），男，山東廣饒人，博士，山東青年政治學院副教授，主要研究方向為密碼學與信息安全。

徐秋亮（1960-），男，山東淄博人，山東大學教授、博士生導師，主要研究方向為密碼學與信息安全。

張波（1981-），男，山東德州人，博士，濟南大學講師，主要研究方向為密碼學與信息安全。