|
|
    
|
以前早期的時候有一個研究叫做server aided, 用server來幫助它做計算, 所以在設計particle的時候,複雜的計算不要讓client做, 都是server來做, 做一系列有很多人做了研究, 這個研究的缺點是本來是client做百分之50, server做百分之50, 現在變成server做百分之99, client做百分之1, 以整個overall 的computation time來講的話,幾乎double了, 本來50/50的話很多計算可以同時來處理, 雖然server aided當時有很多的研究, 很多的論發表, 但是以global的眼光來講, 還是有一點點的缺點,那我們所謂的user efficient來講, 是盡量不增加server的load, 但是希望把client的load降到最低, 就是還是維持50/50的計算, 但是以演算法的方法來降到最低, 要怎樣做呢? 那就要看你的功力啦, 把資料結構, 演算法, 作業系統的基楚打穩, 才有辦法想出這個東西出來, 因為基本上簡單的說, 比如做一個public key的加密的方式, 最難的部分是在做指數的運算, server aided事實上的做法就是說, 本來是它要做兩個指數運算, 我要做兩個指數運算, 它的做法是說, 它做四個指數運算, 我做十個乘法, 通常一個指數運算相對差不多一千個乘法, 我們有辦法讓它做兩個指數運算, 我不要做指數運算, 但是我們不可能做到零個指數運算, 那是不可能, 那種東西做不出來, 因為基本上有問題的計算難度在那邊,所以我有辦法由particle設計, 你說可以把五個變成四個, 或者四個變成三個,那你沒辦法把一個變成零個, 那是差了n倍, 那是無窮多倍, 那種事以理論上是做不出來的, 大概是這個樣子.這個我想同學們就比較清楚. 這個我們要的, internet的, 基本上我今天要講到的, 就是service, 因為我現在要做的是從user這邊來考量, 我要讓, 基本上我等於說, 以前的人的一個做法一個系統的話, 因為它是要賣給這個, 像說賣給isp呀, 或者賣給大主富, 像現在我們在使用的網路下單系統, 它security採用ssl,security socket layer呢它只有單向的認證, 它沒有雙向的認證, 結果它保護的是誰, 保護的是奸商, customer其實它完全沒有保護, 所以說今天的話, 你下單啦, 你說我沒下單, 你賴不掉, 反過來講的話, 你下單啦, 但奸商說我跟本沒有收到, 你沒有prove, 他可以把你賴掉, 只是說大部分人不知道這種事, 那我們是以user的角度來講, 我們是希望user的計算量降低, 當然也要考慮到user能滿意你的服務, 怎樣能滿意你的服務呢, 基本上呢你要有效率, 現在internet上呢,當然有效率, 除了這些以外呢, 當然也有你的構, 我們的構呢, 最主要有兩點,基本上呢就是security的方面, security的方面呢, 我們就是說能不能從底層開始想起, 我們想幾個底層比較security mechanisms, 利用這個mechanism來構建上層的一個讓user非常滿意, 而且又非常安全的service, 像說電子投票呀, 電子貨幣等等這種東西, 你要達到這種東西, 你當然要考慮到hacker, viruses這些東西, 另外一個就是efficiency, efficiency就是你可能是ic card, 或者是一些moble的sinclient, 它的計算能力很低. 接下來這是數學, 我們以幾個圖來表示,首先數位簽章, digital signature, 數位簽章是做一個認證的動作,authentication, 通常簽章是說, 我一個東西, 我蓋了章, 蓋了這個章可以證明什麼東西, 數位簽章則是, 我有一份文件(message), 我拿給一個有公信力的機關去證明我的身份呀, 我有什麼權力呀等等, 我拿了一份文件,拿給一個公証人士,我們叫它作Signer.簽章者,它會在這份文件蓋一個章,我們叫這個章叫數位簽章.其實是一個數字,這個數字可能有幾百位元.我們可以拿這些數字和剛才的message配合去作一些事情.例如我給遊樂園主管機關(Signer)一百萬,主管機關(signer)就會幫我簽章,証明我有付百萬.那我就可以到遊樂園玩十年.那數位簽章就是給Server一個message,Server則會給你一個章,而你憑這個章可以做你要做的事情.基本上這數位簽章就是代表是一個簽名.對所做的事情負責. 但有時很多application不只是要數位簽章.假設我們投票好了.現實中的投票.我們不希望表示投票人的身份,以表公正.如你們系上投票要不要成立博士班.投票地點在系辦則我們投票時則需要証明你是本系的學生.但為了公平起見不想知道你是誰,只要知道你是本系學生就夠了. 則我們可以拿一張空白票到系主任那邊.系主任檢查你是否本系學生,若是的話就幫你在空白票上面蓋一個鋼印.這就証明你是本系的學生.你就可以將這經過証明的印拿到系辦上投票,那就知道你是本系的學生,卻不曉得你是誰.這叫做盲目簽章(Blind signature).正式地說我們拿了一個message,將這message打亂數,再去經過認証(打鋼印)拿回想要用的地方(系辦).如例如我們要買電子貨幣.假設我們希望在阿爾巴尼亞買東西.但台幣不能用.那我們就要跟銀行買電子貨幣了.我們拿出現金一百元.給銀行.銀行就在100元的電子貨幣蓋章(鋼印).証明那電子貨幣有效.那我們就可以將電子貨幣在網路上傳送.簽章只有Signer能做,這並不是隨便可以仿造Signer簽章的動作的.因為這牽涉到Key的概念.這個是我們今天所將會講到最關鍵的主題(Blind signature).這有兩個觀念,一個觀念是我們所給的message只有Signer才能幫我們簽章,其他並沒有辦法仿造出Signer的Signature.第二個觀念是Signer所簽的印,signer沒有辦法說誰叫它幫Message 簽的.將來會應用到的如電子貨幣和電子投票.還有其他可以應用到的.不過我相信前兩者我們將來一定會碰到的.題外話,為什麼現在Credit Card還沒有辦法取代貨幣,是因為Credit Card會紀錄所以消費者的用錢,但是不是所有人都希望把他用錢用在那裡給人知道.好像你某天去酒吧.你通常都不會用Credit Card付帳.因為Credit Card的收據會寄到家裡,那就會給老婆知道囉(笑一下).因此還是有人希望匿名的付帳.因此Credit Card還是不可能取代掉現鈔這種匿名的功能.不過數位系統就有辦法.這是題外話.那我們就可以運用到剛才的觀念去進行投票動作,投票者送一個message給Signer叫它幫他簽章,Signer在這Message上(空白票)上打了一個鋼印,証明投票者是符合投票資格的.投票者就可以拿這個蓋了印的空白票到投票中心進行投票.投票中心只知道這一張是有效的選票(符合投票資格),卻不曉得投票者是那一個人.當然.在數位化的國度裡.這些行為則是一連串的數學運算. 當然,還有些問題啦.例如我們現實生活中,可以在自己選票中標一個號碼,那記票中心可以在選舉之後,公告有效選票的號碼出黎,投票人若知道自己所投過的票不在所公告之內.則他可以抗議.這就需要一些機制去運作啦.Digital Cash還有牽涉到一個角色--商家.因為把買賣動作數位化,那會觸及到Double-Spending的問題.因為數位化的東西是很容易copy的,買者可以將他的電子貨幣重複在好幾家商店買賣東西.商店除了要檢查那電子貨幣是不是有效的時候,還要向銀行檢查一下那電子貨幣是不是還沒用過(fresh).如果銀行的Database告訴商家那電子貨幣已經用過了.那商家可以拒絕交易.這就叫做Double-Spending.
剛才所提到的,是普通的Payment系統.還有一種的是Macro-Payment的系統.為什麼有這種系統呢?是因為這種Payment系統也是有成本的,如果認証機關所收獲的,比支出的少.則有可能用另一種較便宜的系統(如
Macro-Payment)去處理.這是商業性的考慮.現實生活中,如資策會的點歌系統.就是採用這種Macro-Payment的方法.使用者先向資策會買點,然後再用點換取服務.為什麼這樣做呢?是因為先把現金收取,再去銀行賺利息.很多時這是商業性的考慮.如Credit
Card提供業者為何一年有這麼多的炸取案例.都仍然用原本的系統呢?就是因為在成本上可以忍受這種缺失.剛才所提到的Double-Spending產生一個問題,就是銀行的Database可能會很大.那怎樣解決呢.在現實生活中我們可以在蓋鋼印的e-cash的地方寫明有效日期.一年或一個月.那database在那段時間之外就把這筆錢的有效狀態砍掉.
所以database 的資料就不會無窮限的增大,
問題是說要怎樣做這樣的事情呢? 怎樣把有效日期放進去呢?
因為一開始簽章時這是一個blind的message,
所以必須有個技術就是今天我sign的時候, 你給我一個blind的message,
一個密封信封裡面放什麼都不知道,
但是怎樣把一個東西的有效期間,
當然蓋章很容易就可以看出有效期間,
不過很可惜我們做的是個數學,
數學必須要讓他說這個跟這個東西, 當recover把信封拿掉的時候,
出來他們兩個的signature, 所以我們就是要有一個signing的方式,
它會製造這個signature出來, signing的function他可能知道啦,
但是他不知道那個key, 所以不能偽造signature出來,我現在需要把一個actual的information加進來,
我們這個signer可以強迫把這個information加到blind signature裡面的這個東西叫partial
signature,為什麼叫partial? 不是完全的呢?
因為他本來是這個東西跟這個東西不能關聯的, 現在如果有a的話,
他至少會知道說, 可能有十萬個人來簽我information是放a的,
可能一百萬人information可以reduce到一萬人, 不是完全的,
但是他至少可以放些information進去,
這個技術望要是要解決你的database無窮無盡增長的問題,
有時候我希望說我設計的東西平常是unlinkable,
但是有必要的時候又可以把他link起來, 給他一個information讓他可以把這兩個東西連起來,
知道那個錢是被誰從誰的戶口拿走的這種觀念叫fair blind
signature. 所謂的fair blind
signature就是說他在一般運作上跟blind signature是一樣的,
但是有必要的時候呢, 就有一個公證第三者, 就像法官一樣,
他可以把犯罪的事告發出來, 把information review,這是在觀念上很簡單,
但是在設計protocol上有點困難, 因為多了法官這第三者,
這就是解決misuse problem, 解決unlinkability的problem.另外的話呢,
以前的貨幣系統是你領多少錢就是多少錢, 不能把他撕開來用,所以以前人家要領一百來用就領一百張一塊來用,
但這沒有效率, 這其實都是一些很複雜的數學計算,
我們就是想要有一個技術可以把錢分割來用,
當然不可以多以一錢本身價值, 這是可分割的電子貨幣的觀念,
那剛剛講到很多的觀念, 有很多觀念可以玩啦,
但是要怎樣有效user efficient的做blind signature?基本上一個典型的blind
secuture schema一定有一個message
schema，然後它需要一些random
number，所以必須要有一個random
number generate，而把一個message
blinding，你就把它乘以一個random
number，所以就如我剛才說的，我們把要投的票，彌封在一個信封裡，那你在數位上要怎麼做呢？就是把原本的intention乘以一個random
number，這樣對方就看不懂你本來寫的是什麼，而到時候，你只要把那個random
number的inverse一乘，就可以消掉，就可以還原，那就當然有所謂的簽章的函數，user送一個message給Signer
sign，sign了以後，就是一個secuture的東西，那當然也有檢驗的function，這個檢驗的function
是public每一個人都可以做的。也就是任何人拿到這個東西都可以驗證你這個東西是true
或是false，那驗證的形式是如何呢？formula
就是跟據你的protocol怎麼設計來決定，所以設計protocol最重要的就是怎麼設計檢驗函式，而且是security大家都可以很快的來驗證是個有效的簽章。當然，兩個重要的動作就是blinding跟unblinking，而有一個很重要的特性，從式子中看，希望得到message
M 的簽章，但這幾個function必須要滿足幾個特性，你送出去不希望別人知道M
是什麼東西，所以把它blind起來，所以signer是站在blind
message上面，然而把blind
的簽章還給你，你再利用unblind
的函數U來還原，這是典型的
blind secuture schema基本上密碼學，都是可以解開的，只是可能要幾千年，所以我們就認為是解不開的，所以在實際上有足夠的機器及運算能力，還是解的開。而密碼跟安全的技術基本上有三個問題，第一個是因式分解，就是給你一個數字，是兩個很大的質數乘積，另外一個就是disscript
log。但是我們今天這一系列主要是另外一個開根號的問題，我給你一個數字，你要求出它的開根號，這是一個很困難的問題。接下來讓我們看一下我們設計出來的第一個blind
secuture schema，message
M就選一個random
number R，USER然後做blinding的動作，然後做signing的動作，signing是sign在blind
message上面，sign出來的結果叫T，就把T回傳給USER，USER就apply
unblind的function，然後把你要的secuture淬取出來，然後最後我們只要把secuture提供給其它的人，但是有時候我們需要從這個schema
recovery回來，有些schema可以從secuture裡面，把M
recovery回來，如果有這樣特性，我們叫做具有message
recovery 特性。有這個特性的話，在傳這個message可以少一半的量，我們是第一個based
on QR的技術，事實上就是開平方根的東西，基本上這裡有個符號同學們可能不知道，ZN*，是指比N小的正整數而且跟N互質的正整數的集合，ZN就是比N小的正整數，這邊假設Y=X
的平方，Y就是QR，那反過來講，X就是Y的平方根。一般來說，假設這些都是module
N的一個算術，N=P1*P2，你只知道N，不知道P1P2，就像剛剛說的開根號一樣很難，如果你知道P1P2是什麼的話，這問題就很容易做了。而這些其是都是based
on這些式子，所以我們看一下我們的protocol，其實這個圖跟我剛剛給你們看的一些典型，事實上是很像的，基本上我們有message
M，那message
M我們要把它做一個blinding，那blinding我們要選兩個random
number，然後寫R是代表random
number的意思，這個符號代表我們在這個裡面選一個random
number，那ZN就代表比N小的正整數而且跟N互質的正整數的集合。那基本上我用的blinding
function就是這樣子，那為何如此都是有它的原因。事實上是防止某一些的abdate，防止redundancy，防止一些request
attack，所以你要把它embed在我們的formula裡面，所以基本上blinding的方程式把它弄成這樣子，那這裡我們又選了另外一個random
number，那這些的random
number其實又要滿足某些特性，事實上理論可以證明QR剛好是一半一半，就是你在一個ZN*裡面，是non
QR跟QR剛好是一半一半，所以你選到的機會是一半一半，那這機率就很大了，所以很容易選到這樣的random
number把它送回來，為什麼要有這一步呢？假如沒有做這一步的話，通常我給你一個簽章，拿另一個message讓你簽，那你簽章是固定的，那攻擊者可以借著這個來做一些破解的分析，而我們這一步就是讓簽章出來的結果不是固定的，只要透過某個式子就可以了，就是我現在簽跟等一下簽結果是不一樣的。那做出來簽章在還給他，在這裡有一個很重要的事情是，我做出來的簽章給他知道的只有這個T，T次方等於這個東西，但是我給他這個東西其實不太容易把它算出來，因為我說過開根靠不容易算，但signor可以很容易的算，因為N=P*Q，所以它可以開根號，但另外一邊沒辦法開根號，那收到這個message的時候，就可以把這個secuture淬取出來，就是這裡有CMS，我們最後導出來的式子是這個樣子，所以你只要把blind
secuture給人家，人家去驗證這個式子，如果正確就表示你是合法取得的blind
secuture。接下來我們看一下到底會有什麼結果。因為前面那些U跟V，都是random選出來的，兩方都是random選出來的，因此這個secuture是不容易偽造出來的。因為這個東西是random選出來的，所以只有USER知道，像R、V都是random選出來的。到時再把這些丟給signor
去sign，因為它是random選出來的,
所以signor
無法control這個東西，所以無法blinding起來，Unvisualable所以無法repair
和apply，它是利用hash
function ，這裡我們稱為one
way 的hash
function，我們從正向算過去很容易，但是反向卻很困難，而我們剛才那個H就必須是hash
function，那到底多有效率，我們回頭來看，做inverse
或指數運算很困難，而我們這個系統就是在public
key的系統，一般而言做inverse
或指數運算大約是乘法的好幾倍時間，以一個key長１０００bit
的運算，做inverse
或指數運算約是乘法的一千倍，差不多是ｂｉｔ長度的倍數，和其中０與１的個數有關。那你可以發現在user邊只做加法和乘法，這邊apply就是先減少user的計算量，接下來就看下面這個表，我們當時就是靠這個表發表上去。另一邊是其他人的各種方法，但最主要你去看，都多多少少要做些指數的運算或是inverse的運算，但是以一個指數運算而言，我們現再一個一千個bit的key，一個指數運算，就相當於一千個乘法的運算，而我們在user這一邊省掉的是99%以上，有的甚至省到99.99%，但注意但在server上，以一個transaction來說，它會快多少，sever上沒有增加多少，也沒有減少多少，所以只有client上省到機忽零，所以整個交易，你快頂多快到一倍，client省99%，但不是能省100倍，而接下來我要說的是Parcail
schema，在blind
secture 上signor要在加上一些value，像是有效期限，假設我是一家銀行，我要發行五種期限的錢，假設有半年期，一年期等，兒這五種user可以選，那user可以選1、2、3、4所以由user來選期限是合理的，那令一邊在驗證是不是我允許的東西，所以a是由user來選由銀行來驗證是合理的，那我們的protocol這樣做事實上跟由user來指定是一樣的，那這裡還是做一些亂數的動作，所以出來的時候就多了一個a在你的secture裡面，所謂電腦本身的應用,包括音樂,例如80年代看錄影帶,90年代看vcd
LD 21世紀看DVD,(雜音中)…..然跟裏面有幾個0幾個1有關係,好,你不管說那inverse的計算,或者說只要一些複雜的運算,開根號或是什麼,你在user這邊做什麼事情,你只做加法和乘法,我要讓user減少他的計算量,基本上做這些是非常非常多啦,基本上Base
要用RSA做是比較困難一點,重點是下面這個表,其實我們那個時候發表論文,在transcation方面,主要是這個表發表上去的,你去看的話,這是比較複雜的運算,其實14個,我們只做10個乘法而已,ㄚ~~這是其他人些方法,那你去看的話呢?
多多少少要做一些指數運算或者是說他有時候還要做一些inverse,基本上指數運算如果是1000個bit話,以現在的科技而言,就相當要做1000個乘法這麼多量,我們在user這邊省掉90%以上,但是你要注意到這一點,這是user這邊省掉90%以上,假設你去看一個transcation,他會快多少?Server那邊所花的時間,基本是差不多,沒有增加啦,也沒有減少多少,所以妳快不會快超過一倍,基本上我們這些觀念從他們那邊過來的,這是不可諱言的,但是我們的Des不一樣,他是用在RSA上面的,基本上他也是一個跑不掉的弱點,我們是有做到這一些功能,Performance這邊來講的話,跟我們不能比,所以我們還是得一樣的結果,那這裡的話,我們總共做了幾個乘法和幾個加法.Ok….為了解決某些問題,既然你要有個公正的第三者過來,基本上如果你要flag
signature,你就跟他講說你要flag
signature,參數必須他來選,所以他選了一些參數給你,才去做一些動作,當然你要有message
m 嘛,基本上你向第三者給你的參數,做了一些事情,真正發生問題的時候,這個傢伙就要跳出來,這些東西可把這些放出來,就可以去追蹤來源,我們能做的事情就是說,你雖然在一個匿名的系統,我們可以把他trace出來,我們儘量利用protocol的設計技巧把server和user所做的事情儘量丟給server做,且又不會增加server的太多負擔,好…..我們來看一下這些簡單的觀念在一個e-mail系統,那你當然就利用,就可以去領一些cash回來,那商家怎麼去check有一個valued的signnature呢?利用hash
function ,在密碼學中,對稱的密碼學就用Des那個東西,基本上比RSA快,基本上,提出一套E-Cash系統必須可以分割的,假設有很多個hash
function,其實應用可以同樣一個hash
就可以了,為了好講起見,我們定義一個符號,是這個樣子,基本上這一個range表示HiàHi+1到m這個上面m,我在抽回來講蓋鋼印的例子好了,今天假設要去領100塊,就是一張蓋100塊,今天我可以拿一百張紙可以複寫的,把一百張紙放在一個信封裡面,讓你去蓋鋼印,那當然說越上面的越清楚,越下面越不清楚,那假設我們可以分辨這個清析度,這是在第一張和第一百張,假設我可以分割啦,數學上一定有辦法做到這一點,那實際上這當然不容易implement,只是我舉一個例子讓你容易了解,那今天我就假設,一個東西讓你去鋼印,那裡就有一百張,那一百張的話,這是第一張,第二張….一直到第一百張,那今天我要發的話,你可以從底下倒數回來,如果妳要花五塊錢,就拿倒數第五張給人家,你要再花八塊錢,你要拿那一張呢?你不是拿倒數第八張喔,你是拿倒數第五加八張,所以是倒數第十三張,這表示說,你前面花五塊錢,所以後面5張都不能用,你要再花八塊錢,再一次拿掉八張,你拿倒數第八張,給人家就可以了,是這種觀念,那實際上去做當然不是這個樣子啦,我們就是給他一個數字,一個數字給給他hashu
一百次,花五塊錢,hash
95次的東西給你,95代表五塊,基本上你把E-cash
分成好多個,但重點的話就是說你要去花掉的錢,加起來和一樣,有一樣東西叫EI,去判斷錢是否夠否?以及UpDate…,通常我們會有一個情況可能是說,你可能是說,有一個問題要解決一個problem
p,你可能公布在網路上,誰能夠解決這種問題,我要給他好多好多的錢,今天一旦公布問題,如果你會解,把你的resolution給他,他把錢給你,以這樣一個流程而言,會有怎樣的問題,有兩個問題,他可以賴帳,他可能身份曝光,當然基本上要有一個銀行,有數位貨幣的服務,另一個重要的就是仲裁者,避免賴帳,不能球員兼裁判,一開始當事者出一個problem,你也可以知道第一個解決的人,他看到第一個對的答案,而且可以給當事者,這是不可以賴帳的,怎樣給錢,跟銀行領一個E-Cash出來,在skin中,兩者的information是不能互相
trace的…….有時候,你領旅行支票,要有兩個簽名欄,要兩個match才行,如果你的E-Cash存在磁片中,如果掉了,假設你要領2000塊,,可以加上一些特定的information,加強整個安全機制,所以拿到也沒用,我大概跟你們講我們做那些事情,電子投票的概念,其實這裡畫一個東西,都是經過一些很複雜的運算,那你去投個票,就是說註冊,然後領票,然後投票,再來記票,記票以後要驗票,驗票如果有問題,你要抗議,等等這些動作,基本上registeration是很複雜,我們要怎樣去做一個改進呢?其實我們想法是,一張票可以重複使用,但不是重複投票,我們認證一次,可以去投好幾種的投票,利用開根號的問題,所以我們做了這個東西可以重複投票,如果在小型選舉中,如何解決重複投票的問題利用一個hash的方式,在一個電子投票的致命問題是投票者可以trace到,我們可以利用某些方式避開這種問題,那現在講到像人家在做data mining, data mining覺得是在破壞隱私的東西,喔~~在 data mining 就是要知道你要幹什麼? 你在那裡養一個小老婆 ,比如說:小老婆生日時,你要不要送個蛋糕,反正..ok..
|