Marshall Ball

Prof. Marshall Ball

orcid

Research Focus & Metrics

Academic Career Length

5Years (2022-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
15 April 2023
Verified
Book Chapter
Closed access
PDF file
MBMarshall Ball
Marshall Ball
HLHanjun Li
Hanjun Li
HLHuijia Lin
Huijia Lin
TLTianren Liu
Tianren Liu

12 October 2022
Verified
Book Chapter
Closed access
PDF file
MBMarshall Ball
Marshall Ball
DDDana Dachman-Soled
Dana Dachman-Soled
JLJulian Loss
Julian Loss

6 November 2023
Verified
Conference Paper
Closed access
MBMarshall Ball
Marshall Ball
YLYanyi Liu
Yanyi Liu
NMNoam Mazor
Noam Mazor
RPRafael Pass
Rafael Pass
Only a handful candidates for computational assumptions that imply secure key-agreement protocols (KA) are known, and even fewer are believed to be quantum safe. In this paper, we present a new hardness assumption-the worst-case hardness of a promise problem related to an interactive version of Kolmogorov Complexity. Roughly speaking, the promise problem requires telling apart tuples of strings $(\pi, x, y)$ with relatively (w.r.t. $\mathrm{K}(\pi)$) low time-bounded Interactive Kolmogorov Complexity $\left(\mathrm{IK}^{t}\right)$, and those with relatively high Kolmogorov complexity, given the promise that $\mathrm{K}^{t}(x \mid y)\lt s, \mathrm{~K}^{t}(y \mid x)\lt s$ and $s=\log n$, and where $\mathrm{IK}^{t}(\pi ; x ; y)$ is defined as the length of the shortest pair of t-bounded TMs $(A, B)$ such that the interaction of $(A, B)$ lead to the transcript $\pi$ and the respective outputs $x, y$. We demonstrate that when t is some polynomial, then not only does this hardness assumption imply the existence of KA, but it is also necessary for the existence of secure KA. As such, it yields the first natural hardness assumption characterizing the existence of key-agreement protocols. We additionally show that when the threshold s is bigger (e.g., $s=55 \log n$), then the (worst-case) hardness of this problem instead characterizes the existence of one-way functions (OWFs). As such, our work also clarifies exactly what it would take to base KA on the existence of OWFs, and demonstrates that this question boils down to demonstrating a worst-case reduction between two closely related promise problems.

28 April 2024
Verified
Book Chapter
Closed access
PDF file
MBMarshall Ball
Marshall Ball
RSRonen Shaltiel
Ronen Shaltiel
JSJad Silbak
Jad Silbak

28 July 2022 in Entropy
Verified
Journal Article
Open access
PDF file
DADivesh Aggarwal
Divesh Aggarwal
MBMarshall Ball
Marshall Ball
MOMaciej Ob
Maciej Ob
Non-malleable codes are a natural relaxation of error correction and error detection codes applicable in scenarios where error-correction or error-detection is impossible. Over the last decade, non-malleable codes have been studied for a wide variety of tampering families. Among the most well studied of these is the split-state family of tampering channels, where the codeword is split into two or more parts and each part is tampered with independently. We survey various constructions and applications of non-malleable codes in the split-state model.

16 August 2024
Verified
Book Chapter
Closed access
PDF file
MBMarshall Ball
Marshall Ball
JGJuan Garay
Juan Garay
PHPeter Hall
Peter Hall
AKAggelos Kiayias
Aggelos Kiayias
GPGiorgos Panagiotakos
Giorgos Panagiotakos