{"metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00190608","sets":["1164:6389:9385:9512"]},"path":["9512"],"owner":"11","recid":"190608","title":["A New Embedding Method for Generalized LWE"],"pubdate":{"attribute_name":"公開日","attribute_value":"2018-07-18"},"_buckets":{"deposit":"c7c3e63a-9883-454d-8914-6ecd96274494"},"_deposit":{"id":"190608","pid":{"type":"depid","value":"190608","revision_id":0},"owners":[11],"status":"published","created_by":11},"item_title":"A New Embedding Method for Generalized LWE","author_link":["436648","436650","436645","436649","436647","436652","436651","436646"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"A New Embedding Method for Generalized LWE"},{"subitem_title":"A New Embedding Method for Generalized LWE","subitem_title_language":"en"}]},"item_type_id":"4","publish_date":"2018-07-18","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"東京大学大学院情報理工学系研究科"},{"subitem_text_value":"東京大学大学院情報理工学系研究科／九州大学大学院数理学府"},{"subitem_text_value":"東京大学大学院情報理工学系研究科／国立研究開発法人産業技術総合研究所"},{"subitem_text_value":"東京大学大学院情報理工学系研究科"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Graduate School of Information Science and Technology, The University of Tokyo","subitem_text_language":"en"},{"subitem_text_value":"Graduate School of Information Science and Technology, The University of Tokyo / Graduate School of Mathematics, Kyushu University","subitem_text_language":"en"},{"subitem_text_value":"Graduate School of Information Science and Technology, The University of Tokyo / National Institute of Advanced Industrial Science and Technology,","subitem_text_language":"en"},{"subitem_text_value":"Graduate School of Information Science and Technology, The University of Tokyo","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/190608/files/IPSJ-SPT18029056.pdf","label":"IPSJ-SPT18029056.pdf"},"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-SPT18029056.pdf","filesize":[{"value":"406.8 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"0","billingrole":"46"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_login","version_id":"5032b8d4-1b86-4955-9b23-8be69905a870","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2018 by the Institute of Electronics, Information and Communication Engineers This SIG report is only available to those in membership of the SIG."}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"王, 偉尭"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"王, 贇トウ"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"高安, 敦"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"高木, 剛"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Weiyao, Wang","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Yuntao, Wang","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Atsushi, Takayasu","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Tsuyoshi, Takagi","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_4_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AA12628305","subitem_source_identifier_type":"NCID"}]},"item_4_textarea_12":{"attribute_name":"Notice","attribute_value_mlt":[{"subitem_textarea_value":"SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc."}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_18gh","resourcetype":"technical report"}]},"item_4_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"2188-8671","subitem_source_identifier_type":"ISSN"}]},"item_4_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"Estimating for the computational cost of solving learning with errors (LWE) problem is an indispensable research topic to the lattice-based cryptography in practice. For this purpose, the embedding approach is usually employed. The technique first constructs a basis matrix by embedding an LWE instance. At this stage, Kannan's and Bai-Galbraith's embeddings are believed to be the most efficient approaches for the standard and the binary LWE with secret vectors in Znq and {0,1}ⁿ, respectively. Indeed, both methods work well with sufficiently many LWE samples. After the embedding phase, solving the unique shortest vector problem (uSVP) in the lattice spanned by the basis matrix results in solving the LWE. Recently, there are several lattice-based schemes whose secret vectors have special distributions, e.g., small elements and / or sparse vectors, have been proposed to realize efficient implementations. In this paper, to capture such settings and more, we study the LWE problem in a general setting. We analyze the LWE problem whose secret vectors are sampled from arbitrary distributions. Furthermore, we also study the problem when the number of samples is restricted. We believe that our work provides more general understanding of the hardness of LWE. Moreover, we propose a half-twisted embedding that contains the existing two embedding methods as special cases. This proposal enables us to analyze the hardness of LWE in a generic manner and sometimes provides improved attacks.","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"Estimating for the computational cost of solving learning with errors (LWE) problem is an indispensable research topic to the lattice-based cryptography in practice. For this purpose, the embedding approach is usually employed. The technique first constructs a basis matrix by embedding an LWE instance. At this stage, Kannan's and Bai-Galbraith's embeddings are believed to be the most efficient approaches for the standard and the binary LWE with secret vectors in Znq and {0,1}ⁿ, respectively. Indeed, both methods work well with sufficiently many LWE samples. After the embedding phase, solving the unique shortest vector problem (uSVP) in the lattice spanned by the basis matrix results in solving the LWE. Recently, there are several lattice-based schemes whose secret vectors have special distributions, e.g., small elements and / or sparse vectors, have been proposed to realize efficient implementations. In this paper, to capture such settings and more, we study the LWE problem in a general setting. We analyze the LWE problem whose secret vectors are sampled from arbitrary distributions. Furthermore, we also study the problem when the number of samples is restricted. We believe that our work provides more general understanding of the hardness of LWE. Moreover, we propose a half-twisted embedding that contains the existing two embedding methods as special cases. This proposal enables us to analyze the hardness of LWE in a generic manner and sometimes provides improved attacks.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"8","bibliographic_titles":[{"bibliographic_title":"研究報告セキュリティ心理学とトラスト（SPT）"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"2018-07-18","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"56","bibliographicVolumeNumber":"2018-SPT-29"}]},"relation_version_is_last":true,"weko_creator_id":"11"},"updated":"2025-01-20T01:09:53.369849+00:00","created":"2025-01-19T00:56:34.023819+00:00","links":{},"id":190608}