追跡不能な支払いのための不視署名

追跡不能な支払いのための不視署名	Blind signatures for untraceable payments
序論	Introduction
顧客が利用できる様々な電子銀行業務の成長に見られるように、商品や役務に対する代金支払い方法の自動化が既に進行中である。新しい電子決済方式の根本的な構造は、私事権および電子決済の犯罪使用の内容と範囲に対して実質的な影響を持っているかもしれない。新しい電子決済方式は、理想的にはこのような一見して相反する懸念の両方に対処すべきである。	Automation of the way we pay for goods and services is already underway, as can be seen by the variety and growth of electronic banking services available to customers. The ultimate structure of the new electronic payments system may have a substantial impact on personal privacy as well as on the nature and extent of criminal use of payments. Ideally a new payments system should address both of these seemingly conflicting sets of concerns.
一方、個人によって実行されたあらゆる取引に対する支払いの受取人、金額および時間の情報は、個人の所在、交友関係および生活様式に関して第三者に非常に多くのことを明らかにする可能性がある。たとえば、交通機関、旅館、食堂、映画館、劇場、講演会、食物、医薬品、酒類、書籍、雑誌などに対する支払いや会費、宗教的もしくは政治的な寄付金などの支払いのことを考えよ。	On the other hand, knowledge by a third party of the payee, amount, and time of payment for every transaction made by an individual can reveal a great deal about the individual’s whereabouts, associations and lifestyle. For example, consider payments for such things as transportation, hotels, restaurants, movies, theater, lectures, food, pharmaceuticals, alcohol, books, periodicals, dues, religious and political contributions.
一方、紙幣や硬貨のような匿名決済の方式は管理手段や安全保障が欠如しているという弱点がある。たとえば、決済証明の欠如、決済媒体の盗難、賄賂のための不正な決済、脱税および闇市場などの問題のことを考えよ。	On the other hand, an anonymous payments systems like bank notes and coins suffers from lack of controls and security. For example, consider problems such as lack of proof of payment, theft of payments media, and black payments for bribes, tax evasion, and black markets.
本論文では、下記の性質を有する自動化された決済方式を実現可能にする根本的に新しい種類の暗号学的手法（cryptography）を提案する。         1 第三者は個人によって実行された支払いの受取人、時間および金額を断定することができない。         2 個人は決済証明を提供することができ、また、特別な状況下では受取人の正体を突き止めることができる。         3 盗難に遭ったという報告を受けた決済媒体の使用を停止することができる。	A fundamentally new kind of cryptography is proposed here, which allows an automated payments system with the following properties:         (1) Inability of third parties to determine payee, time or amount of payments made by an individual.         (2) Ability of individuals to provide proof of payment, or to determine the identity of the payee under exceptional circumstances.         (3) Ability to stop use of payments media reported stolen.
不視署名の暗号系	Blind signature cryptosystems
新しい種類の暗号学的手法は、最初に類推を使って導入し、次にその要素、使用法および結果として生じる安全性を説明することによって導入することにする。実際の暗号系（cryptosystem）の例は提示しない。	The new kind of cryptography will be introduced first in terms of an analogy and then by description of its parts, their use, and the resulting security properties. No actual example cryptosystem is presented.
基本的な概念	Basic idea
不視署名（blind signature）の概念は、卑近な紙の書類の世界から持ち込まれる例によって説明することができる。不視署名に対応する紙の書類の世界の類似物は、カーボン紙で内側が覆われた封筒を使って実装することができる。そのような封筒の外側に署名すると、封筒の中にあるカーボン紙に署名の複写が残ることになる。	The concept of a blind signature can be illustrated by an example taken from the familiar world of paper documents. The paper analog of a blind signature can be implemented with carbon paper lined envelopes. Writing a signature on the outside of such an envelope leaves a carbon copy of the signature on a slip of paper within the envelope.
秘密投票方式によるが、有権者が単一の帽子の中に投票用紙を入れるために集まることができないような選挙を実施したいと思っている選挙管理機関が直面する問題のことを考えよ。それぞれの有権者は、自分の投票を選挙管理機関に対して秘匿することができるのか非常に懸念しており、更に、自分の投票が本当に数えられているか検証可能にするよう要求している。	Consider the problem faced by a trustee who wishes to hold an election by secret ballot, but the electors are unable to meet to drop their ballots into a single hat. Each elector is very concerned about keeping his or her vote secret from the trustee, and each elector also demands the ability to verify that their vote is counted.
この問題の解決策は、特別な封筒を使用することによって得られる。それぞれの有権者は、自身の意思を記入した投票用紙をカーボン紙で内側が覆われた封筒の中に入れ、その封筒を自身の返送用宛名を付し、選挙管理機関に宛てたもう1つの封筒の中に入れ、その封筒を選挙管理機関に郵送する。選挙管理機関は、有権者の返送用宛名が書かれた封筒を受け取ったら、中からもう1つの封筒を取り出し、その封筒の外側に署名し、新しい封筒の中に入れ、受け取った封筒に書いてある返送用宛名に宛てて返送する。このようにして、正当性が認められた有権者だけが、署名された投票用紙を受け取ることができる。もちろん、選挙管理機関はその選挙に対してのみ有効な特別な署名を使用する。	A solution can be obtained by use of the special envelopes. Each elector places a ballot slip with their vote written on it in a carbon lined envelope; places the carbon lined envelope in an outer envelope addressed to the trustee, with their own return address; and mails the nested envelopes to the trustee. When the trustee receives an outer envelope with the return address of an elector on it, the trustee removes the inner carbon lined envelope from the outer envelope; signs the outside of the carbon lined envelope; and sends the carbon lined envelope back, in a new outer envelope, to the return address on the old outer envelope. Thus, only authorized electors receive signed ballot slips. Of course, the trustee uses a special signature which is only valid for the election.
有権者は、署名された封筒を受け取ったら、中から内側がカーボン紙で覆われた封筒を取り出し、その封筒の署名を確認し、中から署名された投票用紙を取り出す。選挙日になったら、投票用紙を新しい封筒の中に入れて、返信用宛名を書かずに、選挙管理機関に郵送する。	When an elector receives a signed envelope, the elector removes the outer envelope; checks the signature on the carbon lined envelope; removes the signed ballot slip from the carbon lined envelope; and mails the ballot to the trustee on the day of the election in a new outer envelope, without a return address.
選挙管理機関は、投票用紙を受け取ったら、それを公開することができる。誰でも掲示された投票用紙の枚数を数えることができ、また、投票用紙の署名を確認することができる。有権者が投票用紙の繊維模様のような、自身の投票用紙を特定できる何らかの特徴を記憶しているならば、自身の投票用紙が公開されているか確認することができる。しかしながら、選挙管理機関は、投票用紙に署名する際に決して投票用紙を見ることはないので、（全ての署名が同一であると仮定すると）選挙管理機関は、投票用紙が誰のものであるか特定できるような如何なる特徴も知ることはできない。そのため、選挙管理機関は、投票用紙が含まれている署名された封筒と公開される投票用紙との間の対応について何も知ることはできない。したがって、選挙管理機関は、誰が何に投票したのかを断定することができない。	When the trustee receives the ballots, they can be put on public display. Anyone can count the displayed ballots and check the signatures on them. If electors remember some identifying aspect of their ballot, such as the fiber pattern of the paper, they can check that their ballot is on display. But since the trustee never actually saw the ballot slips while signing them (and assuming every signature is identical), the trustee can not know any identifying aspect of the ballot slips. Therefore, the trustee can not know anything about the correspondence between the ballot containing envelopes signed and the ballots made public. Thus, the trustee can not determine how anyone voted.
関数	Functions
不視署名系は、純粋に2つの鍵を用いるデジタル署名系と交換様式の公開鍵系が特別な方法で結合された系の特徴を有するものであると考えられるかもしれない。下記の3つの関数が不視署名の暗号系を構成している。         1 署名者のみが知っている署名関数 s' およびそれに対応する公知の逆関数 s で、s が s' についての手掛かりを与えないもの。         2 提供者のみが知っている交換関数 c およびその逆関数 c' で、c'(s'(c(x)))=s'(x) が成り立ち、c(x) および s' が x についての手掛かりを与えないもの。         3 有効な署名の探索を非現実的にするのに十分な冗長性を有するか確認する冗長性確認述語 r。	Blind signature systems might be thought of as including the features of true two key digital signature systems combined in a special way with commutative style public key systems. The following three functions make up the blind signature cryptosystem:         (1) A signing function s’ known only to the signer, and the corresponding publically known inverse s, such that s(s’(x))=x and s give no clue about s’.         (2) A commuting function c and its inverse c’, both known only to the provider, such that c’(s’(c(x)))=s’(x), and c(x) and s’ give no clue about x.         (3) A redundancy checking predicate r, that checks for sufficient redundancy to make search for valid signatures impractical.
手順	Protocol
これらの関数は、上で説明した例で、カーボン紙で内側が覆われた封筒が使用されるのと似た方法で使用される。         1 提供者は r(x) が真であるような x を無作為に選び、c(x) を生成し、署名者に渡す。         2 署名者は c(x) に s’ を適用することによって署名 s’(c(x)) を生成し、提供者に返す。         3 提供者は署名 s’(c(x)) に c’ を適用することによって裸状態の署名 c’(s’(c(x)))=s’(x) を生成する。         4裸状態の署名 s’(x) に署名者の公開鍵 s を適用し、r(s(s’(x))) が真であるか調べることによって、誰でも s’(x) が本当に署名者によって生成されたものであるか確認することができる。	The way these functions are used is reminiscent of the way the carbon paper lined envelopes were used in the example described above:         (1) Provider chooses x at random such that r(x), forms c(x), and supplies c(x) to signer.         (2) Signer signs c(x) by applying s’ and returns the signed matter s’(c(x)) to provider.         (3) Provider strips signed matter by application of c’, yielding c’(s’(c(x)))=s’(x).         (4) Anyone can check that the stripped matter s’(x) was formed by the signer, by applying the signer’s public key s and checking that r(s(s’(x))).
性質	Properties
上記の関数と手順からなる不視署名方式は、下記の安全保障の性質を有していることが望ましい。         1 デジタル署名――誰でも裸状態の署名 s’(x) が本当に署名者の秘密鍵 s’ を用いて生成されたものであるか確認することができる。         2 不視署名――署名者は裸状態の署名の集合の要素 s’(xi) と裸状態ではない署名の集合の要素 s’(c(xi)) の間の対応に関して何も知ることができない。         3 署名の保全――提供者は署名者によって生成されたそれぞれの署名に対して裸状態の署名を最大でも1つまでしか生成することができない（すなわち、c, c’, xi に対する裸状態ではない署名 s’(c(x1)) … s’(c(xn)) を保有していても、y!=xi であり r(y) が真であるような s’(y) を生成するのは非現実的である）。	The following security properties are desired of the blind signature system comprising the above functions and protocols:         (1) Digital signature—anyone can check that a stripped signature s’(x) was formed using signer’s private key s’.         (2) Blind signature—signer knows nothing about the correspondence between the elements of the set of stripped signed matter s’(xi) and the elements of the set of unstrapped signed matter s’(c(xi)).         (3) Conservation of signatures—provider can create at most one stripped signature for each thing signed by signer (i.e. even with s’(c(x1)) … s’(c(xn)) and choice of c, c’, and xi, it is impractical to produce s’(y), such that r(y) and y!=xi).
暗号学の研究でよく目にするように、独立して生成された無作為の数が同一の値である可能性があるということは無視している。	As is common in cryptographic work, the possibility that the same random number could be generated independently is ignored.
追跡不能な支払い方式	Untraceable payments system
模範的な支払い取引の例を用いて、追跡不能な支払い方式を構築するために、上で導入した不視署名の方法がどのように使用できるのかを説明することにする。重要なのは、銀行はどのようなものにも自身の秘密鍵で署名するが、そのようにして署名された全てのものは、たとえば、1ドルという風に、一定の価値しか持たないということである。下記の例で登場する人物および機関は、銀行、支払人および受取人である。支払人が1枚の紙幣を生成し、銀行が署名し、支払人が裸の状態にし、受取人に与えられ、銀行が消去する。1回の支払い取引は、詳細には下記のような段階で進行する。         1 支払人は r(x) が真であるような x を無作為に選び、紙幣 c(x) を生成する。         2 支払人は紙幣 c(x) を銀行に転送する。         3 銀行は紙幣に署名する。すなわち、s’(c(x)) を生成する。更に、支払人の口座の借方に金額を記入する。         4 銀行は署名した紙幣 s’(c(x)) を支払人に返送する。         5 支払人は c’(s’(c(x)))=s’(x) を生成することによって紙幣を裸の状態にする。         6 支払人は s(s’(x))=x が成り立つかどうかを確認して、そうでなければ中断する。         7 それから暫くして、支払人は支払いを行うために受取人に紙幣 s’(x) を渡す。         8 受取人は r(s(s’(x))) が真であるかどうかを確認して、そうでなければ中断する。         9 受取人は紙幣 s’(x) を銀行に転送する。         10 銀行はr(s(s’(x))) が真であるかどうかを確認して、そうでなければ中断する。         11 銀行は消去済みの紙幣を網羅した一覧表に受け取った紙幣を追加する。受け取った紙幣が既に一覧表の中に存在する場合は中断する。         12 銀行は受取人の口座の貸方に金額を記入する。         13 銀行は受け取りが受理されたことを受取人に通知する。	An example payment transaction will illustrate how the blind signature systems introduced above can be used to make an untraceable payments system. The critical concept is that the bank will sign anything with its private key, but anything so signed is worth a fixed amount, say $1. The actors in the example below are a bank, a payer, and a payee. A single note will be formed by the payer, signed by the bank, stripped by the payer, provided to the payee, and cleared by the bank. The following traces the detailed steps of a single payment transaction:         (1) Payer chooses x at random such that r(x), and forms note c(x).         (2) Payer forwards note c(x) to bank.         (3) Bank signs note, i.e. forms s’(c(x)), and debits payer’s account.         (4) Bank returns the signed note, s’(c(x)), to payer.         (5) Payer strips note by forming c’(s’(c(x)))=s’(x).         (6) Payer checks note by checking that s(s’(x))=x and stops if false.         (7) Payer makes payment some time later by providing note s’(x) to payee.         (8) Payee checks note by forming r(s(s’(x))) and stops if false.         (9) Payee forwards note s’(x) to bank.         (10) Bank checks note by forming r(s(s’(x))) and stops if false.         (11) Bank adds note to comprehensive list of cleared notes and stops if note already on list.         (12) Bank credits account of payee.         (13) Bank informs payee of acceptance.
上記の不視署名の性質により、銀行は、消去されることになる紙幣を段階9で受取人から受け取っても、元々その紙幣が段階4でどの支払人に対して発行されたものであるか知ることはない。デジタル署名およびそれに関連する上記の署名性質の保持によって、偽造行為が不可能であることが保証される。	Notice that by the blind signature property above, when the bank receives a note to be cleared from the payee in step (9) the bank does not know which payer the note was originally issued to in step (4). The digital signature and related conservation of signatures properties above ensure that counterfeiting is not possible.
監査可能性	Auditability
現在の取引慣行を電子的な世界に演繹すると、支払人は受取人からデジタル領収書を受け取るということになる。このような領収書には、購入した商品あるいは役務に対する説明および購入日が記載されているだろう。それに加えて、領収書には、支払いに使用した紙幣の複製を添付することができる。会計監査のような特別な状況下では、支払人は、領収書に添付されている紙幣の複製によって、銀行と協力して（また、後述のように清算機関と協力して）、紙幣が実際にはどの口座に預け入れられたのかを検証することができるだろう。	Extension of current practice suggests that payers receive digital receipts from payees. These receipts would include the usual description of the goods or services purchased, and the date. In addition, the receipt could also include a copy of the note. Under exceptional circumstances, such as an audit, the note would allow the payer, with the cooperation of the bank (and clearing house(s) as described below), to verify which account the note was actually deposited to.
実際に紙幣が預け入れられた口座ではなく、別の口座にその紙幣が預け入れられたということを示している領収書が存在するならば、それは不正行為の証拠であるだろう。不満を持っている闇市場の顧客は、闇市場に供給された紙幣を明らかにすることができ、その結果、その紙幣が最終的に到達した口座までの動きを追跡することができる。盗難に遭ったという報告を受けたもののまだ消去されていない紙幣は、清算機関の一覧に含めることができ、このようにして、消去されることがないようにできる。盗まれた紙幣で既に消去されているものは、その動きを追跡することができる。	A receipt indicating that a note was deposited to an account other than the account actually deposited to would be evidence of fraud. One dissatisfied customer of a black market could reveal a note supplied to the black market, which could then be traced to the account it ultimately ended up in. Uncleared notes reported as stolen could be included on clearing house lists and thus be prevented from being cleared; stolen notes cleared could be traced.
受取人によって支払人に発行された領収書は、全ての流出の管理手段を提供し、したがって、全ての資金の流れの管理手段を提供する。納税者は税務監査のために必要な任意の出費に対する検証可能な領収書を提供することができる。個人は実質的な流入に対する領収書を保持する必要があるかもしれないが、組織が流入に対する領収書を保持するのは望ましくないかもしれない。なぜなら、その組織の顧客を明らかにしてしまう可能性があるからである。	Receipts issued by payee to payer provide control over all outflows, and thus all flows of funds. A taxpayer could provide verifiable receipts for any expenditures needed for tax audit. Individuals could be required to keep receipts for substantial inflows, but inflow receipts maintained by organizations may be undesirable, if they could reveal the organization’s patrons.
精緻化	Elaborations
技術的な機構の効率的な使用、業務の分割および分散化を可能にするために、様々な方法を使って、上記の単純な方式の例を拡張することができる。たとえば、額面金額の異なる複数の紙幣を使用すれば、効率性が明確に向上するだろう。銀行業務および清算機関の業務は分離することができる。複数の銀行が存在する可能性があり、複数の清算機関は異なる銀行あるいは重複する銀行に対して業務を行う可能性がある。紙幣を署名するのに用いられる鍵を定期的に変更すると、安全性および監査可能性が向上し、貨幣供給量に関する不確実性が減少するかもしれない。	The simple system of the above example could be extended in various ways to provide economy of mechanism, disaggregation of services, and decentralization. For example, obvious efficiencies would result from use of multiple denomination notes. The banking and clearing house functions could be separated. There might be multiple banks; multiple clearing houses could serve different or overlapping banks. Periodic changes of the key(s) used to sign notes might increase security, increase auditability, and reduce uncertainty about the size of the money supply.
要約および推測される影響	Summary and implications
新しい種類の暗号学的手法である不視署名を導入した。これによって、現在の方式と比較して、より強力な監査可能性と管理手段を提供し、同時に、より強力な私事権を提供する追跡不能な支払い方式を実現することが可能となる。	A new kind of cryptography, blind signature, has been introduced. It allows realization of untraceable payments systems which offer improved auditability and control compared to current systems, while at the same time offering increased personal privacy.