This week, we have kicked off our research from the Privacy transition of Ethereum, starting from the concept of Stealth Address.

Why We Start from Stealth Address

In Vitalik's recent "3 transitions" post, he highlighted "As Ethereum transitions from a young experimental technology into a mature tech stack that is capable of actually bringing an open, global and permissionless experience to average users…The privacy transition - making sure privacy-preserving funds transfers are available, and making sure all of the other gadgets that are being developed (social recovery, identity, reputation) are privacy-preserving"

He further illustrated the idea of Stealth Address with a more detailed post and ERC-5564 associated with it. However, this is not the first time that Stealth Address was proposed. Let's start from a literature review.

A Literature Review

Research

• 17 April 2011; The most basic Stealth Address (SA) technique was invented by user ‘bytecoin’ in bitcoin forum
  user ‘bytecoin’. Untraceable transactions which can contain a secure message are inevitable. 2011. https://bitcointalk.org/index.php?topic=5965.0
• 2013, Nicolas van Saberhagen in CryptoNote’s white paper. https://www.semanticscholar.org/paper/CryptoNote-v-2.0-Saberhagen/5bafdd891c1459ddfd22d71412d5365de723fb23
• 06 Jan 2014, Peter Todd, [Bitcoin-development] Stealth addresses. 2014. http://www.mailarchive.com/[e-mail]/msg03613.html
• 2017, Robust Multi-Key Stealth Address. Nicolas T. Courtois and Rebekah Mercer, Stealth Address and Key Management Techniques in Blockchain Systems. https://www.scitepress.org/papers/2017/62700/62700.pdf
• 2018, Fan xinxin et al. Faster dual-key stealth address for blockchain-based internet of things systems, With an increasing counter, enabling the protocol user faster parsing. https://arxiv.org/pdf/1806.00951.pdf
• 2019, Fan Jia et al. A new stealth address scheme for blockchain. This is to solve the problem of key length by bilinear maps. https://sci-hub.se/https://dl.acm.org/doi/abs/10.1145/3321408.3321573
• 2019, A lattice based linkable ring signature supporting stealth addresses.
  https://ink.library.smu.edu.sg/cgi/viewcontent.cgi?article=8416&context=sis_research, prevent adversarially-chosen-key attack
• 3 July 2020, Gary Yu, Blockchain Stealth Address Schemes, https://eprint.iacr.org/2020/548.pdf,
• 2021, Mexchange: A privacy-preserving blockchain-based framework for health information exchange using ring signature and stealth address,
• ##2022, Pdksap: Perfected double-key stealth address protocol without temporary key leakage in blockchain. NO DH but peers for no temporary key leakage https://sci-hub.se/https://ieeexplore.ieee.org/document/9209929
• 25 June 2023, BasedSAP. BaseSAP is a fully open and reusable stealth address protocol that can reliably offer stealth addresses at the application layer of programmable blockchains such as Ethereum. e Secp256k1 elliptic curve, stealth address protocols based on elliptic curve pairings or generated using lattice-based cryptography. https://arxiv.org/pdf/2306.14272.pdf

EIP

EIP-5564 https://eips.ethereum.org/EIPS/eip-5564
Toni Wahrstätter (@nerolation), Matt Solomon (@mds1), Ben DiFrancesco (@apbendi), Vitalik Buterin (@vbuterin)

Draft Proposal for Ethereum Research

Introduction

The Stealth Address (SA) prevents the public association of a blockchain transaction's output with a recipient's wallet address, effectively concealing the actual destination address of the transaction. As vitalik highlighted the practical and privacy-preserving implementation of SA in the application layer of programmable blockchains such as Ethereum, we propose a SA protocol with Fully Homomorphic Encryption (FHE) to 1) prevent quantum computing attacks based on Learning with Error (LWE) security assumption; 2) help the receiver outsource the computation of checking the entire chain for stealth addresses containing assets without revealing his view key.

Background

How to provide privacy in the Ethereum ecosystem is a big challenge. Recently, discussions surrounding privacy enhancements have predominantly focused on a particular scenario: the preservation of privacy during transfers, particularly self-transfers, involving ETH and widely used ERC20 tokens. Setalth address provides a privacy protection solution for receivers of cryptocurrencies. It requires the sender to create random one-time addresses for every transaction on behalf of the recipient so that different payments are made to the same payee unlinkable. Nowadays, the most popular SA scheme is the Dual-Key Stealth Address Protocols (Courtois, N. T., & Mercer, R. 2017). However, this scheme is still vulnerable to key leakage attacks and quantum computing attacks. To prevent these attacks, we propose implementing SA into FHE, an application of lattices.
Homomorphic encryption (HE) has been called “Swiss Army knife of cryptography”, since it provides the approach to operate on encrypted data without requiring decryption. It can be categorized into two main types: partially homomorphic encryption and fully homomorphic encryption. Partially homomorphic encryption and fully homomorphic encryption differ in their capabilities to perform computations on encrypted data. Partially homomorphic encryption allows for the evaluation of only specific types of operations, such as either addition or multiplication, while maintaining the ability to decrypt the result. On the other hand, fully homomorphic encryption enables the evaluation of arbitrary computations on encrypted data, including both addition and multiplication operations, without requiring decryption. HE can be extensively utilized across various sectors like healthcare, government, and finance, facilitating secure data analysis and sharing. On the other hand, it poses considerable computational challenges, primarily due to the intricate algebraic operations and the intensive computations associated with ciphertexts.

