We propose a definition of ballot secrecy in the computational model of cryptography. The definition builds upon and strengthens earlier definitions by Bernhard et al. (ASIACRYPT'12, ESORICS'11 & ESORICS'13). The new definition is intended to ensure that ballot secrecy is preserved in the presence of malicious bulletin boards, whereas earlier definitions only consider trusted bulletin boards. It follows that the new definition prevents more attacks in comparison with earlier definitions.

The well-known Signed ElGamal scheme consists of ElGamal encryption with a non-interactive Schnorr proof of knowledge. While this scheme should be intuitively secure against chosen-ciphertext attacks in the random oracle model, its security has not yet been proven nor disproven so far, without relying on further non-standard assumptions like the generic group model. Currently, the best known positive result is that Signed ElGamal is non-malleable under chosen-plaintext attacks. In this paper we provide evidence that Signed ElGamal may not be CCA secure in the random oracle model. That is, building on previous work of Shoup and Gennaro (Eurocrypt’98), Seurin and Treger (CT-RSA 2013), and Bernhard et al. (PKC 2015), we exclude a large class of potential reductions that could be used to establish CCA security of the scheme.

We formalise the notion of adaptive proofs of knowledge in the random oracle model, where the extractor has to recover witnesses for multiple, possibly adaptively chosen statements and proofs. We also discuss extensions to simulation soundness, as typically required for the ``encrypt-then-prove'' construction of strongly secure encryption from IND-CPA schemes. Utilizing our model we show three results: (1) Simulation-sound adaptive proofs exist. (2) The ``encrypt-then-prove'' construction with a simulation-sound adaptive proof yields CCA security. This appears to be a ``folklore'' result but which has never been proven in the random oracle model. As a corollary, we obtain a new class of CCA-secure encryption schemes. (3) We show that the Fiat-Shamir transformed Schnorr protocol is _not_ adaptively secure and discuss the implications of this limitation. Our result not only separates adaptive proofs from proofs of knowledge, but also gives a strong hint why Signed ElGamal as the most prominent encrypt-then-prove example has not been proven CCA-secure without making further assumptions.

Proofs of work (PoW) have been suggested by Dwork and Naor (Crypto'92) as protection to a shared resource. The basic idea is to ask the service requestor to dedicate some non-trivial amount of computational work to every request. The original applications included prevention of spam and protection against denial of service attacks. More recently, PoWs have been used to prevent double spending in the Bitcoin digital currency system. In this work, we put forward an alternative concept for PoWs -- so-called \emph{proofs of space} (PoS), where a service requestor must dedicate a significant amount of disk space as opposed to computation. We construct secure PoS schemes in the random oracle model (with one additional mild assumption required for the proof to go through), using graphs with high ``pebbling complexity'' and Merkle hash-trees. We discuss some applications, including follow-up work where a decentralized digital currency scheme called Spacecoin is constructed that uses PoS (instead of wasteful PoW like in Bitcoin) to prevent double spending. The main technical contribution of this work is the construction of (directed, loop-free) graphs on $N$ vertices with in-degree $O(\log\log N)$ such that even if one places $\Theta(N)$ pebbles on the nodes of the graph, there's a constant fraction of nodes that needs $\Theta(N)$ steps to be pebbled (where in every step one can put a pebble on a node if all its parents have a pebble).

Computationalnotionsofentropy(a.k.a.pseudoentropy)have found many applications, including leakage-resilient cryptography, deter- ministic encryption or memory delegation. The most important tools to argue about pseudoentropy are chain rules, which quantify by how much (in terms of quantity and quality) the pseudoentropy of a given random variable X decreases when conditioned on some other variable Z (think for example of X as a secret key and Z as information leaked by a side-channel). In this paper we give a very simple and modular proof of the chain rule for HILL pseudoentropy, improving best known parameters. Our version allows for increasing the acceptable length of leakage in ap- plications up to a constant factor compared to the best previous bounds. As a contribution of independent interest, we provide a comprehensive study of all known versions of the chain rule, comparing their worst-case strength and limitations.

We revisit the classical problem: given a memoryless source having a certain amount of Shannon Entropy, how many random bits can be extracted? This question appears in works studying random number generators built from physical entropy sources. Some authors use a heuristic estimate obtained from the Asymptotic Equipartition Property, which yields roughly $n$ extractable bits, where $n$ is the total Shannon entropy amount. However the best known precise form gives only $n-O(\sqrt{\log(1/\epsilon) n})$, where $\epsilon$ is the distance of the extracted bits from uniform. In this paper we show a matching $ n-\Omega(\sqrt{\log(1/\epsilon) n})$ upper bound. Therefore, the loss of $\Theta(\sqrt{\log(1/\epsilon) n})$ bits is necessary. As we show, this theoretical bound is of practical relevance. Namely, applying the imprecise AEP heuristic to a mobile phone accelerometer one might overestimate extractable entropy even by $100\%$, no matter what the extractor is. Thus, the ``AEP extracting heuristic'' should not be used without taking the precise error into account.

Universal Computational Extractors (UCEs), introduced by Bellare, Hoang and Keelveedhi (CRYPTO 2013), are a framework of assumptions on hash functions that allow to instantiate random oracles in a large variety of settings. Brzuska, Farshim and Mittelbach (CRYPTO 2014) showed that a large class of UCE assumptions with \emph{computationally} unpredictable sources cannot be achieved, if indistinguishability obfuscation exists. In the process of circumventing obfuscation-based attacks, new UCE notions emerged, most notably UCEs with respect to \emph{statistically} unpredictable sources that suffice for a large class of applications. However, the only standard model constructions of UCEs are for a small subclass considering only $q$-query sources which are \emph{strongly statistically} unpredictable (Brzuska, Mittelbach; Asiacrypt 2014). The contributions of this paper are threefold: 1) We show a surprising equivalence for the notions of strong unpredictability and (plain) unpredictability thereby lifting the construction from Brzuska and Mittelbach to achieve $q$-query UCEs for statistically unpredictable sources. This yields standard model instantiations for various ($q$-query) primitives including, deterministic public-key encryption, message-locked encryption, multi-bit point obfuscation, CCA-secure encryption, and more. For some of these, our construction yields the first standard model candidate. 2) We study the blow-up that occurs in indistinguishability obfuscation proof techniques due to puncturing and state the \emph{Superfluous Padding Assumption} for indistinguishability obfuscation which allows us to lift the $q$-query restriction of our construction. We validate the assumption by showing that it holds for virtual black-box obfuscation. 3) Brzuska and Mittelbach require a strong form of point obfuscation secure in the presence of auxiliary input for their construction of UCEs. We show that this assumption is indeed necessary for the construction of injective UCEs.

The multiple ideal query (MIQ) model [Goyal, Jain, and Ostrovsky, Crypto'10] offers a relaxed notion of security for concurrent secure computation, where the simulator is allowed to query the ideal functionality multiple times per session (as opposed to just once in the standard definition). The model provides a quantitative measure for the degradation in security under concurrent self-composition, where the degradation is measured by the number of ideal queries. However, to date, all known MIQ-secure protocols guarantee only an overall average bound on the number of queries per session throughout the execution, thus allowing the adversary to potentially fully compromise some sessions of its choice. Furthermore, [Goyal and Jain, Eurocrypt'13] rule out protocols where the simulator makes only an adversary-independent constant number of ideal queries per session. We show the first MIQ-secure protocol with worst-case per-session guarantee. Specifically, we show a protocol for any functionality that matches the [GJ13] bound: The simulator makes only a constant number of ideal queries in every session. The constant depends on the adversary but is independent of the security parameter. As an immediate corollary of our main result, we obtain the first password authenticated key exchange (PAKE) protocol for the fully concurrent, multiple password setting in the standard model with no set-up assumptions.

In [Eurocrypt 2004] Katz and Ostrovsky establish the exact round complexity of secure two-party computation with respect to black-box proofs of security. They prove that 5 rounds are necessary for secure two-party protocols (4-round are sufficient if only one party receives the output) and provide a protocol that matches such lower bound. The main challenge when designing such protocol is to parallelize the proofs of consistency provided by both parties – necessary when security against malicious adversaries is considered– in 4 rounds. Toward this goal they employ specific proofs in which the statement can be unspecified till the last round but that require non-black-box access to the underlying primitives. A rich line of work [IKLP06, Hai08, CDSMW09, IKOS07, PW09] has shown that the non- black-box use of the cryptographic primitive in secure two-party computation is not necessary by providing black-box constructions matching basically all the feasibility results that were previously demonstrated only via non-black-box protocols. All such constructions however are far from being round optimal. The reason is that they are based on cut-and-choose mechanisms where one party can safely take an action only after the other party has successfully completed the cut-and-choose phase, therefore requiring additional rounds. A natural question is whether round-optimal constructions do inherently require non-black- box access to the primitives, and whether the lower bound shown by Katz and Ostrovsky can only be matched by a non-black-box protocol. In this work we show that round-optimality is achievable even with only black-box access to the primitives. We provide the first 4-round black-box oblivious transfer based on any enhanced trapdoor permutation. Plugging a parallel version of our oblivious transfer into the black- box non-interactive secure computation protocol of [IKO+11] we obtain the first round-optimal black-box two-party protocol in the plain model for any functionality.

Increasing the computational complexity of evaluating a hash function, both for the honest users as well as for an adversary, is a useful technique employed for example in password-based cryptographic schemes to impede brute-force attacks, and also in so-called proofs of work (used in protocols like Bitcoin) to show that a certain amount of computation was performed by a legitimate user. A natural approach to adjust the complexity of a hash function is to iterate it $c$~times, for some parameter $c$, in the hope that any query to the scheme requires $c$ evaluations of the underlying hash function. However, results by Dodis et al. (Crypto 2012) imply that plain iteration falls short of achieving this goal, and designing schemes which provably have such a desirable property remained an open problem. This paper formalizes explicitly what it means for a given scheme to amplify the query complexity of a hash function. In the random oracle model, the goal of a secure query-complexity amplifier (QCA) scheme is captured as transforming, in the sense of indifferentiability, a random oracle allowing $R$ queries (for the adversary) into one provably allowing only $r < R$ queries. Turned around, this means that making $r$ queries to the scheme requires at least $R$ queries to the actual random oracle. Second, a new scheme, called collision-free iteration, is proposed and proven to achieve $c$-fold QCA for both the honest parties and the adversary, for any fixed parameter~$c$.

We provide the first standard model construction for a powerful class of Universal Computational Extractors (UCEs; Bellare et al. Crypto 2013) based on indistinguishability obfuscation. Our construction suffices to instantiate correlation-secure hash functions and universal one-way functions. For many cryptographic primitives and in particular for correlation-secure hash functions all known constructions are in the random-oracle model. Indeed, recent negative results by Wichs (ITCS 2013) rule out a large class of techniques to prove the security of correlation-secure hash functions in the standard model. Our construction is based on puncturable PRFs (Sahai und Waters; STOC 2014) and indistinguishability obfuscation. However, our proof also relies on point obfuscation under auxiliary inputs (AIPO). This is crucial in light of Wichs' impossibility result. Namely, Wichs proves that it is often hard to reduce two-stage games (such as UCEs) to a "one-stage assumption" such as DDH. In contrast, AIPOs and their underlying assumptions are inherently two-stage and, thus, allow us to circumvent Wichs' impossibility result. Our positive result is also noteworthy insofar as Brzuska, Farshim and Mittelbach (Crypto 2014) have shown recently, that iO and some variants of UCEs are mutually exclusive. Our results, hence, validate some of the new UCE notions that emerged as a response to the iO-attack.

In this paper we present a new NTRU-Like public key cryptosystem with security provably based on the worst case hardness of the approximate both Shortest Vector Problem (SVP) and Closest Vector Problem (CVP) in some structured lattices, called ideal lattices. We show how to modify the ETRU cryptosystem, an NTRU-Like public key cryptosystem based on the Eisenstein integers where is a primitive cube root of unity, to make it provably secure, under the assumed quantum hardness of standard worst-case lattice problems, restricted to a family of lattices related to some cyclotomic fields. The security then proves for our main system from the already proven hardness of the R-LWE and R-SIS problems.

