逆像オラクル付きランダム関数を用いた一方向関数の構成条件の拡張

• Item type: Symposium(1)
• 公開日: 2024-10-15
• タイトル: 逆像オラクル付きランダム関数を用いた一方向関数の構成条件の拡張
• タイトル / 言語: en
• タイトル: Extensions of the Conditions for Constructing One-Way Functions from Random Ones with the Inverse Oracles
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 一方向性関数，ランダム関数，強識別不可能性
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 電気通信大学
• 著者所属: 電気通信大学／産業技術総合研究所
• 著者所属: 電気通信大学
• 著者所属(英): en
• 著者所属(英): The University of Electro-Communications
• 著者所属(英): en
• 著者所属(英): The University of Electro-Communications / AIST
• 著者所属(英): en
• 著者所属(英): The University of Electro-Communications
• 著者名: 儀保, 駿; 渡邉, 洋平; 岩本, 貢
• 著者名(英): Hayato, Gibo; Yohei, Watanabe; Mitsugu, Iwamoto
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 一方向性関数とは順方向の計算は容易だが逆像計算が困難な関数であり，暗号理論を含む理論計算機科学において重要な関数である．Ghosal とSahai (GS) は一方向性関数が構成できるための条件として「簡単な関数」を定義し，独立な二つの簡単な関数の和が一方向性をもつことを，いくつかの条件の下で示した．ここで，簡単な関数とは逆像オラクルをもつランダム関数のことである．本研究では，GS が示した二つの簡単な関数の和による一方向性関数の構成がより広い範囲で成り立つことを示す．具体的には，二つの関数f, g : {0, 1}^m → {0, 1}^n が{0, 1}^m から{0, 1}^n に定まる関数全体の集合から一様ランダムに選ばれる場合に，GS が示した条件m − n = ω(log n) を
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: One-way functions, which are easy to compute but hard to invert, are important in theoretical computer science, including cryptography. Ghosal and Sahai (GS) defined an easy function as a building block for constructing a one-way function and showed that adding two unrelated easy functions becomes a oneway function under several conditions, where an easy function is a random function with the inverse oracle. In this study, we will show that the constructions of a one-way function by adding two easy functions proposed by GS holds in a wider range. Specifically, if a random function is described as f, g : {0, 1}^m → {0, 1}^n and f and g are chosen at uniformly random from the whole set of functions mapping from {0, 1}^m to {0, 1}^n, the condition m − n = ω(log n) given by GS can be extended to
• 書誌情報: コンピュータセキュリティシンポジウム2024論文集; p. 1433-1440, 発行日 2024-10-15
• 出版者 / 言語: ja
• 出版者: 情報処理学会