29
votes
Accepted
What is the progress on the MIT LCS35 Time Capsule Crypto-Puzzle?
2) Has anyone claimed to make any progress with this challenge?
Ah that question I can answer now...
I found the solution on the 15th of April 2019 and sent it to the MIT's CSAIL on the 16th of ...
- 456
13
votes
Accepted
Free Start Collision In SHA-3
NO, you can't !
I will only consider initial_vector_0 and next_block_0.
What you have found is this:
...
- 10k
11
votes
Why not use random world events instead of a proof-of-work algorithm?
A true source of randomness or a Common Reference String (CRS) as it's referred to in cryptography, could potentially be used in some cases in the place of Proof-of-Work, although as forest pointed ...
- 583
11
votes
Accepted
Proof of work designed for CPUs?
CryptoNight, the pow function used by Monero is such a function.
https://monerodocs.org/proof-of-work/cryptonight/
Basically it needs more random memory accesses, and GPU memory is not designed for ...
- 469
8
votes
Memory-hard proof-of-work: are they ASIC-resistant?
Yes, the argument is largely correct. A good memory-hard proof-of-work scheme can be fairly resistant to speedup using ASIC, if designed around a good primitive like Argon2 and parametrized ...
- 144k
7
votes
Accepted
Verifiable delay functions vs Proof of Sequential Work
A typical thing which you cannot do with a proof of sequential work is achieving time-lock encryption. In time lock encryption, you want the user to be able to retrieve the hidden message only after ...
- 20.9k
6
votes
Prove that you have $K$ bytes of memory
There has been a huge amount of work on related questions in the past years. As Thomas Prest mention, this problem was considered for memory-hard function, which provably (in some idealized models) ...
- 20.9k
5
votes
Why not use random world events instead of a proof-of-work algorithm?
You are misunderstanding what a proof-of-work algorithm is designed to accomplish. It's designed to provide an economic disincentive to repeating the process many times (e.g. sending an email or ...
- 15.4k
5
votes
Accepted
Is this simple memory-hard function good?
TL;DR: No, this is not memory-hard and may not even be as computationally intense as you would have thought.
Suppose we have a hash function $H:\{0,1\}^*\to\{0,1\}^n$, for example SHA-256. Now we can ...
- 46.3k
5
votes
P256 seed problem
The curve parameters were generated with $y^2=x^3+ax+H(s)$ with $H$ being SHA-1 and $s$ being the special seed. As the values are generated by passing the seed through SHA-1, it would be difficult to ...
- 15.4k
4
votes
Accepted
Embedding POW in an EC public key
I like the features of the second, except for some drawbacks:
I don't believe the drawbacks are as bad as you think.
1.This reduces the number of valid public keys that exist, and could reduce ...
- 150k
4
votes
"Memory-Hard" vs. "Memory-Bound" Functions?
The Wikipedia definitions are clear;
memory-bound functions;
Memory bound refers to a situation in which the time to complete a given computational problem is decided primarily by the amount of ...
- 49.3k
3
votes
Accepted
Proof of work - 51% attack
Since they're all competing, the hash-power used to create a block in 10 minutes, is 1/4 of the total hashing power.
That's not correct.
If the work effort is set to $n$, that is, it takes an ...
- 150k
3
votes
Accepted
Can/Which encryption algorithms be daisy chained to create a cryptographic computational puzzle?
Taking away the worries
Would the provided "Prefix: " provide a weakness that can be exploited?
No, any secure cipher should be protected against plaintext attacks. To be precise, the ciphertext ...
- 94k
3
votes
Can/Which encryption algorithms be daisy chained to create a cryptographic computational puzzle?
Can encryption algorithms be used daisy chained like this to create a simple computational puzzle…
It can be done, but remember encryption algos are built to be (among other things) fast/speedy while ...
- 18k
3
votes
Prove that you have $K$ bytes of memory
I see at least one way of doing what you want to do: memory-hard functions.
Alice just needs to store a value $m$ and its hash $H(m)$, where $H$ is a memory-hard function and where the parameters are ...
- 1,080
3
votes
Accepted
Reason for squaring and not arbitrary exponentiation in Wesolowski and Pietrzak verifiable delay functions (VDFs)
Suppose I had an enormous exponent $B$. To compute $g^B\mod G$ (I'll omit "mod $ G$" from now on), I would use a square-and-multiply method: I would compute $g$, $g^2$, $g^4$,\dots, $g^{2^t}$...
- 1,212
3
votes
Partial proof of work: an hash function that validates parts of input, insensitive to the rest
If you give me enough information to evaluate $h$ on inputs of my choice, then I can easily check whether $h$ is sensitive to the $i$th bit of input --- just evaluate it on two strings that differ ...
- 14.1k
3
votes
Accepted
Complexity of Hash mining/signing
For a random input. Each bit has probability $\frac{1}{2}$ to be zero.
Then because we suppose independence (ideal hash function implies this assumption). For each input the probability to have $4$ ...
- 2,625
3
votes
Accepted
Why is $\operatorname{Hash}(x \oplus y)$ not a secure proof-of-work algorithm?
The alleged prover can pre-compute a $u$ such that $H(u)$ satisfies the condition of the proof of work.
Given a challenge $x$, the prover can output $x \text{XOR} u$ as the proof thus cheating the ...
- 9,682
3
votes
Accepted
Fischlin vs. Fiat-Shamir Performance
Please check the work here: https://eprint.iacr.org/2024/526
Just quoting the number there, the running time of generating a single discrete log proof on secp256k1 curve on Apple M3 Pro CPU:
Fiat-...
- 46
2
votes
What is the progress on the MIT LCS35 Time Capsule Crypto-Puzzle?
Amazingly enough, the puzzle was solved a few weeks after @TacticalCoder got an answer, on May 10, as described at https://www.cryptophage.com. Their solution worked in 2 months, rather than nearly 4 ...
- 580
2
votes
Can the proof of elasped time (PoET) consensus algorithm be exploited by multiple nodes?
Yes, here's an article stating that "SgxSpectre Attack Can Extract Data from Intel SGX Enclaves".
According to researchers, SgxSpectre works because of specific code
patterns in software ...
- 121
2
votes
Accepted
Anti-spamming hash-based proof-of-work?
I agree with e-sushi that PoW does work, however, the primitives used by HashCash are too friendly for adversaries. As the OP pointed out we need contextually bound challenge and response that cannot ...
- 1,422
2
votes
POW with Linear time to solve it?
I don't think an algorithm like that would exist. For PoW to facilitate a random slot leader for block generation, it has to be necessary that the PoW puzzle is really hard to solve by anyone and that ...
- 447
2
votes
Accepted
Bit-strength of discrete logarithm for a group of integers modulo a safe prime
For a proof of work scheme, you're probably better off making $p$ large enough that you don't have to worry about NFS (e.g. 2048 bits or more), or alternatively, using an elliptic curve group (e.g. ...
- 150k
2
votes
Estimating difficulty of "Memory-Hard Proof-of-Work" based on "size of memory"?
The measure of resource typically used to evaluate memory-hard functions is not the amount of work (i.e., $T$-complexity) but rather the space-time complexity (i.e., $ST$-complexity) of the ...
- 5,428
2
votes
Verifiable delay functions vs Proof of Sequential Work
The randomness beacon critically relies on the uniqueness (or function) property of VDFs. As you said a PoSW can have multiple output. A malicious prover would select the PoSW output that yields her ...
- 203
2
votes
Reason for squaring and not arbitrary exponentiation in Wesolowski and Pietrzak verifiable delay functions (VDFs)
Does the use of repeated squaring rather than some arbitrary exponent have any cryptographic significance? Is it just simpler?
Mostly, it makes the description simpler.
The prover and the verifier ...
- 150k
2
votes
Accepted
Single-block hash construction based on a block cipher with two fixed keys
This construction is well-known as XORP = "XOR of independent permutations". In your case the permutations are obtained by invoking a block cipher $E$ with different keys.
If $E$ is an ideal ...
- 14.1k
Only top scored, non community-wiki answers of a minimum length are eligible