# Tag Info

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

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

7

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

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

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

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 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$\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) ... 4 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 ... 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 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 ... 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 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 ... 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 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

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

2

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

2

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

1

In the paper the following remark is probably most important: For example, observing the frequency-error characteristics of Figure 4, the hashing cores corresponding to both approximate adders, $\operatorname{GDA}_{(1,4)}$ and $\operatorname{KSA}_{16}$, have negligible error rates at nominal frequency. Also, their nominal operating frequencies are ...

1

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 possibility might be to use the proof-of-work nonce for your load-balancing algorithm. For example, use the least significant 3 bits to distribute across 8 ...

1

Soundness usually means "you can't prove a false statement". There are different ways to formalise this but usually the probability of an efficient algorithm coming up with a false statement and a proof that verifies is negligible in some parameter (such as the length of the statement). Soundness can be defined for any proof scheme, including ones that are ...

1

Your property of what I would call "improvable" is actually considered undesirable for PoWs. It would allow a prover to make continuous progress toward a solution that satisfies the difficulty threshold. Which would mean that a prover that's twice as fast as another, has more than double the chance to win the race, which is considered unfair. Being twice as ...

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

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

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

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