*05:22* [Pub][ePrint]
From Weak to Strong Zero-Knowledge and Applications, by Kai-Min Chung and Edward Lui and Rafael Pass
The notion of \\emph{zero-knowledge} \\cite{GMR85} is formalized by requiring that for every malicious efficient verifier $V^*$, there exists an efficient simulator $S$ that can reconstruct the view of $V^*$ in a true interaction with the prover, in a way that is indistinguishable to \\emph{every} polynomial-time distinguisher. \\emph{Weak zero-knowledge} weakens this notions by switching the order of the quantifiers and only requires that for every distinguisher $D$, there exists a (potentially different) simulator $S_D$.In this paper we consider various notions of zero-knowledge, and investigate whether their weak variants are equivalent to their strong variants. Although we show (under complexity assumption) that for the standard notion of zero-knowledge, its weak and strong counterparts are not equivalent, for meaningful variants of the standard notion, the weak and strong counterparts are indeed equivalent. Towards showing these equivalences, we introduce new non-black-box simulation techniques permitting us, for instance, to demonstrate that the classical 2-round graph non-isomorphism protocol of Goldreich-Micali-Wigderson \\cite{GMW91} satisfies a ``distributional\'\' variant of zero-knowledge.

Our equivalence theorem has other applications beyond the notion of zero-knowledge. For instance, it directly implies the \\emph{dense model theorem} of Reingold et al (STOC \'08), and the leakage lemma of Gentry-Wichs (STOC \'11), and provides a modular and arguably simpler proof of these results (while at the same time recasting these result in the language of zero-knowledge).

*05:22* [Pub][ePrint]
Secure information transmission based on physical principles, by Dima Grigoriev and Vladimir Shpilrain
We employ physical properties of the real world to design a protocol for secure information transmission where one of the parties is ableto transmit secret information to another party over an insecure channel, without any prior secret arrangements between the parties.

The distinctive feature of this protocol, compared to all known

public-key cryptographic protocols, is that neither party uses a

one-way function. In particular, our protocol is secure against (passive) computationally unbounded adversary.

*05:22* [Pub][ePrint]
An efficient FHE based on the hardness of solving systems of non-linear multivariate equations, by GĂ©rald Gavin
We propose a general framework to develop fully homomorphic encryption schemes (FHE) without using the Gentry\'s technique. The security relies on the difficulty of solving systems of non-linear equations (which is a $\\mathcal{NP}$-complete problem). While the security of our scheme has not been reduced to a provably hard instance of this problem,security is globally investigated.

*05:22* [Pub][ePrint]
Encrypted Secret Sharing and Analysis by Plaintext Randomization, by Stephen R. Tate and Roopa Vishwanathan and Scott Weeks
In this paper we consider the problem of secret sharing where sharesare encrypted using a public-key encryption (PKE) scheme and

ciphertexts are publicly available. While intuition tells us that the

secret should be protected if the PKE is secure against

chosen-ciphertext attacks (i.e., CCA-secure), formally proving this

reveals some subtle and non-trivial challenges. We isolate the

problems that this raises, and devise a new analysis technique called

``plaintext randomization\'\' that can successfully overcome these

challenges, resulting in the desired proof. The encryption of

different shares can use one key or multiple keys, with natural

applications in both scenarios.

*05:22* [Pub][ePrint]
Attribute-Based Encryption with Fast Decryption, by Susan Hohenberger and Brent Waters
Attribute-based encryption (ABE) is a vision of public key encryption that allows users to encrypt and decrypt messages based on user attributes. This functionality comes at a cost. In a typical implementation, the size of the ciphertext is proportional to the number of attributes associated with it and the decryption time is proportional to the number of attributes used during decryption. Specifically, many practical ABE implementations require one pairing operation per attribute used during decryption.This work focuses on designing ABE schemes with fast decryption algorithms. We restrict our attention to expressive systems without system-wide bounds or limitations, such as placing a limit on the number of attributes used in a ciphertext or a private key. In this setting, we present the first key-policy ABE system where ciphertexts can be decrypted with a constant number of pairings. We show that GPSW ciphertexts can be decrypted with only 2 pairings by increasing the private key size by a factor of X, where X is the set of distinct attributes that appear in the private key. We then present a generalized construction that allows each system user to independently tune various efficiency tradeoffs to their liking on a spectrum where the extremes are GPSW on one end and our very fast scheme on the other. This tuning requires no changes to the public parameters or the encryption algorithm. Strategies for choosing an individualized user optimization plan are discussed. Finally, we discuss how these ideas can be translated into the ciphertext-policy ABE setting at a higher cost.

*05:22* [Pub][ePrint]
Multi-Party Computation of Polynomials and Branching Programs without Simultaneous Interaction, by S. Dov Gordon and Tal Malkin and Mike Rosulek and Hoeteck Wee
Halevi, Lindell, and Pinkas (CRYPTO 2011) recently proposed a model for secure computation that captures communication patterns that arisein many practical settings, such as secure computation on the web. In their model, each party interacts only once, with a single centralized server. Parties do not interact with each other; in fact, the parties need not even be online simultaneously.

In this work we present a suite of new, simple and efficient protocols for secure computation in this \"one-pass\" model. We give protocols that obtain optimal privacy for the following general tasks:

-- Evaluating any multivariate polynomial $F(x_1, \\ldots ,x_n)$ (modulo a large RSA modulus N), where the parties each hold an input $x_i$.

-- Evaluating any read once branching program over the parties\' inputs.

As a special case, these function classes include all previous functions for which an optimally private, one-pass computation was known, as well as many new functions, including variance and other statistical functions, string matching, second-price auctions, classification algorithms and some classes of finite automata

and decision trees.

*05:22* [Pub][ePrint]
Chosen Ciphertext Secure (CCS): Stateful Symmetric Key CCA Encryption with Minimal Ciphertext Expansion, by Jonathan Trostle
In some wireless environments, minimizing the size of messages is paramount due to the resulting significant energy savings. Wepresent a new stateful symmetric encryption scheme: CCS or Chosen

Ciphertext Secure scheme. CCS has the property that modifications to

the ciphertext randomizes the resulting plaintext. Using this property,

we prove the scheme is CCA2 secure. Thus we obtain CCA2 encryption

schemes with minimal ciphertext expansion which are applicable to resource constrained wireless environments. For protocols that send short messages, our scheme is similar to Counter with CBC-MAC (CCM) for

computation but has much shorter messages (since we can use much

smaller or no MAC tags) for a similar level of security. A key idea is

that various protocol fields in the underlying plaintext act as an authentication tag given changes to the message ciphertext. To the best of our knowledge, CCS is the first scheme that achieves CCA2 security with only 2-3 bytes of ciphertext expansion.

*05:22* [Pub][ePrint]
Pseudorandom Generators from Regular One-way Functions: New Constructions with Improved Parameters, by Yu Yu
We revisit the problem of basing pseudorandom generators on regular one-way functions, and present the following constructions: (1) For any known-regular one-way function (on $n$-bit inputs) that is known to be $\\eps$-hard to invert, we give a neat (and tighter) proof for the folklore construction of pseudorandom generator of seed length $\\Theta(n)$ by making a single call to the underlying one-way function.

(2) For any unknown-regular one-way function with known $\\eps$-hardness, we give a new construction with seed length $\\Theta(n)$ and $O(n/\\log{(1/\\eps)})$ calls. Here the number of calls is also optimal by matching the lower bounds of Holenstein and Sinha [FOCS 2012].

Both constructions require the knowledge about $\\eps$, but the dependency can be removed while keeping nearly the same parameters. In the latter case, we get a construction of pseudo-random generator from any unknown-regular one-way function using seed length $\\tilde{O}(n)$ and $\\tilde{O}(n/\\log{n})$ calls, where $\\tilde{O}$ omits a factor that can be made arbitrarily close to constant (e.g. $\\log\\log\\log{n}$ or even less). This improves the \\emph{randomized iterate} approach by Haitner, Harnik and Reingold [CRYPTO 2006] which requires seed length $O(n{\\log}{n})$ and $O(n/\\log{n})$ calls.