Bitcoin Forum
September 28, 2023, 02:21:00 PM
 News: Latest Bitcoin Core release: 25.0 [Torrent]
 Home Help Search Login Register More
 Pages: [1]
 Author Topic: ring signature efficiency  (Read 5679 times)
Sr. Member

Offline

Activity: 404
Merit: 332

in bitcoin we trust

 March 01, 2015, 12:19:30 PMLast edit: March 02, 2015, 03:48:29 PM by adam3us

The traceable ring signature used in cryptonote https://cryptonote.org/whitepaper.pdf looks like:

KEYGEN: P_i=x_i*G, I_i=x_i*H(P_i)

SIGN: as signer j; random s_i, w_i

(I relabeled q_i as s_i to be more standard, and relabeled the signer s as signer j)

IF i=j THEN L_i=s_i*G ELSE L_i=s_i*G+w_i*P_i
IF i=j THEN R_i=s_i*H(P_i) ELSE R_i=s_i*H(P_i)+w_i*I_j

c=h(m,L_1,...,L_n,R_1,...,R_n)

IF i=j THEN c_i=c-sum_{i!=j}(c_i) ELSE c_i=w_i
IF i=j THEN r_i=w_i-c_i*x_i ELSE r_i=w_i

\sigma = (m,I_j,c_1,...,c_n,r_1,...,r_n)

VERIFY:

L_i'=r_i*G+c_i*P_i
R_i'=r_i*H(P_i)+c_i*I_j
sum_{1..n}( c_j ) =? h(m,L_1',...,L_n',R_1',...,R_n')

where H(.) is a hash2curve function (taking a value in Zn and deterministically mapping it to a curve point), and h(.) is a hash function with a hash output size very close to n the order of the curve, ie h(.)=SHA256(.) mod n.

Towards finding a more compact ring signature I'd been trying to find a way to make c_i into a CPRNG generated sequence as they are basically arbitrary, though they must be bound to the rest of the signature (non-malleable) so that you can compute at most n-1 existential signature forgeries without knowing any private keys.

I found this paper "1-out-of-n Signatures from a Variety of Keys" by Abe, Ohkubo and Suzuki http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.363.3431&rep=rep1&type=pdf section 5.1 shows a way to do it.  I show here how to add traceability to it in a way that makes it compatible with crypto note:

KEYGEN: P_i=x_i*G, I_i=x_i*H(P_i)

SIGN: as signer j; \alpha = random, \forall_{i!=j} s_i = random

c_{j+1} = h(P_1,...,P_n,\alpha*G,\alpha*H(P_j))
c_{j+2} = h(P_1,...,P_n,s_{j+1}*G+c_{j+1}*P_{j+1},s_{j+1}*H(P_{j+1})+c_{j+1}*I_j)
...
c_j = h(P_1,...,P_n,s_{j-1}*G+c_{j-1}*P_{j-1},s_{j-1}*H(P_{j-1})+c_{j-1}*I_j)

so that defines c_1,...,c_n with j values taken mod l some number of signers.  Next find the s_j value:

Now \alpha*G = s_j*G+c_j*P_j so \alpha = s_j+c_j*x_j so s_j = \alpha - c_j*x_j mod n.

Similarly \alpha*H(P_j) = s_j*H(P_j)+c_j*I_j so \alpha works there too.

\sigma = (m,I_j,c_1,s_1,...,s_n)

VERIFY:

\forall_{i=1..n} compute e_i=s_i*G+c_i*P_i and E_i=s_i*H(P_i)+c_i*I_j and c_{i+1}=h(P_1,...,P_n,e_i,E_i)

check c_{n+1}=c_1

This alternate linkable ring signature tends to 1/2 the size of the crypto note ring signature as the signature is 3+n values vs 2+2n values.

hashcash, committed transactions, homomorphic values, blind kdf; researching decentralization, scalability and fungibility/anonymity
1695910860
Hero Member

Offline

Posts: 1695910860

Ignore
 1695910860

1695910860
 Report to moderator
1695910860
Hero Member

Offline

Posts: 1695910860

Ignore
 1695910860

1695910860
 Report to moderator
1695910860
Hero Member

Offline

Posts: 1695910860

