Divisible Digital Cash Via Secret Sharing Schemes
Loading...
Date
2002-08
Authors
Yip, Wai Kuan
Journal Title
Journal ISSN
Volume Title
Publisher
Universiti Sains Malaysia
Abstract
Digital cash describes a class of cryptographically secure and transactionally anonymous payment
protocols featuring exchange of a data structure-thereafter referred to as a Coin-which can be
employed as a medium of exchange/store of value analogous to physical currency. It would
minimally be required to support offline (Coin authenticity is verifiable without Merchant-Bank
connectivity) and conditionally anonymous payment (the User's identity is untraceable until he
commits a fraudulent payment). However, Coin creation is typically processor and
storage/bandwidth intensive, hence the motivation for aggregating a withdrawal single episode over
multiple independent payment units or sub-Coins. Such digital cash schemes are said to be
divisible, which has no physical analogue given that a broken-off piece of physical currency is not
considered valid. Various divisible cash protocols based on the nested computation of modular ยท
quadratic residues (QR)-resulting in binary tree-like Coin structures-have been formulated, and -
have been demonstrated to be both theoretically elegant and computationally efficient. On the other
hand, their divisibility is based on successive binary exponentiations and would therefore be
transactionally awkward within the context of a decimal currency system.
This thesis demonstrates the incorporation of transactionally flexible k-divisibility into the Brands
single-term scheme by application of Shamir secret sharing (SS), and Feldman (1987) and Pedersen
( 1991) verifiable SS (VSS), which are respectively based on modular polynomial interpolation and
the discrete logarithmic (DL) protected analogue thereof. The purely DL nature of the featured
scheme contrasts with Okamoto's original tree-based scheme-which can itself be considered to be
a functional extension of the seminal Chaum digital cash-and with the Chan-Frankel-Tsiounis
composite construction of tree-like Coins within a fundamentally DL Brands framework. This
allows for an elliptic curve (EC) DL (ECDL) implementation; which invariably reduces processor,
storage and bandwidth overheads by a significant degree when deployed as a straightforward
replacement of a integer-field DL analogue. The experimental data, in fact, indicates that the
featured scheme would be more efficient than tree-based schemes (for a comparable degree of
security) for up to k -10, which would be adequate for most practical applications. The
dramatically reduced storage and bandwidth overhead also opens-up the possibility of
implementation on lightweight platforms i.e. smartcards and Personal Digital Assistants (PDA).
We demonstrate that a transactional solution featuring polynomial-divided sub-Coins in conjunction
with a small number of Coin denominations can be implemented so as to be comparable in
efficiency to a theoretically-optimal tree-based scheme. The thesis demonstrates a provisional
solution featuring a constraint-based sub-Coin dispenser to compute exact User-to-Merchant
payment or Merchant-to-User change, which would be useful and straightforwardly integratable
into a Coin-processing purse application.
Description
Keywords
Divisible digital cash via , via secret sharing schemes