Mark
  • Member for 4 years, 9 months
  • Last seen this week
Encryption that purposefully take hours to decrypt
Accepted answer
40 votes

Time-lock puzzles appear to be what you want (see for example this). A basic construction is via "Repeated Squaring in the RSA group". Let $p,q$ be large primes, and let $N = pq$. The goal is, for ...

View answer
How can I force slow decryption in the browser?
Accepted answer
32 votes

As I indicated in the comments, I believe a non-cryptographic solution may be the best for this task, where instead of attempting to measure "10 minutes" by the average amount of time it ...

View answer
Why are finite fields so important in cryptography?
Accepted answer
17 votes

One particularly important topic for this question is that of the encoding size. This comes from the following "trivial fact": For an infinite set $A$, there does not exist some $s\in \...

View answer
Meaning of "Security can be reduced to a problem"
14 votes

You are (mostly) right. Reductions are an algorithmic notion — $P$ reduces to $Q$ if the ability to solve $Q$ allows you to solve $P$. There are many ways to formalize this, but the one that you ...

View answer
Why was the term "discrete" used in discrete logarithm?
13 votes

While I agree completely with poncho's answer, this other viewpoint might be useful. Specifically, I think a better comparison isn't between $\mathbb{Z}_p^*$ and $\mathbb{R}^*$, but with $\mathbb{Z}_p^...

View answer
Clarification of the provable cryptography controversies
Accepted answer
11 votes

In general, that article seems to be referring to the "Another Look At..." line of work. Many of the papers are collated on this website. There are a number of "controversies" you ...

View answer
Why Elliptic Curve Cryptography protocols depend on fixed curves?
8 votes

The reason to not fix a specific curve/group/whatever to work over is if it hurts security, namely if: There are precomputation attacks — an attack that costs $T$ that can be amortized over $n$ users ...

View answer
If OWF were to exist, do we know for sure that one of the candidate OWF would indeed be a OWF?
Accepted answer
8 votes

Yes, you are looking for the notion of a universal one-way function. Rafael Pass/abhi shelat's notes contain a construction on page 49. The construction is "unnatural" in the sense that it ...

View answer
What does the work "An Efficient Quantum Algorithm for Lattice Problems Achieving Subexponential Approximation Factor" mean?
7 votes

