期末考說明
valeria wang
同時出席，就可以打開密室。請問：
(a) 最少需要幾把鎖?
(b) 最少需要幾把鑰匙?
[提示：請畫出解題的0/1矩陣，並說明0與1在(a)(b)中分別代表的意義。]
這題就是隨堂測驗"七"，題目都沒改，就是( 4, 6 )，
可是幾乎所有同學都沒說明 0與1的代表意義，
所以，只要你有寫出正確矩陣與正確的鎖及鑰匙數目，
我就都給15分~~
2. 擬分享一數字 s 給 n 位參與者，
(a) (5%) 何謂 (k, n) 機密分享機制？
有n位參予者，分享機密數字s，只要有k位或k位以上參與者到齊，即可得知機密訊息
內容。
(b) (10%) 請設計兩種 (n, n) 機密分享機制；
講義: 0401_Trivial_Secret_Sharing_XOR+Add.pdf 即有兩種作法，
1. XOR
2. Addition and subtraction
(c) (10%) 請解釋 Adi Shamir 的 (k, n) 機密分享機制；
講義: Secret_Sharing_Introduction.pdf 第19頁
(d) (10%) 請解釋George Blakley 的 (k, n) 機密分享機制。
講義: Secret_Sharing_Introduction.pdf 第17頁
(a)是基本分，沒想到還是有同學空白，實在是太浪費了....
(c)(d)許多同學是照抄英文的，說實話，抄完後到底有沒有了解呢??
用自己語言寫出答案的同學，我給到10分，
抄英文的同學，5~8分不等。
3. (10%) 擬以 (k, n) 門檻式結構分享一張大小為 h × m 的機密影像 S 給 n 位參與者：
(a) 用 Shamir 的方法，其分享影像的大小為何？ h × m
(b) 用 Thien-Lin 的方法，其分享影像的大小為何？ h × m / k
這題是隨堂測驗"九"，一模一樣都沒更動，
怎麼同學還是空白或寫錯咧?????
4. (10%) 考慮一個 4 位參與者的集合 P = {1, 2, 3, 4} 和在P 上的存取結構 (access structure)
Γ = (ΓQual, ΓForb)；而 ΓQual = {{1, 2}, {1, 3}, {2, 3}, {1, 2, 3}, {2,
4}, {1, 2, 4}, {3, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}}。
(a) 請找出最小允許集合 (minimal qualified set) Γ0；
Γ0是找出ΓQual的subset，所以 Γ0 = {{1, 2}, {1, 3}, {2, 3}, {2, 4}, {3,
4}}。
(b) 請找出最大禁止集合 (maximal forbidden set) Zm。
Zm就是找出ΓForb的powerset，ΓForb={{1}, {2}, {3}, {4}, {1,4}}，
所以ZM = {{2}, {3}, {1, 4}}。
5. (10%) 同上；而P = {1, 2, 3, 4, 5} 且 ΓQual = {{1, 2},{1, 2, 3}, {1, 4},
{1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}, {2, 5}, {1, 2, 5}, {2,
3, 5}, {1, 2, 3, 5}, {1, 4, 5}, {2, 4, 5}, {1, 2, 4, 5}, {3, 4, 5},
{1, 3, 4, 5}, {2, 3, 4, 5}, {1, 2, 3, 4, 5}}。
(a) 請找出最小允許集合 Γ0；
Γ0 = {{1, 2}, {1, 4}, {2, 3, 4}, {2, 5}, {3, 4, 5}}。
(b) 請找出最大禁止集合 Zm。
ZM = {{2, 3}, {2, 4}, {3, 4}, {1, 3, 5}, {4, 5}}。
6. (20%) 請設計符合下列要求的視覺密碼基本矩陣 (B0, B1)︰
(a) (3, 3)；
(b) (5, 5)；
(c) P = {1, 2, 3, 4, 5, 6} 且 Γ0 = {{1, 2, 3, 4, 5, 6}}
(d) P = {1, 2, 3} 且 Γ0 = {{1, 2}, {2, 3}} 。
課堂上有教過(3, 3)矩陣，許多同學都知道，
B0矩陣中每一行含有偶數個1，B1矩陣中每一行含有奇數個1，
(a)所以可得知，B0矩陣含有C(3,0)+C(3,2)的組合，
B1矩陣含有C(3,1)+C(3,3)的組合。
矩陣大小為3 X 4。
0 0 1 1 1 0 0 1
B0 = 0 1 0 1 B1 = 1 0 1 0
0 1 1 0 1 1 0 0
(b)同理可推，(5, 5)中B0矩陣含有C(5,0)+C(5,2)+C(5,4)的組合，
B1矩陣含有C(5,1)+C(5,3)+C(5,5)的組合。
矩陣大小為5 X 16。
0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0
0 1 0 0 0 1 1 1 0 0 0 1 1 1 0 1
B0 = 0 0 1 0 0 1 0 0 1 1 0 1 1 0 1 1
0 0 0 1 0 0 1 0 1 0 1 1 0 1 1 1
0 0 0 0 1 0 0 1 0 1 1 0 1 1 1 1
0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 1
0 0 0 1 0 1 1 1 0 0 0 1 1 1 0 1
B1 = 0 0 1 0 0 1 0 0 1 1 0 1 1 0 1 1
0 1 0 0 0 0 1 0 1 0 1 1 0 1 1 1
1 0 0 0 0 0 0 1 0 1 1 0 1 1 1 1
(c) 由Γ0 可推出是(6,6)，
所以同理， B0矩陣含有C(6,0)+C(6,2)+C(6,4)+C(6,6)的組合，
B1矩陣含有C(6,1)+C(6,3)+C(6,5)的組合。
矩陣大小為6 X 32。
(d) Γ0 = {{1, 2}, {2, 3}} ，所以ΓForb = {{1}, {2}, {3}, {1, 3}}，ΓQual =
{{1, 2}, {2, 3}, {1, 2, 3}}
題目並沒有要求矩陣大小，所以你想變多大都可以，
因此只要達到題目條件即可。
掌握兩項要訣，一是不論在B0及B1中的單張share，都要有相同數量的黑點與白點；
二是，在ΓQual集合裡，疊合後的B0及B1(不論疊幾張)，B0的黑點個數一定會比B1少，
一定比較少，才能看出黑白差異喔~~
以下列舉:
1 0 0 0 1 0 0 0
B0 = 1 0 1 0 B1 = 0 1 1 0
0 0 1 0 0 0 0 1
{1, 2}及{2, 3}相疊，B0為2黑2白，B1為3黑1白，對比不一樣了，自然能看出黑白機密；
{1, 2, 3}相疊時，B0為2黑2白，B1為全黑，當然也能區分出黑白；
{1, 3}相疊，B0與B1皆為2黑2白，無法區分，也就不能得知機密影像；
就單張share來看，假設分別是甲乙丙三位參與者，雖然乙拿到share的B0與B1是由2黑2白組
成，不同於甲丙的B0與B1(1黑3白)，但因他們的黑白個數相同，自然不會透露出機密，只是乙
的share會比甲丙看起來來的深一些而已。
所以這四小題的矩陣，你想怎麼長都可以，只要條件達到，我就給分，
(b)少部分同學有解出來；(c)班上只有一位陳同學答對，請大家鼓鼓掌；
(d)很可惜沒有同學解出，暑假時可以試著自己解看看喔~~