status

Understanding One-Shot Signatures

Published 19.1.2024

In 2020, the IOG team published the work One-shot Signatures and Applications to Hybrid Quantum/Classical Authentication. The work went unnoticed. It was known only in the Cardano community. The Ethereum team recently came across this work and is excited about it. A collaborative workshop between the University of Edinburgh, IOG, and the Ethereum team is planned. One-shot signatures bring advanced cryptography to better secure the functioning of the blockchain. In addition, it allows the creation of such things as blockchain-less cryptocurrency. In the article, we will explain the basic principles of one-shot signatures.

Hybrid System

The one-shot signatures scheme is a hybrid system that combines principles from quantum mechanics with classical communication methods.

Classical communication methods include traditional internet technologies for transferring data (protocols) and classical cryptographic schemes, such as public key cryptography.

So, while the system allows for local quantum operations (more details later), the actual transmission of information is done using these classical methods. This approach allows for the implementation of quantum principles in a way that is compatible with existing technologies.

The system utilizes the quantum no-cloning principle, which is a fundamental postulate of quantum mechanics stating that it is impossible to create an identical copy of an arbitrary unknown quantum state.

This principle ensures that once a secret key is used, it cannot be cloned or reused. This is a key aspect of the security provided by one-shot signatures. Any secret key can be used to sign only a single message. Then the key self-destructs. This cannot be achieved in classical cryptography.

In classical cryptography, the owner of the secret key (private key) can sign as many messages as he wants. There is no way to prevent multiple messages from being signed (a possible mitigation can be achieved through some system of counters and timestamps defining the order of messages) or to prevent key sharing between multiple people.

The one-shot signatures system is a kind of mathematical system that incorporates principles from quantum mechanics to provide enhanced security features. But it’s also a hybrid system that combines these quantum principles with classical communication methods.

Understanding Quantum No-cloning Principle

I have no ambition to explain quantum mechanics in detail. Fortunately, you only need to understand the quantum no-cloning principle. The one-shot signatures system uses the principle but implements it through classical methods.

Let's explain the quantum no-cloning principle with a simple example.

Imagine you have a magical box that can create a unique kind of candy every time you open it. Each candy has a special flavor that you've never tasted before.

Now, suppose you really liked one of the candies and wanted to make an exact copy of it.

In the world of quantum mechanics, this is like trying to clone a quantum state. But here's the catch: the 'no-cloning principle' says that you can't make an exact copy of that candy. No matter how hard you try, you can't recreate the exact same flavor again.

In the context of one-shot signatures, this principle is used to ensure that once a secret key (think of it as the special candy) is used, it cannot be copied or used again. This makes the system very secure because no one else can recreate your special candy (or secret key).

In the image below, each key in the magical box is unique (non-clonable).

In the candy analogy, the 'magical box' can be thought of as a quantum system, and the creation of a unique kind of candy can be seen as a local quantum operation.

As you will see later, the local quantum operation is part of the process during the interaction between the participants.

In real quantum systems, a local quantum operation could be something like preparing a quantum state or performing a measurement on a part of the system. These operations are 'local' because they're performed on individual parts of the quantum system, independently of other parts.

For example, imagine you have two magical boxes (two parts of a quantum system). You could open one box to create a candy (perform a local quantum operation), without affecting the other box at all. This is what we mean by 'local' in local quantum operations.

In the context of quantum cryptography, these local quantum operations are used to manipulate quantum information, such as the secret keys used in one-shot signatures.

Using A One-shot Signatures System

I will show you an example that best demonstrates the power of the one-shot signatures system, as it enables an interaction between Alice and Bob that is unattainable through classical cryptography.

Consider the task of signature delegation. Alice wishes to allow Bob to sign a single message on her behalf. Carol has the public key to verify the message.

Alice could just give Bob her secret key, but this would allow Bob to sign any number of messages.

In the image below, you can see how the scenario would look using classic cryptography. Alice would share the secret key with the Bot. Bob could sign the message. Carol would use the verification (public) key to verify the authenticity of the message.

Alice instead wants to give Bob enough information to ensure that Bob can subsequently sign a single arbitrary message, without any further action on Alice's part. Crucially, we want the message to only be decided after Alice hands this information to Bob.

Of course, as shown above, this task is impossible in a purely classical world, as Bob can re-use whatever information he learned from Alice. In traditional public key cryptography, a single private key can be used to sign multiple messages.

One could hope that Alice could provide Bob with a quantum signing token, which self-destructs after signing a message. By quantum no-cloning (which says that general unknown quantum states cannot be copied) Bob cannot copy the token, and therefore can only sign a single message.

In the picture, you can see that Alice creates a quantum token that she sends to Bob. Bob can sign only one message using the token. The token is subsequently self-destructed. Bob cannot sign another message.

Note that Alice must be able to pass the cryptographic secret to Bob in a specific way. Bob must not be able to clone cryptographic secrets. He can only use it once, i.e. perform a one-shot signature of the message. A quantum signing token was used to pass the cryptographic secret.

Alice can create a secret key (which is represented by a quantum state) and pass it to Bob. This secret key can then be used by Bob to sign a single message on Alice's behalf.

However, it's important to note that neither Alice nor Bob can know the exact value of the key.

