
Digital wallets enable essential applications like encrypted messaging and online banking. However, digital wallets are vulnerable to loss and theft. In this paper, we investigate current wallet standards. We show that multi-signature wallets are an insufficient replacement for classical hierarchical deterministic keychains. We address the usability concern of multi-signature wallets with threshold cryptography. SWORD improves the security of digital wallets by distributing account management across a group of shareholders. In addition to removing a single point of failure, SWORD simplifies the wallet experience by incorporating passwordless authentication. SWORD has been adopted and is used in the open-source Kryptik wallet.

## 1. Introduction

The internet relies on a peer-to-peer connection between computers, but the majority of services we use daily are centralized. While corporations like Chase and Facebook are easy to use, centralized convenience often comes at the cost of privacy and ownership.

Since the development of Bitcoin in 2009, there has been a significant push to make the internet more decentralized. Blockchains like Bitcoin and Ethereum promise to shift power from the few to the many, opening a new frontier of digital exploration.

A few examples of popular blockchain apps are shown below.

- **Augur.** A prediction market for betting on real world events like sports games and election outcomes.
- **Opensea.** A marketplace for digital collectibles.
- **Lens.** A user controlled social media platform. Developers can use a standard interface.
- **AAVE.** Lending and borrowing with over four billion dollars in assets.
- **SIWE.** One click login using an Ethereum account.
- **Uniswap.** A decentralized exchange for digital currencies.
- **IPFS.** Store files on a global network of computers.

Every blockchain application requires a digital wallet that can send and sign transactions. Since 2009, over one hundred million wallets have been created worldwide.

## 2. Wallets Are Hard to protect

One of the best parts of cryptocurrency wallets is the ability to control your own money and data. Unlike traditional banks or third-party services, no third party holds assets on your behalf. However, with great power comes great responsibility.

> Over $85,000,000,000 worth of cryptocurrency has been permanently lost after users have lost access to their wallets.[^1]

Today, holding your own cryptographic keys requires memorizing long mnemonic phrases, trusting third-party custodians, or purchasing complicated hardware wallets. These solutions are insufficient for most internet users looking for a simple way to manage private keys.

## 3. Standard Solutions

Noncustodial wallet management is an open problem, with an inherent tradeoff between security and ease of use. Standard solutions are shown below:

**Multisig Wallets.** A multi-signature wallet requires multiple private keys to authorize transactions.

**Smart Contract Wallets.** Smart contract wallets are just a multisig with extra bells and whistles for recovery and permissions. For example, Argent— a smart contract wallet with over four million accounts— allows ‘guardians’ to replace the account owner and set approvals for value-subtracting transactions.[^2]

**Account Abstraction.** Account abstraction turns every blockchain account into a smart contract wallet.[^3] Account abstraction has not been implemented on major blockchains like Ethereum despite discussion since 2014.

Smart contract wallets have been described as a breakthrough in the security and usability of crypto wallets; However, smart contracts have significant drawbacks, explained below:

- **Network Specific.** Smart contract wallets are implemented as code that runs on a single blockchain. Chain-specific contracts require users to create a separate wallet for each blockchain which is a hassle and a security risk.
- **Time Lag.** Adding guardians or transferring ownership requires a ‘security period’ that can last multiple days.
  No UTXO support. Smart contract wallets require Turing-complete blockchains, so there is no support for transaction-based networks like Bitcoin.
- **Variable fees.** Processing payments requires executing smart contract code, which can vary in cost for each wallet.
- **Upfront cost.** Smart contract wallets require an initial setup fee to pay for the creation of a new contract on the blockchain.

Large companies may benefit from the policies provided by smart contract wallets. However, smart contracts restrict wallets to a single blockchain and prevent users from accessing the benefits provided by a unique public-private key pair.

**Multi-party computation (MPC).** MPC wallets require multiple participants to authorize a transaction. Unlike multi-signature wallets, MPC wallets submit a single signature to the blockchain, reducing transaction fees and enabling interoperability with multiple blockchains.
However, multi-party computation protocols have high computation and communication requirements. The industry standard requires four rounds of online computation or seven rounds of pre-signing computation.[^4] In addition, most user-facing implementations like Coinbase dApp Wallet and Zengo allow a single computer to initiate a signing round.[^5]

