19

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 April. Another team shall have the answer by the 11th or 12th of May (they used a FPGA). I noticed around the end of 2015 that if I used GMP I could find the ...


13

NO, you can't ! I will only consider initial_vector_0 and next_block_0. What you have found is this: +---+ | | | | IV0 ---->+ f +----> state | | | | | +---+ | xor +---------> 1111111111...1 0000000000 +---+ | | | ...


11

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 out it isn't immediately clear how to achieve this or whether it is possible, especially in settings such as blockchains where something closer to a Random Oracle ...


9

The puzzle has now been solved! The solution was announced in May 2019. It was solved by Bernard Fabrot, who used a modern optimized implementation of big integer multiplication to speed up the computation and finish it in about 3.5 years of computation instead of 35 years. At around the same time, a second team using FPGAs reported being weeks away from ...


9

Uniformity is a tricky one. SHA-256 (as well as SHA-3 for that matter) follows a heuristic approach. That is, the design is not based on a hardness assumption (for example, the factoring or discrete-log assumption) but on criteria that have only been verified empirically. As such, also the study of uniformity is an empirical study. The development of SHA-1/...


8

What prevents an attacker from building a custom ASIC and buying off-the-shelf DRAM chips, and building systems that pair each ASIC with a DRAM chip? DRAM memory is already pretty optimized for random memory accesses per second per dollar. Since a memory bound PoW spends more time waiting for memory than doing computation, there's little point in using an ...


8

Bitcoin ASIC miners are specialized hardware, which is capable of computing SHA-256 only. If you change almost any parameter in the Bitcoin proof-of-work, the existing miners will be useless. For instance, you could just change SHA-256 to SHA-1 or SHA-3. To be more efficient against spammers equipped with GPU, you might want to employ a hash function that ...


7

Is this usable? Or does the generation of the modulus outweigh any gains in the difference in signing time? No, it does not work. The generation cost itself isn't too important, because signing any one nonce doesn't help the client sign any other nonce, so you can just use a single key all the time (if you had to create a new keypair for every puzzle, ...


7

Memory-hard proof-of-work: are they ASIC-resistant? Theoretically, the answer is a clear “no”. Given enough resources (read: invested time and money) and the appropriate knowledge (ASICs don’t grow on trees, they have to be designed) all currently known and/or published “memory-hard PoW” solutions could be rendered into futile efforts. But theory ends ...


7

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 appropriately; in particular, having a large fraction of its cost spent in un-cacheable accesses to enough memory that DRAM is the only economical choice for that. The ...


6

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) require some amount of space to be evaluated. However, MHF alone are only the weakest primitive of this kind; many primitives have been designed that enhance ...


5

The paper "Proofs of Space: When Space is of the Essence" proposes a scheme that allows a client to prove that it has read/write access to at least $B$ bytes of memory. Basically, the server gives the client a function $f$ that requires at least $B$ bytes to compute, and the client proves it can compute $f$. The method is complicated and I haven't absorbed ...


5

Using time of day is predictable. Challenges should be unpredictable to an adversary. If they were not (as you sort of say), the adversary could solve a set of challenges ahead of time and then use them in rapid succession to cause a DOS. You want to meter access to the service, which is about not only ensuring clients do some work, but that work is done at ...


5

A good PRNG can't be exhausted, so your argument against random bytes doesn't matter. firstly I'd like the server to be completely stateless. Sounds impossible to me. a PRNG needs state. A clock needs state. An open connection is state too You probably want to store open challenges too. This part isn't strictly necessary, but very convenient. You ...


5

Edit: I just realized that the scheme that was proposed has serious security problems, and should not be used. The question is rather confused and ambiguous, but there seems to be a serious security problem. If I understand the proposal correctly, you are giving the client the private exponent $d$ and the modulus $n$ and the iteration count $k$ (say, $k=...


5

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 construct $H':\{0,1\}^*\to\{0,1\}^n:m\mapsto H(M\parallel m)$ for some fixed, pre-defined message $M$ and where $\parallel$ denotes concatenation. Note how $H'$...


5

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 visiting a website). Real-world values on the other hand have the distinct property of being difficult to predict in advance, making it useful for proving that a ...


4

It is hard to tell from this question, but I suspect that you may have managed to confuse yourself about what problem you have: i.e., that you've gotten caught up in a particular mechanism, and would benefit from taking a moment to step back and look at the actual requirements. I found it hard to extract the actual requirements from your question. In these ...


4

One obvious approach would be look at a discrete log problem. That is, you pick an appropriate group of order $n$ (where $n$ is prime) and a generator $G$; for a challenge, you pick a random element $H$, and you ask for the value $0 \le k < n$ such that $H = kG$. This meets your requirements (1) the value produced is effectively random, requirement (2) ...


4

Currently, it is probably safe. There are preimage attacks on MD5 but they are only slightly better than brute force. With a proof of work that only requires the initial bits of the hash to match it would likely be easier to use brute force than try to apply any attacks on it. However, I cannot see a good reason you would do that instead of using a more ...


4

In short: the question does not explain well the notion of asymmetry in ECC; and the exposition is not how Elliptic Curve Cryptography works. A reasoning sidestepping the notion of Discrete Logarithm Problem over a finite group can not really explain asymmetry as meant in ECC. Asymmetry is in the knowledge Alice and Bob have about the key, not asymmetry of ...


4

What is the probability that both [Hu] = [Hmu] and [He] = [Hme]. In english, what is the chance that two different files can have identical hashes in both an unencrypted and encrypted form? Depends on whether they are "random" files or attacker controlled. MD5 is a 128-bit hash, so for two random files that differ the probability that they have the same ...


4

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 search space for an attacker attempting in the process of brute forcing public keys. It doesn't help the attacker; if the attacker sees the public key, the ...


4

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 some time (i.e., you want to "send a message to the future", as its inventors initially put it). With a VDF, you can use the unique secret to mask the secret ...


3

The probability of finding an acceptable number is $$Pr(\mbox{accept})=2^{-20}.$$ Thus the probability not to find an acceptable number is $$Pr(\mbox{reject})=1-Pr(\mbox{accept})=1-2^{-20}.$$ Assuming independent events, the probability not to find an acceptable number in $k$ attempts is given by $$Pr(\mbox{$k$ rejects})=(1-2^{-20})^k.$$ Thus, the ...


3

Updated answer: No, this is not possible with cryptography. You have the ciphertext and you have the key. For all anyone knows, you could have made a copy of those to some other computer and decrypted the ciphertext without telling anyone. There's no way (with cryptography) to prove you haven't done that. One approach would be to implement a secure service ...


3

We know that traditional mathematical proofs can contain mistakes, and that these mistakes can remain undiscovered for years. Sometimes, the scheme is secure even if the proof is incorrect, e.g. RSA-OAEP. Sometimes, the scheme is mildly flawed, the flaws undiscovered because of mistakes in the proof, e.g. HMQV. And sometimes a scheme is simply insecure. We ...


3

Unless $2^t$ is the order of $2$ in the group $\mathbb Z_n$, in which case the solution is trivial. Unless the factors of $n$ are known, in which case the Chinese remainder theorem can be used. Unless $n$ (or its factors) has a special form, with only a few sparse bits being set (e.g. $n = 2^a + 2^b + 1$) and similar cases where $n$ has only a few ...


3

Here is one simple solution. After a new user installs the Pokemon software, before the new user can use that software (for tournament-eligible activities), they must register it with a central tournament server. The tournament server gives the user's software a random 128-bit seed $S$, and remembers this seed. The Pokemon software now creates a ...


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