Oded Goldreich, Rafail Ostrovsky, Erez Petrank

We study the computational complexity of languages which have

interactive proofs of logarithmic knowledge complexity. We show that

all such languages can be recognized in ${\cal BPP}^{\cal NP}$. Prior

to this work, for languages with greater-than-zero knowledge

complexity (and specifically, even for knowledge complexity 1) only

trivial computational complexity bounds ...
more >>>

Oded Goldreich, Leonid Levin, Noam Nisan

We show how to construct length-preserving 1-1 one-way

functions based on popular intractability assumptions (e.g., RSA, DLP).

Such 1-1 functions should not

be confused with (infinite) families of (finite) one-way permutations.

What we want and obtain is a single (infinite) 1-1 one-way function.

Joe Kilian, Erez Petrank

We consider noninteractive zero-knowledge proofs in the shared random

string model proposed by Blum, Feldman and Micali \cite{bfm}. Until

recently there was a sizable polynomial gap between the most

efficient noninteractive proofs for {\sf NP} based on general

complexity assumptions \cite{fls} versus those based on specific

algebraic assumptions \cite{Da}. ...
more >>>

Oded Goldreich, Shai Halevi

Recently Ajtai described a construction of one-way functions whose

security is equivalent to the difficulty of some well known approximation

problems in lattices. We show that essentially the same

construction can also be used to obtain collision-free hashing.

Oded Goldreich, Shai Halevi

Following Ajtai's lead, Ajtai and Dwork have recently introduced a

public-key encryption scheme which is secure under the assumption

that a certain computational problem on lattices is hard on the

worst-case. Their encryption method may cause decryption errors,

though with small probability (i.e., inversely proportional to the

more >>>

Eli Biham, Dan Boneh, Omer Reingold

The Diffie-Hellman key-exchange protocol may naturally be

extended to k>2 parties. This gives rise to the generalized

Diffie-Hellman assumption (GDH-Assumption).

Naor and Reingold have recently shown an efficient construction

of pseudo-random functions and reduced the security of their

construction to the GDH-Assumption.

In this note, we ...
more >>>

Phong Nguyen, Jacques Stern

Recently, Ajtai discovered a fascinating connection

between the worst-case complexity and the average-case

complexity of some well-known lattice problems.

Later, Ajtai and Dwork proposed a cryptosystem inspired

by Ajtai's work, provably secure if a particular lattice

problem is difficult. We show that there is a converse

to the ...
more >>>

Matthias Krause, Hans Ulrich Simon

This paper shows that the largest possible contrast C(k,n)

in a k-out-of-n secret sharing scheme is approximately

4^(-(k-1)). More precisely, we show that

4^(-(k-1)) <= C_{k,n} <= 4^(-(k-1))}n^k/(n(n-1)...(n-(k-1))).

This implies that the largest possible contrast equals

4^(-(k-1)) in the limit when n approaches ...
more >>>

Matthias Krause, Stefan Lucks

\begin{abstract}

A set $F$ of $n$-ary Boolean functions is called a pseudorandom function generator

(PRFG) if communicating

with a randomly chosen secret function from $F$ cannot be

efficiently distinguished from communicating with a truly random function.

We ask for the minimal hardware complexity of a PRFG. This question ...
more >>>

Maria Isabel Gonzalez Vasco, Igor E. Shparlinski

Boneh and Venkatesan have recently proposed a polynomial time

algorithm for recovering a ``hidden'' element $\alpha$ of a

finite field $\F_p$ of $p$ elements from rather short

strings of the most significant bits of the remainder

mo\-du\-lo $p$ of $\alpha t$ for several values of $t$ selected uniformly

at random ...
more >>>

Maria Isabel Gonzalez Vasco, Igor E. Shparlinski

Boneh and Venkatesan have recently proposed a polynomial time

algorithm for recovering a ``hidden'' element $\alpha$ of a

finite field $\F_p$ of $p$ elements from rather short

strings of the most significant bits of the remainder

mo\-du\-lo $p$ of $\alpha t$ for several values of $t$ selected

uniformly at ...
more >>>

Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, Ke Yang

