Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [proof-of-work]

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

2
votes
1answer
41 views

Embedding POW in an EC public key

I have an application where it would be advantageous for an attacker to have to spend a long time generating public keys. To do this, I require that the hash of the public key be less than a certain ...
0
votes
1answer
50 views

What Proof of Work does IOTA use? [closed]

I have some trouble finding valid information about IOTA. Actually I would be nice if there would be a good source. So my question is: Bitcoin uses the SHA-256 twice and some "target bits" for ...
1
vote
1answer
59 views

Hashing with (some sort of) Public and Private keys/salt/nonce

I'm trying to design a protocol where hashing can involve some public and private components. The idea is that Alice hashes a value with minimal computation and sends the hash to Bob. For Bob it ...
0
votes
0answers
39 views

Authenticated undistributable proof-of-work

I'm looking for a proof-of-work scheme with the following properties: It should be possible tell that the work was performed by the holder of private key $x$ Holder of $x$ should not be able to ...
2
votes
1answer
70 views

POW with Linear time to solve it?

Any suggestions for A Proof-of-Work algorithm in literature so that the time required for solving it is linear with the puzzle difficulty ??
0
votes
0answers
30 views

Proof of work using any computational puzzles

if we have a system in which any user can send arbitrary messages of his choice, and any one can receive that message. So a malicious user can send any messages which may lead to DOS attacks. Any ...
1
vote
0answers
54 views

Scrypt with weak parameters, for proof of work?

I need a proof of work/memory that takes about 100ms to complete, and as short time as possible to validate. Hashing random values and a nounce to get enough leading zeroes is my current approach, and ...
4
votes
2answers
274 views

Why not use world random world events instead of proof of work algorithm?

Taking a combination of world events like thunders, astronomical imagery, vote outcomes, stock index values and deriving the id of source of truth from hashed combination of them could be used instead ...
4
votes
0answers
92 views

Proof of knowledge of exponentiations

I am reading a paper of Furukawa and Sako, "An efficient scheme for proving a shuffle" from 2001. This paper writes a protocol for verifiable shuffling in mixnets. Their protocol make use of ...
1
vote
2answers
73 views

Are there Guaranteed Proof-of-work Systems?

Proof-of-Work systems such as hashcash, it seems to me, do not actually prove that a certain amount of work has been performed. For example, in the case of hashcan, could not the first random hash ...
5
votes
1answer
139 views

Making attacks on password hashes less economical

Perhaps an abstract question on complexity given the trade offs between memory vs runtime, I was wondering if it's possible to constrain only either extremes approaches to be optimally efficient, thus ...
0
votes
0answers
40 views

What are the implementation details about proof of stake?

All I find online are mostly conceptual ideas while I am interested in the tecnical details of how would go about designing a proof of stake sThat is how does proof of stake work under the hood? Is ...
5
votes
1answer
280 views

Time-locked Puzzles & Dead Man's Switch Intervention

I have been researching time-based puzzles. Specifically, computationally expensive algorithms for the purpose of a time-lock. This has lead me to sequential squaring, firstly, as well as some memory-...
3
votes
2answers
239 views

Can the proof of elasped time (PoET) consensus algorithm be exploited by multiple nodes?

i recently learned about the Hyperledger Blockchain Project and the specific frameworks. In case of the Sawtooth framework, consensus is reached not by PoW but by PoET (Proof of elapsed Time). When ...
3
votes
2answers
122 views

Why does the prover in an interactive proof run in exponential time with the space of the computation?

I'm currently trying to gain an understanding of verifiable computation and the strengths and weaknesses of past approaches. In particular, I've been watching the following YouTube video which talks ...
4
votes
3answers
189 views

Anti-spamming hash-based proof-of-work?

I'm planning to implement a public mailbox for receiving feedback, and I'd like to use hash-based proof-of-work to frustrate spammers. First, we want to use 320-bit capacity Gimli permutation as the ...
3
votes
2answers
156 views

Can/Which encryption algorithms be daisy chained to create a cryptographic computational puzzle?

Goal Create a computational puzzle that is fast to generate, takes an average computer minutes to solve, doesn't have any exploitable weaknesses, makes use of existing/tested encryption algorithms ...
1
vote
1answer
80 views

how to efficiently prove the query result is empty?

Consider a simplified scenario. Suppose an untrusted server holds a set of data $A=\{ a_1,a_2,\cdots,a_n\}$. A client issues a query $b$ to the server and wants to decide if $b\in A$. The server ...
1
vote
1answer
219 views

Security proof of mix net

I am writing an exercise in cryptography about anonymous communication. One of the systems I have looked into is the mix net protocol. I want to prove that this is secure. I have seen many different ...
1
vote
0answers
207 views

