Proof of work | EPFL Graph Search

Proof of work (PoW) is a form of cryptographic proof in which one party (the prover) proves to others (the verifiers) that a certain amount of a specific computational effort has been expended. Verifiers can subsequently confirm this expenditure with minimal effort on their part. The concept was invented by Moni Naor and Cynthia Dwork in 1993 as a way to deter denial-of-service attacks and other service abuses such as spam on a network by requiring some work from a service requester, usually meaning processing time by a computer. The term "proof of work" was first coined and formalized in a 1999 paper by Markus Jakobsson and Ari Juels. Proof of work was later popularized by Bitcoin as a foundation for consensus in a permissionless decentralized network, in which miners compete to append blocks and mine new currency, each miner experiencing a success probability proportional to the computational effort expended. PoW and PoS (proof of stake) remain the two best known Sybil deterrence mechanisms. In the context of cryptocurrencies they are the most common mechanisms. A key feature of proof-of-work schemes is their asymmetry: the work – the computation – must be moderately hard (yet feasible) on the prover or requester side but easy to check for the verifier or service provider. This idea is also known as a CPU cost function, client puzzle, computational puzzle, or CPU pricing function. Another common feature is built-in incentive-structures that reward allocating computational capacity to the network with value in the form of cryptocurrency. The purpose of proof-of-work algorithms is not proving that certain work was carried out or that a computational puzzle was "solved", but deterring manipulation of data by establishing large energy and hardware-control requirements to be able to do so. Proof-of-work systems have been criticized by environmentalists for their energy consumption. One popular system, used in Hashcash, uses partial hash inversions to prove that computation was done, as a goodwill token to send an e-mail.

Time in cryptography

Gwangbae Choi

Time travel has always been a fascinating topic in literature and physics. In cryptography, one may wonder how to keep data confidential for some time. In this dissertation, we will study how to make private information travel to the future. This dissertation consists of three parts: Timed-release encryption, witness encryption and self-encryption. With timed-release encryption, one can send to a counterpart a message which cannot be read before some time has elapsed. One possible solution is to use a third party. At every time period, the third party releases a time bound key, and a ciphertext which is encrypted for a time period requires the time bound key of that time period for decryption. Then, a problem occurs when the counterpart somehow loses the release time of ciphertext. We propose a solution by introducing a master time bound key which can be considered as a valid time bound key of all time periods. We propose a provably secure construction and show the experimental results. In 2018, Liu, Jager, Kakvi and Warinschi introduced a timed-release encryption scheme based on a blockchain with proof-of-work and witness encryption. Current proposals of witness encryption are based on multilinear maps. In this part, we propose a new construction without. We propose the notion of hidden group with hashing and make a witness encryption from it. We show that the construction is secure in a generic model. We propose a concrete construction based on RSA-related problems. Namely, we use an extension of the knowledge-of-exponent assumption and the order problem. We finally estimate the cost of the bitcoin blockchain implementation. Although our estimates are still high (for a release time of one hour / one year, we respectively use ciphertexts of 567 MB / 4.5 TB and a decryption time of 27 min / 5.2 months on a single core), there is room for improvement by a factor 20 000 by adapting the blockchain structure and by adopting a hash function which is better adapted to this type of programming than SHA256. In self-encryption, a device encrypts some piece of information for itself to decrypt in the future. We are interested in security of self-encryption when the state occasionally leaks. Applications where self-encryption operates are cloud storage, when a client encrypts files to be stored, and in 0-RTT session resumptions, when a server encrypts a resumption key to be stored by the client. Previous works focused on forward secrecy and resistance to replay attacks. In our work, we study post-compromise security. Post-compromise security was already solved in ratcheted instant messaging schemes, at the price of having an inflating state size. However, it was not known whether state inflation was necessary. We prove here that this is the case. In our results, we prove that post-compromise security implies a super-linear state size in terms of the number of ciphertexts which can still be decrypted by the state. We apply our result to self-encryption for cloud storage and 0-RTT session resumption, and also to secure messaging. We further show how to construct a secure scheme matching our bound on the state size.

EPFL2020

Neuron splitting in compute-bound parallel network simulations enables runtime scaling with twice as many processors

Michael Lee Hines

Neuron tree topology equations can be split into two subtrees and solved on different processors with no change in accuracy, stability, or computational effort; communication costs involve only sending and receiving two double precision values by each subtree at each time step. Splitting cells is useful in attaining load balance in neural network simulations, especially when there is a wide range of cell sizes and the number of cells is about the same as the number of processors. For compute-bound simulations load balance results in almost ideal runtime scaling. Application of the cell splitting method to two published network models exhibits good runtime scaling on twice as many processors as could be effectively used with whole-cell balancing.

Springer Verlag2008

Time in cryptography

Gwangbae Choi

EPFL2020