1. 前のページに戻る

メタ計算量による暗号の安全性の解析

研究課題

戦略的な研究開発の推進 創発的研究支援事業

体系的番号 JPMJFR226Y
DOI https://doi.org/10.52926/JPMJFR226Y

研究代表者

平原 秀一  国立情報学研究所, 情報学プリンシプル研究系, 准教授

研究期間 (年度) 2024 – 2030 (予定)
概要計算量理論は、計算に必要とされる計算量(計算時間・メモリ等)を解析する学問です。近年、計算量を問う問題の計算量を考える「メタ計算量」という概念を用いることにより、計算量理論および暗号理論における重要な未解決問題に進展を与えられることが明らかとなってきました。本研究では、メタ計算量を用いて、暗号の安全性に関わる未解決問題を解決し、より安全な暗号を構築することを目指します。
研究領域八木パネル

報告書

(1件)
  • 2024 年次報告書 ( PDF )
  • 主な研究成果

    (10件)

すべて 2024

すべて 雑誌論文 (10件) (国際共著 6件、 査読あり 10件、 オープンアクセス 10件)

  • [雑誌論文] One-Way Functions and pKt Complexity.2024

    • 著者名
      Shuichi Hirahara, Zhenjian Lu, Igor C. Oliveira
    • 雑誌名

      TCC (1)

      ページ: 253-286

    • 査読あり / オープンアクセス / 国際共著
  • [雑誌論文] Optimal Coding for Randomized Kolmogorov Complexity and Its Applications.2024

    • 著者名
      Shuichi Hirahara, Zhenjian Lu, Mikito Nanashima
    • 雑誌名

      FOCS

      ページ: 369-378

    • 査読あり / オープンアクセス / 国際共著
  • [雑誌論文] Symmetric Exponential Time Requires Near-Maximum Circuit Size.2024

    • 著者名
      Lijie Chen, Shuichi Hirahara, Hanlin Ren
    • 雑誌名

      STOC

      ページ: 1990-1999

    • 査読あり / オープンアクセス / 国際共著
  • [雑誌論文] One-Way Functions and Zero Knowledge.2024

    • 著者名
      Shuichi Hirahara, Mikito Nanashima
    • 雑誌名

      STOC

      ページ: 1731-1738

    • 査読あり / オープンアクセス
  • [雑誌論文] Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems.2024

    • 著者名
      Shuichi Hirahara, Naoto Ohsaka
    • 雑誌名

      STOC

      ページ: 1435-1445

    • 査読あり / オープンアクセス
  • [雑誌論文] Beating Brute Force for Compression Problems.2024

    • 著者名
      Shuichi Hirahara, Rahul Ilango, R. Ryan Williams
    • 雑誌名

      STOC

      ページ: 659-670

    • 査読あり / オープンアクセス / 国際共著
  • [雑誌論文] Planted Clique Conjectures Are Equivalent.2024

    • 著者名
      Shuichi Hirahara, Nobutaka Shimizu
    • 雑誌名

      STOC

      ページ: 358-366

    • 査読あり / オープンアクセス
  • [雑誌論文] Optimal PSPACE-Hardness of Approximating Set Cover Reconfiguration.2024

    • 著者名
      Shuichi Hirahara, Naoto Ohsaka
    • 雑誌名

      ICALP

      ページ: 85-18

    • 査読あり / オープンアクセス
  • [雑誌論文] Exact Search-To-Decision Reductions for Time-Bounded Kolmogorov Complexity.2024

    • 著者名
      Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira
    • 雑誌名

      CCC

      ページ: 29-56

    • 査読あり / オープンアクセス / 国際共著
  • [雑誌論文] One-Tape Turing Machine and Branching Program Lower Bounds for MCSP.2024

    • 著者名
      Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, Yuichi Yoshida
    • 雑誌名

      Theory of Computing Systems

      巻: 68 号: 4 ページ: 868-899

    • 査読あり / オープンアクセス / 国際共著

URL: 

JSTプロジェクトデータベース掲載開始日: 2025-07-16   JSTプロジェクトデータベース最終更新日: 2026-09-08  

サービス概要 よくある質問 利用規約

Powered by NII jst