(57)【要約】本発明の技術は、既に知られている暗号化技術の新たな利用法を含む。本技術は、情報を安全に共有するコンピュータベースの方法を、特に、準同形暗号化での秘密キー／公開キー・パラダイムに頼る非対称で安全な計算方法を伴う。この方法、及び本発明におけるプログラムされたコンピュータ装置は、商業的に有用であり、今までは可能ではなかった数学的概念を、サービスまたは作業に適用する。この方法の、クラウド・コンピューティング・パラダイム内の応用を提示する。本発明における方法及び装置の応用は広範囲にわたり：価格交渉の何らかの状況が予期される不動産または自動車のような売買取引；株式市場；法的和解；賃金交渉；競売、及び他の種類の複雑な金融取引を含むが、それらに限定されない。
2018531431.tif 000002
【特許請求の範囲】
【請求項１】
第１の当事者と第２の当事者とが安全に入札を交換する方法であって、
前記第１の当事者が第１の入札を生成するステップと、
前記第１の当事者が、第１組の公開キー及び第１組の秘密キーを生成するステップと、
前記第１の当事者が、前記第１の入札を前記第１組の公開キーで暗号化し、これにより第１の暗号化した入札を生成するステップと、
前記第２の当事者が第２の入札を生成するステップと、
前記第２の当事者が、第２組の公開キー及び第２組の秘密キーを生成するステップと、
前記第２の当事者が、前記第２の入札を前記第２組の公開キーで暗号化し、これにより第２の暗号化した入札を生成するステップと、
前記第１の当事者が、前記第１の暗号化した入札及び前記第１組の公開キーを、前記第２の当事者に送信するステップと、
前記第２の当事者が、前記第２の暗号化した入札及び前記第２組の公開キーを、前記第１の当事者に送信するステップと、
前記第１の当事者が、前記第１組の秘密キーを前記第２の当事者に送信するステップと、
前記第２の当事者が、前記第２組の秘密キーを前記第１の当事者に送信するステップと、
前記第１の当事者が、前記第２の暗号化した入札を、前記第２組の秘密キーで暗号解読し、これにより前記第２の入札を明示するステップと、
前記第２の当事者が、前記第１の暗号化した入札を、前記第１組の秘密キーで暗号解読し、これにより前記第１の入札を明示するステップと
を含む方法。
【請求項２】
前記第１の当事者が、前記第１の公開キー及び前記第１の秘密キーを生成するステップが、素因数分解、離散対数問題、及びＲＳＡ暗号化、のうちの１つに基づくアルゴリズムを用いる、請求項１に記載の方法。
【請求項３】
請求項１に記載の方法を実行するように構成されたコンピュータ装置。
【請求項４】
第１の当事者と第２の当事者との間で、実際情報を公表せずに情報を安全に比較する方法であって、
前記第１の当事者が、第１のデータから第１指紋を作成するステップと、
前記第２の当事者が、第２のデータから第２指紋を作成するステップと、
前記第１の当事者が、第１組のＧＭキーを、関連する公開キー及び秘密キーと共に生成するステップと、
前記第１の当事者が、前記第１指紋を前記公開キーで暗号化して、第１の暗号化した指紋を作成するステップと、
前記第１の当事者が、前記公開キーを前記第２の当事者に送信するステップと、
前記第２の当事者が、前記第２指紋を前記公開キーで暗号化して、第２の暗号化した指紋を作成するステップと、
前記第１の当事者が、前記第１の暗号化した指紋を前記第２の当事者に送信するステップと、
前記第２の当事者が、前記第１の暗号化した指紋及び前記第２の暗号化した指紋に対してＸＯＲ演算を実行し、これにより暗号化した指紋ＸＯＲを作成するステップと、
前記第２の当事者が、前記暗号化した指紋ＸＯＲをスクランブルし、これにより、暗号化してスクランブルした指紋ＸＯＲを作成するステップと、
前記第２の当事者が、前記暗号化してスクランブルした指紋ＸＯＲを、前記第１の当事者に送信するステップと、
前記第１の当事者が、前記暗号化したスクランブルした指紋ＸＯＲを暗号解読して、スクランブルされた前記暗号化した指紋ＸＯＲ中のビット数を数え、これにより、前記第１指紋と前記第２指紋との類似性のレベルを知るステップと
を含む方法。
【請求項５】
第１の当事者と第２の当事者との間で、実際情報を公表せずに情報を安全に比較する方法であって、
前記第１の当事者が、第１のデータから第１指紋を作成するステップと、
前記第２の当事者が、第２のデータから第２指紋を作成するステップと、
前記第１の当事者が、第１組のＧＭキーを、関連する公開キー及び秘密キーと共に生成するステップと、
前記第１の当事者が、前記第１指紋を前記公開キーで暗号化して第１の暗号化した指紋を作成し、該第１の暗号化した指紋を、第１の安全なクラウド・アカウントにアップロードするステップと、
前記第２の当事者が、前記第２指紋を前記公開キーで暗号化して第２の暗号化した指紋を作成し、該第２の暗号化した指紋を、第２の安全なクラウド・アカウントにアップロードするステップと、
次に、前記第１の当事者が、前記第１のクラウド・アカウント上の前記第１の暗号化した指紋に対する読出し特権を、前記第２の当事者に与えるステップと、
前記第２の当事者が、前記第１の暗号化した指紋及び前記第２の暗号化した指紋に対してＸＯＲ演算を実行し、これにより、暗号化した指紋ＸＯＲを前記第２のクラウド・アカウント内に作成するステップと、
前記第２の当事者が、前記暗号化した指紋ＸＯＲをスクランブルし、これにより、暗号化してスクランブルした指紋ＸＯＲを前記第２のクラウド・アカウント内に作成するステップと、
前記第２の当事者が、前記暗号化してスクランブルした指紋ＸＯＲに対する読出し特権を、前記第１の当事者に与えるステップと、
前記第１の当事者が、前記暗号化してスクランブルした指紋ＸＯＲに対してプログラムを実行して、オン状態にされたビットの数を評価して、前記ビットの数を暗号化して前記第１のクラウド・アカウント内に記憶するステップと、
前記第１の当事者が、前記暗号化したビットの数を、前記第１のクラウド・アカウントからダウンロードし、該第１の当事者のコンピュータ上で暗号解読し、これにより前記第１指紋と前記第２指紋との類似性を知るステップと
を含む方法。
【請求項６】
第１の当事者と第２の当事者との間で、実際情報を公表せずに情報を安全に比較する方法であって、
前記第１の当事者が、第１のデータから第１指紋を作成するステップと、
前記第２の当事者が、第２のデータから第２指紋を作成するステップと、
前記第１の当事者が、第１組のＧＭキーを、関連する公開キー及び秘密キーと共に生成するステップと、
前記第１の当事者が、前記第１指紋を前記公開キーで暗号化して、第１の暗号化した指紋を作成するステップと、
前記第１の当事者が、前記公開キーを前記第２の当事者に送信するステップと、
前記第２の当事者が、前記第２指紋を前記公開キーで暗号化して、第２の暗号化した指紋を作成するステップと、
前記第１の当事者が、前記第１の暗号化した指紋を前記第２の当事者に送信するステップと、
前記第２の当事者が、前記第１の暗号化した指紋及び前記第２の暗号化した指紋に対してＸＯＲ演算を実行し、これにより、暗号化した指紋ＸＯＲを作成するステップと、
前記第２の当事者が、前記暗号化した指紋ＸＯＲをスクランブルし、これにより、暗号化してスクランブルした指紋ＸＯＲを作成するステップと、
前記第２の当事者が、第２組のＥＳＡキーを、関連する第２組の公開キー及び第２組の秘密キーと共に生成するステップと、
次に、前記第２の当事者が、前記暗号化してスクランブルした指紋ＸＯＲを、前記第２組の公開キーで暗号化して、二重に暗号化してスクランブルした指紋ＸＯＲを作成するステップと、
前記第２の当事者が、前記二重に暗号化してスクランブルした指紋ＸＯＲを、前記第１の当事者に送信するステップと、
前記第２の当事者が、前記第２組の秘密キーを前記第１の当事者に送信するステップと、
前記第１の当事者が、前記二重に暗号化してスクランブルした指紋ＸＯＲを、前記第２組の秘密キーで暗号解読し、前記暗号化してスクランブルした指紋ＸＯＲ中のビットの数を数え、これにより前記第１指紋と前記第２指紋との類似性を知るステップと
を含む方法。
【請求項７】
第１の当事者と第２の当事者との間で、実際情報を公表せずに情報を安全に比較する方法であって、
前記第１の当事者と前記第２の当事者とが、それぞれの第１指紋と第２指紋とを互いに交換するステップと、
前記第１の当事者が、請求項４に記載の方法を用いて、前記第１指紋と前記第２指紋との第１ＸＯＲ値を計算するステップと、
前記第２の当事者が、請求項４に記載の方法を用いて、前記第１指紋と前記第２指紋との第２ＸＯＲ値を計算するステップと、
前記第１の当事者が第１組のＲＳＡキーを生成するステップと、
前記第２の当事者が第２組のＲＳＡキーを生成するステップと、
前記第１の当事者が、前記第１ＸＯＲ値を暗号化し、これにより第１の暗号化したＸＯＲ値を作成するステップと、
前記第２の当事者が、前記第２ＸＯＲ値を暗号化し、これにより第２の暗号化したＸＯＲ値を作成するステップと、
前記第１の当事者が、前記第１の暗号化したＸＯＲ値を前記第２の当事者に送信するステップと、
前記第２の当事者が、前記第２の暗号化したＸＯＲ値を前記第１の当事者に送信するステップと、
前記第１の当事者が、第１組の秘密キーを用いて前記第２の暗号化したＸＯＲ値を暗号解読し、これにより前記第２ＸＯＲ値のコピーを明示するステップと、
前記第２の当事者が、第２組の秘密キーを用いて前記第１の暗号化したＸＯＲ値を暗号解読し、これにより前記第１ＸＯＲ値のコピーを明示するステップと、
前記第１の当事者が、前記第２ＸＯＲ値のコピーが、元の前記第２ＸＯＲ値と同じであるか否かをチェックして確かめるステップと、
前記第２の当事者が、前記第１ＸＯＲ値のコピーが、元の前記第１ＸＯＲ値と同じであるか否かをチェックして確かめるステップと
を含む方法。
【請求項８】
第１の当事者と第２の当事者との間で、実際情報を公表せずに情報を安全に比較する方法であって、
前記第１の当事者が、第１組のＲＳＡキー、及び第１ランダム・ビット・パディング及び第２ランダム・ビット・パディングを生成するステップと、
前記第２の当事者が、第２組のＲＳＡキー、及び第３ランダム・ビット・パディング及び第４ランダム・ビット・パディングを生成するステップと、
前記第１の当事者が、前記第１ランダム・ビット・パディング及び前記第２ランダム・ビット・パディングを暗号化し、これにより第１の暗号化したランダム・ビット・パディング及び第２の暗号化したランダム・ビット・パディングを作成するステップと、
前記第２の当事者が、前記第３ランダム・ビット・パディング及び前記第４ランダム・ビット・パディングを暗号化し、これにより第３の暗号化したランダム・ビット・パディング及び第４の暗号化したランダム・ビット・パディングを作成するステップと、
前記第１の当事者が、前記第１の暗号化したランダム・ビット・パディング及び前記第２の暗号化したランダム・ビット・パディングを、前記第２の当事者に送信するステップと、
前記第２の当事者が、前記第３の暗号化したランダム・ビット・パディング及び前記第４の暗号化したランダム・ビット・パディングを、前記第１の当事者に送信するステップと、
前記第１の当事者が、第１指紋を前記第１ランダム・ビット・パディングと併合し、該第１指紋を前記第２ランダム・ビット・パディングと併合して、２つの第１パディング付き指紋のそれぞれを作成するステップと、
前記第２の当事者が、第２指紋を前記第３ランダム・ビット・パディングと併合し、該第２指紋を前記第４ランダム・ビット・パディングと併合して、２つの第２パディング付き指紋のそれぞれを作成するステップと、
前記第１の当事者が、請求項４に記載の方法を用いて、前記２つの第１パディング付き指紋の一方と、前記２つの第２パディング付き指紋の一方との第１ＸＯＲ値を計算するステップと、
前記第２の当事者が、請求項４に記載の方法を用いて、前記２つの第１パディング付き指紋の他方と、前記２つの第２パディング付き指紋の他方との第２ＸＯＲ値を計算するステップと、
前記第１の当事者と前記第２の当事者とが、それぞれの秘密キーの組を交換するステップと、
前記第１の当事者が、前記第２の当事者の秘密キーの組を用いて、前記第３の暗号化したランダム・ビット・パディング及び前記第４の暗号化したランダム・ビット・パディングを暗号解読するステップと、
前記第２の当事者が、前記第１の当事者の秘密キーの組を用いて、前記第１の暗号化したランダム・ビット・パディング及び前記第２の暗号化したランダム・ビット・パディングを暗号解読するステップと、
前記第１の当事者及び前記第２の当事者が共に、前記第１ランダム・ビット・パディング及び前記第２ランダム・ビット・パディングと、前記第３ランダム・ビット・パディング及び前記第４ランダム・ビット・パディングとの新たなＸＯＲ値を計算するステップと、
前記第１の当事者が、前記新たなＸＯＲ値が、元の前記第１ＸＯＲ値及び元の前記第２ＸＯＲ値と同じであるか否かをチェックして確認するステップと、
前記第２の当事者が、前記新たなＸＯＲ値が、元の前記第１ＸＯＲ値及び元の前記第２ＸＯＲ値と同じであるか否かをチェックして確認するステップと
を含む方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書中に説明する技術は、一般に情報の安全性を共有する方法に関するものであり、特に、準同形暗号化を伴う秘密キー（秘密鍵）／公開キー（公開鍵）・パラダイムに頼る非対称で安全な計算方法に関するものである。
【背景技術】
【０００２】
商業及び生活の多数の局面において、２者以上の当事者が、自分が知っていることどうしを、その情報を実際に公表せずに比較することが有利である。例として、あなた及びあなたの隣人が、どちらがより多額の金を稼いでいるかを知りたいとすれば：あなたの給料について何らかのことを公表せずにこのことができるであろうか？こうした例は多数存在する。家を買いたいが、その所有者が価格のリストを作成しないものとする。あなたが進んで支払う額についてのこと以上のことを所有者に告げずに、そして所有者が、あなたが進んで支払う最高額よりも自分が進んで受け入れる額が少ないこと以外のことを所有者が公表せずに、あなたが出すつもりの最高額が、所有者が受け入れるつもりの最低額より多いか否かがわかるであろうか？
【０００３】
スポーツチームが他のチームと選手どうしをトレードしたいものとする。これら２チームが、何らかの選手名を開示せずに、まず希望が一致するか否か、即ち、第１チームの選手を行かせて第２チームが雇用したいか否かを決定することができるであろうか？
【０００４】
２つの当事者が何かに（１回）入札したいが、いずれの当事者も「先発者利益」を失いたくないものとする。即ち、一方が最初に入札すれば、他方は必要最低限だけ上回る額を提示して落札することができる。何らかの第三者に頼らずに、これら２つの当事者が、どちらかにこうした利益を得させることなしに、入札を（電子的に）共有することができるであろうか？
【０００５】
化学の分野では、２つの当事者が既知の組成の分子の集合を有する場合、当事者のいずれかが、(a)これらの分子のいずれかが同一であるか否か、あるいは(b)２つの集合体がどれほど類似しているかを、実際の分子名についての何らかの情報を公表せずに知ることができるであろうか？例えば、２つの会社が、例えば、化合物を取引することによって両社の価値を高める目的で、それぞれの集合体を比較したいが、各社が実際に有するものを取引先の外部に公表したくないことがある。他のシナリオでは、小規模なバイオテクノロジー（生命工学）会社が、ある疾患に対して有効性のある何らかの化合物を作製しており、この化合物を大手の製薬会社に使用許諾したい：一旦、この大手会社が、このバイオテクノロジー会社の化合物を見ると、この大手会社はこれらの化合物を自社で作製しようとするだけのことがある。バイオテクノロジー会社が特許権保護を出願していても、大手会社はそれに対処するのに十分な資力を有することができる。こうしたより小さい会社が、自分自身の化合物の正体を公表せずに、これらの化合物が、大手が自社内に有するものと完全に異なることについて、大手会社を納得させることができるであろうか？
【０００６】
こうした状況の他の異形では、ある会社が、自社のデータセット中の分子毎に一連の特性、例えば標準的な一連のキナーゼに対する活性を知っているものとする。この会社が、他社の集合体を検査して、同様なプロファイル（外観）を有するが異なる分子組成を有する分子を発見することが、いずれかの側が自社の分子または自社のキナーゼ・プロファイルを公表せずにできるであろうか？あるいは逆に：第１社が、自分自身のデータセット中の関心分子と化学的に同様であるが、ラジカル的に異なるキナーゼ・プロファイルを有する分子を、第２社の集合体中に見つけることができるであろうか？
【０００７】
最後に、製薬業界内では、測定または計算した既知の分子の特性に基づいて予測モデルを構築する多大な努力がなされている。分子または測定した特性のいずれかを公表せずに、こうしたモデルを社外の他者と共有することができるであろうか？２社が、この例でも主要事項、即ち分子構造データの発表なしに、自社のデータどうしを組み合わせて、両社が使用することができ、いずれかの社が独自に作成することができるものより良いモデルを構築することができるであろうか？
【０００８】
従って、取引に関係する２つの当事者が、その取引を進めるか否かを決定するために十分な当事者毎の情報を公表するだけで、いずれかの当事者のデータに歩み寄らない方法で、所有するデータを安全に共有することを可能にする方法の必要性が存在する。
【０００９】
本明細書中の背景の説明は、上記技術の状況を説明するために含める。このことは、参照する題材のいずれもが、本明細書に添付する請求項のいずれの優先日においても、公開され、既知であり、あるいは共通の一般知識の一部であったことを認めるものとして解釈するべきではない。
【００１０】
本願の発明の詳細な説明及び特許請求の範囲全体を通して、「具える」、及び「具えている」、「具えた」のようなその変形は、他の追加物、構成要素、数値、またはステップを排除することを意図していない。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】Craig Gentry, “A fully homomorphic encryption scheme”, Ph.D. thesis, Stanford Univ. (2009)
【発明の概要】
【課題を解決するための手段】
【００１２】
本発明は、２つまたは複数の当事者間での情報の安全な共有に応えるものである。特に、本発明は、情報を安全に共有するためのコンピュータベースの方法を含む。本発明は、情報の安全な共有を実行する装置をさらに含む。本発明の装置及びプロセスは、特に交渉取引に応用可能である。
【００１３】
本発明は、本明細書中に記載する方法のいずれをも提供し、これらの方法は、本明細書に添付する特許請求の範囲として表現するものを含み、これらの方法を実行するための装置を提供し、並びにこれらの方法を実行するための命令を符号化したコンピュータ可読媒体を提供する。
【図面の簡単な説明】
【００１４】
【図１】同時入札を管理する方法を示す図であり、例えば素因数分解の困難性に頼る「デジタル・ロックボックス」の例を含む。
【図２Ａ】２つの当事者間の非対称で安全な情報比較の方法を示す図であり、次の４ステップ：i）指紋を作成するステップと；ii）公開キーで暗号化して他の当事者と交換するステップと；iii）暗号化してスクランブルしてＸＯＲをとった指紋を返送するステップと；iv）ローカルに暗号解読するステップとを有する。
【図２Ｂ】ＡＳＣの同期バージョンを示す図であり。Ｌ１距離は一方の側が暗号解読コードを公表する際のみに決定することができる。
【図３】図３Ａは、非対称で安全な比較を、単数の買い手と売り手が関与する入札状況に適用する方法を示す図である。図３Ｂは、非対称で安全な比較を、単数の買い手と売り手が関与する入札状況に適用する方法を示す図である。図３Ｃは、非対称で安全な比較を、単数の買い手と売り手が関与する入札状況に適用する方法を示す図であり、但し買い手の付け値が売り手の価格と正確に一致するか否かを確定することができる場合である。図３Ｄは、非対称で安全な比較を、単数の買い手と売り手が関与する入札状況に適用する方法を示す図であり、但し買い手の付け値が売り手の価格と正確に一致するか否かを確定することができる場合である。図３Ｅは、非対称で安全な比較を、単数の買い手と売り手が関与する入札状況に適用する方法を示す図であり、但し買い手の付け値が売り手の価格と正確に一致するか否かを確定することができる場合である。図３Ｆは、非対称で安全な比較を、ある範囲の数の買い手と売り手が関与する入札状況に適用する方法を示す図である。図３Ｇは、非対称で安全な比較を、ある範囲の数の買い手と売り手が関与する入札状況に適用する方法を示す図である。図３Ｈは、非対称で安全な比較を、ある範囲の数の買い手と売り手が関与する入札状況に適用する方法を示す図である。
【図４Ａ】ゼロ知識証明の思想を行使する例を示す概略図である。
【図４Ｂ】ゼロ知識証明の思想を行使する例を示す概略図である。
【図４Ｃ】ゼロ知識証明の思想を行使する例を示す概略図である。
【図５Ａ】非対称なＡＳＣ：ＡＳＣＵＳバーション１（Ｌ１等価によって対称性を強化された）を示す図である。
【図５Ｂ】ランダムビット・パディングを伴うＡＳＣＵＳバージョン２を示す図である。
【図５Ｃ】図５Ｂを簡略化した概要を示す図である。
【図６Ａ】ランダムビット・パディング、及び「正直な交換」の一例を示す図である。
【図６Ｂ】ランダムビット・パディング、及び「不正直な交換」の一例を示す図である。
【図７Ａ】距離空間内で分子どうしを比較する方法を示す図である。具体的には、図７Ａは類似性（非類似性）の共有行列を生成する方法を示す図である。
【図７Ｂ】距離空間内で分子どうしを比較する方法を示す図である。
【図８Ａ】安全な公売におけるステップ（ステップ１〜３）を示す図である。
【図８Ｂ】安全な公売におけるステップ（ステップ４及び５）を示す図である。
【図８Ｃ】安全な公売におけるステップ（ステップ６及び７）を示す図である。
【図８Ｄ】安全な公売におけるステップ（ステップ８及び９）を示す図である。
【図８Ｅ】安全な公売におけるステップ（ステップ１０及び１１）を示す図である。
【図８Ｆ】安全な公売におけるステップ（ステップ１２〜１４）を示す図である。
【図８Ｇ】安全な公売におけるステップ（ステップ１５〜１７）を示す図である。
【図９】本明細書中に説明する方法を実現する好適なコンピュータ装置を示す図である。
【発明を実施するための形態】
【００１５】
種々の図面中では、同様な参照符号は同様な要素を示す。混乱を減らし明瞭さを向上させるために、本明細書中では、図面中の参照符号を丸カッコ内で、例えば（１２３）のように、意味の暗黙の変更なしに用いることがある。
【００１６】
詳細な説明
情報の安全な比較の課題、及び関連する課題は、整数論の適用によって解決することができ、整数論は一度はほとんど実用的価値のないものと考えられた数学の一分野である！例えば、個人識別番号（ＰＩＮ：personal identification number）を保護する例は、「ゼロ知識証明（ＺＫＰ：Zero Knowledge Proofs）」として知られているものによって解決することができる。ＺＫＰは、一方の当事者が、ある数「Ｘ」を知っていることを、「Ｘ」が何であるかを公表せずに他方の当事者に対して証明することを可能にする。他のより複雑な例は、本明細書中に説明する技術によって応えることができる。第２の当事者が第１の当事者の隠し情報を実際に見出すことができる唯一の方法が、人間のリソースを超えるものであることを証明することができる何らかの計算プロセスによるものである意味で、そのすべてが「証明可能な安全性がある」。
【００１７】
現代世界にとって大きな重要性があり、実際に現代の暗号化法の大部分の基になる整数論の２つの例は、離散対数問題（ＤＬＰ：Discrete Logarithm Problem）及び素因数分解（ＰＮＦ：Prime Number Factorization）である。これらは、化学構造を含む情報を比較するための本発明の方法において役割を果たすので、以下の節ではこれらを簡潔に説明する。
【００１８】
離散対数問題
次式(1)で表される関係があるものとする：
ｇx＝ｙ(mod Ｎ)    (1)
ここに、Ｎは素数であり、「mod」は「モジュロ」または「時計」算術を意味し、即ち、Ｎ以上の数からＮの整数倍を減じた剰余が０からＮ−１までになることを意味する。「生成元（生成作用素）」と称する値ｇは、ｘが１からＮ−１までの範囲である場合に、ｇxがこれらの同じ整数を、但し異なる順序で再現するように見出すことができる。例えば、Ｎ＝５であるものとすれば：
２1：２＝２(mod Ｎ)    (2a)
２2：４＝４(mod Ｎ)    (2b)
２3：８＝３(mod Ｎ)    (2c)
２4：１６＝１(mod Ｎ)    (2d)
となる。
【００１９】
式(2a)〜(2d)に示すように、数「２」は素数「５」にとっての生成元である。
【００２０】
ここで、Ｎは、例えば２００桁以上の非常に大きな素数であるものとし、ｙ、即ち式(1)の右辺（ＲＨＳ：right hand side）は既知であるものとする。逆算して有効なｘを得ることはできるであろうか？即ち、（Ｎ，ｇ，ｙ）が与えらられは、ｘを計算することができるであろうか？ｙが十分に小さければ、単にいくつかのｘの値を入れて、ｙよりも大きいか小さい値を得て、それに応じてｘを調整したい気になることがある。ｘが十分に小さければ、このことは奏功する。しかし、ｘを１からＮ−１までの値にランダムに選定するとなると、このことが常に成り立つ可能性は非常に低い（１０200分の１のオーダーである）。それどころか、ｙも２００桁の数であり、１０200個の数をすべて探索してどの数がこのことをもたらすかを確かめるための実際的な方法は存在しない。こうした探索を実現可能にするための既知のあるｇリズムも存在しない。関係する量が「離散的」（即ち、モジュラー演算に従う整数）でないとすれば、解は次式(3)のようになる：
【数１】
2018531431.tif 000003
【００２１】
従って、この方法は「離散対数問題」（ＤＬＰ）と称され、計算が「困難である」ものと信じられ、その意味は、関係する数の桁数（の増加）と共に、問題が多項式的に難しくなるのとは対照的に指数関数的に難しくなることであり、即ち、ｙが２００桁を有する場合、問題は、ｙが１００桁を有する場合の２倍（線形で）難しくなるか４倍（二乗で）難しくなるのではなく、１０100倍（指数関数的に）難しくなる。
【００２２】
ＤＬＰはデジタル署名及びすべての安全なインターネット接続の基になる。ＤＬＰは、ディフィー・ヘルマン鍵共有として知られているものの基礎にもなる（例えば、http://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange#Cryptographic_explanation）参照、２つの当事者が互いに公開でデータを送信した上で、暗号化メッセージを互いに送信するために使用することができる秘密の数字（「キー（鍵）」）を生成することができるであろうか。このことが真に安全な通信プロトコルの始まりである。
【００２３】
素因数分解
問題を次式(4)によって表現するものとする：
Ｎ＝ｐ＊ｑ    (4)
ここに、ｐ及びｑは大きな素数である。Ｎ（非素数）が与えられれば、ｐ及びｑを見出すことができるであろうか？ＤＬＰだけでは、この問題は計算が困難であるものと信じられ、即ち、この困難さはＮの桁数と共に拡大する。こうした数を予期されるよりも小さい個数に因数分解する方法は知られているが、ｐ及びｑを選定するに当たり比較的単純なセーフガードを無視する場合だけである（例えば、ｐはｑに近過ぎないようにするべきである）。この問題の困難性が、ＲＳＡ暗号化法の基になる。手短に言えば、次のこと（次式(5)）が成り立つことを示すことができ：
ｍn(p-1)(q-1)+1＝ｍ(mod Ｎ)    (5)
ここにｍ及びｎは任意の整数である。
【００２４】
２つの数ｅ及びｄが存在し、
ｅ＊ｄ＝ｎ(ｐ−１)(ｑ−１)＋１    (6)
即ち、
ｅ＊ｄ＝１(mod(ｐ−１)(ｑ−１))    (7)
であるものとすれば：
ｍed＝ｍ(mod Ｎ)    (8)
となる。
【００２５】
但し、
ｍed＝(ｍe)d    (9)
となる。
暗号化方法では、ｅ及びｄを、それぞれ暗号化キー（暗号鍵）及び暗号解読キーと考えることができる。従って、数ｍが暗号化する必要のあるメッセージであるものとする。ｍをｅ乗すれば、新たな数ｍe mod Ｎが得られ、この数は全くｍのように見えない。しかし、ｄを知っていれば、符号化された数ｍeをｄ乗して、ｍ（「メッセージ」！）に戻すだけで済む。このことが容易にｍに戻すための唯一の方法であること、及びｅとＮを知ってもｄについて役立つことは何も得られず、「秘密」キーと称される。数ｐ及びｑは、ｄを容易に計算するために必要であるが、このことはＮを因数分解することを意味し、このことは計算が非常に困難である。従って、数ｅ及びＮは「公開されて」おり（「公開」キーと称する）：誰もがこれらを用いてメッセージを暗号化することができるが、数ｄを有する者だけが、これらのメッセージを暗号解読することができる。そして、ｄは関係者間で、（前述した）ディフィー・ヘルマン鍵共有のような安全な方法を用いて交換することができ、この方法はＤＬＰに頼る。インターネットのウェブサイト：wikipedia.org/wiki/Public-key_cryptographyも参照。
【００２６】
同時入札
ＤＬＰ及びＰＮＦは共に、本願の背景の節で説明した問題のいくつかに対する解決策を既に提供している。各解決策は、現代世界において他の同等のものを有し、他の問題に対するより大きな新たな取り組みの一部を形成することができる。こうした問題の１つは同時入札であり、即ち、第三者が所有するアイテム（品目）に入札したい２つの当事者が、どちらがより高額で進んで入札するかを見出したい場合であるが、他者が示す自分の入札に基づいて自分の入札を変更する機会がどちらにもない場合である。このことは普遍的な「先発者不利益」の例であり、即ち、一旦、一方の当事者が自分の入札を公表すると、他方はそれで得をすることができる知識上の有利性を有する。
【００２７】
物の世界では、２つの入札（数値）を含む封印された封筒が売り主に与えられ、これにより、いずれかの入札者が、他者が進んで支払う額に基づいて自分が入札することができること、例えば、一方の入札者が他方の入札者よりも１ドル高く入札して、入札されているアイテムを購入する権利を勝ち取ることができることを防止する。一旦、入札が提出されると、封筒が開封されるまでこれらの入札を知らなくても、これらの入札を変更することはできない。異なる入札を申し入れる企ては、（開封された）封筒の内容によって否定される。
【００２８】
電子の世界では、ＰＮＦ（及び公開−秘密キー交換方法のような）暗号化方法が、同様なレベルの秘匿性を実現すること、並びにある当事者が（例えば、他の当事者の数値を知った際に）自分の立場を変更したか否かを示すことを可能にするが：ある当事者が不正をしようとする（「封印した」ものとは異なる入札を申し入れようとする）ことを防止することはできず、実際には、この当事者が不正をしたことを露見させることができることがわかっている。両方の入札が預けられて「開封されて」初めて、各当事者が他者の入札がどうであるかを知ることができる。しかし、提供される保護は、それぞれの入札の送信中だけではない。
【００２９】
従って、本明細書中に説明する方法は、大きな素数の因数分解に頼る、公開−秘密キー交換の新たな応用である。一方の当事者はこの素数を用いて自分の入札を暗号化するが、他方の当事者の入札を受信するまでは暗号化キーを送信しない。
【００３０】
従って、同時入札の状況は、非対称暗号化の形式を用いて次のように進めることができる。第１の当事者が素数ｐ及びｑを選定し、第２の当事者が異なる素数ｐ’及びｑ’を選定するものとする。第１の当事者は、自分の入札ｍを、ｐ及びｑから導出したｅを用いて符号化して、ｍe、並びにｅ及びＮ、ｐとｑの積を第２の当事者に提供する。第２の当事者は、自分の(ｍ’)e、ｅ’、及びＮ’のそれぞれを第１の当事者に提供する。第１の当事者が、第２の当事者の暗号化した入札を受信した後に、第１の当事者はｐとｑ、Ｎの因数を第２の当事者に送信する。これにより、第２の当事者は式(6)よりｄを計算することができ、これより、第１の当事者の暗号化した入札を、式(9)を用いて暗号解読することができる。なお、第１の当事者が自分の入札を変更する方法は存在しない。算術の基本定理（ＦＴＡ：Fundamental Theorem of Arithmetic）は、ある数を素数のべき乗に因数分解する方法は１つしか存在しないことを述べており（ここに、これらのべき乗の各々は個別に１とすることができる）、従って、ｐ及びｑは、掛け合わせてＮにすることができる唯一の素数であり、Ｎは暗号化した入札と共に提供されている。ｐ及びｑによれば、ｅと共に役立つｄは１つしか存在せず、ｅも第１の当事者が第２の当事者に送信している。
【００３１】
従って、現在第２の当事者が保有する数値（入札）は、一旦、送信されると、第１の当事者の側では自分から変更することはできず：第１の当事者がｐ及びｑを送信するまでは、第２の当事者がこの数値を読むことができないだけである。同様に、第１の当事者は、第２の当事者のｐ’及びｑ’を受信するまでは第２の当事者の入札を読むことができず、第２の当事者も既に第１の当事者に既に提供した数値を変更することはできない。
【００３２】
このプロセスを図１に例示し、図１は、当事者１及び当事者２が情報を交換することを可能にする「デジタル・ロックボックス」（１００）を示し、（破線の境界を有する別個のボックスで表される）３つの段階（１５０）、（１７０）、及び（１９０）を構成する。なお、コンピュータなしで実行することができる（ロックボックス（鍵付き箱）のような）方法には類似性が存在するが、本明細書中の実現は、物理的物体だけを扱う者にとって利用可能でない技術に頼る。
【００３３】
第１段落（１５０）では、両方の当事者が自分のキーの組を生成して、それぞれの入札を暗号化する。第１段階では、両方の当事者が、素因数分解のような方式を用いて暗号化することに同意することができる。
【００３４】
従って、当事者１はＲＳＡ（Rivest-Shamir-Adleman（リベスト−シャミア−アーデルマン））キーを生成して（１０７）、公開キー１（１０９）及び一組の秘密キー（１１１）をもたらす。次に、当事者１は、入札１（１０１）による入札プロセスを開始し、入札１を暗号化（１０３）して、暗号化した入札１（１０５）を生成する。
【００３５】
これに対応して、当事者２はＲＳＡキーを生成して（１０７）、自分のキーの組、即ち：公開キー２（１１０）及び秘密キー２（１１２）を生成する。次に、当事者２は、入札２（１０２）による入札プロセスに入り、入札２を暗号化（１０４）して暗号化した入札２（１０６）を生成する。
【００３６】
第２段階（１７０）では、これらの当事者がそれぞれの公開キー及び暗号化したフォーム（伝票）を交換する。
【００３７】
従って、当事者１は、暗号化した入札１（１０５）及び公開キー１（１０９）を当事者２に送信し（１１５）、当事者２は、暗号化した入札２（１０６）及び公開キー２（１１０）を当事者１に送信する（１１６）。
【００３８】
この段階では、いずれの当事者も、互いの入札をまだ読むことはできず；各々がデジタル・ロックボックスを有効に受信している。さらに、いずれの当事者も、自分の暗号化した入札及び対応する公開キーを他方の当事者に同時に送信する必要はなく；もちろん、受信側の当事者は、対応するキーを（公開キー及び秘密キーを共に）受信するまでは、受信した暗号化した入札に対して何もすることはできない。
【００３９】
要約すれば、３つの情報、即ち：秘密キー及び２つの公開キーが存在する。いずれの当事者も、２つの公開キーから秘密キーを解明することはできない。
【００４０】
第３及び最終段階では、これらの当事者がそれぞれの秘密キーを交換する。
【００４１】
当事者１は、自分の秘密キー１（１１１）を当事者２に送信し（１２３）、次に、当事者２は、これらの秘密キーを（以前に受信した公開キー１と共に）用いて、暗号化した入札１を暗号解読し（１２０）、これにより入札１（１０１）を明示する。
【００４２】
これに対応して、当事者２は秘密キー（１１２）を当事者１に送信し（１２４）、次に、当事者１は、これらの秘密キーを（以前に受信した公開キー１と共に）用いて、暗号化した入札２（１０６）を暗号解読し、これにより入札２を明示する。
【００４３】
この状況と物理的に等価なものは、２つの当事者が「ロックボックス（鍵付き箱）」を交換しており、各々が、それぞれの入札を封入されて封印された封筒を保持していることである。一旦、ロックボックスを交換すると、次にこれらの当事者は鍵を交換して互いのボックスを開ける。鍵の交換は同時でなくてもよい、というのは、他の当事者は既に他者の入札を有しており、まだそれにアクセスすることができないだけである。この交換を傍受して一方の当事者の秘密キーを入手する第三者は、対応する公開キーを持たない限りメッセージを暗号解読することはできない。もちろん、一方の当事者が、他方の当事者に、自分が所有するボックスのキーを与えることができ、他方の当事者は自分が有するボックスのキーを提供することを拒むことはできるが、このことは同時のキー交換ではない。そして、こうした事態では、取引における信用が自動的に無効になる。本明細書において考慮するプロセスは、当事者による取引に対する良い振る舞いを強いることができるプロセスではなく；むしろ、これらのプロセスは、悪い振る舞いを明らかにするプロセスである。以下では、「ロックボックス」の能力が、本明細書中に記載する他の課題に対する解決策の構成要素として有用であることがわかる。
【００４４】
化学への応用
化学への実際的応用として、２つの分子構造が同一であるか否かを見出すためのＤＬＰの使用を考える。あらゆる分子が、ＳＭＩＬＥＳ（スアイルズ）ストリング（Daylight Chemical Information Systems社、カリフォルニア州ラグーナ  ニゲル（Laguna Niguel, CA）；www.daylight.com/smiles/index.html）として知られている辞書式記述によって表現することができる。例えば、ベンゼンのＳＭＩＬＥＳストリングはc1ccccc1である。
【００４５】
こうした記述は、一意的（正準）にすることができ、こうした「メタ」情報を立体化学として含むことができる。従って、同じ長さの正準のＳＭＩＬＥＳストリングは、企業が有する集合体中のあらゆる分子を一意的に表現するのに十分なものである。こうした文字の「ストリング（列）」が数に変換されるものとする。このことを行う方法はいくつか存在するが、例えば、特定の方法は、ＳＭＩＬＥＳストリング内の各記号がＡＳＣＩＩ（American National Standard Code for Information Interchange：アスキー）コードを有することに基づくことができ：「ｃ」は９９、「１」は４９である。ＦＴＡによれば、ＳＭＩＬＥＳストリングは一意的な数に変換することができ、従って次式：
ｆ(SMILES)＝２99３49５99７99１１99１３99１７49    (10)
のようになり、ここに、元のストリング内のｎ番目の文字は、ｎ番目の素数をその文字のＡＳＣＩＩ等価値でべき乗した値に置き換えられる。ＦＴＡは、任意の数ｆが唯一のこうした因数分解を有することを述べており、従って、この数はＳＭＩＬＥＳストリングを一意的に表現する。さらに、これはとても大きな数でもある！
【００４６】
しかし、こうした数に離散対数問題を適用することを考え、即ち、次式のようになる。
ｇf(SMILES)modＮ＝ｙ    (11)
ここで、ＳＭＩＬＥＳストリングを表現する数ｙは１〜Ｎでなければならない。
【００４７】
さらに、ＤＬＰを前提とすれば、ｙからｆ(SMILES)を計算することは非実際的である。しかし、問題は、与えられたＳＭＩＬＥＳストリングからｆ(SMILES)の一意的な値が存在しても、前者の関数ｙが証明可能な方法で一意的であることを保証されていないことであり、式(11)のｙが証明可能な方法で一意的であるに過ぎない。このため、ｆ(SMILES)は一方向ハッシュ関数と称され、ハッシュは、一部の情報を失ったより大きな数の表現である。一般に、良好なハッシュ関数については、ハッシュ衝突の確率、即ち、この例では、同じｙを生じさせる２つのｆの値が、可能なｙの値の数の平方根、即ち√Ｎに依存する。このため、Ｎが非常に大きく、例えば２００桁である場合、１０100個のＳＭＩＬＥＳストリングを、反復されるｙに追い付きそうになる前にデジタル化しておかなければならない。このことは、各ＳＭＩＬＥＳストリングが本質的にランダムなｙを生じさせるものと仮定する。ＳＭＩＬＥＳストリングの小変化が著しく異なるｙの値を生じさせる、ということが、ここでは非常に起こりがちである、という妥当な議論を行うことができる。こうした主張が裏付けではないとしても、このようなハッシュ関数が「衝突耐性（耐衝突性）がある」ことは証明することができ、このことは、衝突を探すことによって衝突を実際に見つけることは計算が困難であることを意味する。例えば、一方の当事者が、第２の当事者に属する分子に対応するｙの値を有するが、同じｙの値を生じさせる分子を作製したいものとする。第１の当事者は、この分子が実際に第２の当事者の分子と同じであることは気にせず；ただこの分子が同じハッシュｙを与えることだけを気にする。このことを行うために、第１の当事者は、（あり得る分子の数が膨大であることを念頭に置いて）単にランダムな分子を作製して検査するか、あるいは、どのようなｆがあり得るかを見出そうと試みて、それより、どのような分子が同じｙの値を生じさせるかについてより良い見当をつけるかのいずれかをしなければならない。しかし、ＤＬＰが機能する方法に起因して、ｙからｆに至ることはできない。このため、分子の識別子ｙを、異なる分子で「真似る」ことは計算が困難である。
【００４８】
一般に用いられる分子構造の第２の表現は「指紋」と称される。指紋は一般に１と０との集合であり、１はある性質の存在を表し、０は欠如を表す。指紋は、分子を比較する標準的方法の基礎となっており、即ち、２つの分子が一組の性質の存在または欠如の同じパターンを有する場合、これらの分子は同様な分子形状を有することが多い。代表的な指紋は、実際に分子の結合パターンのいくつかの態様を符号化し、このため、同様な指紋を有する２つの分子は同様な化学構造を有することも多い。逆に、２つの異なる分子が同一の指紋を有する場合、これらの分子が同じ分子構造を有することを意味せず；このように、指紋はある種のハッシュ関数でもある、というのは、指紋を作成する際に一部の構造情報は失われているからである。
【００４９】
原則として、異なる分子の集合体から生成することができる多数の指紋が存在する。このため、分子を安全に比較する１つの方法は単に指紋を比較することとすることができるように思われ得る。結局は、指紋を検査して、この指紋を生成した分子を知ることはできず、２つの指紋が同じであっても、そのことは、これらの指紋が同じ分子を表現することは意味しない。しかし、分子の指紋は一般に衝突耐性がないことが示されている。ある指紋が与えられると、全く同じ指紋を有する分子を生成することはコンピュータ計算で実現可能である。このことは、分子に加える変更の指紋に対する影響が線形加算可能であることに起因し、即ち、分子構造に加える小変化は一般に指紋の小変化を生じさせ、従って、「適合性」関数を定義して、例えば一般的アルゴリズムを学習させて、出発構造と、対象（ターゲット）の指紋と最終的に正確に一致する構造との類似性を改善することは容易である。分子を比較することについて評価される（同様な分子は同様な指紋を有する）ことがまさに指紋の特徴であり、このことが指紋を衝突耐性のないものとし、従って安全でなくする。
【００５０】
しかし、指紋を安全に比較することができる方法が存在するものとし、即ち、第１指紋の所有者が、自分の指紋と第２の当事者に属する指紋との類似性を学習することはできるが、第２指紋との同一性は学習せず、１つの例外は、２つの指紋が実際に同一であることをアルゴリズムが報告する場合であるものとする。この場合、２つの分子が同一であることを報告する２つの方法が存在し得る。これらの方法は共に高度な安全性があり、かつ互いに共通なものを有さない。この方法により、（天文学的な確実性で）同一性を確立することだけでなく、２つの分子の化学的類似性（あるいは類似性の他の根拠）を、さらなる情報の交換なしに確立することができる。
【００５１】
指紋（ビット・ストリング）比較
問題の性質は、次の事例を利用して説明することができる。アリスが、２０個の１と０とのストリングを有し、従って：
[100100010010101010001]    (12)
ボブが次のような長さ２０のストリングを有し、従って：
[010101010010101010011]    (13)
【００５２】
ボブとアリスのストリングは共に同数のビットを有するが、各ストリング中の各「１」及び「０」の位置は同じではない。質問は、これら２つのストリングがどれほど類似しているか？である。この例では、ビット・ストリング(12)及び(13)が多数の共通なビットを有するが、（左から右に読むと）１番目、２番目、６番目、及び１９番目のビットは異なる。
【００５３】
ビット・ストリングの差の一般的尺度は「ハミング距離」と称され、「市街距離」、あるいは数学的にＬ１距離としても知られている。Ｌ１は、各位置における差の絶対値の総和をとることを意味するのに対し、Ｌ２は各位置における差の二乗の総和の平方根をとることを意味する。この例では、Ｌ１を用いるかＬ２を用いるかはほとんど差がない、というのは、各順序集合（「ベクトル」）のエントリ（各入力値）が１及び０である（従って、あらゆる所定位置における差が１を超えることはあり得ず、従って、差の二乗も１を超えることはあり得ない）からである。いずれの場合にも、この差は便宜上Ｌ１距離と称する。また、Ｌ１距離は、これら２つのストリングにＸＯＲ（排他的論理和の）論理演算
（外１）
2018531431.tif 000004
を適用した結果における０でないビットの数にも等しい。アリスのストリングとボブのストリングとの間のＬ１距離は４である、というのは、（値が）異なる４つの位置が存在するからである。アリス及びボブの各々が、自分の実際のストリングを公表せずにＬ１の値を学習することができる場合、彼ら二人はそれぞれの類似性を評価するために必要な最小限の情報を開示されているが、それ以上学習することはできない。このことはＺＫＰではないが、追加的開示ゼロ（ＺＡＤ：Zero Additional Disclosure）を含む、というのは、開示されているもののすべてが要求したもの、即ち、これらのストリングがどれほど類似しているかであり、それ以上のものはない。
【００５４】
アリス及びボブが信頼できる第三者クリストファーを知っているものとする。彼ら二人は共に自分のストリングを暗号化してクリストファーに送信し、クリストファーはこれらのストリングを暗号解読し、各ビットを比較してＬ１距離を特定する。従って、次式のようになる：
【数２】
2018531431.tif 000005
【００５５】
演算
（外２）
2018531431.tif 000006
は論理ＸＯＲ演算である。ＸＯＲは「排他的論理和（Exclusive OR）」を意味し、互いに異なる一対のビットから「１」を生成し、それ以外は０を生成する。即ち、次式のようになる：
【数３】
2018531431.tif 000007
【００５６】
従って、ＸＯＲはアリスのストリングとボブのストリングとの間に４つの差を見出し、「１」は式(14)中の最後のストリングとして表現される結果的なストリング中の「１」の箇所に出現する。ここで、クリストファーがしなければならないことは、ＸＯＲストリングＬ１中のビットの数を数え上げて、その結果をアリス及びボブに送信することだけである。なお、クリストファーは結果のストリングをいずれに送信することもできない。クリストファーがそのことをすれば、アリスまたはボブが、他者のストリングとして、そうであるはずのものを再構成することは容易になる。実際に、次式であることを示すことは容易である：
【数４】
2018531431.tif 000008
換言すれば、アリスがしなければならないことは、結果的なストリングと自分自身のストリングとのＸＯＲをとって、ボブのストリングを生成することだけである（その逆も同様である）。
【００５７】
しかし、クリストファーは戻りのストリング中のビットの数を数え上げて、その結果をアリス及びボブに戻す必要はなく、そしてこのことは本発明における主要な発見である。クリストファーがしなければならないことは、このストリング内のビットをランダムに順序変更して、アリス及びボブに返送することだけである。例えば、１から２０までの数のうちの１つを各ビットにランダムに割り当て、これらのビットを各自が受信した乱数のサイズによって順序付けし直す。次に、彼ら二人はこのストリングを見て、ビットの数を数え、その数はまだ４であるが、彼ら二人のどちらも実際に差がある箇所はわからない。クリストファーが、元のＸＯＲストリングに適用した順序変更の記録を保持しているものと仮定すれば、クリストファーだけがこの箇所を知っている。アリス及びボブは、彼ら二人のストリング間の差の大きさは知っているが、これらの差の箇所については何も知っておらず、従って、このことが今度はＺＡＤの状況である。
【００５８】
しかし、アリス及びボブがクリストファーを知っていなければどうであろうか？彼ら二人は同じ結果を自分自身で得ることはできるであろうか？驚くべき答えは「そうであるが」である。アリスが彼ら二人のストリング間のＬ１を、ボブのストリングを知ることなしに知ることはできるが、ボブは何も知っていない。即ち、安全であるが非対称な情報の転送を行うことはできる。もちろん、アリスがＬ１をボブと共有することは自由であるが、ボブは、アリスと同じストリングに対して同じアルゴリズムを実行することを許可されない限り、これを信用しなければならない。このことがどのように機能するかを確かめるために、上記のシナリオを考えるが、アリス及びボブは自分のストリングを最初に暗号化しているものとする（とりあえず、どのよう暗号化するかは脇に置く）。クリストファーは両者のストリングを受信するが、ここでは、これらのストリングが暗号化されているものとすれば、どのようなストリングであるかは知らない。次に、クリストファーは、これらのストリングのＸＯＲをとって、比較ストリングの結果を生成したい。しかし、クリストファーはそれができない、というのは、これらのストリングが暗号化されているからである。しかし、クリストファーはそのことを無視して、とにかくこれらのストリングのＸＯＲをとり、次にその結果を順序変更してアリス及びボブに返送するものとする。このストリングはＬ１距離と関連性がないものと予期されるかもしれない。しかし、GoldWasser及びMicali（ＧＭ）は１９８２年に、暗号化したストリングのＸＯＲが真の結果を暗号化したストリングになることを述べている。即ち、ＧＭ方式を用いて、クリストファーは、暗号化して順序変更したＸＯＲストリングを返送している。ここで、アリス及びボブは共に、この暗号化方法を知っているので、その結果を暗号解読してＬ１を復元することはできるが、ストリング中のどこに差があるのかは知らない。このことは注目に値する結果であり、「準同形暗号化」の新たな応用の例である。これに対し、ＲＳＡのような他の暗号化方式は、メッセージまたは数の全体に適用され、ＧＭキーをビット暗号化に用いる。従って、ＲＳＡキーは、ＸＯＲの事象が存在することになるビット・ストリング暗号化にＧＭキーを用いることができる「ロックボックス」の状況に適用される。
【００５９】
準同形暗号化は、暗号化形式に対する算術計算を可能にし、これにより、暗号化形式を暗号解読する際に、その結果は、この算術計算を非暗号化形式に対して実行したのと同じになる。ＧＭ法は、暗号化形式に対するＸＯＲ演算を可能にする準同形暗号化の例である。何年にもわたって、準同形暗号化の比較的少数の例が存在し、各々が１つの数学演算（加算、減算、等）にしか役に立たなかった。１つの例は、ＲＳＡアルゴリズムにより既に上述している。上述したように、数ｍを暗号化することが望まれ、次の表現式を形成することができる：
ｍe＝ｊ(mod Ｎ)    (17)
ここに、ｅ及びＮは上述した通りであり、ここでｊはｍの暗号化形式である。
【００６０】
第２の数ｎが存在し、暗号化したｋになるものとする：
ｎe＝ｋ(mod Ｎ)    (18)
【００６１】
ここで、暗号化した数ｊとｋを乗算した結果は表現式(19)となる：
ｊ＊ｋ＝ｍeｎe＝(ｍｎ)e(mod Ｎ)    (19)
【００６２】
ｊ×ｋの積を暗号化すれば、表現式(20)となる：
(ｊ＊ｋ)d＝(ｍeｎe)d＝ｍedｎed＝ｍｎ(mod Ｎ)    (20)
この式は、暗号化した数どうしを乗算することは、その基になる暗号化していない数どうしを乗算することも含むことを意味する。これは準同形計算であるが、乗算にのみ当てはまる。乗算はElGamal（エルガマル）暗号システムでも可能であり、ElGamal暗号システムはＤＬＰに頼る。加算は、Benaloh（ベナロー）暗号システム、及びPaillier（パイリア）暗号システムでも可能であり、これらの両者もＤＬＰに頼る。
【００６３】
GoldWasser-Micali暗号化の数学
ＧＭ暗号化は、「平方剰余性」と称されるものに基づき、基本的に、数が平方（二乗）の、所定のＮのモジュロであるか否かを問う。通常の算術では、ある数が平方であるか否かを見分けることは容易であり：その平方根が整数であるか否かをチェックすればよい。ここで、この質問を、モジュロまたは時計の算術について考える。
【００６４】
通常のように、Ｎが２つの大きな数ｐ及びｑの積であるものとする。次に、質問は、所定のｘについて、次式のようなｙが存在するか否かである：
ｘ＝ｙ2(mod Ｎ)    (21)
【００６５】
ｐ及びｑが共に既知である場合、この質問に答えることは相当容易である。必要なものは：
ｘ(p-1)/2＝１(mod ｐ)    (22)
及び
ｘ(q-1)/2＝１(mod ｑ)    (23)
だけである。
しかし、ｐ及びｑは既知でない場合、式(21)の解を確定することは非常に困難であり、即ち、Ｎを因数分解するのと同じくらい困難である。
【００６６】
ここで、式(21)が成り立たない数が存在するものとし、即ち、ｘが平方でないものとする。さらに：
ｘ(p-1)/2＝−１(mod ｐ)    (24)
かつ
ｘ(q-1)/2＝−１(mod ｑ)    (25)
であるものとすれば、任意数ｚ2にｘを乗じたものも平方にはなり得ない。このことを確かめるために、次式を考える：
(ｚ2ｘ)(p-1)/2＝ｚ(p-1)ｘ(p-1)/2＝ｘ(p-1)/2＝−１(mod ｐ)    (26)
というのは、「フェルマーの小定理」により：
ｚp-1＝１(mod ｐ)    (27)
かつ
ａｂ(mod ｐ)＝ａ(mod ｐ)＊ｂ(mod ｐ)    (28)
となるからである。
【００６７】
従って、こうしたｘが存在し（容易に見つけることができ）、積ｘｚ2は何らかの大きな乱数ｚから計算されるものとする。ｐ及びｑは共に既知であるので、ｘｚ2が平方でないことはすぐに見出すことができるが、ｐ及びｑの知識なしでは他のだれもできない。これはコード中の「１」を表す。次に、ｚ2だけを考える（即ち、ｘのことは忘れる）。ここでも、これは因数ｐ及びｑを用いた平方であることは容易に証明することができる。従って、これはコード中の「０」を表す。従って、ビット・ストリングを符号化するために必要なことは、各０または１を、それぞれｚ2またはｘｚ2に置き換えることだけであり、ここにｚはビット毎に異なる（ランダムに選定した）数であり、ｘは式(24)及び(25)に従う。他の当事者にｘ及びＮの値を提供することによって、その当事者は同じことを行うことができ、即ち、これらは「公開」キーである。しかし、このプロセスを逆にすること、即ち、各数が１を表すか０を表すかを見出すことは、ｐ及びｑを知らずには計算が指数関数的に困難になり、ｐ及びｑは「秘密」キーである。
【００６８】
ここで４つのことを注記することが重要である。
【００６９】
第１に、メッセージのサイズが大幅に拡大されている。ここで、非常に大きな数がビット・ストリング中の各ビットを表す。このことが、この方法が暗号化法と同じくらい広く用いられてこなかった理由である。
【００７０】
第２に、「１」及び「０」の乗算は興味深い性質に従う。２つの暗号化した「１」の値を掛け合わせるものとする：
(ｚ2ｘ)(ｗ2ｘ)＝(ｚｗｘ)2(mod Ｎ)    (29)
即ち、平方でない２つの数を掛け合わせることは、平方のモジュロＮを生じさせ、即ち{１，１}＝{０}である。
【００７１】
一方が平方である他方が平方でない２つの数を掛け合わせると、次式のようになる：
(ｘｚ2)(ｗ2)＝ｘ(ｚｗ)2(mod Ｎ)    (30)
その結果は平方ではなく、従って{１，０}または{０，１}は{０}を与え、これは平方である。
【００７２】
最後に平方である２つの数を掛け合わせると、次式のようになる：
(ｚ2)ｗ2＝ｘ(ｚｗ)2(mod Ｎ)    (31)
即ち、{０，０}は{０}を与え、これは平方である。
要約すれば、「１」及び「０」を表す大きな数どうしの乗算は、基になる１及び０のＸＯＲの性質を正確に有する他の大きな数を与える。このことが本願全体を通して用いられる準同形の性質である。
【００７３】
第３に、各ビットは乱数（及びｘ）によって表される。実際に、ＧＭは非常に少数の確率暗号化法の１つである。このことは以下に続くことにおいて重要である、というのは、ビット毎に同じキーを用いるが、表現はすべて予測不可能な様式で異なることを意味するからである。このことは非常に重要である。安全な比較プロトコルを効果的にするここでの主要なステップは、ビットの順序変更である。しかし、２つの当事者（例えば、前述したアリス及びボブ）が、順序変更されたビットを「デスクランブルする（スクランブルを元に戻す）」ことができるならば、彼ら二人は互いのストリングを解明することができる。彼ら二人がこのことを行うことを防ぐものは、基本的に、各ビットを新たなランダムシードで符号化すること、及び、一旦、各ビットを表す値がスクランブルされると、これらの値を元の値まで逆に「辿る」ことができないことである。
【００７４】
第４に、安全のレベルは各ビットを表す数のサイズによって決まる。
【００７５】
２つの大きな数どうしを掛け合わせて、他の大きな数のモジュロをとることによって上記ＸＯＲ演算を実行するものとすれば、即ち、Ａ＊Ｂ＝Ｃ(mod Ｎ)であるとすれば、この演算の１つの追加的な特徴を注記するべきである。ここでの大きな特徴は、結果的なＣをとって、これを、ＸＯＲをとったビット・ストリング中のビットを表す他のすべての数のリスト中のランダム位置に置くことができ、従って、元のＸＯＲストリングがどのように見えるかを隠すこと（従って、何者かが元のストリングを暴くことを防ぐこと）ができる。従って、１つの要件は、何者かがＣだけからＡを解明することができないことである。これがモジュロ算術でないとすれば、これは問題となり得る。例えば当事者Ａ及び当事者Ｂからの次の数があるものとする：
Ａ１＝５、Ｂ１＝７、従ってＣ１＝３５；及び
Ａ２＝８、Ｂ２＝３、従ってＣ２＝２４。
【００７６】
この手順は（Ｃ１，Ｃ２）を任意の順序で戻すことになり、これにより、｛Ｂ１，Ｂ２｝の提供者は、相手が｛Ａ１＊Ｂ１，Ａ２＊Ｂ２｝を見ているか｛Ａ１＊Ｂ２，Ａ２＊Ｂ１｝を見ているかは知らない。しかし、当事者「Ｂ」は自分の値を知っているので、当事者Ｂは、（３５は３で割り切れないので）Ｃ１がＢ２に何かを乗算したものに由来するはずがないものと推論し、従ってＣ１はＢ１に由来するはずであり、即ち、元の順序が復元される。
【００７７】
しかし、モジュロ算術を実行する際には、事態が異なる。実際に、本明細書中に説明するシステムでは、こうした容易な因数分解を行う方法は基本的に存在しない。しかし、例外が存在する。当事者Ｂからの数のうちの１つがキーのうちの１つの倍数であれば、どのような「Ａ」の数を用いても、このキーの倍数が戻され、即ち、誰かは「Ｃ」が由来した所がわかる。このことはあまり役に立たないことがわかり；一例を挙げれば、この方法を用いる当事者Ｂは基本的に自分のキーを明かし、そのいくつかは（当事者）Ａが容易に検出することができる。
【００７８】
近年、完全に準同形の計算、即ち加算及び乗算を共に可能にする第１の方法が報告されている（Craig Gentry, “A fully homomorphic encryption scheme”, Ph.D. thesis, Stanford Univ. (2009)（非特許文献１）、参照することによって本明細書に含める）。この方法の利点は、ホストコンピュータのリソース（例えば、いわゆる「クラウド」コンピュータ）上で安全な計算を実行する能力にある。
【００７９】
しかし、本発明における適合は異なる。計算を行う場所は問題ではなく；その代わりに、問題となるものは、情報の安全な生成及び転送である。従って、このことは準同形暗号化の数学の新規な応用である。特に、主要なデータの公表なしにＬ１距離を安全に計算することができるという見解は、以前には実証されていない。
【００８０】
アリス及びボブ及びクリストファーの例に戻れば：これまでは、アリス及びボブが暗号化したストリングをクリストファーに送信し、クリストファーが暗号化計算を実行し、結果をスクランブルして、アリス及びボブの両者に、いずれの者にも他者のストリングどのようであるかは公表せずに戻す。クリストファーがアリスの元の（暗号化した）ストリングをボブに漏らすことを止めさせるものは何か？クリストファーがこのことを行うようなことがあれば、ボブはアリスのストリングを暗号解読することだけはできる。しかし、ＲＳＡアルゴリズム中に示されているように、アリス及びボブが共に暗号化するために用いることができる公開キー（上記ではｅで表される）を持つことはできるのに対し、暗号解読キーｄはアリスしか知っていない。こうした状況では、クリストファーがアリスのストリングをボブに漏らすことはボブにとって無駄であるのに対し、クリストファーがボブのストリングをアリスに漏らすことはボブのストリングを明らかにする。こうした方式は非対称であり、ボブにとって安全でない。もちろん、クリストファーはｅ及びｄを知ることができ、アリス及びボブはｅしか知らないが、このことは、クリストファーがすべてを知っており、これらの当事者のクリストファーに対する信頼が完全でなければならない状況に、これらの当事者を引き戻す。
【００８１】
しかし、この方式の進展がもう１つ存在するものとする。クリストファーにストリングを受信させて仲介者の役を務めさせるのではなく、この仲介者を解任するものとする。アリスがｅ及びｄを生成し、自分のストリングをｅで暗号化して、自分の暗号化したストリング及びｅをボブに送信するものとする。ボブは自分のストリングをｅで暗号化して、アリスの暗号化したストリングとのＸＯＲを実行し、次に結果的なビットに順序変更を適用し、これをアリスに返送する。アリスはボブのストリングを、暗号化されていてもいなくても、全く目にすることはなく：ボブ以外の誰も目にすることはない！アリスは暗号解読するに至り、従って結果的なストリングを見るが、ボブは順序変更を適用しており、アリスは各ビットが元々あった箇所についての情報を有さない。従って、ここでアリスはＬ１を保有しており、アリスもボブも、強力な暗号化法によって保護されていなかったもの以上のものは露わにしていない。この装置によって、信頼できる第三者がなくなるだけでなく、安全性が実際に増加する、というのは、関係する当事者以外の何者も、暗号化していないストリングを操ることは決してないからである。本明細書では、この方法を非対称で安全な比較（「ＡＳＣ」：Asymmetric Secure Comparison）と称し、図２Ａ及び２Ｂに例示する。
【００８２】
図２Ａ及び２Ｂでは、取引が当事者１と当事者２との間で行われる。このプロセスを図２Ａに４つの段階（２５０）、（２６０）、（２７０）、及び（２８０）で例示し、図２Ｂに５つの段階（２５０）、（２６０）、（２７０）、（２８０）、及び（２９０）で提示する（各段階は、破線の境界を有するボックス（箱形）で表す）。
【００８３】
第１段階（２５０）では、当事者がそれぞれの指紋を作成する。図２Ａでは、当事者１が分子または他のデータ１（２０１）を取得して、指紋（２０５）を作成する（２０３）。その間に、当事者２は分子または他のデータ２（２０２）を取得して、指紋２（２０６）を作製する（２０４）。
【００８４】
第２段階（２５０）では、当事者の指紋の暗号化を行う。当事者１は、ＧＭキー（２０７）及び関連する公開キー（２０９）と秘密キー（２１９）を生成する。指紋１を公開位キー（２０９）で暗号化して、暗号化した指紋１（２１３）を作成する。
【００８５】
当事者１は公開キー（２０９）を当事者２に送信し（２１５）、当事者２もこの公開キーを用いて指紋２を暗号化し（２１０）、これにより暗号化した指紋２（２１２）を作成する。また、当事者１は暗号化した指紋１（２１３）を当事者２に送信し、当事者２は、暗号化した指紋１と暗号化した指紋２（２１２）とのＸＯＲをとり（２１６）、これにより、暗号化した指紋ＸＯＲ（２１８）を作成する。
【００８６】
第３段階（２７０）では、スクランブルを行う。従って、当事者２は、暗号化した指紋ＸＯＲをスクランブルして（２２０）、暗号化してスクランブルした指紋ＸＯＲ（２２２）を作成して、当事者１に返送する（２２４）。
【００８７】
第４段階（２９０）では、当事者１がＬ１を計算する。当事者１は、まず、秘密キー（２１９）を用いて、暗号化してスクランブルした指紋ＸＯＲ（２２２）を暗号解読し（２２１）、これにより（暗号解読された）スクランブルしたＸＯＲ指紋（２２５）を生成する。この指紋中のビット数を数えて（２２７）Ｌ１（２２９）の値を与え、この時点でプロセスを終了する（２３１）ことができる。
【００８８】
図２Ｂでは、第１段階（２５０）で、最初の２、３ステップを図２Ａのように進める。当事者１は、分子または他のデータ１（２０１）を取得して指紋１（２０５）を作成する。その間に、当事者２は分子または他のデータ２（２０２）を取得して、指紋２（２０６）を作成する（２０４）。
【００８９】
第２段階（２６０）では暗号化を行う。当事者１は、ＧＭキー（２０７）及び関連する公開キー１（２０９）と秘密キー１（２１９）を生成する。指紋１を公開キー１（２０９）で暗号化して、暗号化した指紋１（２１３）を作成する。
【００９０】
当事者１は、公開キー１（２０９）を当事者２に送信し、当事者２もこの公開キーを用いて指紋１を暗号化し（２１０）、これにより、暗号化した指紋２（２１２）を作成する。また、当事者１は、暗号化した指紋１（２１３）を当事者２に送信し、当事者２は、暗号化した指紋１と暗号化した指紋２（２１２）とのＸＯＲをとり（２１６）、これにより、暗号化した指紋ＸＯＲ（２１８）を作成する。
【００９１】
そして、第３段階（２７０）では、当事者２は、暗号化した指紋ＸＯＲ（２１８）をスクランブルして（２２０）、暗号化してスクランブルした指紋ＸＯＲ（２２２）を作成する。
【００９２】
ここで、追加的に、（当事者２が、当事者１がＸＯＲストリングを暗号解読する時点を管理する）図２Ａとは異なり、当事者２はＲＳＡキー（２３６）を生成し、このＲＳＡキーから公開キー２（２３８）及び秘密キー２（２４０）を生成する。次に、暗号化してスクランブルした指紋ＸＯＲ（２２２）をＲＳＡ公開キー２で暗号化して、ＲＳＡ公開キー２と共に当事者１に送信し、当事者１は、これを、二重に暗号化してスクランブルした指紋ＸＯＲ（２５１）として受信する。
【００９３】
第４段階（２８０）では、当事者２は公開キー２（２４０）も当事者１に送信し（２４８）、当事者１は、この公開キー２を用いて、二重に暗号化してスクランブルした指紋ＸＯＲ（２５１）を暗号解読する（２５３）。なお、このことは、当事者１が指紋比較の結果を見ることができる時点を当事者２が管理することを可能にする。
【００９４】
最後に、段階（２９０）では、暗号化してスクランブルした指紋ＸＯＲを再生したものを、秘密キー１（２１９）でさらに暗号解読する（２５５）。この暗号解読された指紋中のビット数を数えて（２５５）Ｌ１（２５７）の値を与え、この時点でプロセスを終了することができる（２５９）。
【００９５】
しかし、上述したように、図２Ｂのプロセスには非対称性がとり入れられている。（例えば当事者１として図示される）アリスはＬ１を保有するが、（当事者２として図示される）ボブは保有しない。多数の状況では、このことが問題にならないことがあり、このことが当事者間の実際の関係を反映する場合には、利点にさえもなり得る。例えば、小さい会社が自社の化合物をより大きい会社の化合物と比較する場合には、より大きい会社はＬ１に含まれる情報に影響を与える者である。より大きい会社は、より小さい会社にそれ以上伝えるに値することが存在するものと判定すれば、そうすることを決定する。より小さい会社は、大きい会社にさらに事を進めさせる力はなく；その関係は非対称である。
【００９６】
他の場合には、一旦、有益な商取引を実施することができることの証拠が存在すると、両方の側がそれぞれの主要なデータを示すであろう、という理解が存在する。例えば、売買取引、恐らくは家屋の販売の場合を考える。家の所有者（売り手）が、進んで受け入れる最低価格を表すビット・ストリングを作成し、売り手は、価格が１０００ドルに最も近く示されることについて入札者と同意することによってこのことを行い、そして長さ１０００ビットのビット・ストリングから開始する。売り手が最低限受け入れ可能な価格が４００，０００ドルであれば、売り手は最初の４００ビットを１にセットし、残りを０にセットする。予想される買い手が考えることができる最高額の入札が４２０，０００ドルであれば、この買い手は、４２０ビット目の値以外はすべて０であるストリングを作成し、４２０ビット目は１にセットする。次に、ＡＳＣプロトコルに従って売り手がＬ１を受信し、売り手は、入札者のビット・ストリングと自分のビット・ストリングとの間に４０１の距離が存在することを見出す。このことは、入札者がセットしたビットが４００番目のビットよりも高位であった場合のみに発生し、即ち、このビットでは売り手のビットが０になっている。入札者の最高価格が例えば３８０，０００ドルであった場合、入札者は３８０番目のビットを１にセットしており（他のビットは１にセットしておらず）、売り手は、ストリング間で３９９個のビットが異なっていることを見出し、これは、売り手が受け入れ可能な最低価格よりも少し低いことを示している。しかし、これはＡＳＣであるので、売り手は最高額の入札の実際値を知らず、妥結する用意のある価格を上回るか（下回るか）否かしか知らない。従って、４０１ビットが１にセットされていることを売り手が見出した場合、売り手はさらに議論を進める価値があることを知り；逆に、３９９ビットが１にセットされていることを売り手が見出した場合、当事者が互いの時間を無駄にしても意味がない。要するに、ＡＳＣ法は、売り手と買い手とが取引の可能性から始める指標を提供するに過ぎない。ＡＳＣ法は、買い手の最初の入札が売り手が要求する価格を大幅に上回か否かを、いずれの当事者にも伝えない。
【００９７】
買い手がＬ１について売り手に嘘をつくことは無意味であることが興味深い。入札が一致している場合（即ち、二者間に「ギャップ」が存在せず：要求する価格が購入価格未満である場合）、両当事者を満足させるか両当事者を痛み分けさせる価格に達することができることを売り手が知ると、交渉から引き下がる。双方の期待が一致していない際に、一方の当事者が交渉したいことを他方の当事者に伝えると、同等に欲求不満になるはずである。Ｌ１が両当事者にとって有益であることが両当事者の関心事である。ここでＡＳＣは実際的な有用性を有する、というのは、それぞれの当事者の立場について何も開示することなしに合意の可能性が存在することを、当事者が認めているからである。
【００９８】
このプロセスを種々の形態で図３Ａ〜３Ｈに、１６ビットを有するビット・ストリング及び当事者Ａ（売り手）と当事者Ｂ（買い手）との間の取引について例示する。各場合に、Ｂの入札は異なるように表現され、ＡＳＣの結果はＡ ＸＯＲ Ｂ、及びＬ１の値として示す。記号
（外３）
2018531431.tif 000009
は、ストリング内のビットの総和を計算する演算子を示す。各場合に、スクランブルしたＡ ＸＯＲ Ｂのストリングも示す。もちろん、スクランブルは、Ａ ＸＯＲ Ｂ中の０にセットされたビットが位置する箇所を目立たなくする。
【００９９】
図３Ａ及び３Ｂでは、Ｂの入札は単一のビットをセットすることによって表現される。図３Ａでは、当事者Ｂの入札が低額過ぎ、図３Ｂでは、当事者Ｂの入札が高額である。従って、図３Ａ及び３Ｂでは、１ビットのみを用いることによって、Ｂの入札がＡが提示する価格よりも大きいか小さいかだけを示すことができる。
【０１００】
図３Ｃ〜３Ｅでは、（同じ１６ビットのビット・ストリングについて）、入札者（Ｂ）が、１にセットされた２つの隣接するビットを用いれば、入札が要求される価格よりも大きいか、要求される価格に等しいか、要求される価格よりも小さいかを示すことができる。各場合に、２つのセットされたビットのうち低位の方がその入札であり；それに隣接する第２のビットをより高位の側に追加して、区別を実現する。今度は、Ａが要求する価格との０、１、または２ビットのオーバーラップ（重複）を有することができる。ここで、当事者は、入札が(i)売値よりも高いか（図３Ｃ）、(ii)売値に等しいか（図３Ｄ）、あるいは(iii)売値よりも低いかを実際に伝えることができる。本明細書では、このことを「ＧＥＬ」（より高い、等しい、より低い）と称する。
【０１０１】
ＧＥＬ方式を拡張して、図３Ｆ〜３Ｈに例示するように、２つの数値範囲がオーバーラップするか否かを判定することができ、これらの図では、売り手Ａが、自分が希望する売値を２つの境界内で表現し（境界間の範囲内のすべてのビットがセットされている）、入札者は、自分の範囲の両端のビットを「オン」にセットする。図３Ｆでは、これらの範囲が一方の端でオーバラップしているのに対し、図３Ｇでは、これらの範囲がオーバーラップしていない。図３Ｈは、入札の範囲が要求される範囲の内側にある状況を例示する。
【０１０２】
その代わりに、当事者の立場のＡＳＣ比較後に、それぞれの主要データを開示するという２つの当事者の合意が存在し得る。例えば、合意の一種は、買い手が売り手の最低額を上回る価格価格で進んで購入する場合、当事者は直ちに、売り手の最低額と入札者の最高額との差を互いに分け合うことに当事者が合意する、ということとすることができる。以上の例示では、このことは、４１０，０００ドルの価格で合意することを意味する。
【０１０３】
この例では、ＡＳＣのＧＭコンポーネント（構成要素）の他の性質が有用であり、ボブが自分の価格をごまかしていないことをアリスが確信することを可能にするために設立された二次的メカニズムを可能にする。ＧＭ用の暗号解読キーは大きな素因数であり、符号化Ｎのｐ及びｑである。上記の例では、ボブがアリスのビット・ストリングのコピーをＮと共に受信して、自分の符号化を可能にする。アリスが、一旦Ｌ１を知って、自分とボブが商取引を行うことを決めた場合、彼ら二人は、アリスがｐ及びｑを公表することに同意していることがある。家屋を購入する例では、このことは、アリスが最低限受け入れ可能な売値をボブ（入札者）が直ちに見出すことを意味する。事実上、ここでは非対称性が入れ替えられている！今度は、ボブがアリスよりも多くの情報を有する！ボブは、アリスが商取引をしたいか否かを示すＬ１を知っているが、ボブはアリスの情報の主要なものも知っており、即ち、アリスが購入価格として進んで受け入れる最低額を知っている。アリスはＬ１しか知らないが、アリスは、自分が保持するストリングからは、ボブの元のストリングが実際にどうであったかは分からない。しかし、ボブが、自分がスクランブルしたＡＳＣストリングに加えて、自分の実際の購入価格を、但しＲＳＡ方式を用いて符号化していれば、バランスを取り戻すことができる。即ち、ボブは、自分の（暗号化した）真の価格を、式(8)からのＮ及びｅと共にアリスに送信する。アリスが自分の秘密キーを示せば、ボブはアリスが最低限受け入れ可能な価格を知るが、自分のキーを返す以外に選択肢はなく、従ってアリスはボブが最大限受け入れ可能な価格を知ることができる。あらゆる拒絶が不誠実になる、というのは、こうした価格が、アリスが提示する最低限の閾値を上回ることを、ボブのＡＳＣストリングがアリスに伝えているからである。従って、ＡＳＣプロトコルとＰＮＦアルゴリズムの「ロックボックス」機能との組合せが、このように組み合わせたプロトコルのある程度の対称性を可能にする。こうした組合せが、ＡＳＣをより概ね対称なプロトコル「対称的に用いられる非対称で安全な比較（ＡＳＣＵＳ：Asymmetric Secure Comparison Used Symmetrically）」にする方法は、以下でさらに説明する。
【０１０４】
対称性は、以下に続く開示が起こりそうにない状況において重要な特徴である。背景の節で参照した例を考え、今度は、暦年中にどちらがより多額の金を稼いでいるかという問題にＡＳＣを適用する。１ドルを賭ける友好的な者がいて、より多額を稼ぐ人の所、あるいは最少額を稼ぐ人の所、のいずれかに行くが、いずれの当事者も自分の実際の給料を公表しないことの合意があるものとする。前述した（図３Ａ〜３Ｅの）家屋の価格のシナリオに従うが、当事者が  想定される売値として今回は自分の給料を公式に符号化している場合、Ｌ１の受信者であるアリスは、自分がボブよりも多く稼いでいるか少なく稼いでいるかを知る。しかし、家屋の価格の変形例におけるように、彼ら二人が自分の主要なデータを公表しようとしない場合、アリスは自分のキーを有し、ボブはアリスに送信したロックボックスのキーを有し、アリスが上記の１ドルを受け取るために嘘をついているか否かをボブが知る方法は存在しない。対称な比較では、ボブもＬ１を知るが、アリスに尋ねる必要はない。表面的には、このことを実現することは困難であるように思われる。同時に、アリスが自分のキーで暗号化した自分のストリングをボブに送信し、ボブは、自分のキーで暗号化した自分のストリングをアリスに送信し、各自がＡＳＣプロトコルに従う場合、各自がＬ１に到達するはずである。さらに、暗号化してスクランブルしたビット・ストリングを元の当事者に返送する、ＡＳＣにおける最終ステップは、ＰＮＦの「ロックボックス」内にまとめることができ、即ち、アリス及びボブの両者がＬ１を同時に見出すことができる、というのは、彼ら二人は、次に互いのキーを要求して、暗号化してスクランブルしたそれぞれのビット・ストリングがどのように見えるかを見出すからである。この仮定には２つの良くない点があることが分かっている。
【０１０５】
ＡＳＣＵＳ問題点１
アリスは正直であるが、ボブは正直でないものと仮定する。ボブがアリスに送信してＸＯＲをとられるストリングとは異なるストリングを用いて、アリスがボブに送信するストリングに対して（ボブの暗号化に基づいて）ＸＯＲをとることを、「悪意あるボブ」が行うことは止めさせようがない。このことを、化学的比較に関連して想定する。恐らくは、悪意あるボブは、自分の化合物がアリスの化合物に非常に近いことを疑っているが、アリスがこのことを知って欲しくない。アリスが暗号化した指紋をボブが受信すると、ボブは自分のではなくランダムな化合物に対してＸＯＲをとり、その結果をスクランブルしてアリスに返送する。その間に、ボブは自分の実際の化合物をアリスに送信しており、アリスは、正直に、この化合物に対して自分の貴重な化合物のＸＯＲをとって、その結果をボブに返送する。アリスは、両者が非常に異なる化合物を有していると思い込んで終わるのに対し、悪意あるボブは他のことを知っている。
【０１０６】
ＡＣＵＳの問題点２
ＡＳＣＵＳの問題点１におけるように、悪意あるボブがアリスをだまして、両者が非常に類似した化合物を有するものと信じ込ませる。ボブがアリスの化合物を知っていれば、ボブは厳密に一致する指紋を生成して、アリスの化合物に対してＸＯＲをとって、スクランブルしたストリングをアリスに送信することができ、アリスはこのストリングを非常に類似した化合物に由来するものと解釈し、即ち、ＸＯＲ後に非常に相違が少ないものと解釈する。しかし、悪意あるボブはアリスの主要な化合物を知らず；ボブはその後に知る（例えば、恐らくはアリスをだまして主要なデータを開示させる）。しかし、このことは悪意あるボブにとって問題ではない。ボブはアリスからの暗号化キーを有し、従って、ボブは、アリスに返送したいストリングを任意数のビットで作り上げることができ、即ち、アリスは、自分に返送されたストリングが実際には何物かに対してＸＯＲをとられていないことを知る方法がない。
【０１０７】
ＡＣＳＵＳの問題点１及び２は難しい問題であり、元々非対称でない状況にＡＳＣ法を適用する問題を反映している。賭け金にされた１ドルが存在しても、不正直な挙動の結果は存在しないことがある。しかし、ＡＳＣを部分的にＡＳＣＵＳにすることができる、ＡＳＣに加える２つの適応が存在し、即ち、これにより、悪意あるボブの本性が見出される可能性はある程度存在する。
【０１０８】
ＡＳＣＵＳの適応１
今までは、ＡＳＣの対称な応用に基づくＡＳＣＵＳでは、各当事者がＬ１を伝える必要はない。しかし、Ｌ１の伝達が合意の必要な部分をなしているものとする。各自が（他の当事者から返送された、暗号化したＸＯＲストリングを受信した際に自分が計算した）Ｌ１を他の当事者に提出しなければならないが、上述した暗号化したロックボックスによって提出するものとする。こうした方法で、ＡＳＣＵＳの第１の問題点に応えることができる。ＡＳＣＵＳの第１の問題点では、ボブが、自分の分子を表すものとは異なる分子を選定し、ＸＯＲをとり、スクランブルしてアリスに返送している。しかし、このことはボブがアリスのＬ１を知らないことを意味する。ボブはそれを当てることしかできない。ボブが正直であったとして、正しい指紋を用いたならば、ボブはアリスの分子に対するＬ１を知ることになるが、ボブはそれを知ることがない。もちろん、アリスが自分のＬ１を示せば、悪意あるボブはこの番号を自分自身の番号として復唱して返送することができる。しかし、その代わりに、これら２つの番号がロックボックスに入っていれば、ボブは、自分が申告したＬ１をアリスのものにすり替えることはできない。このため、アリスは自分のＬ１を計算し、ロックボックスを介してボブのＬ１を受信し、そしてこれらの番号が同じでない（なさそうな）ことを見出して、ボブが不正直であったことを知る。もちろん、悪意あるボブがアリスのＬ１を当てることはあり得るが、その勝算は通常、ボブに非常に不利であり：ボブは、自分が実際に用いた分子がアリスの未知の構造とどれだけ異なるかを知る方法がない。
【０１０９】
この方式を図５Ａに例示し、この方式は４つの段階（５２０）、（５３０）、（５４０）、及び（５５０）を構成し、これらの段階のうち最初の３つは、図２Ｂに示すそれぞれの段階と同じである。図５Ａ中の最後の段階は、追加的な検証ステップである。
【０１１０】
図５Ａでは、当事者１及び当事者２が安全な取引に入る。これらの当事者のそれぞれの機密情報が指紋１（５０５）及び指紋２（５０６）として表現される。図５Ａ中の第１段階（５２０）では、当事者がそれぞれの指紋を安全な方法で互いに交換する（５０３）、（５０４）。各当事者は、両方の指紋を「同期ＡＳＣ」プロセスに提出し、図５Ａでは、当事者１及び当事者２用の同期ＡＳＣプロセスが、それぞれ（５０７）及び（５０８）で表される。それぞれの同期ＡＳＣプロセスは、当事者１のＬ１−１（５０９）及び当事者２のＬ１−２（５１０）を生成する。
【０１１１】
その間に、段階２（５３０）では、当事者１及び当事者２が、それぞれのＲＳＡキー１（５１５）及びＲＳＡキー２（５１６）を生成し（５０１）、（５０２）、これらのキーは互いに異なる。それぞれのキーを用いて、これらの当事者のＬ１を次のように暗号化する：当事者１は、キー１（５１５）を用いてＬ１−１（５０９）を暗号化して（５１１）、暗号化したＬ１−１（５１４）を生成して当事者２に送信する（５１７）。これに対応して、当事者２は、キー２（５１６）を用いてＬ１−２（５１０）を暗号化して（５１２）、暗号化したＬ１−２を当事者１に送信する。
【０１１２】
段階３（５４０）では、２つの当事者が、秘密キー１（５２１）及び秘密キー２（５２４）を用いて、他の当事者から受信した、それぞれの暗号化したＬ１−１及びＬ１−２を暗号解読し（５１９）、（５２２）、これにより、それぞれのＬ１−１（５０９）及びＬ１−２（５１０）の元の値を取り出す。
【０１１３】
ここで、当事者１は、当事者２のＬ１−２を暗号解読した値が自分自身の元のＬ１−１と同じであるか否かをチェックし（５２５）、これに対応して、当事者２は、当事者１のＬ１−１の値が自分自身の元のＬ１−２と同じであるか否かをチェックする（５２８）。各場合に、それぞれがチェックした値が互いに同じであれば、プロセスを停止する（５２９）、（５３４）。そうでなければ、いずれの当事者も、問題があるか否かを確認することができる（５２７）、（５２８）。
【０１１４】
ＡＳＣＵＳの適応２．
ＡＳＣＵＳの適応１は、ＡＳＣＵＳの問題点２に直面すれば、即ち、悪意あるボブが、アリスがボブに送信する公開キーを完全に最初から用いて、ＸＯＲをとってスクランブルした自分のストリングであるとするものを構成する場合には、役に立たない。ここで、ボブは、アリスが知覚するものを正確に知っており、この番号をロックボックス内に置いて、でっち上げた返送用ストリングと共にアリスに送信することができる。アリスはこのストリングを暗号解読し、ロックボックスを解錠して、何も間違っていないものと信じる。一見して、対称にされたＡＳＣでは、このことはアリスの信頼にとって乗り越えられない問題であるように思われる。（アリスは、自分が見るものがボブが見るものであることについて、ボブを信頼することができない。）
【０１１５】
しかし、指紋中でセットされたビットの数は少数である。このことは、一般に分子の指紋の場合である。さらに、２つの指紋間でいつも異なり得るビットの数は、常にビット数の半分未満であるものと仮定する。こうした状況では、アリス及びボブは実際に、Ｌ１を取り出すために互いに対して送信することができるストリングにおいて、２つの選択肢を有する。彼ら二人は、それぞれの分子構造について通常のビット・ストリングを送信することができ、あるいは、彼ら二人は自分のストリングの補数、即ち、すべての０が１にされ、すべての１が０にされたストリングをを送信することができる。ここで、ＸＯＲ演算によって明らかにしたすべての相違を同値として記録し、すべての同値を相違にする。ビット・ストリングが長さＫであり、２つのストリング間にｈ個（箇所）の相違が存在する場合、一方のストリングをこの方法で「反転」させれば、Ｈ＝Ｋ−ｈ個の相違が存在する。両方のストリングを反転させれば、相違の個数は再びｈに等しくなる。ｈ＜Ｋ／２という上記の条件下では、アリスまたはボブが自分のストリングに施す反転の入れ替えがどうであれ、彼ら二人は真のｈを常に解明することができる。即ち、次式のようになる：
【数５】
2018531431.tif 000010
従って、セットされたビットの見かけの数がＫ／２より大きければ、実際の数はＫ−ｈである。
【０１１６】
従って、Ｌ１についての情報を収集する意味では、アリスまたはボブが自分の真のストリングを送信するか自分のストリングの補数を送信するかに違いはない。しかし、ボブが偽のＸＯＲストリングをでっち上げる場合には、違いが生じる。ボブは、アリスがＫ／２よりも大きいビット数を期待しているかＫ／２よりも小さいビット数を期待しているかを知る方法がない。このことは、ボブがアクセスできない情報に依存する。ボブは、自分のＬ１から知覚しているビット数をアリスに送信して初めて、このビット数を知ることができる。例として、ビット・ストリング長が２０であり、正しいＬ１は２であるが、悪意あるボブは、５ビットが１にセットされた、即ち５であるＬ１に対応する偽のＸＯＲストリングをアリスに送信しようとしている。悪意あるボブは、アリスが自分に返送したＸＯＲストリング中に１にセットされた５つのビットが見られることをアリスに報告しなければならない、というのは、これが、アリスが自分のストリング中に見る（ビット）数であり、ボブがそのように作り上げているからである！しかし、アリスは、実際には、暗号化したストリングを反転してボブに送信しており、アリスは、５つではなく１５個のビットが見えるものと期待しているはずである。悪意あるボブは誤った数を伝えており、しかも自分の報告を変更することはできない。アリスがストリングをランダムに反転させていれば、悪意あるボブが見破られる５０％の可能性が常に存在する。
【０１１７】
従って、こうしたＡＣＳと何らかのＰＮＦロックボックス適応との組合せは、ビット密度が５０％未満であることが分かっている場合、不正を少なくとも５０％の効率で発見することができるＡＳＣＵＳのバージョンを作り上げることができる。しかし、一見すれば、ＡＳＣＵＳの悪用の２形態、即ち、他の当事者が暗号化したストリングに対して異なるストリングを用いてＸＯＲをとること、あるいは、偽の暗号化したＸＯＲストリングを生成することに対する保護は、同等に効果的でないように思われる。
【０１１８】
前者の場合には、悪意あるボブは、自分の代わりのビット・ストリングとアリスからのストリングとの間でいくつのビットが異なるかを当てなければならない。ボブは、こうした相違の予備知識を有さないので、このことは困難な作業となり得る。例えば、代表的な相違が、均等に、１個（箇所）から１００個までの範囲に及ぶ場合、ボブが見破られない可能性は１／１００しかない。この値は、ボブが偽のＸＯＲストリングを構成する場合の１／２のリスクよりもずっと小さい。しかし、これら２つの状況間には１つの違いがある。彼らが自分達のストリングを再検査することを要求するものとする。悪意あるボブがあるＸＯＲストリングを構成していたならば、ボブは、初回の検査より前と同じ状況のままである。上記の例では、ボブは、５ビットがセットされたストリングを構成するか１５ビットがセットされたストリングを構成するかを決めなければならず、ボブは、そのどちらを受信することをアリスが期待しているかを知ることができず、回数の５０％は誤る。即ち、検査毎に、悪意あるボブが見破られる１／２の確率が独立して存在する。
【０１１９】
この状況は、導入部で言及したゼロ知識証明に非常に特有である。例えば、古典的なＺＫＰの例を図４Ａ〜４Ｃに示す。ここでは、その思想は、記号「Ａ」及び「Ｂ」を付けた２つの開口を有するループ化された通路（４０５）が存在し、通路のいずれかの端（４０１）、（４０３）にも１つの開口が存在するが、通路（４０５）は魔法のドア（４０７）によって内部が閉鎖されており、魔法のドアを開けるためには秘密のパスワードが必要である。この通路に入って正しい端（ＡまたはＢ）からうまく出ることができるための作業は、一切れの紙に書き留められた命令に基づく。人は、基本的には、出るための秘密の命令を持って入る。人は、このトンネルの内部に入るまでは、その命令を開封しない。例えば、ボブがドア（４０７）に対するパスワードを知りたいと主張する。アリスは、「Ａ」または「Ｂ」を一切れの紙に書き留め、封筒に入れ封印してボブに手渡す。次に、アリスは、ボブが一方の出入り口（４０１）または他方の出入り口（４０３）の中に姿を消すことを見届ける。ボブが見えなくなると、ボブは封筒を開封することを許され、封筒の中身は、ボブが通って戻る必要がある通路をボブに伝える。ボブがＡの側に行っており、アリスの書置きが「Ａ」であれば、ボブは単に向き直って戻ってくる。しかし、アリスの書置きが「Ｂ」であり、ボブが「Ａ」を通って入っていれば、ボブは、パスワードを知っていれば、書置きに従うことしかできない。ボブがパスワードを知っていなければ、ボブがアリスの要求に従う可能性は５０％であるが、ボブがパスワードを知っていれば、その可能性は１００％である。このプロセスには確率的要素が存在する。この手順を１回繰り返す場合、ボブがパスワードを知っていなければ、ボブが２回とも書置きに従う可能性は２５％に低下し、従って、これに続く例では１２．５％に低下し、即ち、毎回書置きに従う確率は１／２Nであり、ここにＮは試行の回数である。ボブがアリスからの（ランダムな）命令に従い続ければ、ボブがパスワードを知っていることを、ボブが決してアリスに示さなくても、アリスはますます確信することができる。
【０１２０】
しかし、図４に関して説明したＺＫＰと、本発明におけるＡＳＣの状況とには、重要な相違がある。ボブがアリスによって「テストされる」毎に、ボブは、アリスのビット・ストリングに対して選定するビット・ストリングを調整することにもなり；即ち、ボブは実際に情報を得る。このことは不可避である、というのは、ＡＳＣはゼロ知識のテストではないからである。「類似性」を知ることの概念は、少なくともいくらかの知識を暗に意味する。例えば、ボブはまず全部０のビット・ストリングを用いることができ：このことは、アリスのストリング中にいくつのビットがセットされているかをボブに伝える。次に、ボブは、体系的に、一度に１つのビットを「オン」にして、アリスの指紋中のどのビットがセットされているかを特定することができる。基本的に、ボブは、アリスが要求するテスト毎に１ビットの情報を得る。
【０１２１】
しかし、悪意あるボブは、偽のＸＯＲストリングの方策を進めておらず、その代わりに、単に異なる分子の指紋に置き換えているものとする。ボブが、初回に、アリスが自分のＬ１中に見るビット数を正しく当てていれば、ボブは、今後のテストのために、単に、この数を常に報告することを知る。その間に、各テストは、アリスにとっての安全性を何ら加えることなしに、アリスのストリングの匿名性を徐々に、一度に１ビットずつそぎ落としていく。換言すれば、相補性のテストは適用するのは簡単であるが、限界がある。しかし、これらの例は、ＡＳＣＵＳを不正直さに対してよりロバストにするためのより良い方法を示唆している。核となる見解は、ＰＮＦロックボックスを介してアリスに報告するべきことに対するボブの不確実性を低減するもののいずれも、安全性を増加させる、ということである。ボブが、暗号化してＸＯＲをとるステップにおいて異なる指紋を用いれば、ボブはアリスが見るものの知識を失う。ボブが、アリスが見るものを知っていると確信していれば、アリスがランダムに適用したビット・ストリングの反転がこの確実性を取り去る。以下の方法「ランダム・ビット・パディング（付加）」（ＲＢＰ：random bit padding）が両見解に基づいて構築される。
【０１２２】
ＡＳＣＵＳ及びランダム・ビット・パディング
アリス及びボブがストリングを比較するプロセスを開始する前に、彼ら二人は長さＭのビット・ストリングをランダムに生成する手順を決めるものとする。このことは、ビットをランダムにセットすることに合意することによって、あるいは、この長さの既存のビット・ストリングの集合からランダムに選択することによって行うことができる。彼ら二人は、各自がこうしたランダムなストリングを秘密裏に生成して、このストリングを、彼ら二人が比較したい指紋に付加することに合意している。彼ら二人は、さらに、自分の指紋の２つのバージョンを作成することに合意し、各バージョンは、異なるこの種のランダムなストリングを有し：一方のバージョンは、他方の当事者が提供したキーでＧＭ暗号化されて検査用に他者に送信され、他方のバージョンは、自分自身のＧＭキーで暗号化され、他者が暗号化したストリングに対してローカルにＸＯＲをとられている。実際に、彼ら二人は共に、ＡＳＣＵＳの問題点１の悪事、即ち：異なる公開ストリング及び秘密ストリングの使用を犯すことに合意している。しかし、各自は、どのようなランダム・ストリングを生成したかも、同じＰＮＦロックボックス内に記録しており、このロックボックスは、後に、Ｌ１についての彼ら二人の主張を含む。ここでの予想は、これらのＬ１の値が同じではないことであるはずである、ということが直ちにわかる。このことが、ＡＳＣＵＳの問題点１を理解する方法であり、即ち、一方の側が同じ公開ストリング及び秘密ストリングを使用しなければ、ボブまたはアリスは、両方のＬ１の値を知ることを保証されないからである。しかし、ランダム・ストリングを記録しているので、これらを入手すれば、アリス及びボブは共にバックトラックして（逆に辿って）、互いのＬ１の値から彼ら二人のランダム・ストリングを減じたものが実際に確かに一致しているか否かを確かめることができる。両者が正直であったならば、このことはその通りになるはずであるが、こうしたランダム・ストリングの使用は、不正直な挙動にとっては関心事の実現となる。この方式を図５Ｂに例示し、その簡略化した概要を図５Ｃに示す。
【０１２３】
図５Ｂ、５Ｃ中の方式の４つの段階は次の通りである：第１段階（５６０）では、当事者１及び当事者２がそれぞれのＲＳＡキー及びランダム・ビット・パディング（ＲＢＰ）を生成し、その後者を暗号化してデジタル・ロックボックス内で他の当事者と共有し、即ち、このロックボックスは後になるまで開くことはできない。第２段階（５７０）では、当事者１及び当事者２が（自分自身のＲＢＰを用いて）それぞれのパディング付き指紋を作成し、これらの指紋をＡＳＣを介して共有して、各当事者がそれぞれのＬ１を計算することを可能にし、次に、これらのＬ１を暗号化して、第１段階でのランダム・ビット・パディングと同じ方法で、即ち、デジタル・ロックボックス内に共有する。第３段階（５８０）では、相手の当事者のランダム・ビット・パディング及びＬ１を各当事者が暗号解読して（デジタル・ロックボックスを開いて）、各当事者が観測したＬ１と比較し、これらのＬ１は受信したランダム・ビット・パディングに応じて調整されている。最終段階（５９０）は検証であり：これらのＬ１どうしが実際に一致しているか否かを確かめるためのチェックである。
【０１２４】
図５Ｂに示す実施形態では、当事者１及び当事者２を、それぞれ「アリス」及び「ボブ」に置き換える。
【０１２５】
一般的な意味で、図５Ｂでは、取引を行う当事者、アリス及びボブが、それぞれ指紋Ａ（５６１）及び指紋Ｂ（５６４）を有し、それぞれがＲＳＡキーを生成し（５５１）、（５５２）、これらのＲＳＡキーは、それぞれ、秘密キーＡ（５３３ａ）と公開キーＡ（５５４ａ）、及び秘密キーＢ（５５３ｂ）と公開キーＢ（５５４ｂ）を与える。２つの当事者間で公開キーＡとＢを交換する（５４８）（図面中の「交換１」）。
【０１２６】
アリス及びボブは、それぞれ、２組のランダム・ビット・パディングも生成しており、即ち：ランダム・ビット・パディングＡ１（５５７−１）、ビット・パディングＡ２（５５７−２）、ビット・パディングＢ１（５５８−１）、及びビット・パディングＢ２（５５８−２）である。それぞれの当事者は、それぞれの公開キーＡ（５５４ａ）及び公開キーＢ（５５４ｂ）を用いて、これらのＲＢＰを暗号化して（５５５）、（５５６）、暗号化したランダム・ビット・パディングＡ１（５６２−１）、暗号化したランダム・ビット・パディングＡ２（５６２−２）、暗号化したランダム・ビット・パディングＢ１（５５９−１）、及び暗号化したランダム・ビット・パディングＢ２（５５９−１）を作成し、これらの各々を他の当事者に送信する（５４９）（図面中の「交換２」）。
【０１２７】
第２段階（５７０）では（「ＸＦＰはパディング付き指紋を表す」）アリスは自分の指紋Ａ（５６１）を受け取り、ランダム・ビット・パディングＡ１（５５７−１）及びランダム・ビット・パディングＡ２（５５７−２）のそれぞれと併合して、パディング付き指紋Ａ１（５６５−１）及びパディング付き指紋Ａ２（５６５−２）を作成する。ボブは、指紋Ｂ（５６４）及びランダム・ビット・パディングＢ１（５５８−１）とランダム・ビット・パディングＢ２（５５８−２）で同じことを行って、それぞれのパディング付き指紋Ｂ１（５６８−１）及びパディング付き指紋Ｂ２（５６８−２）を作成する。
【０１２８】
ここで、ボブは、パディング付き指紋Ａ１及びパディング付き指紋Ｂ１にＡＳＣ（５７２）を適用して、「Ｌ１Ｂ」（５８２）で表されるＬ１の値を作成する。
【０１２９】
これに対応して、アリスは、パディング付き指紋Ａ２及びＢ２にＡＳＣ（５６７）を適用することにより、Ｌ１Ａ（５７７）を作成する。
【０１３０】
これら２つのＬ１（５７７）及び（５８４）は必ずしも互いに同じではない、というのは、これらを形成した元の指紋は、異なるビット・ストリングをパディングされていることが多いからである。
【０１３１】
第２段階の終わりに、２つの当事者はこれらのＬ１の値を区間する（５４６）（図面中の「交換３」）。図面中には示していないが、これらの当事者は、例えば公開キーＡ及びＢで暗号化したＬ１の暗号化値を交換することができる。
【０１３２】
第３段階では、アリスが秘密キー（５５３ａ）をボブに送信する（５４５）。これに対応して、ボブは秘密キー（５７６）をアリスに送信する（５５４）（図面中の「交換４」）。
【０１３３】
次に、アリスは、暗号化したランダム・ビット・パディングＢ１（５５９−１）及びＢ２（５５９−２）を暗号解読する（５７１）に当たり秘密キーＢを使用し、これによりランダム・ビット・パディングＢ１（５５８−１）及びＢ２（５５８−２）を取り出す。
【０１３４】
これに対応して、ボブは、暗号化したランダム・ビット・パディングＡ１（５６２−１）及びＡ２（５６２−２）を暗号解読する（５７８）に当たり秘密キーＡを使用し、これによりランダム・ビット・パディングＡ１（５５７−１）及びＢ２（５５７−２）を取り出す。
【０１３５】
次に、アリスは、すべてのランダム・ビット・パターンについての自分の知識を用いて、２つのＬ１（図５Ａ参照）を調整して（５７３）２つの別個のＬ１を作成し、これらはＬ１Ａ’（５７９）及びＬ１Ｂ’（５８４）で表される。これら２つの値を検査して、これらが互いに同じであるか否かを確かめ、同じであればプロセスを停止し（５８５）；そうでなければ問題をフラグで知らせる（５８３）。（段階２でＬ１を暗号化していれば、この調整の前にこれらのＬ１を暗号解読する。）
【０１３６】
同様に、ボブは同じ２つのＬ１を調整して、２つの別個のＬ１（５８２）、（５８４）を作成する。これら２つを検査して、これらが互いに同じであるか否かを確かめ（５８６）、同じであればプロセスを停止し（５９２）；そうでなければ問題をフラグで知らせる（５８８）。
【０１３７】
ここで、ランダム・ストリングの使用を含む２つのシナリオを考える。
【０１３８】
シナリオ１：悪意あるボブが、アリスに送信する公開の分子とは異なる分子のビット・ストリングを自分の秘密ストリングとして用いる。ＲＢＰなしでは、悪意あるボブは、アリスの分子に代わる自分の分子のＬ１を当てることを強いられる。ここではボブがいくらかの助けを受ける、というのは、ボブが自分の実際の分子に対して推し量るＬ１が、アリスが見るＬ１についていくらかの情報を提供し得るからであり、即ち、ボブの公開ストリングと秘密ストリングとが、異なってはいるが比較的類似している場合である。ここでのＲＢＰの主要な特徴は、悪意あるボブは、自分のバージョンのＬ１を記録した後まで、即ち、ＲＢＰが示された後まで、実際のＬ１を知らないということである。即ち、ボブは真のヒントを全く与えられない、というのはランダム要素が挿入されているからである。アリスが繰り返しの推し量り、即ち、ＡＳＣＵＳの問題点２を検出するに当たり有用なもの、即ち、偽の返送ストリングを求めれば、この利点は度合いを増す。換言すれば、通常、ボブは、各回の後に、アリスのストリングについての自分の知識を改善することができるが、ここでは、ＲＢＰの値を複数回の検査の終わりまで保持しておき、実際の知識の蓄積を防止することができる。
【０１３９】
シナリオ２：悪意あるボブが、アリスに返送するＸＯＲストリングを、全体的に、あるいはランダム部分に属するサブストリングを付加して、のいずれかで偽る。前者の場合には、ボブは、アリスが記録する初期のＬ１を正確に知り、後者の場合には、ボブは、ＲＢＰが公表されアリスがこのＲＢＰを自分のＬ１から減じた際に、ボブはアリスが見出す値を知る。上記では、アリスがビット・ストリング反転を用いて、ボブが偽のＸＯＲストリングを構成しているか否かを５０％の成功率で検査することができる方法を説明しており、この検査は反復することができるが、ボブがアリスのストリングについて一層知る可能性があるという代償を払う。ここではこの状況を考える。ボブがどちらの選択肢を選定するかにかかわらず、ボブは、アリスに報告するべきＬ１を知らない、というのは、ボブは自分のＸＯＲストリング中にいくつのランダムビットがあるかを知らないからである。問題は：アリスのＸＯＲストリングについてのボブの知識はもはや役に立たず：アリスは、ボブがそれを明確にすることは期待していない、ということにある、というのは、両者のストリングにはランダム要素が付いているからである。アリスは、これらのランダム要素を減じた後に数どうしが一致することを期待しており、このランダム要素はボブが知らない。以下は単純な例であり、各数値は表１からのものである。
【０１４０】
【表１】
2018531431.tif 000011
【０１４１】
表１中の数値は、ボブ及びアリスが暗号解読することができるＸＯＲストリングの各部分中で１にセットされたビット数を表す。もちろん、これらのストリングはスクランブルされており、従って、彼ら二人はその分解を見ることはできない。しかし、ロックボックスを開けた後には、彼ら二人は、自分達が考えたＲＢＰ要素がわかる。
【０１４２】
悪意あるボブが、アリスのビット・ストリング全体を合成するものと仮定する。アリスは、ロックボックスを開くと、「オン」になった８つのビットが存在することがわかり、アリスは、これらのビットのうちの３つがＲＢＰに由来していることがわかり：この数は、ボブがそれより早く操作するか知ることができる数ではない。従って、アリスは、正しいＬ１は５であるものと確信する。アリスは、ボブのＸＯＲストリング中のＲＢＰより、ボブが５ビットを有していたはずであることもわかり；これもボブがそれより早く操作するか知ることができる数ではない。従ってアリスは、ボブが１０のＬ１を報告するはずであるものと推論する。ここで、悪意あるボブがアリスのストリングを構成するものとすれば、ボブは、アリスが８ビットを見ることを知り、ボブは、自分自身の７ビットが存在することはわかるが、ボブがいずれかのＲＢＰ数を知らないものとすれば、アリスを満足させる１０のＬ１を報告するべきことを、ボブはどのようにして知るであろうか？アリスが見るビットの数をボブが知っている際でも、ボブは、自分の報告において、まだ知っていない２つの数の差によってこの数を調整する必要がある。なお、ここで、２つの異なるＲＢＰを有することがどれほど必要であろうか。これらのＲＢＰからのビット数が同じであったならば、アリスは、ボブが報告したＬ１が自分のＬ１と同じであることを期待するだけであり、ボブがアリスのストリング全体を偽れば、これはボブが容易に提供することができる何らかのものである。ボブが、どのような偽のＬ１をアリスに提出するかを知ることを防止するものは、これら２つのＲＢＰ間の差の不確定性である。この手順の実施例を図６Ａ及び６Ｂに示す。
【０１４３】
図６Ａでは、量Ｌ１B−Ｌ１RB（６０１）及びＬ１A−Ｌ１RA（６０３）を計算し、ここにＬ１A及びＬ１Bはストリングの全体部分を参照し、Ｌ１RA及びＬ１RBはストリングのランダムビット部分である。これらの量が互いに同じであれば（６０５）、プロセスを停止する（６０７）。
【０１４４】
図６Ｂでは、量Ｌ１B−Ｌ１RB（６０２）及びＬ１A−Ｌ１RA（６０４）を計算する。これらが互いに同じでなければ（６０６）、プロセスは問題があったことを報告する（６０８）。
【０１４５】
ＲＢＰの追加的な複雑性を各ビット・ストリングに含めることの効果は、ボブが有する、アリスを誤った方向に導くための２つの方法、即ち(1)アリスのビット・ストリングとのＸＯＲをとるものとは異なるビット・ストリングを用いて、(2)ボブが返送するビット・ストリングを完全に偽ることを、アリスが見破ることを同じくらい容易にする、ということである。実際に、ボブにとっての道筋(1)での困難さは、彼ら二人の２つのビット・ストリングの実際の類似性と、アリスのビット・ストリング−ボブが自分のビット・ストリングを置き換えたビット・ストリング間の類似性との相違を、ボブがうまく当てなければならないことである。道筋(2)では、ボブは、彼ら二人のビット・ストリングの実際の類似性と、ボブが構成する偽のビット・ストリング中でボブが「オン」にセットするビット数との相違を、ボブがうまく当てなければならない。ボブは、彼ら二人の２つの真のビット・ストリングの実際の類似性についての予備知識を必要とし、これはボブが事前に知ることができないことである（ボブが既にこれを知っていたならば、ボブはこれを見出すための口実を口にする必要はない。）ボブの不正直さが見つかる可能性は、上記いずれかの相違を推定することの困難さに直接比例する。アリスが保有するものをボブが当てることが先験的に困難である場合には、不正の確率は低くなる。ボブがうまく当てることができる場合、ボブがアリスをだます可能性は増加する。しかし、両者が同じ先験的な期待を有する場合、ボブはアリスを大いにだますことはできず、即ち、両者が自分達のストリングの類似性について妥当な期待を有する場合、アリスは、自分達のストリングが非常に異なることを示すボブによってだまされる可能性は低い。従って、ボブがアリスを誤った方向に導く可能性がより高い領域内であっても、ＡＳＣＵＳ手順からの結果をアリスが少なくとも疑う可能性もより高くなる。
【０１４６】
一般に、当事者が情報を安全に、あるいは秘密に保持したいことがある理由は多数存在する。これは、時々ではあるが、機密保持違反に至る商業的因果関係が存在するからであることが多く、人間の感情に起因して、人間は特定の情報についてはプライバシーを保ちたくなる。例えば、入札のプロセスを考える。一方の側が、他者が所有するものに対して入札する。売却されるアイテムへの感情的愛着がなければ、入札を開示するのに不都合な点は存在しない。しかし、そうでないことが多い。売却されるアイテムが事業であり、所有者が価値あるものを築き上げるために何年も尽力してきたものとし、しかも入札が「低く見積もられた」付け値であるものとする。所有者が拒否し得るだけでなく、この付け値が「侮辱的」に見えて、当事者間の将来の取引に摩擦を生じさせることがある。こうした状況では、「仕事上だけのこと」という格言に訴えるのが一般的であるが、それが一人の人物の生涯の仕事であった際には、「仕事上だけのこと」では済まされない。
【０１４７】
ＡＳＣＵＳは、両方の側に、関係を損なう恐れなしにやり取りする機会を与える。ベンチャー・コミュニティー（冒険的事業団体）における共通のルール、即ち「トップ（Topp）」ルールは、２つの側が価格において２という因数の範囲内であれば、取引に至り得るが、そうでなければ、先に進めない方がよい、というものである。所有者が自分の価格を考え出し、それを２で割ったものを自分の「最低限受け入れ可能な入札」として提示し、買い手は自分が購入を考える価格を提示すれば、ＡＳＣＵＳは、このルールのどちらの側に両者が該当するかを、両方の側が知ることを可能にする。価格がその範囲内でなければ、両者が期待を裏切られ得るが、いずれかの側が動揺するような単一の数字は存在しない。価格がその範囲内であれば、両方の側が真の入札を提出することが感情的により安全になり、所有者が求める最低額よりも多額を買い手が進んで支払う、という状況が存在するか否かを確かめ、この時点で、詳細な交渉無しに取引が均等になりやすい。実際に、この段階で、参加者は、さらなる交渉なしに自動的に取引に合意する機会を有する：というのは、参加者は共に入札及び要求価格を、但し暗号化形式で有し、参加者がしなければならないことは、自分のＧＭ暗号化キーを交換することだけである。ＡＳＣＵＳプロセスにおいて公開キーを交換することによって、参加者は自動的に「ロックボックス」を構成しており、即ち、既に送信したものを変更する方法は存在しない。このため、興味深い可能性は、入札が要求価格よりも高額である場合、入札と要求価格との差を分け合うことへの事前合意を確立することである。両方の側が満足であるはずであり：所有者は進んで売るよりも多額を得て、買い手は自分が進んで支払うよりも少額を支払う。このことは最高相互満足感（ＭＭＨ：Maximum Mutual Happiness）の原理と称され；このことは以下の例で、競売及び株式交換を考える際に再検討する。
【０１４８】
なお、取引決定状況では、範囲比較用のＧＥＬプロセスを用いることもでき、即ち、両方の側が、自分が考えることができる価格範囲を有する場合、ＧＥＬプロセスは、これらの範囲が少しでもオーバーラップするか否かを示す。考慮に値する他の詳細は、ビット増分のプロセスである、というのは、ビット増分はビット・ストリングの長さを決めるからである。増分は１ドル、１０ドル、１００ドル、あるいはより大きい数値であるべきか？明らかに、このことは購入価格に依存する。何千ドルもの購入価格中の１ドルが重要である可能性は低い；百万ドルの取引における１００ドルの増分も同様である。購入価格に合った自然な尺度及び「問題となる」増分が存在する。こうした増分は売り手、買い手が設定するか、あるいは交渉することができるが、大部分は前者による。一般的慣行では、一旦、増分を決定すると上限も決定しなければならず、例えば、増分が１ドルである場合、下限が１ドルであれば最高価格はビット数に等しい。例えば、十分なダイナミックレンジ（大小範囲）を入札プロセスに与えるのに十分なビット数が存在するように、このことを事前に決定することができる。標準的な数は、ビット数及び増分が販売価格についての情報を明かさないように選定することができ、但し非常に大きな範囲内の販売価格を除く。実際的であると思われる代表的なビット・ストリング長は、１００、１２８、２００、２５６、５００、５１２、１０００、及び１０２４である。
【０１４９】
実現の詳細
本明細書中に説明する方法は１つ以上のコンピュータシステム上で実現することが好ましく、こうした実現は当業者の能力の範囲内である。分子の指紋を表現すること、公開、秘密キーの生成、暗号化及び暗号解読演算のような、ビット・ストリング操作用のコンピュータ機能は、当業者のプログラマーが開発することができる。これらの機能は多種多様なプログラミング言語によって実現することができ、これらのプログラミング言語は、一部の場合には、混合実現を含む（即ち、互いに伝達し合うように適切に構成された１つ以上のコンピュータ言語によって書かれた別個な部分に頼る）。例えば、これらの機能、並びにあらゆる必要なスクリプト記述機能は、Ｃ、Ｃ＋＋、Ｊａｖａ（登録商標）、ＪａｖａＳｃｒｉｐｔ（登録商標）、ビジュアルベーシック（VisualBasic：登録商標）、Ｔｃｌ／Ｔｋ（登録商標）、Ｐｙｔｈｏｎ（ピュトン：登録商標）、Ｐｅｒｌ（パール：登録商標）、Ｃ＃のようなネット言語、及びたの等価な言語でプログラムすることができる。こうした技術の能力は、基本機能にアクセスすることの実現または制御に使用する基になる言語によって制限されず、こうした言語に依存しない。その代わりに、こうした機能は、ビット・ストリング及び指紋を操作するための以前に開発された機能に頼るツールキットのような、より高位の機能により実現することができる。
【０１５０】
２つ以上の当事者が別個に独立して、暗号化演算または指紋の操作のような計算を実行する場合、種々の当事者によって操作される種々のコンピュータシステムの能力が、あるいは各当事者がプログラムした方法の正確な細部が互いに同一である必要はないとしても、各当事者は独立して、本明細書中に説明する能力を有するコンピュータシステムにアクセスするものと仮定するべきである。
【０１５１】
本発明における技術は、今日使用されているコンピュータのオペレーティングシステムのいずれで実行されるようにも、並びに本明細書中に挙げていない他のもので実行されるようにも開発することができる。ここれらのオペレーティングシステムは：Ｗｉｎｄｏｗｓ（ウィンドウズ：登録商標）（マイクロソフト社から入手可能なWindows XP、Windows 95、Windows 2000、Windows Vista、Windows 7、Windows 8（Windows 8.1として知られている種々のアップデート、等を含む）、Windows 10を含む）；Ａｐｐｌｅ  ｉＯＳ（登録商標）（iOS3、iOS4、iOS5、iOS6、iOS7、iOS8のような改良版、及びそれらの中間アップデートを含む）；アップル社のＭａｃｉｎｔｏｓｈ（マッキントッシュ：登録商標）オペレーティングシステム、例えばOS9、OS10.x、OS X（”Leopard”、”Snow Leopard”、”Mountain Lion”、”Lion”、”Tiger”、”Panther”、”Jaguar”、”Puma”、”Cheetah”、”Mavericks”、及び”Yosemite”として知られている改良版を含む）；ＵＮＩＸ（ユニックス：登録商標）オペレーティングシステム（例えばBerkeley Standard version（バークレー標準版））及びＩＲＩＸ（登録商標）、ＵＬＴＲＩＸ（登録商標）、及びＡＩＸ（登録商標）のような改良版；及びＬｉｎｕｘ（リナックス：登録商標）オペレーティングシステム（例えば、Red Hat Computing社より入手可能）を含むが、これらに限定されない。
【０１５２】
所定の実現が、順序変更操作を適用する機能、ビット・ストリングのオーバーラップ及びスクランブルを計算する機能、公開キー及び秘密キーを計算する機能、及びデータを暗号化及び暗号解読する機能のような既に実現されている他のソフトウェア・コンポーネントに頼る範囲内で、これらの機能は当業者のプログラマーにとってアクセス可能であるものと仮定することができる。
【０１５３】
さらに、本明細書中に説明する、分子の指紋を匿名化する方法を、適切にプログラムされたコンピュータに実行させる実行可能な命令は、あらゆる適切なコンピュータ可読なフォーマットで記憶して伝達することができることは明らかである。このことは、例えばコンピュータのＵＳＢ（Universal Serial Bus：ユニバーサル・シリアル・バス）ポートに接続することができる大容量の「ハード（ディスク）ドライブ」または「ペン・ドライブ」のような携帯型可読ドライブ（駆動装置）、コンピュータの内蔵ドライブ、及びＣＤ−ＲＯＭまたは光ディスクを含むことができるが、それらに限定されない。さらに、実行可能な命令は、携帯型コンピュータ可読媒体上に記憶し、こうした有形の形態で購入者またはユーザに送り届けることができるが、実行可能な命令は、リモート位置から例えばインターネット接続を通してユーザのコンピュータにダウンロードすることができることは明らかであり、インターネット接続は部分的にＷｉＦｉのような無線技術に頼ることができる。こうした技術の態様は、実行可能な命令が信号または他の無形の具体化の形態をとることを暗に意味しない。実行可能な命令は、「仮想マシン」の実現の一部分として実行することもできる。
【０１５４】
計算装置
本明細書中に説明する方法を実施するのに適した好適な汎用コンピュータ装置（９００）を概略的に図９に示す。こうしたシステムは、本明細書中に説明するように情報を安全に共有したい２つ以上の当事者のうちの１つ以上の当事者のいずれも使用することができる。
【０１５５】
コンピュータシステム（９００）は、少なくとも１つのデータ処理装置（ＣＰＵ：central processing unit）（９２２）、メモリ（９３８）、ユーザ・インタフェース（９２４）、１つ以上のディスク（９３４）、及びネットワーク上で他のコンピュータと通信するための少なくとも１つのネットワーク接続または他の通信インタフェースを具え、上記メモリは、一般に高速なランダムアクセスメモリ並びに（１つ以上の磁気ディスクドライブのような）不揮発性メモリを共に含み、上記ネットワーク接続または通信インタフェースは、インターネット（９６０）、並びに高速ネットワークケーブルまたは無線接続経由のような他の装置を含む。ネットワーク接続（９３６）は、（ビット・ストリングとして符号化されたデータのような）データを一社が他社と共有するために用いることができ、他社は、コンピュータシステム（９９０）と同様な能力を有するコンピュータシステム（９９０）（図示せず）を有し、共有するデータをコンピュータ（９００）から受信することができる。コンピュータ（９００）とインターネット（９６０）との間にはファイアウォール（９５２）が随意的に存在することができる。少なくとも、ＣＰＵ（９２２）、メモリ（９３８）、ユーザ・インタフェース（９２４）、ディスク（９３４）、及びネットワーク・インタフェース（９３６）は、少なくとも１つの通信バス（９３３）を通して互いに通信する。
【０１５６】
メモリ（９３８）は手順及びデータを記憶し、一般に次のものの一部または全部を含む：基本的なシステムサービスを提供するためのオペレーティングシステム（９４０）；パーサー（構文解析）ルーチン（９５０）のような１つ以上のアプリケーション・プログラム、コンパイラ（図９には図示せず）、ファイルシステム（９４２）、分子構造または「指紋」のようなデータを記憶する１つ以上のデータベース（９４４）、及び随意的に、暗号化及び暗号解読演算のような高度な数学演算を実行する浮動小数点コプロセッサを必要な所に含む。本発明の技術の方法は、１つ以上のダイナミックリンクされるライブラリに含まれる機能を利用することもでき、これらのライブラリは図９に図示しないが、メモリ（９３８）にもディスク（９３４）にも記憶することができる。
【０１５７】
図９に、メモリ（９３８）に記憶されているものとして示すデータベース及び他のルーチンは、代わりに、随意的にディスク（９３４）に記憶することができ、データベース内のデータの量は、メモリ（９３８）に効率的に記憶するには大量過ぎる。データベースは、その代わりに、あるいは部分的に１つ以上のリモート・コンピュータ上に記憶することもでき、こうしたリモート・コンピュータは、本明細書中の「例」で説明する方法により、ネットワーク・インタフェース（９３６）を通してコンピュータシステム（９００）と通信することができる。
【０１５８】
メモリ（９３８）には、少なくとも次のことを行うための命令（９４６）が符号化されている：暗号化及び暗号解読演算を実行すること；データベース内に電子的に記憶された分子のビット・ストリング表現のような指紋またはビット・ストリングを操作すること；及び指紋の対（つい）に対して類似性のスコア（得点）またはＸＯＲ演算値を計算すること。これらの命令は、所望に応じて、乱数を発生すること、及びデータベース内に記憶された分子構造の指紋またはビット・ストリング表現を計算すること、のうちの１つ以上を実行するためにプログラムされた命令をさらに含むことができる。多数の具体例では、指紋自体は、暗号化または暗号解読を実行するコンピュータ（９００）上では計算されず、異なるコンピュータ（図示せず）上で計算されて、例えばネットワーク・インタフェース（９３６）を通してコンピュータ（９００）上に転送される。乱数または擬似乱数を発生する場合には、プロセスは、数学的な公式またはプロセスだけに基づかないことが好ましい。乱数、あるいは乱数発生方法の「種」の選定は、使用中のコンピュータ装置内の電位のような現実世界における変動量から得ることが好ましい。
【０１５９】
本明細書中の技術の種々の実現は、特に、複雑性が変化する１つ以上のコンピュータ装置（算術を実行するようにプログラムすることができるマシン）上で実行されるものと考えることができ、これらのコンピュータ装置は、限定なしに、ワークステーション、ＰＣ（personal computer：パーソナル・コンピュータ）、ラップトップ・コンピュータ、ノート型コンピュータ、タブレット、ネットブック（廉価なノート型コンピュータ）、及び他のモバイル（携帯）コンピュータ装置を含み、これらのモバイル・コンピュータ装置は、セルラ電話機、携帯電話機、及びパーソナル・デジタル・アシスタント（個人用形態情報端末）を含む。本明細書中の方法は、さらに、量子コンピュータ上での実行を可能にすることができる。上記コンピュータ装置は、適切に構成されたプロセッサを有することができ、こうしたプロセッサは、限定なしに、本明細書中の方法を実行するソフトウェアを実行するためのグラフィック・プロセッサまたは数値演算コプロセッサを含む。これに加えて、特定の計算機能を２つ以上のコンピュータにわたって分散させ、これにより、例えば、１つのコンピュータが入力及び命令を受け入れ、第２または追加的なコンピュータが、これらの命令をネットワーク接続を通して受信して、リモート位置で処理を実行して、随意的に結果または出力を第１のコンピュータに返送する。従って、本明細書中の方法は、特に、クラウド・コンピュータ環境内で実行可能であり、クラウド・コンピュータ環境では、データが、一時的または恒久的に、データ記憶装置の１つ以上のホスト・アレイ上に安全な方法で記憶され、これにより、データは特定のアカウント保有者にしか見えない。クラウド・コンピュータ環境では、リモート・プロセッサのアレイの処理能力を利用して、クラウド環境内に記憶されたデータに対する操作を実行することもでき、これにより、こうした操作の結果は、特定のアカウント保有者及び／または操作にアクセスする許可を与えた者にしか知られない。
【０１６０】
コンピュータ装置の制御は、ユーザ・インタフェース（９２４）を介することができ、ユーザ・インタフェースは、ディスプレイ、マウス、キーボード、及び／または図９に図示していない他のアイテム、あるいはユーザ・インタフェースの入力装置の任意のサブコンビネーション（副次的組合せ）または組合せを含むことができ、これらの他のアイテムは、例えばトラックパッド、トラックボール、タッチスクリーン、スタイラス（入力ペン）、音声認識装置、ジェスチャー認識技術、人間の指紋読み取り器、または例えばユーザの眼の動きに基づく他の入力装置である。
【０１６１】
一実施形態では、入札をＱＲ（Quick Response）コードで表現して、例えば、携帯電話インタフェース上に表示することができ；こうしたコードは、互いの装置のスクリーンを光学的にスキャンすることによって個人間で往復して交換することができる。このようにして、通信の手段、例えば無線、インターネット、近赤外通信の妥協を回避することができる。
【０１６２】
こうした技術の動作の様式は、１つ以上のソフトウェア・モジュール、関数、またはサブルーチンとしての具体例に単純化すると、分子構造または指紋を記憶しているデータベース上におけるように、バッチモードの形にすることができ、これらの分子構造または指紋は、バッチ処理され、あるいは単一の分子構造または指紋に対する特定の命令をを入力するユーザとの対話によって処理される。
【０１６３】
本明細書中の技術によって行われる類似性の計算、並びに匿名化された指紋自体は、有形の形で、例えば１つ以上のコンピュータ・ディスプレイ上に表示することができ、こうしたディスプレイは、例えばモニタ、ラップトップ・ディスプレイ、あるいはタブレット、ノート型コンピュータ、ネットブック、またはセルラ電話機のスクリーンである。類似性のスコア及び指紋は、さらに、紙面の形に印刷することができ、こうした紙面は電子ファイルとして、コンピュータ可読媒体上に蓄積するためのフォーマットで、またはコンピュータ間で転送または共有するためのフォーマットで記憶され、あるいは、プレゼンテーション（発表）中のように会場のスクリーン上に投影することができる
【０１６４】
特定のデフォルト設定を、コンピュータ実現に対して構築することができるが、ユーザは、望むだけの数の選択肢を、指紋の類似性の計算に置いて用いる特徴に対して与えられることができる。
【０１６５】
例
例１：対象物のリストの比較
メモリ帯域幅の要求
単一のビットを要求される安全性のレベルまで拡張するというＧＭ暗号化の性質は、必要な計算リソースの意味で、（例えば２社間で）分子のリストどうしを比較するためのＡＳＣまたはＡＳＣＵＳ法の実際的応用に大きな影響を与える。次の２つの主要な場合が存在する：まず、単一の分子をリストと比較し（１対多）、次に、２つの分子リストを比較する（多対多）。両方の場合に、単に、２社の代表者間の物理的な会合を設けることによって、ネットワーク帯域幅の必要性を回避することができ、各自がそれぞれの装置上に符号化された集合体を持ってくる。例えば、２社間に高速なギガビット・スイッチを確立することによって、ネットワーク・リソースの必要性をなくすことができる。それにもかかわらず、リモート取引の状況では、次の考察が当てはまる。
【０１６６】
１対多
各指紋が１０００ビットを有し、従って、暗号化したストリングのサイズは必要な安全性のレベルに依存するものとする。今日、商取引では、２５６ビットの暗号化が代表的である。米国国家安全保障局（ＮＳＡ：National Security Agency）はこうしたレベルの暗号化を当たり前に解読することができるものと信じられ、但し、多数の小国の計算能力を超える専用の計算能力による。従って、必要性が生じても２５６ビットで十分であるものと仮定することができ、１０２４ビットのセキュリティは今日の地球上のあらゆるリソースを超えることはほぼ確かである。２５６ビットのセキュリティでは、各分子指紋は３２キロバイト長になる。企業の代表的な集合体は百万個のオーダーの化合物となり得る。従って、こうした集合体は、暗号化されると３２ギガバイトのサイズになる。この値は、今日のハードディスクの容量を前提とすれば、記憶するには手に負えないサイズである。しかし、ＡＳＣ法は、公開指紋及びＸＯＲ指紋の両方の完全な伝送を要求し、このことは、単一の分子と企業の集合体との比較の完全な転送が、こうした量の双方向の伝送を必要とすることを意味する。即ち、３２ギガバイトのサイズのファイルを送信して比較毎に検索する必要がある。非常に高速なインターネット接続をもってしても、（１秒当たり１メガバイトの速度を仮定すれば）このことは１回の転送当たり１２時間のオーダーを要する可能性が高い！この数字を低減する唯一の方法は、セキュリティのレベルを、例えば適度な１２８ビットまで低減するか、あるいは比較する化合物の数を低減するかのいずれかであり、これによりファイルのサイズを２分の１以下に低減することができる。
【０１６７】
後者に対する妥当な方法は、化合物をクラスタ（群）分けすることである。企業の集合体は、完全に異なる化合物を百万個は含まない。これらの化合物を「化学者にとって非常に類似している」ことと等価な類似性の閾値に合わせてクラスタ分けしたならば、恐らくは約２万個のクラスタが存在する。群に分けることの他の利点は、実際の化合物どうしを比較する必要がないことであり：会社は、代表的な化合物とは対照的に、化合物のクラスタの中心を表すビットパターンを選択することができる。このため、実際の指紋は「理想的な」分子を表す。従って、検索は、これらのクラスタに合わせたターゲットの発見した類似性に基づいて改良することができる。レベルが低減された１２８ビット（まだ十分であるものと考えられる）の暗号化は、比較に要する時間が１０分のオーダーになることを意味する。
【０１６８】
多対多
各社が、比較すべき１０，０００個のクラスタの中心を有するものとし、これは合計１億（即ち、１０8）回の比較になり、各社が３２kBのデータの転送を必要とする。これは、往復で送信する必要のある３．２テラバイトのデータになる。今日、このことを行うための最高速の方法は、安全なハード・ドライブ及びＦｅｄＥｘ（登録商標）のような国際宅配便であり、こうした運用にとって妥当な選択肢であり得る、というのは、このことは、何週間または何カ月のタイムスケール（時間的尺度）を有する２社間の事業計画であり得るからである。今日のブロードバンド（広帯域）接続によっても、個別ユーザの１％未満しか１テラバイト以上のデータを所定の月極の支払い請求サイクル中にダウンロードしていない。
【０１６９】
核となる問題はＡＳＣの「往復の」性質にある。一般に（即ち、暗号化の必要性なしに）こうした大規模な比較操作はフィルタをかけることができ、即ち、重要であるものと考えられる分子の類似性しか返送する必要がない。しかし、ＡＳＣでは、２社が「公開」ストリングの発生源を返送されるまでは類似性がどうであるかを知らず、従って、当事者間の完全な類似性行列（マトリクス）の送信を回避する方法は存在しない。（１つの集合からのｍ個の分子と第２の集合からのｎ個の分子との間での、対（つい）毎の類似性の計算は、ｍ×ｎの類似性行列を生成し、その（ｉ，ｊ）要素は分子ｊに対する分子ｉの類似性である。）このため、ＡＳＣまたはＡＳＣＵＳは、大規模な全部対全部（多対多）の比較のための理想的な技術ではない。
【０１７０】
大規模な比較の他の問題：１対多
ＡＳＣＵＳ方式で、帯域幅及び可能なディスク空間に制限がなかったとしても、多数の化合物に対する１つの化合物の類似性を考える際に出される基本的な質問が存在する。例えば、対象の指紋を、各々が１ビットだけ有する一連の指紋と比較することによって、「多数の」指紋の所有者は、「１つの」指紋が含むものを正確に復号化することができ、このことは比較の目的を無効にする。
【０１７１】
「１対多」は、１つの化合物の所有者が、多数の化合物の所有者に返送される暗号化したＸＯＲストリングの順序を再編成することによって、この種の攻撃に対して安全にすることができる。このため、前者が「１ビットの」ストリングを含めていたならば、多数の化合物の所有者は今回自分が参照するビットがわからない。このため、情報の送信は：「多数の化合物中のどの化合物が１つの化合物に類似しているか」から「自分がどの化合物であるかを知らなくても、類似したストリングが存在するか」に移り換わる。このことはまだ価値ある安全な比較である。
【０１７２】
多対多の比較のための追加的保護
１対多の比較が情報を公表し過ぎる危険性を有する（というのは、各回の安全な比較が少なくとも１ビットの情報を伝えるからである）のと同様に、多対多の比較も同じ理由でそうした危険性を有する。取引の一方の当事者は、自分のビット・ストリングのリストを、他の当事者のビット・ストリング中のビットの位置を明らかにするだけのために選定したストリングで「改ざんする」ことができる。しかし、１対多の比較におけるのと同じ方法をとって、こうした危険性を取り除くことができる。基本的に、各当事者は、互いに対して送信する「返信」ビット・ストリングをスクランブルする。
【０１７３】
例えば、アリス及びボブの各々が次の２つのビット・ストリングを有し：Ａ１及びＡ２がアリスに属し、Ｂ１及びＢ２がボブに属するものとする。アリスはＡ１を暗号化形式でボブに送信する。ボブはＡ１とＢ１及びＢ２とのＸＯＲを計算し、これにより、２つの暗号化してスクランブルしたストリングＥＢ１及びＥＢ２を生成して、これらのストリングを返送する順序をランダムにし、この順序変更はアリスに伝えない。即ち、ＥＢ１を最初に、ＥＢ２を２番目に返送することができ、あるいは、ＥＢ２を最初に、ＥＢ１を２番目に返送することができる。次に、アリスは、自分が受信したストリング中のストリング中のビット数を数え上げて、これら２つのビット数を、アリスもランダムな順序でボブに返送する。即ち、ボブは、Ａ１とＢ１とで異なるビット数が、アリスが最初に送信したビット数であるか２番目に送信したビット数であるかがわからないようにする。次に、両者は共に、この手順をアリスのビット・ストリングＡ２に対して繰り返す。この手順の終わりに、各当事者は４つの数を保有し、これらの数は、Ａ１とＢ１とで異なるビット数（＝Ｎ１：１）、Ａ１とＢ２とで異なるビット数（＝Ｎ１：２）、Ａ２とＢ１とで異なるビット数（＝Ｎ２：１）、及びＡ２とＢ２とで異なるビット数（＝Ｎ２：２）である。しかし、アリスもボブもこれらの数ごとの２番目のインデックスは知らない。即ち、いずれの当事者も、（Ｎ１：１）が実際には（Ｎ１：２）であるか否か、あるいは（Ｎ２：１）が現実には（Ｎ２：２）であるか否かは知らない。
【０１７４】
これら４つの数を２×２行列として表現し、アリスのストリングが行列の行を表するとすれば、この行列は「行をスクランブルした」ものとして記述される（各行内の値がスクランブルされている）。ここで、このことは非対称な配列であり：ボブの「インデックス」だけがスクランブルされ、アリスの「インデックス」はスクランブルされていない。この状況に固有の情報は、アリス及びボブは、アリスの集合体中の各化合物と類似した化合物または非類似の化合物がボブの集合体中に存在するか否かは知っているが、それがどの化合物であるかは知らない。
【０１７５】
単純には、この状況を対称にするためにしなければならないことは、プロセスを反復することだけであるように思われるが、今回は、ボブとアリスの役割を交換させることである（ボブがアリスの役割を演じ、アリスがボブの役割を演じる）。従って、このことを行うことは、「列をスクランブルした」行列を返送することであり、即ち、今度は、彼ら二人は共に、ボブの集合体中の所定の化合物と類似した、あるいは非類似の化合物がアリスの集合体中に存在するか否かを知っているが、ここでも、どの化合物であるかは知らないだけである。
【０１７６】
しかし、アリス及びボブが共に、「行をスクランブルした」行列及び「列をスクランブルした」行列の両方のコピーを保有していれば、彼ら二人は正しい行及び列のインデックスを解明することができる可能性があることを、ちょっとした考察が示している。例えば、行をスクランブルした行列及び列をスクランブルした行列が次の通りであるものとする：
行をスクランブルした行列：
（外４）
2018531431.tif 000012
列をスクランブルした行列：
（外５）
2018531431.tif 000013
【０１７７】
「４」のカウント数が、行をスクランブルした行列からのＡ１に関連するので、列をスクランブルした行列についても同じはずであり、即ち、恐らくはスクランブルされている第１列の順序は、Ａ２、次にＡ１であるはずである。このことは、行をスクランブルした行列中の第１行の順序は、Ｂ１にＢ２が続くはずであることを意味する。このプロセスを継続すれば、各行列は次のようにデスクランブルする（スクランブルを元に戻す）ことができる：
行をデスクランブルした行列：
（外６）
2018531431.tif 000014
列をデスクランブルした行列：
（外７）
2018531431.tif 000015
【０１７８】
このため、対称な比較のためには、最終的な交換を回避しなければならず、即ち、アリスは行をスクランブルした自分の行列を決してボブに送信してはならず、ボブは列をスクランブルした自分の行列を決してアリスに送信してはならない。このようにして、各当事者は、各自の集合体中にある既知の化合物と類似しているか非類似の化合物が互いの集合体中に存在するか否かについての情報を有するが、いずれの当事者も、どの化合物どうしが互いに類似しているかは知らない。
【０１７９】
最後に、各側が差分の情報を有する必要性を回避する完全に対称な比較のためのメカニズムが存在する。アリスが暗号化したＡ１及び暗号化したＡ２を共にボブに送信するものとする。次に、ボブは、自分のＢ１及びＢ２を暗号化してＸＯＲをとったストリングを構成して、４つのストリングを自分に与える。しかし、ボブは、Ｂ１及びＢ２をＡ１及びＡ２に適用する順序をランダムにし、即ち、ボブは行及び列をランダムにする。ボブから返送された、これら４つの暗号化したＸＯＲストリングを受信すると、アリスは、各ストリングに対してビットを数える操作を実行するが、アリスが返送するものも行及び列をスクランブルされ、即ち、彼ら二人は共に、行及び列をスクランブルした行列を有する。従って、この行列は、いくつの化合物が類似し、いくつが類似していないかのような、それぞれの集合体についての情報を含むが、彼ら二人のどちらも、自分の化合物のどれに、こうした名称を付けることができるかは知らない。このデータは、集合体間の類似性の分布を表現するに過ぎないが、こうしたデータを知ることはまだ有益であり得る。例えば、アリスのライブラリとボブのライブラリとが互いに同じように見えるか見えないか？同じように見えなければ、恐らくは、より綿密な比較を行って、彼ら二人が化合物を交換したいか否かを確かめて、各自の集合体の多様性を豊富にすることが有益であり得る。
【０１８０】
クラウドベースの多対多の比較
大規模な多対多の比較に関係する問題の１つが、当事者が非常に大きなデータセットを生成することである。例えば、（以上で参照した）各々が１０，０００個の化合物から成る２つの集合体の、対（つい）毎の類似性を暗号化形式で捕捉するために、３．２×１０12バイト（３．２テラバイト）が必要であったとする。これら２つの集合体が、その代わりに、各々が百万個の化合物であったならば、この数は薬品の集合体にとって実情に合わない数とは言えず、上記の数値は記憶装置における３２ペタバイト（３．２×１０16バイト）まで増加する。比較的少数の組織しかこうした記憶装置にアクセスすることができず、こうした量のデータの伝送は、現在のインターネット・インフラストラクチャをもってしても許容外に大きい。
【０１８１】
しかし、近年、ホスト・コンピュータのリソース、いわゆる「クラウド」コンピュータセンターが経済的に実現可能である。複数ペタバイトに及ぶほど莫大な記憶装置の要求でも、レンタル（賃借）で利用可能である。このことは、大規模な多対多の比較に固有の問題を完全には解決しない、というのは、準同形暗号化の古典的概念は、（まだ暗号化形式の）最終的な「結果」ファイルをいずれの当事者にも送信すること、即ち、インターネットのような公共インフラストラクチャを経由したペタバイト級のファイルを送信することを要求するからである。
【０１８２】
しかし、ストリングの全部の対におけるビット・カウント数の差を計算するような何らかの形態の暗号解読がクラウド内で可能であれば、送信の要求は扱いやすくなる。各々が百万個の化合物から成る２つの集合体間の、１０12回のビット・カウント数の比較を送信することは、高速インターネット接続により完全に可能である。多数の大手会社が、こうしたことを１時間くらいで遂行することができるギガビット・スイッチを有する。
【０１８３】
従って、本発明における、第１の当事者と第２の当事者との間で、実際の情報を公表せずに情報を安全に比較する方法は、次のステップを含む：第１の当事者が第１のデータから第１指紋を作成する。第２の当事者は第２のデータから第２指紋を作成する。次に、第１の当事者は、第１組のＧＭキーを、関連する公開キー及び秘密キーと共に生成して、第１指紋をこの公開キーで暗号化して、第１の暗号化した指紋を作成する。次に、第１の当事者は、第１の暗号化した指紋を、自分しか管理できない第１の安全なクラウド・アカウントにアップロードし、次に、公開キーを第２の当事者に送信する。同様に、第２の当事者は、第２指紋を自分の公開キーで暗号化して、第２の暗号化した指紋を作成して、第２の暗号化した指紋を、自分しか管理できない第２の安全なクラウド・アカウントにアップロードする。次に、第１の当事者は、第１のクラウド・アカウント上の第１の暗号化したストリングに対する「読出し」特権を、第２の当事者に与える。（このことは、自分の暗号化したストリングを第２の当事者に送信することと等価である。）第２の当事者は、第１の暗号化した指紋に対してＸＯＲ演算を実行し、これにより、暗号化した指紋ＸＯＲを第２のクラウド・アカウント内に作成する。次に、第２の当事者は、暗号化した指紋ＸＯＲをスクランブルし、これにより、暗号化してスクランブルした指紋ＸＯＲを第２のクラウド・アカウント内に作成する。次に、第２の当事者は、暗号化した指紋ＸＯＲに対する「読出し」特権を第１の当事者に与える。（ここでも、このことは、暗号化してＸＯＲをとりスクランブルした自分のストリングを第１の当事者に送信することと等価である。）第１の当事者は、暗号化してスクランブルした指紋ＸＯＲに対してプログラムを実行して、「オン」状態にされたビット数を評価し、この数を暗号化して第１の当事者のクラウド・アカウント内に記憶し；最後に、第１の当事者は、この暗号化した結果を第１のクラウド・アカウントからダウンロードして、自分のコンピュータ上で暗号解読し、これにより、第１指紋と第２指紋との類似性を知る。
【０１８４】
しかし、この方法の主な欠点は、一方の当事者が、暗号化したストリングのビット数を数えることを可能にするプログラムを、クラウド・リソースにアップロードしなければならないことである。敵意を抱く者がこのプログラムにアクセスできたならば、この者はこのプログラムを用いて、例えば、このプログラムを、いずれかの当事者が現在クラウド上に記憶している集合体を表現する暗号化したストリングの集合体に適用することによって、あらゆる暗号化したストリングを暗号解読することができる。（例えば、こうした当事者は、暗号化したストリングの各ビットを一度に取得し、これらのビットをこうしたプログラムに供給して、１または０のビット・カウント数を戻させることができる。）２つの当事者は、各ストリングをクラウド内に記憶する前に、即ち、あらゆる暗号解読がずっと低価値になるように、各ストリング内のビットのランダムなスクランブルについて合意することによって、このことを防ぐことができる。しかし、このことは、暗号解読方法を有する第三者が、やり取り中の当事者の一方にこの方法を売却することを防止することはできない。この危険性を軽減するための１つの可能な方法は、あらゆるクラウドベースのビット・カウント数の暗号解読の結果自体を暗号化してしまうことである。こうした結果を、暗号解読プログラムの所有者以外の誰も暗号解読することができず、かつ、この結果が元のビット・ストリングよりも小さければ、暗号化したストリングの集合全体を一方の当事者に返送することに関係する問題を軽減することができる。例えば、ストリングが１０２４ビット長であれば、何個のビットがオンにされているかを記述するために１０ビットしか要さず、即ち１００分の１の圧縮率である。本明細書中に説明する同様な暗号化の方法を用いたならば、これを１２８倍または２５６倍に拡張したものがまだ存在するが、こうした拡張を考えても、対（つい）毎の行列全体の送信は、物理的媒体上でも、高速インターネット接続上でも、数日中に可能である。
【０１８５】
ＧＭ法を用いて、共通のビット数を暗号化することは、大部分のコンピュータ・リソースにとってまだ挑戦的である、というのは、ＧＭ法はこうした大きなビット数を用いるからである。例えば、１２８ビットのセキュリティを用いている場合には、１０ビットの数を記憶するために１０＊１２８ビットを要し、あるいは、２５６ビットのセキュリティについては１０＊２５６ビットである。より単純な方法は、例えば１００ビットのランダムなビット・ストリングを生成し、次に、このストリングの最初の１０ビットを、「共通のビット」のカウント数を表す１０ビットになるようにセットする。次に、これらの１００ビットは、あらゆる方式、例えばＲＣＡを用いて暗号化して記憶することができる。必要なことは、暗号化方法が、同じビット・カウント数に対して毎回同じ「メッセージ」を生成しないことであり、さもなければ、このプログラムにアクセスできる敵対者（例えば、クラウド・リソースの所有者）は、暗号化したメッセージがどのようであるかを、オン状態にされたビットのないストリング、１ビットがオン状態にされたストリング、２ビットがオン状態にされたストリング、等について単に確かめ、次に、こうしたメッセージの集合を、このプログラムが任意のストリングに対して生成したあらゆるものと単に比較することができる。「オン状態にされたビットのない」ストリングに対して、２**90個（＝１０**27個）の可能なメッセージが存在する場合、敵対者は、これらのメッセージのほんの一部分さえも補足する見込みがない。このレベルの比較、即ち、ビット・カウント数当たり１００ビットによれば、対の比較のＮ＊Ｎ行列の全体は１０**14ビットであり、即ち、〜１０テラバイトである。こうした量のデータを送信するための配送コストは今日でも妥当である。
【０１８６】
例２：活性プロフィールの比較
例１では、化学構造の集合を比較し、指紋中の各ビットは分子構造の特徴を表す。指紋によって表されるものを拡張することによって、分子の対の他の性質どうしを比較することができる。例えば、１つの拡張は、指紋中のビットが分析試料における活性を表現することである。活性が二者択一の特性（例えば、活性／不活性）であれば、この拡張は単純であり：活性の指紋は、単に「１」を指紋中の「活性」用に予約された位置に置き、そうでない位置に「０」を置く。その代わりに、活性を帯域または範囲の形に定量化する場合、このことは指紋を拡張することによって行うことができる。例えば、特定の分析試料中の活性物質は、次の８つの、対数単位の範囲に定量化することができる：
｛＜１nM｝、｛１nM＜１０nM｝、｛１０nM＜１００nM｝、｛１００nM＜１μM｝、｛１μM＜１０μM｝、｛１０μM＜１００μM｝、｛１００μM＜１mM｝、｛＞１mM｝。
【０１８７】
ある化合物が５０nMの活性物質を有するものとし、即ち３番目のカテゴリーに入る。このことは次の短いビット・ストリングとして表すことができ、ビット・ストリング中の各位置は上記８つの範囲のうちの１つに対応する：
（外８）
2018531431.tif 000016
この場合、最初の３つのビットは「１」にセットされる。このビット・ストリングを、２mMの活性物質を有する他の化合物のビット・ストリングと対比すれば、この化合物は次のビット・ストリングを有する：
（外９）
2018531431.tif 000017
（これらのビット・ストリングの両方において、ある範囲のビットが、２つのストリングが互いに同じカテゴリーを表すか否かの単純な判定ではなく、これらのストリング間の実際の差を得ることができるようにセットされている。）従って、これらのストリング間のＬ１距離は５になり、この活性物質についての２つの分子間のカテゴリー番号の差を表している。分子毎に２つの、測定される活性物質が存在する場合、例えば、考慮する第１の分子が：第１のキナーゼに対して５０nＭ、第２のキナーゼに対して５μMであれば、このことは、２つのこうしたビット・ストリングをこのように連結することによって表現することができる（付加したストリングは下線付きのビットで示している）：
（外１０）
2018531431.tif 000018
【０１８８】
第２の化合物が、第２のキナーゼに対する５nMの活性物質を有すれば、その合成ストリングは次のようになる（ここでも、付加したストリングは下線付きのビットを有する）：
（外１１）
2018531431.tif 000019
【０１８９】
これらのストリング間のＬ１は５＋３＝８である。従って、ＡＳＣまたはＡＳＣＵＳは、活性カテゴリーの差Ｌ１の平均値、即ち４を示す。両方の側が、一方のキナーゼに対する活性が非常にある化合物を有することを知っているので、両方の側が、他方の側が異なるキナーゼに対する活性を有する化合物を有するものと仮定することができる。差の平均値が非常に小さかったならば、両方の側が、両方のキナーゼのキナーゼ・プロフィールどうしが相当類似しているものと仮定している。
【０１９０】
活性プロフィールを比較するこうした概念は、任意の多数の分析試料の結果に拡張することができる。その有用性は一般に次のいずれかを見出すことである：(A)同様な化学的性質を有するが、異なる活性プロフィールを有する化合物（化学的Ｌ１は低いが活性のＬ１は高い）、あるいは(B)化学的には非常に異なるが非常に類似した活性プロフィールを有する化合物（化学的Ｌ１は高いが活性のＬ１は低い）。
【０１９１】
当然、性質はカテゴリーの意味で必要に応じて細かく表現することができる。性質をまとめてグループ化して、グループ単位の活性の類似性を与えることができる。例えば、恐らくは、あるキナーゼ・スクリーンが存在するが、ＧＰＣＲ（G-protein-coupled recepton：Ｇタンパク質受容体）用のスクリーンも存在する。従って、各々が別個の指標的な差Ｌ１を与える。
【０１９２】
２つの性質間の実際の差の尺度を与える上記のようなビット表現を用いることの代案として、ＧＥＬ指紋プロセスを用いて、単一の性質がより高い、より低い、または同じであるかを、カテゴリー毎に（あるいは、所定のカテゴリーについて）判定することもできる。例えば、２つの化合物を化学的に比較する必要があるが、一方の化合物の溶解度が他方の化合物の溶解度よりも高いか否かを確認する必要があるものとする。上記の指紋は差の度合いしか与えず、この差の向き（より大きいかより小さいか）は与えない。しかし、上記のＧＥＬ形式は、後者を可能にする。それだけでも、化学的指紋と同時にも用いられ、２人の研究者が、２つの化合物が類似しているが一方がより良好な溶解度を有することを確認することができる。創薬における化合物の第一線の最適化では、多数の性質を同時に最適化することが重要であり、化合物の合成の大部分は性質を改善することを中心に展開され、即ち、性質を変更する方向に展開される。
【０１９３】
例えば、２社が同様な分子に取り組んでいるが、異なる物理的性質が欠如している状況にある、ということがあり、恐らくは、一方の側では溶解度が低過ぎ、他方の側では代謝クリアランスが高過ぎる。ＧＥＬフォーマットを化学的類似性Ｌ１と共に用いて、２つの側が自分達の化学的情報を共有して、個別の不具合に対してどのような責任があるかを両社が知ることができるか否か、即ち、こうした状況が存在することを両社が知っていれば、両社が自社の化合物を改良する可能性を有するか否かを確かめることができる。そして、ここでも、このことは実際の化合物または実際の物理的性質を公表せずに行うことができる。
【０１９４】
最後に、考慮してきた２つのストリング間の測定基準は「市街距離」またはＬ１距離である。しかし、２つの、数値のリストまたは数値のベクトルを比較する場合、Ｌ２距離を求めることがより有用であり、Ｌ２距離は距離の二乗の総和である。
【０１９５】
以上に述べたように、リストまたはベクトルにおけるエントリ（各入力値）が１または０であれば、Ｌ１とＬ２との間に差は存在しない（１＊１＝１、０＊０＝０である）。しかし、上記のように表現される活性物質のリストが、順序付きのカテゴリであるものと考えるとすれば、どの測定基準を計算するべきであるかの選定が存在する。このことを確かめるために、上記の例を考え、ここでは２つの性質が次のように表現される：
（外１２）
2018531431.tif 000020
及び
（外１３）
2018531431.tif 000021
【０１９６】
ＡＳＣ／ＡＳＣＵＳプロセスは次のようなＸＯＲベクトルを生成する：
（外１４）
2018531431.tif 000022
次に、これを次のようにスクランブルすることができる：
（外１５）
2018531431.tif 000023
これは、Ｌ１＝８、即ち８ビットがセットされていることを示している。
【０１９７】
しかし、その代わりに、ストリングをそのサブベクトルの範囲内でスクランブルするものとし、即ち、次のようにスクランブルする：
（外１６）
2018531431.tif 000024
ここで、読者は、５及び３のＬ１距離がストリング中に埋め込まれていることを知るが、これらのＬ１距離がどの性質を参照しているかは知らない。さらに、個別の距離が与えられれば、Ｌ２距離（二乗）は５＊５＋３＊３＝３４として計算することができる。従って、ＡＳＣ／ＡＳＣＵＳ法は、性質のベクトル間のＬ２距離も可能にし、ここで各性質の差はビット・ストリングとして表されるが、性質の順序は失われている。明らかに、このプロセスは、性質の数が大きい場合に最良に機能する。
【０１９８】
例３：共有モデル
２社が、自社の化合物を公表せずに、共同予測モデルを作成することに向けて協力することができるか否かの課題は、実際に簡単であり、ＡＳＣ法を何ら必要としない。一般に、こうした予測モデルはデータセットを出しあうことによって作成されるが、各分子は、そのモデルにおいて使用される一組の性質に、予測が必要な数量を加えたものによってしか表現されない。従って、ＱＳＡＲのような標準的な方法を適用して、その数量向けの（一般に高度にパラメータ化された）モデルを考え出す。
【０１９９】
しかし、一組の性質ではなく、ある特性空間内での分子間の類似性に由来する第２のクラスのモデルが存在する。例えば、指紋の差がこうしたクラスを形成する。指紋中の各ビットは、（一部のＱＳＡＲモデルに含めるための）異なる性質として扱われず、むしろ、その距離を全体論的な対（つい）毎の性質として解釈する。例えば、ｋＮＮ法（「ｋ」人の最寄りの隣人）が、ｋ人の隣人の性質を平均することによって、新たな化合物についての予測を作成する。これらのモデルは共有することがより困難である、というのは、新たな分子までの距離を計算しなければならないからである。例えば、Ａ社が自社の新たな分子についての予測を欲しい場合、Ａ社はその分子をＢ社に開示して、Ｂ社の集合体中の、構造及び／または性質がＡ社の新たな化合物に近いあらゆる分子から予測するための入力を受信しなければならない。また、例えばクリギング（Kriging）法における加重距離方式では、今までのすべての分子間の距離（即ち、Ａ社のすべての化合物とＢ社のすべての化合物との間の距離）を必要とする。しかし、もちろん、こうした状況は、ＡＳＣＵＳ法にとって理想的であり、即ち、分子の２つの集合間の類似性を計算する。このため、分子構造を示さずに２つ以上の会社のリソースを使用する単一モデルが実際的である。
【０２００】
この手順を図７Ａ及び７Ｂに示す。開始点は指紋の種々の集合であり、図７Ａ中に（７０３）、（７０５）、（７０７）、（７０９）、（７１１）で表す。これらの集合は互いに同じサイズである必要はなく、図面中では異なるサイズの平行四辺形で表される。図７Ａの上部のパネル中に示すように、ＡＳＣＵＳ法（７０１）を用いて、指紋の種々の集合を対（つい）毎に比較することができる。最初のステップは、各寄与者が自分達の化合物間の類似性（７１５）の行列を生成する（７１３）ことを含む。これらの化合物は、全体的な類似性行列の中心部を形成する。第２部分は、ＡＳＣＵＳを用いてこの行列の非対角要素を形成することであり、即ち、各社の化合物の、互いの集合との類似性をセットする。図示するように、寄与分は同等である必要はない。計算した量が、ＡＳＣＵＳのＬ１距離におけるような差であり得るとしも、「類似性」行列のことを話すことは通常のことである。各寄与者は、この行列の１つの行、即ち自社の化合物の各他社との類似性、及びすべての他社どうしの化合物の類似性にアクセスすることができる。次に、これらの行を寄与者間で共有し、これにより各社が行列全体を有して終了するものと仮定する。次に、新たな化合物を予測する必要がある場合、この化合物から各社の化合物までの距離のベクトルを計算する必要がある。予測を行うためには、完成したベクトル（７１２）が必要であり、このことは、指紋の集合（７０９）について図７Ｂに例示するように、他社の集合の各々に対してＡＳＣ／ＡＳＣＵＳを用いることに比べれば、各社が部分的に寄与しなければならない。この第２ステップでは、提出した会社だけがベクトル全体を有し、従って、提出した会社を越えて予測を知らせる必要がある理由は存在しない。このため、対称なプロセス（ＡＣＳ）は、類似性のベクトルを生成するために適用するのに適した方法である。
【０２０１】
次に、類似性のベクトルを類似性の行列と共に用いて、関心のある性質を予測する。なお、この行列は、クリギングのような方法にしか役に立たず、こうした方法は、距離と性質の分散との相関を考慮に入れる。ｋＮＮのような方法は、類似性のベクトルを計算することしか必要とせず、即ち、必要なものは上記第２ステップだけである。
【０２０２】
例４：形状比較
これまでは、ＡＳＣ／ＡＳＣＵＳプロセスの用途は、活性物質のリスト、あるいは化学的パターンまたは性質を表す指紋のような物理的性質に限定されていた。しかし、この方法は、分子の三次元形状の比較にも適応させることができる。分子の配座（立体構造）の配向を考えると、規則的な間隔をおいた点の格子を分子構造上に重ね合わせることができ、各点は１（分子の内部）または０（分子の外部）の値を与えられる。ここで、こうした１または０の格子は１及び０のベクトルに変化させることができる。
【０２０３】
例えば、格子が｛ｘ＝−１０Å，ｘ＝１０Å｝、｛ｙ＝−１０Å，ｙ＝１０Å｝、｛ｚ＝−１０Å，ｚ＝１０Å｝の範囲内に広がるものとし、格子点は１Åの間隔をおいて直線をなすものとする。このことは、２１＊２１＊２１＝９２６１個の点が格子上に存在することを意味する。まず、直線｛ｙ＝−１０Å，ｚ＝−１０Å｝に沿ったｘ＝−１０Åからｘ＝＋１０Åまでの２１個の値をとり、次に、｛ｙ＝−９Å，ｚ＝−１０Å｝に沿った２１個の値をとり、等によって、この格子からベクトルを形成することができる。ここで、このように格子をベクトルにする順序付けは、所定配向の２つの形状を表す２つのベクトルを比較することができることを意味する。これに加えて、格子をｘ軸及びｙ軸の周りに１８０度回転させることによって、他の３つの配向を比較することができる。これらの回転は、指紋内のビットの順序を変更することに相当し、即ち、形状を新たな格子にマッピング（対応付け）する必要なしに、４つの異なる配向を比較することができる。もちろん、格子に対するこうした代わりの配向及び変換を構成して比較することもでき、例えば「正準（カノニカル）な」配向の集合は、分子の慣性モーメントをデカルト軸に合わせて整列させることができるが、他の配向も考えることができる。
【０２０４】
なお、最後に、形状の比較を分子構造の例によって説明してきたが、形状は完全に一般的な概念であり、分子だけに限定されない。
【０２０５】
考えることができる一対の拡張は、各格子点において１でも０でもない値を用いること、及び他の三次元的性質を比較することである。第１の拡張は、各格子点を単一のビットとして表現するのではなく、一組のビットを各格子点に与えることができ、即ち、上述したように、活性のような性質の比較を考える際である。ここで、こうした格子から生成されたベクトルを拡張し：例えば、上記の例では、各格子点に８ビットを与えてその点におけるいくつかの性質を表現する場合、生成されるビット・ベクトルは８＊２１＊２１＊２１ビットのサイズになる。次に、２つの形状間のＸＯＲが２１＊２１＊２１個のサブベクトルを生成し（各々が８ビット長）、これらのサブベクトルは上述したようにスクランブルすることができる。このようにスクランブルしたストリングの読者は、各点における形状値の差は知るが、その値がどの点を参照するかは知らない。しかし、ここでも、上述したように、読者はＬ２距離を計算することができる。こうした手順を用いる例は、電界どうしを比較することであり得る。即ち、各点における電位をビット・パターンに変換し、これにより、２つのこうしたパターン間のＸＯＲは、その点における電位差を近似する。
【０２０６】
これら２つの方法では、形状の値のアレイまたは形状のビットのアレイどうしを組み合わせることができ：例えば、２つの分子形状間のＬ１距離を、それらの電界間のＬ１またはＬ２距離と同時に計算することができる。薬物のような分子上に一般に見られる水素結合供給体及び水素結合受容体のような官能基の種類までの空間距離のような他の分野も、こうした方法で比較することができる。
【０２０７】
化学的指紋の比較を越える
安全な比較の原理の特徴は、情報交換を期待される方法に限定することを可能にすることである。化学的類似性以外の人間に関する事柄でも、本明細書中に説明する方法を有効にすることができる例が存在する。そのいくつかは以上に例として参照または説明しており、例えば、給与を比較すること、あるいは入札価格と販売価格とが近いか否かを判定することである。以下の例は他のいくつかの例示を提供する。
【０２０８】
例５：特徴の集合の比較：スポーツチーム間での選手のトレード
選手をトレードすることに関心のある２つのスポーツチームを考える。これらのチームは、進んで手放そうとする選手のリストを互いに対して提示することしかできない。しかし、こうした情報は公にしにくい。スター選手は、自分がトレードを考えられていることを見出して非常に不満になり得る。チームどうしの会合が機密であっても、一旦、リストが交換されると、その情報は漏れることがあるし、恐らくは漏れる。一方、リストを比較することは、良好なトレードを行うことができる場合に真価を有する。チーム１が自チームの選手のリストをアルファベット順に作成して、引き留めたい各選手の直後に０を付けるが、トレードを考えている各選手の直後には１を付けるものとする。チーム２は、チーム１の選手のリストと同様なリストを作成し、関心のない選手毎に０を付け、トレードし得る選手毎に１を付けるものとする。ベクトルはこのようになる：
チーム１：チーム１が売却し得る４人の選手：
（外１７）
2018531431.tif 000025
チーム２：をチーム２が買収を考えている５人の選手：
（外１８）
2018531431.tif 000026
【０２０９】
これら２つのストリング間の距離は、各チームがＡＳＣＵＳを介して見出すことができ、Ｌ１＝５である。しかし、いずれのチームも、他の１つの情報：即ち、他のチームのストリング中の「１」がセットされたビット数なしには、いくつの一致が存在するかを正確に分かることはできない。この数を、チーム１についてはＮ、チーム２についてはＭと称する。従って、一致の数は次式の通りである：
【数６】
2018531431.tif 000027
このことは、単に、ビット間の一致のすべてが（Ｍ＋Ｎ）なる最大のＬ１から２を取り去ることに起因する。従って、上記の例では、Ｎ＝４、Ｍ＝５、Ｌ１＝５であり、従って２つの一致があるはずであり、これらの一致はリスト中の位置３及び位置９に存在する。この時点で、これらのチームは自チームのリストを互いに示し合うことを考えることができる。まだいくらかの危険性が存在する、というのは、そのスター選手はチーム１のリスト上に存在し得るが、チーム２のリストに対する当たりではなかった。しかし、この危険性は減少させることができる、というのは、これらのチームはある程度の共通の見地を有するからである。
【０２１０】
こうした交換の変形例は考慮するに値する。各チームが共通のビット数、即ち一致の個数を計算するためには、Ｎ及びＭを知る必要がある：このことはＸＯＲ演算の性質に起因し、ＸＯＲ演算は、共通のビット数ではなくビット・ストリング間の相違の個数を特定する。２つのチームが、それぞれのチームがいくつのビットを「１」にセットしているかを認めたくないものとする。驚くべきことに、それでも進展を遂げることができる。上記の例では、各チームがＸＯＲをとってスクランブルしたストリングを返送するものとし、このストリングは受信したストリングの２倍の大きさであり、ここに、追加されたビットは、全部１のストリングを、公開された、即ち受信したストリングに対してＸＯＲをとることに由来する。即ち、チーム２は次のストリングを計算する：
（外１９）
2018531431.tif 000028
【０２１１】
このストリングは、到着したストリング中のビットがセットされた箇所にしか０を有さず、即ち、セットされたビットの総数は｛Ｂ−Ｎ｝であり、ここにＢはビットの総数であり、ここでは１６に等しい。ここで、チーム２は、このストリングを、自チームのストリングと受信したストリングとのＸＯＲ（をとったストリング）に付加して、これら２つのストリングを一緒にスクランブルしてチーム１に返送する。ここで、チーム１によって報告されたＬ１(拡張)は次式の通りである：
Ｌ１(拡張)＝(Ｂ−Ｎ)＋Ｌ１    (34)
【０２１２】
この式より、一致の個数は次式のようになる：
【数７】
2018531431.tif 000029
即ち、チーム２は、この式の右辺の各要素を知っているので、ここで、いくつのビットがセットされているかをチーム１が公表することなしに、チーム２は一致の個数を知る。しかし、ＡＳＣＵＳを用いていれば、こうした難読化は継続しない。即ち、各チームが一致の個数を知っていれば、これらのチームは、自チームが報告したＬ１(拡張)に戻って、いくつのビットを他のチームがセットしているかを計算することができる。このための式は単に次式の通りである：
Ｍ＝Ｌ１(拡張)＋２＊一致−Ｂ    (36)
【０２１３】
例６：インターネット・ベースの一致実行
情報交換に含めることができる他の１つの人間の感情は困惑である。インターネットの重要な発明の１つは、Match.com、Tinder、他のようなオンライン・デート・サイトである。こうしたサイトは一般に互いの関心、例えばスポーツ、キャンプ、特定種類の音楽が好きか、に基づいて人どうしを仲介しようと試みる。しかし、人どうしを頻繁に結び付けるものは、共有することを戸惑い得るものであり：例えば、どの低俗映画を自分達が好きであるか！である。参加者が１００本の映画のリストを与えられ、これらの映画は「罪深き愉しみ（guilty pleasure）」であるものと考えられ、即ち、自分は好きかも知れないが、自分が好きであることを他人に知って欲しいかは自信がないと考えられる場合を想像する。一例は、”Terms of Endearment”のような過度の感傷主義、あるいは”Harold and Kumar”のような子供向けのユーモアであり得る。このことは、例５において自分達の名簿を比較する２つのスポーツチームについて説明した問題とちょうど同じ問題であり、いくつの映画を選択したかを各側に知らせることに加えて、Ｌ１は、いくつのこうした「罪深き愉しみ」を２人の人が共に楽しめるかを、この人達が見出すことを可能にする。大きなオーバーラップが存在する場合、これら２人の人が互いの交わりを楽しむ確率は高くなり得るし、ＡＳＣＵＳにより、参加者がどの映画を選択するかを開示せずに、このことを行うことができる。このことは効果的であるだけでなく、サービス・プロバイダがすべてを知ってしまうというオンライン仲介サイトの問題を回避する。
【０２１４】
より巧妙な例として、内気な少年の集団と内気な少女の他の集団とのパーティ用の招待客名簿を作成することを考える。どの少年も、他の集団の誰かに興味があるか否かについて、他の少年、及び間違いなく少女の誰に対しても認めたくはなく；少女にも逆のことが当てはまる。各側は、自分達自身の公開ＧＭキー及び秘密ＧＭキーを導出して、公開キーを交換する。次に、各少年は１と０のベクトルを作成し、１と０は、アルファベット順に並べた、興味のある少女及び興味のない少女に、それぞれ対応する。彼らは、これらのベクトルを互いに共有しない、というのは、各少年は、他者のベクトルを暗号解読してその所有者をからかうことができるからである。むしろ、彼らは自分のベクトルを暗号化して少女に送信し、少女がこのビット・ストリングを暗号解読することができないことは知っている。他のすべての少年が、同じ順序に作成した、例えば少女の名前をアルファベット順にしたこうしたストリングを送信しており、少女は、各ストリングから自分に関係する１ビットを抽出する。例えば、Abigailがアルファベット順のリスト上の２番目の少女であれば、彼女は、各少年のリスト中の２番目にあるすべての暗号化したビットのリストを作成して、各少年からの興味に対応する暗号化したストリングを、ここでも、多分アルファベット順に形成する。次に、各少女は、各少年に対する自分の興味または興味のなさに対応する自分自身のストリングを、その少年の公開キーを用いて作成し、このストリングと上記抽出したストリングとのＸＯＲをとってスクランブルする。
【０２１５】
名簿を比較するスポーツチームの例と同様に、興味のアイテムは共通するビット数であり、このビット数は（興味の）一致の可能性が存在するか否かを暗に意味する。しかし、上記のように、ＸＯＲプロセスは相違、即ち、一方の側が異なる意見を有することについてしか伝えない。共通するビット数は、各側でいくつのビットがセットされているかを知っている場合にしか抽出することができない。しかし、このことは困難なことであり：どの少年も自分に興味がないことは、どの少女も知りたくはなく、その逆も同様である。同様に、少女は、少年のうちの誰も実際に自分に興味がない（あるいは、全員が！実際に自分に興味がある）ことを少年が知ることに当惑し得る。従って、このことは、上述した拡張されたＬ１が最適な解決策であることの例である。上記のように、少女が拡張されたストリングを少年に返送すれば、少年が計算した（拡張された）Ｌ１は、彼女に興味があるとして少年がセットした個数、あるいは彼女が興味があるとして少年に対してセットした個数を少年には知らせず、これらの数量の差に関係する数値のみを知らせる。自分がいくつのビットをセットしたかを知る少女のみが、（興味の）一致の個数を知るが；彼女は、何人の少年が彼女に会いたいかは知らない。逆に、少年は、自分達のうちの何人が彼女を好んでいるか、あるいは自分達のうちの何人が彼女に好かれているかは知らない。（興味の）一致が存在しない場合、少女は落胆するかもしれないが、このことは、彼女を好んだ少年が、彼女が好む少年ではなかったという永遠の真理であり：人生とはそのようなものである！
【０２１６】
このようにして、各少年（及び各少女）は、「好み」の一致がいくつ存在するかを、次のことについての情報なしに見出す：(a)他の集団のうちの何人が自分を好むか；(b)同じ集団のうちの何人が、特定の少女（または少年）を好んだかについてのあらゆること；(c)他方の集団中のどの特定のメンバーが自分を好んだか。
【０２１７】
こうした特定の方式を（Ｎ(Ｎ−１)／２回の対（つい）毎の比較により）Ｎ個の集合に拡張して、これら３つの原理を維持しつつ、集合中の各アイテムと、他のあらゆる集合中のあらゆるアイテムとの間に何らかの一致の可能性が存在するか否かを判定することができる。
【０２１８】
例７：入札システム
例えば、取引を行うことができるか否かを判定するに当たり、自分の数値が他者の数値よりも高いか、他者の数値に等しいか、他者の数値よりも低いかをいずれかの当事者が判定することができるシステムは、（例えば、図２及び３Ａ〜３Ｈに関して）既に説明してきた。例えば競売（オークション）のように、２つ以上の当事者が、異なる当事者が保持するアイテムに入札したい際に、同じシステムを用いることができる。このことが奏功することができる方法を確かめるために、２つの当事者だけが入札していることを想像する。入札は、比較することになる数値を表現する。ＡＳＣＵＳ法を適用した後に、各当事者は、自分の入札が他者の入札よりも高いか低いかを知る。次に、この入札を第三者である売り手に転送し、売り手は、前述したようにこの入札が十分に高いか否かを判定することができる。ここで、売り手の「最低限受け入れ可能な価格」を通常「最低競売価格」と称する。
【０２１９】
この手順について注記するべきいくつかの事項は次の通りである：
ｉ．すべての入札が公開されて入手可能であり、但し暗号化形式である。（入札を公開し、但し暗号化されているとは、これらの入札を後に変更することはできないが、これらの入札を（その所有者が）暗号化するだけでよいことを意味し、暗号化はこのプロセスにとって必要である。）
ｉｉ．「入札」の提出は、この入札が中に入っている「ロッボックス」に相当する。即ち、販売の決定時に、落札者（だけ）に秘密キーを公表し、落札できなかった当事者は、誰の入札が実際により高額であるかの判定の正確さをチェックすることができる。従って、確立されたルールが存在すれば、ＡＳＣＵＳにおける対称性を強制しようとする必要性は存在しない。
ｉｉｉ．落札できなかった入札を公開する（暗号解読する）必要はない。
ｉｖ．落札が最低競売価格に達しない場合、その入札を公開する必要はない。
ｖ．（ｉｖ）の場合、例えば、一方の入札者が他方の入札者をだまして、実際にはそうでなくても自分がより高額の入札者であるものと思い込ませるような場合でも、対称性を強いる必要がある可能性がまだ存在する。このことは、受け入れ可能な入札を落札者が有していない際に、落札できなかった入札者が、実際には受け入れ可能な入札を有するか否かを販売者にチェックさせることによって容易に見つけることができる。落札できなかった入札者が実際には受け入れ可能な入札を有する場合、落札者は嘘をついている。落札できなかった入札者が実際には受け入れ可能な入札を有さない場合、落札者が嘘を付いているか否かは無関係であり：誰もその競売で落札していない。
【０２２０】
このプロセスは、複数当事者の入札システムに拡張することができる。本発明における中心概念は、「整数（入札）Ａが整数（入札）Ｂよりも大きいか」という概念を、整数のリストをソートすることに拡張し、これにより、最終的に、（同等な入札の場合を除いて）リスト中の皆が他者の入札を知ることなしに自分の入札のランクを知る。このことが機能することができる方法を図８Ａ〜８Ｇに示して以下に説明する。入札を順序付けするためのプロセスは、単に、各当事者が自分の入札を他のすべての入札と比較して、いくつの入札が、自分の入札よりも高額であるか、自分の入札に等しいか、自分の入札よりも低額であるかの経過を追う、というだけである。このプロセスの終了時に、各入札者は自分のランク（同順位があれば同順位を含む）を知る。次に、最高額の入札者は、最低競売価格をチェックすることができる。この方式では、落札の公開を用いてセキュリティ（安全性）を保証し、即ち、各参加者は順序付けの有効性をチェックすることができる。
【０２２１】
この順序付けを実現することができる方法については変形例が存在する。順序付けが完全でなくても、単一アイテムの競売において必要なことは、最高額の入札者が存在することだけである。このことは最大（Ｎ−１）回のＡＳＣＵＳ比較しか必要とせず、ここにＮは入札者の数であり、入札のリストの順序付けを確立するための(Ｎ−１)＊(Ｎ−１)回とは対照的である。同様に、アイテム対アイテムの比較のみに依存するソート・アルゴリズムは、Ｎ＊Ｎ回ではなくＮlogＮ回のオーダーの比較を必要とするように書くことができる。このことは、ネットワーク・トラフィックを（暗号化した公開入札ストリングの往復のために、Ｎ＊Ｎ回からＮlogＮ回に）低減する入札の完全なソートを行うことができることを意味する。
【０２２２】
図８Ａ〜８Ｇに示すステップは次の通りである：
(1) 入札を指紋として用意する（８００）。（図８Ａ）；
(2) ＧＭキーを生成し（８０２）、このＧＭキーより、公開キー（８０４）を導出することができ、公開キーを用いて指紋（８０６）を暗号化して、暗号化したビット・ストリング（８０８）を作成する。（図８Ａ）；
(3) ＲＳＡキーを生成し（８１０）、このＲＳＡキーからＲＳＡ公開キー（８１２）を導出することができ、ＲＳＡ公開キーを用いて入札（８１４）を暗号化して、暗号化した入札（８１６）を作成する。（図８Ａ）；
(4) ＧＭ公開キー（８０４）、暗号化した指紋（８０８）、及び入札ファイル（８１６）の集合（８３１）を登録所（８２８）に送信する。このことは、他のすべての入札者（８３０）についても行うことができる。（図８Ｂ）；
(5) 公開キー及び暗号化したファイルのすべての集合（８３１）、（８３３）、（８３５）、（８３７）を、登録所（８２８）（または他の入札者）から読み出す（。図８Ｂ）；
(6) すべての公開キー及び暗号化したファイルを読み出すと、入札をＧＥＬ指紋（８４０）として用意する。（図８Ｃ）；
(7) 図示するように、３つの異なる入札者「Ｋ」、「Ｔ」、及び「Ｐ」について、ＧＥＬ指紋（８４０）を、読み出した各公開キー（８０４）、（８０５）、（８０７）で暗号化し、これにより暗号化したＧＥＬ指紋（８４３）、（８４６）、（８４９）を作成する。（なお、全員の入札を各自のキーで暗号化する。）（図８Ｃ）；
(8) 暗号化したＧＥＬ指紋の各々と、同じキーで暗号化されている読み出した指紋とのＸＯＲをとって（８５２）、暗号化してＸＯＲをとった指紋（８５３）を生成する。この指紋をスクランブルして（８５４）、暗号化してＸＯＲをとってスクランブルした指紋（８５５）を生成する。（図８Ｄは、暗号化したＧＥＬ指紋（８４３）及び暗号化されている読み出した指紋（８０８）の例を示す。）；
(9) すべての、暗号化してＸＯＲをとりスクランブルした指紋（８５５）、（８５７）、（８５９）を、登録所（８２８）（または他の入札者（図示せず））に返送する。（図８Ｄ）；
(10) すべての、暗号化してＸＯＲをとりスクランブルした指紋（８５５）、（８５７）、（８５９）、（８６１）を登録所（８２８）（または他の入札者）から読み出し、これらの指紋は自分の公開キーで符号化されている。（図８Ｅ；５つの指紋を示す）；
(11) ＸＯＲをとってスクランブルした指紋（８５５）、（８５７）、（８５９）、（８６１）の各々を、自分のＧＭ秘密キー（８７１）で暗号解読し（８７２）、これにより、それぞれの指紋毎のＧＥＬ番号（８７４）、（８７６）、（８７８）、（８８０）を生成する。（図８Ｅ；４つの指紋を示す）；
(12) すべてのＧＥＬ番号からの｛Ｇ，Ｅ，Ｌ｝の三つ組を形成し、最初はＧ＝Ｅ＝Ｌ＝０にセットする。自分の入札を他の全員の入札と比較する；今度は、どんな価格であるかを見出す必要がある。入札（８２２）中の入札の数をＧＥＬ番号（８８３）と比較する：入札がＧＥＬを超える場合、カウンタＧを１だけ進める；入札がＧＥＬに等しい場合、カウンタＥを１だけ進める；入札がＧＥＬよりも低い場合、カウンタＬを１だけ進める。Ｇ＝０である場合（自分が最高額の入札者である）、(13)に進んでキーを公表する。（図８Ｆ）；
入札のランクは（１＋Ｌ，Ｅ＋Ｌ+１）で与えられる。例えば、Ｇ＝９、Ｅ＝２、Ｌ＝０、ランク＝（１，３）は、１番目から３番目までが最高額の入札で同順位である（自分の入札と他の２者の入札とが最高位の入札で横並びすることを意味し；自分と他の２者は同順位であり、自分は１、２、及び３位を占める；
(13) 最高額の入札者用のＲＳＡ公開キー（８８８）を登録所（８２８）に送信する；
(14) （１，１）にランク付けされた（即ち、明らかに最高位にランク付けされた）場合、入札の秘密キーを登録所に送信する（８９４）ことによって公表する；このことは、１つの入札が最高額であることのチェックである。登録所（８２８）は公開にすることができる。（ボックス（８９４）は、最高額の入札を有することを主張する人物に対する申し立てである；このボックスは、最高額の入札者であることを主張する人物に対する申し立てのように、何かうまくいかないことがあった場合のみに必要になる。）
【０２２３】
最後に、入札の治安（図８には図示せず）及び誤りの報告が存在し得る：例えば、公表された落札者よりも高額の入札を申請したことを誰かが主張した場合、自分の秘密キーを公表することによってそのことを証明することができ；誤りがなかった場合には、その申し立てをされた最高額の入札者が落札するが；誤りが検証された場合には、最高額にランク付けされた入札を破棄し、次に最高額の入札でステップ(14)を繰り返す、等を、入札が全員によって検証されるまで、即ち、誰もより高額の入札を提出したことを主張しなくなるまで行うことができる。（このことによって例示する基本的思想は、入札者が自分の入札をランク付けすることができるか否かである。上記リストは、入札の値を知ることなしに順序付けすることができる：というのは、この方法は、対をどのように比較するかを示し、従って、対（つい）毎の比較を用いてリストをソートすることができる。）
【０２２４】
例８：最高相互満足感（ＭＭＨ）証券取引
例７で説明した安全な競売は、非常に新規な方法での証券の買い付け及び売り付けに拡張することができる。現在、株式は、一方の側が価格をリストに挙げ、他方の側がその価格に応じたいか否かを決定することによって、売却または取り引きされる。しかし、このことは先発者利益の古典的な例であり、即ち、買い手は売り手が期待することを知っており、その価格よりも多額を支払おうとはしない。売り手は常に自分がリストに挙げた価格を得ることしかできず、売り手にとっての「利点」は存在せず、買い手にとっての利点しか存在しない。さらに、売却は一対一のベースでは行われず：一般に中間ブローカー（仲介業者、仲買人）を必要とする。その結果、「鞘取り」の機会が存在し、即ち、買い手が進んで支払う金額と買い手が進んで受け入れる金額との間に差が存在することをブローカーが知っている場合、ブローカーは売り手から買い付けて買い手に売却して、その差を着服することができ、このことが「首位独走」の本質であり、超高速取引から得られる利益における強い特徴であり、小規模な投資家はより大規模な運用者に対して不利であることを意味する。この例では、株式取引のこれらの問題となる状況をすべて取り除くシステムの例を説明する。
【０２２５】
単一の売り手
証券の売り手が１０００株を売却する場合を考える。売り手は自分の売値を取引での暗号化した売り注文として（即ち、ＡＳＣＵＳストリングとして）自分の公開キーと共に記録し、こうして自分の価格用のロックボックスを確立し、即ち、この売り注文は売り手の命令により暗号解読することができるが変更することはできない。入札の増分及びビット・ストリング中のビット数は、売り手が規定するか一般的な協約によって規定することができる。
【０２２６】
次に、取引での一連の入札を登録すると共に、並びに買い手が取得することに関心のある価格の株数を登録する。
【０２２７】
図７において上述した入札のＡＳＣＵＳ順序付けがこれに続く。
【０２２８】
本明細書中の他所に説明するように、通常のＡＳＣＵＳプロセスによって、最高額の入札を、暗号化した売値と比較する。最高額の入札が売値以上であれば、契約によって売り付けが保証される。買い手は、その入札に対する自分の秘密キーを公表し（買い手は１つ以上の秘密キーを作成しておくことができる）；売り手は自分の秘密キーを公表する。買い手が１０００株よりも多く買い付けたい場合、この注文の一部しか叶えられずに競売を終了する。買い手が１０００株よりも少なく買い付けたい場合、売り手の注文の一部しか叶えられない。買い手が支払う価格は、売り手の価格と入札との平均値である（ＭＭＨ原理）。残りの株式が存在する場合、これらの株式は次に最高額の入札者に渡され、この入札者の入札をＡＳＣＵＳによって売値と比較する。入札が売値よりも高額である（または売値に等しい）場合、かつ、その入札者が残りの株式の量よりも大量の注文を登録している場合には、競売を終了する。２番目の入札者が支払う価格は、自分の入札と売値との平均値である。このプロセスは、(a)売り手の株式の全部が売却されること、あるいは(b)売値以上の入札を有するすべての買い手が自分の注文を叶えること、のいずれかが先に発生するまで継続する。これらの条件のいずれかが満たされると、すべての売り付けが公開され、登録された入札に基づく申し立てが行われる。申し立てがなければ、競売は終了したものと考える。
【０２２９】
入札は最高額から最低額まで進むので、同額の入札が存在する場合、この入札は、単に、残りの株式から各入札者に同数の株式をその価格で与えることによって処理され、売り残しはランダムな抽選によって割り当てられる。例えば、上位２つの入札の各々が６００株を欲しい場合、各々が、売りに出された１０００株から５００株ずつ取得する。一方の入札が１０株で他方の入札が２０００株である場合、第１の入札者は１０株を取得し第２の入札者は９９０株を取得する。各々が３３３株よりも多数の３つの同等な入札が存在する場合、各入札者は３３３株を取得し、残りの株式はランダムな抽選によって買い手のうちの１人に行く。
【０２３０】
ここで発生することを分析することは発展的である。第１に、各買い手は自分の入札未満（または以下）を支払い、売り手は自分の売値よりも高額（または売値以上）を得る。第２に、価格差の利益を得る仲介者は存在せず：こうした利益はすべて買い手及び売り手に同等に行く。取引は、一般的な競売におけるように、標準的な売り上げの取り分によって、あるいは「満足感」、即ち、買値と売値との差の取り分を得るより進んだプロセスによって金を稼ぐことができ、本質的に、鞘取りの割合を取り除きつつ、大部分は参加者に行く。第３に、大規模または小規模であること、あるいは高速または低速であることの利点は存在しない。すべての入札を考慮し、参加者にとって最大の満足感を生み出す順序で叶える。
【０２３１】
複数の売り手
売り出しに複数の売値が存在し、各々が複数の株式割り当てを伴う場合、このことは同様に対処することができる。唯一の相違は、これらの売値も、まず、ＡＳＣＵＳの順序付けを施されることである。その後は、最低の売値については競売を通常通りに進める。この順序を完了すると、プロセスは次に低い売値にに進む、等である。どの売値よりも高額な買いの入札が存在しない際に、またはすべての売り注文が叶えられた際に、あるいは全ての買い注文が完了した際に、競売を終了する。もちろん、売り手が単数及び複数の取引の両方について、その後に未売却株の売り競売が存在し得る。
【０２３２】
複数の売り手が存在する際には、価格増分及びビット数（売上範囲）を誰が設定するかの疑問が存在する。このことは、各売り手が増分及び範囲を要求して、取引は、最小の増分と最大の範囲との組合せを用い、あるいは取引設定「方針」による。このことは数値の比較でもあるので、このことをＡＳＣＵＳによって実現することもでき、即ち、完全に分散された取引を望む場合、最小のステップサイズ（増分）は、ＡＳＣＵＳを用いてすべての売り手が提案する最小の増分を見出すことによって、そして同様に最大の範囲を見出すことによって決定することができ、両者のための増分は一般的な指針によって決定される。
【０２３３】
例９：モバイル機器上で実現される価格交渉
価格交渉は、２つ（以上）の当事者が、何らかの形の補償（通常は金銭）と引き換えに商品またはサービスを交換することに関心があり、本明細書中の他所に説明する方法により実現することができ、但しモバイル技術の基盤に基づく。通常、交渉に入るに際し、各当事者は一般に、それを超えたら交渉を進めない数値を念頭に置き、本明細書では取引の「中止」数と称する。このプロセスでは、こうした「中止」数を秘密にして厳重に保護し、その結果、決して「先に進まない」取引交渉では多大な労力が無駄になる、というのは、当事者の「中止」数は成功する取引とは両立しないからである。（「ノゴシエーション（nogotiation）」と非公式に称する）これらの状況では、一刻も早く立ち去ることが両当事者の関心事である。
【０２３４】
この例は、すべての当事者の「中止」の制約を前提とし、自分の制約を他のあらゆる当事者に公表することなしに、２つ（以上）の当事者が、取引の可能性があり得るか否かを判定することを可能にする方法を説明する。ＡＳＣＵＳ技術を用いれば、すべての当事者が自分の制約を暗号化様式で指定することができ、これにより、買い手の最高価格が売り手の最低価格を超えているか否かを判定することができる。
【０２３５】
実際問題として、このプロセスは、妥当な量の計算資源を、取引における当事者毎に必要とする。こうした理由で、次のモデルが適用可能である：
【０２３６】
ピア・ツー・ピアの直接交渉
このモデルでは、各当事者が、直接または無線のネットワーク能力によりコンピュータ装置（セルラ電話機、モバイル機器、タブレット、ラップトップ（コンピュータ）、ＰＣ（personal computer：パーソナルコンピュータ）、等）にアクセスすることができる。各装置には、交渉アプリケーション（「ＮＡ」；Negotiation Application）または交渉サービスがインストールされている。ＮＡは、起動されると、利用可能なネットワークのうちの１つ以上に発見可能なように現れると共に、これらのネットワーク上で発見可能なＮＡの他の例を検索する。
【０２３７】
一方の当事者がＮＡを通して所望の相手を識別することができ、次に、この開始する当事者（「開始者」）が、ＮＡを通して招待状を相手（「受信者」）に送信するものと仮定する。受信者がこの招待状を受け取れば、取引プロセスを開始することができる。
【０２３８】
その代わりに、ＮＡは発見不能な様式で動作することができ、この場合、開始者は、（電子メールまたはテキスト・メッセージのような）他の手段を通して招待状を所望の相手に送信することができる。招待状は、適切なネットワークを介してこのＮＡに接続するために必要な情報を受信者に提供する。受信者がこの招待を受け入れて、ある種の相互接続ネットワークを介して自分のＮＡを開始者のＮＡに接続して、交渉プロセスを開始することができるものと仮定する。
【０２３９】
サポートされるネットワーク能力に応じて、このプロセスを直接に、あるいはリモートで行うことができる。両方の場合において、各当事者は自分の装置にアクセスして、最低レベルのセキュリティ（安全性）を保証することができる。
【０２４０】
一旦、２つのＮＡ間の交渉を開始すると、この交渉は次のプロセスを用いる：
【０２４１】
この時点で、「開始者」は、自分がどのような種類の取引（買い、売り、バーター（物々交換）、等）に関心があるか、及び取引の最小単位（「ＭＵＥ：minimum unit of exchange」）をどうするかを示す。ＭＵＥは、取引の通貨、及び「中止」の値をどれほど木目細かくするかを定める（例えば、+/-百万ドルに対して+/-１ドル）。
【０２４２】
各当事者は自分の「中止」数を自分のＮＡに入力する。
【０２４３】
ＡＳＣＵＳ技術を用いれば、これらのＮＡは自分の「中止」数を暗号化して、取引が可能であるか否かを判定することができる。
【０２４４】
一旦、各装置上での計算を完了すると、「続行」または「中止」の答えを両当事者に提出し、この時点で、両当事者は、立ち去るか、あるいは妥協点に達することのできる実際の交渉を誠意をもって開始するかを選定することができる。
【０２４５】
約束のあるピア・ツー・ピアの直接交渉
上述した第１のモデルは、（その成果にかかわらず）交渉にかかわることを望む２つ（以上）の当事者に大きな価値をもたらすことができる。しかし、最初の交渉プロセスが、取引が可能であることを示すものと仮定しても、標準的な交渉戦術がまだ必要である。１つの修正は、各当事者が互いに最適な価格設定（ＭＯＰ：Mutually Optimal Pricing）を実現することを保証しつつ、これらの取引を簡略化して促進するためのモデルである。互いに最適な価格設定は、元の「中止」数を開示し、次に差を２者間で分け合うことによって実現される。このことは、買い手及び売り手が共に、交渉の終わりに受け入れたであろう価格よりも良い価格を実現し、その結果を迅速に、かつ対立的な交渉戦術の感情的影響なしに実現することを保証する。
【０２４６】
このプロセスを効果的にするためには、各当事者が、最初の交渉を実行する前に、これらの条件下で取引を完了することを約束する必要がある。この約束は、他の当事者との適法契約の完了を要求することによって、ＮＡを通して得ることができる。このことは、デジタル署名または法的に容認された他の結合手段を用いて実現することができる。取引のあり得る規模次第では、ＮＡは個人向け電子銀行取引（例えばＰａｙＰａｌ（ペイパル：登録商標）、Ｇｏｏｇｌｅ  Ｗａｌｌｅｔ（グーグル・ウォレット：登録商標））情報の提供を同時に求めて、交渉の完了時に資金を直接移動することができることを保証することができる。直接の資金移動が可能でない場合、ＮＡは、適切な購入注文／納品書・請求書（インボイス）を必要に応じて当事者に提供することができる。
【０２４７】
この取引のブローカーのように、ＮＡは取引の料金を徴収することができ、この料金は均一料金、取引総額の一定割合、または２つの「中止」数間の差の一定割合であり、こうして、取引の料金が２つの当事者のためのＭＯＰの実現に悪影響を与えないことを保証する。この料金は、ＮＡの実現に応じた種々の手段によりＮＡ内で徴収することができ、ＮＡの実現は、直接的なクレジットカード課金、ＥＦＴ（electronic fund transfer：電子決済、電子資金移動）、ＰａｙＰａｌ（登録商標）、または他のデジタル手段、ｉＴｕｎｅｓ（登録商標）によるアプリケーション内課金、Ｇｏｏｇｌｅ  Ｐｌａｙ（グーグルプレイ：登録商標）、Ａｍａｚｏｎ  Ｍａｒｋｅｔｐｌａｃｅ（アマゾン・マーケットプレイス：登録商標）、等を含む。
【０２４８】
ＭＯＰはあらゆる個別の取引にとって理論的に最適であるが、売り手の最低価格を頻繁に変更することができず、販売の完了による最低価格の開示が商売に損害を与え得る商品を販売する大企業（例えば、自動車の販売業者）にとっては最適でないことがある。こうした状況では、ＮＡは、プロセス中に実際の価格をユーザに示すことを防ぎ、最終的な取引価格だけを報告するためのステップを踏むことができる。もちろん、ＭＯＰに到達するための機能を知っていれば、元の「中止」価格はその機能から決定することができる。このことを最終的に回避するために、ＮＡはその代わりに、価格の単純なランダム選択から、大きく変化する料率に及び、追加的かつより巧妙な方法に至る広範な手段を用いて、互いに有益な価格（ＭＢＰ：Mutually Beneficial Price）を選択することができ、ＭＢＰは「中止」価格間にあるが、必ずしもこれらの価格の中間値ではない。
【０２４９】
本明細書中に引用したすべての参考文献は、その全文を参照することによって本明細書に含める。
【０２５０】
以上の説明は、本発明の技術の種々の態様を例示することを意図している。本明細書中に提示する例は、添付した特許請求の範囲を限定することは意図していない。本発明はここで十分に説明されており、添付した特許請求の範囲の精神及び範囲から逸脱することなしに、多数の変更及び修正を本発明に加えることができることは、通常の当業者にとって明らかである。さらに、添付した特許請求の範囲は、本明細書中に説明した種々の実施形態のいくつかを代表すること、及び、そのように説明しているが添付した請求項のうちの１つには表現していないあらゆる実施形態は、同時に発生する優先権の喪失なしに、本願の優先権を主張する応用の形で、請求項の形に表現することができることも明らかである。
【図１】
2018531431.tif 000030
【図２Ａ】
2018531431.tif 000031
【図２Ｂ】
2018531431.tif 000032
【図３−１】
2018531431.tif 000033
【図３−２】
2018531431.tif 000034
【図３−３】
2018531431.tif 000035
【図３−４】
2018531431.tif 000036
【図４Ａ】
2018531431.tif 000037
【図４Ｂ】
2018531431.tif 000038
【図４Ｃ】
2018531431.tif 000039
【図５Ａ】
2018531431.tif 000040
【図５Ｂ】
2018531431.tif 000041
【図５Ｃ】
2018531431.tif 000042
【図６Ａ】
2018531431.tif 000043
【図６Ｂ】
2018531431.tif 000044
【図７Ａ】
2018531431.tif 000045
【図７Ｂ】
2018531431.tif 000046
【図８Ａ】
2018531431.tif 000047
【図８Ｂ】
2018531431.tif 000048
【図８Ｃ】
2018531431.tif 000049
【図８Ｄ】
2018531431.tif 000050
【図８Ｅ】
2018531431.tif 000051
【図８Ｆ】
2018531431.tif 000052
【図８Ｇ】
2018531431.tif 000053
【図９】
2018531431.tif 000054
【手続補正書】
【提出日】平成30年6月27日(2018.6.27)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
第１の当事者と第２の当事者とが安全に入札を交換する方法であって、
前記第１の当事者が第１の入札を生成するステップと、
前記第１の当事者が、第１組の公開キー及び第１組の秘密キーを生成するステップと、
前記第１の当事者が、前記第１の入札を前記第１組の公開キーで暗号化し、これにより第１の暗号化した入札を生成するステップと、
前記第２の当事者が第２の入札を生成するステップと、
前記第２の当事者が、第２組の公開キー及び第２組の秘密キーを生成するステップと、
前記第２の当事者が、前記第２の入札を前記第２組の公開キーで暗号化し、これにより第２の暗号化した入札を生成するステップと、
前記第１の当事者が、前記第１の暗号化した入札及び前記第１組の公開キーを、前記第２の当事者に送信するステップと、
前記第２の当事者が、前記第２の暗号化した入札及び前記第２組の公開キーを、前記第１の当事者に送信するステップと、
前記第１の当事者が、前記第１組の秘密キーを前記第２の当事者に送信するステップと、
前記第２の当事者が、前記第２組の秘密キーを前記第１の当事者に送信するステップと、
前記第１の当事者が、前記第２の暗号化した入札を、前記第２組の秘密キーで暗号解読し、これにより前記第２の入札を明示するステップと、
前記第２の当事者が、前記第１の暗号化した入札を、前記第１組の秘密キーで暗号解読し、これにより前記第１の入札を明示するステップと
を含む方法。
【請求項２】
前記第１の当事者が、前記第１の公開キー及び前記第１の秘密キーを生成するステップが、素因数分解、離散対数問題、及びＲＳＡ暗号化、のうちの１つに基づくアルゴリズムを用いる、請求項１に記載の方法。
【請求項３】
請求項１に記載の方法を実行するように構成されたコンピュータ装置。
【請求項４】
第１の当事者と第２の当事者との間で、実際情報を公表せずに情報を安全に比較する方法であって、
前記第１の当事者が、第１のデータから第１指紋を作成するステップと、
前記第２の当事者が、第２のデータから第２指紋を作成するステップと、
前記第１の当事者が、第１組のＧＭキーを、関連する公開キー及び秘密キーと共に生成するステップと、
前記第１の当事者が、前記第１指紋を前記公開キーで暗号化して、第１の暗号化した指紋を作成するステップと、
前記第１の当事者が、前記公開キーを前記第２の当事者に送信するステップと、
前記第２の当事者が、前記第２指紋を前記公開キーで暗号化して、第２の暗号化した指紋を作成するステップと、
前記第１の当事者が、前記第１の暗号化した指紋を前記第２の当事者に送信するステップと、
前記第２の当事者が、前記第１の暗号化した指紋及び前記第２の暗号化した指紋に対してＸＯＲ演算を実行し、これにより暗号化した指紋ＸＯＲを作成するステップと、
前記第２の当事者が、前記暗号化した指紋ＸＯＲをスクランブルし、これにより、暗号化してスクランブルした指紋ＸＯＲを作成するステップと、
前記第２の当事者が、前記暗号化してスクランブルした指紋ＸＯＲを、前記第１の当事者に送信するステップと、
前記第１の当事者が、前記暗号化したスクランブルした指紋ＸＯＲを暗号解読して、スクランブルされた前記暗号化した指紋ＸＯＲ中のビット数を数え、これにより、前記第１指紋と前記第２指紋との類似性のレベルを知るステップと
を含む方法。
【請求項５】
第１の当事者と第２の当事者との間で、実際情報を公表せずに情報を安全に比較する方法であって、
前記第１の当事者が、第１のデータから第１指紋を作成するステップと、
前記第２の当事者が、第２のデータから第２指紋を作成するステップと、
前記第１の当事者が、第１組のＧＭキーを、関連する公開キー及び秘密キーと共に生成するステップと、
前記第１の当事者が、前記第１指紋を前記公開キーで暗号化して第１の暗号化した指紋を作成し、該第１の暗号化した指紋を、第１の安全なクラウド・アカウントにアップロードするステップと、
前記第２の当事者が、前記第２指紋を前記公開キーで暗号化して第２の暗号化した指紋を作成し、該第２の暗号化した指紋を、第２の安全なクラウド・アカウントにアップロードするステップと、
次に、前記第１の当事者が、前記第１のクラウド・アカウント上の前記第１の暗号化した指紋に対する読出し特権を、前記第２の当事者に与えるステップと、
前記第２の当事者が、前記第１の暗号化した指紋及び前記第２の暗号化した指紋に対してＸＯＲ演算を実行し、これにより、暗号化した指紋ＸＯＲを前記第２のクラウド・アカウント内に作成するステップと、
前記第２の当事者が、前記暗号化した指紋ＸＯＲをスクランブルし、これにより、暗号化してスクランブルした指紋ＸＯＲを前記第２のクラウド・アカウント内に作成するステップと、
前記第２の当事者が、前記暗号化してスクランブルした指紋ＸＯＲに対する読出し特権を、前記第１の当事者に与えるステップと、
前記第１の当事者が、前記暗号化してスクランブルした指紋ＸＯＲに対してプログラムを実行して、オン状態にされたビットの数を評価して、前記ビットの数を暗号化して前記第１のクラウド・アカウント内に記憶するステップと、
前記第１の当事者が、前記暗号化したビットの数を、前記第１のクラウド・アカウントからダウンロードし、該第１の当事者のコンピュータ上で暗号解読し、これにより前記第１指紋と前記第２指紋との類似性を知るステップと
を含む方法。
【請求項６】
第１の当事者と第２の当事者との間で、実際情報を公表せずに情報を安全に比較する方法であって、
前記第１の当事者が、第１のデータから第１指紋を作成するステップと、
前記第２の当事者が、第２のデータから第２指紋を作成するステップと、
前記第１の当事者が、第１組のＧＭキーを、関連する公開キー及び秘密キーと共に生成するステップと、
前記第１の当事者が、前記第１指紋を前記公開キーで暗号化して、第１の暗号化した指紋を作成するステップと、
前記第１の当事者が、前記公開キーを前記第２の当事者に送信するステップと、
前記第２の当事者が、前記第２指紋を前記公開キーで暗号化して、第２の暗号化した指紋を作成するステップと、
前記第１の当事者が、前記第１の暗号化した指紋を前記第２の当事者に送信するステップと、
前記第２の当事者が、前記第１の暗号化した指紋及び前記第２の暗号化した指紋に対してＸＯＲ演算を実行し、これにより、暗号化した指紋ＸＯＲを作成するステップと、
前記第２の当事者が、前記暗号化した指紋ＸＯＲをスクランブルし、これにより、暗号化してスクランブルした指紋ＸＯＲを作成するステップと、
前記第２の当事者が、第２組のＥＳＡキーを、関連する第２組の公開キー及び第２組の秘密キーと共に生成するステップと、
次に、前記第２の当事者が、前記暗号化してスクランブルした指紋ＸＯＲを、前記第２組の公開キーで暗号化して、二重に暗号化してスクランブルした指紋ＸＯＲを作成するステップと、
前記第２の当事者が、前記二重に暗号化してスクランブルした指紋ＸＯＲを、前記第１の当事者に送信するステップと、
前記第２の当事者が、前記第２組の秘密キーを前記第１の当事者に送信するステップと、
前記第１の当事者が、前記二重に暗号化してスクランブルした指紋ＸＯＲを、前記第２組の秘密キーで暗号解読し、前記暗号化してスクランブルした指紋ＸＯＲ中のビットの数を数え、これにより前記第１指紋と前記第２指紋との類似性を知るステップと
を含む方法。
【請求項７】
第１の当事者と第２の当事者との間で、実際情報を公表せずに情報を安全に比較する方法であって、
前記第１の当事者と前記第２の当事者とが、それぞれの第１指紋と第２指紋とを互いに交換するステップと、
前記第１の当事者が、請求項４に記載の方法を用いて、前記第１指紋と前記第２指紋との第１ＸＯＲ値を計算するステップと、
前記第２の当事者が、請求項４に記載の方法を用いて、前記第１指紋と前記第２指紋との第２ＸＯＲ値を計算するステップと、
前記第１の当事者が第１組のＲＳＡキーを生成するステップと、
前記第２の当事者が第２組のＲＳＡキーを生成するステップと、
前記第１の当事者が、前記第１ＸＯＲ値を暗号化し、これにより第１の暗号化したＸＯＲ値を作成するステップと、
前記第２の当事者が、前記第２ＸＯＲ値を暗号化し、これにより第２の暗号化したＸＯＲ値を作成するステップと、
前記第１の当事者が、前記第１の暗号化したＸＯＲ値を前記第２の当事者に送信するステップと、
前記第２の当事者が、前記第２の暗号化したＸＯＲ値を前記第１の当事者に送信するステップと、
前記第１の当事者が、第１組の秘密キーを用いて前記第２の暗号化したＸＯＲ値を暗号解読し、これにより前記第２ＸＯＲ値のコピーを明示するステップと、
前記第２の当事者が、第２組の秘密キーを用いて前記第１の暗号化したＸＯＲ値を暗号解読し、これにより前記第１ＸＯＲ値のコピーを明示するステップと、
前記第１の当事者が、前記第２ＸＯＲ値のコピーが、元の前記第２ＸＯＲ値と同じであるか否かをチェックして確かめるステップと、
前記第２の当事者が、前記第１ＸＯＲ値のコピーが、元の前記第１ＸＯＲ値と同じであるか否かをチェックして確かめるステップと
を含む方法。
【請求項８】
第１の当事者と第２の当事者との間で、実際情報を公表せずに情報を安全に比較する方法であって、
前記第１の当事者が、第１組のＲＳＡキー、及び第１ランダム・ビット・パディング及び第２ランダム・ビット・パディングを生成するステップと、
前記第２の当事者が、第２組のＲＳＡキー、及び第３ランダム・ビット・パディング及び第４ランダム・ビット・パディングを生成するステップと、
前記第１の当事者が、前記第１ランダム・ビット・パディング及び前記第２ランダム・ビット・パディングを暗号化し、これにより第１の暗号化したランダム・ビット・パディング及び第２の暗号化したランダム・ビット・パディングを作成するステップと、
前記第２の当事者が、前記第３ランダム・ビット・パディング及び前記第４ランダム・ビット・パディングを暗号化し、これにより第３の暗号化したランダム・ビット・パディング及び第４の暗号化したランダム・ビット・パディングを作成するステップと、
前記第１の当事者が、前記第１の暗号化したランダム・ビット・パディング及び前記第２の暗号化したランダム・ビット・パディングを、前記第２の当事者に送信するステップと、
前記第２の当事者が、前記第３の暗号化したランダム・ビット・パディング及び前記第４の暗号化したランダム・ビット・パディングを、前記第１の当事者に送信するステップと、
前記第１の当事者が、第１指紋を前記第１ランダム・ビット・パディングと併合し、該第１指紋を前記第２ランダム・ビット・パディングと併合して、２つの第１パディング付き指紋のそれぞれを作成するステップと、
前記第２の当事者が、第２指紋を前記第３ランダム・ビット・パディングと併合し、該第２指紋を前記第４ランダム・ビット・パディングと併合して、２つの第２パディング付き指紋のそれぞれを作成するステップと、
前記第１の当事者が、請求項４に記載の方法を用いて、前記２つの第１パディング付き指紋の一方と、前記２つの第２パディング付き指紋の一方との第１ＸＯＲ値を計算するステップと、
前記第２の当事者が、請求項４に記載の方法を用いて、前記２つの第１パディング付き指紋の他方と、前記２つの第２パディング付き指紋の他方との第２ＸＯＲ値を計算するステップと、
前記第１の当事者と前記第２の当事者とが、それぞれの秘密キーの組を交換するステップと、
前記第１の当事者が、前記第２の当事者の秘密キーの組を用いて、前記第３の暗号化したランダム・ビット・パディング及び前記第４の暗号化したランダム・ビット・パディングを暗号解読するステップと、
前記第２の当事者が、前記第１の当事者の秘密キーの組を用いて、前記第１の暗号化したランダム・ビット・パディング及び前記第２の暗号化したランダム・ビット・パディングを暗号解読するステップと、
前記第１の当事者及び前記第２の当事者が共に、前記第１ランダム・ビット・パディング及び前記第２ランダム・ビット・パディングと、前記第３ランダム・ビット・パディング及び前記第４ランダム・ビット・パディングとの新たなＸＯＲ値を計算するステップと、
前記第１の当事者が、前記新たなＸＯＲ値が、元の前記第１ＸＯＲ値及び元の前記第２ＸＯＲ値と同じであるか否かをチェックして確認するステップと、
前記第２の当事者が、前記新たなＸＯＲ値が、元の前記第１ＸＯＲ値及び元の前記第２ＸＯＲ値と同じであるか否かをチェックして確認するステップと
を含む方法。
【請求項９】
前記情報が、デジタル符号化した１つ以上の分子構造を含む、請求項４〜８のいずれかに記載の方法。
【請求項１０】
前記第１指紋及び前記第２指紋の各々が、分析試料中の分子の活性を表す１つ以上のビットを含む、請求項４〜８のいずれかに記載の方法。
【請求項１１】
前記第１指紋及び前記第２指紋の各々が、分子の三次元形状を表す１つ以上のビットを含む、請求項４〜８のいずれかに記載の方法。
【請求項１２】
前記第１の当事者及び前記第２の当事者がハンドヘルド機器を使用中である、請求項１、２、４〜８のいずれかに記載の方法。
【請求項１３】
指紋をスクランブルすることが、ランダム・ビット・パディングを導入することを含む、請求項４〜６のいずれかに記載の方法。
【国際調査報告】
2018531431.tif 000055
2018531431.tif 000056
2018531431.tif 000057
2018531431.tif 000058