Cryptography Foundation

We will learn about the cryptography foundation behind the Desig Protocol.

Elliptic Curve Digital Signature Algorithms

Based on the article Cryptography behind the top 100 cryptocurrencies, most current blockchains support 2 well-adopted Elliptic Curve Digital Signature Algorithms namely EdDSA (Ed255519), and ECDSA (Secp256k1). By success to integrate them, Desig Protocol can fully serve the multisig solution to Bitcoin, Ethereum, BSC, Solana, Near, Cardano, Avalanche, and many others.

EdDSA (Ed25519)

$$s = r + H(R,Pub,m)*Priv$$

ECDSA (Secp256k1)

$$s = r^{-1}*(H(m)+R_x*Priv)$$

We shared the same notations in both algorithms.

• m: message

• s: signature

• r: random scalar

• R: on-curve point corresponding to r

• H: hash function

• Pub/Priv: public and private key

Shamir's Secret Sharing Scheme

In Desig Protocol, we target to build a layer-0 multisig solution, or chain-neutral multisig solution which means we are not using a smart contract as a layer for the multisig to consent and execute the transactions. Instead, the Desig protocol will cryptographically split a private key to multiple shares. By each share, shareholders can independently sign on the raw transaction and combine results into a single signature which is equivalent to the original signature. To build such a protocol, we employed Shamir's Secret Sharing Scheme.

$$f(0) = \sum_{j=0}^{k-1}y_j \prod_{i=0,i \neq j}^{k-1} \frac{x_i}{x_i-x_j}$$

The list of points on the polynomial is given as k pairs of the form .

ElGamal Encryption

This version is specialized to the aforementioned Elliptic Curves. ElGamal Encryption is working well in the context that people can encrypt a message by your public key, then you can decrypt it by the private key.

Key Generation

$$Pub = G * Priv$$

Encryption

$$E(m) = \{c=m+r*Pub, s= r*G\}$$

Decryption

$$D(c,s,Priv) = \{m=c-s*Priv\}$$

References

[1] Bernstein, Daniel J., et al. "High-speed high-security signatures." International Workshop on Cryptographic Hardware and Embedded Systems. Springer, Berlin, Heidelberg, 2011.

[2] Bernstein, Daniel J., et al. "TweetNaCl: A crypto library in 100 tweets." International Conference on Cryptology and Information Security in Latin America. Springer, Cham, 2014.

[3] Bogdanov, Dan. "Foundations and properties of Shamir’s secret sharing scheme research seminar in cryptography." University of Tartu, Institute of Computer Science 1 (2007).

[4] ECDSA: Elliptic curve signatures. ECDSA: Elliptic Curve Signatures - Practical Cryptography for Developers. (n.d.). Retrieved November 30, 2022, from https://cryptobook.nakov.com/digital-signatures/ecdsa-sign-verify-messages

[5] ElGamal encryption. (2022, November 23). In Wikipedia. https://en.wikipedia.org/wiki/ElGamal_encryption

[6] ElGamal, Taher. "A public key cryptosystem and a signature scheme based on discrete logarithms." IEEE transactions on information theory 31.4 (1985): 469-472.

[7] Escudero, Daniel. "An Introduction to Secret-Sharing-Based Secure Multiparty Computation." Cryptology ePrint Archive (2022).

[8] Gennaro, Rosario, and Steven Goldfeder. "Fast multiparty threshold ECDSA with fast trustless setup." Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. 2018.

[9] Gennaro, Rosario, and Steven Goldfeder. "One round threshold ECDSA with identifiable abort." Cryptology ePrint Archive (2020).

[10] Iwamura, Keiichi, and Ahmad Akmal Aminuddin Mohd Kamal. "Fast Secrecy Computation with Multiplication Under the Setting of k < N < 2k-1 using Secret Sharing Scheme." Cryptology ePrint Archive (2019).

[11] Pieprzyk, Josef, Hossein Ghodosi, and Ron Steinfeld. "Multi-Party Computation with Conversion of Secret Sharing." NTU, Singapore, September (2011).

[12] Shingu, Takeshi, Keiichi Iwamura, and Kitahiro Kaneda. "Secrecy Computation without Changing Polynomial Degree in Shamir's (K, N) Secret Sharing Scheme." DCNET. 2016.

[13] Shamir, Adi. "How to share a secret." Communications of the ACM 22.11 (1979): 612-613.