All reports by Author Noam Mazor:

__
TR24-055
| 12th March 2024
__

Marshall Ball, Yanyi Liu, Noam Mazor, Rafael Pass#### Kolmogorov Comes to Cryptomania: On Interactive Kolmogorov Complexity and Key-Agreement

__
TR24-053
| 10th March 2024
__

Noam Mazor, Rafael Pass#### Gap MCSP is not (Levin) NP-complete in Obfustopia

__
TR24-003
| 2nd January 2024
__

Noam Mazor, Rafael Pass#### Search-to-Decision Reductions for Kolmogorov Complexity

__
TR23-192
| 28th November 2023
__

Noam Mazor, Rafael Pass#### A Note On the Universality of Black-box MKtP Solvers

Revisions: 1

__
TR23-175
| 15th November 2023
__

Noam Mazor, Rafael Pass#### The Non-Uniform Perebor Conjecture for Time-Bounded Kolmogorov Complexity is False

__
TR23-143
| 22nd September 2023
__

Noam Mazor, Rafael Pass#### Counting Unpredictable Bits: A Simple PRG from One-way Functions

Revisions: 1

__
TR23-123
| 21st August 2023
__

Noam Mazor#### Key-Agreement with Perfect Completeness from Random Oracles

__
TR23-013
| 7th February 2023
__

Noam Mazor#### A Lower Bound on the Share Size in Evolving Secret Sharing

Revisions: 1

__
TR22-049
| 4th April 2022
__

Xinyu Mao, Noam Mazor, Jiapeng Zhang#### Non-Adaptive Universal One-Way Hash Functions from Arbitrary One-Way Functions

Revisions: 2

__
TR22-032
| 1st March 2022
__

Iftach Haitner, Noam Mazor, Jad Silbak#### Incompressiblity and Next-Block Pseudoentropy

__
TR21-124
| 17th August 2021
__

Iftach Haitner, Noam Mazor, Jad Silbak, Eliad Tsfadia#### On the Complexity of Two-Party Differential Privacy

Revisions: 1

__
TR20-089
| 8th June 2020
__

Dror Chawin, Iftach Haitner, Noam Mazor#### Lower Bounds on the Time/Memory Tradeoff of Function Inversion

Revisions: 1

__
TR19-081
| 31st May 2019
__

Iftach Haitner, Noam Mazor, Ronen Shaltiel, Jad Silbak#### Channels of Small Log-Ratio Leakage and Characterization of Two-Party Differentially Private Computation

Revisions: 1

__
TR18-031
| 15th February 2018
__

Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, Amir Yehudayoff#### On the Communication Complexity of Key-Agreement Protocols

Revisions: 2

Marshall Ball, Yanyi Liu, Noam Mazor, 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 ...
more >>>

Noam Mazor, Rafael Pass

We demonstrate that under believable cryptographic hardness assumptions, Gap versions of standard meta-complexity problems, such as the Minimum Circuit Size problem (MCSP) and the Minimum Time-Bounded Kolmogorov Complexity problem (MKTP) are not NP-complete w.r.t. Levin (i.e., witness-preserving many-to-one) reductions.

In more detail:

- Assuming the existence of indistinguishability obfuscation, and ...
more >>>

Noam Mazor, Rafael Pass

A long-standing open problem dating back to the 1960s is whether there exists a search-to-decision reduction for the time-bounded Kolmogorov complexity problem - that is, the problem of determining whether the length of the shortest time-$t$ program generating a given string $x$ is at most $s$.

In this work, we ... more >>>

Noam Mazor, Rafael Pass

The relationships between various meta-complexity problems are not well understood in the worst-case regime, including whether the search version is harder than the decision version, whether the hardness scales with the ``threshold", and how the hardness of different meta-complexity problems relate to one another, and to the task of function ... more >>>

Noam Mazor, Rafael Pass

The Perebor (Russian for “brute-force search”) conjectures, which date back to the 1950s and 1960s are some of the oldest conjectures in complexity theory. The conjectures are a stronger form of the NP ? = P conjecture (which they predate) and state that for “meta-complexity” problems, such as the Time-bounded ... more >>>

Noam Mazor, Rafael Pass

A central result in the theory of Cryptography, by Hastad, Imagliazzo, Luby and Levin [SICOMP’99], demonstrates that the existence one-way functions (OWF) implies the existence of pseudo-random generators (PRGs). Despite the fundamental importance of this result, and several elegant improvements/simplifications, analyses of constructions of PRGs from OWFs remain complex (both ... more >>>

Noam Mazor

In the Random Oracle Model (ROM) all parties have oracle access to a common random function, and the parties are limited in the number of queries they can make to the oracle. The Merkle’s Puzzles protocol, introduced by Merkle [CACM ’78], is a key-agreement protocol in the ROM with a ... more >>>

Noam Mazor

Secret sharing schemes allow sharing a secret between a set of parties in a way that ensures that only authorized subsets of the parties learn the secret. Evolving secret sharing schemes (Komargodski, Naor, and Yogev [TCC ’16]) allow achieving this end in a scenario where the parties arrive in an ... more >>>

Xinyu Mao, Noam Mazor, Jiapeng Zhang

Two of the most useful cryptographic primitives that can be constructed from one-way functions are pseudorandom generators (PRGs) and universal one-way hash functions (UOWHFs). The three major efficiency measures of these primitives are: seed length, number of calls to the one-way function, and adaptivity of these calls. Although a long ... more >>>

Iftach Haitner, Noam Mazor, Jad Silbak

A distribution is k-incompressible, Yao [FOCS ’82], if no efficient compression scheme compresses it to less than k bits. While being a natural measure, its relation to other computational analogs of entropy such as pseudoentropy, Hastad, Impagliazzo, Levin, and Luby [SICOMP 99], and to other cryptographic hardness assumptions, was unclear.

... more >>>Iftach Haitner, Noam Mazor, Jad Silbak, Eliad Tsfadia

In distributed differential privacy, the parties perform analysis over their joint data while preserving the privacy for both datasets. Interestingly, for a few fundamental two-party functions such as inner product and Hamming distance, the accuracy of the distributed solution lags way behind what is achievable in the client-server setting. McGregor, ... more >>>

Dror Chawin, Iftach Haitner, Noam Mazor

We study time/memory tradeoffs of function inversion: an algorithm, i.e., an inverter, equipped with an $s$-bit advice for a randomly chosen function $f\colon [n] \mapsto [n]$ and using $q$ oracle queries to $f$, tries to invert a randomly chosen output $y$ of $f$ (i.e., to find $x$ such that $f(x)=y$). ... more >>>

Iftach Haitner, Noam Mazor, Ronen Shaltiel, Jad Silbak

Consider a PPT two-party protocol ?=(A,B) in which the parties get no private inputs and obtain outputs O^A,O^B?{0,1}, and let V^A and V^B denote the parties’ individual views. Protocol ? has ?-agreement if Pr[O^A=O^B]=1/2+?. The leakage of ? is the amount of information a party obtains about the event {O^A=O^B}; ... more >>>

Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, Amir Yehudayoff

Key-agreement protocols whose security is proven in the random oracle model are an important alternative to the more common public-key based key-agreement protocols. In the random oracle model, the parties and the eavesdropper have access to a shared random function (an "oracle"), but they are limited in the number of ... more >>>