ブラウザよりも高速アクセス！
25 関係: 健全性、合成数、対話型証明系、一方向性関数、ハミルトン路、ハミルトン閉路問題、パスワード、ビットコミットメント、デジタル署名、命題、グラフ同型、グラフ理論、シャフィ・ゴールドワッサー、公開鍵暗号、個人情報、素因数、素因数分解、証明、離散対数、Fiat-Shamirヒューリスティック、NP完全問題、PCP (計算複雑性理論)、暗号理論、数学、1985年。
健全性
健全性（けんぜんせい、Soundness）は、論証が次の属性を持つことと同値である。.
新しい！!: ゼロ知識証明と健全性 · 続きを見る »
合成数
合成数（ごうせいすう、Composite number）は、自然数で、1とその数自身以外の約数を持つ数である。2つ以上の素数の積で表すことのできる自然数と定義してもよい。たとえば15は1と15自身以外に3と5を約数に持つ（または 3×5 と素数の積で表される）ので合成数である。9や25など素数を2乗した数は1つしか素因数をもたないが、9.
新しい！!: ゼロ知識証明と合成数 · 続きを見る »
対話型証明系
対話型証明系（たいわがたしょうめいけい、Interactive proof system）は、2者間のメッセージ交換によって計算をモデル化した計算模型であり、計算複雑性理論で使われる。2者とは、検証者と証明者と呼ばれ、与えられた文字列がある形式言語に属するか否かをメッセージのやり取りによって決定するものである。証明者は無限の計算資源を持つ全能の計算能力を持つが、検証者の方は限定的な計算能力を持つ。メッセージのやり取りは、検証者が証明者による証明に納得して正しいと判断するまで続けられる。 対話型証明系は、必ず次のような2つの要求に従う。.
新しい！!: ゼロ知識証明と対話型証明系 · 続きを見る »
一方向性関数
一方向性関数（いちほうこうせいかんすう、one-way function）とは、簡単に計算できるが逆関数の計算は非常に困難である関数を指す。暗号理論などで用いられる概念である。素因数分解問題の困難性を用いたものが代表的。 下では、単に「多項式時間アルゴリズム」と書いたら「平均多項式時間確率アルゴリズム」を指す。.
新しい！!: ゼロ知識証明と一方向性関数 · 続きを見る »
ハミルトン路
ハミルトン路とは、グラフ上の全ての頂点を 1 度ずつ通る路のこと。特に、グラフ上の全ての頂点を 1 度ずつ通る閉路はハミルトン閉路という。また、ハミルトン閉路を含むグラフのことをハミルトングラフといい、ハミルトン路は含むがハミルトン閉路は含まないようなグラフのことを準ハミルトングラフという。 与えられたグラフがハミルトン路を含むかどうか判定する問題は、NP完全。与えられたグラフがハミルトングラフかどうか判定する問題については、ハミルトン閉路問題を参照のこと。.
新しい！!: ゼロ知識証明とハミルトン路 · 続きを見る »
ハミルトン閉路問題
ハミルトン閉路問題（ハミルトンへいろもんだい）とは、与えられたグラフについて、全ての頂点を一度だけ通る閉路が存在するかどうか調べる問題である。名称はこの問題を最初に研究した数学者ウィリアム・ローワン・ハミルトンの名に因む。.
新しい！!: ゼロ知識証明とハミルトン閉路問題 · 続きを見る »
パスワード
パスワード（）とは、一般的に合言葉（あいことば）を指すが、特にコンピュータ関連で使用する場合は、特定の機能を使用する際に認証を得るため入力する文字及び数字の羅列を指す。多くの場合、その利用者が本人であることを確認するもので、その利用者のみが知る文字列を用いる。.
新しい！!: ゼロ知識証明とパスワード · 続きを見る »
ビットコミットメント
ビットコミットメント、コミットメント方式とは、暗号理論におけるプロトコルである。ビットコミットメントを用いることで、ユーザーは値を秘密裏にコミットすることができる。また、ユーザーは後にコミットされた値を明らかにすることが可能である。 コミットメント方式を想像するには以下の喩えが有効である。送信者は値を書いた紙を箱に入れカギを掛け、その箱を受信者に送る。箱の中身は受信者には見えないし、送信者が鍵を送らなければ錠前を開けることもできない。また受信者が箱を持っているので送信者が箱の中身を改ざんすることも不可能である。コミットメント方式は暗号プロトコルと密接な関係を持っている。とくにゼロ知識証明やマルチパーティ計算、また電子マネーや電子投票 に用いられている。.
新しい！!: ゼロ知識証明とビットコミットメント · 続きを見る »
デジタル署名
デジタル署名（デジタルしょめい）とは、書面上の手書き署名のセキュリティ特性を模倣するために用いられる公開鍵暗号技術の一種である。.
新しい！!: ゼロ知識証明とデジタル署名 · 続きを見る »
命題
命題（めいだい、proposition）とは、論理学において判断を言語で表したもので、真または偽という性質をもつもの。また数学で、真偽の判断の対象となる文章または式。定理または問題のこと。西周による訳語の一つ。 厳密な意味での命題の存在は、「意味」の存在と同様に、疑問を投げかける哲学者もいる。また、「意味」の概念が許容される場合にあっても、その本質は何であるかということにはなお議論のあるところである。古い文献では、語の集まりあるいはその語の集まりの表す「意味」という意味で命題という術語を用いているかどうかということが、つねに十分に明らかにされているわけではなかった。 現在では、論争や存在論的な含みを持つことを避けるため、ある解釈の下で（真か偽のいずれであるかという）真理の担い手となる記号列自体について述べる時は、「命題」という代わりに「文 (sentence)」という術語を用いる。ストローソンは「言明 ("statement")」 という術語を用いることを提唱した。.
グラフ同型
ラフ同型（ぐらふどうけい）とはグラフ理論における概念の一つである。.
新しい！!: ゼロ知識証明とグラフ同型 · 続きを見る »
グラフ理論
ラフ理論（グラフりろん、graph theory）は、ノード（節点・頂点）の集合とエッジ（枝・辺）の集合で構成されるグラフに関する数学の理論である。グラフ (データ構造) などの応用がある。.
新しい！!: ゼロ知識証明とグラフ理論 · 続きを見る »
シャフィ・ゴールドワッサー
ャフリラ・ゴールドワッサー（Shafrira Goldwasser、、1958年 - ）は、マサチューセッツ工科大学の電気工学と計算機科学の教授で、イスラエルのワイツマン科学研究所の数学の教授。通称はシャフィ (Shafi)。.
新しい！!: ゼロ知識証明とシャフィ・ゴールドワッサー · 続きを見る »
公開鍵暗号
公開鍵暗号（こうかいかぎあんごう、Public-key cryptography）とは、暗号化と復号に別個の鍵（手順）を用い、暗号化の鍵を公開すらできるようにした暗号方式である。 暗号は通信の秘匿性を高めるための手段だが、それに必須の鍵もまた情報なので、鍵を受け渡す過程で盗聴されてしまうというリスクがあった。共通鍵を秘匿して受け渡すには（特使が運搬するというような）コストもかかり、一般人が暗号を用いるための障害であった。この問題に対して、暗号化鍵の配送問題を解決したのが公開鍵暗号である。.
新しい！!: ゼロ知識証明と公開鍵暗号 · 続きを見る »
個人情報
個人情報とは、任意の一人の個人に関する情報であり、かつその情報に含まれる記述等によって特定の個人を識別できるものを指す。英語では personally identifiable information (PII) もしくは sensitive personal information (SPI), より一般には personal data と呼ばれる。.
新しい！!: ゼロ知識証明と個人情報 · 続きを見る »
素因数
数学において、ある自然数の素因数（そいんすう、prime factor）とは、その約数になる素数のことである。ある数の素因数を求めてその積の形で表すことを素因数分解という。例えば 60 は 22×3×5 と素因数分解されるので 60 の相異なる素因数は 2, 3, 5 の3つである。また、7 は素数であるため、7 の素因数は 7 自身のみとなる。素因数のことを素因子（そいんし）、素因数分解のことを素因子分解ということもある。 2つの自然数が互いに素であることと、2つの自然数が共通の素因数を持たないことは同値である。なお 1 は素因数を持たない数であり、したがって 1 は全ての（1 自身を含めた）自然数と互いに素である。 自然数の素因数分解の結果は、素因数を掛ける順番の違いを除けば一意的に決まる。この事実は算術の基本定理と呼ばれている。 スミス数は自然数であって、その素因数の数字の和と各桁の数字の和が等しい数のことである。また、ルース＝アーロン・ペアは連続する自然数の組であって、それぞれの素因数の和が互いに等しいような二数のことである。.
新しい！!: ゼロ知識証明と素因数 · 続きを見る »
素因数分解
素因数分解 (そいんすうぶんかい、prime factorization) とは、ある正の整数を素数の積の形で表すことである。ただし、1 に対する素因数分解は 1 と定義する。 素因数分解には次のような性質がある。.
新しい！!: ゼロ知識証明と素因数分解 · 続きを見る »
証明
証明（しょうめい）とは、ある事柄が真理もしくは事実であることを明らかにすること。また、その内容。.
離散対数
代数学における離散対数（りさんたいすう、discrete logarithm）とは、通常の対数の群論的な類似物である。 離散対数を計算する問題は整数の因数分解(en:integer factorization)と以下の点が共通している：.
新しい！!: ゼロ知識証明と離散対数 · 続きを見る »
Fiat-Shamirヒューリスティック
Fiat-Shamirヒューリスティックは、honest verifierかつパブリックコインな対話証明プロトコルをハッシュ関数を用いる事で証明文作成プロトコルや電子署名方式に変換する方法。 対話証明プロトコルから証明文作成プロトコルを作成する方法は以下の通り: 対話証明プロトコルにおける、verifierからの送信メッセージ(チャレンジ)の代わりに、その時点までのverifierのviewのハッシュ値を用いる。証明プロトコル終了時点における、verifierのviewと送信したハッシュ値の組の列が証明文である。 より厳密には、対話証明プロトコル(P(w),V)(x)から、作られた証明文作成プロトコルは以下の通り。 こうして作成された証明文vが正当なものであるかどうかを検証するには、まずverifierのviewのハッシュ値からチャレンジを作成し、次に証明プロトコルとしての検証操作をおこなう。証明プロトコルとしての検証を通れば証明文は正当であるとみなす。 対話証明プロトコルから署名方式を作成する方法もほぼ同様である。 チャレンジとして、viewのハッシュ値の代わりに、viewと署名したいメッセージとのコンカチネーションのハッシュ値を用いる。 証明プロトコル終了時点における、verifierのviewとハッシュ値の組の列が署名文である。 より厳密には、対話証明プロトコル(P(w),V)(x)から作られた署名アルゴリズムは以下の通り。 こうして作成された署名文vが正当なものであるかどうかを検証するには、まずverifierのviewと署名したいメッセージとのコンカチネーションのハッシュ値からチャレンジを作成し、次に証明プロトコルとしての検証操作をおこなう。証明プロトコルとしての検証を通れば署名文は正当であるとみなす。.
新しい！!: ゼロ知識証明とFiat-Shamirヒューリスティック · 続きを見る »
NP完全問題
NP完全（な）問題（エヌピーかんぜん（な）もんだい、NP-complete problem）とは、(1) クラスNP（Non-deterministic Polynomial）に属する決定問題（言語）で、かつ (2) 任意のクラスNPに属する問題から多項式時間還元（帰着）可能なもののことである。条件 (2) を満たす場合は、問題の定義が条件 (1) を満たさない場合にも、NP困難な問題とよびその計算量的な困難性を特徴づけている。多項式時間還元の推移性から、クラスNPに属する問題で、ある一つのNP完全問題から多項式時間還元可能なものも、またNP完全である。現在発見されているNP完全問題の証明の多くはこの推移性によって充足可能性問題などから導かれている。充足可能性問題がNP完全であることは1971年、スティーブン・クック（Stephen Cook (1971).
新しい！!: ゼロ知識証明とNP完全問題 · 続きを見る »
PCP (計算複雑性理論)
計算複雑性理論における PCP とは、確率的検査可能証明（probabilistically checkable proof）系を持つ決定問題の複雑性クラスである。.
新しい！!: ゼロ知識証明とPCP (計算複雑性理論) · 続きを見る »
暗号理論
暗号理論（あんごうりろん）の記事では暗号、特に暗号学に関係する理論について扱う。:Category:暗号技術も参照。.
新しい！!: ゼロ知識証明と暗号理論 · 続きを見る »
数学
数学（すうがく、μαθηματικά, mathematica, math）は、量（数）、構造、空間、変化について研究する学問である。数学の範囲と定義については、数学者や哲学者の間で様々な見解がある。.
1985年
この項目では、国際的な視点に基づいた1985年について記載する。.
新しい！!: ゼロ知識証明と1985年 · 続きを見る »
