In this work, we give an optimal analysis of the plane versus plane test of Raz and Safra (STOC'97). More specifically, consider a table \(\mathcal{T}\) that assigns every plane \(P\) from \(\mathbb{F}_q^m\) a bivariate degree \(d\) polynomial. The goal is to check if these polynomials are restrictions of a global degree \(d\) polynomial \(f : \mathbb{F}_q^m \to \mathbb{F}_q\). Raz and Safra introduced the following natural test: sample two random planes \(P, P'\) intersecting in a line \(\ell\) and check if \(\mathcal{T}(P)|_{\ell} = \mathcal{T}(P')|_{\ell}\), i.e., the two table entries agree on the points on~\(\ell\).

Random walks in expander graphs and their various derandomizations (e.g., replacement/zig-zag product) are invaluable tools from pseudorandomness. Recently, Ta-Shma used$s$-wide replacement walks in his breakthrough construction of a binary linear code almost matching the Gilbert-Varshamov bound (STOC 2017). Ta-Shma’s original analysis was entirely linear algebraic, and subsequent developments have inherited this viewpoint. In this work, we rederive Ta-Shma’s analysis from a combinatorial point of view using repeated application of the expander mixing lemma. We hope that this alternate perspective will yield a better understanding of Ta-Shma’s construction. As an additional application of our techniques, we give an alternate proof of the expander hitting set lemma.

We give an efficient algorithm for list-decoding the binary code by Ta-Shma (STOC 2017) to the Johnson Bound. Ta-Shma’s code has distance $\frac{1-\varepsilon}{2}$ and rate $\Omega\left(\varepsilon^{2+o(1)}\right)$ and thus it almost achieves the Gilbert-Varshamov bound. Johnson bound states that such codes are combinatorially list decodable upto $\frac{1-\rho}{2}-$ fraction of errors as long as $\rho \geq \sqrt{\varepsilon}$. We give a polynomial time decoding algorithm that nearly achieves this bound. Thus our result implies the only known binary code that simultaneously nearly achieves both the Gilbert-Varshamov and the Johnson bounds. Our decoding algorithm is based on semidefinite programming hierarchies and includes a new rounding step which might be of independent interest.

In this work we prove a high dimensional analogue of the beloved Goldreich-Levin Theorem (STOC 1989). We consider the following algorithmic problem: given oracle access to a function f:ℤqm→ℤqn such that Prx∼ℤqm[f(x)=Ax]≥ε for some A∈ℤqn× m and ε>0, recover A (or a list of all such matrices). We focus on the case ε≤ 1/q since when ε ≥ 1/q+δ, the problem is solved by the original Goldreich-Levin Theorem. As stated, this problem cannot be efficiently solved, since when ε ≤ 1/q the list of A with good agreement with f might be exponentially large. Our main theorem gives an algorithm which efficiently recovers a list of affine maps of size (1/ε ) which have good agreement with f, and such that every linear map which has good agreement with f, also has good agreement with some affine map in our list. Our proof makes novel use of Fourier analysis. Our main theorem has applications to effective property testing.

Signature-based authentication is a core cryptographic primitive essential for most secure networking protocols. We introduce a new signature scheme, MSS, that allows a client to efficiently authenticate herself to a server. We model our new scheme in an offline/online model where client online time is premium. The offline component derives basis signatures that are then composed based on the data being signed to provide signatures efficiently and securely during run-time. MSS requires the server to maintain state and is suitable for applications where a device has long-term associations with the server. MSS allows direct comparison to hash chains-based authentication schemes used in similar settings, and is relevant to resource-constrained devices e.g., IoT. We derive MSS instantiations for two cryptographic families, assuming the hardness of RSA and decisional Diffie-Hellman (DDH) respectively, demonstrating the generality of the idea. We then use our new scheme to design an efficient time-based one-time password (TOTP) protocol. Specifically, we implement two TOTP authentication systems from our RSA and DDH instantiations. We evaluate the TOTP implementations on Raspberry Pis which demonstrate appealing gains: MSS reduces authentication latency and energy consumption by a factor of ~82 and 792, respectively, compared to a recent hash chain-based TOTP system.

In their seminal work on nonmalleable cryptography, Dolev, Dwork, and Naor showed how to construct a nonmalleable commitment with logarithmically-many “rounds''/``slots,” the idea being that any adversary may successfully maul in some slots but would fail in at least one. Since then new ideas have been introduced, ultimately resulting in constant-round protocols based on any one-way function. Yet, in spite of this remarkable progress, each of the known constructions of nonmalleable commitments leaves something to be desired. In this paper we propose a new technique that allows us to construct a nonmalleable protocol with only a single slot and to improve in at least one aspect over each of the previously proposed protocols. Two direct byproducts of our new ideas are a four-round nonmalleable commitment and a four-round nonmalleable zero-knowledge argument, the latter matching the round-complexity of the best known zero-knowledge argument (without the nonmalleability requirement). The protocols are based on the existence of one-way functions and admit very efficient instantiations via standard homomorphic commitments and sigma protocols. Our analysis relies on algebraic reasoning, and makes use of error correcting codes in order to ensure that committers' tags differ in many coordinates. One way of viewing our construction is as a method for combining many atomic subprotocols in a way that simultaneously amplifies soundness and nonmalleability, thus requiring much weaker guarantees to begin with, and resulting in a protocol which is much trimmer in complexity compared to the existing ones.

We give the first construction of three-round non-malleable commitments from the almost minimal assumption of injective one-way functions. Combined with the lower bound of Pass (TCC 2013), our result is almost the best possible w.r.t. standard polynomial-time hardness assumptions (at least w.r.t. black-box reductions). Our results rely on a novel technique which we call 'bidirectional Goldreich-Levin extraction'. Along the way, we also obtain the first rewind secure delayed-input witness indistinguishable (WI) proofs from only injective one-way functions. We also obtain the first construction of an epsilon-extractable commitment scheme from injective one-way functions. We believe both of these to be of independent interest. In particular, as a direct corollary of our rewind secure WI construction, we are able to obtain a construction of 3-round promise zero-knowledge from only injective one-way functions.

In this work, we examine the feasibility of secure and undetectable point-to-point communication when an adversary (e.g., a government) can read all encrypted communications of surveillance targets. We consider a model where the only permitted method of communication is via a government-mandated encryption scheme, instantiated with government-mandated keys. Parties cannot simply encrypt ciphertexts of some other encryption scheme, because citizens caught trying to communicate outside the government's knowledge (e.g., by encrypting strings which do not appear to be natural language plaintexts) will be arrested. The one guarantee we suppose is that the government mandates an encryption scheme which is semantically secure against outsiders: a perhaps reasonable supposition when a government might consider it advantageous to secure its people's communication against foreign entities. But then, what good is semantic security against an adversary that holds all the keys and has the power to decrypt? We show that even in the pessimistic scenario described, citizens can communicate securely and undetectably. In our terminology, this translates to a positive statement: all semantically secure encryption schemes support subliminal communication. Informally, this means that there is a two-party protocol between Alice and Bob where the parties exchange ciphertexts of what appears to be a normal conversation even to someone who knows the secret keys and thus can read the corresponding plaintexts. And yet, at the end of the protocol, Alice will have transmitted her secret message to Bob. Our security definition requires that the adversary not be able to tell whether Alice and Bob are just having a normal conversation using the mandated encryption scheme, or they are using the mandated encryption scheme for subliminal communication. Our topics may be thought to fall broadly within the realm of steganography. However, we deal with the non-standard setting of an adversarially chosen distribution of cover objects (i.e., a stronger-than-usual adversary), and we take advantage of the fact that our cover objects are ciphertexts of a semantically secure encryption scheme to bypass impossibility results which we show for broader classes of steganographic schemes. We give several constructions of subliminal communication schemes under the assumption that key exchange protocols with pseudorandom messages exist (such as Diffie-Hellman, which in fact has truly random messages).

We present a new non-malleable commitment protocol. Our protocol has the following features: itemize The protocol has only three rounds of interaction. Pass (TCC 2013) showed an impossibility result for a two-round non-malleable commitment scheme w.r.t. a black-box reduction to any ``standard" intractability reduction. Thus, this resolves the round complexity of non-malleable commitment at least w.r.t. black-box security reductions. Our construction is secure as per the standard notion of non-malleability w.r.t. commitment. Our protocol is truly efficient. In our basic protocol, the entire computation of the committer is dominated by just three invocations of a non-interactive statically binding commitment scheme, while, the receiver computation (in the commitment stage) is limited to just sampling a random string. Unlike many previous works, we directly construct a protocol for large tags and hence avoid any non-malleability amplification steps. Our protocol is based on a black-box use of any non-interactive statistically binding commitment scheme. Such schemes, in turn, can be based on any one-to-one one-way function (or any one-way function at the cost of an extra initialization round). Previously, the best known black-box construction of non-malleable commitments required a larger (constant) number of rounds. Our construction is public-coin and makes use of only black-box simulation. Prior to our work, no public-coin constant round non-malleable commitment schemes were known based on black-box simulation. itemize Our techniques depart significantly from the techniques used previously to construct non-malleable commitment schemes. As a main technical tool, we rely on non-malleable codes in the split state model. Our proofs of security are purely combinatorial in nature. In addition, we also present a simple construction of constant round non-malleable commitments from any one-way function. While this result is not new, the main feature is its simplicity compared to any previous construction of non-malleable commitments (in any number of rounds). We believe the construction is simple enough to be covered in a graduate level course on cryptography. The construction uses non-malleable codes in the split state model in a black-box way.

The notion of non-malleability in cryptography refers to the setting where the adversary is a man-in-the-middle (MIM) who takes part in two or more protocol executions and tries to use information obtained in one, to violate the security of another. Despite two decades of research, non-malleable commitments (NMCs) have remained too inefficient to be implemented in practice, without some sort of trusted setup. In this work, we give a fast implementation of NMC in the plain model, based on the DDH assumption being hard over elliptic curve groups. Our main theoretical result is a new NMC scheme which can be thought of as a "high dimensional" generalization of the one in the recent work of [GRRV14]. Central to our efficiency improvements is a method of constraining challenges sent by the receiver. This new approach enables us to obtain dramatically improved parameters over those suggested in [GRRV14]. In particular, our work opens the door to implementations based on Elliptic Curves.

In their seminal work on non-malleable cryptography, Dolev, Dwork and Naor, showed how to construct a non-malleable commitment with logarithmically-many "rounds"/"slots", the idea being that any adversary may successfully maul in some slots but would fail in at least one. Since then new ideas have been introduced, ultimately resulting in constant-round protocols based on any one-way function. Yet, in spite of this remarkable progress, each of the known constructions of non-malleable commitments leaves something to be desired. In this paper we propose a new technique that allows us to construct a non-malleable protocol with only a single "slot", and to improve in at least one aspect over each of the previously proposed protocols. Two direct byproducts of our new ideas are a four round non-malleable commitment and a four round non-malleable zero-knowledge argument, the latter matching the round complexity of the best known zero-knowledge argument (without the non-malleability requirement). The protocols are based on the existence of one-way functions and admit very efficient instantiations via standard homomorphic commitments and sigma protocols. Our analysis relies on algebraic reasoning, and makes use of error correcting codes in order to ensure that committers' tags differ in many coordinates. One way of viewing our construction is as a method for combining many atomic sub-protocols in a way that simultaneously amplifies soundness and non-malleability, thus requiring much weaker guarantees to begin with, and resulting in a protocol which is much trimmer in complexity compared to the existing ones.