Can Bitcoin mining solve Graph Isomorphism-related problems?

Given a cryptographic hash $H:\{0,1\}^*\mapsto\{0,1\}^N$ and data $D\in\{0,1\}^*$, the Hashcash/Bitcoin Proof-of-Work entails finding a nonce $x$ such that $H(x\Vert D)$ begins with $d$ leading zeros, ...
1
vote
0answers
95 views

Difficulty of finding partially matching ciphertexts for a given plaintext when encrypted with two different keys

I'm trying to find a simple, practical proof-of-work scheme based purely on encryption (due to wide availability of optimized, hardware accelerated AES execution on most platforms, including modern ...
3
votes
0answers
92 views

Can a stream cipher with a big S-box create ASIC-resistance?

For a proof of work system a hash algorithm generates one pseudorandom index each round, in the same manner as RC4 and Spritz do. And it uses a bigger S-box, e.g. 2^20 numbers. The actual hash would ...
8
votes
1answer
831 views

Free Start Collision In SHA-3

Given that the five sub-functions that comprise SHA-3 are reversible an individual can produce specific outputs of their choosing. The following is to my knowledge an example of a free start collision ...
6
votes
1answer
709 views

Is this simple memory-hard function good?

I'm trying to come up with a simple memory-hard function for a proof-of-work system to protect against spam. Is the one below secure? For a message M, append a random number R. Repeat until you find ...
3
votes
0answers
88 views

Why does the DBDH simulator have half the advantage of an adversary?

Literature that includes the DBDH assumption such as this paper or this paper has a formal security proof that states: Suppose an adversary with non-negligible advantage $\varepsilon = Adv$. A ...
4
votes
0answers
155 views

Complexity: Taylor series and security proofs

Taylor Series For some functions entered into Wolfram, a Taylor series expansion is represented in Big-O notation. E.g. $\sin x, x = \frac \pi4$ produces: $\frac {1} {\sqrt[]{2}} +\frac{x-\frac{\pi}...
2
votes
0answers
45 views

Is there a proof-of-work scheme vulnerable to length extension attack?

I wonder is there an example of proof of work scheme that uses a hash function and requires the hash function to be immune to length extension attack? I mean the scheme, that becomes easy to solve if ...
1
vote
0answers
471 views

how to prove by reduction correctly?

some times when see a problem like : if some G is a PRG then G' is also a PRG. we prove this by reduction in the following way: we assume there is a Distinguisher A for G' and we construct ...
1
vote
0answers
84 views

Fill-and-question as a proof of space

This question follows from my previous one on proofs of space. Proof of space mechanisms rely on the computation of some proof that is easy to verify and requires from the prover an arbitrary amount ...
12
votes
2answers
215 views

Prove that you have $K$ bytes of memory

Alice has bought a brand new hard disk, $K$ (with $K \sim 10^{12}$) bytes in size. She is very happy about her purchase, and tells Bob about it. Bob claims he also bought a $K$ bytes hard disk. Alice ...
0
votes
2answers
339 views

Encryption scheme with arbitrary length message

Is the definition $\Pr[\operatorname{PrivK}_{\mathcal A,\Pi}^{eav}(n) = 1] \leq \frac{1}{2} + negl(n)$ still valid in case we have an encryption scheme $\pi (Gen,Enc,Dec)$ with arbitrary length, and ...
0
votes
1answer
220 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 ...
1
vote
2answers
266 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 ...
0
votes
1answer
79 views

Function with no fast path and with fast proof

When a function is iterated and each time a previous result is used as input to the next iteration (feedback), so that there is a limited benefit from parallel computing, is there such function that: ...
1
vote
2answers
120 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 ...
1
vote
0answers
135 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 ...
17
votes
3answers
5k 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. ...
1
vote
1answer
177 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, ...
1
vote
0answers
95 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 ...
1
vote
1answer
937 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 ...
2
votes
1answer
157 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 ...
0
votes
1answer
2k views

Collision resistant hash functions

Let (Gen1,H1) and (Gen2,H2) be two hash functions. Define (Gen,H) so that Gen runs Gen1 and Gen2 to obtain keys s1 and s2, respectively. Then define Hs1,s2(x)=Hs1(x)||Hs2(x). a) Prove that if at ...
4
votes
1answer
755 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 ...
5
votes
1answer
12k 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 the ...
2
votes
1answer
156 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 $+$ ...
8
votes
1answer
3k 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 ...
1
vote
0answers
109 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 ...
1
vote
0answers
293 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 ...
1
vote
0answers
103 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 "...
7
votes
1answer
1k 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 ...