0


安全多方计算之七:门限密码系统

门限密码系统

1. 定义

门限密码系统由分布式密钥生成算法、加密算法、门限解密算法三部分构成,定义如下:

(1)分布式密钥生成:这是一个由参与者共同生成公钥

  1. y
  2. y
  3. y的协议,协议运行结束后,每个参与者将获得一个关于私钥
  4. x
  5. x
  6. x的碎片、对应于该碎片的公钥密钥
  7. y
  8. i
  9. y_i
  10. yi​,以及与私钥
  11. x
  12. x
  13. x相对应的公钥
  14. y
  15. y
  16. y

(2)加密算法:该算法的输入为公钥

  1. y
  2. y
  3. y和待加密的消息
  4. m
  5. m
  6. m,其输出为在公钥
  7. y
  8. y
  9. y下明文
  10. m
  11. m
  12. m对应的密文
  13. c
  14. c
  15. c

(3)门限解密: 这是一个由任意

  1. t
  2. t
  3. t个参与者
  4. P
  5. i
  6. 1
  7. ,
  8. P
  9. i
  10. 2
  11. ,
  12. ,
  13. P
  14. i
  15. t
  16. P_{i_1^{\prime}}, P_{i_2^{\prime}}, \ldots, P_{i_{t}}
  17. Pi1′​​,Pi2′​​,…,Pit​​ 运行的协议, 对于给定输人密文
  18. c
  19. c
  20. c
  21. t
  22. t
  23. t个公开验证密钥
  24. h
  25. i
  26. 1
  27. ,
  28. h
  29. i
  30. 2
  31. ,
  32. ,
  33. h
  34. i
  35. t
  36. h_{i_1^{\prime}},h_{i_2^{\prime}}, \ldots, h_{i_{t}}
  37. hi1′​​,hi2′​​,…,hit​​ 以及
  38. t
  39. t
  40. t 个碎片
  41. x
  42. i
  43. 1
  44. x
  45. i
  46. 2
  47. ,
  48. ,
  49. x
  50. i
  51. t
  52. x_{i_1^{\prime}} x_{i_2^{\prime}}, \ldots, x_{i_{t}}
  53. xi1′​​xi2′​​,…,xit​​, 协议运行结束后将输出 密文
  54. c
  55. c
  56. c 和对应的明文
  57. m
  58. m
  59. m

2. 分布式ElGamal加密

系统参数:

  1. p
  2. q
  3. pq
  4. pq是大素数,
  5. q
  6. /
  7. p
  8. 1
  9. q / p-1
  10. q/p1, 满足
  11. Z
  12. p
  13. Z_{p}
  14. Zp​中离散对数问题是难解的,
  15. g
  16. g
  17. g
  18. Z
  19. p
  20. Z_{p}^{*}
  21. Zp∗​的本原元,
  22. M
  23. M
  24. M 为明文消息。
  25. n
  26. n
  27. n个参与者
  28. P
  29. 1
  30. ,
  31. P
  32. 2
  33. ,
  34. ,
  35. P
  36. n
  37. P_{1}, P_{2}, \ldots, P_{n}
  38. P1​,P2​,…,Pn​分别选取一个随机数
  39. x
  40. i
  41. Z
  42. p
  43. ,
  44. i
  45. =
  46. 1
  47. ,
  48. 2
  49. ,
  50. ,
  51. n
  52. x_{i} \in Z_{p},i=1,2, \ldots, n
  53. xi​∈Zp​,i=1,2,…,n 计算
  54. y
  55. i
  56. =
  57. g
  58. x
  59. i
  60. m
  61. o
  62. d
  63. p
  64. y_{i}= g^{x_{i}} \bmod p
  65. yi​=gximodp并公布。

私钥:

  1. x
  2. =
  3. i
  4. =
  5. 1
  6. n
  7. x
  8. i
  9. m
  10. o
  11. d
  12. p
  13. x=\sum_{i=1}^{n} x_{i} \bmod p
  14. x=i=1nximodp**公钥**:
  15. y
  16. =
  17. i
  18. =
  19. 1
  20. n
  21. y
  22. i
  23. m
  24. o
  25. d
  26. p
  27. =
  28. g
  29. i
  30. =
  31. 1
  32. n
  33. x
  34. i
  35. m
  36. o
  37. d
  38. p
  39. =
  40. g
  41. x
  42. m
  43. o
  44. d
  45. p
  46. y=\prod_{i=1}^{n} y_{i} \bmod p=g^{\sum_{i=1}^{n} x_{i}} \bmod p = g^x \bmod p
  47. y=i=1nyimodp=gi=1nximodp=gxmodp