> MPC wallets are best suited for institutions that can maintain multiple independent signers.

Multi-party computation also encourages walled gardens. Users are limited to the provider’s ecosystem without access to the wallet seed.

## 4. Wallet Basics

**Random Seeds.** At the core of every wallet is a single seed: a string of randomness. As a seed grows in length, the less likely it is to be guessed by an attacker.

Most wallets use seeds with 256 bits of entropy. In practice, this looks like a long string of ones and zeros, with each character having two distinct possibilities. The number of possible seeds grows exponentially. For example, if a seed has 8 bits of entropy, there are $2^8$ (256) possibilities of what it could be. With 256 bits of entropy, there are 2^256 possible seeds, which is more than the number of atoms in the observable universe.

| **Entropy As an Image**                                                                                                  |
| :----------------------------------------------------------------------------------------------------------------------- |
| ![Entropy as an Image](/blog/entropyAsAnImage.jpg)                                                                       |
| _Entropy is a measure of randomness. The more entropy increases, the less likely a piece of information can be guessed._ |

Seeds are hard to guess and are an ideal source for generating public-private key pairs.

**Deterministic Wallets.** Early Bitcoin clients used a random stash of keys once per transaction. Once the initial supply of keys was exhausted, wallets would invalidate the backup; this made key management complex and insecure.[^6]

Deterministic wallets simplify key management. A single seed can generate an unlimited number of keys. However, most deterministic wallets store keypairs on a single chain. Sharing a deterministic wallet is “all or nothing”: sharing a single key requires sharing all keys.

**Hierarchical Deterministic Wallets.** Hierarchical deterministic wallets are structured as a tree of key pairs. A single master key is stored at the root, and new child keys are derived from a unique derivation path. Each path of the HD tree can be shared without exposing the complete tree.

| **HD Tree**                                                               |
| :------------------------------------------------------------------------ |
| ![Entropy as an Image](/blog/hdtree.jpg)                                  |
| _A tree of HD keypairs. Each branch represents a unique derivation path._ |

> For cryptocurrency wallets, each blockchain has a unique derivation path. The derivation path contains directions to a key’s location within the tree structure.

HD wallets provide several benefits. For example, HD Wallets permit an online shop to accept payments at a new address for each order without giving the server access to the corresponding private keys (required for spending the received funds).

## 5. Secure Wallet Origin Distribution (SWORD)

To secure ownership and privacy across the web, we need a better way to protect asymmetric keys. Fortunately, threshold cryptography provides a neat solution.

> As a quick reminder, threshold cryptography protects information by splitting pieces of a secret between groups.[^7]

Instead of relying on a smart contract with trusted guardians, SWORD distributes shares of an encryption key to a group of shareholders; k of n shares are required to reconstruct the original secret.[^8] The encryption key creates an encrypted version of the wallet. Whenever a user wants to regain access to their wallet, the shares are reassembled, and the wallet is decrypted.

| **SWORD Shareholders**                                                                                                                                                               |
| :----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| ![KSWORD Shareholders](/blog/swordShareholderRing.jpg)                                                                                                                               |
| _Kryptik key management splits a secret encryption key among n shareholders. Each share is represented as a coordinate point. K shares are required to recover the original secret._ |

The Kryptik key management has a number of positive properties:

- **Network Agnostic.** Kryptik is network agnostic. Use any blockchain you want.
- **Quick recovery.** Account recovery takes seconds instead of days. Just log in like you would for any other app. Creating a new shareholder is also fast.
- **Multi-factor Authentication.** Verify ownership of your account with a combination of any standard authentication scheme like 2fa.
- **Predictable Fees.** Transaction verification logic is unmodified and the cost can be hard coded by applications.
- **No setup cost.** No smart contracts need to be created or paid for.

In short, Kryptik key management addresses the complexity, fees, and time delay of smart contract wallets. Furthermore, shareholders can be used for wallet recovery and authentication.

## 6. Challenges

While secret sharing improves the security of online wallets, there are several challenges. Each challenge presents tradeoffs between security and ease of use that must be addressed by Kryptik.

