Tatsuaki Okamoto is the real Satoshi Nakamoto, who will write such a paper in 1990s and worked in the NSA at the same time, as we know NSA created SHA256 and SHA256 is the algorithm used in Bitcoin, this paper called "Universal Electronic Cash" is sufficient enough to prove who is the real Satoshi. Here is the paper: 1 Universal Electronic Cash Tatsuaki Okamoto KKazuo Ohta NTT Laboratorics Nippon Telegraph and Telephone Corporation 1-2356, Take, Yokosuka-shi, Kanagawa-ken, 238-03 Japan Abstract This paper proposes the first ideal untraccable electronic cash system which solves the most crucial problem inherent with real cash and all previous untraceable electronic cash systems. The main advantage of the new system is that the customer can subdivide his cash balance, C (dollars), into many pieces in any way he pleases until the total value of all subdivided piece equals C. This system can be implemented efficiently. In a typical implementation, the data size of one picce of electronic cash is less than 100 bytes regardless of the face value of piece, the computation time for cach transaction is several seconds, assuming the existence of a Rabin scheme chip. The security of this scheme relies on the difficulty of factoring. 1 Introduction Electronic cash is one of the most important applications of modern cryptology because an electronic moncy (cash) system will be widely installed in the near future; smart cards will become electronic wallets storing clectronic cash. The security of real cash heavily depends on physical properties such as the difficulty of reproducing bills and coins. The security of electronic cash systems cannot depend on any physical condition, but must be guarantecd by mathematics. Here, cryptographic techniques are essentially used to guarantee sccurity. Then, information itself has a value, and electronic cash can be transfered through networks. What then is the ideal cash system? The criteria describing the ideal cash system are as follows: (a) Independence: The security of electronic cash cannot depend on any physical condition. Then the cash can be transfered through networks. (b) Security: The ability to copy (reuse) and forge the cash must be prevented. (c) Privacy (Untraceability): The privacy of the user should be protected. That is, the relationship between the user and his purchases must be untraccable by anyone. (d) Off-line paymeni: When a user pay the electronic cash to a shop, the procedure between the user and the shop should be exccuted in an off-line manner. That is, the shop does not need to be linked to the host in user's payment procedure. ... 2 Preparations 2.1 Number Theoretic Conventions Definition 2.1 N is called the Blum integer [Bl] if N = PQ (P,Q are prime) and P =3 (mod 4), and Q=3 (mod 4). N is called the Williams integer [W] if N = PQ (P,Q are prime) and P = 3 (mod 8), and Q = 7 (mod 8). Note that the Williams interger is a specific type of the Blum integer. So, the Williams integer has all properties of the Blum integcr. Let (x/N) denote the Jacobi symbol, when N is a composite numbcr, and denote the Legendre symbol, when N is a prime. When N = PQ (P,Q are prime), we can classify Zx, into four classes; Za) = {2 € ZN (z/P) =1,(z/Q) = 1} Za,-1 = {x € Zy (2/P) = 1,(2/Q) = -1}, Z-13) = {z € ZN (z/P) = -1,(z/Q) = 1}, and Z(-1,-1) = {« € Zy | (2/P) = -1,(2/Q) = -1}. Clearly, Z(1,1) denotes the set of quadratic residuc intergers in Hereafter, we often write ORy as 24,1), and QNRy as the other classes. Proposition 2.2 Let N be the Blum integer, and x € QRy. Then, for any integer t (1 gpr= dz mod N such that d € {41,42} and dz mod N € QRy. ,=d'z mod N such that d' € {1,2} and (d'z/N) =1. _,;=d"z mod N such that d" € {1,2} and (d"z/N) = -1. From the properties of the Williams number (and the Blum number), each value of y,y',y", d,d',d" is uniquely determined respectively. 2.2 Hierarchical Structure Table In our cash system, the hierarchical structure table plays an important role because it allows the issued electronic bill C to be subdivided into many pieces such that each subdivided piece is worth any desired value less than C and the total value of all pieces is equivalent to C. The hierarchical structure table is a tree of ¢ levels, in which cach node has two sons, the unique root node exists at the top of the tree. So, there are 2'~! nodes at the 7-th level. Here, we show the significance of the tree in our cash system. For easy understanding, we use a simple example, where the tree has three levels, and the value of the issucd bill C is $100. The nodes of the i-th level correspond to $100/2'-'. So, the customer can use the bill in $25 increments, since the nodes of the bottom level (the third level) correspond to $25 (see Figure 1). We give two restrictions to the usage of the bill with relating to the tree as follows: 1. The value corresponding to a node, N, is the total of the values corresponding to nodes that are the direct sons of N. 2. When a node (the corresponding value) is used, all descendant nodes and all ancestor nodes of this node cannot be used. 3. No node can be used more than once. 3 Basic Universal Electronic Cash Scheme In this section, we introduce the basic universal electronic cash scheme which satisfics the five criteria ((a) through (f) except (c)(Transferability)). 3.1 Protocol Protocol 1 (Basic universal electronic cash): For blind digital signatures[Ch], bank A has generated keys of the RSA scheme; (ea,masdas), (el, na A? and d4,d,,... where (e4,n4),(e4,n), ... are public keys, are the corresponding secret keys. A has published (e4,n7,4), (e'A? n (e%s where (€4,n,) corresponds to the electronic license that A issucs, and (e/, 7/4), nt), correspond to the value of the clectronic bill that A issues. For example, $100 corresponds to (e',,n',), and $500 corresponds to (e4,n%), etc. Bank A1 also scts the security parameter K = O(|n,|) = O(|n4]) =... (for example, K = 40). A has also published three randomized hash functions, fr, fa, fa, to generate the hierarchical structure tables, [ table and A table. Herc, the function values are assumed to distribute uniformly (for example, the universal hash functions [CW], and pseudo- random gencrator). Note that the one-wayness or collision-freeness is not required for these functions. Customer P has a bank account number IDp and has generated the key of the RSA scheme, (ep,np;dp), and published (ep,np) for digital signatures. Note 1: Any multiple blind digital signature [OkOh1] can be used in place of the RSA scheme for bank A above. For example, the blind digital signature scheme based on the Fiat-Shamir signature scheme (OkOh2] can be used for this purpose. Morcover, any digital signature scheme can be uscd in place of the RSA scheme for customer P above. For example, [FOM] can be used for this purpose. Note 2: The secure exchange problem is out of the scope of this paper. For example, A and P exchange electronic cash and withdrawal, P and V exchange payment and articles, and V and A exchange payment history and credit. The secure exchange problem can be practically solved by the usage of digital signature schemes. More secure but less efficient solutions for this problem has been shown in ([EGL].Part I. 1 <2 < When a customer / opens an account at bank A, A issues an electronic license LlB = {B; | W/2} to use the electronic cash of bank A. (Precisely, the electronic license is (B, {J;,N;}, £). For simplicity, however, we simply call it B.) To get B, P conducts the following protocol with A. This procedure is executed only once when P opens the account, unless P uses the electronic cash invalidly. Step 1: Customer P chooses a random value a,, and the Williams integers N; with two large prime factors P;,Q; (Ni = P,Q;), where P; = 3 (mod 8) and Q; = 7 (mod 8),fori=1,...,K. Step 2: P forms and sends K blind candidates Wit=1,..., A) to bank A. W, = r gi | | Ni) modny for 1 QR, A;ouw =< fale 010 N;) >ar- Step 5: V verifies that (Yioo/Ni) = (-1)"°°, (¥io10/Ni) = (-1)"*°, 00 4,00 = GLa(C | ] | Nj) mod 72 = falC } 010 I Nj) mod N,, ,010 where di, € {+1,+2} (¢=1,...,4°/2). If verification succeeds, V accepts P's messages as $75 from electronic bill C. Next, we show the protocol of Part III in general cases. [Icre, we assume that T table has more than ¢ levels, and that the node corresponding to the value of P's payment to V is r (and Aj,...;,), where 1 jt € {0,1}. Usually, there are several nodes which correspond to the payment (e.g., in the above simple example, two nodes form P's $75 payment). Then, the following protocol of each node must be executed simultancously, in the same manner as the above protocol, which has two nodes. Step 1: This preliminary stage of Part III is the same as the above protocol. Step 2: When P determines the node, [';,...;, (and Aj,...;,), corresponding to the payment, P computes t, 1, = [OR74 02, 1,0 mod where 22; =< fa(C | | i P I ji Ni) >1- sends (J;, Ni, = 1,.--,4/2) and (B,C) to V. Note: The above calculation of X;,;,...;, is based on the following algorithm: i J1 Je mod N;]-1, where Dy in Step 3: V verifies the validity of the 9 signatures B for {(J;, N;)}, and C for B. V computes (if = 1) then verifies the validitv of @ that = 1...,. N19) such (X;,5,-- oe Ni) 1, -13, 0 Je fr(C | | | | Ni) mod Nj, = where d; € {+1,+2} (2 1,... 4/2). If they are valid, V selects random bits, = 77,11, € {0,1} (¢ 1,...,K/2), and sends them to P. Otherwise V halts this protocol. Copyright (c) 1998, Springer-Verlag 10 333 Step 4: P computes = [Av mod Ni) y* Here, je =< FACE [ai Uae NG) >er- Step 5: V verifies that Ni) = (-1) Ys = d fa(C | ] ji Ni) mod Ni, = where € {41,42} (¢ 1,...,4/2). If verification succeeds, V accepts P's messages as payment of the amount due. Note: To prevent bank A from crediting an invalid shop's account in Part II], we can enhance the protocol as follows: IIcre, we simply write E; as F;,;,...;,. V selects ©a random value E!, and sends V's identity Dy, time T, and (i = 1,..., 4/2) to P in place of where A is a sending £;. V computes (£y,..., = h(1Dy T | | one-way function whose output is uniformly random. P also computes E£; (t = 1,..., 4/2). Part IV. For bank A to credit V's account by the appropriate amount, V sends the history of Part III of this protocol, H, to A, which credits V's account. After checking the validity of H, bank A must store H in its database. If A finds an invalid payment, A reveal the secret information S; of costomer P who is responsible for the invalid payment from /I and the related history. (End of Protocol 1) Note 1: Since bank A has already known K/2 pieces of S; in Part I (e.g., (K/2+1) pieces of S; shown by A are the evidence of the invalid payment by a customer. Note 2: Bank A can store H with dividing it into two parts, H, and H2. H, is used to check the invalid payment, and H2 is to compute S; when A finds an invalid payment. Ay consists of the hashed value of C and the nodes corresponding to the payment. Here, the hashed value of C is the searching key in the database, and [/, can be very short (c.g, 10 bytes). On the other hand, Fz is almost same as H, and is pointed from H,. Therefore, H,1 can be stored in a database which is easy of access, while //, can be stored in a device such as a magnetic tape and a laser disk, which is not easy of access but has big capacity. H, and Hz (especially Hz) can be stored in a distributed manner. 3.2 Correctness Here, we show briefly that Protocol 1 satisfies the five criteria of (a) Independence, (b)Securit y, (c\Privacn, (d\Off-line payment. and (f\ Among them, criteria (a) and (d) are clearly satisfied. Therefore, we show that the other three criteria are satisfied. e Privacy: First, if the customer accuratcly follows the protocol, even the coalition of bank A and store V cannot get any knowledge about the identity of P with non-negligible probability, assuming that factoring is difficult for A and V. ... 6 Conclusion In this paper, we have proposed the first ideal untraccable electronic cash system, The customer can subdivide his cash balance, C (dollars), into many pieces in any way he pleases until the total value of all subdivided picce equals C. A smart card equipped with a Rabin scheme chip and the distributed database system for a bank to store HM, and Hy should be implemented efficiently to realize the universal clectronic cash system. From a theoretical viewpoint, it remains open to construct an unconditionally untraccable universal electronic cash system. ...