加密: 选取随机数

  1. r
  2. Z
  3. p
  4. r \in Z_{p}
  5. rZp​, 计算
  6. E
  7. (
  8. M
  9. )
  10. =
  11. (
  12. α
  13. ,
  14. β
  15. )
  16. =
  17. (
  18. g
  19. r
  20. m
  21. o
  22. d
  23. p
  24. ,
  25. y
  26. r
  27. M
  28. m
  29. o
  30. d
  31. p
  32. )
  33. E(M)=(\alpha, \beta) = (g^{r} \bmod p, y^{r} M \bmod p)
  34. E(M)=(α,β)=(grmodp,yrMmodp)**解密**:
  35. n
  36. n
  37. n个参与者首先分别计算
  38. α
  39. x
  40. i
  41. m
  42. o
  43. d
  44. p
  45. \alpha^{x_{i}}\bmod p
  46. αximodp并公布, 然后共同计算出
  47. i
  48. =
  49. 1
  50. n
  51. α
  52. x
  53. i
  54. \prod_{i=1}^{n} \alpha^{x^{i}}
  55. i=1n​αxi, 从而解出
  56. M
  57. M
  58. M:
  59. M
  60. =
  61. β
  62. i
  63. =
  64. 1
  65. n
  66. α
  67. x
  68. i
  69. m
  70. o
  71. d
  72. p
  73. =
  74. β
  75. α
  76. i
  77. =
  78. 1
  79. n
  80. x
  81. i
  82. m
  83. o
  84. d
  85. p
  86. =
  87. β
  88. α
  89. x
  90. m
  91. o
  92. d
  93. p
  94. M=\frac{\beta}{\prod_{i=1}^{n} \alpha^{x^{i}}} \bmod p =\frac{\beta}{\alpha^{\sum_{i=1}^{n} x^{i}}} \bmod p =\frac{\beta}{\alpha^x} \bmod p
  95. M=∏i=1n​αxiβ​modp=α∑i=1nxiβ​modpxβ​modp

推广

令消息

  1. M
  2. =
  3. M
  4. 1
  5. M
  6. 2
  7. M
  8. n
  9. M=M_{1} M_{2} \cdots M_{n}
  10. M=M1M2​⋯Mn​,
  11. n
  12. n
  13. n个参与者
  14. P
  15. 1
  16. ,
  17. P
  18. 2
  19. ,
  20. ,
  21. P
  22. n
  23. P_{1}, P_{2}, \ldots, P_{n}
  24. P1​,P2​,…,Pn​分别对消息
  25. M
  26. 1
  27. ,
  28. M
  29. 2
  30. ,
  31. ,
  32. M
  33. n
  34. M_{1}, M_{2}, \ldots, M_{n}
  35. M1​,M2​,…,Mn 加密。

系统参数:

  1. p
  2. q
  3. pq
  4. pq是大素数,
  5. q
  6. /
  7. p
  8. 1
  9. q / p-1
  10. q/p1, 满足
  11. Z
  12. p
  13. Z_{p}
  14. Zp​中离散对数问题是难解的,
  15. g
  16. g
  17. g
  18. Z
  19. p
  20. Z_{p}^{*}
  21. Zp∗​的本原元,
  22. M
  23. M
  24. M 为明文消息。

利用分布式 ElGamal 加密方式产生私钥/公钥对:

  1. n
  2. n
  3. n个参与者分别选取一个随机数
  4. x
  5. i
  6. Z
  7. p
  8. ,
  9. i
  10. =
  11. 1
  12. ,
  13. 2
  14. ,
  15. ,
  16. n
  17. x_{i}\in Z_{p},i=1,2, \ldots,n
  18. xi​∈Zp​,i=1,2,…,n 计算
  19. y
  20. i
  21. =
  22. g
  23. x
  24. i
  25. m
  26. o
  27. d
  28. p
  29. y_{i}=g^{x_{i}} \bmod p
  30. yi​=gximodp 并公布。