Proposal

We created a method that relies solely on cryptography using FHE to realize the full privacy protection of stealth address under computing over ciphertext. While the original proposal of SA builds on the dual-key, our approach can help the receiver outsource the computation of checking the entire chain for stealth addresses containing assets without revealing his view key, and prevent quantum computing attacks based on the lattice cryptographic construction that relies on far simpler mathematics than elliptic curve isogenies.

Dual-key Stealth Address Protocol (DKSAP)

DKSA builds on the Diffile-helleman key exchange protocol in elliptic curve. When a sender A would like to send a transaction to a receiver B in stealth mode, DKSAP works as follows:

1. The receiver B has a pair of private/public keys (vB, VB) and (sB, SB), where vB and sB are called B’s ‘scan private key’ and ‘spend private key’, respectively, whereas VB = vBG and SB = sBG are the corresponding public keys. Note that none of VB and SB ever appear in the blockchain and only the sender A and the receiver B know those keys.
2. The sender A generates an ephemeral key pair (rA, RA) with RA = rAG and 0 < rA < n, and sends RA to the receiver B.
3. Both the sender A and the receiver B can perform the ECDH protocol to compute a shared secret: cAB = H(rAvBG) = H(rAVB) = H(vBRA), where H(·) is a cryptographic hash function.
4. The sender A can now generate the destination address of the receiver B to which A should send the payment: TA = cABG + SB. Note that the one-time destination address TA is publicly visible and appears on the blockchain.
5. Depending on whether the wallet is encrypted, the receiver B can compute the same destination address in two different ways: TA = cABG + SB = (cAB + sB)G. The corresponding ephemeral private key is tA = cAB + sB, which can only be computed by the receiver B, thereby enabling B to spend the payment received from A later on.

Fully Hommorphic Encryption

Homomorphic Encryption (HE) refers to a special type of encryption technique that allows computations to be done on encrypted data, without requiring access to a secret (decryption) key. The results of the computations remain encrypted, and can be revealed only by the owner of the secret key. There are additive homomorphism and multiplicative homomorphism as below:
Additive homomorphism:

$$E(m_1)+E(m_2)=E(m_1+m_2)$$
Multiplicative homomorphism:

$$E(m_1)\ast E(m_2)=E(m_1\ast m_2)$$
A homomorphic encryption scheme consists of four procedures, E = ( KeyGen, Encrypt, Decrypt, Evaluate):

• (sk, pk) ← KeyGen (1λ, 1τ ). Takes the security parameter λ and another parameter τ and outputs a secret/public key-pair.
• c ← Encrypt(pk, b). Given the public key and a plaintext bit, outputs a ciphertext.
• b ← Decrypt(sk, c). Given the secret key and a ciphertext, outputs a plaintext bit.
  c ← Evaluate(pk, Π, c ). Takes a public key pk, a circuit Π, a vector of ciphertexts, one for every input bit of Π, and outputs another vector of ciphertexts, one for every output bit of Π.

FHE Dual-key Stealth Address Protocol

Our FHE-DKSAP can be presented as follows:

1. Bob creates two key pairs: (sk2, PK2) and (sk_b, PK_b). The wallet address is generated using sk2, while PK_b is used to encrypt the value of sk2. Bob publicly shares PK2, PK_b, and the ciphertext C2.
2. Alice generates a key pair (sk1, PK1) randomly. She then combines the two public keys, PK1 and PK_b, to obtain PK_z. The stealth address is generated based on PK_z. Finally, Alice encrypts the secret key sk1 using Bob's fully homomorphic encryption (FHE) public key PK_b, resulting in the ciphertext C1.
3. Bob receives the ciphertext C1 and adds two ciphertexts together to get the C. With the additive homomorphism, he can decrypt the ciphertext C with his FHE private key sk_b. The result is the secret key sk_z. Then, he can generate the stealth address with sk_z and decrypt it with the private key, which only bob ones.
   

Conclusion

Motivated by the DKSAP, we propose the FHE-DKSAP to help the receiver outsource the computation of checking the entire chain for stealth addresses containing assets without revealing his view key, and prevent quantum computing attacks.