TRANSFERENCE PRINCIPLE ON SIMULTANEOUS APPROXIMATION PROBLEMS OF $p$-ADIC NUMBERS AND CONSTRUCTION OF LATTICE BASED CRYPTOSYSTEMS (Nonlinear Analysis and Convex Analysis)

全文

(1)57. 数理解析研究所講究録第2011巻 2016年 57-63. TRANSFERENCE PRINCIPLE ON SIMULTANEOUS APPROXIMATION PROBLEMS OF. ‐ADIC NUMBERS. AND. CONSTRUCTION OF LATTICE BASED CRYPTOSYSTEMS HIROHITO. INOUE, SHOICHI. KAMADA AND KOICHIRO NAITO. GRADUATE SCHOOL OF SCIENCE AND. TECHNOLOGY,. KUMAMOTO UNIVERSITY. 1. INTRODUCTION. In this paper. we. study. the two types, named the 1st. type and the 2nd type,. of simultaneous approximations problems (SAP) of p\leftrighta‐adic numbers, constructing r ow multi‐dimensional p‐adic approximation lattices. It is known that the transfer‐ ence. principle gives the inequality. SAP of p‐‐adic numbers. (cf. [1]).. relations between the exponents given by the we estimate the l_{\infty} norms of the solutions. First. of the 1st type and the 2nd type SAP theoretically. For these approximation problems we construct basis matrices, given by mth order approximations of the p‐‐adic numbers, and we show that the unimodular transformation of these matrices. combined. by the duality relation, given by the transpose and the Using these duality relations and the LLL algorithm (cf. [8], [9], [10]), we construct the algorithm, which gives the solutions of the 2nd type SAP from the solutions of the 1st type SAP. Next we propose a new lattice based cryptosystem where we choose a n‐tuple of p‐‐adic integers as public keys and we set the 2nd type SAP solutions of these numbers as common private keys, the security of which depends on NP‐hardness are. inverse. operations of these matrices.. of SAP. (see [7]).. Our. plan of this paper is as follows. In section 2 we introduce the p‐‐adic approximation lattices and we estimate the l_{\infty} norm of p‐‐adic solutions of the 1st type SAP. In section 3 we treat the 2nd type SAP and we give the duality relation between these two types of SAP solutions. new lattice based cryptosystem as an application.. In section 4. we. propose. a. 2. p ‐ADIC LATTICE. In this section. we. introduce. p‐‐adic approximation. lattices and. investigate. si‐. multaneous rational approximations of p‐adic numbers. Let p be a fixed rational prime number and |\cdot|_{p} be the corresponding p‐adic valuation, normalized so that 2010 Mathematics. Key. words and. Subject Classification. llE95, llA55, 14\mathrm{G}50. phrases. \mathrm{P} ‐adic theory, LLL algorithm, Cryptography..

