Topic: Cryptonote auditability and efficient scheme for anonymous key vector proof. (Read 129 times)

Hello all,

Some time ago I read the Cryptonote original whitepaper and became interested in the possibility
of adding an optional wallet balance audit to it.

The balance audit seems a quite desirable option for an anonymous cryptocurrency, together with other
types of audits like total coins amount (that is trivial for a currency without hidden amounts).

As I wasn't able to find any publication describing any ready cryptographic scheme for the wallet
balance audit, I tried to think out mine.

This resulted in a series of posts that I put to the medium:
https://medium.com/@coffeemas1/cryptonote-auditability-how-to-append-the-wallet-balance-audit-b2e5b47b69a6
Maybe, it could be of interest to someone.


As of today, I have obtained the following optimized scheme, that takes only
sizeof(ec_point)*2+sizeof(int)*(n+1) for the auditable wallets signature size:
https://medium.com/@coffeemas1/multi-signature-within-lsag-one-more-memory-efficient-approach-to-unlinkable-auditable-wallets-b70cc86d7c30

Also, I provide a generalized scheme for arbitrary key vectors, that takes
sizeof(ec_point)*m+sizeof(int)*(n+1) for NIZK proof of m key images.

The idea is that it's possible to combine a BN-style multi-signature formula with a method used in the
LSAG to significantly reduce the number of integers in the signature.

Namely, suppose we want to prove the following statement:
I know a private key vector (x1, x2, ..., xm), such that
the corresponding public key vector is one of:
(X11, X12, ..., X1m)
(X21, X22, ..., X2m)
           ...
(Xn1, Xn2, ..., Xnm),
and the corresponding key image vector is:
(I1, I2, ..., Im),
    where the key images are defined as:
    (I1=x1*Hp(Xs1), I2=x2*Hp(Xs1), ..., Im=xm*Hp(Xs1)),
        where s is an index of true public key vector
        between the decoys above.


Then we can build a Schnorr-type ring signature as:
L1=r1*G+c11*X11+c12*X12+...+c1m*X1m
R1=r1*Hp(X11)+c11*I1+c12*I2+...+c1m*Im

L2=r2*G+c21*X21+c22*X22+...+c2m*X2m
R2=r2*Hp(X21)+c21*I1+c22*I2+...+c2m*Im
                                              ...
                                              ...
Ln=rn*G+cn1*Xn1+cn2*Xn2+...+cnm*Xnm
Rn=rn*Hp(Xn1)+cn1*I1+cn2*I2+...+cnm*Im
Where for each i the row (ci1, ci2, ..., cim) is generated as for the BN using some random seed ci,
and all n ci's are reduced to single c1 the same way as in the LSAG.

This gives the following signature:
signature=(I1, I2, ..., Im, c1, r1, r2, ..., rn)

Any comments are welcome)