**Ciphertext Storage.** Ciphertext storage presents a tradeoff between security and convenience. By keeping ciphertext on the original device, shareholders function as gatekeepers, releasing shares when specific criteria have been met: for example, when a login link has been clicked, or security questions have been answered. Since the wallet owner is the only one with access to the ciphertext, shareholder collusion will not compromise the wallet. The secret encryption key may be recovered, but decrypting the wallet is impossible without the corresponding ciphertext (held in local storage).

> _Local Storage Drawback_
>
> Wallet recovery is no longer an option if the user's device is lost or stolen.

Cloud storage removes the user's device as a single point of failure. Anyone who has access to the remote database has access to the ciphertext. If the database is a blockchain like Ethereum, then the wallet ciphertext is public and viewable by anyone. In this case, shareholder collusion would compromise the wallet.

> _Cloud Storage Drawback_
>
> K of n shareholders can collude and decipher the public ciphertext.

Permissioned databases like AWS provide an alternative to public storage on a blockchain. Users can upload a copy of the ciphertext to a cloud provider like AWS and benefit from server-side access control. However, each shareholder would need access to the database to retain the benefits of cloud recovery. At this point, the security assumptions become identical to the public model.

| **Local Storage**                                          | **Cloud Storage**                                           |
| ---------------------------------------------------------- | ----------------------------------------------------------- |
| Keeps ciphertext on the same device that generates shares. | Keeps ciphertext on a remote database like AWS or Ethereum. |
| A single copy. Easy to lose.                               | Multiple copies. Hard to lose.                              |
| Recovery requires possession of the device.                | Recovery requires access to the database.                   |

**Denial of shares.** Shareholders may refuse to respond. K of N shares are required to reconstruct the original secret. If more than M-K shareholders refuse to respond, there is no way to reconstruct the original secret.

The wallet owner can keep k shares to avoid the ‘denial of shares’ attack, but this creates a single point of failure. Shares can be stored on separate devices, but there is still the underlying concern of a single person owning k shares.

**False shares.** Malicious shareholders may cheat and submit incorrect shares. Cheating does not compromise wallet security, but it does impair recovery. A single incorrect share is enough to invalidate reconstruction.

In the case of a cheater, the recovery protocol can cycle through k of m submitted shares to obtain a valid subset. Recovery is possible as long as k of m submitted shares are honest.

## Kryptik Implementation Details

Distributed key management is a general tool for sharing secrets online. While several secret sharing implementations— such as SLIP 044— have been proposed, each implementation suffers from various drawbacks that limit usability. SWORD uses encryption and authentication to achieve a better balance of security and usability. Specific design decisions made by SWORD are discussed below.

**Optimal threshold.** SWORD requires two-of-three shares for wallet recovery. An external database manages one share; separate user devices store the remaining shares. The two-of-three threshold provides fault tolerance in case one of the shareholders becomes unresponsive.

| **Shareholder**       | **Purpose**                                                               | **Holds Ciphertext?** |
| --------------------- | ------------------------------------------------------------------------- | --------------------- |
| Primary User Device   | Distributes shares and initiates transactions.                            | Yes                   |
| Secondary User Device | Used for wallet recovery if the external database refuses to respond.     | Yes                   |
| External Database     | Authenticates share requests. Release share if the request is authorized. | No                    |

**Wallet Storage.** Local wallets are held in a software vault. Vaults are locked by default and can only be unlocked with a valid set of shares. The standard vault interface is shown below.

```typescript
interface VaultContents {
  // ciphertext of encrypted seedloop
  seedloopSerlializedCipher: string;
  // version: default is 0
  vaultVersion: number;
  // share of the encryption key
  localShare: string;
  // timestamps stored as...
  // number of milliseconds since the epoch
  lastUnlockTime: number;
  createdTime: number;
  // user id generated by wallet app
  uid: string;
  // if unlock correct, should read "valid"
  check: string;
}
```

**Share Generation.** New vaults are encrypted with a 256-bit encryption key, which is then split into m shares. Shares are created using shamir secret sharing configured with a finite field in $Gf(2^8)$ and 128 bits of padding. Each shareholder receives a single share.

**External Authentication.** An external authentication provider generates a one-time code, which is shared via email. After validation, the code is exchanged with the database for an access token, and the user session begins. No passwords are required.

