一次元折り紙の計算量的複雑性とその電子署名方式への応用

• Item type: SIG Technical Reports(1)
• 公開日: 2022-05-12
• タイトル: 一次元折り紙の計算量的複雑性とその電子署名方式への応用
• タイトル / 言語: en
• タイトル: Computational Complexity of One-Dimensional Origami and Its Application to Digital Signature
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 北陸先端科学技術大学院大学
• 著者所属: 茨城工業高等専門学校
• 著者所属: 北陸先端科学技術大学院大学
• 著者所属: 北陸先端科学技術大学院大学
• 著者名: 芳師渡, 淳之介; 安細, 勉; 鎌田, 斗南; 上原, 隆平
• 著者名(英): Junnosuke, Hoshido; Tsutomu, Ansai; Tonan, Kamata; Ryuhei, Uehara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿は，折り目幅復元問題と呼ばれる問題を提案し，その複雑性を示すとともに，電子署名方式への応用を提案するものである．長さ n+1 の短冊状の紙を等間隔に刻まれた n 本の折り目に従って長さ 1 に折り畳んだとき，各折り目に挟まる紙の枚数を折り目幅とよぶ．折り目幅復元問題とは，折り目幅の情報が入力として与えられたとき，それに矛盾しない折り畳み状態が存在するかどうかを問う問題である．これは折り目幅問題と関連して得られる，新たな一次元折り紙問題である．問題には，それぞれの折り目の向きが与えられているか否か，折り目幅の情報が全て与えられているか否か，などの条件設定が存在する．ここでは，それらの内のいくつかの場合について，NP 困難性を証明する．さらに，問題の計算複雑性を利用した新たな電子署名方式を提案する．
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2022-AL-188, 号 1, p. 1-7, 発行日 2022-05-12
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会