Foundations, Properties, and Security Applications of Puzzles: A Survey
---
paper_title: Pricing via processing or combatting junk mail

paper_content:

We present a computational technique for combatting junk mail in particular and controlling access to a shared resource in general. The main idea is to require a user to compute a moderately hard, but not intractable, function in order to gain access to the resource, thus preventing frivolous use. To this end we suggest several pricing Junctions, based on, respectively, extracting square roots modulo a prime, the Fiat-Shamir signature scheme, and the Ong-Schnorr-Shamir (cracked) signature scheme.
---
paper_title: On Memory-Bound Functions for Fighting Spam

paper_content:

In 1992, Dwork and Naor proposed that e-mail messages be accompanied by easy-to-check proofs of computational effort in order to discourage junk e-mail, now known as spam. They proposed specific CPU-bound functions for this purpose. Burrows suggested that, since memory access speeds vary across machines much less than do CPU speeds, memory-bound functions may behave more equitably than CPU-bound functions; this approach was first explored by Abadi, Burrows, Manasse, and Wobber [3].
---
paper_title: Secure communications over insecure channels

paper_content:

According to traditional conceptions of cryptographic security, it is necessary to transmit a key, by secret means, before encrypted massages can be sent securely. This paper shows that it is possible to select a key over open communications channels in such a fashion that communications security can be maintained. A method is described which forces any enemy to expend an amount of work which increases as the square of the work required of the two communicants to select the key. The method provides a logically new kind of protection against the passive eavesdropper. It suggests that further research on this topic will be highly rewarding, both in a theoretical and a practical sense.
---
paper_title: Moderately hard, memory-bound functions

paper_content:

A resource may be abused if its users incur little or no cost. For example, e-mail abuse is rampant because sending an e-mail has negligible cost for the sender. It has been suggested that such abuse may be discouraged by introducing an artificial cost in the form of a moderately expensive computation. Thus, the sender of an e-mail might be required to pay by computing for a few seconds before the e-mail is accepted. Unfortunately, because of sharp disparities across computer systems, this approach may be ineffective against malicious users with high-end systems, prohibitively slow for legitimate users with low-end systems, or both. Starting from this observation, we research moderately hard functions that most recent systems will evaluate at about the same speed. For this purpose, we rely on memory-bound computations. We describe and analyze a family of moderately hard, memory-bound functions, and we explain how to use them for protecting against abuses.
---
paper_title: A Guided Tour Puzzle for Denial of Service Prevention

paper_content:

Various cryptographic puzzle schemes are proposed as a defense mechanism against denial of service attack. But, all these puzzle schemes face a dilemma when there is a large disparity between the computational power of attackers and legitimate clients: increasing the difficulty of puzzles might unnecessarily restrict legitimate clients too much, and lower difficulty puzzles cannot sufficiently block attackers with large computational resources. In this paper, we introduce guided tour puzzle, a novel puzzle scheme that is not affected by such resource disparity. A guided tour puzzle requires a client to visit a predefined set of nodes, called tour guides, in a certain sequential order to retrieve an n piece answer, one piece from each tour guide that appears in the tour. This puzzle solving process is non-parallelizable, thus cheating by trying to solve the puzzle in parallel is not possible. Guided tour puzzle not only achieves all previously defined desired properties of a cryptographic puzzle scheme, but it also satisfies more important requirements, such as puzzle fairness and minimum interference, that we identified. The number of tour guides required by the scheme can be as few as two, and this extra cost can be amortized by sharing the same set of tour guides among multiple servers.
---
paper_title: Hashcash - A Denial of Service Counter-Measure

paper_content:

Hashcash was originally proposed as a mechanism to throttle systematic abuse of un-metered internet resources such as email, and anonymous remailers in May 1997. Five years on, this paper captures in one place the various applications, improvements suggested and related subsequent publications, and describes initial experience from experiments using hashcash. The hashcash CPU cost-function computes a token which can be used as a proof-of-work. Interactive and noninteractive variants of cost-functions can be constructed which can be used in situations where the server can issue a challenge (connection oriented interactive protocol), and where it can not (where the communication is store–and– forward, or packet oriented) respectively.
---
paper_title: CAPTCHA: Using Hard AI Problems for Security

paper_content:

We introduce CAPTCHA, an automated test that humans can pass, but current computer programs can't pass: any program that has high success over a CAPTCHA can be used to solve an unsolved Artificial Intelligence (AI) problem. We provide several novel constructions of CAPTCHAS. Since CAPTCHAs have many applications in practical security, our approach introduces a new class of hard problems that can be exploited for security purposes. Much like research in cryptography has had a positive impact on algorithms for factoring and discrete log, we hope that the use of hard AI problems for security purposes allows us to advance the field of Artificial Intelligence. We introduce two families of Al problems that can be used to construct CAPTCHAS and we show that solutions to such problems can be used for steganographic communication. CAPTCHAS based on these AI problem families, then, imply a win-win situation: either the problems remain unsolved and there is a way to differentiate humans from computers, or the problems are solved and there is a way to communicate covertly on some channels.
---
paper_title: Pricing via processing or combatting junk mail

paper_content:

We present a computational technique for combatting junk mail in particular and controlling access to a shared resource in general. The main idea is to require a user to compute a moderately hard, but not intractable, function in order to gain access to the resource, thus preventing frivolous use. To this end we suggest several pricing Junctions, based on, respectively, extracting square roots modulo a prime, the Fiat-Shamir signature scheme, and the Ong-Schnorr-Shamir (cracked) signature scheme.
---
paper_title: Secure communications over insecure channels

paper_content:

According to traditional conceptions of cryptographic security, it is necessary to transmit a key, by secret means, before encrypted massages can be sent securely. This paper shows that it is possible to select a key over open communications channels in such a fashion that communications security can be maintained. A method is described which forces any enemy to expend an amount of work which increases as the square of the work required of the two communicants to select the key. The method provides a logically new kind of protection against the passive eavesdropper. It suggests that further research on this topic will be highly rewarding, both in a theoretical and a practical sense.
---
paper_title: Pricing via processing or combatting junk mail

paper_content:

We present a computational technique for combatting junk mail in particular and controlling access to a shared resource in general. The main idea is to require a user to compute a moderately hard, but not intractable, function in order to gain access to the resource, thus preventing frivolous use. To this end we suggest several pricing Junctions, based on, respectively, extracting square roots modulo a prime, the Fiat-Shamir signature scheme, and the Ong-Schnorr-Shamir (cracked) signature scheme.
---
paper_title: Time-lock puzzles and timed-release crypto

paper_content:

Our motivation is the notion of ``timed-release crypto,'''' where the goal is to encrypt a message so that it can not be decrypted by anyone, not even the sender, until a pre-determined amount of time has passed. The goal is to ``send information into the future.'''' This problem was first discussed by Timothy May \cite{May93}. What are the applications of ``timed-release crypto''''? Here are a few possibilities (some due to May): A bidder in an auction wants to seal his bid so that it can only be opened after the bidding period is closed. A homeowner wants to give his mortgage holder a series of encrypted mortgage payments. These might be encrypted digital cash with different decryption dates, so that one payment becomes decryptable (and thus usable by the bank) at the beginning of each successive month. An individual wants to encrypt his diaries so that they are only decryptable after fifty years. A key-escrow scheme can be based on timed-release crypto, so that the government can get the message keys, but only after a fixed period (say one year). \ There are presumably many other applications. There are two natural approaches to implementing timed-release crypto: Use ``time-lock puzzles''''--computational problems that can not be solved without running a computer continuously for at least a certain amount of time. Use trusted agents who promise not to reveal certain information until a specified date. Using trusted agents has the obvious problem of ensuring that the agents are trustworthy; secret-sharing approaches can be used to alleviate this concern. Using time-lock puzzles has the problem that the CPU time required to solve a problem can depend on the amount and nature of the hardware used to solve the problem, as well as the parallelizability of the computational problem being solved. In this note we explore both approaches. (We note that Tim May has suggested an approach based on the use of trusted agents.)
---
paper_title: Pricing via processing or combatting junk mail

paper_content:

We present a computational technique for combatting junk mail in particular and controlling access to a shared resource in general. The main idea is to require a user to compute a moderately hard, but not intractable, function in order to gain access to the resource, thus preventing frivolous use. To this end we suggest several pricing Junctions, based on, respectively, extracting square roots modulo a prime, the Fiat-Shamir signature scheme, and the Ong-Schnorr-Shamir (cracked) signature scheme.
---
paper_title: Hashcash - A Denial of Service Counter-Measure

paper_content:

Hashcash was originally proposed as a mechanism to throttle systematic abuse of un-metered internet resources such as email, and anonymous remailers in May 1997. Five years on, this paper captures in one place the various applications, improvements suggested and related subsequent publications, and describes initial experience from experiments using hashcash. The hashcash CPU cost-function computes a token which can be used as a proof-of-work. Interactive and noninteractive variants of cost-functions can be constructed which can be used in situations where the server can issue a challenge (connection oriented interactive protocol), and where it can not (where the communication is store–and– forward, or packet oriented) respectively.
---
paper_title: Verifiable Delay Functions

paper_content:

We study the problem of building a verifiable delay function (VDF). A \(\text {VDF}\)requires a specified number of sequential steps to evaluate, yet produces a unique output that can be efficiently and publicly verified. \(\text {VDF}\)s have many applications in decentralized systems, including public randomness beacons, leader election in consensus protocols, and proofs of replication. We formalize the requirements for \(\text {VDF}\)s and present new candidate constructions that are the first to achieve an exponential gap between evaluation and verification time.
---
paper_title: Time-lock puzzles and timed-release crypto

paper_content:

Our motivation is the notion of ``timed-release crypto,'''' where the goal is to encrypt a message so that it can not be decrypted by anyone, not even the sender, until a pre-determined amount of time has passed. The goal is to ``send information into the future.'''' This problem was first discussed by Timothy May \cite{May93}. What are the applications of ``timed-release crypto''''? Here are a few possibilities (some due to May): A bidder in an auction wants to seal his bid so that it can only be opened after the bidding period is closed. A homeowner wants to give his mortgage holder a series of encrypted mortgage payments. These might be encrypted digital cash with different decryption dates, so that one payment becomes decryptable (and thus usable by the bank) at the beginning of each successive month. An individual wants to encrypt his diaries so that they are only decryptable after fifty years. A key-escrow scheme can be based on timed-release crypto, so that the government can get the message keys, but only after a fixed period (say one year). \ There are presumably many other applications. There are two natural approaches to implementing timed-release crypto: Use ``time-lock puzzles''''--computational problems that can not be solved without running a computer continuously for at least a certain amount of time. Use trusted agents who promise not to reveal certain information until a specified date. Using trusted agents has the obvious problem of ensuring that the agents are trustworthy; secret-sharing approaches can be used to alleviate this concern. Using time-lock puzzles has the problem that the CPU time required to solve a problem can depend on the amount and nature of the hardware used to solve the problem, as well as the parallelizability of the computational problem being solved. In this note we explore both approaches. (We note that Tim May has suggested an approach based on the use of trusted agents.)
---
paper_title: CAPTCHA: Using Hard AI Problems for Security

paper_content:

We introduce CAPTCHA, an automated test that humans can pass, but current computer programs can't pass: any program that has high success over a CAPTCHA can be used to solve an unsolved Artificial Intelligence (AI) problem. We provide several novel constructions of CAPTCHAS. Since CAPTCHAs have many applications in practical security, our approach introduces a new class of hard problems that can be exploited for security purposes. Much like research in cryptography has had a positive impact on algorithms for factoring and discrete log, we hope that the use of hard AI problems for security purposes allows us to advance the field of Artificial Intelligence. We introduce two families of Al problems that can be used to construct CAPTCHAS and we show that solutions to such problems can be used for steganographic communication. CAPTCHAS based on these AI problem families, then, imply a win-win situation: either the problems remain unsolved and there is a way to differentiate humans from computers, or the problems are solved and there is a way to communicate covertly on some channels.
---
paper_title: Time-lock puzzles and timed-release crypto

paper_content:

Our motivation is the notion of ``timed-release crypto,'''' where the goal is to encrypt a message so that it can not be decrypted by anyone, not even the sender, until a pre-determined amount of time has passed. The goal is to ``send information into the future.'''' This problem was first discussed by Timothy May \cite{May93}. What are the applications of ``timed-release crypto''''? Here are a few possibilities (some due to May): A bidder in an auction wants to seal his bid so that it can only be opened after the bidding period is closed. A homeowner wants to give his mortgage holder a series of encrypted mortgage payments. These might be encrypted digital cash with different decryption dates, so that one payment becomes decryptable (and thus usable by the bank) at the beginning of each successive month. An individual wants to encrypt his diaries so that they are only decryptable after fifty years. A key-escrow scheme can be based on timed-release crypto, so that the government can get the message keys, but only after a fixed period (say one year). \ There are presumably many other applications. There are two natural approaches to implementing timed-release crypto: Use ``time-lock puzzles''''--computational problems that can not be solved without running a computer continuously for at least a certain amount of time. Use trusted agents who promise not to reveal certain information until a specified date. Using trusted agents has the obvious problem of ensuring that the agents are trustworthy; secret-sharing approaches can be used to alleviate this concern. Using time-lock puzzles has the problem that the CPU time required to solve a problem can depend on the amount and nature of the hardware used to solve the problem, as well as the parallelizability of the computational problem being solved. In this note we explore both approaches. (We note that Tim May has suggested an approach based on the use of trusted agents.)
---
paper_title: On Non-Parallelizable Deterministic Client Puzzle Scheme with Batch Verification Modes

paper_content:

A (computational) client puzzle scheme enables a client to prove to a server that a certain amount of computing resources (CPU cycles and/or Memory look-ups) has been dedicated to solve a puzzle. Researchers have identified a number of potential applications, such as constructing timed cryptography, fighting junk emails, and protecting critical infrastructure from DoS attacks. In this paper, we first revisit this concept and formally define two properties, namely deterministic computation and parallel computation resistance. Our analysis show that both properties are crucial for the effectiveness of client puzzle schemes in most application scenarios. We prove that the RSW client puzzle scheme, which is based on the repeated squaring technique, achieves both properties. Secondly, we introduce two batch verification modes for the RSW client puzzle scheme in order to improve the verification efficiency of the server, and investigate three methods for handling errors in batch verifications. Lastly, we show that client puzzle schemes can be integrated with reputation systems to further improve the effectiveness in practice.
---
paper_title: Pricing via processing or combatting junk mail

paper_content:

We present a computational technique for combatting junk mail in particular and controlling access to a shared resource in general. The main idea is to require a user to compute a moderately hard, but not intractable, function in order to gain access to the resource, thus preventing frivolous use. To this end we suggest several pricing Junctions, based on, respectively, extracting square roots modulo a prime, the Fiat-Shamir signature scheme, and the Ong-Schnorr-Shamir (cracked) signature scheme.
---
paper_title: Design and implementation of network puzzles

paper_content:

Client puzzles have been proposed in a number of protocols as a mechanism for mitigating the effects of distributed denial of service (DDoS) attacks. In order to provide protection against simultaneous attacks across a wide range of applications and protocols, however, such puzzles must be placed at a layer common to all of them; the network layer. Placing puzzles at the IP layer fundamentally changes the service paradigm of the Internet, allowing any device within the network to push load back onto those it is servicing. An advantage of network layer puzzles over previous puzzle mechanisms is that they can be applied to all traffic from malicious clients, making it possible to defend against arbitrary attacks as well as making previously voluntary mechanisms mandatory. In this paper, we outline goals which must be met for puzzles to be deployed effectively at the network layer. We then describe the design, implementation, and evaluation of a system that meets these goals by supporting efficient, fine-grained control of puzzles at the network layer. In particular, we describe modifications to existing puzzle protocols that allow them to work at the network layer, a hint-based hash-reversal puzzle that allows for the generation and verification of fine-grained puzzles at line speed in the fast path of high-speed routers, and an iptables implementation that supports transparent deployment at arbitrary locations in the network.
---
paper_title: Security Notions and Generic Constructions for Client Puzzles

paper_content:

By a computational puzzle we mean a mildly difficult computational problem that requires resources (processor cycles, memory, or both) to solve. Puzzles have found a variety of uses in security. In this paper we are concerned with client puzzles : a type of puzzle used as a defense against Denial of Service (DoS) attacks. The main contribution of this paper is a formal model for the security of client puzzles.We clarify the interface that client puzzles should offer and give two security notions for puzzles. Both functionality and security are inspired by, and tailored to, the use of puzzles as a defense against DoS attacks.Our definitions fill an important gap: breaking either of the two properties immediately leads to successful DoS attacks. We illustrate this point with an attack against a previously proposed puzzle construction.We also provide a generic construction of a client puzzle which meets our security definitions.
---
paper_title: Towards uncheatable benchmarks

paper_content:

