# Tagged Questions

A proof of work system is based on a mathematical problem that is moderate hard to solve but easy to verify.

301 views

### Proof of work for standard computers

I'm interested in a proof-of-work system that works well on standard computers without using the GPU. Properties the system should have: Seed based proof-of-work. There is no distinguished ...
427 views

### How can uniformity of hash functions (e.g. SHA-256) be proved?

In reading about the Bitcoin protocol I noticed how much its proofs-of-work apparently depend on uniformity of the SHA-256 hash function. And so presumably do many other applications. How do ...
2k views

### What is the progress on the MIT LCS35 Time Capsule Crypto-Puzzle?

Ron Rivest posed a puzzle in 1999. MIT LCS35 Time Capsule Crypto-Puzzle. The problem is to compute $2^{2^t} \pmod n$ for specified values of $t$ and $n$. Here $n$ is the product of two large ...
564 views

### Proof of storage scheme

I'm familiar with client puzzles, where the client performs some work and there is a way to prove to the server that the client has done so. Is there a way to do this, but where the client's resource ...
403 views

### What challenge should I use in a challenge-response proof-of-work?

In order to guard against denial-of-service attacks, I want to require clients to do some work (more work than the server does fulfilling the request) before talking to them. Client connects Server ...
164 views

### Proof of work scheme with one and only one correct answer

I need a problem that has one and only one solution, such that the solution is hard to find but easy to verify. I need to be able to generate the problem deterministically from a random seed. So ...
3k views

### Probability that two different files can have same MD5 hash for both an unencrypted and encrypted version (AES256, same key between files)

This math is way over my head, and don't even know if it can be done, but here are the assumptions: Take unencrypted File [Fu] of variable length, but assume 100KB as an example. Let File [Fe] be ...
573 views

### A proof-of-work random number generation system for Pokémon [closed]

(The original question that was here was considered too confusing, unclear, and rambling. You can still view it in the edit history, but the content is no longer useful by itself, and cannot be ...
280 views

### Simple proof of work example?

Can anyone show me a simple proof of work algorithm that I can use to stop spammers? I've looked at hashcat, but i think there's a bit too much specialized hardware for bitcoin mining. That is, the ...
248 views

### Memory-hard proof-of-work: are they ASIC-resistant?

Is a memory-hard proof-of-work scheme necessarily resistant to speedups from custom ASICS? Background: Bitcoin uses a proof-of-work scheme based on SHA256 hashing. The scheme is compute-bound. ...
191 views

### Is it safe to use RSA as a proof-of-work system?

Suppose I devised the following challenge-response proof-of-work system: A server generates a 2048-bit RSA modulus, and uses the "public" exponent (usually 65537) to sign a random nonce a fixed ...
252 views

### Is it possible to cryptographically prove when was the last time a ciphertext was decrypted/encrypted?

I want to provide a service that encrypts and decrypts documents and I want to provide the users with proof that I haven't stolen their secret key and read their documents. I know I can prove when a ...
127 views

### Is there a number of tries after which Hashcash is guaranted to be solved?

Hashcash is a proof-of-work system in which the Sender needs to find $Y$ such as the first (let's say 20) bits of $H(X+Y)$ are zeros where $H$ is a one-way hash function, $X$ is a fixed value and $+$ ...
161 views

### how much trust can we place in protocol verifiers? [closed]

I read many papers on authenticated key exchange protocols, and most security proofs are done by the authors. In this method, you can imagine that the efficiency is low. Moreover, even if you have ...
147 views

### difference between soundness in ZKPoK and special soundness for sigma proofs

What is the difference between soundness in ZKPoK and special soundness for sigma proofs?
98 views

### Is there an “additive” proof-of-work?

I'm trying to find a proof-of-work algorithm with the following properties: If A(1) is a proof of work with Difficulty(A(1))=n (requires n basic operations on average), then one can find a proof of ...
208 views

### Proof of work for determining whether a number is prime?

I have an idea for a system that would be outsourcing some brute force calculations to many users in hopes of finding divisors of a number. However, there is a possibility that a given number would be ...
72 views

### Any functioning system for interactive proof?

My problem is to outsource an array of data and ask the prover to sort the data. I am wonder if there is any working system out there that support interactive proof for the above computation? Or if ...
210 views

### Simplified Example of ECC to use in the classroom

I have come up with the following rudimentary example of how ECC relates to asymmetric keys. Is this a valid explanation of ECC and its relationship to asymmetry? To only be deciphered by the person ...
297 views

### how to mathematically prove a key exchange algorithm [closed]

I want to know the basic methodology that can be used to prove that a key exchange algorithm is secure. I am not asking about any specific algorithm. I want to know what should be proven and how to ...
106 views

### Can “Approximate Hashing” work in a Proof-of-Work context?

Here is a draft of an article claimed to soon appear in a peer-reviewed conference: Matthew Vilim, Uenry Duwe, Rakesh Kumar, Approximate Bitcoin Mining. It is proposed to simplifying a SHA-256 engine ...
56 views

### key exchange using hashing with preshared secret

I came upon an idea the other day that I had some questions about. I am not a security professional but I do study with an amateur interest and have not heard of this particular idea before. There ...
85 views

### Prove that certain amount of data was stored

I'm looking for a way to prove that a certain amount of data was stored, through some easily verifiable piece of information. Similarly to how proof-of-work can prove through a hash that a certain ...
88 views

### Parallel-resistant proof-of-work scheme without hidden knowledge

Follow-up to: Parallel-resistant proof-of-work scheme? Is there a proof-of-work scheme that: can only be solved serially; given the solution, can be verified in minimal time; deterministically ...
166 views

### Hash function that is efficient on GPU and poorly suited to ASIC

I have such requirements to the hash function in my project: operating on 32-bit data, not mathematically breakable (built on existing hashes known to be secure), free of branching, as much as ...
70 views

### Looking for alternative key stretching

I am by no means a security expert, but I am curious whether functions that don't produce different outputs when raised to the power of N (without any psuedo-randomness) exist, that are as strong as "...
70 views

### Is there a password hash function with a human component?

Sort of Related: Is there a cryptographic hash function that can be performed with pencil and paper? One problem with hashing passwords is that the attacker has more of everything it seems. More ...
61 views

### Is it safe to use MD5 in a proof of work system?

Here is the POW system: you are given a string and you need to compute a suffix so that first few bits of the MD5 value are all 0. I know MD5 is collision vulnerable, but is it safe to use MD5 here, ...
61 views

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

I'm designing an API. To avoid abuse, I need to rate limit the requests somehow, but I don't want to do it per user as it's very easy to create new accounts automatically. I think a proof of work ...