Informally, an <i>obfuscator</i> <b>O</b> is an (efficient, probabilistic)

"compiler" that takes as input a program (or circuit) <b>P</b> and

produces a new program <b>O(P)</b> that has the same functionality as <b>P</b>

yet is "unintelligible" in some sense. Obfuscators, if they exist,

would have a wide variety of cryptographic ...
more >>>

Moni Naor, Omer Reingold, Alon Rosen

Factoring integers is the most established problem on which

cryptographic primitives are based. This work presents an efficient

construction of {\em pseudorandom functions} whose security is based

on the intractability of factoring. In particular, we are able to

construct efficient length-preserving pseudorandom functions where

each evaluation requires only a ...
more >>>

Oded Goldreich

We consider the function ensembles emerging from the

construction of Goldreich, Goldwasser and Micali (GGM),

when applied to an arbitrary pseudoramdon generator.

We show that, in general, such functions

fail to yield correlation intractable ensembles.

Specifically, it may happen that, given a description of such a ...
more >>>

Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey

We study the role of connectivity of communication networks in private

computations under information theoretic settings. It will be shown that

some functions can be computed by private protocols even if the

underlying network is 1-connected but not 2-connected. Then we give a

complete characterisation of non-degenerate functions that can ...
more >>>

Yael Tauman Kalai

In 1986, Fiat and Shamir suggested a general method for transforming secure 3-round public-coin identification schemes into digital signature schemes. The significant contribution of this method is a means for designing efficient digital signatures, while hopefully achieving security against chosen message attacks. All other known constructions which achieve such security ... more >>>

Daniele Micciancio

Lattices have received considerable attention as a potential source of computational hardness to be used in cryptography, after a breakthrough result of Ajtai (STOC 1996) connecting the average-case and worst-case complexity of various lattice problems. The purpose of this paper is twofold. On the expository side, we present a rigorous ... more >>>

Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey

We study private computations in information-theoretical settings on

networks that are not 2-connected. Non-2-connected networks are

``non-private'' in the sense that most functions cannot privately be

computed on such networks. We relax the notion of privacy by

introducing lossy private protocols, which generalize private

protocols. We measure the information each ...
more >>>

Yehuda Lindell, Benny Pinkas

In the mid 1980's, Yao presented a constant-round protocol for

securely computing any two-party functionality in the presence of

semi-honest adversaries (FOCS 1986). In this paper, we provide a

complete description of Yao's protocol, along with a rigorous

proof of security. Despite the importance of Yao's protocol to the

field ...
more >>>

Thomas Holenstein

Assume that Alice and Bob, given an authentic channel, have a protocol where they end up with a bit S_A and S_B, respectively, such that with probability (1+eps)/2 these bits are equal. Further assume that conditioned on the event S_A = S_B no polynomial time bounded algorithm can predict the ... more >>>

Saurabh Sanghvi, Salil Vadhan

We study the round complexity of two-party protocols for

generating a random $n$-bit string such that the output is

guaranteed to have bounded bias (according to some measure) even

if one of the two parties deviates from the protocol (even using

unlimited computational resources). Specifically, we require that

the output's ...
more >>>

Ronen Gradwohl, Salil Vadhan, David Zuckerman

We consider the problem of random selection, where $p$ players follow a protocol to jointly select a random element of a universe of size $n$. However, some of the players may be adversarial and collude to force the output to lie in a small subset of the universe. We describe ... more >>>

Jonathan Katz, Chiu-Yuen Koo

