YOI 676：同じ演算が、順は多項式・逆は指数である：ただし比が大きいだけでは足りない

論文676 の記録のページです。住所（YOI）は https://www.yamagishiyuuki.com/yoi/676 で、論文の本文は下の PDF にあります。ファイルは自分で用意した置き場所（https://yamagishi.sakuraweb.com）に置き、日付の証拠（.ots）を添えています。Zenodo でも公開しています（DOI：10.5281/zenodo.23014770）。

本文のサイトの記事は、これから順に公開します。

@misc{yamagishi2026yoi676,
  author = {Yamagishi, Yuuki},
  title = {One Operation, Polynomial Forwards and Exponential Backwards: But a Large Ratio Is Not Enough},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/676},
  doi = {10.5281/zenodo.23014770},
  note = {Preprint, edition 1}
}

日付の証拠（OpenTimestamps）

2026年10月1日に、2 本の PDF の指紋（SHA-256）をまとめて OpenTimestamps に送り、ビットコインのブロック 969436・969440・969456・969461 に記録されました（2026年10月01日 18:32（日本時間））。この .ots があれば、PDF がその時点で存在したことを、このサイトや運営者を信用しなくても、誰でも確かめられます。

書誌

要旨

公開の場で数を交換するだけで、二人だけが知る秘密を作れる。同じ演算が、順方向は易しく逆方向は難しいからである。その易しさと難しさを実際に数え、比がどれだけあれば安全と言えるのかを見る。新しい定理も法則も主張しない。

第一に、手続きは実際に動く。法 $2^{127}-1$ で鍵交換を行い、両側がそれぞれの計算から同じ共有秘密に達することを確かめた（第2節）。

第二に、順と逆の手間は桁で違う。作る側は約 $254$ 回の乗算、破る側（平方根の攻撃）は約 $\mathbf{1.304382}\times10^{19}$ 回で、比は $\mathbf{5.135361}\times10^{16}$ 倍である（第2節）。

第三に、これが本稿の芯である。比が大きいだけでは足りない。その $5.135361\times10^{16}$ 倍という比があっても、毎秒 $1$ 兆回の機械なら $\mathbf{0.413334}$ 年で破れてしまう（第3節）。

第四に、桁を $2$ 倍にすると、二つの側の効き方が違う。作る手間は $\mathbf{2.000000}$ 倍にしかならないのに、破る手間は $\mathbf{1.304382}\times10^{19}$ 倍になり、破るのに要る時間は $\mathbf{5.391449}\times10^{18}$ 年になる（第3節）。

第五に、だから鍵長は「比」ではなく「絶対の大きさ」で決める。比は $127$ bit でも $254$ bit でも同じ形で効くが、破るのに要る時間は $0.413334$ 年と $5.391449\times10^{18}$ 年に分かれる（第3節）。

第六に、分離子は、逆問題が易しいか難しいかである。難しさに賭けているのであって、不可能性に賭けているのではない（第4節）。

キーワード：鍵交換、離散対数、一方向性、計算量、公開鍵暗号、鍵長

Abstract

Two people can build a secret known only to them by exchanging numbers in the open, because one operation is easy forwards and hard backwards.That ease and that hardness are counted, and how large the ratio must be before one may call it safe is examined.No new theorem or law is claimed.

First, the procedure really runs、a key exchange for the modulus $2^{127}-1$ was carried out, and both sides, starting from different secrets, reached the same shared secret (Section 2).

Second, the two directions differ by orders、making it takes about $254$ multiplications and breaking it, by a square-root attack, about $\mathbf{1.304382}\times10^{19}$ operations, a ratio of $\mathbf{5.135361}\times10^{16}$ (Section 2).

Third, and this is the core. A large ratio is not enough、even with that ratio of $5.135361\times10^{16}$, a machine doing a trillion operations a second breaks the key in $\mathbf{0.413334}$ years (Section 3).

Fourth, doubling the bits acts differently on the two sides、the cost of making it rises only $\mathbf{2.000000}$ times while the cost of breaking it rises $\mathbf{1.304382}\times10^{19}$ times, putting the time to break at $\mathbf{5.391449}\times10^{18}$ years (Section 3).

Fifth, so a key length is chosen by absolute size, not by ratio、the ratio takes the same form at $127$ bits and at $254$, while the time to break divides into $0.413334$ years and $5.391449\times10^{18}$ years (Section 3).

Sixth, the separator is whether the inverse problem is easy or hard、the wager is on hardness, not on impossibility (Section 4).

Keywords: key exchange, discrete logarithm, one-way function, computational cost, public-key cryptography, key length

版の記録

ここの PDF（倉庫の v1）は第1版（2026年9月）の原稿から作りました。ファイルは版ごとに分けて置いています（/yoi/676/v1/ の下）。中身を直すときは、このファイルを書き換えず、新しい版を足します（住所 https://www.yamagishiyuuki.com/yoi/676 はいつも最新の版を指します）。Zenodo の記録とは、Zenodo に上げる前の改訂のぶんだけ違うことがあります。

YOI の一覧へ