Mathematical Ideas in Lattice Based Cryptography - Jill Pipher

This is great Youtube

(below is made with Notebook LLM)

Mathematical Ideas in Lattice-Based Cryptography

I. Foundations of Public Key Cryptography (PKC)

  1. Public Key Cryptography was designed to enable secure communication across insecure channels between parties who have never shared a secret.
    • This field began as a mathematical subject in 1977 with the Diffie and Hellman paper, "New Directions in Cryptography".
  2. The initial paper defined the concept of a PKC system and secure key exchange, but provided no example of a complete PKC system.
  3. The concept of secure key exchange was illustrated using the discrete logarithm problem, now known as the Diffie-Hellman problem.
  4. A core requirement for PKC is the one-way function, which is computationally easy to perform but computationally hard to reverse (invert).
    • The definition of "hard to invert" relates directly to complexity theory and the unknown relationship between P and NP.
  5. To decrypt a message, which is necessary despite the function being one-way, the recipient must possess a trapdoor (the private key).

II. Integer Lattices and Geometric Representation

  1. An integer lattice is a regular array of points that can be easily visualized in two dimensions.
  2. All points within a lattice are generated by integer linear combinations of a set of basis vectors.
    • The region generated by the basis vectors is termed the fundamental parallelepiped.
  3. A lattice can be formally represented as a matrix where the row vectors constitute the basis.
  4. Any given lattice possesses many different bases; a change of basis is achieved by multiplication by another matrix having integer entries and a determinant of one.

