Mark
  • Member for 4 years, 9 months
  • Last seen this week
*-LWE equivalent of Diffie-Hellman $g^{x^2}$ vulnerability
Accepted answer
4 votes

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'}...

View answer
Why RLWE is hard or even has a solution?
4 votes

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 ...

View answer
Consequences of P=NP for Authentication
Accepted answer
4 votes

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 ...

View answer
Lattice in Sage: Generate matrix A from a basis S such that AS = 0 (mod q)
Accepted answer
4 votes

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 ...

View answer
Why is the market for cryptographic primitives non-commercialized?
4 votes

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 ...

View answer
SVP algorithms and complexity
Accepted answer
4 votes

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 ...

View answer
Expansion Factors
Accepted answer
4 votes

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 ...

View answer
LWE: Round a continuous Gaussian to a true Discrete Gaussian
4 votes

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, ...

View answer
Is this variant of Diffie-Hellman viable and quantum resilient?
4 votes

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 ...

View answer
Shamir secret sharing with no dealer
Accepted answer
4 votes

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: ...

View answer
Whitebox AES: why not steal the whole whitebox?
Accepted answer
4 votes

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 ...

View answer
What basic knowledge is required to understand SIKE?
Accepted answer
4 votes

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, ...

View answer
Practical examples of Threshold Secret Sharing?
4 votes

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. ...

View answer
Is $f(K, f(K, x))$ a pseudorandom function?
Accepted answer
4 votes

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) ...

View answer
How does the security parameter within a digital locker help prove that it unlocked correctly?
Accepted answer
4 votes

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....

View answer
Do people manually select every integer used in a crypto hash function or are they generated by a computer?
Accepted answer
3 votes

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 ...

View answer
Different secret sharing schemes instead of Shamir's?
3 votes

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 ...

View answer
Functional and security model for SEAL
3 votes

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 ...

View answer
How to generate a random string in Python for a mission-critical application
Accepted answer
3 votes

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 ...

View answer
Proof that (ring-)LWE secret is unique
Accepted answer
3 votes

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 ...

View answer
Why is implementation relevant to timing attacks?
3 votes

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" ...

View answer
generic method/process to construct a cryptosystem based on the Decisional Problem
3 votes

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 &...

View answer
Volume of an NTRU lattice
Accepted answer
3 votes

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 ...

View answer
What is the name of this public key encryption cryptosystem?
3 votes

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$...

View answer
Rigorous practical pseudorandom generators
Accepted answer
3 votes

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 ...

View answer
Error Check in Lattice PQC
3 votes

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 ...

View answer
How expensive would running a practical application on full homomorphic encryption be?
Accepted answer
3 votes

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 ...

View answer
Why NIST insists on post-quantum standardization procedure rather than post-quantum competition?
3 votes

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 ...

View answer
LWE with identity sub-matrix and reused sampled from [MP12]: why is it secure?
Accepted answer
3 votes

As a quick aside, while Hermite refers to the same person, "Hermitian" means something different for matrices than "Hermite Normal Form". HNF is essentially "Row Echelon Form/...

View answer
I need a pathway for studying Lattice-Based Cryptography
3 votes

Katz and Lybushavesky just (yesterday) released a book on lattice based cryptography. My particular copy is still shipping, so I can't mention whether it covers what you are in particular interested ...

View answer