| **Kryptik Authentication Flow**                                                                                                             |
| :------------------------------------------------------------------------------------------------------------------------------------------ |
| ![Kryptik Authentication Flow](/blog/authenticationFlowPlain.png)                                                                           |
| _The passwordless authentication flow. A one-time code is sent via email. After validation, the user can access the server’s secret share._ |

**Recovery.** When a new user session begins, SWORD retrieves the database share and combines it locally to recover the original encryption secret. The wallet is then decrypted and made available for use. This arrangement results in a strong security scheme, where an attacker must compromise two of three systems to obtain a user’s private seed.

> If the database is unresponsive, a share can be retrieved from the user’s secondary device via a QR code.

**Synchronization.** Initial share distribution requires an exchange of credentials between the user’s primary and secondary devices. The user’s primary device displays two QR codes: one code for the local shamir share and one code for the wallet ciphertext. Both codes are protected from prying eyes by a temporary encryption key only authenticated users can access.

After the QR codes have been scanned and decrypted, an identical vault (with a unique shamir share) is created on the secondary device.

## Conclusion

SWORD uses shamir secret sharing and symmetric encryption to improve wallet security. When implemented in software, SWORD provides users with a simple wallet experience that does not require passwords or smart contracts.

[^1]: Charoenwong, Ben and Bernardi, Mario, A Decade of Cryptocurrency ‘Hacks’: 2011 – 2021 (October 1, 2021). Available at SSRN: https://ssrn.com/abstract=3944435 or http://dx.doi.org/10.2139/ssrn.3944435
[^2]: Argent (2020, October 8). Guardian Approvals. Retrieved January 4, 2023, from https://support.argent.xyz/hc/en-us/articles/360008828238-Guardian-approvals-needed-
[^3]: Ethereum (2021, September 29). EIP-4337: Account Abstraction Using Alt Mempool. Ethereum.org. Retrieved October 7, 2022, from https://eips.ethereum.org/EIPS/eip-4337
[^4]: Canetti, R., Gennaro, R., Goldfeder, S., Makriyannis, N., & Peled, U. (2020). UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts. In CCS 2020 - Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security (pp. 1769-1787). (Proceedings of the ACM Conference on Computer and Communications Security). Association for Computing Machinery. https://doi.org/10.1145/3372297.3423367
[^5]: ZenGo (2018, June 28). Multi-party ECDSA. Github. Retrieved January 11, 2023, from https://github.com/ZenGo-X/multi-party-ecdsa
[^6]: BitcoinWiki (2019, May 23). Deterministic Walet. Retrieved February 15, 2022, from https://en.bitcoinwiki.org/wiki/Deterministic_wallet
[^7]: Alfredo De Santis, Yvo Desmedt, Yair Frankel, Moti Yung: How to share a function securely. STOC 1994: 522-533
[^8]: Adi Shamir. 1979. How to share a secret. Commun. ACM 22, 11 (Nov. 1979), 612–613. https://doi.org/10.1145/359168.359176


Jett Hays

SWORD


The internet relies on a peer-to-peer connection between computers, but the majority of services we use daily are centralized. While corporations like Chase and Facebook are easy to use, centralized convenience often comes at the cost of privacy and ownership.

Since the development of Bitcoin in 2009, there has been a significant push to make the internet more decentralized. Blockchains like Bitcoin and Ethereum promise to shift power from the few to the many, opening a new frontier of digital exploration.

A few examples of popular blockchain apps are shown below.

- **Augur.** A prediction market for betting on real world events like sports games and election outcomes.
- **Opensea.** A marketplace for digital collectibles.
- **Lens.** A user controlled social media platform. Developers can use a standard interface.
- **AAVE.** Lending and borrowing with over four billion dollars in assets.
- **SIWE.** One click login using an Ethereum account.
- **Uniswap.** A decentralized exchange for digital currencies.
- **IPFS.** Store files on a global network of computers.

Every blockchain application requires a digital wallet that can send and sign transactions. Since 2009, over one hundred million wallets have been created worldwide.

> Digital wallets enable essential applications like encrypted messaging and online banking.

## Random Seeds

At the core of every wallet is a single seed: a string of randomness. As a seed grows in length, the less likely it is to be guessed by an attacker.