III. Hard Computational Problems in Lattices

  1. Two primary associated computational problems are the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP).
  2. SVP asks for the shortest non-zero vector in the lattice, given any basis.
  3. CVP asks for the lattice point closest to an arbitrary, randomly chosen point in space.
  4. Solving CVP efficiently requires a "good basis," meaning the basis vectors are both as short as possible and as orthogonal as possible.
  5. While a known algorithm (Gauss's) efficiently finds the shortest basis in two dimensions, this method fails upon reaching dimension three.
  6. The LLL (Lenstra, Lenstra, Lovász) algorithm, developed in 1982, finds short basis vectors in high dimensions.
    • LLL is guaranteed to run in polynomial time relative to the dimension of the lattice.
  7. The LLL algorithm guarantees finding a vector no larger than a defined multiple of the actual shortest vector.
  8. The Closest Vector Problem is formally classified as an NP-hard problem.

IV. Lattice-Based Cryptography and NTRU

  1. Lattices initially gained prominence in cryptanalysis, notably when the LLL algorithm was used to break cryptosystems based on the subset sum (knapsack) problem.
  2. This cryptanalytic application relied on the realization that the inversion problem was equivalent to finding a short vector in an integer lattice.
  3. In the mid-1990s, lattices were reintroduced for constructive use in cryptography.
  4. NTRU was designed to achieve high efficiency by utilizing the CVP/SVP within a specific class of lattices characterized by a great deal of symmetry.
  5. Early feedback from powerful voices in the crypto community doubted NTRU's security, significantly stalling its development.
  6. Despite initial skepticism, NTRU proved to be much more efficient than alternatives like RSA or ECC, capable of functioning on low-power devices such as an 8-bit processor.

V. NTRU Structure and Lattice Connection

  1. NTRU operates using polynomials with integer coefficients within a ring structure where the fundamental operation is convolution multiplication.
  2. The process involves a double reduction of coefficients: first modulo a large integer (Q), then modulo a small integer (P).
  3. The private key consists of randomly chosen polynomials (F and G) having very small coefficients (e.g., zeros, ones, and minus ones).
  4. The public key (H) is computationally derived and is designed to appear statistically random to an outside observer.
  5. The core hard problem in NTRU is a kind of factoring problem: recovering the short secret polynomials F and G from the public key H.
  6. The operation of convolution multiplication of coefficient vectors is mathematically equivalent to multiplication by a circulant matrix.
  7. The public key H, being large, corresponds to a "bad basis" of the associated lattice.
  8. The secret key components (F, G) correspond to a short basis vector within this highly structured lattice.

VI. Digital Signatures and Secret Leakage

  1. A digital signature must produce data bound to a document whose authenticity is verifiable by anyone, but whose production is restricted solely to the private key holder.
  2. The digital signature problem is often harder than encryption because the signing process risks revealing information about the private key.
  3. In a lattice-based signature scheme, the signature is intended to be the closest lattice point to the document (represented as a target point in space).
  4. The difference between the target point and the signature point lies within the lattice's fundamental parallelepiped.
  5. Repeatedly generating signatures causes information to leak because the shape of the fundamental parallelepiped is gradually revealed.
  6. Rejection sampling, a statistical concept, was introduced to combat this leakage.
  7. This technique hides the distribution of the generated samples by intentionally rejecting a subset of the samples produced during the signature generation process.

VII. Fully Homomorphic Encryption (FHE)

  1. FHE solves the decades-old problem of developing an encryption system where computations performed on encrypted data yield the encrypted result of computations performed on the plaintext.
  2. Craig Gentry found the first solution in 2009 using ideal lattices (a generalization of NTRU lattices) and a technique called bootstrapping, which relies on the scheme encrypting its own decryption circuit.

以下は「Mathematical Ideas in Lattice-Based Cryptography（格子暗号における数学的アイデア）」の日本語訳です。英語原文の構成を保ちながら、専門用語を自然な形で訳しました。

I. 公開鍵暗号 (PKC) の基礎

公開鍵暗号は、秘密を共有していない当事者間で、安全でない通信路を介して安全に通信を行うために設計された。
この分野は1977年、DiffieとHellmanによる論文「New Directions in Cryptography」によって数学的分野として始まった。
その最初の論文では、公開鍵暗号システムと安全な鍵交換の概念が定義されたが、完全な公開鍵暗号システムの例は示されなかった。
安全な鍵交換の概念は離散対数問題（現在ではDiffie-Hellman問題として知られる）を使って説明された。

公開鍵暗号の中核的要件は「一方向関数」である。これは、計算的には容易に実行できるが、その逆演算（反転）は非常に困難である関数である。
「反転が難しい」とは計算量理論における P と NP の関係に直接関わる。
一方向関数であっても復号が必要であるため、受信者は「トラップドア（秘密鍵）」を持つ必要がある。

II. 整数格子と幾何的表現

整数格子とは、二次元で容易に可視化できる規則的な点の配列である。
格子内のすべての点は、基底ベクトルの整数線形結合によって生成される。
基底ベクトルによって生成される領域は「基本平行六面体（fundamental parallelepiped）」と呼ばれる。
格子は行ベクトルが基底を成す行列として形式的に表すことができる。
一つの格子には多数の異なる基底が存在し、別の整数行列（行列式が1）を掛けることで基底を変換できる。

III. 格子における困難な計算問題

格子に関連する主要な計算問題は、最短ベクトル問題（SVP）と最近傍ベクトル問題（CVP）である。
SVPは、与えられた基底に対して最も短い非零ベクトルを求める問題である。
CVPは、任意の点に最も近い格子点を求める問題である。

CVPを効率的に解くには「良い基底」が必要であり、基底ベクトルが短く、かつできるだけ直交していることが望ましい。
ガウスによる2次元での最短基底探索アルゴリズムは知られているが、3次元以上ではこの方法は機能しない。

1982年に開発されたLLL（Lenstra–Lenstra–Lovász）アルゴリズムは、高次元格子における短い基底を見つける手法である。
LLLは格子の次元に対して多項式時間で動作し、最短ベクトルのある定数倍以内のベクトルを必ず見つけることが保証されている。
CVPは形式的にNP困難な問題として分類される。

IV. 格子暗号と NTRU

格子は当初、暗号解析において注目された。特にLLLアルゴリズムがナップサック問題（部分和問題）に基づく暗号を破るために利用された。
この応用は、暗号の逆問題が整数格子における短いベクトル探索と等価であるという発見に基づいていた。

1990年代半ば、格子は建設的な用途として再び暗号分野に導入された。
NTRUは、対称性の高い特殊な格子クラス内でCVP/SVPを利用することで、高速な処理を実現するよう設計された。
当初は暗号コミュニティ内の有力者たちから安全性を疑問視され、開発は大きく遅れた。
しかしNTRUは、RSAや楕円曲線暗号（ECC）よりもはるかに効率的で、8ビットプロセッサのような低消費電力デバイスでも動作可能であることが証明された。

V. NTRU の構造と格子との関係

NTRUは整数係数を持つ多項式を用い、環構造のもとで畳み込み積（convolution multiplication）を基本演算とする。
係数は2段階で縮約される。まず大きな整数Qでの剰余、次に小さな整数Pでの剰余である。
秘密鍵は、非常に小さい係数（0、±1 など）を持つ多項式FとGからなる。
公開鍵Hはこれらから計算的に導出され、外部から見ると統計的にランダムに見えるように設計されている。

NTRUの根幹の難問は「因数分解」に類する問題であり、公開鍵Hから短い秘密多項式FとGを復元することである。
係数ベクトルの畳み込み積は循環行列との行列積と数学的に等価である。
公開鍵Hは格子における「悪い基底」に対応し、秘密鍵成分FとGは構造化された格子内の短い基底ベクトルに対応する。

VI. デジタル署名と秘密情報漏洩

デジタル署名は、任意の人が検証可能で、かつ署名者だけが生成可能な文書への認証データを生成する必要がある。
署名は暗号化よりも難しいことが多く、署名生成過程で秘密鍵に関する情報が漏洩する危険がある。

格子ベース署名方式では、署名は「文書を表す点」に最も近い格子点として構成される。
このとき、文書点と署名点との差は格子の基本平行六面体内に存在する。
しかし、署名を繰り返し生成すると、その平行六面体の形状に関する情報が徐々に漏洩してしまう。

これに対処するため、「棄却サンプリング（rejection sampling）」という統計的手法が導入された。
この手法では、署名生成時に得られるサンプルの一部を意図的に棄却することで、出力の分布を秘匿する。

VII. 完全準同型暗号 (FHE)

完全準同型暗号（FHE）は、暗号文のまま演算を行い、その結果が平文演算の結果を暗号化したものと一致する暗号方式である。
これは数十年来の未解決問題であったが、Craig Gentry が2009年に初めて実現した。
彼は「イデアル格子（ideal lattices）」というNTRUの一般化構造と、「ブートストラッピング（bootstrapping）」という手法を用いた。
この手法では、暗号方式自身の復号回路を暗号化することで、誤差を制御しながら計算を続行できるようにしている。

この翻訳は、原文の専門的正確さを保ちつつも、日本語として自然に読めるよう調整してある。

格子暗号の数学的背景は、代数・幾何・計算理論が融合する現代暗号の最前線であり、数学的構造の美しさがそのまま安全性を生む珍しい領域である。