Ignore
 1695910860

1695910860
 Report to moderator
"You Asked For Change, We Gave You Coins" -- casascius
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
1695910860
Hero Member

Offline

Posts: 1695910860

Ignore
 1695910860

1695910860
 Report to moderator
1695910860
Hero Member

Offline

Posts: 1695910860

Ignore
 1695910860

1695910860
 Report to moderator
1695910860
Hero Member

Offline

Posts: 1695910860

Ignore
 1695910860

1695910860
 Report to moderator
waxwing
Sr. Member

Offline

Activity: 469
Merit: 250

 March 01, 2015, 09:21:29 PM

http://www.texpaste.com/ is an easy way to throw out some TeX; maybe mods would consider implementing formatting for it?

PGP fingerprint 2B6FC204D9BF332D062B 461A141001A1AF77F20B (use email to contact)
sickpig
Legendary

Offline

Activity: 1260
Merit: 1008

 March 02, 2015, 09:26:47 AM

http://www.texpaste.com/ is an easy way to throw out some TeX; maybe mods would consider implementing formatting for it?

it would be useful imho, look at Adam post "translated":

http://www.texpaste.com/n/xaypn9ni

fancy, isn't it?

Anyway I think that cryptonote based coins devs would find Adams's finding useful.

Bitcoin is a participatory system which ought to respect the right of self determinism of all of its users - Gregory Maxwell.
Sr. Member

Offline

Activity: 404
Merit: 332

in bitcoin we trust

 March 21, 2015, 03:29:14 PM

I found this paper "1-out-of-n Signatures from a Variety of Keys" by Abe, Ohkubo and Suzuki http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.363.3431&rep=rep1&type=pdf section 5.1 shows a way to do it.  I show here how to add traceability to it in a way that makes it compatible with crypto note:

KEYGEN: P_i=x_i*G, I_i=x_i*H(P_i)

SIGN: as signer j; \alpha = random, \forall_{i!=j} s_i = random

c_{j+1} = h(P_1,...,P_n,\alpha*G,\alpha*H(P_j))
c_{j+2} = h(P_1,...,P_n,s_{j+1}*G+c_{j+1}*P_{j+1},s_{j+1}*H(P_{j+1})+c_{j+1}*I_j)
...
c_j = h(P_1,...,P_n,s_{j-1}*G+c_{j-1}*P_{j-1},s_{j-1}*H(P_{j-1})+c_{j-1}*I_j)

so that defines c_1,...,c_n with j values taken mod l some number of signers.  Next find the s_j value:

Now \alpha*G = s_j*G+c_j*P_j so \alpha = s_j+c_j*x_j so s_j = \alpha - c_j*x_j mod n.

Similarly \alpha*H(P_j) = s_j*H(P_j)+c_j*I_j so \alpha works there too.

\sigma = (m,I_j,c_1,s_1,...,s_n)

VERIFY:

\forall_{i=1..n} compute e_i=s_i*G+c_i*P_i and E_i=s_i*H(P_i)+c_i*I_j and c_{i+1}=h(P_1,...,P_n,e_i,E_i)

check c_{n+1}=c_1

It looks like Joseph Liu, Victor Wei and Duncan Wong made the same observation in "Linkable Spontaneous Anonymous Group
Signature for Ad Hoc Groups" 2004 https://eprint.iacr.org/2004/027.pdf

The proposed scheme is basically the same as what I propose above, and the Liu, Wei & Wong 2004 publication seems to predate the 2007 Fujisaki & Suzuki "Traceable ring signature" https://eprint.iacr.org/2006/389.pdf cited by cryptonote.

hashcash, committed transactions, homomorphic values, blind kdf; researching decentralization, scalability and fungibility/anonymity
marcus_of_augustus
Legendary

Offline

Activity: 3920
Merit: 2347

 March 23, 2015, 11:38:20 PM

Thanks for posting Adam, that looks like some useful milestones.

np
Newbie

Offline

Activity: 9
Merit: 0

 March 26, 2015, 08:26:01 AM

It looks like Joseph Liu, Victor Wei and Duncan Wong made the same observation in "Linkable Spontaneous Anonymous Group
Signature for Ad Hoc Groups" 2004 https://eprint.iacr.org/2004/027.pdf