This is due to the quantum no-cloning principle, which states that it is impossible to create an exact copy of an arbitrary unknown quantum state.

So, while Alice and Bob can use the key for signing and verifying messages, they cannot see or clone the key.

Once Bob uses the secret key to sign a message, the key self-destructs and cannot be used again. This ensures the security of the system, as it prevents any potential misuse of the secret key.

This is the essence of the innovation brought by the one-shot signatures system.

We will return to this scenario later when we explain local quantum operations.

Interaction between Alice and Bob

With one-shot signatures, it’s possible that the same public key could be associated with multiple private keys, each of which can be used once for signing.

However, the specifics of how the public and private keys are generated and used would depend on the particular implementation of the one-shot signatures system.

For concrete use cases, it may be important to ensure that participants are limited in their ability to produce new cryptographic secrets (for example, quantum tokens). The effect could be similar to reusing the same private key over and over again.

Generally, in cryptographic systems, mechanisms are put in place to ensure the integrity and authenticity of the signatures. These mechanisms could include the use of timestamps, sequence numbers, or other forms of record-keeping that track the usage of the secret keys.

As explained in the introduction, the one-shot signatures scheme is a hybrid system using the principle of quantum mechanics, but fully implemented through classical cryptographic schemes (and using internet protocols to allow communication between participants).

Classical cryptographic schemes refer to traditional methods of encrypting and decrypting information, such as symmetric key algorithms (where the same key is used for encryption and decryption) and asymmetric key algorithms (where different keys are used for encryption and decryption).

Classical cryptography is used to perform local quantum operations.

The interaction between Alice and Bob is fully implemented using classic methods. However, a key part of the interaction process is the creation (emulation) of the quantum state.

Local quantum operation refers to quantum operations that are performed locally, i.e., on individual parts of the quantum system, as part of the one-shot signature scheme.

In a typical scenario, one party performs a local quantum operation on their part of the quantum system. The results of this operation are then communicated to the other party using classical communication. Based on this information, the second party may then perform their local quantum operation.

In the one-shot signatures system, the parties manipulate and exchange quantum information. They perform local quantum operations as part of the signature scheme, with the results being communicated classically.

Here's a simplified step-by-step process:

  1. The sender performs a local quantum operation on their part of the quantum system. This operation could involve preparing a quantum state or performing a measurement.
  2. The sender then communicates the result of this operation to the receiver using classical communication.
  3. Upon receiving this information, the receiver can then perform their own local quantum operation. This operation could be conditioned on the information received from the sender.
  4. The receiver's operation could involve verifying the sender's message, decoding information, or performing some other task relevant to the protocol.

Non-clonable Keys

The concept of non-clonable keys in quantum cryptography is closely related to the no-cloning theorem in quantum mechanics.

This means that once a quantum state (which could represent a secret key) is used, it cannot be cloned or copied. This provides a fundamental level of security, as it prevents any potential eavesdropper from making a copy of the quantum state and thereby gaining access to the secret key.

Let's now return to the scenario from the beginning of the article when Alice wanted to delegate to Bob the right to sign a message on her behalf. We will explain how a quantum signing token is created.

Alice can create a secret key (which is represented by a quantum state) and pass it to Bob. This secret key can then be used by Bob to sign a single message on Alice's behalf.

Recall that neither participant knows the value of the key.

Once Bob uses the secret key to sign a message, the quantum state is no longer valid for further use. Thus, it is not possible to make a copy.

In quantum terminology, it is said that the quantum state 'collapses' when a measurement is made. The act of using the secret key to sign a message can be thought of as a kind of measurement, causing the quantum state to collapse. After this collapse, the quantum state (i.e., the secret key) cannot be used again.

Now let's go through the scenario step by step. We will show how a secret key is created and subsequently self-destructed.

Alice performs a local quantum operation (quantum state X) during which the private key X is created. Alice sends the key X to Bob in a quantum signing token (a box that protects the value of the key X).

Bob performs a local quantum operation (quantum state Y) during which the message is signed. The input for this operation is a quantum signing token containing a private key X. The output of the operation is a message signed by private key X. The message signature initializes the collapse of the quantum state.

At the moment when Bob signs the message with the private key X, the quantum state X collapses, i.e. also the private key X self-destructs.

At this point in the scenario, it is not possible to clone the private key X or use it again. No one has ever known its value and will never know. The result is a signed message.

I hope you now understand the concept of non-clonable keys.

Conclusion

One-shot signatures have numerous applications including one-time signature tokens (our example), quantum money, decentralized blockchain-less cryptocurrency, signature schemes with unclonable secret keys, non-interactive certifiable min-entropy, and more. The one-shot signatures system is a powerful new building block for novel quantum cryptographic protocols.

The IOG team created one-shot signatures to improve the security of Cardano. The system can help prevent long-range attacks in PoS networks by ensuring that any secret key can be used to sign only a single block and then self-destruct. Cardano can provide stronger security guarantees by replacing the KES mechanism with one-shot signatures. An adversary cannot use old secret keys to rewrite the full history of the blockchain because these keys will not exist after signing the blocks. This effectively prevents long-range attacks and enhances the security of PoS networks. We will talk about this in more detail next time.

Featured:

Related articles

Did you enjoy this article? Other great articles by the same author