The problem of how to make benchmarks resistant to tampering and hence more trustworthy is studied. Some schemes that are based on modern cryptography and complexity theory are proposed to make benchmarks uncheatable. The philosophy is the same as that of encryption-decryption schemes, namely, that trust in individuals and organizations is replaced by trust in the impossibility of breaking certain computational problems. >
---
paper_title: SybilControl: practical sybil defense with computational puzzles

paper_content:

Many distributed systems are subject to the Sybil attack, where an adversary subverts system operation by emulating the behavior of multiple distinct nodes. Most recent works addressing this problem leverage social networks to establish trust relationships between users. However, social networks are not appropriate in all systems. They can be subverted by social engineering techniques, require nodes to maintain and be aware of social network information, and may require overly optimistic assumptions about the fast-mixing nature of social links. This paper explores an alternate approach. We present SybilControl, a novel decentralized scheme for controlling the extent of Sybil attacks. It is an admission and retainment control scheme for nodes in a distributed system that requires them to periodically solve computational puzzles. SybilControl consists of a distributed protocol to allow nodes to collectively verify the computational work of other nodes, and mechanisms to prevent the malicious influence of misbehaving nodes that do not perform the computational work. We investigate the practical issues involved with deploying SybilControl into existing DHTs, particularly with handling churn. SybilControl is shown to provide strict bounds on the size of Sybil attacks, given adversaries with finite resources. We also show through simulations that the performance overhead of enabling SybilControl is manageable using commonplace DHT churn-handling techniques. This provides strong evidence that SybilControl can be practically deployed.
---
paper_title: Time-lock puzzles and timed-release crypto

paper_content:

Our motivation is the notion of ``timed-release crypto,'''' where the goal is to encrypt a message so that it can not be decrypted by anyone, not even the sender, until a pre-determined amount of time has passed. The goal is to ``send information into the future.'''' This problem was first discussed by Timothy May \cite{May93}. What are the applications of ``timed-release crypto''''? Here are a few possibilities (some due to May): A bidder in an auction wants to seal his bid so that it can only be opened after the bidding period is closed. A homeowner wants to give his mortgage holder a series of encrypted mortgage payments. These might be encrypted digital cash with different decryption dates, so that one payment becomes decryptable (and thus usable by the bank) at the beginning of each successive month. An individual wants to encrypt his diaries so that they are only decryptable after fifty years. A key-escrow scheme can be based on timed-release crypto, so that the government can get the message keys, but only after a fixed period (say one year). \ There are presumably many other applications. There are two natural approaches to implementing timed-release crypto: Use ``time-lock puzzles''''--computational problems that can not be solved without running a computer continuously for at least a certain amount of time. Use trusted agents who promise not to reveal certain information until a specified date. Using trusted agents has the obvious problem of ensuring that the agents are trustworthy; secret-sharing approaches can be used to alleviate this concern. Using time-lock puzzles has the problem that the CPU time required to solve a problem can depend on the amount and nature of the hardware used to solve the problem, as well as the parallelizability of the computational problem being solved. In this note we explore both approaches. (We note that Tim May has suggested an approach based on the use of trusted agents.)
---
paper_title: Moderately Hard Functions: Definition, Instantiations, and Applications

paper_content:

Several cryptographic schemes and applications are based on functions that are both reasonably efficient to compute and moderately hard to invert, including client puzzles for Denial-of-Service protection, password protection via salted hashes, or recent proof-of-work blockchain systems. Despite their wide use, a definition of this concept has not yet been distilled and formalized explicitly. Instead, either the applications are proven directly based on the assumptions underlying the function, or some property of the function is proven, but the security of the application is argued only informally. The goal of this work is to provide a (universal) definition that decouples the efforts of designing new moderately hard functions and of building protocols based on them, serving as an interface between the two.
---
paper_title: WiSec' 2011 poster: security enhancement for bluetooth low energy with Merkle's puzzle

paper_content:

This is a conceptual study attempting to provide a supplementary security feature based on Merkle's Puzzle (MP) in Bluetooth Low Energy (BLE).
---
paper_title: Secure communications over insecure channels

paper_content:

According to traditional conceptions of cryptographic security, it is necessary to transmit a key, by secret means, before encrypted massages can be sent securely. This paper shows that it is possible to select a key over open communications channels in such a fashion that communications security can be maintained. A method is described which forces any enemy to expend an amount of work which increases as the square of the work required of the two communicants to select the key. The method provides a logically new kind of protection against the passive eavesdropper. It suggests that further research on this topic will be highly rewarding, both in a theoretical and a practical sense.
---
paper_title: Key Predistribution Schemes for Establishing Pairwise Keys with a Mobile Sink in Sensor Networks

paper_content:

Security services such as authentication and pairwise key establishment are critical to sensor networks. They enable sensor nodes to communicate securely with each other using cryptographic techniques. In this paper, we propose two key predistribution schemes that enable a mobile sink to establish a secure data-communication link, on the fly, with any sensor nodes. The proposed schemes are based on the polynomial pool-based key predistribution scheme, the probabilistic generation key predistribution scheme, and the Q-composite scheme. The security analysis in this paper indicates that these two proposed predistribution schemes assure, with high probability and low communication overhead, that any sensor node can establish a pairwise key with the mobile sink. Comparing the two proposed key predistribution schemes with the Q-composite scheme, the probabilistic key predistribution scheme, and the polynomial pool-based scheme, our analytical results clearly show that our schemes perform better in terms of network resilience to node capture than existing schemes if used in wireless sensor networks with mobile sinks.
---
paper_title: Pricing via processing or combatting junk mail

paper_content:

We present a computational technique for combatting junk mail in particular and controlling access to a shared resource in general. The main idea is to require a user to compute a moderately hard, but not intractable, function in order to gain access to the resource, thus preventing frivolous use. To this end we suggest several pricing Junctions, based on, respectively, extracting square roots modulo a prime, the Fiat-Shamir signature scheme, and the Ong-Schnorr-Shamir (cracked) signature scheme.
---
paper_title: On Memory-Bound Functions for Fighting Spam

paper_content:

In 1992, Dwork and Naor proposed that e-mail messages be accompanied by easy-to-check proofs of computational effort in order to discourage junk e-mail, now known as spam. They proposed specific CPU-bound functions for this purpose. Burrows suggested that, since memory access speeds vary across machines much less than do CPU speeds, memory-bound functions may behave more equitably than CPU-bound functions; this approach was first explored by Abadi, Burrows, Manasse, and Wobber [3].
---
paper_title: Pebbling and proofs of work

paper_content:

We investigate methods for providing easy-to-check proofs of computational effort. Originally intended for discouraging spam, the concept has wide applicability as a method for controlling denial of service attacks. Dwork, Goldberg, and Naor proposed a specific memory-bound function for this purpose and proved an asymptotically tight amortized lower bound on the number of memory accesses any polynomial time bounded adversary must make. Their function requires a large random table which, crucially, cannot be compressed. ::: ::: We answer an open question of Dwork et al. by designing a compact representation for the table. The paradox, compressing an incompressible table, is resolved by embedding a time/space tradeoff into the process for constructing the table from its representation.
---
paper_title: Moderately hard, memory-bound functions

paper_content:

A resource may be abused if its users incur little or no cost. For example, e-mail abuse is rampant because sending an e-mail has negligible cost for the sender. It has been suggested that such abuse may be discouraged by introducing an artificial cost in the form of a moderately expensive computation. Thus, the sender of an e-mail might be required to pay by computing for a few seconds before the e-mail is accepted. Unfortunately, because of sharp disparities across computer systems, this approach may be ineffective against malicious users with high-end systems, prohibitively slow for legitimate users with low-end systems, or both. Starting from this observation, we research moderately hard functions that most recent systems will evaluate at about the same speed. For this purpose, we rely on memory-bound computations. We describe and analyze a family of moderately hard, memory-bound functions, and we explain how to use them for protecting against abuses.
---
paper_title: "Proof-of-Work" Proves Not to Work

paper_content:

A frequently proposed method of reducing unsolicited bulk email (\spam") is for senders to pay for each email they send. Proof-of- work schemes avoid charging real money by requiring senders to demon- strate that they have expended processing time in solving a crypto- graphic puzzle. We attempt to determine how di-cult that puzzle should be so as to be efiective in preventing spam. We analyse this both from an economic perspective, \how can we stop it being cost-efiective to send spam", and from a security perspective, \spammers can access insecure end-user machines and will steal processing cycles to solve puzzles". Both analyses lead to similar values of puzzle di-culty. Unfortunately, real- world data from a large ISP shows that these di-culty levels would mean that signiflcant numbers of senders of legitimate email would be unable to continue their current levels of activity. We conclude that proof-of-work will not be a solution to the problem of spam.
---
paper_title: Proof of Work can Work

paper_content:

and Overview Proof of work has been proposed as a mechanism to increase the cost of email so that spamming is no longer economically attractive. However, the first economic examination of proof of work argued that POW would not, in fact, work because of the difference of cost to spammers and senders of legitimate email. We illustrate that this shift in the production frontier enabled by zombies does not remove the efficacy of proof of work if work requirements are weighted by a reputation function. We illustrate that proof of work can worked when combined with the currently used reputation systems in commercial anti-spam technologies.
---
paper_title: Hashcash - A Denial of Service Counter-Measure

paper_content:

Hashcash was originally proposed as a mechanism to throttle systematic abuse of un-metered internet resources such as email, and anonymous remailers in May 1997. Five years on, this paper captures in one place the various applications, improvements suggested and related subsequent publications, and describes initial experience from experiments using hashcash. The hashcash CPU cost-function computes a token which can be used as a proof-of-work. Interactive and noninteractive variants of cost-functions can be constructed which can be used in situations where the server can issue a challenge (connection oriented interactive protocol), and where it can not (where the communication is store–and– forward, or packet oriented) respectively.
---
paper_title: CAPTCHA: Using Hard AI Problems for Security

paper_content:

We introduce CAPTCHA, an automated test that humans can pass, but current computer programs can't pass: any program that has high success over a CAPTCHA can be used to solve an unsolved Artificial Intelligence (AI) problem. We provide several novel constructions of CAPTCHAS. Since CAPTCHAs have many applications in practical security, our approach introduces a new class of hard problems that can be exploited for security purposes. Much like research in cryptography has had a positive impact on algorithms for factoring and discrete log, we hope that the use of hard AI problems for security purposes allows us to advance the field of Artificial Intelligence. We introduce two families of Al problems that can be used to construct CAPTCHAS and we show that solutions to such problems can be used for steganographic communication. CAPTCHAS based on these AI problem families, then, imply a win-win situation: either the problems remain unsolved and there is a way to differentiate humans from computers, or the problems are solved and there is a way to communicate covertly on some channels.
---
paper_title: TLS Client Puzzles Extension

paper_content:

Client puzzles allow a TLS server to defend itself against asymmetric ::: DDoS attacks. In particular, it allows a server to request clients ::: perform a selected amount of computation prior to the server ::: performing expensive cryptographic operations. This allows servers to ::: employ a layered defense that represents an improvement over pure ::: rate-limiting strategies. Client puzzles are implemented as an ::: extension to TLS 1.3 [I-D.ietf-tls-tls13] wherein a server can issue a ::: HelloRetryRequest containing the puzzle as an extension. The client ::: must then resend its ClientHello with the puzzle results in the ::: extension.
---
paper_title: Revisiting Client Puzzles for State Exhaustion Attacks Resilience

paper_content:

In this paper, we address the challenges facing the adoption of client puzzles as a means to protect the TCP connection establishment channel from state exhaustion DDoS attacks. We model the problem of selecting the puzzle difficulties as a Stackelberg game with the server as the leader and the clients as the followers and obtain the equilibrium solution for the puzzle difficulty. We then present an implementation of client puzzles inside the TCP stack of the Linux 4.13.0 kernel. We evaluate the performance of our implementation and the obtained solution against a range of attacks through reproducible experiments on the DETER testbed. Our results show that client puzzles are effective at boosting the tolerance of the TCP handshake channel to state exhaustion DDoS attacks by rate limiting malicious attackers while allocating resources for legitimate clients.
---
paper_title: Guaranteeing access in spite of distributed service-flooding attacks

paper_content:

I'd like to be able to offer some guarantees of access in spite of flooding attacks in distributed denial of service instances. This is a topic that has interested me for a number of years, and hopefully I have now got a handle on it. ::: ::: In large open networks, in which all clients are legitimately authorised access to a particular service – regardless of their speed, or their location, or any other attributes – we'd obviously like to have client registration and authentication become unnecessary for service access. Of course, authentication might be necessary to control access to certain objects within the particular service, but that has nothing to do with whether or not the client can actually address or access the service.
---
paper_title: mod kaPoW: Protecting the web with transparent proof-of-work

paper_content:

Attacks from automated Web clients are a significant problem on the Internet. Web sites often employ Turing tests known as CAPTCHAs to combat automated agents. Unfortunately, such defenses require frequent human user input, are becoming less effective as computer vision techniques improve, and can be subverted by adversaries willing to hire humans to solve challenges. Several alternative defenses based upon cryptographic methods rather than human input have been proposed to achieve the same goals. Such "proof-of-work" techniques prioritize clients based on their willingness to solve computational challenges of client-specific difficulty set by the server. Unfortunately, few proof-of-work schemes have been deployed since they require wide-scale adoption of special client software to operate properly. To address these problems we present mocLkaPoW, a novel system that has the efficiency and human-transparency of proof-of-work schemes as well as the software backwards-compatibility of CAPTCHA schemes. The system leverages common Web technologies to deliver a challenge, solve it, and submit the client response, while providing accessibility for legacy clients. This paper describes and evaluates a prototype of this system.
---
paper_title: Design and implementation of network puzzles

paper_content:

Client puzzles have been proposed in a number of protocols as a mechanism for mitigating the effects of distributed denial of service (DDoS) attacks. In order to provide protection against simultaneous attacks across a wide range of applications and protocols, however, such puzzles must be placed at a layer common to all of them; the network layer. Placing puzzles at the IP layer fundamentally changes the service paradigm of the Internet, allowing any device within the network to push load back onto those it is servicing. An advantage of network layer puzzles over previous puzzle mechanisms is that they can be applied to all traffic from malicious clients, making it possible to defend against arbitrary attacks as well as making previously voluntary mechanisms mandatory. In this paper, we outline goals which must be met for puzzles to be deployed effectively at the network layer. We then describe the design, implementation, and evaluation of a system that meets these goals by supporting efficient, fine-grained control of puzzles at the network layer. In particular, we describe modifications to existing puzzle protocols that allow them to work at the network layer, a hint-based hash-reversal puzzle that allows for the generation and verification of fine-grained puzzles at line speed in the fast path of high-speed routers, and an iptables implementation that supports transparent deployment at arbitrary locations in the network.
---
paper_title: "Proof-of-Work" Proves Not to Work

paper_content:

A frequently proposed method of reducing unsolicited bulk email (\spam") is for senders to pay for each email they send. Proof-of- work schemes avoid charging real money by requiring senders to demon- strate that they have expended processing time in solving a crypto- graphic puzzle. We attempt to determine how di-cult that puzzle should be so as to be efiective in preventing spam. We analyse this both from an economic perspective, \how can we stop it being cost-efiective to send spam", and from a security perspective, \spammers can access insecure end-user machines and will steal processing cycles to solve puzzles". Both analyses lead to similar values of puzzle di-culty. Unfortunately, real- world data from a large ISP shows that these di-culty levels would mean that signiflcant numbers of senders of legitimate email would be unable to continue their current levels of activity. We conclude that proof-of-work will not be a solution to the problem of spam.
---
paper_title: Defending against denial-of-service attacks with puzzle auctions

paper_content:

Although client puzzles represent a promising approach to defend against certain classes of denial-of-service attacks, several questions stand in the way of their deployment in practice: e.g., how to set the puzzle difficulty in the presence of an adversary with unknown computing power, and how to integrate the approach with existing mechanisms. In this paper, we attempt to address these questions with a new puzzle mechanism called the puzzle auction. Our mechanism enables each client to "bid" for resources by tuning the difficulty of the puzzles it solves, and to adapt its bidding strategy in response to apparent attacks. We analyze the effectiveness of our auction mechanism and further demonstrate it using an implementation within the TCP protocol stack of the Linux kernel. Our implementation has several appealing properties. It effectively defends against SYN flooding attacks, is fully compatible with TCP, and even provides a degree of interoperability with clients with unmodified kernels: Even without a puzzle-solving kernel, a client still can connect to a puzzle auction server under attack (albeit less effectively than those with puzzle-solving kernels, and at the cost of additional server expense).
---
paper_title: DOS-Resistant Authentication with Client Puzzles

paper_content:

Denial of service by server resource exhaustion has become a major security threat in open communications networks. Public-key authentication does not completely protect against the attacks because the authentication protocols often leave ways for an unauthenticated client to consume a server's memory space and computational resources by initiating a large number of protocol runs and inducing the server to perform expensive cryptographic computations. We show how stateless authentication protocols and the client puzzles of Juels and Brainard can be used to prevent such attacks.
---
paper_title: Mitigating bandwidth-exhaustion attacks using congestion puzzles

paper_content:

We present congestion puzzles (CP), a new countermeasure to bandwidth-exhaustion attacks. Like other defenses based on client puzzles, CP attempts to force attackers to invest vast resources in order to effectively perform denial-of-service attacks. Unlike previous puzzle-based approaches, however, ours is the first designed for the bandwidth-exhaustion attacks that are common at the network (IP) layer. At the core of CP is an elegant distributed puzzle mechanism that permits routers to cooperatively impose and check puzzles. We demonstrate through analysis and simulation that CP can effectively defend networks from flooding attacks without relying on the formulation of attack signatures to filter traffic. Moreover, as many such attacks are conducted by "zombie" computers that have been silently commandeered without the knowledge of their owners, the overheads that CP imposes on heavily engaged zombies can increase the likelihood that the computer's owner detects the compromise and takes action to remedy it.
---
paper_title: Towards Denial-of-Service-Resilient Key Agreement Protocols

paper_content:

Denial of service resilience is an important practical consideration for key agreement protocols in any hostile environment such as the Internet. There are well-known models that consider the security of key agreement protocols, but denial of service resilience is not considered as part of these models. Many protocols have been argued to be denial-of-service-resilient, only to be subsequently broken or shown ineffective. ::: ::: In this work we propose a formal definition of denial of service resilience, a model for secure authenticated key agreement, and show how security and denial of service resilience can be considered in a common framework, with a particular focus on client puzzles. The model accommodates a variety of techniques for achieving denial of service resilience, and we describe one such technique by exhibiting a denial-of-service-resilient secure authenticated key agreement protocol. Our approach addresses the correct integration of denial of service countermeasures with the key agreement protocol to prevent hijacking attacks that would otherwise render the countermeasures irrelevant.
---
paper_title: Majority Is Not Enough: Bitcoin Mining Is Vulnerable

paper_content:

The Bitcoin cryptocurrency records its transactions in a public log called the blockchain. Its security rests critically on the distributed protocol that maintains the blockchain, run by participants called miners. Conventional wisdom asserts that the mining protocol is incentive-compatible and secure against colluding minority groups, that is, it incentivizes miners to follow the protocol as prescribed.
---
paper_title: The Sybil Attack

paper_content:

Large-scale peer-to-peer systems face security threats from faulty or hostile remote computing elements. To resist these threats, many such systems employ redundancy. However, if a single faulty entity can present multiple identities, it can control a substantial fraction of the system, thereby undermining this redundancy. One approach to preventing these "Sybil attacks" is to have a trusted agency certify identities. This paper shows that, without a logically centralized authority, Sybil attacks are always possible except under extreme and unrealistic assumptions of resource parity and coordination among entities.
---
paper_title: Nonoutsourceable Scratch-Off Puzzles to Discourage Bitcoin Mining Coalitions

paper_content:

An implicit goal of Bitcoin's reward structure is to diffuse network influence over a diverse, decentralized population of individual participants. Indeed, Bitcoin's security claims rely on no single entity wielding a sufficiently large portion of the network's overall computational power. Unfortunately, rather than participating independently, most Bitcoin miners join coalitions called mining pools in which a central pool administrator largely directs the pool's activity, leading to a consolidation of power. Recently, the largest mining pool has accounted for more than half of network's total mining capacity. Relatedly, "hosted mining" service providers offer their clients the benefit of economies-of-scale, tempting them away from independent participation. We argue that the prevalence of mining coalitions is due to a limitation of the Bitcoin proof-of-work puzzle -- specifically, that it affords an effective mechanism for enforcing cooperation in a coalition. We present several definitions and constructions for "nonoutsourceable" puzzles that thwart such enforcement mechanisms, thereby deterring coalitions. We also provide an implementation and benchmark results for our schemes to show they are practical.
---
paper_title: Proofs of Space

paper_content:

Proofs of work (PoW) have been suggested by Dwork and Naor (Crypto’92) as protection to a shared resource. The basic idea is to ask the service requestor to dedicate some non-trivial amount of computational work to every request. The original applications included prevention of spam and protection against denial of service attacks. More recently, PoWs have been used to prevent double spending in the Bitcoin digital currency system.
---
paper_title: Analysis of the Blockchain Protocol in Asynchronous Networks

paper_content:

Nakamoto’s famous blockchain protocol enables achieving consensus in a so-called permissionless setting—anyone can join (or leave) the protocol execution, and the protocol instructions do not depend on the identities of the players. His ingenious protocol prevents “sybil attacks” (where an adversary spawns any number of new players) by relying on computational puzzles (a.k.a. “moderately hard functions”) introduced by Dwork and Naor (Crypto’92).
---
paper_title: SoK: Research Perspectives and Challenges for Bitcoin and Cryptocurrencies

paper_content:

Bit coin has emerged as the most successful cryptographic currency in history. Within two years of its quiet launch in 2009, Bit coin grew to comprise billions of dollars of economic value despite only cursory analysis of the system's design. Since then a growing literature has identified hidden-but-important properties of the system, discovered attacks, proposed promising alternatives, and singled out difficult future challenges. Meanwhile a large and vibrant open-source community has proposed and deployed numerous modifications and extensions. We provide the first systematic exposition Bit coin and the many related crypto currencies or 'altcoins.' Drawing from a scattered body of knowledge, we identify three key components of Bit coin's design that can be decoupled. This enables a more insightful analysis of Bit coin's properties and future stability. We map the design space for numerous proposed modifications, providing comparative analyses for alternative consensus mechanisms, currency allocation mechanisms, computational puzzles, and key management tools. We survey anonymity issues in Bit coin and provide an evaluation framework for analyzing a variety of privacy-enhancing proposals. Finally we provide new insights on what we term disinter mediation protocols, which absolve the need for trusted intermediaries in an interesting set of applications. We identify three general disinter mediation strategies and provide a detailed comparison.
---
paper_title: The Bitcoin Backbone Protocol: Analysis and Applications

paper_content:

Bitcoin is the first and most popular decentralized cryptocurrency to date. In this work, we extract and analyze the core of the Bitcoin protocol, which we term the Bitcoin backbone, and prove two of its fundamental properties which we call common prefix and chain quality in the static setting where the number of players remains fixed. Our proofs hinge on appropriate and novel assumptions on the “hashing power” of the adversary relative to network synchronicity; we show our results to be tight under high synchronization.
---
paper_title: Making Peer-Assisted Content Distribution Robust to Collusion Using Bandwidth Puzzles

paper_content:

Many peer-assisted content-distribution systems reward a peer based on the amount of data that this peer serves to others. However, validating that a peer did so is, to our knowledge, an open problem; e.g., a group of colluding attackers can earn rewards by claiming to have served content to one another, when they have not. We propose a puzzle mechanism to make contribution-aware peer-assisted content distribution robust to such collusion. Our construction ties solving the puzzle to possession of specific content and, by issuing puzzle challenges simultaneously to all parties claiming to have that content, our mechanism prevents one content-holder from solving many others' puzzles. We prove (in the random oracle model) the security of our scheme, describe our integration of bandwidth puzzles into a media streaming system, and demonstrate the resulting attack resilience via simulations.
---
paper_title: Bandwidth Hard Functions for ASIC Resistance

paper_content:

Cryptographic hash functions have wide applications including password hashing, pricing functions for spam and denial-of-service countermeasures and proof of work in cryptocurrencies. Recent progress on ASIC (Application Specific Integrated Circuit) hash engines raise concerns about the security of the above applications. This leads to a growing interest in ASIC resistant hash function and ASIC resistant proof of work schemes, i.e., those that do not give ASICs a huge advantage. The standard approach towards ASIC resistance today is through memory hard functions or memory hard proof of work schemes. However, we observe that the memory hardness approach is an incomplete solution. It only attempts to provide resistance to an ASIC’s area advantage but overlooks the more important energy advantage. In this paper, we propose the notion of bandwidth hard functions to reduce an ASIC’s energy advantage. CPUs cannot compete with ASICs for energy efficiency in computation, but we can rely on memory accesses to reduce an ASIC’s energy advantage because energy costs of memory accesses are comparable for ASICs and CPUs. We propose a model for hardware energy cost that has sound foundations in practice. We then analyze the bandwidth hardness property of ASIC resistant candidates. We find scrypt, Catena-BRG and Balloon are bandwidth hard with suitable parameters. Lastly, we observe that a capacity hard function is not necessarily bandwidth hard, with a stacked double butterfly graph being a counterexample.
---
paper_title: Computational Puzzles as Sybil Defenses

paper_content:

We consider the problem of defending against Sybil attacks using computational puzzles. A fundamental difficulty in such defenses is enforcing that puzzle solutions not be reused by attackers over time. We propose a fully decentralized scheme to enforce this by continually distributing locally generated challenges that are then incorporated into the puzzle solutions. Our approach consists of an all-to-all broadcast of challenges, with a combining function to ensure this can be done efficiently. The combining function generates certificates that can be used to prove that each node's challenge was delivered to and used by each other node, therefore proving the freshness of each puzzle. We show how our distribution and verification mechanisms can be implemented on top of the the Chord in Stoica et al., (2001) overlay
---
paper_title: Proofs of Work From Worst-Case Assumptions

paper_content:

We give Proofs of Work (PoWs) whose hardness is based on well-studied worst-case assumptions from fine-grained complexity theory. This extends the work of (Ball et al., STOC ’17), that presents PoWs that are based on the Orthogonal Vectors, 3SUM, and All-Pairs Shortest Path problems. These, however, were presented as a ‘proof of concept’ of provably secure PoWs and did not fully meet the requirements of a conventional PoW: namely, it was not shown that multiple proofs could not be generated faster than generating each individually. We use the considerable algebraic structure of these PoWs to prove that this non-amortizability of multiple proofs does in fact hold and further show that the PoWs’ structure can be exploited in ways previous heuristic PoWs could not.
---
paper_title: A Survey on Consensus Mechanisms and Mining Management in Blockchain Networks.

paper_content:

The past decade has witnessed the rapid evolution in blockchain technologies, which has attracted tremendous interests from both the research communities and the industry. The blockchain network was originated in the Internet finical sector as a decentralized, immutable ledger system for transactional data ordering. Nowadays, it is envisioned as a powerful backbone/framework for decentralized data processing and data-driven self-organization in flat, open-access networks. In particular, the plausible characteristics of decentralization, immutability and self-organization are primarily owing to the unique decentralized consensus mechanisms introduced by blockchain networks. This survey is motivated by the lack of a comprehensive literature review on the development of decentralized consensus mechanisms in blockchain networks. In this survey, we provide a systematic vision of the organization of blockchain networks. By emphasizing the unique characteristics of incentivized consensus in blockchain networks, our in-depth review of the state-of-the-art consensus protocols is focused on both the perspective of distributed consensus system design and the perspective of incentive mechanism design. From a game-theoretic point of view, we also provide a thorough review on the strategy adoption for self-organization by the individual nodes in the blockchain backbone networks. Consequently, we provide a comprehensive survey on the emerging applications of the blockchain networks in a wide range of areas. We highlight our special interest in how the consensus mechanisms impact these applications. Finally, we discuss several open issues in the protocol design for blockchain consensus and the related potential research directions.
---
paper_title: Blockchain world - Feeding the blockchain beast if bitcoin ever does go mainstream, the electricity needed to sustain it will be enormous

paper_content:

Bitcoin "miners" are electromagnetic alchemists, effectively turning megawatt-hours of electricity into the world's fastest-growing currency. Their intensive computational activity cryptographically secures the virtual currency, approves transactions, and, in the process, creates new bitcoins for the miners, as payment. And it does another thing, too: It uses an absolutely stunning amount of power. The ever-expanding racks of processors used by miners already consume as much electricity as a small city. It's a problem that experts say is bad and getting worse. "The concern that people continue to debate is, where does this end?" says Michael Reed, head of blockchain technology for Intel. The Bitcoin leech sucking on the world's power grids has been held in check, so far, by rapid gains in the energy efficiency of mining hardware. But energy and blockchain analysts are worried about the possibility of a perfect storm: Those efficiency gains are slowing while bitcoin value is rising fast-and its potential transaction growth is immense.
---
paper_title: SybilControl: practical sybil defense with computational puzzles

paper_content:

Many distributed systems are subject to the Sybil attack, where an adversary subverts system operation by emulating the behavior of multiple distinct nodes. Most recent works addressing this problem leverage social networks to establish trust relationships between users. However, social networks are not appropriate in all systems. They can be subverted by social engineering techniques, require nodes to maintain and be aware of social network information, and may require overly optimistic assumptions about the fast-mixing nature of social links. This paper explores an alternate approach. We present SybilControl, a novel decentralized scheme for controlling the extent of Sybil attacks. It is an admission and retainment control scheme for nodes in a distributed system that requires them to periodically solve computational puzzles. SybilControl consists of a distributed protocol to allow nodes to collectively verify the computational work of other nodes, and mechanisms to prevent the malicious influence of misbehaving nodes that do not perform the computational work. We investigate the practical issues involved with deploying SybilControl into existing DHTs, particularly with handling churn. SybilControl is shown to provide strict bounds on the size of Sybil attacks, given adversaries with finite resources. We also show through simulations that the performance overhead of enabling SybilControl is manageable using commonplace DHT churn-handling techniques. This provides strong evidence that SybilControl can be practically deployed.
---
paper_title: Limiting Sybil Attacks in Structured P2P Networks

paper_content:

One practical limitation of structured peer-to-peer (P2P) networks is that they are frequently subject to Sybil attacks: malicious parties can compromise the network by generating and controlling large numbers of shadow identities. In this paper, we propose an admission control system that mitigates Sybil attacks by adaptively constructing a hierarchy of cooperative peers. The admission control system vets joining nodes via client puzzles. A node wishing to join the network is serially challenged by the nodes from a leaf to the root of the hierarchy. Nodes completing the puzzles of all nodes in the chain are provided a cryptographic proof of the vetted identity. We evaluate our solution and show that an adversary must perform days or weeks of effort to obtain even a small percentage of nodes in small P2P networks, and that this effort increases linearly with the size of the network. We further show that we can place a ceiling on the number of IDs any adversary may obtain by requiring periodic reassertion of the IDs continued validity.
---
paper_title: Permacoin: Repurposing Bitcoin Work for Data Preservation

paper_content:

Bit coin is widely regarded as the first broadly successful e-cash system. An oft-cited concern, though, is that mining Bit coins wastes computational resources. Indeed, Bit coin's underlying mining mechanism, which we call a scratch-off puzzle (SOP), involves continuously attempting to solve computational puzzles that have no intrinsic utility. We propose a modification to Bit coin that repurposes its mining resources to achieve a more broadly useful goal: distributed storage of archival data. We call our new scheme Perm coin. Unlike Bit coin and its proposed alternatives, Perm coin requires clients to invest not just computational resources, but also storage. Our scheme involves an alternative scratch-off puzzle for Bit coin based on Proofs-of-Retrievability (PORs). Successfully minting money with this SOP requires local, random access to a copy of a file. Given the competition among mining clients in Bit coin, this modified SOP gives rise to highly decentralized file storage, thus reducing the overall waste of Bit coin. Using a model of rational economic agents we show that our modified SOP preserves the essential properties of the original Bit coin puzzle. We also provide parameterizations and calculations based on realistic hardware constraints to demonstrate the practicality of Perm coin as a whole.
---
paper_title: Bitcoin and Beyond: A Technical Survey on Decentralized Digital Currencies

paper_content:

Besides attracting a billion dollar economy, Bitcoin revolutionized the field of digital currencies and influenced many adjacent areas. This also induced significant scientific interest. In this survey, we unroll and structure the manyfold results and research directions. We start by introducing the Bitcoin protocol and its building blocks. From there we continue to explore the design space by discussing existing contributions and results. In the process, we deduce the fundamental structures and insights at the core of the Bitcoin protocol and its applications. As we show and discuss, many key ideas are likewise applicable in various other fields, so that their impact reaches far beyond Bitcoin itself.
---
paper_title: Designing Proof of Human-Work Puzzles for Cryptocurrency and Beyond

paper_content:

We introduce the novel notion of a Proof of Human-work PoH and present the first distributed consensus protocol from hard Artificial Intelligence problems. As the name suggests, a PoH is a proof that a human invested a moderate amount of effort to solve some challenge. A PoH puzzle should be moderately hard for a human to solve. However, a PoH puzzle must be hard for a computer to solve, including the computer that generated the puzzle, without sufficient assistance from a human. By contrast, CAPTCHAs are only difficult for other computers to solve -- not for the computer that generated the puzzle. We also require that a PoH be publicly verifiable by a computer without any human assistance and without ever interacting with the agent who generated the proof of human-work. We show how to construct PoH puzzles from indistinguishability obfuscation and from CAPTCHAs. We motivate our ideas with two applications: HumanCoin and passwords. We use PoH puzzles to construct HumanCoin, the first cryptocurrency system with human miners. Second, we use proofs of human work to develop a password authentication scheme which provably protects users against offline attacks.
---
paper_title: On Power Splitting Games in Distributed Computation: The Case of Bitcoin Pooled Mining

paper_content:

Several new services incentivize clients to compete in solving large computation tasks in exchange for financial rewards. This model of competitive distributed computation enables every user connected to the Internet to participate in a game in which he splits his computational power among a set of competing pools -- the game is called a computational power splitting game. We formally model this game and show its utility in analyzing the security of pool protocols that dictate how financial rewards are shared among the members of a pool. As a case study, we analyze the Bitcoin crypto currency which attracts computing power roughly equivalent to billions of desktop machines, over 70% of which is organized into public pools. We show that existing pool reward sharing protocols are insecure in our game-theoretic analysis under an attack strategy called the "block withholding attack". This attack is a topic of debate, initially thought to be ill-incentivized in today's pool protocols: i.e., causing a net loss to the attacker, and later argued to be always profitable. Our analysis shows that the attack is always well-incentivized in the long-run, but may not be so for a short duration. This implies that existing pool protocols are insecure, and if the attack is conducted systematically, Bitcoin pools could lose millions of dollars worth in months. The equilibrium state is a mixed strategy -- that is -- in equilibrium all clients are incentivized to probabilistically attack to maximize their payoffs rather than participate honestly. As a result, the Bitcoin network is incentivized to waste a part of its resources simply to compete.
---
paper_title: An Auditable Metering Scheme for Web Advertisement Applications

paper_content:

This paper proposes a cryptographic scheme for metering the duration and/or the number of instances of running a process. This scheme has the following property: knowing a secret, one can validate a piece of metering evidence in constant units of time while without the secret the job of generating a valid piece of evidence requires time indicated by the evidence. Because the scheme utilises a well-known computational complexity problem, the meter based on it can be implemented in software yet is tamper-resistant.We will address the use of this scheme in building an auditable metering scheme for finding the popularity of web sites. The scheme is suitable for rapidly increasing web advertisement applications. We will also discuss the related security issues.
---
paper_title: A software infrastructure for authenticated Web metering

paper_content:

As the popularity of the Internet and the number of resources available on it have grown, potential customers are increasingly turning to it for information about products and services. Accordingly, online advertising is gaining a significant portion of the advertising market. The Internet has become a mainstream advertising channel, surpassing traditional media such as newspapers and radio in number of advertisements. Advertisers exploit the popularity of the best-known Web sites, typically search engines or portals, to advertise their products and reach the most potential customers. Traditional rating systems are of little value when applied to the Internet because of the enormous number of Web pages available to online advertisements. Counting accesses to a Web service is a difficult task and the data may be unreliable. Several metering techniques attempt to accurately measure the number of visits a site receives and hence the advertising exposure, but advertisers and auditing companies haven't adopted a standard technique. We propose a framework based on hash chains. Unlike similar approaches, our implementation minimizes the overhead associated with the additional communication required to implement the protocol while providing an efficient and flexible scheme. Furthermore, the resulting framework offers additional guarantees such as security and nonrepudiation of the produced proof of visits.
---
paper_title: Towards uncheatable benchmarks

paper_content:

The problem of how to make benchmarks resistant to tampering and hence more trustworthy is studied. Some schemes that are based on modern cryptography and complexity theory are proposed to make benchmarks uncheatable. The philosophy is the same as that of encryption-decryption schemes, namely, that trust in individuals and organizations is replaced by trust in the impossibility of breaking certain computational problems. >
---
paper_title: Making benchmarks uncheatable

paper_content:

The industry is full of anecdotes of benchmark "cheating" of various degrees ranging from innocent mistakes to flagrant misuse. Based on the tremendous progress made in recent years in theoretical computer science, it becomes possible to make a wide variety of existing benchmarks more accurate, resistant to tampering and more trustworthy. We propose two methods, the Secret Key method and the result verification method, to take computational advantage in judging performance claims. A realtime measurement method is also proposed to prevent cheating on performance reporting. The design and implementation of uncheatable benchmarks are presented in this paper.
---
paper_title: Pseudonymous Secure Computation from Time-Lock Puzzles.

paper_content:

In standard models of secure computation, point-to-point channels between parties are assumed to be authenticated by some pre-existing means. In other cases, even stronger pre-existing setup—e.g., a public-key infrastructure (PKI)—is assumed. These assumptions are too strong for open, peer-to-peer networks, where parties do not necessarily have any prior relationships and can come and go as they please. Nevertheless, these assumptions are made due to the prevailing belief that nothing “interesting” can be achieved without them. Taking inspiration from Bitcoin, we show that precise bounds on computational power can be used in place of pre-existing setup to achieve weaker (but nontrivial) notions of security. Specifically, under the assumptions that digital signatures exist and each party can solve cryptographic “time-lock” puzzles only at a bounded rate, we show that without prior setup and with no bound on the number of corruptions, a group of parties can agree on a PKI with which they can then realize pseudonymous notions of authenticated communication, broadcast, and secure computation. Roughly, “pseudonymous” here means that inputs/outputs are (effectively) bound to pseudonyms rather than parties’ true identities.
---
paper_title: Publicly verifiable proofs of sequential work

paper_content:

We construct a publicly verifiable protocol for proving computational work based on collision-resistant hash functions and a new plausible complexity assumption regarding the existence of "inherently sequential" hash functions. Our protocol is based on a novel construction of time-lock puzzles. Given a sampled "puzzle" P getsr Dn, where $n$ is the security parameter and Dn is the distribution of the puzzles, a corresponding "solution" can be generated using N evaluations of the sequential hash function, where N>n is another parameter, while any feasible adversarial strategy for generating valid solutions must take at least as much time as Ω(N) serial evaluations of the hash function after receiving $P$. Thus, valid solutions constitute a "proof" that Ω(N) parallel time elapsed since p was received. Solutions can be publicly and efficiently verified in time poly(n) ⋅ polylog(N). Applications of these "time-lock puzzles" include noninteractive timestamping of documents (where the distribution over the possible documents corresponds to the puzzle distribution Dn) and universally verifiable CPU benchmarks. Our construction is secure in the standard model under complexity assumptions (collision-resistant hash functions and inherently sequential hash functions), and makes black-box use of the underlying primitives. Consequently, the corresponding construction in the random oracle model is secure unconditionally. Moreover, as it is a public-coin protocol, it can be made non-interactive in the random oracle model using the Fiat-Shamir Heuristic. Our construction makes a novel use of "depth-robust" directed acyclic graphs---ones whose depth remains large even after removing a constant fraction of vertices---which were previously studied for the purpose of complexity lower-bounds. The construction bypasses a recent lower-bound of Mahmoody, Moran, and Vadhan (CRYPTO '11) for time-lock puzzles in the random oracle model, which showed that it is impossible to have time-lock puzzles like ours in the random oracle model if the puzzle generator also computes a solution together with the puzzle.
---
paper_title: Simple Verifiable Delay Functions.

paper_content:

We construct a verifiable delay function (VDF) by showing how the Rivest-Shamir-Wagner time-lock puzzle can be made publicly verifiable. Concretely, we give a statistically sound public-coin protocol to prove that a tuple (N,x,T,y) satisfies y=x2T (mod N) where the prover doesn’t know the factorization of N and its running time is dominated by solving the puzzle, that is, compute x2T, which is conjectured to require T sequential squarings. To get a VDF we make this protocol non-interactive using the Fiat-Shamir heuristic.The motivation for this work comes from the Chia blockchain design, which uses a VDF as akey ingredient. For typical parameters (T≤2 40, N= 2048), our proofs are of size around 10K B, verification cost around three RSA exponentiations and computing the proof is 8000 times faster than solving the puzzle even without any parallelism.
---
paper_title: Offline Submission with RSA Time-Lock Puzzles

paper_content:

We introduce a non-interactive RSA time-lock puzzle scheme whose level of difficulty can be arbitrarily chosen by artificially enlarging the public exponent. Solving a puzzle for a message m means for Bob to encrypt m with Alice's public puzzle key by repeated modular squaring. The number of squarings to perform determines the puzzle complexity. This puzzle is non-parallelizable. Thus, the solution time cannot be shortened significantly by employing many machines and it varies only slightly across modern CPUs. Alice can quickly verify the puzzle solution by decrypting the ciphertext with a regular private key operation. Our main contribution is an offline submission protocol which enables an author being currently offline to commit to his document before the deadline by continuously solving an RSA puzzle based on that document. When regaining Internet connectivity, he submits his document along with the puzzle solution which is a proof for the timely completion of the document. We have implemented a platform-independent tool performing all parts of our offline submission protocol: puzzle benchmark, issuing a time-lock RSA certificate, solving a puzzle and finally verifying the solution for a submitted document. Two other applications we propose for RSA time-lock puzzles are trial certificates from a well-known CA and a CEO disclosing the signing private key to his deputy.
---
paper_title: Forgetting with Puzzles: Using Cryptographic Puzzles to support Digital Forgetting

paper_content:

Digital forgetting deals with the unavailability of content uploaded to web and storage servers after the data has served its purpose. The content on the servers can be deleted manually, but this does not prevent data archival and access at different storage locations. This is problematic since then the data may be accessed for unintended or even malicious purposes long after the owners have decided to abandon the public availability of their data. Approaches which assign a lifetime value to data or use heuristics like interest in data to make it inaccessible after some time have been proposed, but digital forgetting is still in its infancy and there are a number of open problems with the proposed approaches. In this paper, we outline a general use case of cryptographic puzzles in the context of digital forgetting which---to the best of our knowledge---has not been proposed or explored before. One problem with recent proposals for digital forgetting is that attackers could collect or even delete anyone's public data during their lifetime. In our approach, we deal with these problems by making it hard for the attacker to delete large quantities of data while making sure that the proposed solutions will not adversely deteriorate user experience in a disturbing manner. As a proof-of-concept, we propose a system with cryptographic (time-lock) puzzles that deals with malicious users while ensuring the permanent deletion of data when interest in it dies down. We have implemented a prototype and evaluate it thoroughly with promising results.
---
paper_title: Simple Proofs of Sequential Work

paper_content:

At ITCS 2013, Mahmoody, Moran and Vadhan [MMV13] introduce and construct publicly verifiable proofs of sequential work, which is a protocol for proving that one spent sequential computational work related to some statement. The original motivation for such proofs included non-interactive time-stamping and universally verifiable CPU benchmarks. A more recent application, and our main motivation, are blockchain designs, where proofs of sequential work can be used – in combination with proofs of space – as a more ecological and economical substitute for proofs of work which are currently used to secure Bitcoin and other cryptocurrencies.
---
paper_title: Verifiable Delay Functions

paper_content:

We study the problem of building a verifiable delay function (VDF). A \(\text {VDF}\)requires a specified number of sequential steps to evaluate, yet produces a unique output that can be efficiently and publicly verified. \(\text {VDF}\)s have many applications in decentralized systems, including public randomness beacons, leader election in consensus protocols, and proofs of replication. We formalize the requirements for \(\text {VDF}\)s and present new candidate constructions that are the first to achieve an exponential gap between evaluation and verification time.
---
paper_title: Two-Round and Non-Interactive Concurrent Non-Malleable Commitments from Time-Lock Puzzles

paper_content:

Non-malleable commitments are a fundamental cryptographic tool for preventing (concurrent) man-in-the-middle attacks. Since their invention by Dolev, Dwork, and Naor in 1991, their round-complexity...
---
paper_title: Time-lock puzzles and timed-release crypto

paper_content:

Our motivation is the notion of ``timed-release crypto,'''' where the goal is to encrypt a message so that it can not be decrypted by anyone, not even the sender, until a pre-determined amount of time has passed. The goal is to ``send information into the future.'''' This problem was first discussed by Timothy May \cite{May93}. What are the applications of ``timed-release crypto''''? Here are a few possibilities (some due to May): A bidder in an auction wants to seal his bid so that it can only be opened after the bidding period is closed. A homeowner wants to give his mortgage holder a series of encrypted mortgage payments. These might be encrypted digital cash with different decryption dates, so that one payment becomes decryptable (and thus usable by the bank) at the beginning of each successive month. An individual wants to encrypt his diaries so that they are only decryptable after fifty years. A key-escrow scheme can be based on timed-release crypto, so that the government can get the message keys, but only after a fixed period (say one year). \ There are presumably many other applications. There are two natural approaches to implementing timed-release crypto: Use ``time-lock puzzles''''--computational problems that can not be solved without running a computer continuously for at least a certain amount of time. Use trusted agents who promise not to reveal certain information until a specified date. Using trusted agents has the obvious problem of ensuring that the agents are trustworthy; secret-sharing approaches can be used to alleviate this concern. Using time-lock puzzles has the problem that the CPU time required to solve a problem can depend on the amount and nature of the hardware used to solve the problem, as well as the parallelizability of the computational problem being solved. In this note we explore both approaches. (We note that Tim May has suggested an approach based on the use of trusted agents.)
---
paper_title: FaceDCAPTCHA: Face detection based color image CAPTCHA

paper_content:

With data theft and computer break-ins becoming increasingly common, there is a great need for secondary authentication to reduce automated attacks while posing a minimal hindrance to legitimate users. CAPTCHA is one of the possible ways to classify human users and automated scripts. Though text-based CAPTCHAs are used in many applications, they pose a challenge due to language dependency. In this paper, we propose a face image-based CAPTCHA as a potential solution. To solve the CAPTCHA, users must correctly identify visually-distorted human faces embedded in a complex background without selecting any non-human faces. The proposed algorithm generates a CAPTCHA that offers better human accuracy and lower machine attack rates compared to existing approaches.
---
paper_title: Constructing Secure Audio CAPTCHAs by Exploiting Differences between Humans and Machines

paper_content:

To prevent abuses of Internet services, CAPTCHAs are used to distinguish humans from programs where an audio-based scheme is beneficial to support visually impaired people. Previous studies show that most audio CAPTCHAs, albeit hard to solve for humans, are lacking security strength. In this work we propose an audio CAPTCHA that is far more robust against automated attacks than it is reported for current CAPTCHA schemes. The CAPTCHA exhibits a good trade-off between human usability and security. This is achieved by exploiting the fact that the human capabilities of language understanding and speech recognition are clearly superior compared to current machines. We evaluate the CAPTCHA security by using a state-of-the-art attack and assess the intelligibility by means of a large-scale listening experiment.
---
paper_title: Re: CAPTCHAs-Understanding CAPTCHA-Solving Services in an Economic Context

paper_content:

Reverse Turing tests, or CAPTCHAs, have become an ubiquitous defense used to protect open Web resources from being exploited at scale. An effective CAPTCHA resists existing mechanistic software solving, yet can be solved with high probability by a human being. In response, a robust solving ecosystem has emerged, reselling both automated solving technology and realtime human labor to bypass these protections. Thus, CAPTCHAs can increasingly be understood and evaluated in purely economic terms; the market price of a solution vs the monetizable value of the asset being protected. We examine the market-side of this question in depth, analyzing the behavior and dynamics of CAPTCHA-solving service providers, their price performance, and the underlying labor markets driving this economy.
---
paper_title: The SoundsRight CAPTCHA: an improved approach to audio human interaction proofs for blind users

paper_content:

In this paper we describe the development of a new audio CAPTCHA called the SoundsRight CAPTCHA, and the evaluation of the CAPTCHA with 20 blind users. Blind users cannot use visual CAPTCHAs, and it has been documented in the research literature that the existing audio CAPTCHAs have task success rates below 50% for blind users. The SoundsRight audio CAPTCHA presents a real-time audio-based challenge in which the user is asked to identify a specific sound (for example the sound of a bell or a piano) each time it occurs in a series of 10 sounds that are played through the computer's audio system. Evaluation results from three rounds of usability testing document that the task success rate was higher than 90% for blind users. Discussion, limitations, and suggestions for future research are also presented.
---
paper_title: The end is nigh: generic solving of text-based CAPTCHAs

paper_content:

Over the last decade, it has become well-established that a captcha's ability to withstand automated solving lies in the difficulty of segmenting the image into individual characters. The standard approach to solving captchas automatically has been a sequential process wherein a segmentation algorithm splits the image into segments that contain individual characters, followed by a character recognition step that uses machine learning. While this approach has been effective against particular captcha schemes, its generality is limited by the segmentation step, which is hand-crafted to defeat the distortion at hand. No general algorithm is known for the character collapsing anti-segmentation technique used by most prominent real world captcha schemes. ::: ::: This paper introduces a novel approach to solving captchas in a single step that uses machine learning to attack the segmentation and the recognition problems simultaneously. Performing both operations jointly allows our algorithm to exploit information and context that is not available when they are done sequentially. At the same time, it removes the need for any hand-crafted component, making our approach generalize to new captcha schemes where the previous approach can not. We were able to solve all the real world captcha schemes we evaluated accurately enough to consider the scheme insecure in practice, including Yahoo (5.33%) and ReCaptcha (33.34%), without any adjustments to the algorithm or its parameters. Our success against the Baidu (38.68%) and CNN (51.09%) schemes that use occluding lines as well as character collapsing leads us to believe that our approach is able to defeat occluding lines in an equally general manner. The effectiveness and universality of our results suggests that combining segmentation and recognition is the next evolution of catpcha solving, and that it supersedes the sequential approach used in earlier works. More generally, our approach raises questions about how to develop sufficiently secure captchas in the future.
---
paper_title: CAPTCHAs: An Artificial Intelligence Application to Web Security

paper_content:

Abstract Nowadays, it is hard to find a popular Web site with a registration form that is not protected by an automated human proof test which displays a sequence of characters in an image, and requests the user to enter the sequence into an input field. This security mechanism is based on the Turing Test—one of the oldest concepts in Artificial Intelligence—and it is most often called Completely Automated Public Turing test to tell Computers and Humans Apart (CAPTCHA). This kind of test has been conceived to prevent the automated access to an important Web resource, for example, a Web mail service or a Social Network. There are currently hundreds of these tests, which are served millions of times a day, thus involving a huge amount of human work. On the other side, a number of these tests have been broken, that is, automated programs designed by researchers, hackers, and spammers have been able to automatically serve the correct answer. In this chapter, we present the history and the concept of CAPTCHAs, along with their applications and a wide review of their instantiations. We also discuss their evaluation, both from the user and the security perspectives, including usability, attacks, and countermeasures. We expect this chapter provides to the reader a good overview of this interesting field.
---
paper_title: PessimalPrint: a reverse Turing test

paper_content:

Abstract. We exploit the gap in ability between human and machine vision systems to craft a family of automatic challenges that tell human and machine users apart via graphical interfaces including Internet browsers. Turing proposed [Tur50] a method whereby human judges might validate “artificial intelligence” by failing to distinguish between human and machine interlocutors. Stimulated by the “chat room problem” posed by Udi Manber of Yahoo!, and influenced by the CAPTCHA project [BAL00] of Manuel Blum et al. of Carnegie-Mellon Univ., we propose a variant of the Turing test using pessimal print: that is, low-quality images of machine-printed text synthesized pseudo-randomly over certain ranges of words, typefaces, and image degradations. We show experimentally that judicious choice of these ranges can ensure that the images are legible to human readers but illegible to several of the best present-day optical character recognition (OCR) machines. Our approach is motivated by a decade of research on performance evaluation of OCR machines [RJN96,RNN99] and on quantitative stochastic models of document image quality [Bai92,Kan96]. The slow pace of evolution of OCR and other species of machine vision over many decades [NS96,Pav00] suggests that pessimal print will defy automated attack for many years. Applications include `bot' barriers and database rationing.
---
paper_title: Recognizing objects in adversarial clutter: breaking a visual CAPTCHA

paper_content:

In this paper we explore object recognition in clutter. We test our object recognition techniques on Gimpy and EZ-Gimpy, examples of visual CAPTCHAs. A CAPTCHA ("Completely Automated Public Turing test to Tell Computers and Humans Apart") is a program that can generate and grade tests that most humans can pass, yet current computer programs can't pass. EZ-Gimpy, currently used by Yahoo, and Gimpy are CAPTCHAs based on word recognition in the presence of clutter. These CAPTCHAs provide excellent test sets since the clutter they contain is adversarial; it is designed to confuse computer programs. We have developed efficient methods based on shape context matching that can identify the word in an EZ-Gimpy image with a success rate of 92%, and the requisite 3 words in a Gimpy image 33% of the time. The problem of identifying words in such severe clutter provides valuable insight into the more general problem of object recognition in scenes. The methods that we present are instances of a framework designed to tackle this general problem.
---
paper_title: How Good Are Humans at Solving CAPTCHAs? A Large Scale Evaluation

paper_content:

Captchas are designed to be easy for humans but hard for machines. However, most recent research has focused only on making them hard for machines. In this paper, we present what is to the best of our knowledge the first large scale evaluation of captchas from the human perspective, with the goal of assessing how much friction captchas present to the average user. For the purpose of this study we have asked workers from Amazon’s Mechanical Turk and an underground captchabreaking service to solve more than 318 000 captchas issued from the 21 most popular captcha schemes (13 images schemes and 8 audio scheme). Analysis of the resulting data reveals that captchas are often difficult for humans, with audio captchas being particularly problematic. We also find some demographic trends indicating, for example, that non-native speakers of English are slower in general and less accurate on English-centric captcha schemes. Evidence from a week’s worth of eBay captchas (14,000,000 samples) suggests that the solving accuracies found in our study are close to real-world values, and that improving audio captchas should become a priority, as nearly 1% of all captchas are delivered as audio rather than images. Finally our study also reveals that it is more effective for an attacker to use Mechanical Turk to solve captchas than an underground service.
---
paper_title: Emerging Image Game CAPTCHAs for Resisting Automated and Human-Solver Relay Attacks

paper_content:

CAPTCHAs represent an important pillar in the web security domain. Yet, current CAPTCHAs do not fully meet the web security requirements. Many existing CAPTCHAs can be broken using automated attacks based on image processing and machine learning techniques. Moreover, most existing CAPTCHAs are completely vulnerable to human-solver relay attacks, whereby CAPTCHA challenges are simply outsourced to a remote human solver. In this paper, we introduce a new class of CAPTCHAs that can not only resist automated attacks but can also make relay attacks hard and detectable. These CAPTCHAs are carefully built on the notions of dynamic cognitive games (DCG) and emerging images (EI), present in the literature. While existing CAPTCHAs based on the DCG notion alone (e.g., an object matching game embedded in a clear background) are prone to automated attacks and those based on the EI notion alone (e.g., moving text embedded in emerging images) are prone to relay attacks, we show that a careful amalgamation of the two notions can resist both forms of attacks. Specifically, we formalize, design and implement a concrete instantiation of EI-DCG CAPTCHAs, and demonstrate its security with respect to image processing and object tracking techniques as well as their resistance to and detectability of relay attacks.
---
paper_title: reCAPTCHA: Human-Based Character Recognition via Web Security Measures

paper_content:

CAPTCHAs (Completely Automated Public Turing test to tell Computers and Humans Apart) are widespread security measures on the World Wide Web that prevent automated programs from abusing online services. They do so by asking humans to perform a task that computers cannot yet perform, such as deciphering distorted characters. Our research explored whether such human effort can be channeled into a useful purpose: helping to digitize old printed material by asking users to decipher scanned words from books that computerized optical character recognition failed to recognize. We showed that this method can transcribe text with a word accuracy exceeding 99%, matching the guarantee of professional human transcribers. Our apparatus is deployed in more than 40,000 Web sites and has transcribed over 440 million words.
---
paper_title: Security and Usability Challenges of Moving-Object CAPTCHAs: Decoding Codewords in Motion

paper_content:

We explore the robustness and usability of moving-image object recognition (video) captchas, designing and implementing automated attacks based on computer vision techniques. Our approach is suitable for broad classes of moving-image captchas involving rigid objects. We first present an attack that defeats instances of such a captcha (NuCaptcha) representing the state-of-the-art, involving dynamic text strings called codewords. We then consider design modifications to mitigate the attacks (e.g., overlapping characters more closely). We implement the modified captchas and test if designs modified for greater robustness maintain usability. Our lab-based studies show that the modified captchas fail to offer viable usability, even when the captcha strength is reduced below acceptable targets--signaling that the modified designs are not viable. We also implement and test another variant of moving text strings using the known emerging images idea. This variant is resilient to our attacks and also offers similar usability to commercially available approaches. We explain why fundamental elements of the emerging images concept resist our current attack where others fails.
---
paper_title: Usability of CAPTCHAs or usability issues in CAPTCHA design

paper_content:

CAPTCHA is now almost a standard security technology, and has found widespread application in commercial websites. Usability and robustness are two fundamental issues with CAPTCHA, and they often interconnect with each other. This paper discusses usability issues that should be considered and addressed in the design of CAPTCHAs. Some of these issues are intuitive, but some others have subtle implications for robustness (or security). A simple but novel framework for examining CAPTCHA usability is also proposed.
---
paper_title: CAPTCHA: Using Hard AI Problems for Security

paper_content:

We introduce CAPTCHA, an automated test that humans can pass, but current computer programs can't pass: any program that has high success over a CAPTCHA can be used to solve an unsolved Artificial Intelligence (AI) problem. We provide several novel constructions of CAPTCHAS. Since CAPTCHAs have many applications in practical security, our approach introduces a new class of hard problems that can be exploited for security purposes. Much like research in cryptography has had a positive impact on algorithms for factoring and discrete log, we hope that the use of hard AI problems for security purposes allows us to advance the field of Artificial Intelligence. We introduce two families of Al problems that can be used to construct CAPTCHAS and we show that solutions to such problems can be used for steganographic communication. CAPTCHAS based on these AI problem families, then, imply a win-win situation: either the problems remain unsolved and there is a way to differentiate humans from computers, or the problems are solved and there is a way to communicate covertly on some channels.
---
paper_title: How to Generate and Use Universal Samplers

paper_content:

A random oracle is an idealization that allows us to model a hash function as an oracle that will output a uniformly random string given any input. We introduce the notion of a universal sampler scheme that extends the notion of a random oracle, to a method of sampling securely from arbitrary distributions. ::: ::: We describe several applications that provide a natural motivation for this notion; these include generating the trusted parameters for many schemes from just a single trusted setup. We further demonstrate the versatility of universal samplers by showing how they give rise to simple constructions of identity-based encryption and multiparty key exchange. In particular, we construct adaptively secure non-interactive multiparty key exchange in the random oracle model based on indistinguishability obfuscation; obtaining the first known construction of adaptively secure NIKE without complexity leveraging. ::: ::: We give a solution that shows how to transform any random oracle into a universal sampler scheme, based on indistinguishability obfuscation. At the heart of our construction and proof is a new technique we call "delayed backdoor programming" that we believe will have other applications.
---
paper_title: A Spelling Based CAPTCHA System by Using Click

paper_content:

CAPTCHA has been widely used for preventing malicious programs to access web resources automatically. In this paper, a new type CAPTCHA system will be proposed. The proposed scheme, named Click spell, combined the features of text-based and image-based CAPTCHAs. Click spell asks users to spell a randomly chosen word by clicking distorted letters for passing the test. Users can learn the definition(s) of the chosen word. In addition, Click spell can add an advertisement image optionally. Thanks to the advertisement image, Click spell improved the capability of resistance to the attack by malicious programs. Our preliminary test showed that Click spell is practical in the aspects of security and usability.
---
paper_title: Designing Proof of Human-Work Puzzles for Cryptocurrency and Beyond

paper_content:

We introduce the novel notion of a Proof of Human-work PoH and present the first distributed consensus protocol from hard Artificial Intelligence problems. As the name suggests, a PoH is a proof that a human invested a moderate amount of effort to solve some challenge. A PoH puzzle should be moderately hard for a human to solve. However, a PoH puzzle must be hard for a computer to solve, including the computer that generated the puzzle, without sufficient assistance from a human. By contrast, CAPTCHAs are only difficult for other computers to solve -- not for the computer that generated the puzzle. We also require that a PoH be publicly verifiable by a computer without any human assistance and without ever interacting with the agent who generated the proof of human-work. We show how to construct PoH puzzles from indistinguishability obfuscation and from CAPTCHAs. We motivate our ideas with two applications: HumanCoin and passwords. We use PoH puzzles to construct HumanCoin, the first cryptocurrency system with human miners. Second, we use proofs of human work to develop a password authentication scheme which provably protects users against offline attacks.
---
paper_title: Secure communications over insecure channels

paper_content:

According to traditional conceptions of cryptographic security, it is necessary to transmit a key, by secret means, before encrypted massages can be sent securely. This paper shows that it is possible to select a key over open communications channels in such a fashion that communications security can be maintained. A method is described which forces any enemy to expend an amount of work which increases as the square of the work required of the two communicants to select the key. The method provides a logically new kind of protection against the passive eavesdropper. It suggests that further research on this topic will be highly rewarding, both in a theoretical and a practical sense.
---
paper_title: Pricing via processing or combatting junk mail

paper_content:

We present a computational technique for combatting junk mail in particular and controlling access to a shared resource in general. The main idea is to require a user to compute a moderately hard, but not intractable, function in order to gain access to the resource, thus preventing frivolous use. To this end we suggest several pricing Junctions, based on, respectively, extracting square roots modulo a prime, the Fiat-Shamir signature scheme, and the Ong-Schnorr-Shamir (cracked) signature scheme.
---
paper_title: On Non-Parallelizable Deterministic Client Puzzle Scheme with Batch Verification Modes

paper_content:

A (computational) client puzzle scheme enables a client to prove to a server that a certain amount of computing resources (CPU cycles and/or Memory look-ups) has been dedicated to solve a puzzle. Researchers have identified a number of potential applications, such as constructing timed cryptography, fighting junk emails, and protecting critical infrastructure from DoS attacks. In this paper, we first revisit this concept and formally define two properties, namely deterministic computation and parallel computation resistance. Our analysis show that both properties are crucial for the effectiveness of client puzzle schemes in most application scenarios. We prove that the RSW client puzzle scheme, which is based on the repeated squaring technique, achieves both properties. Secondly, we introduce two batch verification modes for the RSW client puzzle scheme in order to improve the verification efficiency of the server, and investigate three methods for handling errors in batch verifications. Lastly, we show that client puzzle schemes can be integrated with reputation systems to further improve the effectiveness in practice.
---
paper_title: Low-cost client puzzles based on modular exponentiation

paper_content:

Client puzzles have been proposed as a useful mechanism for mitigating Denial of Service attacks on network protocols. While several puzzles have been proposed in recent years, most existing non-parallelizable puzzles are based on modular exponentiations. The main drawback of these puzzles is in the high cost that they incur on the puzzle generator (the verifier). In this paper, we propose cryptographic puzzles based on modular exponentiation that reduce this overhead. Our constructions are based on a reasonable intractability assumption in RSA: essentially the difficulty of computing a small private exponent when the public key is larger by several orders of magnitude than the semi-prime modulus. We also discuss puzzle constructions based on CRT-RSA [11]. Given a semi-prime modulus N, the costs incurred on the verifier in our puzzle are decreased by a factor of |N|/k when compared to existing modular exponentiation puzzles, where k is a security parameter. We further show how our puzzle can be integrated in a number of protocols, including those used for the remote verification of computing performance of devices and for the protection against Denial of Service attacks. We validate the performance of our puzzle on PlanetLab nodes.
---
paper_title: Efficient Modular Exponentiation-based Puzzles for Denial-of-Service Protection

paper_content:

Client puzzles are moderately-hard cryptographic problems -- neither easy nor impossible to solve -- that can be used as a countermeasure against denial of service attacks on network protocols. Puzzles based on modular exponentiation are attractive as they provide important properties such as non-parallelisability, deterministic solving time, and linear granularity. We propose an efficient client puzzle based on modular exponentiation. Our puzzle requires only a few modular multiplications for puzzle generation and verification. For a server under denial of service attack, this is a significant improvement as the best known non-parallelisable puzzle proposed by Karame and Capkun (ESORICS 2010) requires at least 2k-bit modular exponentiation, where k is a security parameter. We show that our puzzle satisfies the unforgeability and difficulty properties defined by Chen et al. (Asiacrypt 2009). We present experimental results which show that, for 1024-bit moduli, our proposed puzzle can be up to 30 × faster to verify than the Karame-Capkun puzzle and 99 × faster than the Rivest et al.'s time-lock puzzle.
---
paper_title: Time-lock puzzles and timed-release crypto

paper_content:

Our motivation is the notion of ``timed-release crypto,'''' where the goal is to encrypt a message so that it can not be decrypted by anyone, not even the sender, until a pre-determined amount of time has passed. The goal is to ``send information into the future.'''' This problem was first discussed by Timothy May \cite{May93}. What are the applications of ``timed-release crypto''''? Here are a few possibilities (some due to May): A bidder in an auction wants to seal his bid so that it can only be opened after the bidding period is closed. A homeowner wants to give his mortgage holder a series of encrypted mortgage payments. These might be encrypted digital cash with different decryption dates, so that one payment becomes decryptable (and thus usable by the bank) at the beginning of each successive month. An individual wants to encrypt his diaries so that they are only decryptable after fifty years. A key-escrow scheme can be based on timed-release crypto, so that the government can get the message keys, but only after a fixed period (say one year). \ There are presumably many other applications. There are two natural approaches to implementing timed-release crypto: Use ``time-lock puzzles''''--computational problems that can not be solved without running a computer continuously for at least a certain amount of time. Use trusted agents who promise not to reveal certain information until a specified date. Using trusted agents has the obvious problem of ensuring that the agents are trustworthy; secret-sharing approaches can be used to alleviate this concern. Using time-lock puzzles has the problem that the CPU time required to solve a problem can depend on the amount and nature of the hardware used to solve the problem, as well as the parallelizability of the computational problem being solved. In this note we explore both approaches. (We note that Tim May has suggested an approach based on the use of trusted agents.)
---
paper_title: Host Identity Protocol

paper_content:

This memo specifies the details of the Host Identity Protocol (HIP). ::: HIP allows consenting hosts to securely establish and maintain shared ::: IP-layer state, allowing separation of the identifier and locator ::: roles of IP addresses, thereby enabling continuity of communications ::: across IP address changes. HIP is based on a Sigma-compliant Diffie- ::: Hellman key exchange, using public key identifiers from a new Host ::: Identity namespace for mutual peer authentication. The protocol is ::: designed to be resistant to denial-of-service (DoS) and man-in-the- ::: middle (MitM) attacks. When used together with another suitable ::: security protocol, such as the Encapsulated Security Payload (ESP), it ::: provides integrity protection and optional encryption for upper- layer ::: protocols, such as TCP and UDP. This memo defines an Experimental ::: Protocol for the Internet community.
---
paper_title: Pricing via processing or combatting junk mail

paper_content:

We present a computational technique for combatting junk mail in particular and controlling access to a shared resource in general. The main idea is to require a user to compute a moderately hard, but not intractable, function in order to gain access to the resource, thus preventing frivolous use. To this end we suggest several pricing Junctions, based on, respectively, extracting square roots modulo a prime, the Fiat-Shamir signature scheme, and the Ong-Schnorr-Shamir (cracked) signature scheme.
---
paper_title: Efficient trapdoor-based client puzzle system against DoS attacks

paper_content:

Denial of service (DoS) and distributed denial of service (DDoS) are serious threats to computer networks. DoS and DDoS attacks aim to shut down a target server by depleting its resources and rendering it incapable of offering stable and integrated service to legitimate clients. Preventing DoS and DDoS attacks is a difficult task. A promising countermeasure against DoS attacks is the Client Puzzle method, which nevertheless faces a number of challenges, such as the complexity of puzzle construction and solution verification. Our research focuses on exploring novel puzzle constructions to satisfy the high demands of DoS defence in practice. In this thesis, we first identify the underlying weaknesses of existing client puzzles. To mitigate these vulnerabilities, we recommend the necessary requirements for good client puzzles. Based on this, we propose a new model for puzzle distribution, called the Trapdoor-based Client Puzzle System (TCPS). Two specific schemes are presented to construct puzzles within TCPS. We depict these two schemes, where each trapdoor algorithm is applied respectively. Both schemes have two distinct features: the computational overheads are low, and the difficulty level of puzzles is measurable. Moreover, both puzzle schemes are provably secure under traditional hard problems in mathematics. Our contribution to client puzzle defence against DoS attacks can be summarised as follows: • Identify the shortcomings of existing client puzzles. • Recommend the requirements of good client puzzles. • Formally define the Trapdoor-based Client Puzzle System, along with strict security conditions. • Propose a client puzzle scheme whose security is based on the RSA Assumption. Effectiveness and security are analysed and proven. vi • Propose a second client puzzle scheme whose security is based on the Discrete Logarithm Problem (DLP). Similarly, effectiveness and security are also analysed. • Provide a possible configuration for system parameters. • Discuss further possible attacks and their solutions. As our research is carried out in DoS attack scenarios, we also introduce this technical background before our achievements are presented.
---
paper_title: Design and implementation of network puzzles

paper_content:

Client puzzles have been proposed in a number of protocols as a mechanism for mitigating the effects of distributed denial of service (DDoS) attacks. In order to provide protection against simultaneous attacks across a wide range of applications and protocols, however, such puzzles must be placed at a layer common to all of them; the network layer. Placing puzzles at the IP layer fundamentally changes the service paradigm of the Internet, allowing any device within the network to push load back onto those it is servicing. An advantage of network layer puzzles over previous puzzle mechanisms is that they can be applied to all traffic from malicious clients, making it possible to defend against arbitrary attacks as well as making previously voluntary mechanisms mandatory. In this paper, we outline goals which must be met for puzzles to be deployed effectively at the network layer. We then describe the design, implementation, and evaluation of a system that meets these goals by supporting efficient, fine-grained control of puzzles at the network layer. In particular, we describe modifications to existing puzzle protocols that allow them to work at the network layer, a hint-based hash-reversal puzzle that allows for the generation and verification of fine-grained puzzles at line speed in the fast path of high-speed routers, and an iptables implementation that supports transparent deployment at arbitrary locations in the network.
---
paper_title: Defending against denial-of-service attacks with puzzle auctions

paper_content:

Although client puzzles represent a promising approach to defend against certain classes of denial-of-service attacks, several questions stand in the way of their deployment in practice: e.g., how to set the puzzle difficulty in the presence of an adversary with unknown computing power, and how to integrate the approach with existing mechanisms. In this paper, we attempt to address these questions with a new puzzle mechanism called the puzzle auction. Our mechanism enables each client to "bid" for resources by tuning the difficulty of the puzzles it solves, and to adapt its bidding strategy in response to apparent attacks. We analyze the effectiveness of our auction mechanism and further demonstrate it using an implementation within the TCP protocol stack of the Linux kernel. Our implementation has several appealing properties. It effectively defends against SYN flooding attacks, is fully compatible with TCP, and even provides a degree of interoperability with clients with unmodified kernels: Even without a puzzle-solving kernel, a client still can connect to a puzzle auction server under attack (albeit less effectively than those with puzzle-solving kernels, and at the cost of additional server expense).
---
paper_title: Mitigating bandwidth-exhaustion attacks using congestion puzzles

paper_content:

We present congestion puzzles (CP), a new countermeasure to bandwidth-exhaustion attacks. Like other defenses based on client puzzles, CP attempts to force attackers to invest vast resources in order to effectively perform denial-of-service attacks. Unlike previous puzzle-based approaches, however, ours is the first designed for the bandwidth-exhaustion attacks that are common at the network (IP) layer. At the core of CP is an elegant distributed puzzle mechanism that permits routers to cooperatively impose and check puzzles. We demonstrate through analysis and simulation that CP can effectively defend networks from flooding attacks without relying on the formulation of attack signatures to filter traffic. Moreover, as many such attacks are conducted by "zombie" computers that have been silently commandeered without the knowledge of their owners, the overheads that CP imposes on heavily engaged zombies can increase the likelihood that the computer's owner detects the compromise and takes action to remedy it.
---
paper_title: Hashcash - A Denial of Service Counter-Measure

paper_content:

Hashcash was originally proposed as a mechanism to throttle systematic abuse of un-metered internet resources such as email, and anonymous remailers in May 1997. Five years on, this paper captures in one place the various applications, improvements suggested and related subsequent publications, and describes initial experience from experiments using hashcash. The hashcash CPU cost-function computes a token which can be used as a proof-of-work. Interactive and noninteractive variants of cost-functions can be constructed which can be used in situations where the server can issue a challenge (connection oriented interactive protocol), and where it can not (where the communication is store–and– forward, or packet oriented) respectively.
---
paper_title: New client puzzle outsourcing techniques for DoS resistance

paper_content:

We explore new techniques for the use of cryptographic puzzles as a countermeasure to Denial-of-Service (DoS) attacks. We propose simple new techniques that permit the out-sourcing of puzzles; their distribution via a robust external service that we call a bastion. Many servers can rely on puzzles distributed by a single bastion. We show how a bastion, somewhat surprisingly, need not know which servers rely on its services. Indeed, in one of our constructions, a bastion may consist merely of a publicly accessible random data source, rather than a special purpose server. Our out-sourcing techniques help eliminate puzzle distribution as a point of compromise. Our design has three main advantages over prior approaches. First, it is more resistant to DoS attacks aimed at the puzzle mechanism itself, withstanding over 80% more attack traffic than previous methods in our experiments. Second, our scheme is cheap enough to apply at the IP level, though it also works at higher levels of the protocol stack. Third, our method allows clients to solve puzzles offline, reducing the need for users to wait while their computers solve puzzles. We present a prototype implementation of our approach, and we describe experiments that validate our performance claims.
---
paper_title: Mitigating denial of service attacks with password puzzles

paper_content:

The client puzzles have been proposed as an important mechanism in defending against distributed denial-of-service (DDoS) attacks. In this paper we propose a new IP layer client puzzles scheme, password puzzles (PP). In this scheme a puzzle issuer; on the behalf of a receiver, responds to requests with puzzles that a sender must solve before sending in any packet to a receiver. We design two new puzzle types, hash-chain-reversal puzzles and multiple-hash-chains-reversal puzzles, with which a sender is expected to reverse one (multiple) hash chain(s) and send in packets with valid passwords (i.e., solutions of puzzles) to the receiver. Our design achieves three main properties. First, the PP scheme is able to generate puzzles with different difficulties flexibly for various clients. Second, a puzzle issuer is able to generate puzzles at a per-flow and per-packet basis. Third, the PP scheme is able to converge to be a "non-puzzle " protocol.
---
paper_title: Password authentication with insecure communication

paper_content:

A method of user password authentication is described which is secure even if an intruder can read the system's data, and can tamper with or eavesdrop on the communication between the user and the system. The method assumes a secure one-way encryption function and can be implemented with a microcomputer in the user's terminal.
---
paper_title: SybilControl: practical sybil defense with computational puzzles

paper_content:

Many distributed systems are subject to the Sybil attack, where an adversary subverts system operation by emulating the behavior of multiple distinct nodes. Most recent works addressing this problem leverage social networks to establish trust relationships between users. However, social networks are not appropriate in all systems. They can be subverted by social engineering techniques, require nodes to maintain and be aware of social network information, and may require overly optimistic assumptions about the fast-mixing nature of social links. This paper explores an alternate approach. We present SybilControl, a novel decentralized scheme for controlling the extent of Sybil attacks. It is an admission and retainment control scheme for nodes in a distributed system that requires them to periodically solve computational puzzles. SybilControl consists of a distributed protocol to allow nodes to collectively verify the computational work of other nodes, and mechanisms to prevent the malicious influence of misbehaving nodes that do not perform the computational work. We investigate the practical issues involved with deploying SybilControl into existing DHTs, particularly with handling churn. SybilControl is shown to provide strict bounds on the size of Sybil attacks, given adversaries with finite resources. We also show through simulations that the performance overhead of enabling SybilControl is manageable using commonplace DHT churn-handling techniques. This provides strong evidence that SybilControl can be practically deployed.
---
paper_title: Factoring polynomials with rational coefficients

paper_content:

In this paper we present a polynomial-time algorithm to solve the following problem: given a non-zero polynomial fe Q(X) in one variable with rational coefficients, find the decomposition of f into irreducible factors in Q(X). It is well known that this is equivalent to factoring primitive polynomials feZ(X) into irreducible factors in Z(X). Here we call f~ Z(X) primitive if the greatest common divisor of its coefficients (the content of f) is 1. Our algorithm performs well in practice, cf. (8). Its running time, measured in bit operations, is O(nl2+n9(log(fD3).
---
paper_title: Time-lock puzzles and timed-release crypto

paper_content:

Our motivation is the notion of ``timed-release crypto,'''' where the goal is to encrypt a message so that it can not be decrypted by anyone, not even the sender, until a pre-determined amount of time has passed. The goal is to ``send information into the future.'''' This problem was first discussed by Timothy May \cite{May93}. What are the applications of ``timed-release crypto''''? Here are a few possibilities (some due to May): A bidder in an auction wants to seal his bid so that it can only be opened after the bidding period is closed. A homeowner wants to give his mortgage holder a series of encrypted mortgage payments. These might be encrypted digital cash with different decryption dates, so that one payment becomes decryptable (and thus usable by the bank) at the beginning of each successive month. An individual wants to encrypt his diaries so that they are only decryptable after fifty years. A key-escrow scheme can be based on timed-release crypto, so that the government can get the message keys, but only after a fixed period (say one year). \ There are presumably many other applications. There are two natural approaches to implementing timed-release crypto: Use ``time-lock puzzles''''--computational problems that can not be solved without running a computer continuously for at least a certain amount of time. Use trusted agents who promise not to reveal certain information until a specified date. Using trusted agents has the obvious problem of ensuring that the agents are trustworthy; secret-sharing approaches can be used to alleviate this concern. Using time-lock puzzles has the problem that the CPU time required to solve a problem can depend on the amount and nature of the hardware used to solve the problem, as well as the parallelizability of the computational problem being solved. In this note we explore both approaches. (We note that Tim May has suggested an approach based on the use of trusted agents.)
---
paper_title: Pricing via processing or combatting junk mail

paper_content:

We present a computational technique for combatting junk mail in particular and controlling access to a shared resource in general. The main idea is to require a user to compute a moderately hard, but not intractable, function in order to gain access to the resource, thus preventing frivolous use. To this end we suggest several pricing Junctions, based on, respectively, extracting square roots modulo a prime, the Fiat-Shamir signature scheme, and the Ong-Schnorr-Shamir (cracked) signature scheme.
---
paper_title: On Memory-Bound Functions for Fighting Spam

paper_content:

In 1992, Dwork and Naor proposed that e-mail messages be accompanied by easy-to-check proofs of computational effort in order to discourage junk e-mail, now known as spam. They proposed specific CPU-bound functions for this purpose. Burrows suggested that, since memory access speeds vary across machines much less than do CPU speeds, memory-bound functions may behave more equitably than CPU-bound functions; this approach was first explored by Abadi, Burrows, Manasse, and Wobber [3].
---
paper_title: Efficient trapdoor-based client puzzle system against DoS attacks

paper_content:

Denial of service (DoS) and distributed denial of service (DDoS) are serious threats to computer networks. DoS and DDoS attacks aim to shut down a target server by depleting its resources and rendering it incapable of offering stable and integrated service to legitimate clients. Preventing DoS and DDoS attacks is a difficult task. A promising countermeasure against DoS attacks is the Client Puzzle method, which nevertheless faces a number of challenges, such as the complexity of puzzle construction and solution verification. Our research focuses on exploring novel puzzle constructions to satisfy the high demands of DoS defence in practice. In this thesis, we first identify the underlying weaknesses of existing client puzzles. To mitigate these vulnerabilities, we recommend the necessary requirements for good client puzzles. Based on this, we propose a new model for puzzle distribution, called the Trapdoor-based Client Puzzle System (TCPS). Two specific schemes are presented to construct puzzles within TCPS. We depict these two schemes, where each trapdoor algorithm is applied respectively. Both schemes have two distinct features: the computational overheads are low, and the difficulty level of puzzles is measurable. Moreover, both puzzle schemes are provably secure under traditional hard problems in mathematics. Our contribution to client puzzle defence against DoS attacks can be summarised as follows: • Identify the shortcomings of existing client puzzles. • Recommend the requirements of good client puzzles. • Formally define the Trapdoor-based Client Puzzle System, along with strict security conditions. • Propose a client puzzle scheme whose security is based on the RSA Assumption. Effectiveness and security are analysed and proven. vi • Propose a second client puzzle scheme whose security is based on the Discrete Logarithm Problem (DLP). Similarly, effectiveness and security are also analysed. • Provide a possible configuration for system parameters. • Discuss further possible attacks and their solutions. As our research is carried out in DoS attack scenarios, we also introduce this technical background before our achievements are presented.
---
paper_title: Design and implementation of network puzzles

paper_content:

Client puzzles have been proposed in a number of protocols as a mechanism for mitigating the effects of distributed denial of service (DDoS) attacks. In order to provide protection against simultaneous attacks across a wide range of applications and protocols, however, such puzzles must be placed at a layer common to all of them; the network layer. Placing puzzles at the IP layer fundamentally changes the service paradigm of the Internet, allowing any device within the network to push load back onto those it is servicing. An advantage of network layer puzzles over previous puzzle mechanisms is that they can be applied to all traffic from malicious clients, making it possible to defend against arbitrary attacks as well as making previously voluntary mechanisms mandatory. In this paper, we outline goals which must be met for puzzles to be deployed effectively at the network layer. We then describe the design, implementation, and evaluation of a system that meets these goals by supporting efficient, fine-grained control of puzzles at the network layer. In particular, we describe modifications to existing puzzle protocols that allow them to work at the network layer, a hint-based hash-reversal puzzle that allows for the generation and verification of fine-grained puzzles at line speed in the fast path of high-speed routers, and an iptables implementation that supports transparent deployment at arbitrary locations in the network.
---
paper_title: Moderately hard, memory-bound functions

paper_content:

A resource may be abused if its users incur little or no cost. For example, e-mail abuse is rampant because sending an e-mail has negligible cost for the sender. It has been suggested that such abuse may be discouraged by introducing an artificial cost in the form of a moderately expensive computation. Thus, the sender of an e-mail might be required to pay by computing for a few seconds before the e-mail is accepted. Unfortunately, because of sharp disparities across computer systems, this approach may be ineffective against malicious users with high-end systems, prohibitively slow for legitimate users with low-end systems, or both. Starting from this observation, we research moderately hard functions that most recent systems will evaluate at about the same speed. For this purpose, we rely on memory-bound computations. We describe and analyze a family of moderately hard, memory-bound functions, and we explain how to use them for protecting against abuses.
---
paper_title: Defending against denial-of-service attacks with puzzle auctions

paper_content:

Although client puzzles represent a promising approach to defend against certain classes of denial-of-service attacks, several questions stand in the way of their deployment in practice: e.g., how to set the puzzle difficulty in the presence of an adversary with unknown computing power, and how to integrate the approach with existing mechanisms. In this paper, we attempt to address these questions with a new puzzle mechanism called the puzzle auction. Our mechanism enables each client to "bid" for resources by tuning the difficulty of the puzzles it solves, and to adapt its bidding strategy in response to apparent attacks. We analyze the effectiveness of our auction mechanism and further demonstrate it using an implementation within the TCP protocol stack of the Linux kernel. Our implementation has several appealing properties. It effectively defends against SYN flooding attacks, is fully compatible with TCP, and even provides a degree of interoperability with clients with unmodified kernels: Even without a puzzle-solving kernel, a client still can connect to a puzzle auction server under attack (albeit less effectively than those with puzzle-solving kernels, and at the cost of additional server expense).
---
paper_title: DOS-Resistant Authentication with Client Puzzles

paper_content:

Denial of service by server resource exhaustion has become a major security threat in open communications networks. Public-key authentication does not completely protect against the attacks because the authentication protocols often leave ways for an unauthenticated client to consume a server's memory space and computational resources by initiating a large number of protocol runs and inducing the server to perform expensive cryptographic computations. We show how stateless authentication protocols and the client puzzles of Juels and Brainard can be used to prevent such attacks.
---
paper_title: A Guided Tour Puzzle for Denial of Service Prevention

paper_content:

Various cryptographic puzzle schemes are proposed as a defense mechanism against denial of service attack. But, all these puzzle schemes face a dilemma when there is a large disparity between the computational power of attackers and legitimate clients: increasing the difficulty of puzzles might unnecessarily restrict legitimate clients too much, and lower difficulty puzzles cannot sufficiently block attackers with large computational resources. In this paper, we introduce guided tour puzzle, a novel puzzle scheme that is not affected by such resource disparity. A guided tour puzzle requires a client to visit a predefined set of nodes, called tour guides, in a certain sequential order to retrieve an n piece answer, one piece from each tour guide that appears in the tour. This puzzle solving process is non-parallelizable, thus cheating by trying to solve the puzzle in parallel is not possible. Guided tour puzzle not only achieves all previously defined desired properties of a cryptographic puzzle scheme, but it also satisfies more important requirements, such as puzzle fairness and minimum interference, that we identified. The number of tour guides required by the scheme can be as few as two, and this extra cost can be amortized by sharing the same set of tour guides among multiple servers.
---
paper_title: Hashcash - A Denial of Service Counter-Measure

paper_content:

Hashcash was originally proposed as a mechanism to throttle systematic abuse of un-metered internet resources such as email, and anonymous remailers in May 1997. Five years on, this paper captures in one place the various applications, improvements suggested and related subsequent publications, and describes initial experience from experiments using hashcash. The hashcash CPU cost-function computes a token which can be used as a proof-of-work. Interactive and noninteractive variants of cost-functions can be constructed which can be used in situations where the server can issue a challenge (connection oriented interactive protocol), and where it can not (where the communication is store–and– forward, or packet oriented) respectively.
---
paper_title: New client puzzle outsourcing techniques for DoS resistance

paper_content:

We explore new techniques for the use of cryptographic puzzles as a countermeasure to Denial-of-Service (DoS) attacks. We propose simple new techniques that permit the out-sourcing of puzzles; their distribution via a robust external service that we call a bastion. Many servers can rely on puzzles distributed by a single bastion. We show how a bastion, somewhat surprisingly, need not know which servers rely on its services. Indeed, in one of our constructions, a bastion may consist merely of a publicly accessible random data source, rather than a special purpose server. Our out-sourcing techniques help eliminate puzzle distribution as a point of compromise. Our design has three main advantages over prior approaches. First, it is more resistant to DoS attacks aimed at the puzzle mechanism itself, withstanding over 80% more attack traffic than previous methods in our experiments. Second, our scheme is cheap enough to apply at the IP level, though it also works at higher levels of the protocol stack. Third, our method allows clients to solve puzzles offline, reducing the need for users to wait while their computers solve puzzles. We present a prototype implementation of our approach, and we describe experiments that validate our performance claims.
---
paper_title: DDoS defense by offense

paper_content:

This paper presents the design, implementation, analysis, and experimental evaluation of speak-up, a defense against application-level distributed denial-of-service (DDoS), in which attackers cripple a server by sending legitimate-looking requests that consume computational resources (e.g., CPU cycles, disk). With speak-up, a victimized server encourages all clients, resources permitting, to automatically send higher volumes of traffic. We suppose that attackers are already using most of their upload bandwidth so cannot react to the encouragement. Good clients, however, have spare upload bandwidth and will react to the encouragement with drastically higher volumes of traffic. The intended outcome of this traffic inflation is that the good clients crowd out the bad ones, thereby capturing a much larger fraction of the server's resources than before. We experiment under various conditions and find that speak-up causes the server to spend resources on a group of clients in rough proportion to their aggregate upload bandwidth. This result makes the defense viable and effective for a class of real attacks.
---
paper_title: Time-lock puzzles and timed-release crypto

paper_content:

Our motivation is the notion of ``timed-release crypto,'''' where the goal is to encrypt a message so that it can not be decrypted by anyone, not even the sender, until a pre-determined amount of time has passed. The goal is to ``send information into the future.'''' This problem was first discussed by Timothy May \cite{May93}. What are the applications of ``timed-release crypto''''? Here are a few possibilities (some due to May): A bidder in an auction wants to seal his bid so that it can only be opened after the bidding period is closed. A homeowner wants to give his mortgage holder a series of encrypted mortgage payments. These might be encrypted digital cash with different decryption dates, so that one payment becomes decryptable (and thus usable by the bank) at the beginning of each successive month. An individual wants to encrypt his diaries so that they are only decryptable after fifty years. A key-escrow scheme can be based on timed-release crypto, so that the government can get the message keys, but only after a fixed period (say one year). \ There are presumably many other applications. There are two natural approaches to implementing timed-release crypto: Use ``time-lock puzzles''''--computational problems that can not be solved without running a computer continuously for at least a certain amount of time. Use trusted agents who promise not to reveal certain information until a specified date. Using trusted agents has the obvious problem of ensuring that the agents are trustworthy; secret-sharing approaches can be used to alleviate this concern. Using time-lock puzzles has the problem that the CPU time required to solve a problem can depend on the amount and nature of the hardware used to solve the problem, as well as the parallelizability of the computational problem being solved. In this note we explore both approaches. (We note that Tim May has suggested an approach based on the use of trusted agents.)
---
paper_title: CAPTCHA: Using Hard AI Problems for Security

paper_content:

We introduce CAPTCHA, an automated test that humans can pass, but current computer programs can't pass: any program that has high success over a CAPTCHA can be used to solve an unsolved Artificial Intelligence (AI) problem. We provide several novel constructions of CAPTCHAS. Since CAPTCHAs have many applications in practical security, our approach introduces a new class of hard problems that can be exploited for security purposes. Much like research in cryptography has had a positive impact on algorithms for factoring and discrete log, we hope that the use of hard AI problems for security purposes allows us to advance the field of Artificial Intelligence. We introduce two families of Al problems that can be used to construct CAPTCHAS and we show that solutions to such problems can be used for steganographic communication. CAPTCHAS based on these AI problem families, then, imply a win-win situation: either the problems remain unsolved and there is a way to differentiate humans from computers, or the problems are solved and there is a way to communicate covertly on some channels.
---
paper_title: Proofs of Space

paper_content:

Proofs of work (PoW) have been suggested by Dwork and Naor (Crypto’92) as protection to a shared resource. The basic idea is to ask the service requestor to dedicate some non-trivial amount of computational work to every request. The original applications included prevention of spam and protection against denial of service attacks. More recently, PoWs have been used to prevent double spending in the Bitcoin digital currency system.
---
paper_title: Moderately hard, memory-bound functions

paper_content:

A resource may be abused if its users incur little or no cost. For example, e-mail abuse is rampant because sending an e-mail has negligible cost for the sender. It has been suggested that such abuse may be discouraged by introducing an artificial cost in the form of a moderately expensive computation. Thus, the sender of an e-mail might be required to pay by computing for a few seconds before the e-mail is accepted. Unfortunately, because of sharp disparities across computer systems, this approach may be ineffective against malicious users with high-end systems, prohibitively slow for legitimate users with low-end systems, or both. Starting from this observation, we research moderately hard functions that most recent systems will evaluate at about the same speed. For this purpose, we rely on memory-bound computations. We describe and analyze a family of moderately hard, memory-bound functions, and we explain how to use them for protecting against abuses.
---
paper_title: Bandwidth Hard Functions for ASIC Resistance

paper_content:

Cryptographic hash functions have wide applications including password hashing, pricing functions for spam and denial-of-service countermeasures and proof of work in cryptocurrencies. Recent progress on ASIC (Application Specific Integrated Circuit) hash engines raise concerns about the security of the above applications. This leads to a growing interest in ASIC resistant hash function and ASIC resistant proof of work schemes, i.e., those that do not give ASICs a huge advantage. The standard approach towards ASIC resistance today is through memory hard functions or memory hard proof of work schemes. However, we observe that the memory hardness approach is an incomplete solution. It only attempts to provide resistance to an ASIC’s area advantage but overlooks the more important energy advantage. In this paper, we propose the notion of bandwidth hard functions to reduce an ASIC’s energy advantage. CPUs cannot compete with ASICs for energy efficiency in computation, but we can rely on memory accesses to reduce an ASIC’s energy advantage because energy costs of memory accesses are comparable for ASICs and CPUs. We propose a model for hardware energy cost that has sound foundations in practice. We then analyze the bandwidth hardness property of ASIC resistant candidates. We find scrypt, Catena-BRG and Balloon are bandwidth hard with suitable parameters. Lastly, we observe that a capacity hard function is not necessarily bandwidth hard, with a stacked double butterfly graph being a counterexample.
---
paper_title: Proofs of Space : When Space is of the Essence

paper_content:

Proofs of computational effort were devised to control denial of service attacks. Dwork and Naor (CRYPTO ’92), for example, proposed to use such proofs to discourage spam. The idea is to couple each email message with a proof of work that demonstrates the sender performed some computational task. A proof of work can be either CPU-bound or memory-bound. In a CPU-bound proof, the prover must compute a CPU-intensive function that is easy to check by the verifier. A memory-bound proof, instead, forces the prover to access the main memory several times, effectively replacing CPU cycles with memory accesses.
---
paper_title: Moderately hard, memory-bound functions

paper_content:

A resource may be abused if its users incur little or no cost. For example, e-mail abuse is rampant because sending an e-mail has negligible cost for the sender. It has been suggested that such abuse may be discouraged by introducing an artificial cost in the form of a moderately expensive computation. Thus, the sender of an e-mail might be required to pay by computing for a few seconds before the e-mail is accepted. Unfortunately, because of sharp disparities across computer systems, this approach may be ineffective against malicious users with high-end systems, prohibitively slow for legitimate users with low-end systems, or both. Starting from this observation, we research moderately hard functions that most recent systems will evaluate at about the same speed. For this purpose, we rely on memory-bound computations. We describe and analyze a family of moderately hard, memory-bound functions, and we explain how to use them for protecting against abuses.
---
paper_title: On Memory-Bound Functions for Fighting Spam

paper_content:

In 1992, Dwork and Naor proposed that e-mail messages be accompanied by easy-to-check proofs of computational effort in order to discourage junk e-mail, now known as spam. They proposed specific CPU-bound functions for this purpose. Burrows suggested that, since memory access speeds vary across machines much less than do CPU speeds, memory-bound functions may behave more equitably than CPU-bound functions; this approach was first explored by Abadi, Burrows, Manasse, and Wobber [3].
---
paper_title: Pebbling and proofs of work

paper_content:

We investigate methods for providing easy-to-check proofs of computational effort. Originally intended for discouraging spam, the concept has wide applicability as a method for controlling denial of service attacks. Dwork, Goldberg, and Naor proposed a specific memory-bound function for this purpose and proved an asymptotically tight amortized lower bound on the number of memory accesses any polynomial time bounded adversary must make. Their function requires a large random table which, crucially, cannot be compressed. ::: ::: We answer an open question of Dwork et al. by designing a compact representation for the table. The paradox, compressing an incompressible table, is resolved by embedding a time/space tradeoff into the process for constructing the table from its representation.
---
paper_title: Moderately hard, memory-bound functions

paper_content:

A resource may be abused if its users incur little or no cost. For example, e-mail abuse is rampant because sending an e-mail has negligible cost for the sender. It has been suggested that such abuse may be discouraged by introducing an artificial cost in the form of a moderately expensive computation. Thus, the sender of an e-mail might be required to pay by computing for a few seconds before the e-mail is accepted. Unfortunately, because of sharp disparities across computer systems, this approach may be ineffective against malicious users with high-end systems, prohibitively slow for legitimate users with low-end systems, or both. Starting from this observation, we research moderately hard functions that most recent systems will evaluate at about the same speed. For this purpose, we rely on memory-bound computations. We describe and analyze a family of moderately hard, memory-bound functions, and we explain how to use them for protecting against abuses.
---
paper_title: Efficient Memory Bound Puzzles Using Pattern Databased

paper_content:

CPU bound client puzzles have been suggested as a defense mechanism against connection depletion attacks. However, the wide disparity in CPU speeds prevents such puzzles from being globally deployed. Recently, Abadi et. al. [1] and Dwork et. al. [2] addressed this limitation by showing that memory access times vary much less than CPU speeds, and hence offer a viable alternative. In this paper, we further investigate the applicability of memory bound puzzles from a new perspective and propose constructions based on heuristic search methods. Our constructions are derived from a more algorithmic foundation, and as a result, allow us to easily tune parameters that impact puzzle creation and verification costs. Moreover, unlike prior approaches, we address client-side cost and present an extension that allows memory constrained clients (e.g., PDAs) to implement our construction in a secure fashion.
---
paper_title: Scrypt Is Maximally Memory-Hard

paper_content:

Memory-hard functions (MHFs) are hash algorithms whose evaluation cost is dominated by memory cost. As memory, unlike computation, costs about the same across different platforms, MHFs cannot be evaluated at significantly lower cost on dedicated hardware like ASICs. MHFs have found widespread applications including password hashing, key derivation, and proofs-of-work.
---
paper_title: Bandwidth Hard Functions for ASIC Resistance

paper_content:

Cryptographic hash functions have wide applications including password hashing, pricing functions for spam and denial-of-service countermeasures and proof of work in cryptocurrencies. Recent progress on ASIC (Application Specific Integrated Circuit) hash engines raise concerns about the security of the above applications. This leads to a growing interest in ASIC resistant hash function and ASIC resistant proof of work schemes, i.e., those that do not give ASICs a huge advantage. The standard approach towards ASIC resistance today is through memory hard functions or memory hard proof of work schemes. However, we observe that the memory hardness approach is an incomplete solution. It only attempts to provide resistance to an ASIC’s area advantage but overlooks the more important energy advantage. In this paper, we propose the notion of bandwidth hard functions to reduce an ASIC’s energy advantage. CPUs cannot compete with ASICs for energy efficiency in computation, but we can rely on memory accesses to reduce an ASIC’s energy advantage because energy costs of memory accesses are comparable for ASICs and CPUs. We propose a model for hardware energy cost that has sound foundations in practice. We then analyze the bandwidth hardness property of ASIC resistant candidates. We find scrypt, Catena-BRG and Balloon are bandwidth hard with suitable parameters. Lastly, we observe that a capacity hard function is not necessarily bandwidth hard, with a stacked double butterfly graph being a counterexample.
---
paper_title: Cuckoo hashing

paper_content:

We present a simple dictionary with worst case constant lookup time, equaling the theoretical performance of the classic dynamic perfect hashing scheme of Dietzfelbinger et al. [SIAM J. Comput. 23 (4) (1994) 738-761]. The space usage is similar to that of binary search trees. Besides being conceptually much simpler than previous dynamic dictionaries with worst case constant lookup time, our data structure is interesting in that it does not use perfect hashing, but rather a variant of open addressing where keys can be moved back in their probe sequences. An implementation inspired by our algorithm, but using weaker hash functions, is found to be quite practical. It is competitive with the best known dictionaries having an average case (but no nontrivial worst case) guarantee on lookup time.
---
paper_title: Cuckoo Cycle: A Memory Bound Graph-Theoretic Proof-of-Work

paper_content:

We introduce the first graph-theoretic proof-of-work system, based on finding small cycles or other structures in large random graphs. Such problems are trivially verifiable and arbitrarily scalable, presumably requiring memory linear in graph size to solve efficiently. Our cycle finding algorithm uses one bit per edge, and up to one bit per node. Runtime is linear in graph size and dominated by random access latency, ideal properties for a memory bound proof-of-work. We exhibit two alternative algorithms that allow for a memory-time trade-off (TMTO)—decreased memory usage, by a factor k, coupled with increased runtime, by a factor \(\varOmega (k)\). The constant implied in \(\varOmega ()\) gives a notion of memory-hardness, which is shown to be dependent on cycle length, guiding the latter’s choice. Our algorithms are shown to parallelize reasonably well.
---
paper_title: Egalitarian computing

paper_content:

In this paper we explore several contexts where an adversary has an upper hand over the defender by using special hardware in an attack. These include password processing, hard-drive protection, cryptocurrency mining, resource sharing, code obfuscation, etc. We suggest memory-hard computing as a generic paradigm, where every task is amalgamated with a certain procedure requiring intensive access to RAM both in terms of size and (very importantly) bandwidth, so that transferring the computation to GPU, FPGA, and even ASIC brings little or no cost reduction. Cryptographic schemes that run in this framework become \emph{egalitarian} in the sense that both users and attackers are equal in the price-performance ratio conditions. Based on existing schemes like {Argon2} and the recent generalized-birthday proof-of-work, we suggest a generic framework and two new schemes: {MTP}, a memory-hard Proof-of-Work based on the memory-hard function with fast verification and short proofs. It can be also used for memory-hard time-lock puzzles. {MHE}, the concept of memory-hard encryption, which utilizes available RAM to strengthen the encryption for the low-entropy keys (allowing to bring back 6 letter passwords).
---
paper_title: On Memory-Bound Functions for Fighting Spam

paper_content:

In 1992, Dwork and Naor proposed that e-mail messages be accompanied by easy-to-check proofs of computational effort in order to discourage junk e-mail, now known as spam. They proposed specific CPU-bound functions for this purpose. Burrows suggested that, since memory access speeds vary across machines much less than do CPU speeds, memory-bound functions may behave more equitably than CPU-bound functions; this approach was first explored by Abadi, Burrows, Manasse, and Wobber [3].
---
paper_title: Proofs of Space

paper_content:

Proofs of work (PoW) have been suggested by Dwork and Naor (Crypto’92) as protection to a shared resource. The basic idea is to ask the service requestor to dedicate some non-trivial amount of computational work to every request. The original applications included prevention of spam and protection against denial of service attacks. More recently, PoWs have been used to prevent double spending in the Bitcoin digital currency system.
---
paper_title: Proof of Space from Stacked Expanders

paper_content:

Recently, proof of space PoS has been suggested as a more egalitarian alternative to the traditional hash-based proof of work. In PoS, a prover proves to a verifier that it has dedicated some specified amount of space. A closely related notion is memory-hard functions MHF, functions that require a lot of memory/space to compute. While making promising progress, existing PoS and MHF have several problems. First, there are large gaps between the desired space-hardness and what can be proven. Second, it has been pointed out that PoS and MHF should require a lot of space not just at some point, but throughout the entire computation/protocol; few proposals considered this issue. Third, the two existing PoS constructions are both based on a class of graphs called superconcentrators, which are either hard to construct or add a logarithmic factor overhead to efficiency. In this paper, we construct PoS from stacked expander graphs. Our constructions are simpler, more efficient and have tighter provable space-hardness than prior works. Our results also apply to a recent MHF called Balloon hash. We show Balloon hash has tighter space-hardness than previously believed and consistent space-hardness throughout its computation.
---
paper_title: Moderately hard, memory-bound functions

paper_content:

A resource may be abused if its users incur little or no cost. For example, e-mail abuse is rampant because sending an e-mail has negligible cost for the sender. It has been suggested that such abuse may be discouraged by introducing an artificial cost in the form of a moderately expensive computation. Thus, the sender of an e-mail might be required to pay by computing for a few seconds before the e-mail is accepted. Unfortunately, because of sharp disparities across computer systems, this approach may be ineffective against malicious users with high-end systems, prohibitively slow for legitimate users with low-end systems, or both. Starting from this observation, we research moderately hard functions that most recent systems will evaluate at about the same speed. For this purpose, we rely on memory-bound computations. We describe and analyze a family of moderately hard, memory-bound functions, and we explain how to use them for protecting against abuses.
---
paper_title: Proofs of Space : When Space is of the Essence

paper_content:

Proofs of computational effort were devised to control denial of service attacks. Dwork and Naor (CRYPTO ’92), for example, proposed to use such proofs to discourage spam. The idea is to couple each email message with a proof of work that demonstrates the sender performed some computational task. A proof of work can be either CPU-bound or memory-bound. In a CPU-bound proof, the prover must compute a CPU-intensive function that is easy to check by the verifier. A memory-bound proof, instead, forces the prover to access the main memory several times, effectively replacing CPU cycles with memory accesses.
---
paper_title: Cuckoo Cycle: A Memory Bound Graph-Theoretic Proof-of-Work

paper_content:

We introduce the first graph-theoretic proof-of-work system, based on finding small cycles or other structures in large random graphs. Such problems are trivially verifiable and arbitrarily scalable, presumably requiring memory linear in graph size to solve efficiently. Our cycle finding algorithm uses one bit per edge, and up to one bit per node. Runtime is linear in graph size and dominated by random access latency, ideal properties for a memory bound proof-of-work. We exhibit two alternative algorithms that allow for a memory-time trade-off (TMTO)—decreased memory usage, by a factor k, coupled with increased runtime, by a factor \(\varOmega (k)\). The constant implied in \(\varOmega ()\) gives a notion of memory-hardness, which is shown to be dependent on cycle length, guiding the latter’s choice. Our algorithms are shown to parallelize reasonably well.
---
paper_title: A Generalized Birthday Problem

paper_content:

We study a k-dimensional generalization of the birthday problem: given k lists of n-bit values, find some way to choose one element from each list so that the resulting k values XOR to zero. For k = 2, this is just the extremely well-known birthday problem, which has a square-root time algorithm with many applications in cryptography. In this paper, we show new algorithms for the case k > 2: we show a cube-root time algorithm for the case of k = 4 lists, and we give an algorithm with subexponential running time when k is unrestricted.We also give several applications to cryptanalysis, describing new subexponential algorithms for constructing one-more forgeries for certain blind signature schemes, for breaking certain incremental hash functions, and for finding low-weight parity check equations for fast correlation attacks on stream ciphers. In these applications, our algorithm runs in O(22?n) time for an n-bit modulus, demonstrating that moduli may need to be at least 1600 bits long for security against these new attacks. As an example, we describe the first-known attack with subexponential complexity on Schnorr and Okamoto-Schnorr blind signatures over elliptic curve groups.
---
paper_title: Argon2: New Generation of Memory-Hard Functions for Password Hashing and Other Applications

paper_content:

We present a new hash function Argon2, which is oriented at protection of low-entropy secrets without secret keys. It requires a certain (but tunable) amount of memory, imposes prohibitive time-memory and computation-memory tradeoffs on memory-saving users, and is exceptionally fast on regular PC. Overall, it can provide ASIC-and botnet-resistance by filling the memory in 0.6 cycles per byte in the non-compressible way.
---
paper_title: Egalitarian computing

paper_content:

In this paper we explore several contexts where an adversary has an upper hand over the defender by using special hardware in an attack. These include password processing, hard-drive protection, cryptocurrency mining, resource sharing, code obfuscation, etc. We suggest memory-hard computing as a generic paradigm, where every task is amalgamated with a certain procedure requiring intensive access to RAM both in terms of size and (very importantly) bandwidth, so that transferring the computation to GPU, FPGA, and even ASIC brings little or no cost reduction. Cryptographic schemes that run in this framework become \emph{egalitarian} in the sense that both users and attackers are equal in the price-performance ratio conditions. Based on existing schemes like {Argon2} and the recent generalized-birthday proof-of-work, we suggest a generic framework and two new schemes: {MTP}, a memory-hard Proof-of-Work based on the memory-hard function with fast verification and short proofs. It can be also used for memory-hard time-lock puzzles. {MHE}, the concept of memory-hard encryption, which utilizes available RAM to strengthen the encryption for the low-entropy keys (allowing to bring back 6 letter passwords).
---
paper_title: Proofs of Space

paper_content:

Proofs of work (PoW) have been suggested by Dwork and Naor (Crypto’92) as protection to a shared resource. The basic idea is to ask the service requestor to dedicate some non-trivial amount of computational work to every request. The original applications included prevention of spam and protection against denial of service attacks. More recently, PoWs have been used to prevent double spending in the Bitcoin digital currency system.
---
paper_title: Proofs of Space : When Space is of the Essence

paper_content:

Proofs of computational effort were devised to control denial of service attacks. Dwork and Naor (CRYPTO ’92), for example, proposed to use such proofs to discourage spam. The idea is to couple each email message with a proof of work that demonstrates the sender performed some computational task. A proof of work can be either CPU-bound or memory-bound. In a CPU-bound proof, the prover must compute a CPU-intensive function that is easy to check by the verifier. A memory-bound proof, instead, forces the prover to access the main memory several times, effectively replacing CPU cycles with memory accesses.
---
paper_title: Egalitarian computing

paper_content:

In this paper we explore several contexts where an adversary has an upper hand over the defender by using special hardware in an attack. These include password processing, hard-drive protection, cryptocurrency mining, resource sharing, code obfuscation, etc. We suggest memory-hard computing as a generic paradigm, where every task is amalgamated with a certain procedure requiring intensive access to RAM both in terms of size and (very importantly) bandwidth, so that transferring the computation to GPU, FPGA, and even ASIC brings little or no cost reduction. Cryptographic schemes that run in this framework become \emph{egalitarian} in the sense that both users and attackers are equal in the price-performance ratio conditions. Based on existing schemes like {Argon2} and the recent generalized-birthday proof-of-work, we suggest a generic framework and two new schemes: {MTP}, a memory-hard Proof-of-Work based on the memory-hard function with fast verification and short proofs. It can be also used for memory-hard time-lock puzzles. {MHE}, the concept of memory-hard encryption, which utilizes available RAM to strengthen the encryption for the low-entropy keys (allowing to bring back 6 letter passwords).
---
paper_title: Proofs of Space

paper_content:

Proofs of work (PoW) have been suggested by Dwork and Naor (Crypto’92) as protection to a shared resource. The basic idea is to ask the service requestor to dedicate some non-trivial amount of computational work to every request. The original applications included prevention of spam and protection against denial of service attacks. More recently, PoWs have been used to prevent double spending in the Bitcoin digital currency system.
---
paper_title: Pebbling and proofs of work

paper_content:

We investigate methods for providing easy-to-check proofs of computational effort. Originally intended for discouraging spam, the concept has wide applicability as a method for controlling denial of service attacks. Dwork, Goldberg, and Naor proposed a specific memory-bound function for this purpose and proved an asymptotically tight amortized lower bound on the number of memory accesses any polynomial time bounded adversary must make. Their function requires a large random table which, crucially, cannot be compressed. ::: ::: We answer an open question of Dwork et al. by designing a compact representation for the table. The paradox, compressing an incompressible table, is resolved by embedding a time/space tradeoff into the process for constructing the table from its representation.
---
paper_title: DDoS defense by offense

paper_content:

This paper presents the design, implementation, analysis, and experimental evaluation of speak-up, a defense against application-level distributed denial-of-service (DDoS), in which attackers cripple a server by sending legitimate-looking requests that consume computational resources (e.g., CPU cycles, disk). With speak-up, a victimized server encourages all clients, resources permitting, to automatically send higher volumes of traffic. We suppose that attackers are already using most of their upload bandwidth so cannot react to the encouragement. Good clients, however, have spare upload bandwidth and will react to the encouragement with drastically higher volumes of traffic. The intended outcome of this traffic inflation is that the good clients crowd out the bad ones, thereby capturing a much larger fraction of the server's resources than before. We experiment under various conditions and find that speak-up causes the server to spend resources on a group of clients in rough proportion to their aggregate upload bandwidth. This result makes the defense viable and effective for a class of real attacks.
---
paper_title: A Guided Tour Puzzle for Denial of Service Prevention

paper_content:

Various cryptographic puzzle schemes are proposed as a defense mechanism against denial of service attack. But, all these puzzle schemes face a dilemma when there is a large disparity between the computational power of attackers and legitimate clients: increasing the difficulty of puzzles might unnecessarily restrict legitimate clients too much, and lower difficulty puzzles cannot sufficiently block attackers with large computational resources. In this paper, we introduce guided tour puzzle, a novel puzzle scheme that is not affected by such resource disparity. A guided tour puzzle requires a client to visit a predefined set of nodes, called tour guides, in a certain sequential order to retrieve an n piece answer, one piece from each tour guide that appears in the tour. This puzzle solving process is non-parallelizable, thus cheating by trying to solve the puzzle in parallel is not possible. Guided tour puzzle not only achieves all previously defined desired properties of a cryptographic puzzle scheme, but it also satisfies more important requirements, such as puzzle fairness and minimum interference, that we identified. The number of tour guides required by the scheme can be as few as two, and this extra cost can be amortized by sharing the same set of tour guides among multiple servers.
---
paper_title: Making Peer-Assisted Content Distribution Robust to Collusion Using Bandwidth Puzzles

paper_content:

Many peer-assisted content-distribution systems reward a peer based on the amount of data that this peer serves to others. However, validating that a peer did so is, to our knowledge, an open problem; e.g., a group of colluding attackers can earn rewards by claiming to have served content to one another, when they have not. We propose a puzzle mechanism to make contribution-aware peer-assisted content distribution robust to such collusion. Our construction ties solving the puzzle to possession of specific content and, by issuing puzzle challenges simultaneously to all parties claiming to have that content, our mechanism prevents one content-holder from solving many others' puzzles. We prove (in the random oracle model) the security of our scheme, describe our integration of bandwidth puzzles into a media streaming system, and demonstrate the resulting attack resilience via simulations.
---
paper_title: A New Bound on the Performance of the Bandwidth Puzzle

paper_content:

A bandwidth puzzle was recently proposed to defend against colluding adversaries in peer-to-peer networks. The colluding adversaries do not do actual work but claim to have uploaded content for each other to gain free credits from the system. The bandwidth puzzle guarantees that if the adversaries can solve the puzzles, they must have spent substantial bandwidth, the size of which is comparable to the size of the content they claim to have uploaded for each other. Therefore, the puzzle discourages the collusion. In this paper, we study the performance of the bandwidth puzzle and give a lower bound on the average number of bits the adversaries must receive to be able to solve the puzzles with a certain probability. We show that our bound is tight in the sense that there exists a strategy to approach this lower bound asymptotically within a small factor with practical puzzle parameters. The new bound gives better security guarantees than the existing bound, and can be used to guide the choices of puzzle parameters for practical systems.
---

Title: Foundations, Properties, and Security Applications of Puzzles: A Survey

Section 1: INTRODUCTION
Description 1: Present an introduction to the concept of security puzzles, historical context, and critical importance in various security fields. Summarize the contributions and organization of the paper.

Section 2: FOUNDATIONS AND BACKGROUND
Description 2: Discuss the abstract structure of puzzles and differentiate between puzzle categories. Present the conceptual framework and the evolution of puzzle schemes.

Section 3: Abstract Structure of Puzzles
Description 3: Describe the core components and phases of a puzzle scheme, detailing the interactions between the verifier and the prover.

Section 4: Types of Puzzles
Description 4: Classify puzzles based on their applications, resources required for solving, and verification types. Elaborate on the various categories and their respective features.

Section 5: IDIOSYNCRATIC FEATURES
Description 5: List and explore the essential properties and requirements for designing effective puzzles, including asymmetry, granularity, efficiency, and fairness.

Section 6: APPLICATIONS
Description 6: Review significant applications of puzzles in different security fields, categorizing them based on their usage. Discuss the key requirements and the viability of each type in its respective application area.

Section 7: CONSTRUCTION SCHEMES
Description 7: Survey various construction schemes for CPU-bound, memory-bound, memory-hard, and bandwidth-bound puzzles. Highlight the techniques used, their distinctive characteristics, limitations, and benefits.

Section 8: CONCLUSION
Description 8: Summarize the survey, recapitulate the contributions, and provide an overview of the integration of scattered notions related to puzzles. Discuss potential research directions and future insights in the field of puzzles.