Hot answers tagged


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.


Yes, these are public parameters of the system. Note that NTRU is not implemented exactly this way any more. The most up-to-date current spec is EESS#1, which can be obtained from


I guess you are taking this information from this document. In Section 2.1 you can see a table with different sizes. In particular, a plaintext block (that is, an encoded message) has size $(n-k) \log_2 p$ bits, while a ciphertext has size $n \log_2 q$ bits. The explanation is simple: ciphertexts are actually polynomials of $n$ terms (since degree is $n-1$)...


I do not have enough high reputation to comment so I am writing here. I have also looked at the paper so I would like to share my thoughts. I think that in order to understand whether the bit is in the "plain sight" one has to ask the question: Is it possible to recover the bit $y$ from the cipher $$g=y\oplus \bigoplus _{i=1}^{\alpha}\bigoplus_{a=1}^{\beta}{...


Blockchains seem to be a common buzzword these days. And more often than not it is used by people, who don't understand the actual concept in detail. For example, that blockchains are based on assumptions about the distribution of processing power. And when you use it outside the context of bitcoins, you still need an incentive for many people to contribute, ...


I would just like to know on what basis they can say it is PQC without any NP problem reduction. I believe that the point you're making is assuming that a Quantum Computer could solve any problem in NP that's not actually NP-complete quickly (or, at least, in polynomial time). That's not known to be true; Quantum Computers would be able to solve some ...

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