One-way functions are central to classical cryptography. They are necessary for the existence of non-trivial classical cryptosystems, and also sufficient to realize meaningful primitives including commitments, pseudorandom generators and digital signatures. At the same time, a mounting body of evidence suggests that assumptions even weaker than one-way functions may suffice for many cryptographic tasks of interest in a quantum world, including bit commitments and secure multi-party computation. This work studies one-way state generators [Morimae-Yamakawa, CRYPTO 2022], a natural quantum relaxation of one-way functions. Given a secret key, a one-way state generator outputs a hard to invert quantum state. A fundamental question is whether this type of quantum one-wayness suffices to realize quantum cryptography. We obtain an affirmative answer to this question, by proving that one-way state generators with pure state outputs imply quantum bit commitments and secure multiparty computation. Along the way, we use efficient shadow tomography [Huang et. al., Nature Physics 2020] to build an intermediate primitive with classical outputs, which we call a (quantum) one-way puzzle. Our main technical contribution is a proof that one-way puzzles imply quantum bit commitments. This proof develops new techniques for pseudoentropy generation [Hastad et. al., SICOMP 1999] from arbitrary distributions, which may be of independent interest.

We study verifiable outsourcing of computation in a model where the verifier has black-box access to the function being computed. We introduce the problem of oracle-aided batch verification of computation (OBVC) for a function class $$\mathcal {F}$$ . This allows a verifier to efficiently verify the correctness of any $$f \in \mathcal {F}$$ evaluated on a batch of n instances $$x_1, \ldots , x_n$$ , while only making $$\lambda $$ calls to an oracle for f (along with $$O(n \lambda )$$ calls to low-complexity helper oracles), for security parameter $$\lambda $$ . We obtain the following positive and negative results:

We construct a succinct non-interactive publicly-verifiable delegation scheme for any log-space uniform circuit under the sub-exponential Learning With Errors (LWE) assumption. For a circuit C:{0,1}N→{0,1} of size S and depth D, the prover runs in time poly(S), the communication complexity is D · polylog(S), and the verifier runs in time (D+N) ·polylog(S). To obtain this result, we introduce a new cryptographic primitive: a lossy correlation-intractable hash function family. We use this primitive to soundly instantiate the Fiat-Shamir transform for a large class of interactive proofs, including the interactive sum-check protocol and the GKR protocol, assuming the sub-exponential hardness of LWE.

The round complexity of zero-knowledge protocols is a long-standing open question, yet to be settled under standard assumptions. So far, the question has appeared equally challenging for relaxations such as weak zero-knowledge and witness hiding. Protocols satisfying these relaxed notions under standard assumptions have at least four messages, just like full-fledged zero-knowledge. The difficulty in improving round complexity stems from a fundamental barrier: none of these notions can be achieved in three messages via reductions (or simulators) that treat the verifier as a black box.

We construct a delegation scheme for verifying non-deterministic computations, with complexity proportional only to the non-deterministic space of the computation. Specifically, letting n denote the input length, we construct a delegation scheme for any language verifiable in non-deterministic time and space (T(n), S(n)) with communication complexity poly(S(n)), verifier runtime n.polylog(T(n))+poly(S(n)), and prover runtime poly(T(n)).

Non-malleable commitments, introduced by Dolev, Dwork and Naor (STOC 1991), are a fundamental cryptographic primitive, and their round complexity has been a subject of great interest. And yet, the goal of achieving non-malleable commitments with only one or two rounds has been elusive. Pass (TCC 2013) captured this difficulty by proving important impossibility results regarding two-round non-malleable commitments. This led to the widespread belief that achieving two-round nonmalleable commitments was impossible from standard assumptions. We show that this belief was false. Indeed, we obtain the following positive results: We construct two-message non-malleable commitments satisfying non-malleability with respect to commitment, based on standard sub-exponential assumptions, namely: sub-exponential one-way permutations, sub-exponential ZAPs, and sub-exponential DDH. Furthermore, our protocol is public-coin.; We obtain two-message private-coin non-malleable commitments with respect to commitment, assuming only sub-exponential DDH or QR or Nth-residuosity.; We bootstrap the above protocols (under the same assumptions) to obtain two round constant boundedconcurrent non-malleable commitments. In the simultaneous message model, we obtain unbounded concurrent non-malleability in two rounds.; In the simultaneous messages model, we obtain oneround non-malleable commitments, with unbounded concurrent security with respect to opening, under standard sub-exponential assumptions.; This implies non-interactive non-malleable commitments with respect to opening, in a restricted model with a broadcast channel, and a-priori bounded polynomially many parties such that every party is aware of every other party in the system. To the best of our knowledge, this is the first protocol to achieve completely non-interactive non-malleability in any plain model setting from standard assumptions.; As an application of this result, in the simultaneous exchange model, we obtain two-round multi-party pseudorandom coin-flipping.; We construct two-message zero-knowledge arguments with super-polynomial strong simulation (SPSS-ZK), which also serve as an important tool for our constructions of non-malleable commitments.; In order to obtain our results, we develop several techniques that may be of independent interest.; We give the first two-round black-box rewinding strategy based on standard sub-exponential assumptions, in the plain model.;- We also give a two-round tag amplification technique for non-malleable commitments, that amplifies a 4-tag scheme to a scheme for all tags, while relying on sub-exponential DDH. This includes a more efficient alternative to the DDN encoding.

