特許ウォッチ

公開番号2025012196
公報種別公開特許公報(A)
公開日2025-01-24
出願番号2023114862
出願日2023-07-13
発明の名称署名生成方法、署名検証方法、存在証明システム、通信装置、プログラム
出願人日本電信電話株式会社,国立大学法人東京大学
代理人個人,個人,個人
主分類H04L 9/32 20060101AFI20250117BHJP(電気通信技術)
要約【課題】分散型データ流通基盤における存在証明に用いることができ、署名データのサイズが小さい署名技術を提供する。
【解決手段】署名生成方法は、通信装置U₀が、通信装置U_n(n=1, …, N)から署名σ_nとメッセージhs_nと公開鍵pks_nの組(σ_n, hs_n, pks_n)を受信し、集約署名σ_Aggを生成し、メッセージm₀, m₁, …, m_Nを含むメッセージの列messagesと公開鍵pk₀, pk₁, …, pk_Nを含む公開鍵の列pubkeysとメッセージm_nと公開鍵pk_nの組(m_n, pk_n)(n=0, 1, …, N)を含むテーブルtabを生成し、集約署名σ_Agg、メッセージの列messages、公開鍵の列pubkeys、テーブルtabを含むブロックをブロックB_Lの次のブロックB_L+1としてローカルチェーンLC₀に追加する第3生成ステップを含む。
【選択図】図4
特許請求の範囲【請求項１】
ローカルチェーンを記録する複数の通信装置から構成される存在証明システムに含まれるN+1台(ただし、Nは1以上の整数）の通信装置が共同して集約署名を生成する署名生成方法であって、
U
0
を前記N+1台の通信装置のうち集約署名の生成依頼をする通信装置、U
1
, …, U
N
を前記N+1台の通信装置のうち通信装置U
0
からの集約署名の生成依頼に参加する通信装置とし、
通信装置U
0
が、記録部に記録しているローカルチェーンLC
0
を構成するブロックのうち最新のブロックB
L
のハッシュ値h
L
からメッセージm
0
を生成し、メッセージm
0
と通信装置U
0
の公開鍵pk
0
の組(m
0
, pk
0
)を通信装置U
1
, …, U
N
にブロードキャストする第１生成ステップと、
通信装置U
0
が、通信装置U
n
(n=1, …, N)からメッセージm
n
と通信装置U
n
の公開鍵pk
n
の組(m
n
, pk
n
)を受信し、メッセージhs
0
=m
0
||m
1
||…||m
N
と公開鍵pks
0
=pk
0
||pk
1
||…||pk
N
を生成し、署名σ
0
=H(hs
0
||pk
0
)
sk_0
（ただし、Hはハッシュ関数、sk
0
は通信装置U
0
の秘密鍵）を生成し、署名σ
0
とメッセージhs
0
と公開鍵pks
0
の組(σ
0
, hs
0
, pks
0
)を通信装置U
1
, …, U
N
にブロードキャストする第２生成ステップと、
通信装置U
0
続きを表示（約 4,400 文字）【請求項２】
ローカルチェーンを記録する複数の通信装置から構成される存在証明システムに含まれるN+1台(ただし、Nは1以上の整数）の通信装置が共同して集約署名を生成する署名生成方法であって、
U
0
を前記N+1台の通信装置のうち集約署名の生成依頼をする通信装置、U
1
, …, U
N
を前記N+1台の通信装置のうち通信装置U
0
からの集約署名の生成依頼に参加する通信装置とし、
m
0
を通信装置U
0
がローカルチェーンを構成するブロックのうち最新のブロックのハッシュ値に基づいて生成したメッセージ、m
n
(n=1, …, N)を通信装置U
n
が生成したメッセージ、pk
0
を通信装置U
0
の公開鍵とし、
通信装置U
0
が、メッセージm
0
, m
1
, …, m
N
に基づいて生成されるメッセージhs
0
と公開鍵pk
0
とから、署名σ
0
を生成する署名生成ステップと、
pk
n
(n=1, …, N)を通信装置U
n
の公開鍵、σ
n
(n=1, …, N)を通信装置U
n
がメッセージm
0
, m
1
, …, m
N
に基づいて生成されるメッセージhs
n
と公開鍵pk
n
とから生成した署名とし、
通信装置U
0
が、署名σ
0
, σ
1
, …, σ
N
から集約署名σ
Agg
を生成し、集約署名σ
Agg
、メッセージm
0
, m
1
, …, m
N
を含むメッセージの列messages、公開鍵pk
0
, pk
1
, …, pk
N
を含む公開鍵の列pubkeys、メッセージm
n
と公開鍵pk
n
の組(m
n
, pk
n
)(n=0, 1, …, N)を含むテーブルtabを含むブロックを前記最新のブロックの次のブロックとして前記ローカルチェーンに追加する第３生成ステップと
を含む署名生成方法。
【請求項３】
ローカルチェーンを記録する複数の通信装置から構成される存在証明システムに含まれる通信装置が集約署名を検証する署名検証方法であって、
V
0
を集約署名を検証する通信装置、U
0
を検証対象となる集約署名σ
Agg
を含むブロックB
L+1
を含むローカルチェーンLC
0
を記録部に記録している通信装置V
0
とは異なる通信装置、U
1
, …, U
N
を通信装置U
0
からの集約署名σ
Agg
の生成依頼に参加した通信装置とし、
ブロックB
L+1
は、集約署名σ
Agg
とともに、通信装置U
0
が生成したメッセージm
0
（ただし、m
0
はローカルチェーンLC
0
を構成するブロックのうちブロックB
L+1
からみて最新のブロックB
L
のハッシュ値h
L
から生成されたメッセージ）、通信装置U
1
が生成したメッセージm
1
、…、通信装置U
N
が生成したメッセージm
N
を含むメッセージの列messagesと通信装置U
0
の公開鍵pk
0
、通信装置U
1
の公開鍵pk
1
、…、通信装置U
N
のpk
N
を含む公開鍵の列pubkeysとメッセージm
n
と公開鍵pk
n
の組(m
n
, pk
n
)(n=0, 1, …, N)を含むテーブルtabを含むものとし、
通信装置V
0
が、集約署名σ
Agg
の生成に関係した通信装置U
0
, U
1
, …, U
N
の中に信頼できる通信装置が含まれているか否か判定する判定ステップと、
集約署名σ
Agg
の生成に関係した通信装置U
0
, U
1
, …, U
N
の中に信頼できる通信装置が含まれている場合には、通信装置V
0
が、テーブルtabに含まれるメッセージm
n
と公開鍵pk
n
の組(m
n
【請求項４】
ローカルチェーンを記録する複数の通信装置から構成され、その中のN+1台(ただし、Nは1以上の整数）の通信装置が共同して集約署名を生成する存在証明システムであって、
U
0
を前記N+1台の通信装置のうち集約署名の生成依頼をする通信装置、U
1
, …, U
N
を前記N+1台の通信装置のうち通信装置U
0
からの集約署名の生成依頼に参加する通信装置とし、
通信装置U
0
は、
記録部に記録しているローカルチェーンLC
0
を構成するブロックのうち最新のブロックB
L
のハッシュ値h
L
からメッセージm
0
を生成し、メッセージm
0
と通信装置U
0
の公開鍵pk
0
の組(m
0
, pk
0
)を通信装置U
1
, …, U
N
にブロードキャストする第１生成部と、
通信装置U
n
(n=1, …, N)からメッセージm
n
と通信装置U
n
の公開鍵pk
n
の組(m
n
, pk
n
)を受信し、メッセージhs
0
=m
0
||m
1
||…||m
N
と公開鍵pks
0
=pk
0
||pk
1
||…||pk
N
を生成し、署名σ
0
=H(hs
0
||pk
0
)
sk_0
（ただし、Hはハッシュ関数、sk
0
は通信装置U
0
の秘密鍵）を生成し、署名σ
0
とメッセージhs
0
と公開鍵pks
0
の組(σ
0
, hs
0
, pks
0
)を通信装置U
1
, …, U
N
にブロードキャストする第２生成部と、
通信装置U
n
【請求項５】
ローカルチェーンを記録する複数の通信装置から構成され、その中のN+1台(ただし、Nは1以上の整数）の通信装置が共同して集約署名を生成する存在証明システムに含まれる、集約署名の生成依頼をする通信装置であって、
U
0
を前記N+1台の通信装置のうち集約署名の生成依頼をする通信装置、U
1
, …, U
N
を前記N+1台の通信装置のうち通信装置U
0
からの集約署名の生成依頼に参加する通信装置とし、
ローカルチェーンLC
0
を記録する記録部と、
前記記録部に記録しているローカルチェーンLC
0
を構成するブロックのうち最新のブロックB
L
のハッシュ値h
L
からメッセージm
0
を生成し、メッセージm
0
と通信装置U
0
の公開鍵pk
0
の組(m
0
, pk
0
)を通信装置U
1
, …, U
N
にブロードキャストする第１生成部と、
通信装置U
n
(n=1, …, N)からメッセージm
n
と通信装置U
n
の公開鍵pk
n
の組(m
n
, pk
n
)を受信し、メッセージhs
0
=m
0
||m
1
||…||m
N
と公開鍵pks
0
=pk
0
||pk
1
||…||pk
N
を生成し、署名σ
0
=H(hs
0
||pk
0
)
sk_0
（ただし、Hはハッシュ関数、sk
0
は通信装置U
0
の秘密鍵）を生成し、署名σ
0
とメッセージhs
0
と公開鍵pks
0
の組(σ
0
, hs
0
, pks
0
)を通信装置U
1
, …, U
N
にブロードキャストする第２生成部と、
通信装置U
n
【請求項６】
請求項５に記載の通信装置としてコンピュータを機能させるためのプログラム。

発明の詳細な説明【技術分野】
【０００１】
本発明は、分散型データ流通基盤における存在証明技術に関する。
続きを表示（約 4,400 文字）【背景技術】
【０００２】
AIによるデータ活用が叫ばれ、データ活用のモチベーションも社会に浸透しつつある。その一方で、データ量の不足やデータ共有に対するセキュリティ上の不安などに起因し、データ活用は期待するほど進んでいない。この問題を解決するため、誰もが安全で安価に利用できるデータ流通基盤が求められている。
【０００３】
データ流通基盤には、サービス提供者など信頼できる第三者（TTP: Trusted Third Party）にすべての処理を代行させる中央集権型（Centralized)モデルと、信頼できる第三者を想定せずに参加者自らが安全性を確認する分散型(Decentralized)モデルとがある。サービス提供者によるデータの悪用などの不安からデータ共有が進まない現状を考えると、他者への信頼をベースとしない分散型データ流通基盤が望ましい。分散型データ流通基盤として、BitcoinやBlockeneのようにブロックチェーンを利用するもの（参考非特許文献１、参考非特許文献２参照）、コストや性能を改善するため有向非巡回グラフ（DAG: Directed Acyclic Graph）を元に台帳基盤を構築するもの（参考非特許文献３参照）が知られている。
【０００４】
（参考非特許文献１：Satoshi Nakamoto, “Bitcoin: A Peer-to-Peer Electronic Cash System,” https://bitcoin.org/bitcoin.pdf, 2020.）
（参考非特許文献２：Sambhav Satija, Apurv Mehra, Sudheesh Singanamalla, Karan Grover, Muthian Sivathanu, Nishanth Chandran, Divya Gupta, and Satya Lokam, “Blockene: a high-throughput blockchain over mobile devices,” Proceedings of the 14th USENIX Conference on Operating Systems Design and Implementation, USENIX Association, pp.567-582, 2020.）
（参考非特許文献３：Qin Wang, Jiangshan Yu, Shiping Chen, Yang Xiang, “SoK: Diving into DAG-based Blockchain Systems,” arXiv e-prints, 2020.）
データ流通基盤の重要な機能として、ある時刻にあるデータが存在していたことを証明する存在証明（タイムスタンプともいう）がある。分散型データ流通基盤で安全かつ効率的に存在証明を行うため、分散型データ流通基盤の利用者の中からランダムに決定された署名参加者によって存在証明を行うランダム署名が提案されている（非特許文献１参照）。ランダム署名では、分散型データ流通基盤の利用者がそれぞれ存在証明に必要なデータをローカルチェーンとして管理する。ローカルチェーンは、ある時刻においてあるデータが存在していたことを示すためのデータであるブロックが時間的な前後関係がわかるように関連付けられたブロックの列である。ブロックの関連付けに用いるデータであるリンクには、ハッシュ値を用いる。具体的には、ローカルチェーンに含まれるあるブロックは当該ブロックからみて最新のブロックのハッシュ値をリンクとして含む。また、ローカルチェーンは他の利用者に公開される。
【先行技術文献】
【非特許文献】
【０００５】
大橋盛徳, 張一凡, 細井琢朗, 松浦幹太, “DAGベース分散タイムスタンプ手法の検討,” 情報処理学会研究報告, コンピュータセキュリティ(CSEC), 2023-CSEC-100, Vol.67, pp.1-7, 2023.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ランダム署名では、複数の利用者が共同して署名する。そのため、利用者の増加に伴い、ブロックに含まれる署名データのサイズが大きくなり、分散型データ流通基盤における通信量が増加するという問題があった。
【０００７】
そこで本発明では、分散型データ流通基盤における存在証明に用いることができ、署名データのサイズが小さい署名技術を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の一態様は、ローカルチェーンを記録する複数の通信装置から構成される存在証明システムに含まれるN+1台(ただし、Nは1以上の整数）の通信装置が共同して集約署名を生成する署名生成方法であって、U
0
を前記N+1台の通信装置のうち集約署名の生成依頼をする通信装置、U
1
, …, U
N
を前記N+1台の通信装置のうち通信装置U
0
からの集約署名の生成依頼に参加する通信装置とし、通信装置U
0
が、記録部に記録しているローカルチェーンLC
0
を構成するブロックのうち最新のブロックB
L
のハッシュ値h
L
からメッセージm
0
を生成し、メッセージm
0
と通信装置U
0
の公開鍵pk
0
の組(m
0
, pk
0
)を通信装置U
1
, …, U
N
にブロードキャストする第１生成ステップと、通信装置U
0
が、通信装置U
n
(n=1, …, N)からメッセージm
n
と通信装置U
n
の公開鍵pk
n
の組(m
n
, pk
n
)を受信し、メッセージhs
0
=m
0
||m
1
||…||m
N
と公開鍵pks
0
=pk
0
||pk
1
||…||pk
N
を生成し、署名σ
0
=H(hs
0
||pk
0
)
sk_0
（ただし、Hはハッシュ関数、sk
0
は通信装置U
0
の秘密鍵）を生成し、署名σ
0
とメッセージhs
0
と公開鍵pks
0
の組(σ
0
, hs
0
, pks
0
)を通信装置U
1
, …, U
N
にブロードキャストする第２生成ステップと、通信装置U
0
が、通信装置U
n
(n=1, …, N)から署名σ
n
とメッセージhs
n
と公開鍵pks
n
【０００９】
本発明の一態様は、ローカルチェーンを記録する複数の通信装置から構成される存在証明システムに含まれる通信装置が集約署名を検証する署名検証方法であって、V
0
を集約署名を検証する通信装置、U
0
を検証対象となる集約署名σ
Agg
を含むブロックB
L+1
を含むローカルチェーンLC
0
を記録部に記録している通信装置V
0
とは異なる通信装置、U
1
, …, U
N
を通信装置U
0
からの集約署名σ
Agg
の生成依頼に参加した通信装置とし、ブロックB
L+1
は、集約署名σ
Agg
とともに、通信装置U
0
が生成したメッセージm
0
（ただし、m
0
はローカルチェーンLC
0
を構成するブロックのうちブロックB
L+1
からみて最新のブロックB
L
のハッシュ値h
L
から生成されたメッセージ）、通信装置U
1
が生成したメッセージm
1
、…、通信装置U
N
が生成したメッセージm
N
を含むメッセージの列messagesと通信装置U
0
の公開鍵pk
0
、通信装置U
1
の公開鍵pk
1
、…、通信装置U
N
のpk
N
を含む公開鍵の列pubkeysとメッセージm
n
と公開鍵pk
n
の組(m
n
, pk
n
)(n=0, 1, …, N)を含むテーブルtabを含むものとし、通信装置V
0
が、集約署名σ
Agg
の生成に関係した通信装置U
0
, U
1
, …, U
N
の中に信頼できる通信装置が含まれているか否か判定する判定ステップと、集約署名σ
Agg
の生成に関係した通信装置U
0
, U
1
, …, U
N
の中に信頼できる通信装置が含まれている場合には、通信装置V
0
が、テーブルtabに含まれるメッセージm
n
と公開鍵pk
n
の組(m
n
, pk
n
)(n=0, 1, …, N)からハッシュ値h
n
=H(m
n
||pk
n
【発明の効果】
【００１０】
本発明によれば、分散型データ流通基盤における存在証明に用いることができる署名に必要となるデータサイズを小さくすることが可能となる。
【図面の簡単な説明】
（【００１１】以降は省略されています）

関連特許