Ring oscillator (RO) based physically unclonable function (PUF) on FPGAs is crucial and popular for its nice properties and easy implementation. The compensated measurement based on the ratio of two ring oscillators’ frequencies proves to be particularly effective to extract entropy of process variations. However from two ring oscillators only one bit entropy is extracted and RO PUFs will occupy numerous resource with the size of private information increasing. Motivated by this inefficient resource usage, we propose an elegant and efficient method to extract at least 31 bits entropy from two ring oscillators on FPGAs by utilizing the fine control of programmable delay lines (PDL). We call this construction Further ROPUF (FROPUF). In this paper, we present in detail how to take advantage of the underlying random process variation which derives from the lookup tables (LUT) of two ring oscillators, and show that the in-depth variation can be extracted by a similar second order difference calculation. In addition, we reveal the consistency of the evaluation results from Xilinx FPGAs (e.g. Virtex-5, Virtex-6, Kintex-7) and those by simulation of FROPUF. The responses of our new construction have a nominal bit-error-rate (BER) of 1.85% at 27 &#9702; C and FROPUF greatly promotes the number of entropy with equivalent reliability of the general ROPUF.

We reconsider the concept of two-prover (and more generally: multi-prover) commitments, as introduced in the late eighties in the seminal work by Ben-Or et al. As was recently shown by Crëpeau et al., the security of known two-prover commitment schemes not only relies on the explicit assumption that the two provers cannot communicate, but also depends on what their information processing capabilities are. For instance, there exist schemes that are secure against classical provers but insecure if the provers have quantum information processing capabilities, and there are schemes that resist such quantum attacks but become insecure when considering general so-called non-signaling provers, which are restricted solely by the requirement that no communication takes place. This poses the natural question whether there exists a two-prover commitment scheme that is secure under the sole assumption that no communication takes place, and that does not rely on any further restriction of the information processing capabilities of the dishonest provers; no such scheme is known. In this work, we give strong evidence for a negative answer: we show that any single-round two-prover commitment scheme can be broken by a non-signaling attack. Our negative result is as bad as it can get: for any candidate scheme that is (almost) perfectly hiding, there exists a strategy that allows the dishonest provers to open a commitment to an arbitrary bit (almost) as successfully as the honest provers can open an honestly prepared commitment, i.e., with probability (almost) $1$ in case of a perfectly sound scheme. In the case of multi-round schemes, our impossibility result is restricted to perfectly hiding schemes. On the positive side, we show that the impossibility result can be circumvented by considering {\em three} provers instead: there exists a three-prover commitment scheme that is secure against arbitrary non-signaling attacks.

Plaintext is mixed with AI-generated dis-information which binds the cryptanalyst to an irreducible set of mutually exclusive plausible plaintext candidates. As impractical as Vernam "One Time Pad" cipher has been, it's security strategy: equivocation is fundamentally superior to the prevailing strategy: intractability. Intractability erodes, equivocation endures. Alas, Vernam was an overkill. Equivocation works even if only a few plaintext candidates are left as an irreducible set, which is what Equivoe-T offers. The AI engine builds decoys off the plaintext such that each decoy has a counter-meaning, or at least an off-meaning per the guarded plaintext, while claiming at least threshold plausibility to “pump” entropy into the irreducible field of plaintext candidates. Equivoe-T uses a complete transposition algorithm that guarantees the existence of a key that matches any two arbitrarily selected permutations of the n transposed elements. Therefore every decoy qualifies as a plaintext. The transposed elements may be words, letters, a mix, or otherwise. n can be selected to add intractability to the built-in equivocation since the key space grows fast (|Ktransposition| = n!).

We present a new fully homomorphic encryption (FHE) scheme that is efficient for practical applications. The main feature of our scheme is that noise reduction considered essential in current FHE schemes, such as boot strapping and modulus switching, is not needed in our scheme, because it allows arbitrarily large noises in its ciphertexts. A ciphertext in our scheme is a vector with its dimension specified as a security parameter of the encryption key. The dimension of ciphertexts does not change with homomorphic operations and all ciphertext elements are in a finite domain, so our scheme is compact. In addition, our scheme can directly encrypt big integers, rather than only bit messages. We proved the hardness of recovering encryption keys from any number of ciphertexts with chosen plaintexts and then the semantic security of our scheme. The hardness of recovering keys from ciphertexts is based on the approximate greatest common divisors problem. We implemented a prototype of our scheme and evaluated its concrete performance extensively from the aspects of encryption, decryption, homomorphic operations, and bitwise operators over ciphertexts. The efficiency of our scheme is confirmed by the evaluation result.