We construct two-message non-malleable commitments with respect to opening in the standard model, assuming only one-to-one one-way functions. Our protocol consists of two unidirectional messages by the committer (with no message from the receiver), and is secure against all polynomial-time adversaries in the standard synchronous setting. Pass (TCC 2013) proved that any commitment scheme with non-malleability with respect to commitment, using only 2 rounds of communication, cannot be proved secure via a black-box reduction to any "standard" intractability assumption. We extend this by showing a similar impossibility result for commitments with non-malleability with respect to opening, another standard notion of non-malleability for commitments, for any 2-message challenge-response protocol, as well. However, somewhat surprisingly, we show that this barrier breaks down in the setting of two unidirectional messages by the committer (with no message from the receiver), for non-malleability with respect to opening.°Our protocol makes only black-box use of any non-interactive statistically binding commitment scheme. Such a scheme can be based on any one-to-one one-way function.°Our techniques depart significantly from the commit-challenge-response structure followed by nearly all prior works on non-malleable protocols in the standard model. Our methods are combinatorial in nature.°Our protocol resolves the round complexity of commitments with non-malleability with respect to opening via natural (non-embedding) black-box security reductions. We show that completely non-interactive non-malleable commitments w.r.t. opening cannot be proved secure via most natural black-box reductions. This result extends to also rule out bi-directional two-message non-malleable commitments w.r.t. opening in the synchronous or asynchronous setting.°Our protocol, together with our impossibility result, also resolves the round complexity of block-wise non-malleable codes (Chandran et al) w.r.t. natural black-box reductions.

We study the cryptographic complexity of two-party differentially-private protocols for a large natural class of boolean functionalities. Information theoretically, McGregor et al. [FOCS 2010] and Goyal et al. [Crypto 2013] demonstrated several functionalities for which the maximal possible accuracy in the distributed setting is significantly lower than that in the client-server setting. Goyal et al. [Crypto 2013] further showed that "highly accurate" protocols in the distributed setting for any non-trivial functionality in fact imply the existence of one-way functions. However, it has remained an open problem to characterize the exact cryptographic complexity of this class. In particular, we know that semi-honest oblivious transfer helps obtain optimally accurate distributed differential privacy. But we do not know whether the reverse is true. We study the following question: Does the existence of optimally accurate distributed differentially private protocols for any class of functionalities imply the existence of oblivious transfer (or equivalently secure multi-party computation)? We resolve this question in the affirmative for the class of boolean functionalities that contain an XOR embedded on adjacent inputs. We give a reduction from oblivious transfer to: - Any distributed optimally accurate epsilon-differentially private protocol with epsilon > 0 computing a functionality with a boolean XOR embedded on adjacent inputs. - Any distributed non-optimally accurate epsilon-differentially private protocol with epsilon > 0, for a constant range of non-optimal accuracies and constant range of values of epsilon, computing a functionality with a boolean XOR embedded on adjacent inputs. Enroute to proving these results, we demonstrate a connection between optimally-accurate twoparty differentially-private protocols for functions with a boolean XOR embedded on adjacent inputs, and noisy channels, which were shown by Crépeau and Kilian [FOCS 1988] to be sufficient for oblivious transfer.

While DES has been proven to be breakable within a day given sufficient computational power, AES is still in use because it is extremely resistant to cryptanalytic attacks. Power Analytic Attacks use power consumption traces of the hardware or software implementation of these algorithms to reduce search space exponentially in the size of the key, thereby making computational complexity several orders of magnitude lower. This paper analyzes the increase in the computational advantage of an adversary who uses DPA and higher order power analysis attacks as opposed to algorithmic cryptanalysis. We highlight why there can be no perfect masking against DPA, and then define a standard for the security of masking countermeasures to such attacks. The main contribution is a security metric for systems and a cut-off for the number of encryptions allowable for a given order of masking to make the system immune to higher order DPA attacks.