In a seminal paper, Feldman and Micali (STOC '88) show an n-party Byzantine agreement protocol tolerating t < n/3 malicious parties that runs in expected constant rounds. Here, we show an expected constant-round protocol for authenticated Byzantine agreement assuming honest majority (i.e., $t < n/2$), and relying only on the ... more >>>

Salil Vadhan

We prove a number of general theorems about ZK, the class of problems possessing (computational) zero-knowledge proofs. Our results are unconditional, in contrast to most previous works on ZK, which rely on the assumption that one-way functions exist.

We establish several new characterizations of ZK, and use these characterizations to ... more >>>

Minh-Huyen Nguyen, Shien Jin Ong, Salil Vadhan

We show that every language in NP has a *statistical* zero-knowledge

argument system under the (minimal) complexity assumption that

one-way functions exist. In such protocols, even a computationally

unbounded verifier cannot learn anything other than the fact that the

assertion being proven is true, whereas a polynomial-time prover

cannot convince ...
more >>>

Lance Fortnow, Rahul Santhanam

We study the notion of "instance compressibility" of NP problems [Harnik-Naor06], closely related to the notion of kernelization in parameterized complexity theory [Downey-Fellows99, Flum-Grohe06, Niedermeier06]. A language $L$ in NP is instance compressible if there

is a polynomial-time computable function $f$ and a set $A$ such that

for each instance ...
more >>>

Manoj Prabhakaran, Mike Rosulek

We develop new tools to study the relative complexities of secure

multi-party computation tasks (functionalities) in the Universal

Composition framework. When one task can be securely realized using

another task as a black-box, we interpret this as a

qualitative, complexity-theoretic reduction between the two tasks.

Virtually all previous characterizations of ...
more >>>

Iftach Haitner, Omer Reingold, Salil Vadhan, Hoeteck Wee

We put forth a new computational notion of entropy, which measures the

(in)feasibility of sampling high entropy strings that are consistent

with a given protocol. Specifically, we say that the i'th round of a

protocol (A, B) has _accessible entropy_ at most k, if no

polynomial-time strategy A^* can generate ...
more >>>

Daniele Venturi

The principal aim of this notes is to give a survey on the state of the art of algorithmic number theory, with particular focus on the theory of elliptic curves.

Computational security is the goal of modern cryptographic constructions: the security of modern criptographic schemes stems from the assumption ...
more >>>

Panagiotis Voulgaris, Daniele Micciancio

We present new faster algorithms for the exact solution of the shortest vector problem in arbitrary lattices. Our main result shows that the shortest vector in any $n$-dimensional lattice can be found in time $2^{3.199 n}$ and space $2^{1.325 n}$.

This improves the best previously known algorithm by Ajtai, Kumar ...
more >>>

Brett Hemenway, Rafail Ostrovsky

In STOC '08, Peikert and Waters introduced a powerful new primitive called Lossy Trapdoor Functions (LTDFs). Since their introduction, lossy trapdoor functions have found many uses in cryptography. In the work of Peikert and Waters, lossy trapdoor functions were used to give an efficient construction of a chosen-ciphertext secure ... more >>>

Vipul Goyal, Yuval Ishai, Mohammad Mahmoody, Amit Sahai

Motivated by the question of basing cryptographic protocols on stateless tamper-proof hardware tokens, we revisit the question of unconditional two-prover zero-knowledge proofs for $NP$. We show that such protocols exist in the {\em interactive PCP} model of Kalai and Raz (ICALP '08), where one of the provers is replaced by ... more >>>

Brett Hemenway, Rafail Ostrovsky

Injective one-way trapdoor functions are one of the most fundamental cryptographic primitives. In this work we give a novel construction of injective trapdoor functions based on oblivious transfer for long strings.

Our main result is to show that any 2-message statistically sender-private semi-honest oblivious transfer (OT) for ...
more >>>

Zeev Dvir, Dan Gutfreund, Guy Rothblum, Salil Vadhan

We investigate the complexity of the following computational problem:

Polynomial Entropy Approximation (PEA):

Given a low-degree polynomial mapping

$p : F^n\rightarrow F^m$, where $F$ is a finite field, approximate the output entropy

$H(p(U_n))$, where $U_n$ is the uniform distribution on $F^n$ and $H$ may be any of several entropy measures.

Salil Vadhan, Colin Jia Zheng

We provide a characterization of pseudoentropy in terms of hardness of sampling: Let $(X,B)$ be jointly distributed random variables such that $B$ takes values in a polynomial-sized set. We show that $B$ is computationally indistinguishable from a random variable of higher Shannon entropy given $X$ if and only if there ... more >>>

Mahdi Cheraghchi, Venkatesan Guruswami

Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), encode messages $s$ in a manner so that tampering the codeword causes the decoder to either output $s$ or a message that is independent of $s$. While this is an impossible goal to achieve against unrestricted tampering functions, rather surprisingly ... more >>>

Mahdi Cheraghchi, Venkatesan Guruswami

Non-malleable coding, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), aims for protecting the integrity of information against tampering attacks in situations where error-detection is impossible. Intuitively, information encoded by a non-malleable code either decodes to the original message or, in presence of any tampering, to an unrelated message. Non-malleable ... more >>>

