Author: AdamISZ 2022-08-11 15:31:48
Published on: 2022-08-11T15:31:48+00:00
Recently, a lot of study has been done on the topic of sublinear ring signatures and Groth/Kohlweiss 2014 can give logarithmic scaled ring signatures. A blog by AdamISZ [1] was written about making logarithmic sized ring sigs on taproot keys. The outstanding question was how to get one/N time usage of these ring signatures with key images. Noether & Goodall's Triptych [3] can address this issue. The GK paper [2] is the core idea: bit decomposition of index. Bootle et al. in "Short Accountable Ring Signatures Based on DDH" in 2015 [4] found a significant further efficiency/compaction by generalising the concept a bit using an n-ary decomposition and delta-functions as a way to identify the index with the correct digits in n-ary. In 2020, Triptych was introduced which takes the n-ary decomposition as above and adds one more element: a key image, as in the basic cryptonote, LWW, LSAG design. Bootle et al. claimed their construction is "2.8 times smaller" than the GK [2] design. Adding in the key image needs more space in the proof, but only by less than a factor of 2. Therefore, Triptych [3] seems to give both things needed: first, a key image, which is essential for something like RIDDLE, along with a very compact size for high anon sets. The research endpoint, for now, is that Triptych [3] appears to be practical for genuinely big anonymity sets. There might be a sensible way of 'transferring' over to other curves via bilinear pairings crypto, which could give substantially more efficient constructions, but that would not work on 'bare' secp256k1. AdamISZ will probably add some code for this at some point to go along with the GK [2] toy code at [6].
Updated on: 2023-05-22T20:59:47.244013+00:00