私钥:

  1. x
  2. =
  3. i
  4. =
  5. 1
  6. n
  7. x
  8. i
  9. m
  10. o
  11. d
  12. p
  13. x=\sum_{i=1}^{n} x_{i} \bmod p
  14. x=i=1nximodp**公钥**:
  15. y
  16. =
  17. i
  18. =
  19. 1
  20. n
  21. y
  22. i
  23. m
  24. o
  25. d
  26. p
  27. =
  28. g
  29. i
  30. =
  31. 1
  32. n
  33. x
  34. i
  35. m
  36. o
  37. d
  38. p
  39. =
  40. g
  41. x
  42. m
  43. o
  44. d
  45. p
  46. y=\prod_{i=1}^{n} y_{i} \bmod p=g^{\sum_{i=1}^{n} x_{i}} \bmod p = g^x \bmod p
  47. y=i=1nyimodp=gi=1nximodp=gxmodp

加密:

  1. n
  2. n
  3. n个参与者分别选取随机数
  4. r
  5. 1
  6. ,
  7. r
  8. 2
  9. ,
  10. ,
  11. r
  12. n
  13. Z
  14. p
  15. r_{1}, r_{2}, \ldots, r_{n} \in Z_{p}
  16. r1​,r2​,…,rn​∈Zp​, 对消息
  17. M
  18. i
  19. M_{i}
  20. Mi 加密
  21. E
  22. (
  23. M
  24. i
  25. )
  26. =
  27. (
  28. α
  29. i
  30. ,
  31. β
  32. i
  33. )
  34. =
  35. (
  36. g
  37. r
  38. i
  39. m
  40. o
  41. d
  42. p
  43. ,
  44. y
  45. r
  46. i
  47. M
  48. i
  49. m
  50. o
  51. d
  52. p
  53. )
  54. E\left(M_{i}\right)= \left(\alpha_i ,\beta_i\right) =(g^{r_{i}} \bmod p, y^{r_{i}} M_{i} \bmod p)
  55. E(Mi​)=(αi​,βi​)=(grimodp,yriMimodp)

根据同态性计算

  1. E
  2. (
  3. M
  4. )
  5. =
  6. E
  7. (
  8. M
  9. 1
  10. M
  11. 2
  12. M
  13. n
  14. )
  15. =
  16. E
  17. (
  18. M
  19. 1
  20. )
  21. E
  22. (
  23. M
  24. 2
  25. )
  26. E
  27. (
  28. M
  29. n
  30. )
  31. =
  32. (
  33. α
  34. ,
  35. β
  36. )
  37. E(M)=E\left(M_{1} M_{2} \cdots M_{n}\right)= E(M_{1})E(M_{2}) \cdots E(M_{n})= (\alpha, \beta)
  38. E(M)=E(M1M2​⋯Mn​)=E(M1​)E(M2​)⋯E(Mn​)=(α,β)其中,
  39. α
  40. =
  41. i
  42. =
  43. 1
  44. n
  45. α
  46. i
  47. =
  48. g
  49. i
  50. =
  51. 1
  52. n
  53. r
  54. i
  55. m
  56. o
  57. d
  58. p
  59. ,
  60. β
  61. =
  62. i
  63. =
  64. 1
  65. n
  66. β
  67. i
  68. =
  69. y
  70. i
  71. =
  72. 1
  73. n
  74. r
  75. i
  76. M
  77. m
  78. o
  79. d
  80. p
  81. \alpha=\prod_{i=1}^{n} \alpha_{i}=g^{\sum_{i=1}^{n} r_{i}} \bmod p,\beta = \prod_{i=1}^{n} \beta_{i}=y^{\sum_{i=1}^{n} r_{i}} M \bmod p
  82. α=i=1n​αi​=gi=1nrimodp,β=i=1n​βi​=yi=1nriMmodp