Benny Applebaum

Constant parallel-time cryptography allows to perform complex cryptographic tasks at an ultimate level of parallelism, namely, by local functions that each of their output bits depend on a constant number of input bits. A natural way to obtain local cryptographic constructions is to use \emph{random local functions} in which each ... more >>>

Benny Applebaum, Shachar Lovett

Suppose that you have $n$ truly random bits $x=(x_1,\ldots,x_n)$ and you wish to use them to generate $m\gg n$ pseudorandom bits $y=(y_1,\ldots, y_m)$ using a local mapping, i.e., each $y_i$ should depend on at most $d=O(1)$ bits of $x$. In the polynomial regime of $m=n^s$, $s>1$, the only known solution, ... more >>>

Iftach Haitner, Nikolaos Makriyannis, Eran Omri

A two-party coin-flipping protocol is $\varepsilon$-fair if no efficient adversary can bias the output of the honest party (who always outputs a bit, even if the other party aborts) by more than $\varepsilon$. Cleve [STOC '86] showed that $r$-round $o(1/r)$-fair coin-flipping protocols do not exist. Awerbuch et al. [Manuscript '85] ... more >>>

Eric Binnendyk

Boolean circuits are a model of computation. A class of Boolean circuits is called a polynomial class if the number of nodes is bounded by a polynomial function of the number of input variables. A class $C_n[s(n)]$ of Boolean functions is called learnable if there are algorithms that can approximate ... more >>>

tatsuie tsukiji

This paper aims to derandomize the following problems in the smoothed analysis of Spielman and Teng. Learn Disjunctive Normal Form (DNF), invert Fourier Transforms (FT), and verify small circuits' unsatisfiability. Learning algorithms must predict a future observation from the only $m$ i.i.d. samples of a fixed but unknown joint-distribution $P(G(x),y)$ ... more >>>

Scott Aaronson, Shih-Han Hung

We propose an application for near-term quantum devices: namely, generating cryptographically certified random bits, to use (for example) in proof-of-stake cryptocurrencies. Our protocol repurposes the existing "quantum supremacy" experiments, based on random circuit sampling, that Google and USTC have successfully carried out starting in 2019. We show that, whenever the ... more >>>

Shuichi Hirahara, Mikito Nanashima

Pessiland is one of Impagliazzo's five possible worlds in which NP is hard on average, yet no one-way function exists. This world is considered the most pessimistic because it offers neither algorithmic nor cryptographic benefits.

In this paper, we develop a unified framework for constructing strong learning algorithms ... more >>>

Guangxu Yang, Jiapeng Zhang

Collision problems are important problems in complexity theory and cryptography with diverse applications. Previous fruitful works have mainly focused on query models. Driven by various applications, several works by Bauer, Farshim and Mazaheri (CRYPTO 2018), Itsykson and Riazanov (CCC 2021), Göös and Jain (RANDOM 2022) independently proposed the communication version ... more >>>

Shuo Wang, Guangxu Yang, Jiapeng Zhang

Set-disjointness is one of the most fundamental and widely studied problems in the area of communication complexity. In this problem, each party $i$ receives a set $S_i\subseteq [N]$. The goal is to determine whether $\bigcap S_i$ is empty via communication between players. The decision version simply asks if the common ... more >>>

Eldon Chung, Alexander Golovnev, Zeyong Li, Maciej Obremski, Sidhant Saraogi, Noah Stephens-Davidowitz

We study the Range Avoidance Problem (Avoid), in which the input is an expanding circuit $C : \{0,1\}^n \to \{0,1\}^{n+1}$, and the goal is to find a $y \in \{0,1\}^{n+1}$ that is not in the image of $C$. We are interested in the randomized complexity of this problem, i.e., in ... more >>>