特許ウォッチ

公開番号2025121868
公報種別公開特許公報(A)
公開日2025-08-20
出願番号2025012242
出願日2025-01-28
発明の名称計算装置、計算方法、およびプログラム
出願人学校法人中部大学
代理人個人,個人,個人
主分類G06N 10/70 20220101AFI20250813BHJP(計算;計数)
要約【課題】LWE問題を効率的に解く。
【解決手段】計算装置は、LWE問題を特定するパラメータセットを用い、LWE問題を1次元LWE-Like問題の集合に変換し、1次元LWE-Like問題の集合を誤差付きの位相推定問題の集合に変換し、誤差付きの位相推定問題の集合を解いて、誤差付きの位相推定問題の解の集合を得、誤差付きの位相推定問題の解の集合をLWE問題の解に変換し、LWE問題の解を出力する。
【選択図】図1
特許請求の範囲【請求項１】
LWE問題を特定するための情報を用い、前記LWE問題を、エラーベクトルの要素ごとに前記エラーベクトルが従う標準偏差が定められた１次元LWE-Like問題の集合に変換し、前記１次元LWE-Like問題の集合を特定するための情報を得るLWE帰着部と、
前記１次元LWE-Like問題の集合を誤差付きの位相推定問題の集合に変換し、前記誤差付きの位相推定問題の集合を特定するための情報を得る問題変換部と、
前記誤差付きの位相推定問題の集合を解いて、誤差付きの位相推定問題の解の集合を得る求解部と、
前記誤差付きの位相推定問題の解の集合を前記LWE問題の解に変換し、前記LWE問題の解を出力する解変換部と、
を有する計算装置。
続きを表示（約 8,300 文字）【請求項２】
内挿点選択部とサンプル点選択部とを有する計算装置であって、
m,n,m',n',jが正整数を表し、αが正の実数を表し、q,q'が1より大きな整数を表し、Z
q
がqを法とする商環Z/qZを表し、Zが整数集合を表し、σ=αqであり、N(0,σ
2
)がZ
q
上の平均0で標準偏差σのガウス分布を表し、||β
1
||がβ
1
のノルムを表し、a
1
,a
2
,…,a
m
∈Z
q
n
がそれぞれn次元行ベクトルを表し、Aがm×n行列
TIFF
2025121868000329.tif
31
169
を表し、εが前記ガウス分布N(0,σ
2
)に従った実数の要素を持つm次元の列ベクトルを表し、s∈Z
q
n
がn次元の列ベクトルを表し、tが
TIFF
2025121868000330.tif
13
169
を満たすm次元の列ベクトルを表し、Xがn個のm次元列ベクトルx
1
,…,x
n
∈Z
m
の集合{x
1
,…,x
n
}を表し、〈β
1
,β
2
〉がβ
1
とβ
2
の内積を表し、格子∧
q
(X)が∧
q
(X):={x∈Z
m
|∃s"∈Z
n
s.t. x≡s"X mod q}であり、前記格子∧
q
(X)の双対格子∧
q
⊥
(X)が∧
q
⊥
(X):={y∈Z
m
|<x,y>≡0 mod q for all x∈∧
q
(X)}であり、β
4
T
がβ
4
の転置を表し、
TIFF
2025121868000331.tif
12
169
が直積を表し、R
c
が
TIFF
2025121868000332.tif
13
169
に含まれる領域を表し、∧
q
⊥
(A
T
)∩R
c
が空集合ではなく、
前記内挿点選択部は、0<θ<q'を満たす任意の整数θについて、
TIFF
2025121868000333.tif
14
169
かつ
TIFF
2025121868000334.tif
14
169
を満たす内挿点ベクトルu~
j,1
【請求項３】
請求項２の計算装置であって、
m=2かつn=1であり、m'=m=2かつn'=1であり、υが0以上の整数を表し、ξが正整数を表し、q'がフィボナッチ数列{F
k
}
k=0,...,∞
に属する要素F
ξυ+2
であり、j=1,...,mであり、κ=1,2であり、Zが整数集合を表し、B
-
1
およびB
-
2
が双対格子∧
q
⊥
(A
T
)の2個の基底を表し、B
-
j
={b
-
j,1
,b
-
j,2
}であり、b
-
j,κ
∈Z
2
であり、前記内挿点ベクトルu~
j,1
が
TIFF
2025121868000335.tif
20
169
であり、
細分点ベクトルd~
j,1
,…,d~
j,ξυ+1
が
TIFF
2025121868000336.tif
45
169
を満たし、
前記サンプル点ベクトルb~
j,1
,…,b~
j,m'
は、前記内挿点ベクトルu~
j,1
および前記細分点ベクトルd~
j,1
,…,d~
j,ξυ+1
に基づく、前記格子L(B~
j
)の基底B~
j
={b~
j,1
,...,b~
j,m
}を構成するｍ次元のベクトルb~
j,1
,...,b~
j,m
である、計算装置。
【請求項４】
請求項３の計算装置であって、
π~(q)がフィボナッチ数列{F
k
mod q}
k=0
∞
に表れる零の周期を表し、υ＝π~(q)である、計算装置。
【請求項５】
請求項２の計算装置であって、
m'=mかつn'=1であり、j=1,..,mであり、υが0以上の整数を表し、ξ，kが正整数を表し、m×m行列
TIFF
2025121868000337.tif
38
169
ならびに、m次元ベクトル[F
k-m+2
,...,F
k
,F
k+1
]
T
および[0,...,0,1]
T
について、
TIFF
2025121868000338.tif
31
169
を満たし、
B
-
が前記双対格子∧
q
⊥
(A
T
)の基底を表し、P
1
,P
2
,...,P
m
が置換行列を表し、B
-
P
1
,B
-
P
2
,...,B
-
P
m
のエルミート標準形HNF(B
-
P
1
),HNF(B
-
P
2
),...,HNF(B
-
P
m
)がそれぞれ、m×m行列
TIFF
2025121868000339.tif
20
169
で表され、I
n
がm-n×m-nの単位行列を表し、*
m-n,n
がq未満の非負整数を要素とするm-n×nの行列を表し、0
n,m-n
がn×m-nの零行列を表し、q
n
が対角成分がqで他の要素が零のn×n行列を表し、B
-
1
=HNF(B
-
P
1
)P
1
T
,B
-
2
=HNF(B
-
P
2
)P
2
T
,...,B
-
m
=HNF(B
-
P
m
)P
m
T
を表し、B
-
【請求項６】
請求項５の計算装置であって、
υ=m+1である、計算装置。
【請求項７】
ベクトル生成部と入力量子状態特定部とを有する計算装置であって、
m,nが正整数を表し、αが正の実数であり、q,q'が1より大きな整数を表し、j=1,...,mであり、eはネイピア数を表し、iは虚数単位を表し、Z
q
がqを法とする商環Z/qZを表し、Zが整数集合を表し、σ=αqであり、N(0,σ
2
)がZ
q
上の平均0で標準偏差σのガウス分布であり、B~
j
は格子L(B~
j
)の基底を表すm×m行列を表し、b~
j,1
,...,b~
j,m
が基底B~
j
を構成するm個のm次元のベクトルを表し、｜β
0
｜がβ
0
の絶対値を表し、＃βが集合βに属する要素数を表し、〈β
1
,β
2
〉がβ
1
とβ
2
の内積を表し、|β
1
>が縦ベクトルβ
1
を表し、a
1
,a
2
,…,a
m
∈Z
q
n
がそれぞれn次元行ベクトルを表し、Aがm×n行列
TIFF
2025121868000345.tif
31
169
を表し、εが前記ガウス分布N(0,σ
2
)に従った実数の要素を持つm次元の列ベクトルを表し、s∈Z
q
n
がn次元の列ベクトルを表し、tが
TIFF
2025121868000346.tif
13
169
を満たすm次元の列ベクトルを表し、Xがn個のm次元列ベクトルx
1
,…,x
n
∈Z
m
の集合{x
1
,…,x
n
}を表し、格子∧
q
(X)が∧
q
(X):={x∈Z
m
|∃s"∈Z
n
s.t. x≡s"X mod q}であり、前記格子∧
q
(X)の双対格子∧
q
⊥
(X)が∧
q
⊥
(X):={y∈Z
m
|<x,y>≡0 mod q for all x∈∧
q
(X)}であり、β
4
T
がβ
4
の転置を表し、B
R
が所定の領域の内部を表し、
Ω
j
⊆Z
q'
m
は、Ω
j
【請求項８】
ベクトル生成部と入力量子状態特定部とを有する計算装置であって、
m,nが正整数を表し、αが正の実数であり、q,q',ζが1より大きな整数を表し、j=1,...,mであり、k'=0,...,ζであり、k"=1,...,ζであり、k'
1
,k'
2
∈{0,...,ζ}であり、0≦k'
1
＜k'
2
≦ζであり、eはネイピア数を表し、iは虚数単位を表し、Z
q
がqを法とする商環Z/qZを表し、Zが整数集合を表し、σ=αqであり、N(0,σ
2
)がZ
q
上の平均0で標準偏差σのガウス分布であり、B~
j
は格子L(B~
j
)の基底を表すm×m行列を表し、〈β
1
,β
2
〉がβ
1
とβ
2
の内積を表し、|β
1
>が縦ベクトルβ
1
を表し、a
1
,a
2
,…,a
m
∈Z
q
n
がそれぞれn次元行ベクトルを表し、Aがm×n行列
TIFF
2025121868000348.tif
31
169
を表し、εが前記ガウス分布N(0,σ
2
)に従った実数の要素を持つm次元の列ベクトルを表し、s∈Z
q
n
がn次元の列ベクトルを表し、tが
TIFF
2025121868000349.tif
13
169
を満たすm次元の列ベクトルを表し、Xがn個のm次元列ベクトルx
1
,…,x
n
∈Z
m
の集合{x
1
,…,x
n
}を表し、格子∧
q
(X)が∧
q
(X):={x∈Z
m
|∃s"∈Z
n
s.t. x≡s"X mod q}であり、Bが格子∧
q
(A
T
)の基底を表すm×m行列を表し、B
0
,...,B
ζ
が前記格子∧
q
(A
T
)の部分格子の基底を表すm×m行列を表し、B=B
0
であり、β
4
T
がβ
4
の転置を表し、
TIFF
2025121868000350.tif
12
169
が直積であり、
TIFF
2025121868000351.tif
21
169
であり、H
k"-1,k"
がB
k"
=H
【請求項９】
入力量子状態生成部と状態整列操作部と逆量子フーリエ変換部と観測部とラベル計算部と解生成部とを有する計算装置であって、
m,nが正整数を表し、q,q'が1より大きな整数を表し、j=1,...,mであり、eはネイピア数を表し、iは虚数単位を表し、Z
q
がqを法とする商環Z/qZを表し、Zが整数集合を表し、B~
j
が格子L(B~
j
)の基底を表すm×m行列を表し、b~
j,1
,...,b~
j,m
が基底B~
j
を構成するm次元のベクトルを表し、β
4
T
がβ
4
の転置を表し、
TIFF
2025121868000366.tif
12
169
が直積を表し、｜β
0
｜がβ
0
の絶対値を表し、＃βが集合βに属する要素数を表し、〈β
1
,β
2
〉がβ
1
とβ
2
の内積を表し、<β
1
|が横ベクトルβ
1
を表し、|β
1
>が縦ベクトルβ
1
を表し、a
1
,a
2
,…,a
m
∈Z
q
n
がそれぞれn次元行ベクトルを表し、Aがm×n行列
TIFF
2025121868000367.tif
31
169
を表し、s∈Z
q
n
がn次元の列ベクトルを表し、Xがn個のm次元列ベクトルx
1
,…,x
n
∈Z
m
の集合{x
1
,…,x
n
}を表し、格子∧
q
(X)が∧
q
(X):={x∈Z
m
|∃s"∈Z
n
s.t. x≡s"X mod q}であり、前記格子∧
q
(X)の双対格子∧
q
⊥
(X)が∧
q
⊥
(X):={y∈Z
m
|<x,y>≡0 mod q for all x∈∧
q
(X)}であり、Bが格子∧
q
(A
T
)の基底を表すm×m行列を表し、内挿点ベクトルu~
j,1
が0<θ<q'を満たす任意の整数θについて、
TIFF
2025121868000368.tif
14
169
かつ
TIFF
2025121868000369.tif
14
169
を満たすベクトルであり、B
【請求項１０】
入力量子状態生成部と逆量子フーリエ変換部と観測部とラベル計算部と解生成部とを有する計算装置であって、
m,nが正整数を表し、αが正の実数であり、q,q',ζが1より大きな整数を表し、j=1,...,mであり、k'=0,...,ζであり、k"=1,...,ζであり、k'
1
,k'
2
∈{0,...,ζ}であり、0≦k'
1
＜k'
2
≦ζであり、eはネイピア数を表し、iは虚数単位を表し、Z
q
がqを法とする商環Z/qZを表し、Zが整数集合を表し、σ=αqであり、N(0,σ
2
)がZ
q
上の平均0で標準偏差σのガウス分布であり、B~
j
は格子L(B~
j
)の基底を表すm×m行列を表し、〈β
1
,β
2
〉がβ
1
とβ
2
の内積を表し、<β
1
|が横ベクトルβ
1
を表し、|β
1
>が縦ベクトルβ
1
を表し、a
1
,a
2
,…,a
m
∈Z
q
n
がそれぞれn次元行ベクトルを表し、Aがm×n行列
TIFF
2025121868000377.tif
31
169
を表し、εが前記ガウス分布N(0,σ
2
)に従った実数の要素を持つm次元の列ベクトルを表し、s∈Z
q
n
がn次元の列ベクトルを表し、tが
TIFF
2025121868000378.tif
13
169
を満たすm次元の列ベクトルを表し、Xがn個のm次元列ベクトルx
1
,…,x
n
∈Z
m
の集合{x
1
,…,x
n
}を表し、格子∧
q
(X)が∧
q
(X):={x∈Z
m
|∃s"∈Z
n
s.t. x≡s"X mod q}であり、B={b
1
,...,b
m
}が格子∧
q
(A
T
)の基底を表すm×m行列を表し、b
1
,...,b
m
が基底Bの行ベクトルであり、L
j
(b
1
),...,L
j
(b
m
)が前記格子∧
q
(A
T
)=L(B)の格子点である行ベクトルb
1
（【請求項１１】以降は省略されています）
発明の詳細な説明【技術分野】
【０００１】
本発明は、量子計算技術に関する。
続きを表示（約 3,600 文字）【背景技術】
【０００２】
LWE（Learning with Errors）問題は機械学習から派生した問題で、次世代の耐量子公開鍵暗号候補にも使用されている問題である。これまでLWE問題を解くさまざまなアルゴリズムが研究されている。例えば、非特許文献１には、LWE問題を最大独立集合問題（MIS）に帰着させるアルゴリズムが開示されている。この技術は、MISを解く量子アニーリングマシン上の既存アルゴリズムと組み合わせることで、LWE問題の解法に応用できる。
【先行技術文献】
【非特許文献】
【０００３】
Yasuhito Kawano, A reduction from an LWE problem to maximum independent set problems, Scientific Reports 13:7130 (2023) DOI 10.1038/s41598-023-34366-7.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、非特許文献１に開示されたアルゴリズムは、多項式時間の帰着アルゴリズムではないため、十分な時間とメモリがあっても、非特許文献１に開示されたアルゴリズムでLWE問題を解くことは保証できない。
【０００５】
このような点に鑑み、LWE問題を効率的に解くための技術を提供する。
【課題を解決するための手段】
【０００６】
計算装置は、LWE問題を特定するための情報を用い、当該LWE問題を１次元LWE-Like問題の集合に変換し、１次元LWE-Like問題の集合を誤差付きの位相推定問題の集合に変換し、誤差付きの位相推定問題の集合を解いて、誤差付きの位相推定問題の解の集合を得、誤差付きの位相推定問題の解の集合をLWE問題の解に変換し、LWE問題の解を出力する。
【発明の効果】
【０００７】
これにより、LWE問題を効率的に解くことができる。
【図面の簡単な説明】
【０００８】
図１は、本実施形態におけるqを法とする2サンプル1次元LWE問題の解法を説明するための図である。
図２は、本実施形態におけるqを法とするmサンプルn次元LWE問題の解法を説明するための図である。
図３は、実施形態の計算装置の全体構成を例示するためのブロック図である。
図４は、実施形態のLWE帰着装置の構成を例示するためのブロック図である。
図５は、実施形態の問題変換装置の構成を例示するためのブロック図である。
図６は、実施形態の求解装置の構成を例示するためのブロック図である。
図７は、実施形態の解変換装置の構成を例示するためのブロック図である。
図８は、双対格子と内挿点ベクトルと細分点ベクトルとの関係を例示するための図である。
図９は、双対格子と内挿点ベクトルとで構成される格子を例示するための図である。
図１０は、LWE問題が構成された格子の双対格子と内挿点ベクトルとで構成される格子とラベルとの関係を例示するための図である。
図１１は、ユニタリ変換による操作内容を例示するための図である。
図１２Ａは、入力量子状態を例示するための図である。図１２Ｂは、入力量子状態に対して状態整列操作を行って得られた量子状態を例示するための図である。図１２Ｃは、入力量子状態に対して状態整列操作を行って得られた量子状態に対して2個の13次元逆量子フーリエ変換の直積を施して得られた量子状態を例示するための図である。
図１３は、観測結果とラベルとの関係を例示するための図である。
図１４は、観測結果z
1
に対応するラベルL
ｊ
(z
1
B)の値の確率分布を例示するための図である。
図１５は、実施形態の求解装置の構成を例示するためのブロック図である。
図１６Ａは、実施形態の非可換図式を例示するための図である。図１６Ｂは、実施形態の非可換図式の一部を例示するための図である。
図１７は、領域内の位置と位相との関係を例示するための図である。
図１８Ａは、入力量子状態に対して2個の13次元逆量子フーリエ変換の直積を施して得られた量子状態を例示するための図である。図１８Ｂは、観測結果MO
1
に対応するラベルL
1
(v'
1
)の値の確率分布を例示するための図である。
【発明を実施するための形態】
【０００９】
以下、本発明の実施形態を説明する。
［原理］
まず、本実施形態の原理を説明する。本実施形態では、LWE（Learning with Errors）問題を効率的に解く量子古典ハイブリッドアルゴリズムを提案する。本実施形態で提案する量子古典ハイブリッドアルゴリズムを用いれば、通常のLWE問題は効率的に解けると考えてよい。特に、以下の仮定１の下では、高い確率でLWE問題を効率的に解くことができる。
仮定１：格子の基底の行列式の絶対値と同じ体積を持つ超球は、その格子の格子点を一つだけ含む。
この仮定はGaussian Heuristicと呼ばれる最近ベクトルの長さを計算する有名なアルゴリズムでも仮定されており、ランダムな格子に関して経験的にほぼ正しいと考えられている。ただし、本実施形態において、この仮定１は必須ではなく、仮定１が厳密に成立しない場合であっても、LWE問題を効率的に解くことができる。すなわち、仮定１が厳密に成立しない場合には、毎回、必ずしも正確な解が得られるとは限らないが、同じ計算を複数回繰り返し、最大頻度の答えを選ぶことによって、誤りを排除し、正しい答えを得ることができる。言い換えると、仮定１が厳密に成立しない場合であっても、最終的な解の分布が正解に偏るのであれば（例えば、仮定１がほぼ成立するのであれば）、LWE問題を効率的に解くことができる。例えば、格子の基底の行列式の絶対値と同じ体積を持つ超球が、その超球の位置にかかわらず、その格子の格子点をほぼ一つだけ含むのであれば、LWE問題を効率的に解くことができる。なお、「ほぼ一つ」とは、例えば、0個であってもよいし、１個であってもよいし、２個であってもよいし、３個であってもよいし、４個以上であってもよい。
【００１０】
＜記号の定義＞
m,n,m',n'：m,n,m',n'は正整数である。例えば、m'はm'≧mを満たし、m'=mである。例えば、n'=1である。
α：αは正の実数である。
j：ｊは正整数であり、j=1,...,m'である。
q,q'：q,q'は１より大きな整数であり、5q/3＜q'を満たす。例えば、q,q'は素数である。
Z
q
：Z
q
はqを法とする商環Z/qZを表す。
Z：Zは整数集合を表す。
Q：Qは有理数集合を表す。
R：Rは実数集合を表す。
e：eはネイピア数を表す。
i：iは虚数単位を表す。
I
m
：I
m
はm×m単位行列を表す。
｜β
0
｜：｜β
0
｜はβ
0
の絶対値を表す。
||β
1
||：||β
1
||はβ
1
のノルムを表す。
＃β：＃βは集合βに属する要素数を表す。
det(β
3
)：det(β
3
)はβ
3
の行列式を表す。
β
4
T
：β
4
T
はβ
4
の転置を表す。
〈β
1
,β
2
〉：〈β
1
,β
2
〉はβ
1
とβ
2
の内積を表す。
<β
1
|：<β
1
|は横ベクトルβ
1
を表す。
|β
1
>：|β
1
>は縦ベクトルβ
1
を表す。
β
1
（【００１１】以降は省略されています）

関連特許