The proposed scheme is basically the same as what I propose above, and the Liu, Wei & Wong 2004 publication seems to predate the 2007 Fujisaki & Suzuki "Traceable ring signature" https://eprint.iacr.org/2006/389.pdf cited by cryptonote.

For his master project/thesis, Jesper Borgstrup (https://jesper.borgstrup.dk/about/) worked on integrating ring-signatures to bitmessage to support a decentralized and trustless e-voting system. The thesis is titled "Private, trustless and decentralized message consensus and voting schemes" (https://jesper.borgstrup.dk/2015/01/masters-thesis-private-trustless-decentralized-message-consensus-voting-schemes/) and can be of interest.

In particular he based his work on the 2004 paper you mentioned by Liu, Wei & Wong. He translated it to elliptic curves and implemented in Python to integrate it in PyBitmessage.

We discovered cryptonote later on and were actually surprised to see that they based their work on "traceable ring signature" to make it linkable without mentioning this prior work.

-- NP
smoothie
Legendary

Offline

Activity: 2464
Merit: 1471

LEALANA Bitcoin Grim Reaper

 November 28, 2015, 06:23:46 AM

This thread was referenced in the followig Ring Confidential Transactions pdf paper by Shen Noether.

https://github.com/ShenNoether/MiniNero/raw/master/RingCT0.5_copy.pdf

The 1/2 size reduction is referenced in the first few pages.

Good stuff.

 ███████████████████████████████████████            ,╓p@@███████@╗╖,                    ,p████████████████████N,              d█████████████████████████b          d██████████████████████████████æ      ,████²█████████████████████████████,   ,█████  ╙████████████████████╨  █████y  ██████    ████████████████    ██████ ║██████       Ñ███████████      ██████████████         ╩██████Ñ         ██████████████    ▐▄     ²██╩     a▌    ███████╢██████    ▐▓█▄          ▄█▓▌    ███████ ██████    ▐▓▓▓▓▌,     ▄█▓▓▓▌    ██████─           ▐▓▓▓▓▓▓█,,▄▓▓▓▓▓▓▌                      ▐▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▌               ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓─        ²▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓╩             ▀▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▀                   ²▀▀▓▓▓▓▓▓▓▓▓▓▓▓▀▀                              ²²²                  ███████████████████████████████████████ . ★☆ WWW.LEALANA.COM        My PGP fingerprint is A764D833.                  History of Monero development Visualization ★☆ .LEALANA BITCOIN GRIM REAPER SILVER COINS.
virtualx
Hero Member

Offline

Activity: 672
Merit: 507

LOTEO

 November 28, 2015, 12:53:32 PM

http://www.texpaste.com/ is an easy way to throw out some TeX; maybe mods would consider implementing formatting for it?

Tex support would make it lots easier to read. I found this mod for TeX support http://custom.simplemachines.org/mods/index.php?mod=1111. I didn't check the code so I'm not sure if it's secure.

 ...loteo...DIGITAL ERA LOTTERY ║║║ .r── TRANSPARENT ──....BLOCKCHAIN LOTTERY. r ▄▄███████████▄▄▄███████████████████▄▄███████████████████████▄▄██████████████████████████▄▄██  ███████▌ ▐██████████████▄▐██▌ ▐█▀  ▀█    ▐█▀   ▀██▀  ▀██▌▐██  █▌ █▌ ██  ██▌ ██▌ █▌ █▌ ██▌▐█▌ ▐█ ▐█ ▐█▌ ▐██  ▄▄▄██ ▐█ ▐██▌▐█  ██▄  ▄██    █▄    ██▄  ▄███▌▀████████████████████████████▀▀██████████████████████████▀▀███████████████████████▀▀███████████████████▀▀▀███████████▀▀ r ..AFFILIATE AVAILABLE!r..... UP TO 40% REWARD ... ║║║ RPLAY NOWRBE A MOON VISITOR!
[/center]
jinumm
Newbie

Offline

Activity: 1
Merit: 0

 November 30, 2015, 06:43:10 AM

thanks adam, i recently use texpaste its good for us, thanks alote
 Pages: [1]