Given $(A, Ax + e)$ and $(A, x^tA+e')$, you can do (at least) one potentially interesting thing to solve LWE. Namely, compute the sample (A+ A^t, Ax + e + (x^tA+e')^t) = (A+A^t, (A + A^t)x + e + {e'}...

There are two key points that you are mentioning (one mentioned by Poncho in the comments --- I repeat here for exposition purposes). The RLWE errors $e_i(x)$ are small, and the secret $s(x)$ is ...

I'll try to answer what I believe to be what you are asking, namely: If $P = NP$, can one "fix" cryptography by replacing constructions with interactive protocols? This is a natural enough ...

Yes, this is relatively straightforward. First, it seems that Sage has this built-in (see the dual flag, although I didn't test it). I'll describe the "mathematical" way to proceed, as I ...

It is worth mentioning that people do try to patent some cryptographic primitives, with certain upsides/downsides for adoption. For example, in the ongoing NIST PQC standardization, the Round5 ...

Lattice-based cryptography is based on the hardness of certain lattice problems (almost tautologically). The region marked "crypto" denotes the region of approximation factors $\gamma$ such ...

I encourage you to read section 3.1 of Generalized Compact Knapsacks are Collision Resistant, where it is first defined. The answers to your questions are: I can find information for the factor in ...

Out of curiosity, what is the current state of the art on the sampling over $D_{\mathbb{Z},\alpha q}$ This is a fairly involved question to answer. There are a number of competing ways to sample it, ...

Just a quick comment on: Is the $\bmod 1$ calculation as described a known one-way/symmetrical function, and is it used elsewhere? fgrieu mentions in his answer: Modular reduction modulo an integer ...

I think this can be done relatively simply with any additive secret sharing scheme (which Shamir's scheme is). The basic idea behind the scheme (to make a $(n, k)$ no-dealer secret sharing scheme) is: ...

This is answered in the Whitebox AES paper. I've quoted the relevant section, which occurs on the second page: A natural question is: if an attacker has access to executing decryption soft-ware ...

Craig Costello has tried writing precisely what you're interested in, see SIKE for Beginners. It refers to numerous other surveys for isogeny-based crypto which may be useful (lecture notes by De Feo, ...

NIST has recently been exploring standardizing various threshold cryptographic primitives. The relevant webpage is here. I imagine that page would be useful for exploring real-world use cases of it. ...

I'm responding to: "If the oracle accessed by B is truly random, how to prove the oracle B constructs for A is truly random, too?" I'd like to know if a solution to (or a construction which avoids) ...

They mention $H(nonce, key)$ is modeled as a random oracle. Then, $H(nonce, key) \oplus M\cong U\oplus M$ where $U$ is uniformly random, so the encryption scheme (essentially) becomes the one time pad....

Generally no. In cryptography, the appearance of "random" strings of numbers is generally quite suspect --- what if there are certain "weak" choices of numbers that yield the ...

You shouldn't think of secret sharing as being (directly) related to polynomials, and instead should see it as being directly related to (usually linear) codes, which are generally related to ...

decryptions of Microsoft SEAL ciphertexts should be treated as private information only available to the secret key owner, as sharing decryptions of ciphertexts may in some cases lead to leaking the ...

the Random module uses a cryptographically insecure PRG (Mersenne Twister). You want the Secrets module (documentation here), which uses urandom on Linux, or CryptGenRandom() on Windows. In fact, I ...

Regev's LWE Survey contains a sketch of the proof. Algorithms. One naive way to solve LWE is through a maximum likelihood algorithm. Assume for simplicity that $q$ is polynomial and that the error ...

This should be a (long) comment, but I do not have space. It is meant to explain why the idea of letting the attacker choose the underlying implementation is too strong --- it "trivially" ...

No. Not only is there not a generic way to build a cryptosystem based on the decision problem, there isn't a single known decision problem that: is NP-Complete, and we can build cryptography from &...

This is a standard computation in number theory. The idea behind it is that the matrix you have written down is a basis of the lattice as an $\mathcal{O}_K$-module, but to find the volume you first ...

You are describing what you might call an "exact GCD" scheme. It is insecure (as discussed in the comments), and I believe the suggested modification to make it secure (add a single error $e$...

It is worth mentioning that there is a connection in complexity theory often called "Hardness v Pseudorandomness" that makes this question somewhat difficult. It may not be surprising that ...

Error-correction occurs within lattices in roughly two forms: Binary error-correction is sometimes used within lattice-based protocols, although not all of the time. There are certain issues with ...

This will likely be rather expensive. This is because the problem you describe seems like it would be hard to express as a shallow arithmetic circuit, which is a rough estimate of how difficult the ...

I don't know if I can comment authoritatively (I did not notice the difference in verbiage), but the NIST PQC process has been roughly the same format as the AES competition. Namely, an open call for ...