AppeCoin, Sergio D. Lerner‘s proposal for an ecash scheme, is designed for a peertopeer network which does not rely on a Trusted Third Party. Like the cryptocurrencies Monero or Zcash, AppeCoin is a protocol which aims to guarantee to its users full privacy. Lerner’s ecash scheme leverages coin shuffling. Unlike ZeroCoin, where the monetary units are of a fixed value and so the transaction amount can be deduced from the number of units sent, AppeCoin enables users to truly hide transaction amounts by offering the option to divide and combine coins.
You can find the latest version of the AppeCoin draft here.
Overview:
Peers have private accounts and can send monetary units, called bills, to other peers. The amount of a bill is encrypted and is only known to the bill`s owner. Bills can be divided into smaller bills or combined into larger bills. The process of bill splitting and bill combining can be done without revealing the value of the bill or its parts. Zeroknowledge proofs are used to demonstrate correctness: the value of the bill is equal to the sum of its parts. There is a minimum bill value in order to avoid inflation.
Transactions to other peers can be sent without revealing their public addresses by using universal reencryption. Once a payment is sent, it has to be accepted by the receiver. Payer and payee exchange the secret keys of the encrypted bill. The communication between payer and payee uses hybrid encryption and entity authentication.
The community verifies the validity of transactions and that coins have been divided or combined correctly. In a proofofwork based framework, these changes are recorded in a ledger maintained by the miners. In order to increase anonymity, AppeCoin provides private, delegated, and public bill shuffling. The correctness of the shuffles is verified by the miners.
AppeCoin seeks to ensure (see p. 6 in draft):
 Efficiency: low transaction waittime.
 Security: no doublespending, no overspending, unforgeability (of bills and payment transcripts), authenticity, nonrepudiation, portability.
 Privacy: anonymity (payer cannot be identified from data exchanged during payment), untraceable (infeasible to follow the history of a bill), unlinkable payments, private account balance, hidden transaction amounts.
The difficulty of the decisional DiffieHellman problem and of the representation problem should guarantee security and privacy as long as the encryption scheme used resists Ciphertextonly attacks and ChosenPlaintext attacks.
More Details:
Below, we describe some key cryptographic building blocks and algorithms used in the AppeCoin protocol.
A.1: Universal ReEncryption of Schnorr Public Keys: A bill contains the public key of the present bill owner. Universal reencryption is used to reencrypt the public key of the bill owner without making him change his private key.
A.2: Bill Shuffle: The BillShuffle algorithm shuffles the bills and provides a zeroknowledge proof of correctness of the shuffle. The input of the BillShuffle algorithm is a list A = (a_{1}, … , a_{n}) of bills a_{i} with i=1, … , n and its output is a list B = (b_{1}, … , b_{n}) where b_{i} is the encryption of a_{π(i)} for a permutation π with encryption key k.
Two proof systems are considered in AppeCoin proposal. Both apply the FiatShamir heuristic to an interactive publiccoin proof system. The second proof system proposed uses a (pseudo)random subset test which makes it more efficient. Zeroknowledge is achieved by blinding the encryption key and only showing the verifier the image or preimage of a randomly chosen subset under the given permutation π, but not the subset itself. The prover commits to the encryption of the product of the elements of the subset. The assumed hardness of the representation problem makes it difficult to just guess the product.
A.3: CoinSplitting: The input of the CoinSplitting algorithm is a bill a and produces an output of two bills b and c whose values add up to the value of bill a. The algorithm provides a zeroknowledge proof for correctness.
The amount v of a bill is hidden in the exponent, i.e. as x^{v}. (Note that in the proposal exponentiation refers to homomorphic encryption). The core idea of the CoinSplitting algorithm for proving balance, i.e. v_{a}= v_{b} + v_{c}, is to check the correctness of the equation x^{va} = x^{vb} × x^{vc}. A blinding factor is used to disguise proportion: x^{kva} z^{k}= x^{kvb} z^{kb} × x^{kvc} z^{kc} with k=k_{b} + k_{c} for random k_{b} and k_{c}. The prover changes exponents or multiplies factors and provides the verifier with proofs of knowledge.
A.4: InRangeProof: The input for the InRangeProof algorithm is a bill and a range for its value. When the bill is in the given range, the algorithm´s output is 1.
A.5: SendBill: This action includes two algorithms which produce a public and a private message.
Public message: This message is spread through the network and contains the hash of the public key of the current bill owner, and the destination address and signature of the sender.
Private message: This message is sent privately from the sender to the receiver of the transaction, and is essentially the encryption of the secret keys of the bill, so that the receiver can verify the amount and modify the bill.
A.6: ReceiveBill: The receiver checks the sender´s identity, and verifies that the bill and the amount which was sent to him, is correct.
A.7: Public Check of Transaction: Miners search for the serial number of the bill in the ledger, and verify that the bill is unspent and that the sender´s Schnorr signature is correct. The sender´s public address is temporarily visible, until it is disguised by reencryption.
Comments:
We think the AppeCoin proposal is exciting and would like to comment on some of its strong points and point to places which we think should be filled out more.
Ad A.1: Universal ReEncryption:
a) The decisional DiffieHellman (DDH) should be assumed instead of computational DiffieHellman (CDH) (AppeCoin draft, p. 8).
b) The AppeCoin draft claims that universal reencryption is secure for any encryption scheme satisfying indistinguishability, but provides no reference. Young/Yung´s article Semantically Secure Anonymity: Foundations of ReEncryption demonstrates the security for one such encryption scheme, the ElGamal encryption.
Ad A.2: BillShuffle:
a) Security aspects: Formal proof is needed for the claim that BillShuffle provides a noninteractive zeroknowledge proof.
The FiatShamir heuristic is a common way to transform a constant round interactive proof into a noninteractive proof. The heuristic is proven to be secure, i.e. computationally sound, in the random oracle model. Some examples of insecure transformations exist in the plain model, but the FiatShamir heuristic applied to interactive proofs, not just arguments, was recently proven secure under some conditions for the hash functions involved. See TaumanKalai/Rothblum/Rothblum.
Some evidence is provided for the security of the BillShuffle algorithm, but there is no formal proof of security in the draft. Completeness is straightforward. The article of TaumanKalai/Rothblum/Rothblum may imply that the BillShuffle algorithm satisfies computational soundness even in the plain model: the FiatShamir transform is applied to proofs. Although it seems plausible that zeroknowledge can be deduced from the strength of the encryption scheme, the required zeroknowledge simulator is missing.
b) Performance: The proof system with the random subset test requires an average of rounds*3/2 exponentiations to prove and verify a shuffle of n bills which results in a very fast run time. [Compare the shuffle protocol by Abe (22*n log(n) exponentiations), SakoKilian (642*n exponentiations), Furukawa or Groth or LipmaaFausti/Zajac (using pairings: roughly 3n), LindellPinkas (cutandchoose on circuits; roughly 15qn + 39n + 10q + 6 exponentiations, where q is a statistical security parameter)].
The private keys of shuffle participants may be vulnerable to sidechannel attacks since a participant of a shuffle must decrypt all shuffled bills until he finds his own which causes an average of n/2 calls of his private key.
c) Technical Remarks:

 In figure 4, the definition of b_{w} as b_{w}:=a_{w}^{k} is missing.

 In figure 7, p. 13, Blob D should start with s (number of rounds) in order to have the same hash H(C) as in the proof;

 In figure 7, p. 13, b_{j} in 8.2.3 should be swapped with a_{Q(s,i)} in 9.2.3;
 In figure 8, p. 14, in 14.1.1.3, t_{s} × k should be replaced by r_{s} × k. Index s should be j. Similarly, this applies to t_{s} × k^{1} in 1.4.2.1.1.
Ad A.3: CoinSplitting:
a) Security aspects: Formal proof is needed for the claim that CoinSplitting provides a zeroknowledge proof for correctness.
Heuristically, the Discrete Logarithm Problem makes it hard for the prover to cheat the verifier by changing exponents. The prover could try to push some part of v_{b} into the exponent of the neighboring factor z, but he would have to know the logarithm of the blinding factor (which should be verifiably chosen at random) with respect to the basepoint or with respect to x. However, the draft lacks a formal proof for soundness. Although we could find no evidence that the proof in CoinSplitting leaks information, the draft does not provide a formal proof for zeroknowledge.
b) Performance: Proof and verification for two bills requires 12 exponentiations and many zkproofs of knowledge of encryption keys (e.g. using Schnorr ID protocol in case of a PohligHellman encryption scheme). The proposal´s author, Sergio Lerner, hopes to improve this in the future.
c) Technical Remarks:
 In DecompProof1, p. 23, we suggest defining b_{u} as b_{u}=a^{‘}_{u}, i.e., b_{u}= a_{u}^{k qb} ; otherwise b_{t}= b_{u}^{t }does not hold;
 In DecompProof1, p. 23, Step 6 should be analogous to step 3.
Additional Resources
 APPECoin, a system with total anonymization – key design points
 APPECoin (Anonymous PeertoPeer electronic Coin) design (2012)
 AppeCoin Anonymous Cryptocurrency Draft (2014)
Permalink
Permalink
Permalink