Bitcoin Forum

Hi - looking for a bit of tech help

Pre-conditions:

1. Alice has encrypted the text "red" with her private key, and stores the ciphertext on a public ledger.
2. Her public key is known.
3. Bob knows that Alice has stored a ciphertext corresponding with either "red" or "white" on the ledger.

My Question:

Using the public key, the ciphertext, and knowing the possible cleartext values, is it possible for Bob to determine the value which has been stored?

To put the question another way: If required could Alice prove that the cleartext value is "Red" without using her private key?

First of all, encryption is done with the public key while decryption is done with the private key.

Depending on the algorithm used, yes it may be possible. Most modern algorithms introduce randomness into the encryption so that others cannot know that the same message was sent twice. With those algorithms, encrypting the same message will result in different ciphertexts. However, for algorithms that don't have that randomness, then encrypting the same message with the same public key will result in the same ciphertext. Bob can then encrypt using Alice's public keys the possible cleartext values and compare them to the ciphertext. If they match, then he has found the right cleartext.

So long as she used an algorithm which produces the same ciphertext with the same plaintext, then yes. Otherwise, no.

Private keys are used for decrypting. So she could simply prove it by using her public (known) key to encrypt "red". Because the resulting ciphertext is the same as what she wants to prove to contain " red ", she provided a valid proof.

.edit:
knightdk was faster :)
The random thingy would in fact invalidate my statement.

What you're talking about is Asymmetric Key Crypto. The basic idea behind CA's and what-not.

Just to be clear. Public key is public, and can be distributed without fear of data theft/MiTM (Man in The Middle) attacks such as sniffing etc. Hence the word 'public' in the name! :) The purpose of the public key is to allow others to use it, and encrypt the data that they wish to send you. Again, to prevent the data being read by a 3rd party. Your private key, is the only key in the whole wide world that can be used to decrypt the data your friend sends you.

Another interesting thing that knightdk mentioned is this:

http://travistidwell.com/jsencrypt/demo/ (http://travistidwell.com/jsencrypt/demo/)

Try typing in the same text and encrypt it multiple times. Each time, the encrypted version is different, even though the plaintext you fed it is the same! :) The reason? They take in a couple of other factors along with your private key and plaintext to increase entropy. There was this website that would ask you to move your mouse-cursor around randomly on the page as the source of entropy. Wish I could link it to you! :)

Super T,

Instead of encryption, how about this...

Alice uses a private key and a digital signature algorithm to generate a signature of the text "red".

Anyone that is presented with her associated public key, the clear text "red", and the signature can verify that the signature was generated with her private key (even though they don't know her private key).  Therefore, as long as Alice keeps her private key secure, it can be determined that the signature was created by Alice and nobody else.

Now, instead of making the signature public, the signature and the text "red" are concatenated together with a delimiter.  The concatenated result is now hashed using the SHA-256 hash algorithm, and the resulting hash is made public.

Given only the hash and the public key, it is not possible for anyone to determine what the signature or signed text are.

Now, if required, Alice can prove that the cleartext value is "Red" by providing the text and the signature.

Anyone can then concatenate the signature and cleartext word with the appropriate delimiter.  They can calculate SHA-256 on the concatenated result and verify that they get the previously published output.  They can then use the public key to verify that the signature is valid for the word "red".

If Bob already knows that the word was either "red" or "white", then Alice only needs to supply the signature for Bob to check both words against the hash value and validate the signature (assuming he already has the hash value and public key to start with).

Thank you all.

@Danny you've given me food for thought...