DahLIAS: Discrete Logarithm-Based Interactive Aggregate Signatures

The discussion between AdamISZ/waxwing and Tim centers on the technical aspects of a signing protocol within cryptocurrency technologies, referencing specifically to an earlier unpublished draft which explored a security proof without certain optimizations that were later considered. The conversation delves into the efficiency of the current signing protocol, which requires three group exponentiations. A proposal to use separate values for 'b' would change one of these exponentiations into a multi-exponentiation of size n-1, significantly affecting the time complexity from O(1) to O(n/log n) for both signing and verifying processes. This comparison brings into focus the trade-offs between computational efficiency and the scalability of cryptographic protocols.

AdamISZ/waxwing mentions discovering similar ideas in the original FROST paper the day after proposing his idea, highlighting the ongoing dialogue and development within the field. The exchange further explores the implications of such changes for Bitcoin and potentially other blockchain applications. Despite the increased computational demand, the argument is made that, in the context of Bitcoin or similar systems where the number of inputs (n) is capped, the scaling impact might be manageable. However, concerns are raised about the practicality of this approach beyond Bitcoin, considering hardware limitations and the broader applicability of the scheme to various cryptographic scenarios.

The conversation also touches upon the potential risks associated with the uniqueness check required by the proposed scheme. While acknowledging the possibility of implementation errors leading to vulnerabilities, they argue that such risks could be mitigated by creating specific test vectors to catch these issues. Furthermore, the dialogue considers how the scheme could handle malicious participants within a signing session, emphasizing the importance of honest coordinators and secure communication channels to accurately identify and exclude disruptive parties.

AdamISZ/waxwing expresses a preference for algebraic algorithms over those requiring comparative checks, citing reasons related to simplicity, ease of encoding in circuits for zero-knowledge proofs, and fewer conditional branches or loops in the code. This preference underscores a deeper interest in the foundational properties and operational efficiencies of cryptographic algorithms, reflecting broader considerations in the design and implementation of secure digital systems.