Source author record

Lear Bahack

Lear Bahack appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Cryptography and Security Computational Complexity Computational Engineering, Finance, and Science math.CO Social and Information Networks

Catalog footprint

What is connected

3works

5topics

1close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

The Game of Tumbleweed is PSPACE-complete

Tumbleweed is a popular two-player perfect-information new territorial game played at the prestigious Mind Sport Olympiad. We define a generalized version of the game, where the board size is arbitrary and so is the possible number of neutral stones. Our result: the complexity of deciding for a given configuration which of the players has a winning strategy is PSPACE-complete. The proof is by a log-space reduction from a Boolean formula game of T.J. Schaefer, known to be PSPACE-complete. We embed the non-planar Schaefer game within the planar Tumbleweed board without using proper "bridges", that are impossible due to the board's topology. Instead, our new technique uses a one-move tight race that forces the players to move only according to the protocol of playing the embedded 4-CNF game.

preprint2014arXiv

On Subversive Miner Strategies and Block Withholding Attack in Bitcoin Digital Currency

Bitcoin is a "crypto currency", a decentralized electronic payment scheme based on cryptography. Bitcoin economy grows at an incredibly fast rate and is now worth some 10 billions of dollars. Bitcoin mining is an activity which consists of creating (minting) the new coins which are later put into circulation. Miners spend electricity on solving cryptographic puzzles and they are also gatekeepers which validate bitcoin transactions of other people. Miners are expected to be honest and have some incentives to behave well. However. In this paper we look at the miner strategies with particular attention paid to subversive and dishonest strategies or those which could put bitcoin and its reputation in danger. We study in details several recent attacks in which dishonest miners obtain a higher reward than their relative contribution to the network. In particular we revisit the concept of block withholding attacks and propose a new concrete and practical block withholding attack which we show to maximize the advantage gained by rogue miners. RECENT EVENTS: it seems that the attack was recently executed, see Section XI-A.

preprint2013arXiv

Theoretical Bitcoin Attacks with less than Half of the Computational Power (draft)

A widespread security claim of the Bitcoin system, presented in the original Bitcoin white-paper, states that the security of the system is guaranteed as long as there is no attacker in possession of half or more of the total computational power used to maintain the system. This claim, however, is proved based on theoretically flawed assumptions. In the paper we analyze two kinds of attacks based on two theoretical flaws: the Block Discarding Attack and the Difficulty Raising Attack. We argue that the current theoretical limit of attacker's fraction of total computational power essential for the security of the system is in a sense not $\frac{1}{2}$ but a bit less than $\frac{1}{4}$, and outline proposals for protocol change that can raise this limit to be as close to $\frac{1}{2}$ as we want. The basic idea of the Block Discarding Attack has been noted as early as 2010, and lately was independently though-of and analyzed by both author of this paper and authors of a most recently pre-print published paper. We thus focus on the major differences of our analysis, and try to explain the unfortunate surprising coincidence. To the best of our knowledge, the second attack is presented here for the first time.