Latest Crypto related questions

In asymmetric key cryptography, public key is available to everyone. If an attacker encrypts the message sent by another user then the receiver might receive that message. Then how the security is established in this scenario.

For elliptic curve cryptography, the procedure to find a base point that generates a subgroup with order $n$ is:

1. Calculate the order $N$ of the elliptic curve (using Schoof's)
2. Choose $n$. $n$ must be prime and a divisor of $N$
3. Compute cofactor $h = \frac{N}{n}$
4. Choose a random point $P$ on the curve
5. Compute $G = hP$
6. If $G$ is 0, then go back to step 4. Otherwise, you've found a generator with order

Do the key check values of two-key 3DES keys have a uniform distribution? If not I'm curious as to what the distribution is.

I ask because I want to know how safe it is to use a key's KCV as an identifier for that key. If the distribution is uniform, then I believe that I can calculate the chances of a KCV collision via the birthday problem and use that to decide whether KCVs are a safe ID for my ...

How do we measure the security levels of Post Quantum Cryptographic algorithms such as: NTRU Prime, Saber, Kyber,...that are submited to NIST PQC Standardization Process(Competition) in general?

I read the documentation in the NIST submission package of NTRU Prime but understanding the security levels does seem very complicated for the PQC algorithms unlike the non-PQC ones for which we can ise  ...

When I read about BFV or BGV, they all look similar: they use polynomials from $\mathbb{Z}[X]/X^n+1$ as secret keys/pubic keys, etc.

What is the main difference?

In CGPR (link to paper) Section 3.5, it is mentioned that the cost of prover is $O(|C| \log(|C|))$, given the size of the circuit is $|C|$.

It looks to me that the polynomial degree in the resulting QAP should be $O(|C|)$. Wouldn't the prover cost be $O(|C|)$? Am I missing some steps here?

According to this there are at least 6 "properties" all cryptographically secure hash functions strive to attain:

• Deterministic: the same message always results in the same hash;
• Quick: it is quick to compute the hash value for any given message;
• One-way function: it is infeasible to generate a message from its hash value except by trying all possible messages;
• Avalanche effect: a small change to a messa ...

In this paper, there is a statement in the abstract:

Our construction uses $3n + 0.002n \log(n)$ logical qubits, $0.3n^3 + 0.0005n ^3\log(n)$ Toffolis, and $500n^2 +n^2 \log(n)$ measurement depth to factor n-bit RSA integers.

The title of the paper states that 20.000.000 qubits are used to crack RSA-2048 where this presentation -also refers that paper- includes table in pg.22 that maps RSA-2048 to  ...

From Vitalik Buterin's Blogpost - An approximate introduction to how zk-SNARKs are possible

From the sub-topic "Comparing a polynomial to itself", I understood till here

In other words, any polynomial that equals zero across some set is a (polynomial) multiple of the simplest (lowest-degree) polynomial that equals zero across that same set.

However, I am unable to figure out how he uses that to veri ...

Reading the selected answer to Designing a hash function from first principles rather than depending on heuristics is very insightful.

The section on "nonlinearity" suggests that making every equation involved in the hash function into a linear one means the attacker can easily figure out the implementation of the hash function.

If you try to make a cryptographic hash function that only uses XOR  ...

Is it possible to tell if a point on an elliptic curve is less than half of the curve's order?

If I have a point $ = [a]$ on a curve with prime order q, is there an efficient way to know that $a < q/2$?

I understand that range proofs would work for this, but is there a quicker way? Specifically, I am working with secp256k1, but any advice is greatly appreciated.

I'm using HElib CKKS to do experiments and wondering if it's possible to control the error bound in each basic operation such as multiplication, encoding, and rotation.

I have this question is because I found that it seems the increase of error bound in HElib is faster than the implementation of HEAAN.

Here is the example of checking the error bound after each square operation from HElib:

  // c *= c;
   ...

I've seen the following (alleged) quotation on this site and other places:-

If you can make random numbers, you can have a private conversation.

-Whitfield Diffie.

Yet we (Google & me) can't find an original source for it. Can anyone point me to the original publication/talk/presentation? Or is it just folklore?

According to https://eprint.iacr.org/2011/133.pdf and many other papers, there's an isomorphsim between the space of polynomials and its coefficients. So, at least in the BFV scheme, we can do:

$$p(x) = [a_1, a_2, ..., a_3]$$ $$\phi(p(x)) = [\phi(a_1), \phi(a_2), ..., \phi(a_3)]$$

So applying one operation to the polynomial is the same as applying to all elements, sort of like SIMD works on CPUs. This is ...

If you can hash a value one way, why can’t you reverse the hash, turning the hash into one of the many possible inputs, that still gives the same hash?