Context

I am implementing LSAG in python because I do not find a non-obviously insecure implementation. I am not a cryptographer myself, thus simplicity is key.

The famous Linkable Spontaneous Anonymous Group Signature for Ad Hoc Groups paper states these algorithm parameters:

Parameters:

1. group G of prime order q
2. hash-function H1 : {0,1}* --> Z_q
3. hash-function H2 : {0,1}* --> G

Requirements:

• discrete log problem over G must be hard
• H1 and H2 must be some statistically independent cryptographic hash functions

Proposed:

• Hashes onto elliptic curves are hard, so I use G = Z mod n with g=suff large prime.
• the thought with g suff large and prime is that i) each exponent yields overflow and thus cryptosecurity and ii) each integer in [0,n) is attainable via the generator.
• Since the order q of G is needed, I choose n prime and obtain q=n-1.
• Since H1 and H2 must be uncorrelated, I simply pick H1=sha512(x)[0:256] and H2=sha512(x)[256:512]. If the bits of sha512 were correlated then it would be a stupid algorithm. I suppose it is not. Hence this choice should be save. Also, each

Questions:

• q is not prime. Does this result in security issues? (property was no-where used in the security analysis)
• There exist d in N such that g^d % n = H2(message). This can break anonymity of the ring-signature when someone is able to brute-force d. It would be beneficial if the image of H2 was disjoint to the span of the generator, hence no d exists. Is there a way to construct G accordingly as a ring?
• EC would be more efficient and secure. Is anyone aware of an implementation of LSAG in python or of triplets for G,H1,H2 (i.e., code) that yield the purpose?
• Monero used to use something called MLSAG, which is a generalization of LSAG that uses Ed25519. There is some Python code for it (which I don't think had a rigorous security audit) here: github.com/monero-project/mininero/blob/master/MLSAG.py Hashing to a group element is implemented with the function name "hashToPoint_cn". You can find exact instructions for implementation of an LSAG here: getmonero.org/library/Zero-to-Monero-2-0-0.pdf on page 30. Jul 30 at 22:54
• I know one shall not thank in comments. But thank you massively for that!!!! I was hustling the information for weeks. This is tremendously useful. Jul 31 at 21:02
• @knaccc : Are you able to make accessible the "hashToPoint_cn" function? I actually do not find it in the repository, nor on github. I see that it is called but I do not find a definition of it. Jul 31 at 21:14
• It's here: github.com/monero-project/mininero/blob/…. Also note: this is implemented to match Monero's implementation, which went to great lengths to be high-performance. There are much easier ways to do hash-to-point, such as simply taking a 256-bit hash, interpreting the result as a compressed point coordinate, incrementing it if you have an invalid point (50% chance), then multiplying it by 8 to ensure it's in the correct subgroup Jul 31 at 23:06
• @knaccc: thank you a lot. Yes, once performance becomes a problem I will probably want to keep this in mind. For now, I have actually opted back towards discrete log and found a way with quadratic residues to make sure a point lives in the ring. Aug 2 at 7:10