28 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 ...
TacticalCoder's user avatar
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: ...
Biv's user avatar
  • 9,979
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 ...
dionyziz's user avatar
  • 573
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 ...
jjj's user avatar
  • 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 ...
fgrieu's user avatar
  • 140k
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 ...
Geoffroy Couteau's user avatar
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) ...
Geoffroy Couteau's user avatar
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 ...
SEJPM's user avatar
  • 45.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 ...
forest's user avatar
  • 15.2k
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 ...
forest's user avatar
  • 15.2k
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 ...
poncho's user avatar
  • 146k
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 ...
kelalaka's user avatar
  • 48.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 ...
poncho's user avatar
  • 146k
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 ...
Maarten Bodewes's user avatar
  • 92.4k
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 ...
e-sushi's user avatar
  • 17.9k
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 ...
Thomas Prest's user avatar
  • 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}$...
Sam Jaques's user avatar
  • 1,135
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 ...
Mikero's user avatar
  • 13.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$ ...
Ievgeni's user avatar
  • 2,585
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 ...
DannyNiu's user avatar
  • 9,080
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 ...
nealmcb's user avatar
  • 570
2 votes

Stateless proof-of-work system with 0-roundtrip time

Is the requirement to prevent replaying identical requests? If not, it seems trivial to use a partial inverse hash of the request body. If you are concerned about replaying identical requests, one ...
geoff_h's user avatar
  • 337
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 ...
Bharat Mallapur's user avatar
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 ...
cypherfox's user avatar
  • 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 ...
Mayank's user avatar
  • 447
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 ...
ckamath's user avatar
  • 5,188
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. ...
poncho's user avatar
  • 146k
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 ...
Benedikt Bünz's user avatar
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 ...
poncho's user avatar
  • 146k
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 ...
Mikero's user avatar
  • 13.1k

Only top scored, non community-wiki answers of a minimum length are eligible