解密:

  1. n
  2. n
  3. n 个参与者首先分别计算
  4. α
  5. x
  6. i
  7. m
  8. o
  9. d
  10. p
  11. \alpha^{x_{i}} \bmod p
  12. αximodp 并公布, 来共同计算出
  13. i
  14. =
  15. 1
  16. n
  17. α
  18. x
  19. i
  20. \prod_{i=1}^{n} \alpha^{x_{i}}
  21. i=1n​αxi​, 从而解出
  22. M
  23. M
  24. M:
  25. M
  26. =
  27. β
  28. i
  29. =
  30. 1
  31. n
  32. α
  33. x
  34. i
  35. m
  36. o
  37. d
  38. p
  39. β
  40. α
  41. i
  42. =
  43. 1
  44. n
  45. x
  46. i
  47. m
  48. o
  49. d
  50. p
  51. =
  52. β
  53. α
  54. x
  55. m
  56. o
  57. d
  58. p
  59. \quad M=\frac{\beta}{\prod_{i=1}^{n} \alpha^{x_{i}}} \bmod p \frac{\beta}{\alpha^{\sum_{i=1}^{n} x_{i}}} \bmod p=\frac{\beta}{\alpha^x} \bmod p
  60. M=∏i=1n​αxi​β​modpα∑i=1nxi​β​modpxβ​modp

3.有可信中心的门限ElGamal密码

(1) 分布式密钥生成

可信中心产生一个密钥

  1. x
  2. x
  3. x, 对应的公钥为
  4. y
  5. =
  6. g
  7. x
  8. m
  9. o
  10. d
  11. p
  12. y=g^{x} \bmod p
  13. y=gxmodp,使用
  14. (
  15. t
  16. ,
  17. n
  18. )
  19. (t, n)
  20. (t,n) 门限方案在协议参与者中分享私钥
  21. x
  22. x
  23. x : 选择随机多项式
  24. f
  25. (
  26. u
  27. )
  28. =
  29. a
  30. t
  31. 1
  32. u
  33. t
  34. 1
  35. +
  36. +
  37. a
  38. 2
  39. u
  40. 2
  41. +
  42. a
  43. 1
  44. u
  45. +
  46. a
  47. 0
  48. G
  49. F
  50. (
  51. q
  52. )
  53. [
  54. u
  55. ]
  56. f(u)=a_{t-1} u^{t-1}+\ldots+a_{2} u^{2}+ a_{1} u+a_{0} \in G F(q)[u]
  57. f(u)=at1ut1+…+a2u2+a1u+a0​∈GF(q)[u]
  58. P
  59. i
  60. P_{i}
  61. Pi 得到
  62. x
  63. i
  64. =
  65. f
  66. (
  67. u
  68. i
  69. )
  70. ,
  71. i
  72. =
  73. 1
  74. ,
  75. 2
  76. ,
  77. ,
  78. n
  79. x_{i}=f\left(u_{i}\right), i=1,2, \ldots, n
  80. xi​=f(ui​),i=1,2,…,n

(2) 加密

选取随机数

  1. k
  2. Z
  3. p
  4. k \in Z_{p}
  5. kZp​计算:
  6. E
  7. (
  8. M
  9. )
  10. =
  11. (
  12. α
  13. ,
  14. β
  15. )
  16. =
  17. (
  18. g
  19. k
  20. m
  21. o
  22. d
  23. p
  24. ,
  25. y
  26. k
  27. M
  28. m
  29. o
  30. d
  31. p
  32. )
  33. E(M)=(\alpha, \beta)= (g^{k} \bmod p, y^{k} M \bmod p)
  34. E(M)=(α,β)=(gkmodp,ykMmodp)

(3) 解密

  1. P
  2. i
  3. P_{i}
  4. Pi 计算
  5. α
  6. i
  7. =
  8. α
  9. x
  10. i
  11. \alpha_{i}=\alpha^{x_{i}}
  12. αi​=αxi​并公布, 同时公布一个零知识证明以证明其计算的正确性;

