# Tag Info

7

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

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

6

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

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

5

The theory is explained in the research paper that introduced the idea: Time-lock puzzles and timed-release crypto. Ronald L. Rivest, Adi Shamir, and David A. Wagner. MIT Laboratory for Computer Science, Technical memo MIT/LCS/TR-684 (1996) (Revision 3/10/96). The paper is cited in Rivest's description of the time capsule. As the security analysis in ...

4

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

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

$\quad$ chosen-prefix partial collisions for scrypt This does somewhat better at #3 than your second option because working requires storing previously obtained scrypt outputs. (I think it would be better to require a at most a given Hamming distance between the outputs rather than equality of a specific set of bits of the output. $\:$ The first of those ...

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

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

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

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

2

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

2

I guess the best place to begin is with the paper that started it all: Entity authentication and key distribution, by Bellare and Rogaway. In a nutshell, they define a protocol to be a secure mutual authenticated key exchange if it fulfills the following four criteria (I will explain the term "matching conversation" below): Matching conversations ...

2

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

2

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

1

Answers surely will be somewhat opinion-based, as no one can really say if manual checks are more or less convincing than automated checks. After all, both can be convincing if communicated/sold successfully to third parties. From my personal point of view, the best approach would be to manually verify the results of automatic verifications. So, first ...

1

First off: Divisibility testing is an atrociously bad way to check whether a number is prime or not. It is horribly inefficient and ineffective. You need to first read up on the literature on primality testing before you think about how to distribute it among untrusted clients. Use any standard primality test. Give each client a different iteration of ...

1

It is possible for Bob and Alice to store many files on some host file server using a host-proof protocol -- i.e., in such a way that even the sysadmins of that server cannot decrypt and read the plaintext of those files. You may be interested in browsing the questions with the host-proof tag. As far as I know, there is only one way to prove that those ...

1

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

1

Fundamentally, all you can do is make it "hard" to roll a character. For example, if it takes about five seconds of computation to roll a character, that will annoy ordinary users as they wait 5 seconds, but it will limit cheaters to 12 rolls per minute. Of course, cheaters can always get their hands on more computing power, and the delays will annoy ...

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