Practical hierarchical threshold cryptosystem without a trusted dealer, with offline distributed signatures and decryption, plus zero-knowledge proofs.

Introduction

A cryptosystem is an implementation of an algorithm for encrypting and decrypting data, such as an email, image, video stream or other document. The simplest are symmetric cryptosystems, in which a single key is used to both encrypt and decrypt messages. This means that both the sender (Alice) and the recipient (Bob) need to know the key. Alice would have to send the key to Bob, with the danger that it would be intercepted. Public key systems, such as RSA, have two keys, a public one for encryption and for verifying signatures, and a secret one for decryption and signing. Alice generates the public key from the private one with a method that is not reversible. She can make the public key known to anyone who wants to send her a message, safe in the knowledge that only she can decrypt the message or sign documents.

In a threshold system, each party has their own part of the secret key, which is not shared. These are used to generate the public key. Decrypting a message requires a minimum number of private keys – the threshold. Thus, a message can be read only if enough parties agree. Moreover, since not all the parts of the private key are required, it does not matter if one is unavailable, so there is no single point of failure. However, existing threshold cryptosystems rely on a single, centralised, trusted entity to generate the keys and distribute them to each party. This entity, denoted as the trusted dealer, can cancel party equality and can become a single point of failure.

In this new cryptosystem, each party choses random numbers that are used to generate the keys. These are distributed in such a way that that the full private key is neither shared nor created. No trusted dealer is required, nor does the algorithm allow one to be established. Hence, this new cryptosystem uses a distributed method of creating and sharing the keys without a trusted dealer. When decrypting a message or signing a document, each party does part of the work. The embedded zero-knowledge proof can be used to prove that a partially decrypted or signed message has not been tampered with. Moreover, the keys can be shared with another group of parties with a different threshold, if the minimum number of secret key holders agree.

Possible applications

Here a few examples of how this cryptosystem could be used in a real application.

• It could be used in a blockchain, in which blocks contain a public key and partial signatures for documents. Anyone who has access to the document and the blockchain can construct a valid signature from the blockchain. The zero-knowledge proof allows anyone to prove that no part of the signature has been tampered with.

• The system can be used in real-life commercial scenarios that require a hierarchical access structure for data, such as where the parties differ in their authority or level of confidence. For example, it can be set up so that the data can be decrypted only by: (1) a single high-level party, (2) two mid-level parties or (3) several low-level parties. Another example would be a document that has to signed by employees at different levels or departments, for example, signing off a repair to a critical component or a financial transaction that has to signed by three employees, one of whom must be a department manager.

• It could be used to implement end-to-end encryption for group messages and voice or video calls, such as those used by instant messaging services like WhatsApp and Telegram. End-to-end encryption means that the message is encrypted on the sender’s device and decrypted only by the recipient’s device, so that all intermediate servers have only the encrypted version. Thus, the cryptosystem could be used to share important data between different parties. It would be decrypted only if the threshold number of recipients have the encrypted message and have exchanged partially decrypted messages.

• A digital signature is a digital analogue of a pen-and-ink signature on a physical document. A digital document is signed with private keys and anyone can use the public key to see that it has been authorised. Legal entities, such as businesses and other organisations, could each have their own keys. The cryptosystem would then allow a majority of them to sign important documents, for example, if there is no clear arbitrator. Alternatively, an encrypted document could be decrypted only if the majority agrees.

• It could be used to store votes cast in an election. A ballot paper would be encrypted when someone votes, so nobody can see which way the election is going until the votes are decrypted. Each candidate or observer would have a key, and decryption would be possible only if the majority of them agree. Thus, no single candidate can prevent decryption.

Interesting?

Right now, we’re on the finish line to bringing this cryptosystem to the world in the way to use inside any native, JVM or JS applications.

Anyway, please contact us at hello@kcry.pt if you want to test it today or learn more. Or you can subscribe to our newsletter to stay tuned.