Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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 >>>

TR24-053 | 10th March 2024
Noam Mazor, Rafael Pass

Gap MCSP is not (Levin) NP-complete in Obfustopia

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 >>>

TR24-003 | 2nd January 2024
Noam Mazor, Rafael Pass

Search-to-Decision Reductions for Kolmogorov Complexity

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 >>>

TR23-192 | 28th November 2023
Noam Mazor, Rafael Pass

A Note On the Universality of Black-box MKtP Solvers

Revisions: 1

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 >>>

TR23-175 | 15th November 2023
Noam Mazor, Rafael Pass

The Non-Uniform Perebor Conjecture for Time-Bounded Kolmogorov Complexity is False

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 >>>

TR23-143 | 22nd September 2023
Noam Mazor, Rafael Pass

Counting Unpredictable Bits: A Simple PRG from One-way Functions

Revisions: 1

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 >>>

TR23-123 | 21st August 2023
Noam Mazor

Key-Agreement with Perfect Completeness from Random Oracles

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 >>>

TR23-013 | 7th February 2023
Noam Mazor

A Lower Bound on the Share Size in Evolving Secret Sharing

Revisions: 1

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 >>>

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

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 >>>

TR22-032 | 1st March 2022
Iftach Haitner, Noam Mazor, Jad Silbak

Incompressiblity and Next-Block Pseudoentropy

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 >>>

TR21-124 | 17th August 2021
Iftach Haitner, Noam Mazor, Jad Silbak, Eliad Tsfadia

On the Complexity of Two-Party Differential Privacy

Revisions: 1

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 >>>

TR20-089 | 8th June 2020
Dror Chawin, Iftach Haitner, Noam Mazor

Lower Bounds on the Time/Memory Tradeoff of Function Inversion

Revisions: 1

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 >>>

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

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 >>>

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

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 >>>

ISSN 1433-8092 | Imprint