One could give a much longer answer to this question (and I would be quite interested in seeing someone like Chris's perspective), but the following two points probably suffice for a non-specialist. ...

View answer
Make a Strong, Easy-to-Remember Password Using Classical Cryptography?
7 votes

If there is no upper bound on the length of the password to be used, the most common suggestion I know to create strong, easily-memorable (for some definition of "easy") password is diceware....

View answer
Why do Problems for Post-Quantum algorithms have to be NP-Hard?
Accepted answer
7 votes

I am unaware of cryptography that is hard solely assuming that $P\neq NP$, so I believe you are misunderstanding something. I know the story best when it comes to lattices, so I'll discuss why ...

View answer
How is R-LWE related to lattice cryptography and homomorphic encryption?
7 votes

While I still think it would be good for you to ask more specific questions, the following might be useful in clearing up your understanding of the underlying hard problems on lattices. I do not see a ...

View answer
Can combining two secure block ciphers be insecure?
7 votes

It depends on what you mean by "a secure block cipher", but under a strong enough definition (which is thought to hold in practice), the answer is "no" for boring reasons. If we ...

View answer
Bits of entropy needed to choose a random element from a list?
7 votes

One can achieve this with a technique called Knuth Yao sampling. It: Allows you to sample from any distribution $X$ of finite support (say where the function $f(i, s) = \text{the }i\text{th bit of }\...

View answer
When is a large semiprime possible to factor?
6 votes

"Trivial" is almost certainly the wrong word for this. A better question is if it is reasonable to efficiently factor. First, it is worth mentioning that your semi-prime is 400 decimal ...

View answer
Why I can't permutate an email and get away with it?
6 votes

It's worth mentioning that permuting things can still leak a lot of information. For example, imagine you see an email with some (small) number of numerals (say 3 or 4), and a symbol such as $. From ...

View answer
Differential privacy guarantees of Gaussian noise, when each coordinate has different sensitivity
Accepted answer
6 votes

I haven't read your full question, but the answer to: Is there an equivalent analytical result where we can add Gaussian noise proportional to each coordinate sensitivity? and (implicitly) Can the ...

View answer
security parameter in lattice cryptography
6 votes

A similar question could be asked about RSA --- why use 2048-bit RSA, and not 80-bit RSA? The answer of course is due to cryptanalytic estimates. In particular, one estimates how difficult the ...

View answer
Mathematical proof or any reference of "Deterministic random bit generator cannot produce more randomness than the randomness of seed"
6 votes

Define the Mutual Information of a pair of random variables. $$I(X; Y) = H(X) - H(X\mid Y)$$ For discrete random variables we hae that $H(X\mid X) = 0$, so: $$I(X; X) = H(X)$$ The Data-Procesing ...

View answer
How to decide if an element is a public key in NTRU encryption scheme?
Accepted answer
5 votes

You can't under a standard assumption known as the "Decisional NTRU Assumption". This is essentially the statement that NTRU public keys are pseudorandom. The following is definition 4.4.4 ...

View answer
How to ethically publish the result in case we prove that P = NP?
5 votes

I'll try to answer what I view to be a much easier question to answer, while still (in my view) capturing the "essence" of the problem. How can one "prove" that they have an ...

View answer
Famous ideal lattices
5 votes

Yes, there are. The following table is taken from this paper of Ducas and van Woerden, although the results are not derived there (in the below, $p$ is an odd prime, and $n, m$ are coprime). \begin{...

View answer
$P \ne NP$: a proof relating complexity theory to block ciphers
5 votes

and the elf model proves a secure block cipher exists It is worth mentioning that lower bounds in computationally limited settings do not "lift" [1] to lower bounds in computationally ...

View answer
Questions regarding the one-wayness and collision-resistance of a hash function based on RSA-like problem
Accepted answer
5 votes

Knowing either $p$ or $q$ is sufficient to recover both of them (as $q = n/p$). So imagine we know all of $p, q$, and $n$. The chinese remainder theorem can be phrased many different ways. In general, ...

View answer
Distribution of the Difference of Uniformly Random Elements
Accepted answer
5 votes

It's worth mentioning that the conditions needed for $f(X_0, X_1)$ to be uniformly random based off the distributions of $X_0, X_1$ are quite mild usually. In particular what you need is: $X_0$ and $...

View answer
Imposibility of bias-resistant coin tossing (Cleve'86) and its connection to modern notion of fairness in Secure Multiparty Computation
5 votes

First, I'll discuss Cleve's result really quickly, as there's a natural generalization of it which may be useful for your understanding. Let $X\sim\mathcal{D}$ be some random variable. A common notion ...

View answer
What does it mean for a number to be “in the order of” a prime number?
5 votes

You are (slightly) misreading the statements. I've checked through all 13 occurrences of the word "order" in that paper, and see only "typical" statements, such as: Let $\mathbb{G}$ be a group of ...

View answer
What is the fastest way to check whether a given vector is the shortest in a lattice?
4 votes

The standard way that SVP is formalized is such that what you ask isn't really relevant to showing $SVP\in\mathsf{NP}$. The typical formalization of SVP is (for an arbitrary norm $\lVert\cdot\rVert$ ...

View answer
LWE and pseudorandom functions
Accepted answer
4 votes

You can. There is a certain caveat that should be mentioned here --- the LWE problems hardness is controlled (in part) by the size of the modulus $q$. Two important parameter regimes are $q$ being ...

View answer
Prove: If there exist strong OWFs then there exist weak OWFs that aren't strong
Accepted answer
4 votes

Two things: Yes, $x_1$ is the first bit. The idea is that if $x_1 = 0$ (which occurs with probability 1/2), it is simple to find a preimage of $g(x) = 0$ --- any string $x'$ with $x'_1 = 0$ will ...

View answer
1
2 3 4 5 6