The multiple ideal query (MIQ) model was introduced by Goyal, Jain and Ostrovsky [Crypto'10] as a relaxed notion of security which allows one to construct concurrently secure protocols in the plain model. The main question relevant to the MIQ model is how many queries must we allow to the ideal world adversary? The importance of the above question stems from the fact that if the answer is positive, then it would enable meaningful security guarantees in many application scenarios, as well as, lead to resolution of long standing open questions such as fully concurrent password based key exchange in the plain model. In this work, we continue the study of the MIQ model and prove severe lower bounds on the number of ideal queries per session. Following are our main results: 1) There exists a two-party functionality that cannot be securely realized in the MIQ model with only a constant number of ideal queries per session. 2) There exists a two-party functionality that cannot be securely realized in the MIQ model by any constant round protocol, with any polynomial number of ideal queries per session. Both of these results are unconditional and even rule out protocols proven secure using a non-black-box simulator. We in fact prove a more general theorem which allows for trade-off between round complexity and the number of ideal queries per session. We obtain our negative results in the following two steps: 1) We first prove our results with respect to black-box simulation, i.e., we only rule out simulators that make black-box use of the adversary. 2) Next, we give a technique to compile our negative results w.r.t. black-box simulation into full impossibility results (ruling out non-black-box simulation as well) in the MIQ model. Interestingly, our compiler uses ideas from the work on obfuscation using tamper-proof hardware, even though our setting does not involve any hardware tokens.

An order-revealing encryption scheme gives a public procedure by which two ciphertexts can be compared to reveal the ordering of their underlying plaintexts. We show how to use order-revealing encryption to separate computationally efficient PAC learning from efficient $(\epsilon, \delta)$-differentially private PAC learning. That is, we construct a concept class that is efficiently PAC learnable, but for which every efficient learner fails to be differentially private. This answers a question of Kasiviswanathan et al. (FOCS '08, SIAM J. Comput. '11). To prove our result, we give a generic transformation from an order-revealing encryption scheme into one with strongly correct comparison, which enables the consistent comparison of ciphertexts that are not obtained as the valid encryption of any message. We believe this construction may be of independent interest.

We provide a new framework of cryptographic agents that unifies various modern ``cryptographic objects'' --- identity-based encryption, fully-homomorphic encryption, functional encryption, and various forms of obfuscation -- similar to how the Universal Composition framework unifies various multi-party computation tasks like commitment, coin-tossing and zero-knowledge proofs. These cryptographic objects can all be cleanly modeled as ``schemata'' in our framework. Highlights of our framework include the following: - We use a new `indistinguishability preserving' (INDPRE) definition of security that interpolates indistinguishability and simulation style definitions, which (often) sidesteps the known impossibilities for the latter. INDPRE-security is parameterized by the choice of the ``test'' family, such that by choosing different test families, one can obtain different levels of security for the same primitive (including various standard definitions in the literature). - We present a notion of `reduction' from one schema to another and a powerful `composition theorem' with respect to INDPRE security. We show that obfuscation is a ``complete'' schema under this notion, under standard cryptographic assumptions. We also provide a stricter notion of reduction that composes even when security is only with respect to certain restricted test families of importance. - Last but not the least, our framework can be used to model abstractions like the generic group model and the random oracle model, letting one translate a general class of constructions in these heuristic models to constructions based on `standard model assumptions'. We also illustrate how our framework can be applied to specific primitives like obfuscation and functional encryption. We relate our definitions to existing definitions and also give new constructions and reductions between different primitives.

Information theoretically secure multi-party computation (MPC) is a central primitive of modern cryptography. However, relatively little is known about the communication complexity of this primitive. In this work, we develop powerful information theoretic tools to prove lower bounds on the communication complexity of MPC. We restrict ourselves to a concrete setting involving 3-parties, in order to bring out the power of these tools without introducing too many complications. Our techniques include the use of a data processing inequality for {\em residual information} --- i.e., the gap between mutual information and Gács-Körner common information, a new {\em information inequality} for 3-party protocols, and the idea of {\em distribution switching} by which lower bounds computed under certain worst-case scenarios can be shown to apply for the general case. Using these techniques we obtain tight bounds on communication complexity by MPC protocols for various interesting functions. In particular, we show concrete functions that have ``communication-ideal'' protocols, which achieve the minimum communication simultaneously on all links in the network. Also, we obtain the first {\em explicit} example of a function that incurs a higher communication cost than the input length in the secure computation model of Feige, Kilian and Naor \cite{FeigeKiNa94}, who had shown that such functions exist. We also show that our communication bounds imply tight lower bounds on the amount of randomness required by MPC protocols for many interesting functions.

We consider the task of deriving a key with high HILL entropy (i.e., being computationally indistinguishable from a key with high min-entropy) from an unpredictable source. Previous to this work, the only known way to transform unpredictability into a key that was $\eps$ indistinguishable from having min-entropy was via pseudorandomness, for example by Goldreich-Levin (GL) hardcore bits. This approach has the inherent limitation that from a source with $k$ bits of unpredictability entropy one can derive a key of length (and thus HILL entropy) at most $k-2\log(1/\epsilon)$ bits. In many settings, e.g. when dealing with biometric data, such a $2\log(1/\epsilon)$ bit entropy loss in not an option. Our main technical contribution is a theorem that states that in the high entropy regime, unpredictability implies HILL entropy. Concretely, any variable $K$ with $|K|-d$ bits of unpredictability entropy has the same amount of so called metric entropy (against real-valued, deterministic distinguishers), which is known to imply the same amount of HILL entropy. The loss in circuit size in this argument is exponential in the entropy gap $d$, and thus this result only applies for small $d$ (i.e., where the size of distinguishers considered is exponential in $d$). To overcome the above restriction, we investigate if it's possible to first ``condense'' unpredictability entropy and make the entropy gap small. We show that any source with $k$ bits of unpredictability can be condensed into a source of length $k$ with $k-3$ bits of unpredictability entropy. Our condenser simply ``abuses" the GL construction and derives a $k$ bit key from a source with $k$ bits of unpredicatibily. The original GL theorem implies nothing when extracting that many bits, but we show that in this regime, GL still behaves like a ``condenser" for unpredictability. This result comes with two caveats (1) the loss in circuit size is exponential in $k$ and (2) we require that the source we start with has \emph{no} HILL entropy (equivalently, one can efficiently check if a guess is correct). We leave it as an intriguing open problem to overcome these restrictions or to prove they're inherent.

A celebrated result by Barak et al (JACM’12) shows the impossibility of general-purpose virtual black-box (VBB) obfuscation in the plain model. A recent work by Canetti, Kalai, and Paneth (TCC’15) extends this result also to the random oracle model (assuming trapdoor per- mutations). In contrast, Brakerski-Rothblum (TCC’15) and Barak et al (EuroCrypt’14) show that in idealized graded encoding models, general-purpose VBB obfuscation indeed is possible; these construction require graded encoding schemes that enable evaluating high-degree (polynomial in the size of the circuit to be obfuscated) polynomials on encodings. We show a complementary impossibility of general-purpose VBB obfuscation in idealized graded encoding models that enable only evaluation of constant-degree polynomials (assuming trapdoor permutations).

In this thesis we present our contribution in the field of post-quantum cryptography. We introduce a new notion of {\em weakly Random-Self-Reducible} public-key cryptosystem and show how it can be used to implement secure Oblivious Transfer. We also show that two recent (Post-quantum) cryptosystems can be considered as {\em weakly Random-Self-Reducible}. We introduce a new problem called Isometric Lattice Problem and reduce graph isomorphism and linear code equivalence to this problem. We also show that this problem has a perfect zero-knowledge interactive proof with respect to a malicious verifier; this is the only hard problem in lattices that is known to have this property.

The traditional notion of {\em program obfuscation} requires that an obfuscation $\tilde{f}$ of a program $f$ computes the exact same function as $f$, but beyond that, the code of $\tilde{f}$ should not leak any information about $f$. This strong notion of {\em virtual black-box} security was shown by Barak et al. (CRYPTO 2001) to be impossible to achieve, for certain {\em unobfuscatable function families}. The same work raised the question of {\em approximate obfuscation}, where the obfuscated $\tilde{f}$ is only required to approximate $\tilde{f}$; that is, $\tilde{f}$ only agrees with $f$ on some input distribution. We show that, assuming {\em trapdoor permutations}, there exist families of {\em robust unobfuscatable functions} for which even approximate obfuscation is impossible. That is, obfuscation is impossible even if the obfuscated $\tilde{f}$ only agrees with $f$ with probability slightly more than $\frac{1}{2}$, on a uniformly sampled input (below $\frac{1}{2}$-agreement, the function obfuscated by $\tilde{f}$ is not uniquely defined). Additionally, we show that, assuming only one-way functions, we can rule out approximate obfuscation where $\tilde{f}$ is not allowed to err, but may refuse to compute $f$ with probability close to $1$. We then demonstrate the power of robust unobfuscatable functions by exhibiting new implications to resettable protocols that so far have been out of our reach. Concretely, we obtain a new non-black-box simulation technique that reduces the assumptions required for resettably-sound zero-knowledge protocols to {\em one-way functions}, as well as reduce round-complexity. We also present a new simplified construction of simultaneously resettable zero-knowledge protocols that does not rely on collision-resistent hashing. Finally, we construct a three-message simultaneously resettable $\WI$ {\em argument of knowledge} (with a non-black-box knowledge extractor). Our constructions are based on a special kind of ``resettable slots" that are useful for a non-black-box simulator, but not for a resetting prover.

A {\em randomized encoding} allows to represent a ``complex'' function $f(x)$ by a ``simpler'' randomized function $\hat{f}(x;r)$ whose output distribution encodes $f(x)$, while revealing nothing else regarding $x$. Existing randomized encodings, geared mostly to allow encoding with low parallel complexity, have proven instrumental in various strong applications such as multiparty computation and parallel cryptography. This work focuses on another natural complexity measure: {\em the time required to encode}. We construct {\em succinct randomized encodings} where a computation given by a (Turing or random-access) machine $M$, and input $x$, requiring time $t$ and space $s$, can be encoded roughly in time $\poly(|x|,\log t,s)$, thus inducing significant savings in time when $s \ll t$. The scheme guarantees computational input-privacy and is based on indistinguishability obfuscation for a relatively simple circuit class, which can in turn be based on a polynomial version of the subgroup elimination assumption on multilinear graded encodings. We then invoke succinct randomized encodings to obtain several strong applications, including: \begin{itemize} \item Indistinguishability obfuscation for uniform (Turing or random-access) machines, where the obfuscated machine $\iO(M)$ computes the same function as $M$ for inputs $x$ of apriori-fixed maximal size $n$, and is computed in time $\poly(n,\log t,s)$. \item Functional encryption for uniform machines, where a functional decryption key corresponding to $M$ allows decrypting $M(x)$ from encryptions of $x$. As in the previous case, inputs $x$ are of apriori-fixed maximal size $n$, and key derivation time is roughly $\poly(n,\log t,s)$. \item Publicly-verifiable 2-message delegation where verification time is roughly $\poly(n,\log t,s)$. We also show how to transform any 2-message delegation scheme to an essentially non-interactive system where the verifier message is reusable. \end{itemize} For the first application, we also require subexponentially-secure indistinguishability obfuscation for circuits, and for the second polynomial indistinguishability obfuscation, which can be replaced by more concrete polynomial hardness assumptions on multilinear graded-encodings. Previously, both applications were only known based on various non-standard knowledge assumptions.

In this work, we define a new notion of weakly Random-Self-Reducibile cryptosystems and show how it can be used to implement secure Oblivious Transfer. We also show that two recent (Post-quantum) cryptosystems (based on Learning with errors and Approximate Integer GCD) can be considered as weakly Random-Self-Reducible.

We study the possibility of computing cryptographic primitives in a fully-black-box arithmetic model over a finite field $\F$. In this model, the input to a cryptographic primitive (e.g., encryption scheme) is given as a sequence of field elements, the honest parties are implemented by arithmetic circuits which make only a black-box use of the underlying field, and the adversary has a full (non-black-box) access to the field. This model captures many standard information-theoretic constructions. We prove several positive and negative results in this model for various cryptographic tasks. On the positive side, we show that, under reasonable assumptions, computational primitives like commitment schemes, public-key encryption, oblivious transfer, and general secure two-party computation can be implemented in this model. On the negative side, we prove that garbled circuits, multiplicative-homomorphic encryption, and secure computation with low online complexity cannot be achieved in this model. Our results reveal a qualitative difference between the standard Boolean model and the arithmetic model, and explain, in retrospect, some of the limitations of previous constructions.

The square map is one of the functions that is used in cryptography. For instance, the square map is used in Rabin encryption scheme, block cipher RC6 and stream cipher Rabbit, in different forms. In this paper we study a special case of the square map, namely the square function modulo a power of two. We obtain probability distribution of the output of this map as a vectorial Boolean function. We find probability distribution of the component Boolean functions of this map. We present the joint probability distribution of the component Boolean functions of this function. We introduce a new function which is similar to the function that is used in Rabbit cipher and we compute the probability distribution of the component Boolean functions of this new map.

A Physically Unclonable Function (PUF) can be seen as a source of randomness that can be challenged with a stimulus and responds in a way that is to some extent unpredictable. PUFs can be used to provide efficient solutions for common cryptographic primitives such as identification/authentication schemes, key storage, and hardware-entangled cryptography. Moreover, Brzuska et al.~have recently shown, that PUFs can be used to construct UC secure protocols (CRYPTO 2011). Most PUF instantiations, however, only provide a static challenge/response space which limits their usefulness for practical instantiations. To overcome this limitation, Katzenbeisser et al. (CHES 2011) introduced Logically Reconfigurable PUFs (LR-PUFs), with the idea to introduce an ``update'' mechanism that changes the challenge/response behaviour without physically replacing or modifying the hardware. In this work, we revisit LR-PUFs. We propose several new ways to characterize the unpredictability of LR-PUFs covering a broader class of realistic attacks and examine their relationship to each other. In addition, we reconcile existing constructions with these new characterizations and show that they can withstand stronger adversaries than originally shown. Since previous constructions are insecure with respect to our strongest unpredictability notion, we propose a secure construction which relies on the same assumptions and is almost as efficient as previous solutions.

Cryptographic protocols are commonly designed and their security proven under the assumption that the protocol parties have access to perfect (uniform) randomness. Physical randomness sources deployed in practical implementations of these protocols often fall short in meeting this assumption, but instead provide only a steady stream of bits with certain high entropy. Trying to ground cryptographic protocols on such imperfect, weaker sources of randomness has thus far mostly given rise to a multitude of impossibility results, including the impossibility to construct provably secure encryption, commitments, secret sharing, and zero-knowledge proofs based solely on a weak source. More generally, indistinguishability-based properties break down for such weak sources. In this paper, we show that the loss of security induced by using a weak source can be meaningfully quantified if the source is bounded, e.g., for the well-studied Santha-Vazirna (SV) sources. The quantification relies on a novel relaxation of indistinguishability by a quantitative parameter. We call the resulting notion differential indistinguishability in order to reflect its structural similarity to differential privacy. More concretely, we prove that indistinguishability with uniform randomness implies differential indistinguishability with weak randomness. We show that if the amount of weak randomness is limited (e.g., by using it only to seed a PRG), all cryptographic primitives and protocols still achieve differential indistinguishability.

Consider a collection $f$ of polynomials $f_i(x)$, $i=1, \ldots,s$, with integer coefficients such that polynomials $f_i(x)-f_i(0)$, $i=1, \ldots,s$, are linearly independent. Denote by $D_m$ the discrepancy for the set of points $\left(\frac{f_1(x) \bmod m}{m},\ldots,\frac{f_s(x) \bmod m}{p^n}\right)$ for all $x \in \{0,1,\ldots,m\}$, where $m=p^n$, $n \in N$, and $p$ is a prime number. We prove that $D_m\to 0$ as $n\to\infty$, and $D_m<c_1 (\log \log m)^{-c_2}$, where $c_1$ and $c_2$ are positive constants that depend only on the collection of $f_i$. As a corollary, we obtain an analogous result for iterations of any polynomial (with integer coefficients) whose degree exceeds~1. Certain results on the uniform distribution were known earlier only for some classes of polynomials with $s \leqslant 3$

Secure and private computations over RAM are preferred over computations with circuits or Turing machines. Secure and private RAM executions become more and more important in the scope avoiding information leakage when executing programs over a single computer as well as over the clouds. In this paper, we propose a distributed scheme for evaluating RAM programs without revealing any information on the computation including the program the data and the result. We use the Shamir secret sharing to share all the program instructions and private string matching technique to ensure the execution of the right instruction sequence. We stress that our scheme obtains information theoretic security and does not rely on any computational hardness assumptions, therefore, gaining indefinite private and secure RAM execution of perfectly unrevealed programs.

A serious concern with quantum key distribution (QKD) schemes is that, when under attack, the quantum devices in a real-life implementation may behave differently than modeled in the security proof. This can lead to real-life attacks against provably secure QKD schemes. In this work, we show that the standard BB84 QKD scheme is one-sided device-independent. This means that security holds even if Bob's quantum device is arbitrarily malicious, as long as Alice's device behaves as it should. Thus, we can completely remove the trust into Bob's quantum device for free, without the need for changing the scheme, and without the need for hard-to-implement loophole-free violations of Bell inequality, as is required for fully (meaning two-sided) device-independent QKD. For our analysis, we introduce a new quantum game, called a monogamy-of-entanglement game, and we show a strong parallel repetition theorem for this game. This new notion is likely to be of independent interest and to find additional applications. Indeed, besides the application to QKD, we also show a direct application to position-based quantum cryptography: we give the first security proof for a one-round position-verification scheme that requires only single-qubit operations.

Password hashing is the common approach for maintaining users' password-related information that is later used for authentication. A hash for each password is calculated and maintained at the service provider end. When a user logins the service, the hash of the given password is computed and contrasted with the stored hash. If the two hashes match, the authentication is successful. However, in many cases the passwords are just hashed by a cryptographic hash function or even stored in clear. These poor password protection practises have lead to efficient attacks that expose the users' passwords. PBKDF2 is the only standardized construction for password hashing. Other widely used primitives are bcrypt and scrypt. The low variety of methods derive the international cryptographic community to conduct the Password Hashing Competition (PHC). The competition aims to identify new password hashing schemes suitable for widespread adoption. It started in 2013 with 22 active submissions. Nine finalists are announced during 2014. In 2015, a small portfolio of schemes will be proposed. This paper provides the first survey and benchmark analysis of the 22 proposals. All proposals are evaluated on the same platform over a common benchmark suite. We measure the execution time, code size and memory consumption of PBKDF2, bcrypt, scrypt, and the 22 PHC schemes. The first round results are summarized along with a benchmark analysis that is focused on the nine finalists and contributes to the final selection of the winners.

The authentication code (A-code) is the one of the most fundamental cryptographic protocols in information-theoretic cryptography, and it provides information-theoretic integrity or authenticity, i.e., preventing information from being altered or substituted by the adversary having unbounded computational powers. In addition, it has a wide range of applications such as multiparty computations and quantum key distribution protocols. The traditional A-code theory states that a good A-code is characterized as an A-code which satisfies equality of a lower bound on size of secret-keys, i.e., an A-code satisfying |K|=\epsilon^{-2}, where |K}| is cardinality of the set of secret-keys and \epsilon is the success probability of attacks of the adversary. However, good A-codes imply that secret-keys must be uniformly distributed. Therefore, if a non-uniformly random key is given, we cannot realize a good A-code by using it as a secret-key. Then, a natural question about this is: what is a good A-code having non-uniformly random keys? And, how can we design such a good A-code having non-uniformly random keys? To answer the questions, in this paper, we perform analysis of A-codes having non-uniformly random keys, and show the principle that guides the design for such good A-codes. Specifically, the contribution of this paper is as follows. We first derive a new lower bound on entropy of secret-keys, and it is described in terms of \R entropy. Next, we define that a good A-code having non-uniformly random keys is the one satisfying equality of the bound, and it is characterized by the min-entropy (a special case of \R entropy). Furthermore, we introduce the classification methodology for A-codes which are realizable from a biased key-source. This classification is performed by using a mathematical tool, i.e., a group action on the set of authentication matrices. By this analysis, we can understand what kind of A-codes is actually constructable. Finally, we design how to construct good A-codes having 1-bit messages from von Neumann sources. We also show that our construction methodology is superior to the one by applying von Neumann extractors and the traditional optimal A-code constructions. Although the case of 1-bit messages may be restricted, however, this case is simple and we believe that a general case will develop from this simple case.

We propose a new cryptographic primitive called \emph{witness pseudorandom functions} (witness PRFs). Witness PRFs are related to witness encryption, but appear strictly stronger: we show that witness PRFs can be used for applications such as multi-party key exchange without trsuted setup, polynomially-many hardcore bits for any one-way function, and several others that were previously only possible using obfuscation. Current candidate obfuscators are far from practical and typically rely on unnatural hardness assumptions about multilinear maps. We give a construction of witness PRFs from multilinear maps that is simpler and much more efficient than current obfuscation candidates, thus bringing several applications of obfuscation closer to practice. Our construction relies on new but very natural hardness assumptions about the underlying maps that appear to be resistant to a recent line of attacks.

In this paper, we investigate some statistical properties of multiplication mod $2^n$ for cryptographic use. For this purpose, we introduce a family of T-functions similar to modular multiplication, which we call M-functions as vectorial Boolean functions. At first, we determine the joint probability distribution of arbitrary number of the output of an M-function component bits. Then, we obtain the probability distribution of the component Boolean functions of combination of a linear transformation with an M-function. After that, using a new measure for computing the imbalance of maps, we show that the restriction of the output of an M-function to its upper bits is asymptotically balanced.

Gennaro et al.\ (Crypto 2010) introduced the notion of \emph{non-interactive verifiable computation}, which allows a computationally weak client to outsource the computation of a function $f$ on a series of inputs $x^{(1)}, \ldots$ to a more powerful but untrusted server. Following a pre-processing phase (that is carried out only once), the client sends some representation of its current input $x^{(i)}$ to the server; the server returns an answer that allows the client to recover the correct result $f(x^{(i)})$, accompanied by a proof of correctness that ensures the client does not accept an incorrect result. The crucial property is that the work done by the client in preparing its input and verifying the server's proof is less than the time required for the client to compute~$f$ on its own. We extend this notion to the \emph{multi-client} setting, where $n$ computationally weak clients wish to outsource to an untrusted server the computation of a function $f$ over a series of {\em joint} inputs $(x_1^{(1)}, \ldots, x_{\clients}^{(1)}), \ldots$ without interacting with each other. We present a construction for this setting by combining the scheme of Gennaro et al.\ with a primitive called proxy oblivious transfer.

We present a constant-round unconditional black-box compiler that transforms any ideal (i.e., statistically-hiding and statistically-binding) straight-line extractable commitment scheme, into an extractable and equivocal commitment scheme, therefore yielding to UC-security [9]. We exemplify the usefulness of our compiler by providing two (constant-round) instantiations of ideal straight-line extractable commitment based on (malicious) PUFs [36] and stateless tamper-proof hardware tokens [26], therefore achieving the first unconditionally UC-secure commitment with malicious PUFs and stateless tokens, respectively. Our constructions are secure for adversaries creating arbitrarily malicious stateful PUFs/tokens. Previous results with malicious PUFs used either computational assumptions to achieve UC- secure commitments or were unconditionally secure but only in the indistinguishability sense [36]. Similarly, with stateless tokens, UC-secure commitments are known only under computational assumptions [13, 24, 15], while the (not UC) unconditional commitment scheme of [23] is secure only in a weaker model in which the adversary is not allowed to create stateful tokens. Besides allowing us to prove feasibility of unconditional UC-security with (malicious) PUFs and stateless tokens, our compiler can be instantiated with any ideal straight-line extractable commitment scheme, thus allowing the use of various setup assumptions which may better fit the application or the technology available.

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 output bit is computed by applying some fixed $d$-ary predicate $P$ to a randomly chosen $d$-size subset of the input bits. In this work, we will study the cryptographic hardness of random local functions. In particular, we will survey known attacks and hardness results, discuss different flavors of hardness (one-wayness, pseudorandomness, collision resistance, public-key encryption), and mention applications to other problems in cryptography and computational complexity. We also present some open questions with the hope to develop a systematic study of the cryptographic hardness of local functions.

We ask whether it is possible to anonymously communicate a large amount of data using only public (non-anonymous) communication together with a small anonymous channel. We think this is a central question in the theory of anonymous communication and to the best of our knowledge this is the first formal study in this direction. To solve this problem, we introduce the concept of anonymous steganography: think of a leaker Lea who wants to leak a large document to Joe the journalist. Using anonymous steganography Lea can embed this document in innocent looking communication on some popular website (such as cat videos on YouTube or funny memes on 9GAG). Then Lea provides Joe with a short key k which, when applied to the entire website, recovers the document while hiding the identity of Lea among the large number of users of the website. Our contributions include: - Introducing and formally defining anonymous steganography, - A construction showing that anonymous steganography is possible (which uses recent results in circuits obfuscation), - A lower bound on the number of bits which are needed to bootstrap anonymous communication.

Yao's Garbled Circuit (GC) technique is a powerful cryptographic tool which allows to ``encrypt'' a circuit $C$ by another circuit $\hC$ in a way that hides all information except for the final output. Yao's original construction incurs a constant overhead in both computation and communication per gate of the circuit $C$ (proportional to the complexity of symmetric encryption). Kolesnikov and Schneider (ICALP 2008) introduced an optimized variant that garbles XOR gates ``for free'' in a way that involves no cryptographic operations and no communication. This variant has become very popular and has been employed in several practical implementations leading to notable performance improvements. The security of the free-XOR optimization was originally proven in the random oracle model. In the same paper, Kolesnikov and Schneider also addressed the question of replacing the random oracle with a standard cryptographic assumption and suggested to use a hash function which achieves some form of security under correlated inputs. This claim was revisited by Choi et al. (TCC 2012) who showed that a stronger form of security is required, and proved that the free-XOR optimization can be realized based on a new primitive called \emph{circular 2-correlation hash function}. Unfortunately, it is currently unknown how to implement this primitive based on standard assumptions, and so the feasibility of realizing the free-XOR optimization in the standard model remains an open question. We resolve this question by showing that the free-XOR approach can be realized in the standard model under the \emph{learning parity with noise} (LPN) assumption. Our result is obtained in two steps: (1) We show that the hash function can be replaced with a symmetric encryption which remains secure under a combined form of related-key and key-dependent attacks; and (2) We show that such a symmetric encryption can be constructed based on the LPN assumption.

Hardcore lemmas are results in complexity theory which state that average-case hardness must have a very hard ``kernel'', that is a subset of instances where the given problem is extremely hard. They find important applications in hardness amplification. In this paper we revisit the following two fundamental results: \begin{enumerate}[(a)] \item The hardcore lemma for unpredictability, due to Impagliazzo (FOCS '95). It states that if a boolean function $f$ is ``moderately'' hard to predict on average, then there must be a set of noticeable size on which $f$ is ``extremely'' hard to predict. \item The hardcore lemma for indistinguishability, proved by Maurer and Tessaro (TCC'10), states that for two random variables $X$ and $Y$ which are $\epsilon$-computationally close, there are events $A$ and $B$ of probability $1-\epsilon$ such that the distributions of $X|A$ and $Y|B$ are ``computationally'' identical. \end{enumerate} Using only the standard min-max theorem and some basic facts about convex approximations in $L_p$ spaces, we provide alternative modular proofs and some generalizations of these results in the nonuniform setting, achieving best possible bounds for (a) and slightly improving the known bounds for (b). As an interesting application, we show a strengthening of the transformation between two most popular pseudoentropy variants: HILL and Metric Entropy, and apply it to show how to extract pseudorandomness from a sequence of metric-entropy sources of poor quality. In this case we significantly improve security parameters, comparing to the best known techniques.

We present a new information-theoretic result which we call the Chaining Lemma. It considers a so-called "chain" of random variables, defined by a source distribution X[0] with high min-entropy and a number (say, t in total) of arbitrary functions (T1,....Tt) which are applied in succession to that source to generate the chain X[0]-->X[1]-->.....-->X[t] such that X[i] = Ti(X[i-1]). Intuitively, the Chaining Lemma guarantees that, if the chain is not too long, then either (i) the entire chain is "highly random", in that every variable has high min-entropy; or (ii) it is possible to find a point j (1 <= j <= t) in the chain such that, conditioned on the end of the chain the preceding part remains highly random. We believe this is an interesting information-theoretic result which is intuitive but nevertheless requires rigorous case-analysis to prove. We believe that the above lemma will find applications in cryptography. We give an example of this, namely we show an application of the lemma to protect essentially any cryptographic scheme against memory-tampering attacks. We allow several tampering requests, the tampering functions can be arbitrary, however, they must be chosen from a bounded size set of functions that is fixed a priori.

Assuming the existence of indistinguishability obfuscation (iO), we show that a number of prominent transformations in the random-oracle model are uninstantiable in the standard model. We start by showing that the Encrypt-with-Hash transform of Bellare, Boldyreva and O'Neill (CRYPTO 2007) for converting randomized public-key encryption schemes to deterministic ones is not instantiable in the standard model. To this end, we build on the recent work of Brzuska, Farshim and Mittelbach (CRYPTO 2014) and rely on the existence of iO for circuits or iO for Turing machines to derive uninstantiability for hash functions of a priori bounded polynomial size and arbitrary polynomial size, respectively. The techniques that we use to establish this result are flexible and lend themselves to a number of other transformations such as the classical Fujisaki--Okamoto transform (CRYPTO 1998) and transformations akin to those by Bellare and Keelveedhi (CRYPTO 2011) and Douceur et al. (ICDCS 2002) for obtaining KDM-secure encryption and de-duplication schemes respectively. Our results call for a re-assessment of scheme design in the random-oracle model and highlight the need for new transforms that do not suffer from iO-based attacks.

\emph{Randomized encodings of functions} can be used to replace a ``complex'' function $f(x)$ by a ``simpler'' randomized mapping $\hat{f}(x;r)$ whose output distribution on an input $x$ encodes the value of $f(x)$ and hides any other information about $x$. One desirable feature of randomized encodings is low \emph{online complexity}. That is, the goal is to obtain a randomized encoding $\hat{f}$ of $f$ in which most of the output can be precomputed and published before seeing the input $x$. When the input $x$ is available, it remains to publish only a short string $\hat{x}$, where the online complexity of computing $\hat{x}$ is independent of (and is typically much smaller than) the complexity of computing $f$. Yao's garbled circuit construction gives rise to such randomized encodings in which the online part $\hat{x}$ consists of $n$ encryption keys of length $\kappa$ each, where $n=|x|$ and $\kappa$ is a security parameter. Thus, the {\em online rate} $|\hat{x}|/|x|$ of this encoding is proportional to the security parameter $\kappa$. In this paper, we show that the online rate can be dramatically improved. Specifically, we show how to encode any polynomial-time computable function $f:\bit^n\to\bit^{m(n)}$ with online rate of $1+o(1)$ and with nearly linear online computation. More concretely, the online part $\hat{x}$ consists of an $n$-bit string and a single encryption key. These constructions can be based on the decisional Diffie-Hellman assumption (DDH), the Learning with Errors assumption (LWE), or the RSA assumption. We also present a variant of this result which applies to {\em arithmetic formulas}, where the encoding only makes use of arithmetic operations, as well as several negative results which complement our positive results. Our positive results can lead to efficiency improvements in most contexts where randomized encodings of functions are used. We demonstrate this by presenting several concrete applications. These include protocols for secure multiparty computation and for non-interactive verifiable computation in the preprocessing model which achieve, for the first time, an optimal online communication complexity, as well as non-interactive zero-knowledge proofs which simultaneously minimize the online communication and the prover's online computation.

Pairing-based cryptography (PBC) has many elegant properties. It is claimed that PBC can offer a desired security level with smaller parameters as the general elliptic curve cryptography (ECC). In the note, we remark that this view is misleading. Suppose that an elliptic curve E is defined over the field F_q. Then ECC is working with elements which are defined over F_q. But PBC is working with the functions and elements defined over F_{q^k}, where k is the embedding degree. The security of PBC depends directly on the intractable level of either elliptic curve discrete log problem (ECDLP) in the group E(F_q) or discrete log problem (DLP) in the group F_{q^k}^*. That means PBC protocols have to work in a running environment with parameters of 1024 bits so as to offer 80 bits security level. The shortcoming makes PBC lose its competitive advantages significantly.

We present new constructions of two-message and one-message witness-indistinguishable proofs (ZAPs and NIWIs). This includes: \begin{itemize} \item ZAP (or, equivalently, non-interactive zero-knowledge in the common random string model) from indistinguishability obfuscation and one-way functions. \item NIWIs from indistinguishability obfuscation and one-way permutations. \end{itemize} The previous construction of ZAPs [Dwork and Naor, FOCS 00] was based on trapdoor permutations. The two previous NIWI constructions were based either on ZAPs and a derandomization-type complexity assumption [Barak, Ong, and Vadhan CRYPTO 03], or on a specific number theoretic assumption in bilinear groups [Groth, Sahai, and Ostrovsky, CRYPTO 06].

We show by counter-example that the soundness security requirement for witness encryption given by Garg, Gentry, Sahai and Waters (STOC 2013) does not suffice for the security of their own applications. We introduce adaptively-sound (AS) witness encryption to fill the gap. We then introduce asymmetric password-based encryption (A-PBE). This offers gains over classical, symmetric password-based encryption in the face of attacks that compromise servers to recover hashed passwords. We distinguish between invasive A-PBE schemes (they introduce new password-based key-derivation functions) and non-invasive ones (they can use existing, deployed password-based key-derivation functions). We give simple and efficient invasive A-PBE schemes and use AS-secure witness encryption to give non-invasive A-PBE schemes.

We study robust secret sharing schemes in which between one third and one half of the players are corrupted. In this scenario, robust secret sharing is possible only with a share size larger than the secrets, and allowing a positive probability of reconstructing the wrong secret. In the standard model, it is known that at least $m+k$ bits per share are needed to robustly share a secret of bit-length $m$ with an error probability of $2^{-k}$; however, to the best of our knowledge, the efficient scheme that gets closest to this lower bound has share size $m+\widetilde O (n+k)$, where $n$ is the number of players in the scheme. We show that it is possible to obtain schemes with close to minimal share size in a model of local adversaries, i.e. in which corrupt players cannot communicate between receiving their respective honest shares and submitting corrupted shares to the reconstruction procedure, but may coordinate before the execution of the protocol and can also gather information afterwards. In this limited adversarial model, we prove a lower bound of roughly $m+k$ bits on the minimal share size, which is (somewhat surprisingly) similar to the lower bound in the standard model, where much stronger adversaries are allowed. We then present an efficient secret sharing scheme that essentially meets our lower bound, therefore improving upon the best known constructions in the standard model by removing a linear dependence on the number of players. For our construction, we introduce a novel procedure that compiles an error correcting code into a new randomized one, with the following two properties: a single local portion of a codeword leaks no information on the encoded message itself, and any set of portions of a codeword reconstructs the message with error probability exponentially low in the set size.

We motivate, define and construct quantum proofs of knowledge, that is, proofs of knowledge secure against quantum adversaries. Our constructions are based on a new quantum rewinding technique that allows us to extract witnesses in many classical proofs of knowledge. We give criteria under which a classical proof of knowledge is a quantum proof of knowledge. Combining our results with Watrous' results on quantum zero-knowledge, we show that there are zero-knowledge quantum proofs of knowledge for all languages in NP (assuming quantum 1-1 one-way functions).

Composite-order bilinear groups provide many structural features that are useful for both constructing cryptographic primitives and enabling security reductions. Despite these convenient features, however, composite-order bilinear groups are less desirable than prime-order bilinear groups for reasons of both efficiency and security. A recent line of work has therefore focused on translating these structural features from the composite-order to the prime-order setting; much of this work focused on two such features, projecting and canceling, in isolation, but a result due to Seo and Cheon showed that both features can be obtained simultaneously in the prime-order setting. In this paper, we reinterpret the construction of Seo and Cheon in the context of dual pairing vector spaces (which provide canceling as well as useful parameter hiding features) to obtain a unified framework that simulates all of these composite-order features in the prime-order setting. We demonstrate the strength of this framework by providing two applications: one that adds dual pairing vector spaces to the existing projection in the Boneh-Goh-Nissim encryption scheme to obtain leakage resilience, and another that adds the concept of projecting to the existing dual pairing vector spaces in an IND-CPA secure IBE scheme to "boost" its security to IND-CCA1. Our leakage-resilient BGN application is of independent interest, and it is not clear how to achieve it from pure composite-order techniques without mixing in additional vector space tools. Both applications rely solely on the Symmetric External Diffie Hellman assumption (SXDH).

We study generic hardness of the multiple discrete logarithm problem, where the solver has to solve $n$ instances of the discrete logarithm problem simultaneously. There are known generic algorithms which perform $O(\sqrt{n p})$ group operations, where $p$ is the group order, but no generic lower bound was known other than the trivial bound. In this paper we prove the tight generic lower bound, showing that the previously known algorithms are asymptotically optimal. We establish the lower bound by studying hardness of a related computational problem which we call the search-by-hyperplane-queries problem, which may be of independent interest.

In the first part of this work, we introduce a new type of pseudo-random function for which ``aggregate queries'' over exponential-sized sets can be efficiently answered. We show how to use algebraic properties of underlying classical pseudo random functions, to construct such ``aggregate pseudo-random functions'' for a number of classes of aggregation queries under cryptographic hardness assumptions. For example, one aggregate query we achieve is the product of all function values accepted by a polynomial-sized read-once boolean formula. On the flip side, we show that certain aggregate queries are impossible to support. Aggregate pseudo-random functions fall within the framework of the work of Goldreich, Goldwasser, and Nussboim on the ``Implementation of Huge Random Objects,'' providing truthful implementations of pseudo-random functions for which aggregate queries can be answered. In the second part of this work, we show how various extensions of pseudo-random functions considered recently in the cryptographic literature, yield impossibility results for various extensions of machine learning models, continuing a line of investigation originated by Valiant and Kearns in the 1980s. The extended pseudo-random functions we address include constrained pseudo random functions, aggregatable pseudo random functions, and pseudo random functions secure under related-key attacks.

A non-malleable code protects messages against a class of tampering functions. Informally, a code is non-malleable if the effect of applying any tampering function on an encoded message is to either retain the message or to replace it with an unrelated message. Two main challenges in this area -- apart from establishing the feasibility against different families of tampering -- are to obtain explicit constructions and to obtain high-rates for such constructions. In this work, we present a compiler to transform low-rate (in fact, zero rate) non-malleable codes against certain class of tampering into an optimal-rate -- i.e., rate 1 -- non-malleable codes against the same class. If the original code is explicit, so is the new one. When applied to the family of bit-wise tampering functions, this subsumes (and greatly simplifies) a recent result of Cheraghchi and Guruswami (TCC 2014). Further, our compiler can be applied to non-malleable codes against the class of bit-wise tampering and bit-level permutations. Combined with the rate-0 construction in a companion work, this yields the first explicit rate-1 non-malleable code for this family of tampering functions. Our compiler uses a new technique for boot-strapping non-malleability by introducing errors, that may be of independent interest.

A simple and practical hashing scheme based on Cyclic Redundancy Check (CRC) is presented. Similarly to previously proposed cryptographically secure CRCs, the presented one detects both, random and malicious, errors without increasing bandwidth. However, we use a product of irreducible polynomials instead of a single irreducible polynomial for generating the CRC. This is an advantage since smaller irreducible polynomials are easier to compute. The price we pay is that the probability that two different messages map into the same CRC increases. We provide a detailed quantitative analysis of the achieved security as a function of message and CRC sizes. The presented method seems to be particularly attractive for the authentication of short messages.

We present a new and conceptually simpler proof of a tight parallel-repetition theorem for public-coin arguments (Pass-Venkitasubramaniam, STOC'07, Hastad et al, TCC'10, Chung-Liu, TCC'10). We follow the same proof framework as the previous non-tight parallel-repetition theorem of Hastad et al---which relied on *statistical distance* to measure the distance between experiments---and show that it can be made tight (and further simplied) if instead relying on *KL-divergence* as the distance between the experiments. We then show that our proof technique directly yields tight ``Chernoff-type'' parallel-repetition theorems (where one considers a ``threshold'' verifier that accepts iff the prover manages to convince a certain fraction of the parallel verifiers, as opposed to all of them) for any public-coin interactive argument; previously, tight results were only known for either constant-round protocols, or when the gap between the threshold and the original error-probability is a constant.

Given a linear code $C$, one can define the $d$-th power of $C$ as the span of all componentwise products of $d$ elements of $C$. A power of $C$ may quickly fill the whole space. Our purpose is to answer the following question: does the square of a code ``typically'' fill the whole space? We give a positive answer, for codes of dimension $k$ and length roughly $\frac{1}{2}k^2$ or smaller. Moreover, the convergence speed is exponential if the difference $k(k+1)/2-n$ is at least linear in $k$. The proof uses random coding and combinatorial arguments, together with algebraic tools involving the precise computation of the number of quadratic forms of a given rank, and the number of their zeros.

Differing inputs obfuscation (diO) is a strengthening of indistinguishability obfuscation (iO) that has recently found applications to improving the efficiency and generality of obfuscation, functional encryption, and related primitives. Roughly speaking, a diO scheme ensures that the obfuscations of two efficiently generated programs are indistinguishable not only if the two programs are equivalent, but also if it is hard to find an input on which their outputs differ. The above ``indistinguishability'' and ``hardness'' conditions should hold even in the presence of an auxiliary input that is generated together with the programs. The recent works of Boyle and Pass (ePrint 2013) and Garg et al. (Crypto 2014) cast serious doubt on the plausibility of general-purpose diO with respect to general auxiliary inputs. This leaves open the existence of a variant of diO that is plausible, simple, and useful for applications. We suggest such a diO variant that we call {\em public-coin} diO. A public-coin diO restricts the original definition of diO by requiring the auxiliary input to be a public random string which is given as input to all relevant algorithms. In contrast to standard diO, we argue that it remains very plausible that current candidate constructions of iO for circuits satisfy the public-coin diO requirement. We demonstrate the usefulness of the new notion by showing that several applications of diO can be obtained by relying on the public-coin variant instead. These include constructions of {\em succinct} obfuscation and functional encryption schemes for Turing Machines, where the size of the obfuscated code or keys is essentially independent of the running time and space.

Lattice rounding in Euclidean space can be viewed as finding the nearest point in the orbit of an action by a discrete group, relative to the norm inherited from the ambient space. Using this point of view, we initiate the study of non-abelian analogs of lattice rounding involving matrix groups. In one direction, we give an algorithm for solving a normed word problem when the inputs are random products over a basis set, and give theoretical justification for its success. In another direction, we prove a general inapproximability result which essentially rules out strong approximation algorithms (i.e., whose approximation factors depend only on dimension) analogous to LLL in the general case.

We revisit "the randomized iterate" technique that was originally used by Goldreich, Krawczyk, and Luby (SICOMP 1993) and refined by Haitner, Harnik and Reingold (CRYPTO 2006) in constructing pseudorandom generators (PRGs) from regular one-way functions (OWFs). We abstract out a technical lemma (which is folklore in leakage resilient cryptography), and use it to provide a simpler and more modular proof for the Haitner-Harnik-Reingold PRGs from regular OWFs. We introduce a more general class of OWFs called "weakly-regular one-way functions" from which we construct a PRG of seed length O(n*logn). More specifically, consider an arbitrary one-way function f with range divided into sets Y1, Y2, ..., Yn where each Y_i={ y:2^{i-1}<=|f^{-1}(y)|<2^{i} }. We say that f is weakly-regular if there exists a (not necessarily efficient computable) cut-off point max such that Y_max is of some noticeable portion (say n^{-c} for constant c), and Y_max+1, ..., Y_n only sum to a negligible fraction. We construct a PRG by making O(n^{2c+1}) calls to f and achieve seed length O(n*logn) using bounded space generators. This generalizes the approach of Haitner et al., where regular OWFs fall into a special case for c=0. We use a proof technique that is similar to and extended from the method by Haitner, Harnik and Reingold for hardness amplification of regular weakly-one-way functions. Our work further explores the feasibility and limits of the "randomized iterate" type of black-box constructions. In particular, the underlying f can have an arbitrary structure as long as the set of images with maximal preimage size has a noticeable fraction. In addition, our construction is much more seed-length efficient and security-preserving (albeit less general) than the HILL-style generators where the best known construction by Vadhan and Zheng (STOC 2012) requires seed length O(n^3).

We address one of the foundational problems in cryptography: the bias of coin-flipping protocols. Coin-flipping protocols allow mutually distrustful parties to generate a common unbiased random bit, guaranteeing that even if one of the parties is malicious, it cannot significantly bias the output of the honest party. A classical result by Cleve [STOC '86] showed that for any two-party $r$-round coin-flipping protocol there exists an efficient adversary that can bias the output of the honest party by $\Omega(1/r)$. However, the best previously known protocol only guarantees $O(1/\sqrt{r})$ bias, and the question of whether Cleve's bound is tight has remained open for more than twenty years. In this paper we establish the optimal trade-off between the round complexity and the bias of two-party coin-flipping protocols. Under standard assumptions (the existence of oblivious transfer), we show that Cleve's lower bound is tight: we construct an $r$-round protocol with bias $O(1/r)$.

Secure Multi-party Computation (MPC) is one of the foundational achievements of modern cryptography, allowing multiple, distrusting, parties to jointly compute a function of their inputs, while revealing nothing but the output of the function. Following the seminal works of Yao and Goldreich, Micali and Wigderson and Ben-Or, Goldwasser and Wigderson, the study of MPC has expanded to consider a wide variety of questions, including variants in the attack model, underlying assumptions, complexity and composability of the resulting protocols. One question that appears to have received very little attention, however, is that of MPC over an underlying communication network whose structure is, in itself, sensitive information. This question, in addition to being of pure theoretical interest, arises naturally in many contexts: designing privacy-preserving social-networks, private peer-to-peer computations, vehicle-to-vehicle networks and the ``internet of things'' are some of the examples. In this paper, we initiate the study of ``topology-hiding computation'' in the computational setting. We give formal definitions in both simulation-based and indistinguishability-based flavors. We show that, even for fail-stop adversaries, there are some strong impossibility results. Despite this, we show that protocols for topology-hiding computation can be constructed in the semi-honest and fail-stop models, if we somewhat restrict the set of nodes the adversary may corrupt.

Decomposing a divisor over a suitable factor basis in the Jacobian of a hyperelliptic curve is a crucial step in an index calculus algorithm for the discrete log problem in the Jacobian. For small genus curves, in the year 2000, Gaudry had proposed a suitable factor basis and a decomposition method. In this work, we provide a new method for decomposition over the same factor basis. The advantage of the new method is that it admits a sieving technique which removes smoothness checking of polynomials required in Gaudry's method. Also, the total number of additions in the Jacobian required by the new method is less than that required by Gaudry's method. The new method itself is quite simple and we present some example decompositions and timing results of our implementation of the method using Magma.

We will introduce different notions of independence, especially computational independence (or more precise independence by polynomial-size circuits (PSC)), which is the analog to computational indistinguishability. We will give some first implications and will show that an encryption scheme having PSC independent plaintexts and ciphertexts is equivalent to having indistinguishable encryptions.

One-way functions are both central to cryptographic theory and a clear example of its complexity as a theory. From the aim to understand theories, proofs, and communicability of proofs in the area better, we study some small theorems on one-way functions, namely: composition theorems of one-way functions of the form "if $f$ (or $h$) is well-behaved in some sense and $g$ is a one-way function, then $f \circ g$ (respectively, $g \circ h$) is a one-way function". We present two basic composition theorems, and generalisations of them which may well be folklore. Then we experiment with different proof presentations, including using the Coq theorem prover, using one of the theorems as a case study.

Garbling schemes (aka randomized encodings of functions) represent a function F by a "simpler" randomized function F^ such that F^(x) reveals F(x) and no additional information about x. Garbling schemes have found applications in many areas of cryptography. Motivated by the goal of improving the efficiency of garbling schemes, we make the following contributions: – We suggest a general new notion of partial garbling which unifies several previous notions from the literature, including standard garbling schemes, secret sharing schemes, and “conditional disclosure of secrets”. This notion considers garbling schemes in which part of the input is public, in the sense that it can be leaked by F^. – We present constructions of partial garbling schemes for (boolean and arithmetic) formulas and branching programs which take advantage of the public input to gain better efficiency. – We demonstrate the usefulness of the new notion by presenting applications to efficient attribute-based encryption, delegation, and secure computation. In each of these applications, we obtain either new schemes for larger classes of functions or efficiency improvements from quadratic to linear. In particular, we obtain the first ABE scheme in bilinear groups for arithmetic formulas, as well as more efficient delegation schemes for boolean and arithmetic branching programs.

In this paper, we investigate matrices acting on finite commutative groups and rings; in fact, we study modules on ring of matrices over Z_N and also modules over the ring (F_2^t,\oplus,\land); these new algebraic constructions are a generalization of some of the constructions which were previously presented by the authors of this paper. We present new linearized and nonlinear MDS diffusion layers, based on this mathematical investigation. Then, we study some types of nonlinear number generators over Z_(2^n ) and we present a lower bound on the period of these new nonlinear number generators. As a consequence, we present nonlinear recurrent sequences over Z_(2^n ) with periods which are multiples of the period of the corresponding sigma-LFSR’s.

Yao's garbled circuit construction is a fundamental construction in cryptography and recent efficiency optimizations have brought it much closer to practice. However these constructions work only for circuits and garbling a RAM program involves the inefficient process of first converting it into a circuit. Towards the goal of avoiding this inefficiency, Lu and Ostrovsky (Eurocrypt 2013) introduced the notion of ``garbled RAM'' as a method to garble RAM programs directly. It can be seen as a RAM analogue of Yao's garbled circuits such that, the size of the garbled program and the time it takes to create and evaluate it, is proportional only to the running time on the RAM program rather than its circuit size. Known realizations of this primitive, either need to rely on strong computational assumptions or do not achieve the aforementioned efficiency (Gentry, Halevi, Lu, Ostrovsky, Raykova and Wichs, EUROCRYPT 2014). In this paper we provide the first construction with strictly poly-logarithmic overhead in both space and time based only on the minimal and necessary assumption that one-way functions exist. Our scheme allows for garbling multiple programs being executed on a persistent database, and has the additional feature that the program garbling is decoupled from the database garbling. This allows a client to provide multiple garbled programs to the server as part of a pre-processing phase and then later determine the order and the inputs on which these programs are to be executed, doing work independent of the running times of the programs itself.

The Fibonacci-to-Galois transformation is useful for reducing the propagation delay of feedback shift register-based stream ciphers and hash functions. In this paper, we extend it to handle Galois-to-Galois case as well as feedforward connections. This makes possible transforming Trivium stream cipher and increasing its keystream data rate by 27\% without any penalty in area. The presented transformation might open new possibilities for cryptanalysis of Trivium, since it induces a class of stream ciphers which generate the same set of keystreams as Trivium, but have a different structure.

We show that there exist commitment, zero-knowledge and general function evaluation protocols with universally composable security, in a model where all parties and all protocols have access to a single, global, random oracle and no other trusted setup. This model provides significantly stronger composable security guarantees than the traditional random oracle model of Bellare and Rogaway [CCS’93] or even the common reference string model. Indeed, these latter models provide no security guarantees in the presence of arbitrary protocols that use the same random oracle (or reference string or hash function). Furthermore, our protocols are highly efficient. Specifically, in the interactive setting, our commitment and general computation protocols are much more efficient than the best known ones due to Lindell [Crypto’11,’13] which are secure in the common reference string model. In the non-interactive setting, our protocols are slightly less efficient than the best known ones presented by Afshar et al. [Eurocrypt ’14] but do away with the need to rely on a non-global (programmable) reference string.

In a recent celebrated breakthrough, Garg et al. (FOCS 2013) gave the first candidate for so-called indistinguishability obfuscation (iO) thereby reviving the interest in obfuscation for a general purpose. Since then, iO has been used to advance numerous sub-areas of cryptography. While indistinguishability obfuscation is a general purpose obfuscation scheme, several obfuscators for specific functionalities have been considered. In particular, special attention has been given to the obfuscation of so-called point functions that return zero everywhere, except for a single point $x$. A strong variant is point obfuscation with auxiliary input (AIPO), which allows an adversary to learn some non-trivial auxiliary information about the obfuscated point $x$ (Goldwasser, Tauman-Kalai; FOCS, 2005). Multi-bit point functions are a strengthening of point functions, where on $x$, the point function returns a string $m$ instead of $1$. Multi-bit point functions with auxiliary input (MB-AIPO) have been constructed from composable AIPO by Canetti and Dakdouk (Eurocrypt 2008) and have been used by Matsuda and Hanaoka (TCC 2014) to construct CCA-secure public-key encryption schemes and by Bitansky and Paneth (TCC 2012) to construct three-round weak zero-knowledge protocols for NP. In this paper we present both positive and negative results. We show that if indistinguishability obfuscation exists, then MB-AIPO does not. Towards this goal, we build on techniques by Brzuska, Farshim and Mittelbach (Crypto 2014) who use indistinguishability obfuscation as a mean to attack a large class of assumptions from the Universal Computational Extractor framework (Bellare, Hoang and Keelveedhi; Crypto 2013). On the positive side we introduce a weak version of MB-AIPO which we deem to be outside the reach of our impossibility result. We build this weak version of MB-AIPO based on iO and AIPO and prove that it suffices to construct a public-key encryption scheme that is secure even if the adversary can learn an arbitrary leakage function of the secret key, as long as the secret key remains computationally hidden. Thereby, we strengthen a result by Canetti et al. (TCC 2010) that showed a similar connection in the symmetric-key setting.

The wide availability of inexpensive positioning systems made it possible to embed them into smartphones and other personal devices. This marked the beginning of location-aware applications, where users request personalized services based on their geographic position. The location of a user is, however, highly sensitive information: the user's privacy can be preserved if only the minimum amount of information needed to provide the service is disclosed at any time. While some applications, such as navigation systems, are based on the users' movements and therefore require constant tracking, others only require knowledge of the user's position in relation to a set of points or areas of interest. In this paper we focus on the latter kind of services, where the location information is essentially used to determine membership in one or more geographic sets. We address this problem using Bloom Filters (BF), a compact data structure for representing sets. In particular, we present an extension of the original bloom filter idea: the Spatial Bloom Filter (SBF). SBF's are designed to manage spatial and geographical information in a space efficient way, and are well-suited for enabling privacy in location-aware applications. We show this by providing two multi-party protocols for privacy-preserving computation of location information, based on the known homomorphic properties of public key encryption schemes. The protocols keep the user's exact position private, but allow the provider of the service to learn when the user is close to specific points of interest, or inside predefined areas. At the same time, the points and areas of interest remain oblivious to the user.

We revisit the question of constructing secure general-purpose indistinguishability obfuscation (iO), with a security reduction based on explicit computational assumptions over multi- linear maps. Previous to our work, such reductions were only known to exist based on meta- assumptions and/or ad-hoc assumptions: In the original constructive work of Garg et al. (FOCS 2013), the underlying explicit computational assumption encapsulated an exponential family of assumptions for each pair of circuits to be obfuscated. In the more recent work of Pass et al. (Crypto 2014), the underlying assumption is a meta-assumption that also encapsulates an exponential family of assumptions, and this meta-assumption is invoked in a manner that captures the specific pair of circuits to be obfuscated. The assumptions underlying both these works substantially capture (either explicitly or implicitly) the actual structure of the obfuscation mechanism itself. In our work, we provide the first construction of general-purpose indistinguishability obfuscation proven secure via a reduction to a natural computational assumption over multilinear maps, namely, the Multilinear Subgroup Elimination Assumption. This assumption does not depend on the circuits to be obfuscated (except for its size), and does not correspond to the underlying structure of our obfuscator. The technical heart of our paper is our reduction, which gives a new way to argue about the security of indistinguishability obfuscation.

In a homomorphic signature scheme, a user Alice signs some large dataset $x$ using her secret signing key and uploads the signed data to an untrusted remote server. The server can then run some computation $y=f(x)$ over the signed data and homomorphically derive a short signature $\sigma_{f,y}$ certifying that $y$ is the correct output of the computation $f$. Anybody can verify the tuple $(f, y, \sigma_{f,y})$ using Alice's public verification key and become convinced of this fact without having to retrieve the entire underlying data. In this work, we construct the first (leveled) fully homomorphic signature schemes that can evaluate arbitrary circuits over signed data. Only the maximal depth $d$ of the circuits needs to be fixed a-priori at setup, and the size of the evaluated signature grows polynomially in $d$, but is otherwise independent of the circuit size or the data size. Our solution is based on the (sub-exponential) hardness of the small integer solution (SIS) problem in standard lattices and satisfies full (adaptive) security. In the standard model, we get a scheme with large public parameters whose size exceeds the total size of a data-set. In the random-oracle model, we get a scheme with short public parameters. In both cases, the schemes can be used to sign many different data-sets. The complexity of verifying a signature for a computation $f$ is at least as large as that of computing $f$, but can be amortized when verifying the same computation over many different data-sets. Furthermore, the signatures can be made context-hiding so as not to reveal anything about the data beyond the outcome of the computation. These results offer a significant improvement in capabilities and assumptions over the best prior homomorphic signature schemes, which were limited to evaluating polynomials of constant degree. As a building block of independent interest, we introduce a new notion called homomorphic trapdoor functions (HTDF) which conceptually unites homomorphic encryption and signatures. We construct HTDFs by relying on the techniques developed by Gentry et al. (CRYPTO '13) and Boneh et al. (EUROCRYPT '14) in the contexts of fully homomorphic and attribute-based encryptions.

This paper studies the question of how to define, construct, and use obfuscators for probabilistic programs. Such obfuscators compile a possibly randomized program into a deterministic one, which achieves computationally indistinguishable behavior from the original program as long as it is run on each input at most once. For obfuscation, we propose a notion that extends indistinguishability obfuscation to probabilistic circuits: It should be hard to distinguish between the obfuscations of any two circuits whose output distributions at each input are computationally indistinguishable, possibly in presence of some auxiliary input. We call the resulting notion probabilistic indistinguishability obfuscation (pIO). We define several variants of pIO, using different approaches to formalizing the above security requirement, and study non-trivial relations among them. Moreover, we give a construction of one of our pIO variants from sub-exponentially hard indistinguishability obfuscation (for deterministic circuits) and one-way functions, and conjecture this construction to be a good candidate for other pIO variants. We then move on to show a number of applications of pIO: * We give a general and natural methodology to achieve leveled homomorphic encryption (LHE) from variants of semantically secure encryption schemes and of pIO. In particular, we propose instantiations from lossy and re-randomizable encryption schemes, assuming the two weakest notions of pIO. * We enhance the above constructions to obtain a full-fledged (i.e., non-leveled) FHE scheme under the same (or slightly stronger) assumptions. In particular, this constitutes the first construction of full-fledged FHE that does not rely on encryption with circular security. * Finally, we show that assuming sub-exponentially secure puncturable PRFs computable in NC1, sub-exponentially-secure indistinguishability obfuscation for (deterministic) NC1 circuits can be bootstrapped to obtain indistinguishability obfuscation for arbitrary (deterministic) poly-size circuits.

It is well known that the random oracle model is not sound in the sense that there exist cryptographic systems that are secure in the random oracle model but when instantiated by any family of hash functions become insecure. However, all known separation results require the attacker to send an appropriately crafted message to the challenger in order to break security. Thus, this leaves open the possibility that some cryptographic schemes, such as bit-encryption, are still sound in the random oracle model. In this work we refute this possibility, assuming the existence of indistinguishability obfuscation. We do so in the following way. First, we present a random oracle separation for bit-encryption; namely, we show that there exists a bit-encryption protocol secure in the random oracle model but \emph{completely insecure} when the random oracle is instantiated by any concrete function. Second, we show how to adapt this separation to work for most natural simulation-based and game-based definitions. Our techniques can easily be adapted to other idealized models, and thus we present a \emph{unified approach} to showing separations for most protocols of interest in most idealized models.

We present a construction of a private-key functional encryption scheme for any family of randomized functionalities based on any such scheme for deterministic functionalities that is sufficiently expressive. Instantiating our construction with existing schemes for deterministic functionalities, we obtain schemes for any family of randomized functionalities based on a variety of assumptions (including the LWE assumption, simple assumptions on multilinear maps, and even the existence of any one-way function) offering various trade-offs between security and efficiency. Previously, Goyal, Jain, Koppula and Sahai [Cryptology ePrint Archive, 2013] constructed a public-key functional encryption scheme for any family of randomized functionalities based on indistinguishability obfuscation. One of the key insights underlying our work is that, in the private-key setting, a sufficiently expressive functional encryption scheme may be appropriately utilized for implementing proof techniques that were so far implemented based on obfuscation assumptions (such as the punctured programming technique of Sahai and Waters [STOC 2014]). We view this as a contribution of independent interest that may be found useful in other settings as well.

The increasing ubiquity of the cloud computing paradigm has renewed focus on the classical problem of allowing weak clients to check the results of computation delegated to powerful servers. Recent advances in proof-based verifiable computation have led to several near-practical protocols. Protocols based on interactive proofs (IPs) work with highly restrictive models of computation and are thus efficient only for a limited class of computations. In contrast, protocols based on argument systems apply to a much larger class of computations, but efficiency requires amortization of very expensive setup costs. This paper initiates the study of the practical efficiency of multiprover interactive proofs (MIPs). We present a new MIP for delegating computation that extends insights from a powerful IP protocol (Goldwasser et al., STOC, 2008). Without reductions or amplification, our protocol uses only two provers (departing from prior work on MIPs), and achieves both the efficiency of interactive proof-based protocols and the generality of argument system-based protocols. Also, this result, together with recently developed machinery, creates a potential avenue toward concretely efficient arguments without setup costs. We describe Clover, a built system for verifiable computation, based on our protocol. Although Clover does not implement the full theory (it has setup costs), it applies to problems that existing IPs cannot efficiently handle, and achieves performance comparable to, or better than, the best argument systems.

Side channel attacks -- attacks that exploit implementation-dependent information of a cryptosystem -- have been shown to be highly detrimental, and the cryptographic community has recently focused on developing techniques for securing implementations against such attacks. An important model called \emph{Only Computation Leaks} (OCL) [Micali and Reyzin, TCC '04] and its stronger variants were proposed to model a broad class of leakage attacks (a type of side-channel attack). These models allow for unbounded, arbitrary leakage as long as (1) information in each leakage observation is bounded, and (2) different parts of the computation leak independently. Various results and techniques have been developed for these models and we continue this line of research in the current work. We address the problem of compiling any circuit into a circuit secure against OCL attacks. In order to leverage the OCL assumption, the resulting circuit will be split into components, where at any point in time only a single component is active. Optimally, we would like to output a circuit that has only one component, and no part of the computation needs to be leak-free. However, this task is impossible due to the result of Barak et al. [JACM '12].The current state-of-the-art constructions achieve either two components with additional leak-free hardware, or many components without leak-free hardware. In this work, we show how to achieve the best of both worlds: We construct two-component OCL schemes without relying on leak-free components. Our approach is general and modular -- we develop generic techniques to remove the hardware component from hardware-based constructions, when the functionality provided by the hardware satisfies some properties. Our techniques use universal deniable encryption (recently constructed by Sahai and Water [STOC '14] using indistinguishable obfuscation) and non-committing encryption in a novel way. Then, we observe that the functionalities of the hardware used in previous two-component constructions of Juma and Vahlis [Crypto '10], and Dziembowski and Faust [TCC '12] satisfy the required properties. The techniques developed in this paper have deep connections with adaptively secure and leakage tolerant multi-party computation (MPC). Our constructions immediately yield adaptively secure and leakage tolerant MPC protocols for any no-input randomized functionality in the semi-honest model. The result holds in the CRS model, without pre-processing. Our results also have implications to two-party leakage tolerant computation for arbitrary functionalities, which we obtain by combining our constructions with a recent result of Bitansky, Dachman-Soled, and Lin [Crypto '14].

A non-malleable code protects messages against various classes of tampering. Informally, a code is non-malleable if the message contained in a tampered codeword is either the original message, or a completely unrelated one. Although existence of such codes for various rich classes of tampering functions is known, \emph{explicit} constructions exist only for ``compartmentalized'' tampering functions: \ie the codeword is partitioned into {\em a priori fixed} blocks and each block can {\em only be tampered independently}. The prominent examples of this model are the family of bit-wise independent tampering functions and the split-state model. In this paper, for the first time we construct explicit non-malleable codes against a natural class of non-compartmentalized tampering functions. We allow the tampering functions to {\em permute the bits} of the codeword and (optionally) perturb them by flipping or setting them to 0 or 1. We construct an explicit, efficient non-malleable code for arbitrarily long messages in this model (unconditionally). We give an application of our construction to non-malleable commitments, as one of the first direct applications of non-malleable codes to computational cryptography. We show that non-malleable {\em string} commitments can be ``entirely based on'' non-malleable {\em bit} commitments. More precisely, we show that simply encoding a string using our code, and then committing to each bit of the encoding using a {\em CCA-secure bit commitment} scheme results in a non-malleable string commitment scheme. This reduction is unconditional, does not require any extra properties from the bit-commitment such as ``tag-based'' non-malleability, and works even with physical implementations (which may not imply standard one-way functions). Further, even given a partially malleable bit commitment scheme which allows toggling the committed bit (instantiated, for illustration, using a variant of the Naor commitment scheme under a non-standard assumption on the PRG involved), this transformation gives a fully non-malleable string commitment scheme. This application relies on the non-malleable code being explicit.

Barak, Shaltiel Tromer showed how to construct a True Random Number Generator (TRNG) which is secure against an adversary who has some limited control over the environment. In this paper we improve the security analysis of this TRNG. Essentially, we significantly reduce the entropy loss and running time needed to obtain a required level of security and robustness. Our approach is based on replacing the combination of union bounds and tail inequalities for $\ell$-wise independent random variables in the original proof, by a more refined of the deviation of the probability that a randomly chosen item is hashed into a particular location.

Quantum zero-knowledge proofs and quantum proofs of knowledge are inherently difficult to analyze because their security analysis uses rewinding. Certain cases of quantum rewinding are handled by the results by Watrous (SIAM J Comput, 2009) and Unruh (Eurocrypt 2012), yet in general the problem remains elusive. We show that this is not only due to a lack of proof techniques: relative to an oracle, we show that classically secure proofs and proofs of knowledge are insecure in the quantum setting. More specifically, sigma-protocols, the Fiat-Shamir construction, and Fischlin's proof system are quantum insecure under assumptions that are sufficient for classical security. Additionally, we show that for similar reasons, computationally binding commitments provide almost no security guarantees in a quantum setting. To show these results, we develop the "pick-one trick", a general technique that allows an adversary to find one value satisfying a given predicate, but not two.

In this paper we present MATor: a framework for rigorously assessing the degree of anonymity in the Tor network. The framework explicitly addresses how user anonymity is impacted by real-life characteristics of actually deployed Tor, such as its path selection algorithm, Tor consensus data, and the preferences and the connections of the user. The anonymity assessment is based on rigorous anonymity bounds that are derived in an extension of the AnoA framework (IEEE CSF 2013). We show how to apply MATor on Tor's publicly available consensus and server descriptor data, thereby realizing the first real-time anonymity monitor. Based on experimental evaluations of this anonymity monitor on Tor Metrics data, we propose an alternative path selection algorithm that provides stronger anonymity guarantees without decreasing the overall performance of the Tor network.

An efficient quantum modular exponentiation method is indispensible for Shor's factoring algorithm. But we find that all descriptions presented by Shor, Nielsen and Chuang, Markov and Saeedi, et al., are flawed. We also remark that some experimental demonstrations of Shor's algorithm are misleading, because they violate the necessary condition that the selected number $q=2^s$, where $s$ is the number of qubits used in the first register, must satisfy $n^2 \leq q < 2n^2$, where $n$ is the large number to be factored.

Cayley hash functions are based on a simple idea of using a pair of (semi)group elements, $A$ and $B$, to hash the 0 and 1 bit, respectively, and then to hash an arbitrary bit string in the natural way, by using multiplication of elements in the (semi)group. In this paper, we focus on hashing with $2 \times 2$ matrices over $F_p$. Since there are many known pairs of $2 \times 2$ matrices over $Z$ that generate a free monoid, this yields numerous pairs of matrices over $F_p$, for a sufficiently large prime $p$, that are candidates for collision-resistant hashing. However, this trick can ``backfire", and lifting matrix entries to $Z$ may facilitate finding a collision. This ``lifting attack" was successfully used by Tillich and Zémor in the special case where two matrices $A$ and $B$ generate (as a monoid) the whole monoid $SL_2(\Z_+)$. However, in this paper we show that the situation with other, ``similar", pairs of matrices from $SL_2(Z)$ is different, and the ``lifting attack" can (in some cases) produce collisions in the {\it group} generated by $A$ and $B$, but not in the positive {\it monoid}. Therefore, we argue that for these pairs of matrices, there are no known attacks at this time that would affect security of the corresponding hash functions. We also give explicit lower bounds on the length of collisions for hash functions corresponding to some particular pairs of matrices from $SL_2(F_p)$.

We study ballot independence for election schemes. First, we formally define ballot independence as a cryptographic game and prove that ballot secrecy implies ballot independence. Secondly, we introduce a notion of controlled malleability and prove that it is sufficient for ballot independence. We also prove that non-malleable ballots are sufficient for ballot independence. Thirdly, we prove that ballot independence is sufficient for ballot secrecy in a special case. Our results show that ballot independence is necessary in election schemes satisfying ballot secrecy. Furthermore, our sufficient conditions enable simpler proofs of ballot secrecy.

Watrous (STOC 2006) proved that plugging classical bit commitment scheme that is secure against quantum attack into the GMW-type construction of zero-knowledge gives a classical zero-knowledge proof that is secure against quantum attack. In this paper, we showed that plugging quantum bit commitment scheme (allowing quantum computation and communication) into the GMW-type construction also gives a quantum zero-knowledge proof, as one expects. However, since the binding condition of quantum bit commitment scheme is inherently different from its classical counterpart, compared with Watrous' security proof, here we encounter new difficulty in soundness analysis. To overcome the difficulty, we take a geometric approach, managing to reduce quantum soundness analysis to classical soundness analysis. We also propose a formalization of non-interactive quantum bit commitment scheme, which may come in handy in other places. Moreover, inspired by our formalization, we generalize Naor's construction of bit commitment scheme to the quantum setting, achieving non-interactive commit stage. We hope quantum bit commitment scheme can find more applications in quantum cryptography.

We construct a constant-round resettably-sound zero-knowledge argument of knowledge based on black-box use of any one-way function. Resettable-soundness was introduced by Barak, Goldreich, Goldwasser and Lindell [FOCS 01] and is a strengthening of the soundness requirement in interactive proofs demanding that soundness should hold even if the malicious prover is allowed to “reset” and “restart” the verifier. In their work they show that resettably-sound ZK arguments require non-black-box simulation techniques, and also provide the first construction based on the breakthrough simulation technique of Barak [FOCS 01]. All known implementations of Barak’s non-black-box technique required non-black-box use of a collision-resistance hash-function (CRHF). Very recently, Goyal, Ostrovsky, Scafuro and Visconti [STOC 14] showed an implementation of Barak’s technique that needs only black-box access to a collision-resistant hash-function while still having a non-black-box simulator. (Such a construction is referred to as semi black-box.) Plugging this implementation in the BGGL’s construction yields the first resettably-sound ZK arguments based on black-box use of CRHFs. However, from the work of Chung, Pass and Seth [STOC 13] and Bitansky and Paneth [STOC13], we know that resettably-sound ZK arguments can be constructed from non-black-box use of any one-way function (OWF), which is the minimal assumption for ZK arguments. Hence, a natural question is whether it is possible to construct resettably-sound zero-knowledge arguments from black-box use of any OWF only. In this work we provide a positive answer to this question thus closing the gap between black-box and non-black-box constructions for resettably-sound ZK arguments.

In this paper we present a new attack on the polynomial version of the Ring-LWE assumption, for certain carefully chosen number fields. This variant of RLWE, introduced in [BV11] and called the PLWE assumption, is known to be as hard as the RLWE assumption for 2-power cyclotomic number fields, and for cyclotomic number fields in general with a small cost in terms of error growth. For general number fields, we articulate the relevant properties and prove security reductions for number fields with those properties. We then present an attack on PLWE for number fields satisfying certain properties.

In this work, we seek to extend the capabilities of the “core obfuscator” from the work of Garg, Gentry, Halevi, Raykova, Sahai, and Waters (FOCS 2013), and all subsequent works constructing general-purpose obfuscators. This core obfuscator builds upon approximate multilinear maps, and applies to matrix branching programs. All previous works, however, limited the applicability of such core obfuscators to matrix branching programs where each matrix was of full rank. As we illustrate by example, this limitation is quite problematic, and intuitively limits the core obfuscator to obfuscating matrix branching programs that cannot “forget.” At a technical level, this limitation arises in previous work because all previous work relies on Kilian’s statistical simulation theorem, which is false when applied to matrices not of full rank. In our work, we build the first core obfuscator that can apply to matrix branching programs where matrices can be of arbitrary rank. We prove security of our obfuscator in the generic multilinear model, demonstrating a new proof technique that bypasses Kilian’s statistical simulation theorem. Furthermore, our obfuscator achieves two other notable advances over previous work: - Our construction allows for non-square matrices of arbitrary dimensions. We also show that this flexibility yields concrete efficiency gains. - Our construction allows for a single obfuscation to yield multiple bits of output. All previous work yielded only one bit of output. Our work leads to significant efficiency gains for obfuscation. Furthermore, our work can be applied to achieve efficiency gains even in applications not directly using obfuscation.

In the problem of anonymous authentication (Boneh et al. CCS 1999), a sender wishes to authenticate a message to a given recipient in a way that preserves anonymity: the recipient does not know the identity of the sender and only is assured that the sender belongs to some authorized set. Although solutions for the problem exist (for example, by using ring signatures, e.g. Naor, Crypto 2002), they provide no security when the anonymity set is a singleton. This work is motivated by the question of whether there is any type of anonymity possible in this scenario. It turns out that we can still protect the identity of all senders (authorized or not) if we shift our concern from preventing the identity information be revealed to the recipient to preventing it could be revealed to an external entity, other than the recipient. We define a natural functionality which provides such guarantees and we denote it by F_{eaa} for externally anonymous authenticated channel. We argue that any realization of F_{eaa} must be deniable in the sense of Dodis et al. TCC 2009. To prove the deniability of similar primitives, previous work defined ad hoc notions of deniability for each task, and then each notion was showed equivalent to realizing the primitive in the Generalized Universal Composability framework (GUC, Canetti et al. TCC 2007). Instead, we put forward the question of whether deniability can be defined independently from any particular task. We answer this question in the affirmative providing a natural extension of the definition of Dodis et al. for arbitrary multiparty protocols. Furthermore, we show that a protocol satisfies this definition if an only if it realizes the ideal functionality F_{eaa} in the GUC framework. This result enables us to prove that most GUC functionalities we are aware of (and their realizations) are deniable. We conclude by applying our results to the construction of a deniable protocol that realizes F_{eaa}.

A constrained pseudorandom function (CPRF) PRF allows to derive constrained evaluation keys that only allow to evaluate PRF on a subset of inputs. CPRFs have only recently been introduced independently by three groups of researchers. However, somewhat curiously, all of them could only achieve a comparatively weak, selective-challenge form of security (except for small input spaces, very limited forms of constrained keys, or with superpolynomial security reductions). In this paper, we construct the first fully secure CPRF without any of the above restrictions. Concretely, we support ``bit-fixing'' constrained keys that hardwire an arbitrary subset of the input bits to fixed values, we support exponentially large input spaces, and our security reduction is polynomial. We require very heavyweight tools: we assume multilinear maps, indistinguishability obfuscation, and our proof is in the random oracle model. Still, our analysis is far from tautological, and even with these strong building blocks, we need to develop additional techniques and tools. As a simple application, we obtain the first adaptively secure non-interactive key exchange protocols for large user groups.

Shor's factoring algorithm uses two quantum registers. By introducing more registers we show that the measured numbers in these registers which are of the same pre-measurement state, should be equal if the original Shor's complexity argument is sound. This contradicts the argument that the second register has $r$ possible measured values. There is an anonymous comment which argues that the states in these registers are entangled. If so, the entanglement involving many quantum registers can not be interpreted by the mechanism of EPR pairs and the like. In view of this peculiar entanglement has not yet been mentioned and investigated, we think the claim that the Shor's algorithm runs in polynomial time needs more physical verifications. We also discuss the problem to certify quantum computers.

We show how to extract an arbitrary polynomial number of simultaneously hardcore bits from any one-way function. In the case the one-way function is injective or has polynomially-bounded pre-image size, we assume the existence of indistinguishability obfuscation (iO). In the general case, we assume the existence of differing-input obfuscation (diO), but of a form weaker than full auxiliary-input diO. Our construction for injective one-way functions extends to extract hardcore bits on multiple, correlated inputs, yielding new D-PKE schemes. Of independent interest is a definitional framework for differing-inputs obfuscation in which security is parameterized by circuit-sampler classes.

Shor's quantum factoring algorithm and a few other efficient quantum algorithms break many classical crypto-systems. In response, people proposed post-quantum cryptography based on computational problems that are believed hard even for quantum computers. However, security of these schemes against \emph{quantum} attacks is elusive. This is because existing security analysis (almost) only deals with classical attackers and arguing security in the presence of quantum adversaries is challenging due to unique quantum features such as no-cloning. This work proposes a general framework to study which classical security proofs can be restored in the quantum setting. Basically, we split a security proof into (a sequence of) classical security reductions, and investigate what security reductions are ``quantum-friendly''. We characterize sufficient conditions such that a classical reduction can be ``lifted'' to the quantum setting. We then apply our lifting theorems to post-quantum signature schemes. We are able to show that the classical generic construction of hash-tree based signatures from one-way functions and and a more efficient variant proposed in~\cite{BDH11} carry over to the quantum setting. Namely, assuming existence of (classical) one-way functions that are resistant to efficient quantum inversion algorithms, there exists a quantum-secure signature scheme. We note that the scheme in~\cite{BDH11} is a promising (post-quantum) candidate to be implemented in practice and our result further justifies it. Actually, to obtain these results, we formalize a simple criteria, which is motivated by many classical proofs in the literature and is straightforward to check. This makes our lifting theorem easier to apply, and it should be useful elsewhere to prove quantum security of proposed post-quantum cryptographic schemes. Finally we demonstrate the generality of our framework by showing that several existing works (Full-Domain hash in the quantum random-oracle model~\cite{Zha12ibe} and the simple hybrid arguments framework in~\cite{HSS11}) can be reformulated under our unified framework.

Information theoretic cryptography is discussed based on conditional Rényi entropies. Our discussion focuses not only on cryptography but also on the definitions of conditional Rényi entropies and the related information theoretic inequalities. First, we revisit conditional Rényi entropies, and clarify what kind of properties are required and actually satisfied. Then, we propose security criteria based on Rényi entropies, which suggests us deep relations between (conditional) Rényi entropies and error probabilities by using several guessing strategies. Based on these results, unified proof of impossibility, namely, the lower bounds of key sizes is derived based on conditional Rényi entropies. Our model and lower bounds include the Shannon's perfect secrecy, and the min-entropy based encryption presented by Dodis, and Alimomeni and Safavi-Naini. Finally, a new optimal symmetric key encryption is proposed which achieve our lower bounds.

Attribute-based encryption (ABE) which allows users to encrypt and decrypt messages based on user attributes is a type of one-to-many encryption. Unlike the conventional one-to-one encryption which has no intention to exclude any partners of the intended receiver from obtaining the plaintext, an ABE system tries to exclude some unintended recipients from obtaining the plaintext whether they are partners of some intended recipients. We remark that this requirement for ABE is very hard to meet. An ABE system cannot truly exclude some unintended recipients from decryption because some users can exchange their decryption keys in order to maximize their own interests. The flaw discounts the importance of the cryptographic primitive.

Most entropy notions $H(.)$ like Shannon or min-entropy satisfy a chain rule stating that for random variables $X,Z$ and $A$ we have $H(X|Z,A)\ge H(X|Z)-|A|$. That is, by conditioning on $A$ the entropy of $X$ can decrease by at most the bitlength $|A|$ of $A$. Such chain rules are known to hold for some computational entropy notions like Yao's and unpredictability-entropy. For HILL entropy, the computational analogue of min-entropy, the chain rule is of special interest and has found many applications, including leakage-resilient cryptography, deterministic encryption and memory delegation. These applications rely on restricted special cases of the chain rule. Whether the chain rule for conditional HILL entropy holds in general was an open problem for which we give a strong negative answer: We construct joint distributions $(X,Z,A)$, where $A$ is a distribution over a \emph{single} bit, such that the HILL entropy $H_\infty(X|Z)$ is large but $H_\infty(X|Z,A)$ is basically zero. Our counterexample just makes the minimal assumption that ${\bf NP}\nsubseteq{\bf P/poly}$. Under the stronger assumption that injective one-way function exist, we can make all the distributions efficiently samplable. Finally, we show that some more sophisticated cryptographic objects like lossy functions can be used to sample a distribution constituting a counterexample to the chain rule making only a single invocation to the underlying object.

Nowadays there are different types of attacks in block and stream ciphers. In this work we will present some of the most used attacks on stream ciphers. We will present the newest techniques with an example of usage in a cipher, explain and comment. Previous we will explain the difference between the block ciphers and stream ciphers.