Marshall Ball

Divesh Aggarwal, Naresh Goud Boddu, Rahul Jain

Non-malleable-codes introduced by Dziembowski, Pietrzak and Wichs [DPW18] encode a classical message $S$ in a manner such that tampering the codeword results in the decoder either outputting the original message $S$ or a message that is unrelated/independent of $S$. Providing such non-malleable security for various tampering function families has received significant attention in recent years. We consider the well-studied (2-part) split-state model, in which the message $S$ is encoded into two parts $X$ and $Y$, and the adversary is allowed to arbitrarily tamper with each $X$ and $Y$ individually. We consider the security of non-malleable-codes in the split-state model when the adversary is allowed to make use of arbitrary entanglement to tamper the parts $X$ and $Y$. We construct explicit quantum secure non-malleable-codes in the split-state model. Our construction of quantum secure non-malleable-codes is based on the recent construction of quantum secure $2$-source non-malleable-extractors by Boddu, Jain and Kapshikar [BJK21].

Michael Dubrovsky, Marshall Ball, Bogdan Penkovsky

Most cryptocurrencies rely on Proof-of-Work (PoW) "mining" for resistance to Sybil and double-spending attacks, as well as a mechanism for currency issuance. Hashcash PoW has successfully secured the Bitcoin network since its inception, however, as the network has expanded to take on additional value storage and transaction volume, Bitcoin PoW's heavy reliance on electricity has created scalability issues, environmental concerns, and systemic risks. Mining efforts have concentrated in areas with low electricity costs, creating single points of failure. Although PoW security properties rely on imposing a trivially verifiable economic cost on miners, there is no fundamental reason for it to consist primarily of electricity cost. The authors propose a novel PoW algorithm, Optical Proof of Work (oPoW), to eliminate energy as the primary cost of mining. Proposed algorithm imposes economic difficulty on the miners, however, the cost is concentrated in hardware (capital expense-CAPEX) rather than electricity (operating expenses-OPEX). The oPoW scheme involves minimal modifications to Hashcash-like PoW schemes, inheriting safety/security properties from such schemes. Rapid growth and improvement in silicon photonics over the last two decades has led to the commercialization of silicon photonic co-processors (integrated circuits that use photons instead of electrons to perform specialized computing tasks) for low-energy deep learning. oPoW is optimized for this technology such that miners are incentivized to use specialized, energy-efficient photonics for computation. Beyond providing energy savings, oPoW has the potential to improve network scalability, enable decentralized mining outside of low electricity cost areas, and democratize issuance. Due to the CAPEX dominance of mining costs, oPoW hashrate will be significantly less sensitive to underlying coin price declines.

Marshall Ball, Dana Dachman-Soled, Siyao Guo et al.

We construct efficient, unconditional non-malleable codes that are secure against tampering functions computed by small-depth circuits. For constant-depth circuits of polynomial size (i.e. $\mathsf{AC^0}$ tampering functions), our codes have codeword length $n = k^{1+o(1)}$ for a $k$-bit message. This is an exponential improvement of the previous best construction due to Chattopadhyay and Li (STOC 2017), which had codeword length $2^{O(\sqrt{k})}$. Our construction remains efficient for circuit depths as large as $Θ(\log(n)/\log\log(n))$ (indeed, our codeword length remains $n\leq k^{1+ε})$, and extending our result beyond this would require separating $\mathsf{P}$ from $\mathsf{NC^1}$. We obtain our codes via a new efficient non-malleable reduction from small-depth tampering to split-state tampering. A novel aspect of our work is the incorporation of techniques from unconditional derandomization into the framework of non-malleable reductions. In particular, a key ingredient in our analysis is a recent pseudorandom switching lemma of Trevisan and Xue (CCC 2013), a derandomization of the influential switching lemma from circuit complexity; the randomness-efficiency of this switching lemma translates into the rate-efficiency of our codes via our non-malleable reduction.