每个协议参与者从公布的计算结果中选择

  1. t
  2. t
  3. t
  4. α
  5. i
  6. 1
  7. ,
  8. α
  9. i
  10. 2
  11. ,
  12. ,
  13. α
  14. i
  15. t
  16. \alpha_{i_1}, \alpha_{i_2}, \ldots, \alpha_{i_t}
  17. αi1​​,αi2​​,…,αit​​,
  18. M
  19. =
  20. β
  21. α
  22. x
  23. =
  24. β
  25. s
  26. =
  27. 1
  28. t
  29. α
  30. i
  31. s
  32. λ
  33. i
  34. s
  35. M=\frac{\beta}{\alpha^{x}}=\frac{\beta}{\prod_{s=1}^{t} \alpha_{i_s}^{\lambda_{i_s}}}
  36. Mxβ​=∏s=1t​αis​λis​​​β​
  37. λ
  38. i
  39. s
  40. \lambda_{i_s}
  41. λis​​ Lagrange 揷值系数, 满足
  42. x
  43. =
  44. λ
  45. i
  46. 1
  47. x
  48. i
  49. 1
  50. +
  51. +
  52. λ
  53. i
  54. t
  55. x
  56. i
  57. t
  58. x=\lambda_{i_1} x_{i_1}+\cdots+\lambda_{i_t} x_{i_t}
  59. xi1​​xi1​​+⋯+λit​​xit​​ .

有可信中的门限ElGamal密码不能算严格意义上的门限密码,存在第三方可心中,参加密钥分享的用户必须完全信任分发者,相信其不会对加密数据执行解密操作。

4. 无可信中心的门限ElGamal密码

(1)分布式密钥生成

每个参与者

  1. P
  2. i
  3. P_{i}
  4. Pi 选择择随机数
  5. x
  6. i
  7. x_{i}
  8. xi 作为私钥, 计算
  9. y
  10. i
  11. =
  12. g
  13. x
  14. i
  15. m
  16. o
  17. d
  18. p
  19. y_{i}=g^{x_{i}} \bmod p
  20. yi​=gximodp, 并公布;

每个参与者收到广播的值后, 计算公钥:

  1. y
  2. =
  3. i
  4. =
  5. 1
  6. n
  7. y
  8. i
  9. m
  10. o
  11. d
  12. p
  13. =
  14. g
  15. i
  16. =
  17. 1
  18. n
  19. x
  20. i
  21. m
  22. o
  23. d
  24. p
  25. =
  26. g
  27. x
  28. m
  29. o
  30. d
  31. p
  32. y=\prod_{i=1}^{n} y_{i} \bmod p=g^{\sum_{i=1}^{n} x_{i}} \bmod p = g^x \bmod p
  33. y=i=1nyimodp=gi=1nximodp=gxmodp每个参与者
  34. P
  35. i
  36. P_{i}
  37. Pi​以秘密分发者身份执行 Feldman VSS 方案,
  38. P
  39. 1
  40. ,
  41. P
  42. 2
  43. ,
  44. ,
  45. P
  46. n
  47. P_{1}, P_{2}, \ldots, P_{n}
  48. P1​,P2​,…,Pn 之间分享秘密
  49. x
  50. i
  51. x_{i}
  52. xi : 选择
  53. t
  54. 1
  55. t-1
  56. t1 次随机多项式,
  57. f
  58. i
  59. (
  60. u
  61. )
  62. =
  63. a
  64. i
  65. ,
  66. t
  67. 1
  68. u
  69. t
  70. 1
  71. +
  72. +
  73. a
  74. i
  75. 2
  76. u
  77. 2
  78. +
  79. a
  80. i
  81. 1
  82. u
  83. +
  84. a
  85. i
  86. o
  87. G
  88. F
  89. (
  90. q
  91. )
  92. [
  93. u
  94. ]
  95. f_{i}(u)=a_{i, t-1} u^{t-1}+\ldots+a_{i 2} u^{2}+a_{i 1} u+a_{i o} \in G F(q)[u]
  96. fi​(u)=ai,t1ut1+…+ai2u2+ai1u+aio​∈GF(q)[u]其中
  97. x
  98. i
  99. =
  100. a
  101. i
  102. 0
  103. =
  104. f
  105. i
  106. (
  107. 0
  108. )
  109. x_{i}=a_{i 0}=f_{i}(0)
  110. xi​=ai0​=fi​(0)
  111. P
  112. i
  113. P_{i}
  114. Pi 计算
  115. x
  116. i
  117. j
  118. =
  119. f
  120. i
  121. (
  122. u
  123. j
  124. )
  125. x_{i j}=f_{i}\left(u_{j}\right)
  126. xij​=fi​(uj​) , 发送给
  127. P
  128. j
  129. ,
  130. j
  131. =
  132. 1
  133. ,
  134. 2
  135. ,
  136. n
  137. P_{j}, j=1,2 \ldots, n
  138. Pj​,j=1,2…,n ;
  139. P
  140. j
  141. P_{j}
  142. Pj 收到其他参与者的值
  143. x
  144. i
  145. j
  146. =
  147. f
  148. i
  149. (
  150. u
  151. j
  152. )
  153. ,
  154. i
  155. =
  156. 1
  157. ,
  158. 2
  159. ,
  160. n
  161. x_{i j}=f_{i}\left(u_{j}\right), i=1,2 \ldots, n
  162. xij​=fi​(uj​),i=1,2…,n, 计算
  163. s
  164. j
  165. =
  166. i
  167. =
  168. 1
  169. n
  170. x
  171. i
  172. j
  173. =
  174. i
  175. =
  176. 1
  177. n
  178. f
  179. i
  180. (
  181. u
  182. j
  183. )
  184. s_{j}=\sum_{i=1}^{n} x_{i j}=\sum_{i=1}^{n} f_{i}\left(u_{j}\right)
  185. sj​=∑i=1nxij​=∑i=1nfi​(uj​) 作为自己最终分享得到的关于私钥
  186. x
  187. x
  188. x的秘密碎片, 其验证公钥为
  189. y
  190. j
  191. =
  192. g
  193. s
  194. j
  195. m
  196. o
  197. d
  198. p
  199. =
  200. g
  201. i
  202. =
  203. 1
  204. n
  205. x
  206. i
  207. j
  208. m
  209. o
  210. d
  211. p
  212. y_{j}=g^{s_{j}} \bmod p=g^{\sum_{i=1}^{n} x_{i j}} \bmod p
  213. yj​=gsjmodp=gi=1nxijmodp**(2) 加密**