Most wallets use seeds with 256 bits of entropy. In practice, this looks like a long string of ones and zeros, with each character having two distinct possibilities. The number of possible seeds grows exponentially. For example, if a seed has 8 bits of entropy, there are $2^8$ (256) possibilities of what it could be. With 256 bits of entropy, there are 2^256 possible seeds, which is more than the number of atoms in the observable universe.

| **Entropy As an Image**                                                                                                  |
| :----------------------------------------------------------------------------------------------------------------------- |
| ![Entropy as an Image](/blog/entropyAsAnImage.jpg)                                                                       |
| _Entropy is a measure of randomness. The more entropy increases, the less likely a piece of information can be guessed._ |

Seeds are hard to guess and are an ideal source for generating public-private key pairs.

## Deterministic Wallets

Early Bitcoin clients used a random stash of keys once per transaction. Once the initial supply of keys was exhausted, the backup would be invalidated; this made key management complex and insecure.

Deterministic wallets simplify key management. A single seed can generate an unlimited number of keys. However, most deterministic wallets store keypairs on a single chain. Sharing a deterministic wallet is “all or nothing”: sharing a single key requires sharing all keys.

## Hierarchical Deterministic Wallets

Hierarchical deterministic wallets are structured as a tree of key pairs. A single master key is stored at the root, and fresh child keys are derived from a unique derivation path. Each path of the HD tree can be shared without exposing the complete tree.

| **HD Tree**                                                               |
| :------------------------------------------------------------------------ |
| ![Entropy as an Image](/blog/hdtree.jpg)                                  |
| _A tree of HD keypairs. Each branch represents a unique derivation path._ |

> For cryptocurrency wallets, each blockchain has a unique derivation path. The derivation path contains directions to a key’s location within the tree structure.

HD wallets provide several benefits. For example, HD Wallets permit an online shop to accept payments at a new address for each order without giving the server access to the corresponding private keys (required for spending the received funds).

## Wallets Are Hard to protect

One of the best parts of HD wallets is the ability to control your own money and data. Unlike traditional banks or third-party services, no third party holds assets on your behalf. However, with great power comes great responsibility.

> Over $100,000,000,000 worth of cryptocurrency has been permanently lost after users have lost access to their wallet.

Today, holding your own cryptographic keys requires memorizing long mnemonic phrases, trusting third-party custodians, or purchasing complicated hardware wallets. These solutions are insufficient for most internet users looking for a simple way to manage private keys.

## Standard Solutions

Noncustodial wallet management is an open problem, with an inherent tradeoff between security and ease of use. Standard solutions are shown below.

**Multisig Wallets.** A multi signature wallet requires multiple private keys to authorize transactions.

**Smart Contract Wallets.** Smart contract wallets are just a multisig with extra bells and whistles for recovery and permissions. For example, Argent— a smart contract wallet with over four million accounts— allows ‘guardians’ to replace the account owner and set permissions for value-subtracting transactions.

**Account Abstraction.** Account abstraction turns every blockchain account into a smart contract wallet. Account abstraction has not been implemented on major blockchains like Ethereum despite discussion since 2014.

Account abstraction and smart contract wallets have been described as a breakthrough in the security and usability of crypto wallets; However, smart contracts have significant drawbacks, explained below.

- **Network specific.** Smart contract wallets are implemented as code that runs on a single blockchain. This requires users to create a separate wallet for each blockchain which is a hassle and a security risk.
- **Time lag.** Adding guardians or transferring ownership requires a ‘security period’ that can last multiple days.
- **No UTXO support.** Smart contract wallets require turing-complete blockchains, so there is no support for transduction based networks like Bitcoin.
- **Variable fees.** Processing payments requires executing smart contract code, which can vary in cost for each wallet.
- **Upfront cost.** Smart contract wallets require an initial setup fee to pay for the creation of a new contract on the blockchain.

Large companies may benefit from the policies provided by smart contract wallets. However, smart contracts restrict wallets to a single blockchain and prevent users from accessing the full range of benefits provided by a personal public-private key pair.

## Distributed Key Management

To secure ownership and privacy across the web, we need a different way to back up asymmetric keys. Fortunately, threshold cryptography provides a neat solution. As a quick reminder, threshold cryptography protects information by splitting pieces of a secret between groups.

