Hot answers tagged

17

Yes. The McEliece cryptosystem using Binary Goppa codes has withstood cryptanalysis to date. Its hardness is based on decoding. I should note that it has been broken for certain classes of codes. Another common example is the Merkle-Hellman knapsack cryptosystem. Unfortunately it was broken. It is likely possible to build a secure cryptosystem based on the ...


11

In addition to McEliece (already mentioned by Mike), there's also Hash Based Signatures (such as this one); these are signature algorithms that is based only on some security assumptions of a hash function (and typical hash functions as about as far from numeric-theoretical problems as you can get)


4

There are known impossibility results regarding basis public-key cryptography on NP-complete problems. In this paper by Goldreich and Goldwasser they show that under common types of reductions, it is not possible to base public-key cryptography on NP-hardness.


3

This is only useful as a thought exercise, but Alice and Bob can do key exchange based only on the strength of AES or some other private cipher: Assumptions: doing $2^{40}$ operations will take "a while" but is doable; $2^{80}$ operations is out of the realm of possibility in a century. Alice can publish arbritary amounts of information which cannot be ...


1

I am currently looking at “A SAT-based Public Key Cryptography Scheme” (PDF) where it is proposed a Public Key Cryptography Scheme based in Boolean Satisfiability Problem which is NP-complete. It seems pretty interesting and the autor also provides an implementation at GitHub. The public key is a SAT formula satisfied by the private key.


1

Let $c_a$ be the encrypted version of $a$, and $c_b$ be the encrypted version of $b$. What you want to compute is $c_c$ which is the encrypted version of $a-b$, so that when you decrypt $c_c$ you get $c=a-b$. Paillier supports a homomomorphic addtion of ciphertexts to get an encrypted version of the sum. The actual mathematical operation it takes to get ...


1

What you're missing is the fact that your $c$ value can get waaay beyond what the library is expecting there and thus issues an error which can be read as "your value is too large". The solution is simple: Reduce the multiplication result $\bmod N^2$, where $N=pq$ is the actual value of your modulus. The code-line which you would need to add there would ...


1

No, there is no checksum built-in to the RSA keys per se. There is no need for that. Does this breaks the key ? Or changes the key internally, without breaking it ? [EDIT] It was rightfully pointed out to me that at least one of the statements I typed (in haste) was plain wrong. Now that the answer has served its initial purpose, I've removed my ...


1

You can send the public key certificate as an attachment with the email or you can send the public key certificate in a separate email. The main point is the end-user should receive the public key for verification. A certificate can be a file e.g. *.cer . The end user needs to have a program to verify the document. UPDATE: Chances of an MIM attack or ...



Only top voted, non community-wiki answers of a minimum length are eligible