选取随机数

  1. k
  2. Z
  3. p
  4. k \in Z_{p}
  5. kZp​,计算
  6. E
  7. (
  8. M
  9. )
  10. =
  11. (
  12. α
  13. ,
  14. β
  15. )
  16. =
  17. (
  18. g
  19. k
  20. m
  21. o
  22. d
  23. p
  24. ,
  25. y
  26. k
  27. M
  28. m
  29. o
  30. d
  31. p
  32. )
  33. E(M)=(\alpha, \beta) =(g^{k} \bmod p, y^{k} M \bmod p)
  34. E(M)=(α,β)=(gkmodp,ykMmodp)**(3) 门限解密**

每个参与者

  1. P
  2. i
  3. P_{i}
  4. Pi 计算
  5. α
  6. i
  7. =
  8. α
  9. s
  10. i
  11. \alpha_{i}=\alpha^{s_{i}}
  12. αi​=αsi , 并公布. 同时公布一个零知识证明以证明其计算的正确性;

每个协议参与者从公布的计算结果中选择

  1. t
  2. t
  3. t
  4. α
  5. i
  6. 1
  7. ,
  8. α
  9. i
  10. 2
  11. ,
  12. ,
  13. α
  14. i
  15. t
  16. \alpha_{i_1}, \alpha_{i_2}, \ldots, \alpha_{i_t}
  17. αi1​​,αi2​​,…,αit​​,
  18. M
  19. =
  20. β
  21. α
  22. x
  23. =
  24. β
  25. s
  26. =
  27. 1
  28. t
  29. α
  30. i
  31. s
  32. λ
  33. i
  34. s
  35. M=\frac{\beta}{\alpha^{x}}=\frac{\beta}{\prod_{s=1}^{t} \alpha_{i_s}^{\lambda_{i_s}}}
  36. Mxβ​=∏s=1t​αis​λis​​​β​
  37. λ
  38. i
  39. s
  40. \lambda_{i_s}
  41. λis​​ Lagrange 揷值系数, 满足
  42. x
  43. =
  44. λ
  45. i
  46. 1
  47. s
  48. i
  49. 1
  50. +
  51. +
  52. λ
  53. i
  54. t
  55. s
  56. i
  57. t
  58. x=\lambda_{i_1} s_{i_1}+\cdots+\lambda_{i_t} s_{i_t}
  59. xi1​​si1​​+⋯+λit​​sit​​ .

本文转载自: https://blog.csdn.net/apr15/article/details/128943155
版权归原作者 机器学习Zero 所有, 如有侵权,请联系我们删除。

“安全多方计算之七:门限密码系统”的评论:

还没有评论