An Ideal Untraceable Electronic Cash System

An Ideal Untraceable Electronic Cash System Discussion of a digital cash protocol proposed by Tatsuaki Okamoto and Kazuo Ohta In class presentation by Catalin Floristean

Overview
Preparations
Basic Scheme
Transferable Cash Protocol
Performance
References

Overview

"Ideal" untraceable electronic cash system:

Independence

Security

Privacy (Untraceability)

Off-line payment

Transferability

Dividability

Main advantage: dividability.

A cash balance of C dollars can be subdivided into many pieces in any desired way.

Efficient.

Less than 100 bytes per piece of e-cash, regardless of face value.

Seconds per transaction.

Security relies on difficulty of factoring.

Uses the cut-and-choose methodology.

New key techniques:

Square root modulo N (Wiliams integers).

Hierarchical structure table corresponding to the structure of the cash system.

Preparations

Number Theoretic Background

Blum integer: N = PQ (P, Q prime), P = 3 (mod 4), Q = 3 (mod 4).

Wiliams integer: N = PQ (P, Q prime), P = 3 (mod 8), Q = 7 (mod 8).

Quadratic rezidue: a, s.t. x²=a (mod m), where (a,m) = 1, is solvable.

(x/N) - Jacobi/Legendre symbol when N is composite/prime.

N = PQ (P, Q prime), Z_N can be classified into four classes:

Z_(1,1)   = {x in Z_N| (x/P) = 1, (x/Q) = 1}

Z_(1,-1) = {x in Z_N| (x/P) = 1, (x/Q) = -1}

Z_(-1,1) = {x in Z_N| (x/P) = -1, (x/Q) = 1}

Z_(-1,-1) = {x in Z_N| (x/P) = -1, (x/Q) = -1}

Z_(1,1) is QR_N, the other classes form QNR_N.

Proposition 1: Let N be a Blum integer and x in QR_N. Then, for any t >= 1, there are values y₁,y₂,y₃,y₄ s.t. y_i^{2^t}= x (mod N) and y₁ in Z_(1,1), y₂ in Z_(-1,1), y₃ in Z_(1,-1), y₄ in Z_(-1,-1). Moreover, y¹ = -y₄ (mod N), y₂= -y₃ (mod N), (y₁/N) = (y₄/N) = 1 and (y₂/N) = (y₃/N) = -1.

x^{1/2^t} mod N can be computed in expected polynomial time from x, P, Q.

(y/N) can be computed efficiently from y and N.

computing x^{1/2^t} mod N from x and N is as difficult as factoring N.

Proposition 2: Let N = PQ be a Williams integer. Then, for any x in Z_N, one of x, -x, 2x and -2x is in QR_N while the others are in QNR_N.



Notation (N is a Williams integer, x in QR_N and z in Z_N):

[x^{1/2^t} mod N]_QR = y, s.t. y^{2^t} = x mod N and y in QR_N.

[x^{1/2^t} mod N]₁ = y, s.t. y^{2^t} = x mod N, (y/N) = 1, 0 < y < N/2.

[x^{1/2^t} mod N]_-1 = y, s.t. y^{2^t} = x mod N (y/N) = -1, 0 < y < N/2.

<z>_QR= dz mod N, s.t. d in {+1, -1, +2, -2} and dz mod N in QR_N.

<z>₁= dz mod N, s.t. d in {+1, +2} and (dz/N) = 1.

<z>_-1= dz mod N, s.t. d in {+1, +2} and (dz/N) = -1.

Hierarchical Structure Table

Allows an issued electronic bill C to be subdivided into many pieces s.t.each piece is worth any desired value less than C and the total value of all pieces is C.

A complete binary tree of t levels with values stored at nodes.

Restrictions:

The value of a node is the sum of the values of the direct descendants.

When a node (the corresponding value) is used, all descendants and ancestors cannot be used (are disabled).

No node can be used more than once.

                           $100
                              O
                    -------/ \---------
                   /                          \
          $50 O                           O $50
        ------/   \-----           -----/   \------
       /                    \        /                     \
     O                    O     O                     O
   $25                $25   $25                  $25

Basic Scheme

Assumptions

Bank A, customer (payer) P, merchant (vendor) V.

A generates RSA keys for blind digital signatures:

(e_A,n_A;d_A) for the electronic license that A issues;