For the past year, I have been developing an open-source wallet (Kryptik) that uses encryption and secret sharing for authentication and account recovery.

**Kryptik Key Management.** Instead of relying on a smart contract with trusted guardians, Kryptik distributes shares of an encryption key to a group of shareholders; k of n shares are required to reconstruct the original secret. The encryption key creates an encrypted version of the wallet. Whenever a user wants to regain access to their wallet, the shares are reassembled, and the wallet is decrypted.

| **Kryptik Shareholders**                                                                                                                                                             |
| :----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| ![Kryptik Shareholders](/blog/kryptikShareholderRing.jpg)                                                                                                                            |
| _Kryptik key management splits a secret encryption key among n shareholders. Each share is represented as a coordinate point. K shares are required to recover the original secret._ |

The Kryptik key management has a number of positive properties:

- **Network Agnostic.** Kryptik is network agnostic. Use any blockchain you want.
- **Quick recovery.** Account recovery takes seconds instead of days. Just log in like you would for any other app. Creating a new shareholder is also fast.
- **Multi-factor Authentication.** Verify ownership of your account with a combination of any standard authentication scheme like 2fa.
- **Predictable Fees.** Transaction verification logic is unmodified and the cost can be hard coded by applications.
- **No setup cost.** No smart contracts need to be created or paid for.

In short, Kryptik key management addresses the complexity, fees, and time delay of smart contract wallets. Furthermore, shareholders can be used for wallet recovery and authentication.


Digital Wallets


As a statistics and machine learning major at Carnegie Mellon, I have taken many math classes ranging from linear algebra and 3D calculus to probability and number theory. However, one of the most powerful ideas I have learned at CMU requires nothing more than 5th grade math.

## The Problem

Consider this problem. Eleven scientists have access to a nuclear bomb. They wish to lock the bomb in a vault so that the vault can only be opened if six of the scientists are present. How many locks are required?

Each combination of six scientists requires a unique padlock. It can be shown that the minimal solution requires 462 locks and 252 keys.These numbers are impractical and grow exponentially as the number of scientists increases.

Instead of physical padlocks the scientists can use a secret code to lock the vault. But how should the secret code be protected?

The most secure solution would keep the code in a single well guarded location: a human brain, a computer, or a safe. However, this scheme is unreliable: a single misfortune (an untimely death, malfunction, or sabotage) would permanently lock the vault.

Copying the code and stashing it in multiple locations adds redundancy, but increases the risk of a security breach. Many copies offer many opportunities for the secret code to be stolen by attackers.

At its core the problem is this: how can we provide the redundancy of multiple backups without increasing the risk of a security breach? Our first attempts at a solution have all had significant drawbacks:

1. Giving each combination of scientists a padlock is too complex and doesn’t scale beyond a few stakeholders.
2. A single secret code is vulnerable to misfortune. If the code is forgotten or destroyed, the bomb becomes unaccessible.
3. Storing copies of the secret code increases the risk of a security breach.

## Threshold Schemes

Security— from nuclear vaults to online encryption— requires accessing and transferring data without revealing the original secret. Threshold schemes help protect information by splitting pieces of a secret— like the code to a nuclear vault— between a group. Recovering the original secret requires k of the n group members to recombine their shares of the secret.

> Threshold schemes have the following properties:
>
> 1. K or more shares can always always be combined to recover the original secret.
> 2. Knowledge of K-1 shares leaves the secret undetermined— all possible values are equally likely.

It turns out that polynomials are all we need to implement a threshold scheme.

## Polynomials 101

Polynomials are just lines that can be represented as an equation. The degree of a polynomial is the largest exponent. For example, $y=2x^2+10x+4$ is a polynomial of degree two.

| **Example Polynomial**                                                         |
| :----------------------------------------------------------------------------- |
| ![Example Polynomial](/blog/polynomial.png)                                    |
| _A third degree polynomial. Four points are required to reconstruct the line._ |

> In general, each term in a polynomial can be written as $cx^k$ where c is a constant, x is a variable, and k is the exponent.

The following polynomial properties are relevant for threshold schemes:

- Every polynomial line crosses the y-axis exactly once.
- Every x-value corresponds to exactly one point on a line.
- A polynomial of degree k can be reconstructed from k+1 points.

