Recently, Benhamouda et al. [1] formulate leakage from the n shares \((X_1,X_2,\ldots ,X_n)\) of a (t, n)-threshold scheme as \(\boldsymbol{Y}=(Y_1,Y_2,\ldots ,Y_n)\) , where \(Y_j = \tau _j(X_j),\,j=1,2,\ldots ,n\) and \(\tau _j,\,j=1,2,\ldots ,n\) are deterministic functions with the range \(\{0,1,\ldots ,L-1\}\) and evaluate the maximum \(V_n^*\) of the total variational distance between the conditional distributions \(P_{\boldsymbol{Y}|S}(\,\cdot \,|s)\) and \(P_{\boldsymbol{Y}|S}(\,\cdot \,|s')\) , where the maximum is taken with respect to \(s, s'\) and \(\tau _j,\,j=1,2,\ldots ,n\) . In this paper, we propose a new method to evaluate \(V_n^*\) more precisely than the existing methods for the (n, n)-threshold scheme over a finite field \(\mathbb {F}_p\) . For the case of \(L=2\) , we show that \(V_n^*\) converges to zero of order \(O((p \sin \frac{\pi }{2p})^{-n})\) . We also characterize the class of leakage functions that attain \(V_n^*\) . For the case of \(L\ge 3\) , we succeed in obtaining an upper bound of \(V_n^*\) by using the theory of majorization. The order of the obtained upper bound is smaller than the upper bound in [1] and is proved to be tight under a certain assumption.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

New Tight Bounds on the Local Leakage Resilience of the Additive (n, n)-Threshold Scheme Determined by the Eigenvalues of Circulant Matrices

  • Hiroki Koga,
  • Hiroto Abe

摘要

Recently, Benhamouda et al. [1] formulate leakage from the n shares \((X_1,X_2,\ldots ,X_n)\) of a (t, n)-threshold scheme as \(\boldsymbol{Y}=(Y_1,Y_2,\ldots ,Y_n)\) , where \(Y_j = \tau _j(X_j),\,j=1,2,\ldots ,n\) and \(\tau _j,\,j=1,2,\ldots ,n\) are deterministic functions with the range \(\{0,1,\ldots ,L-1\}\) and evaluate the maximum \(V_n^*\) of the total variational distance between the conditional distributions \(P_{\boldsymbol{Y}|S}(\,\cdot \,|s)\) and \(P_{\boldsymbol{Y}|S}(\,\cdot \,|s')\) , where the maximum is taken with respect to \(s, s'\) and \(\tau _j,\,j=1,2,\ldots ,n\) . In this paper, we propose a new method to evaluate \(V_n^*\) more precisely than the existing methods for the (n, n)-threshold scheme over a finite field \(\mathbb {F}_p\) . For the case of \(L=2\) , we show that \(V_n^*\) converges to zero of order \(O((p \sin \frac{\pi }{2p})^{-n})\) . We also characterize the class of leakage functions that attain \(V_n^*\) . For the case of \(L\ge 3\) , we succeed in obtaining an upper bound of \(V_n^*\) by using the theory of majorization. The order of the obtained upper bound is smaller than the upper bound in [1] and is proved to be tight under a certain assumption.