(e_A^',n_A^';d_A^'), (e_A^'',n_A^'';d_A^''), ... for the values of the electronic bills issued (e.g. $100, $500, etc.).

A sets the value of the security parameter K = O(|n_A|) = O(|n_A^'|) = ... (e.g. K = 40).

A publishes three randomized hash functions: f_G, f_L and f_O.

P has a bank account number ID_P and generates the RSA key (e_P,n_P;d_P) for digital signatures.

The Protocol

Part I: P opens an account with A and gets the electronic license B = {B_i| 1 <= i <= K/2}.

P chooses random values a_iand Williams integers N_i = P_iQ_i, i = 1 .. K.

P sends K blind candidates W_i to A (r_iare random integers in Z_nA and g is a one-way hash function):

S_i = ID_P || a_i || (g(ID_P || a_i))^dp mod n_p = S_1,i || S_2,i

I_1,i= S_1,i² mod N_i, I_2,i= S_2,i² mod N_i, I_i= I_1,i || I_2,i

Wi = r_i^eAg(I_i || N_i) mod n_A

A chooses a random subset of K/2 blind candidates (assume W_i, i = K/2+1 .. K).

P shows A the a_i, P_i, Q_i, (g(ID_P || a_i))^dp mod n_p,ID_P, r_i for those candidates.

                          K/2

A gives P ( II W_i)^dA mod n_A.

                          i = 1                                          K/2

P can extract the electronic license B = ( II g(I_i || N_i))^dA mod n_A.

                                                                         i = 1

Part II: P gets money from A (e.g. $100).

P chooses a random value b, sends Z to A, Z = r^eA^' g(B || b) mod n_A^', (r in Z_nA', random).

A gives Z^dA^' mod n_A' back to P and charges P's account $100.

P can extract the electronic bill C = (g(B || b))^dA^' mod n_A^'.

Part III: P pays shop V a certain amount (e.g. $75).

Preliminary step: P computes G_i,0 (i = 1 .. K/2) as G_i,0 = <f_G(C || 0 || N_i)>_QR.

To pay V $75, P computes X_i,00 ($50) and X_i,010 ($25) as:

X_i,00 = [G_i,00^1/2 mod N_i]_-1 = [G_i,0^1/4 mod N_i]_-1

X_i,010 = [G_i,010^1/2 mod N_i]_-1 = [(O_i,0²G_i,0)^1/8 mod N_i]_-1, where O_i,0 = <f_O(C || 0 || N_i)>₁.

                               G_i,0
                          1      O       O_i,0
                        -------/ \---------
                      /                           \

G_i,00 = G_i,0^1/2     O                            O   G_i,01 = O_i,0G_i,0^1/2

          ------/   \-----            -----/   \------
      1 /           O_i,00 \         /   1                \   O_i,01
      O                      O     O                      O

           G_i,000           G_i,001G_i,010                 G_i,011
               ||                     ||            ||                   ||
           G_i,00^1/2 O_i,00G_i,00^1/2 G_i,01^1/2    O_i,01G_i,01^1/2

P sends V: (I_i, N_i, X_i,00, X_i,010), (i = 1 .. K/2) and (B, C).

V verifies the validity of signatures B for {(I_i, N_i)}, and C for B.

V computes O_i,0, f_G(C || 0 || N_i), the verifies the validity of X_i,00, X_i,010 (d_iin {+1, -1, +2, -2}):

(X_i,00/N_i) = (X_i,010/N_i) = -1

X_i,00⁴= d_if_G(C || 0 || N_i) mod Ni

X_i,010⁸ = d_iO_i,0²f_G(C || 0 || N_i) mod Ni

If valid, V selects random bits E_i,00, E_i,010and sends them to P.

P computes Y_i,00and Y_i,010 and gives them to V:

L_i,00 = <f_L(C || 00 || N_i)>_QR

L_i,010 = <f_L(C || 010 || N_i)>_QR

Y_i,00 = [L _i,00^1/2mod N_i]_((-1)E_i,00)

Y_i,010 = [L_i,010^1/2 mod Ni]_((-1)E_i,010)

V verifies Y_i,00 and Y_i,010; if valid V accepts payment (d_i^'_,d_i^''in {+1, -1, +2, -2}):

(Y_i,00/N_i) = (-1) ^Ei,00, (Y_i,010/N_i) = (-1)^Ei,010

Y_i,00²= d_i^'f_L(C || 00 || N_i) mod Ni

Y_i,010² = d_i^''f_L(C || 010 || N_i) mod Ni

Part IV: A credits V's account the appropriate amount ($75).

V sends the history of PART III, H, to A.

A checks the validity of H; if invalid, secret information S_iof customer P is revealed.

If valid, A credits V's account.

Correctness

Independence

Off-line payment

Privacy (Untraceability) - if customer follows protocol accurately, even A + V cannot get any knowledge about P.

Dividability - insurred by the Hierarchical Structure Table(s).

Security:

Relies on dificulty of factoring.

The Hierarchical Structure Table's restrictions are securely realized.

The O function is important.

Transferable Cash Protocol

PART I: customers P1 and P2 open accounts at bank A and get licenses B^(j), j = (1,2).

PART II: P1 gets a $100 electronic bill C from A.

PART III: P1 transfers P2 the bill:

P2 takes the role of V and P1 pays "shop" P2 $25 (corresponding to node G₀₁₁) as in PART III above.

P1 sends certification T denoting the transfer of C from P1 to P2 (e.g. T = (<g(C || 011 || B⁽²⁾>_QR)^1/2 mod N₁⁽¹⁾.

PART IV: P2 pays shop V $25:

P2 sends history of the P1 -> P2 transfer H⁽¹⁾ to V; V checks validity.

P2 follows PART III of the basic protocol with shop V to pay C (P2 sends messages for nodes G₀₁₁⁽²⁾ and L₀₁₁⁽²⁾.

PART V: bank A credits V's account $25 after verifying (and storing) history H⁽²⁾ of PART IV above.

Performance

Assuming K = 40, |Ni| = 64 bytes, Hierarchical Structure Table with 17 levels, bills issued in $1000 denominations:

C can be stored using 64 bytes.

B uses several KB.

For a payment of $334.36 the smart card transmits 20 KB, computation time is seconds.

Easy to implement in smart cards.

References

T. Okamoto and K.Ohta, "Universal Electronic Cash", Advances in Cryptology -- CRYPTO '91 Proceedings, Springer-Verlag 1992, pp. 324-337.

T. Okamoto and K.Ohta, "Disposable Zero-Knowledge Authentications and Their Applications to Untraceable Cash", Advances in Cryptology -- CRYPTO '89 Proceedings, Springer-Verlag 1990, pp. 481-496.

D. Chaum, A. Fiat and M. Naor, "Untraceable Electronic Cash", Proceedings of CRYPTO '88, pp. 319-327.

M.O. Rabin, "Digitized Signatures and Public-Key Functions as Intractable as Factorization", Tech. Rep., MIT/LCS/TR-212, MIT Lab. Comp. Sci., (1979).

H.C. Williams, "A Modification of the RSA Public-Key Encryption Procedure", IEEE Trans, on Information Theory, Vol IT-26, No.6, pp. 726-729 (1980).