As a final example, consider the polynomial y= x+10. This equation represents a straight line that extends from negative infinity to positive infinity and crosses the y-axis at a height of ten. Since the largest exponent is one, we can recreate the polynomial from any two points along the line. The process of recreating a polynomial from a collection of points is called polynomial interpolation and is used as the foundation for shamir secret sharing.

## Shamir Secret Sharing

In 1979, Adi Shamir proposed a threshold scheme for sharing secrets.

Shamir secret sharing divides data D into n shares, so at least k shares are required to reconstruct D.

At a very high level, shamir secret sharing hides data in a crowd— where the crowd is the infinite amount of numbers along the y-axis. The location of the secret data is given by a polynomial of degree k-1. The polynomial is broken into n shares and distributed among a group. K shares can be used to recover the secret’s location along the y-axis.

To create a k of n threshold scheme, shamir secret sharing uses the following steps.

_Share Creation_

1. Convert data D into a number.
2. Create an equation for an arbitrary polynomial of degree k-1.
3. Randomly select n points (xi, yi) from the polynomial.
4. Distribute each share to members of the group.

_Secret Recovery_

1. Collect at least k points from the group.
2. Use lagrange interpolation to derive a k-1 polynomial.
3. Convert the y-intercept of the polynomial back into the original secret.

## Applications

Threshold schemes like shamir secret sharing are very useful when individuals with conflicting interests— like eleven scientists from different governments— must cooperate. In addition, shamir secret sharing gives the redundancy of copying a secret, while minimizing the risk of a security breach.

There are many uses of shamir secret sharing ranging from passwordless authentication to collaborative signatures. After learning about threshold schemes my sophomore year at CMU, I built a digital wallet that uses shamir secret sharing for authentication and account recovery. Over the past year, the wallet has received support from many foundations showing that sharing secrets online is a critical problem made easier by polynomials.


Secret Sharing: The Power of Polynomials


For the past fifty years, many of the smartest humans on Earth have been building the internet. So far, change has been rapid. Million dollar mainframes have become front-pocket mainstays, iphones are as common as toasters, and conversations that once took weeks and a postage stamp now take milliseconds and an internet connection. Distances are shrinking, opportunities are opening and none of it would be possible without asymmetric cryptography.

## History of a Secret

Humans have been keeping secrets long before the internet. In Rome, Julius Caesar shared secrets by shifting the alphabet three spaces. The ‘Caesar Cipher’ uses the same key to encrypt and decrypt messages and is a form of symmetric cryptography.

In the 1940's, the Germans used symmetric cryptography to share battle plans and war strategy. The [Enigma](https://bletchleypark.org.uk/our-story/enigma/) cipher was eventually broken by a global team of scientists and supercomputers that included Alan Turing and Polish ‘Bombas’. While the Nazi cipher system kept secrets for over two deades, it required daily key lists and top-secret code books. In addition, the Enigma relied on custom machinery that cost millions of dollars to manufacture. The Enigma may have been useful for a national bureaucracy run by the Nazis, but it was completely unusable for regular people.

**Enigma Requirements:**

- Custom Machinery
- Top Secret Codebooks
- Daily Key Lists
- National coordination
- Multiple secure channels

