Privacy and a New "Paradoxical" Solution to Digital Signature Security

Based on the paper "A “Paradoxical” Solution to the Signature Problem" by researchers at MIT.
See references for more information

It is impossible to live an efficient life in the technology space without having data stored online in cloud services, email accounts or even online bank accounts. The internet makes using technology extremely useful with all the cloud sharing between devices from desktops to laptops to smart phones. But given this, I feel that privacy is extremely important and I strive to control the security of any data I store online, including using proton mail for no-knowledge encryption in my emails, or manual encryption of files before backing up to google drive.

A new problem being solved in digital security is the signature problem.

The Signature Problem

When communicating digitally over the internet, it is very easy for transmissions to be intercepted which is why encryption is very important and a major focus of militaries and intelligence agencies around the world. Encryption uses secret information on both sides of communication to allow the messages sent online and public information sent alongside the messages to be seen by anyone, but requires the secret information to be read, keeping the messages private. A step beyond this is to add some extra information that lets any receiver of the message to be certain as to who the message came from, this is known as a digital signature.

What makes digital signatures different from encryption is that for encryption, public information with the message should not give any information to attackers. While for digital signatures, public information and the message can allow anyone to verify that the message was indeed sent from the person with the digital signature. What digital signatures must not allow is for the public information to allow attackers to forge the signature on their own messages.

Attacks on Signatures and the "Paradox"

A successful attack on a signature is achieved when the secret information is learnt, enabling the attacker to forge the signature on new messages, or if the attack can create an efficient algorithm that can create an equivalent signature, enabling forgery. The two main attacks to achieve this forgery are brute force attacks and chosen message attacks. Brute forcing is simply guessing and checking the secret information until the guess turns out to be correct. In most cases, the algorithms for encryption and signing are public knowledge, so guessing and checking is easy. This attack can also use the public key as information to help the guessing. The difficulty comes from the length of the private keys. More effective attacks are chosen or known message attacks. These attacks use knowledge of the message to break the signature. These attacks can be more effective in a so called "adaptive chosen message attack", where the attackers can choose a custom message based on the public key and based on previous messages.

The paradox, as the paper explains, is a "folklore" in the cryptography community rather than a mathematically proven paradox. It states that it is impossible for the following two statements to be true at the same time in a signature encryption method:

Forging a signature using public information is equivalent to factoring the private keys.
and
An adaptive chosen message attack does not benefit from knowledge of previously signed messages.

A simplified reason for this paradox is that for a signature scheme designed with a trap-door function that makes reversing the scheme equivalent to factoring the number, an attacker can choose a message that represents a mathematical value such as a square number. When the attacker receive this message once it has been signed, they are significantly closer to finding the secret values which means that forging in not equivalent to factoring with the use of adaptive chose message attacks.

The Solution

What the researchers have done is what they call a claw-free family which is using not one trap door function, but two.

As shown in the diagram above, the functions f₀ and f₁ have directions which represent the trap door functions, where calculating with X or Y inputs is easy, but calculating X or Y from the result ( f₀(x) or f₁(y) ) is very difficult. The added complexity in this model going from one key (X) to two keys (X, Y) and two trap door functions (f₀,f₁), results in attackers who know what the functions are, and who know what the result is, cannot easily find X or Y. More crucially, chosen/known message attacks and attacks using the public keys do not gain an advantage in finding X and Y. This proposes a solution to the paradox where calculating the functions in reverse is as difficult as factoring, and preventing public information, including the content of the messages, from being useful to attackers.

References

"A" paradoxical" solution to the signature problem"
Shafi Goldwasser, Silvio Micali, Ronald L Rivest