(2) 58. |p|_{p}=p^{-1}. denoted. The. .. by \mathb {Q}_{p}. .. completion of \mathb {Q} w.r.t. |\cdot|_{p} is called The strong triangle inequality. the field of. p‐‐adic numbers,. |a+b|_{p}\displaystyle \leq\max\{|a|_{p}, |b|_{p}\}, a, b\in \mathbb{Q}_{p} important and essential to construct p‐‐adic approximation lattices. The ring of p‐‐adic integers is defined by \mathbb{Z}_{p}=\{z\in \mathbb{Q}_{p} : |z|_{p}\leq 1\}. Let n\geq 1 be an integer and let $\Xi$=\{$\xi$_{1}, $\xi$_{2}, . . . , $\xi$_{n}\} be a n‐tuple of p‐‐adic integers. is most. Definition 2.1. We denote. such. for. that, inequalities. some. infinitely. by w_{n}( $\Xi$). the supremum of the real numbers w X_{j} , which goes to infinity, the. many real numbers. 0<|a_{0,j}+a_{1,j}$\xi$_{1}+\cdots+a_{n,j}$\xi$_{n}|_{p}\leq X_{j}^{-w-1},. \displaystyle \max_{0\leq i\leq n}|a_{i,j}|\leq X_{j}, have. solution in integers a_{0,j}, a_{1,j} ,. a. For. positive integer. a. .. .. ,. a_{n,j}.. define the. m we. p‐‐adic approximation. lattice. $\Gamma$_{m} by. $\Gamma$_{m}=\{(a_{0}, \mathrm{a}\mathrm{l}, \cdots, a_{n})\in \mathbb{Z}^{n+1} : |a_{0}+a_{1}$\xi$_{1}+\cdots+a_{n}$\xi$_{n}|_{p}\leq p^{-m}\}.. (2.1) When. let. .. a. p‐‐adic integer $\xi$_{i}. has the p‐adic. expansion. $\xi$_{i}=\displaystyle \sum_{k=0}^{\infty}x_{i,k}p^{k}, 0\leq x_{i,k}\leq p-1,. $\xi$_{i,m}. be the m‐th order. approximation of $\xi$_{i} defined by. $\xi$_{i,rn}=\displaystyle\sum_{k=0}^{m-1}x_{i,k}p^{k}.. (2.2) Consider the basis. \{b_{0,m}, b_{1,m}, . . . , b_{n,m}\}\subset \mathbb{Z}^{n+1}. of the lattice $\Gamma$_{m}. given by. b_{0,m}=(p^{m}, 0, \ldots, 0)^{t}, b_{1,m}=($\xi$_{1,m}, -1,0, \ldots, 0)^{t}, b_{2,m}=($\xi$_{2,m}, 0, -1,0, \ldots, 0)^{t}, \cdots , b_{n,m}=($\xi$_{n,m}, 0, \ldots , 0, -1)^{t}. In. fact,. we. have. b_{k,m}\in$\Gamma$_{m},. \forall k , since. we can. estimate. |$\xi$_{k,m}-$\xi$_{k}|_{p}\leq p^{-m}. For. B_{m}=(b_{0,m}b_{1,m}\ldots b_{n,m}). Applying. we. have. B_{m}=\left(bgin{ar y}{l p^{m}&$\xi_{mathr {l},m&$\xi_{2,m}&\cdots&$\xi_{n,m}\ 0&-1 0&\cdots&0\ &0 -1&\cdots&0\ & \dots&\ 0& 0&\cdots&-1 \end{ar y}\ight),|\det(B_{m})|=p^{m}. the LLL. duced basis and B=. algorithm for $\delta$\in(1/4,1) we denote \{b_{0}, b_{1}, . . . , b_{n}\} ( b_{0} bl. b_{n} ). It is known that the shortest vector b_{0} ,. .. .. a re‐. in B.

(3) 59. satisfies. \displaystyle \Vert b_{0}\Vert_{2} \leq \sqrt{n+1}|\det(B)|^{\frac{1}{n+1} (\frac{2}{\sqrt{4 $\delta$-1} )^{n} = \displaystyle \sqrt{n+1}|\det(B_{m})|^{\frac{1}{n+1} (\frac{2}{\sqrt{4 $\delta$-1} )^{n} = \displaystyle \sqrt{n+1}p^{\frac{m}{n+1} (\frac{2}{\sqrt{4 $\delta$-1} )^{n}. (2.3). (cf. [8]). In [4] we. $\lambda$_{1}^{(\infty)}(B_{m}). have. given the. by using. upper bound of the minimum. the famous Dirichlet. norm. value. $\lambda$_{1}^{(\infty)}($\Gamma$_{m})(=. principle.. ‐tuple of p ‐adic integers =\{$\xi$_{1}, . . . , $\xi$_{n}\} which are irrational and linearly independent over \mathb {Q} and each positive integer m there exists a solution in integers a_{0,m}, a_{1,m} a_{n,m}\in \mathbb{Z}^{n+1} which satisfies. Theorem 2.2. For. a n. ,. ,. ,. .. .. .. ,. ,. ,. (2.4). 0<|a_{0,m}+a_{1,m}$\xi$_{1}+\cdots+a_{n,m}$\xi$_{n}|_{p}\leq p^{-m},. (2.5). \displaystyle \max_{0\leq i\leq n}|a_{i,m}|\leq p^{\frac{m}{n+1} .. Consequently,. we. have. $\lambda$_{1}^{(\infty)}($\Gamma$_{m})\leq p^{\frac{m}{n+1}}=\det($\Gamma$_{m})^{\frac{1}{n+1}}.. (2.6). 3. DUAL LATTICE Next. we. consider the. following. problems. p‐‐adic integers.. Let n\geq 1 be. an. Definition 3.1. We denote for. that,. some. infinitely. 2nd type of the simultaneous approximation integer and let =\{$\xi$_{1}, $\xi$_{2}, . . . , $\xi$_{n}\} be a n‐tuple of. by. \mathrm{v}_{n}. the supremum of the real numbers \mathrm{y} such Y_{j} , which goes to infinity, the in‐. many real numbers. equalities. 0<\displaystyle \max_{1\leq i\leq n}|a_{0,j}$\xi$_{i}-a_{i,j}|_{p}\leq Y_{j}^{- $\nu$-1}, \displaystyle \max_{0\leq i\leq n}|a_{i,j}|\leq Y_{j}, have. a. For. (3.1) For. a. solution in a. integers a_{0,j}, a_{1,j},. positive integer. m we. a_{n,j}.. define the. p‐‐adic approximation lattice $\Lambda$_{m} by. $\Lambda$_{m}=\displaystyle \{(a_{0}, \mathrm{a}\mathrm{l}, . . . , a_{n})\in \mathbb{Z}^{n+1} : \max_{1\leq i\leq n}|a_{0}$\xi$_{i}-a_{i}|_{p}\leq p^{-m}\}. radic integer $\xi$_{i}. with its. p‐‐adic expansion. $\xi$_{i}=\displaystyle \sum_{k=0}^{\infty}x_{i,k}p^{k}, 0\leq x_{i,k}\leq p-1.

(4) 60. and the m‐th order. approximation $\xi$_{i,m} given by (2.2) \{b_{0,m}, b_{1,m}, . . . , b_{n,m}\}\subset \mathbb{Z}^{n+1} of the lattice $\Lambda$_{m} where. we can. construct the basis. b_{0,m}=(1, $\xi$_{1,m}, $\xi$_{2,m}, \ldots, $\xi$_{n,m})^{t}, b_{1,m}=(0, -p^{m}, 0, \ldots, 0)^{t}, b_{2,m}=(0,0, -p^{m}, 0, \ldots, 0)^{t}, \cdots, b_{n,m}=(0,0, \ldots, 0, -p^{m})^{t}. In. fact,. we. have. b_{k,m}\in$\Lambda$_{m},. \forall k , since. we can. estimate. |$\xi$_{k,m}-$\xi$_{k}|_{p}\leq p^{-m}. For. B_{m}=(b_{0,m}b_{1,m}\ldots b_{n,m}). we. have. B_{m}=\left(bgin{ar y}{l 1&0 &\cdots&0\ $\xi_{1,m}&-p^{m}&0 \cdots&0\ $\xi_{2,m}&0 -p^{m}&\cdots&0\ & \dots&\ $\xi_{n,m}&0 &\cdots&-p^{rn} \end{ar y}\right),|\det(B_{m})|=p^{nm}.. $\delta$\in(1/4,1) we (b_{0}b_{1} . . . b_{n}) The shortest which are similar to (2.3), following estimates, Applying. the LLL. algorithm. duced basis and B=. [5]. we. $\lambda$_{1}^{(\infty)}(L(B_{m}. denote. vector. have given the estimates of the minimum. \{b_{0}, b_{1}, . . . , b_{n}\}. b_{0}. a n. irrational and a. norm. a re‐. . in B satisfies the. value. $\lambda$_{1}^{(\infty)}($\Lambda$_{m})(=. ‐tuple of p ‐adic integers =\{$\xi$_{1}, . . . , $\xi$_{n}\} which are over and each \mathb {Q} linearly independent positive integer m there solution in integers (a_{0,m}, a_{1,m}, \ldots, a_{n,m})\in \mathbb{Z}^{n+1} which satisfies. Theorem 3.2. For exists. ,. .. \displaystyle \Vert b_{0}\Vert_{2} \leq \sqrt{n+1}|\det(B)|^{\frac{1}{n+1} (\frac{2}{\sqrt{4 $\delta$-1} )^{n} =\displaystyle \sqrt{n+1}|\det(B_{m})|^{\frac{1}{n+1} (\frac{2}{\sqrt{4 $\delta$-1} )^{n} =\displaystyle \sqrt{n+1}p^{\frac{mn}{n+1} (\frac{2}{\sqrt{4 $\delta$-1} )^{n}. (3.2). In. for. ,. ,. ,. ,. (3.3). 0<\displaystyle \max_{1\leq i\leq n}|a_{0,m}$\xi$_{i}-a_{i,m}|_{p}\leq p^{-m},. \displaystyle \max_{0\leq i\leq n}|a_{i,m}|\leq p^{\frac{nm}{n+1} .. (3.4) Consequently,. we. have. $\lambda$_{1}^{(\infty)}($\Lambda$_{m})\leq p^{\frac{nm}{n+1}}=\det($\Lambda$_{m})^{\frac{1}{n+1}}. (3.5) and. \displaystyle \mathrm{v}_{n} \geq\frac{1}{n}.. (3.6) For. by. a. lattice. L(A). with its basis square matrix A , define its dual lattice. L(A)^{*}=L((A^{t})^{-1}). L(A)^{*}.

(5) 61. where A^{t} is the transpose of the matrix of A. For the 1st type lattice $\Gamma$_{\mathrm{m}}=L(B_{m}) and the 2nd type lattice have the following theorem. Theorem 3.3. For. a. positive integer. $\Lambda$_{m}=L(B_{m}). and the 1st type lattice. m. we. $\Gamma$_{m}=L(B_{m}). and the 2nd type lattice $\Lambda$_{m}=L(B_{m}) , let B=B_{m}U and B=B_{m}V unimodular matrices U, V. Then the following duality relation. for. some. L(B)=$\Lambda$_{m}=p^{m}$\Gamma$_{m}^{*}=L(p^{m}(B^{t})^{-1}). (3.7) holds.. Proof.. From the definitions of B_{m} and. B_{m}. have. we. B_{m}=p^{m}(B_{m}^{t})^{-1} Since. L(AW)=L(A) for any unimodular matrix W , following sequence of estimates.. we can. easily. obtain the. L(B) = L(B_{m})=L(p^{m}(B_{m}^{t})^{-1}) = L(p^{m}(B^{t})^{-1})=p^{m}$\Gamma$_{m}^{*}. \square. Since the solutions of the 1st SAP. are. given by the reduced. the solutions of the 2nd SAP construct. solutions. matrix B and. it follows from (3.7) that we can are given by B algorithm, which gives the 2nd SAP solutions from the 1st SAP by applying the LLL algorithm. (For details, see [5].) ,. an. 4. CRYPTOSYSTEM In this section. we. the hardness of. on. propose. solving. that Alice wants to send For. a. a. a new. cryptosystem, the security of which depends. the SAP in the. higher. message to Bob in this. dimensions. Now. we assume. cryptosystem.. n let B= (b_{0}, b_{1}, :. . , b_{n}) be ‐tuple of public keys $\xi$_{i}\in \mathbb{Z}_{p}, i=1 reduced basis given by applying the LLL algorithm as in section 3 from the a n. ,. .. .. .. ,. ,. lattice basis matrix. For. K,. a. \forall i. ,. B_{m}=\left(bgin{ar y}{l 1&0 &\cdots&0\ $xi_{\mathr {l},m&-p^{m}&0 \cdots&0\ $xi_{2,m}&0 -p^{m}&\cdots&0\ & \dots&\ $xi_{n,m}&0 &\cdots&-p^{m} \end{ar y}\ight),|\det(B_{m})|=p^{nm}.. constant K>0 and we. define the secret. vector of random. integers (\mathrm{s}_{0}, s_{n})\in \mathbb{Z}^{n} keys (a_{0}, \mathrm{a}_{1}, a_{n}) by a. ( a_{0} Let the secret. key. a_{i}. be the. ,. al,. sum. a_{i}=$\alpha$_{i}+$\beta$_{i},. \cdots. ,. a_{n}. ). =\displaystyle\sum_{i=0}^{n}s_{i}b_{i}.. of $\alpha$_{i} and. $\alpha$_{i},. $\beta$_{i}\in \mathbb{Z},. $\beta$_{i}. ,. that is. i=0 ,. 1,. .. .. .. ,. n.. :. |s_{i}|\leq.

(6) 62. Alice has the secret. Encryption. key \{$\alpha$_{i}\}. and Bob has the secret. Alice wants to send to Bob. a. list of messages. key \{$\beta$_{i}\}.. given by. x^{(i)}=\displaystyle \sum_{k=0}^{m-1}x_{k}^{(i)}p^{k}, 0\leq x_{k}^{(i)}\leq p-1, i=1, \cdots, n.. Alice constructs the. ciphertext. \mathrm{c}_{A}. by. \mathrm{c}_{A}= (c_{1,A}, c_{2,A}, c_{m,A}) , c_{i,A}=$\alpha$_{0}$\xi$_{i}-$\alpha$_{i}+x^{(i)} and she sends the. ciphertext. \mathrm{c}_{A} to Bob.. Decryption Bob takes the. sum. of \mathrm{c}_{A} and \mathrm{c}_{B} , given. by. \mathrm{c}_{B}= (c_{1,B}, c_{n,B}) , c_{i,B}=$\beta$_{0}$\xi$_{i}-$\beta$_{i},. \mathrm{c}= (c_{1}, c_{ $\eta$})=\mathrm{c}_{A}+\mathrm{c}_{B}, c_{?}\cdot=a_{0}$\xi$_{i}-a_{i}+x^{(i)}. Then he. can. easily. obtain the messages. x^{(i)} by calculating. c_{i}\equiv x^{(i)} \mathrm{m}\mathrm{o}\mathrm{d} p^{m}. REFERENCES 1.. 2.. Y.Bugeaud, Approximation by Algebraic Numbers Cambridge Tracts in Mathematics, Cambridge University Press, 2004. H.Inoue, p ‐adic continued fractions and theory of p ‐adic approximation lattices, Proceed‐ ings of the 8th International Conference on Nonlinear Analysis and Convex Analysis 2013, 139−153.. 3. H. Inoue and K.. 4.. 5.. 6.. 7. 8.. 9. 10.. Naito, Recurrent properties of quasi‐periodic dynamical systems with mul‐ tiple frequencies ofp‐adic Liouville numbers, P‐Adic Numbers, Ultrametric Analysis, and Applications 6 (2014), 195‐206. H.Inoue and K.Naito, The shortest vector problems in p ‐adic lattices and simultaneous approximation problems of p ‐adic numbers, to appear in Proc. of ICM Satellite Conference 2014: the 4th Asian Conf. on Nonlinear Analysis and optimization 2014 (Taipei). H.Inoue, S.Kamada and K.Naito, Transference principle on simultaneous approximation problems ofp‐adic numbers and multidimensional p ‐adic approximation lattices, to appear in Proc. of ICM Satellite Conference 2014: the 4th Asian Conf. on Nonlinear Analysis and optimization 2014 (Taipei). H.Inoue, S.Kamada and K.Naito, Simultaneous approximations of p ‐adic numbers and their applications to cryptography, to appear in Proc. of ICM Satellite Conference 2014: the 4th Asian Conf. on Nonlinear Analysis and optimization 2014 (Taipei). J. C. Lagarias, The computational complexity of simultaneous diophantine approximation problems, SIAM Journal on Computing, 14 (1985), 196‐209. D. Micciancio and S. Goldwasser, Complexity of Lattice Problems, a Cryptographic Per‐ spective Springer International Series in Engineering and Computer Science, vol. 671. Springer, 2002 D. Micciancio and O. Regev, Lattice‐Based Cryptography, in Post Quantum Cryptogra‐ phy D.J. Bernstein; J. Buchmann; E. Dahmen (Eds.), Springer 2009, 147−191. P.Q. Nguyen and B. Vallee (Eds.), The LLL Algorithm, Survey and Applications Springer 2010..

(7) 63. Department of Mathematics, Graduate School of Science and. Technology,. Kumamoto. University, Kumamoto, Japan [email protected]‐u.ac.jp. Kurokami 2‐39‐1,. \mathrm{P}_{\backslash \backslash }^{2}\mathrm{g}\mathrm{X} $\lambda$ F\star\yen^{\backslash }\Re\pm. \mathrm{B}\mathfrak{B}_{1\backslash \backslash }\mathrm{f}\mathrm{f}\not\cong^{\backslash }\mathrm{f}\mathrm{f}\mathrm{l}_{J $\iota$}^{*}\mathrm{f}\mathrm{l}\backslash \backslash Department. mM. ff—. of. Applied Mathematics, Technology, Kumamoto University, [email protected]‐u.ac.jp r^{\mathrm{b} \hat{\mathrm{B}_{1\backslash} ^{\mathrm{b} *\star^{\backslash}\neq^{\backslash}\star^{\backslash}\not\equiv^{\backslash}\ovalbox{\t \smal REJECT}\cdot\in\mathrm{i}_{r\backslash\backslash}\mathrm{H}^{\backslash}\backslash\yen^{\backslash} fflnE Graduate School of Science and. HL \# l_{-}^{-}. Department of Applied Mathematics, Graduate School of Science and Technology, Kumamoto University, [email protected]‐u.ac.jp. \ovalbox{\t \smal REJECT}_{\backslash \backslash }^{\mathrm{e} \mathrm{b}*\not\cong^{\backslash }\star\not\cong^{\backslash }\Re\Leftrightar ow\cdot$\Xi$_{j1\backslash \backslash }^{ $\pi$}\mathrm{R}\backslash \not\cong^{\backslash }\mathrm{f}\mathrm{f}\mathrm{l}^{p}\mathrm{r}^{\mathrm{t} \mathrm{H}\backslash \backslash |\mathrm{r}\ovalbox{\t \smal REJECT}\not\equiv-\mathrm{g} $\beta$.

(8)