In 1974, Whitfield Diffie and Martin Hellman changed everything. Their new system— [asymmetric cryptography](https://ee.stanford.edu/~hellman/publications/24.pdf)— allowed public keys to be shared with anyone, eliminating the need for custom hardware and code books. With a bit of math and a dash of insight, Diffie and Hillman created a way for peers to share secrets without the burden of bureaucracy. Public key cryptography is now embedded within the fabric of the internet and used by billions people around the world.

## Public Crypto 101

Asymmetric cryptography uses public-private key pairs. The two primary functions of key pairs are encryption and digital signatures.

#### Encryption

Public keys can be shared and are used to encrypt messages, but only those who know the private key can decrypt the incoming message. Encryption helps preserve privacy and draws a strong boundary between what is personal and what is public.

#### Digital Signatures

Private keys can be used to create unique signatures that verify the authenticity of messages. Signatures prove ownership and can be validated by anyone who has access to the sender’s public key.

| Public Key        | Private Key      |
| ----------------- | ---------------- |
| Share with anyone | Keep to yourself |
| Encrypt Message   | Decrypt Message  |
| Verify Signature  | Create Signature |

When combined, public-private key pairs provide ownership and privacy: both of which are essential for interacting online.

## Applications

Public-private key pairs are woven into the fabric of the internet and for good reason: privacy and ownership make the internet a better place to protect value and share ideas. Here are a few examples of applications that use asymmetric cryptography.

- **HTTPS:** HTTPS uses public key encryption to send messages between websites and your browser. HTTPS is essential for sensitive activities like logging into email or your bank account.

- **Signal:** Messaging apps like [Signal](https://signal.org/) use public key encryption to ensure messages stay between you and your intended recipient.

- **Bitcoin:** Blockchains like [Bitcoin](https://bitcoin.org/bitcoin.pdf) use private keys to sign transactions. Public keys are used as payment ‘addresses’.

**Bottom Line:** If you use the internet, you use asymmetric cryptography.

## The Promise

With public-private keys, we can unlock a world where ownership and privacy are the default. Whether you’re nineteen in New York or ninety in New Delhi, you have cryptographic superpowers that were once exclusive to national bureaucracies.
Privacy and ownership in your hands. No third party handcuffs. No misplaced trust. Just verifiable ownership that you control.

## The Problem

Most of us have surrendered our right to online privacy and ownership. We’re back to a permissioned society that relies on third party gatekeepers:

- Google can read your messages, but it's still the most popular email system.

- Facebook has a horrendous privacy track record, but it’s still the most popular social network.

- Blockchains offer a peer-to-peer cash system, but the majority of transfers are between custodial exchanges.

The internet relies on a peer to peer connection between computers. But the majority of services we use everyday are centralized. We surrender our privacy and ownership to corporations, because it’s easy. Because companies like Google, Facebook, and Coinbase offer a tremendous amount of value for free.

As consumers, we have surrendered our keys and the gatekeepers became kings. Our content, our messages, and our value are controlled by someone else with different incentives. When we rely on gatekeepers to manage our online experience, we trust they won’t close the gate. We trust they won’t read our messages. We trust they won’t share our data. We trust, we trust, we trust.

## What if….

But what if we had…

- Private messages by default
- Portable social profiles that we control
- Global money transfers in seconds, for pennies

Asymmetric cryptography has given us the keys to an online kingdom: a world where we control what we share and what we own. But it’s up to us as builders to make this dream a reality. The status quo won’t change until everyone has a public-private key pair that can be used with ease.

If we don’t take action soon, then third party gates will become a cage and we won’t be able to get out, because we let someone else hold our asymmetric keys.


Asymmetric Cryptography


The Kryptik wallet relies on distributed key management. Every Kryptik wallet is encrypted using a random encryption key. The encryption key is then shared between the user's device and a server using two-of-two shamir secret sharing. When a user authenticates, shares are recombined and the wallet is decrypted.

While this system has worked well, there are still open questions to explore. For the next few months, we will be continuing research on distributed key management with the goal of providing users a simple and secure wallet experience. Our primary research questions are shown below.

### Should the wallet seed or encryption key be split into shares?

Right now, wallet seeds are stored in a vault with account metadata. Vaults are locked and the encryption key is split into shamir secret shares. However, splitting and sharing the wallet seed itself may be advantageous when syncing between devices.

### What type of authentication should release the remote share?

There are many valid ways to authenticate with the remote server. Kryptik currently uses passwordless email verification to authenticate users. However, passwords and two factor authentication may be considered for additional security.

### How can the model be extended beyond a two of two threshold scheme?

Shamir secret sharing supports any _k of n_ threshold, where _k-1_ shares provide zero information on the secret. Kryptik currently uses a two of two threshold. We're interested in increasing _n_, and allowing users to store additional shares as backups across their devices.

### What are the implications for social recovery?

Social recovery allows a community to recover wallets that have been lost or stolen. Social recovery is a delicate problem that has yet to be solved, but secret sharing may provide a solution.

### Are there any applications beyond wallets that would benefit from distributed key management?

Wallets are not the only applications that rely on high value secrets. Our research will explore additional domains like identity that would benefit from distributed key management.


SWORD

Digital Wallets

Secret Sharing: The Power of Polynomials

Asymmetric Cryptography

Kryptik Research Questions