Secure multi-party computation (MPC) allows multiple parties to compute a known function over inputs held by each party, without any party having to reveal its private input. Unfortunately, traditional MPC algorithms do not scale well to large numbers of parties. In this paper, we describe several recent MPC algorithms that are designed to handle large networks. All of these algorithms rely on recent techniques from the Byzantine agreement literature on forming and using quorums. Informally, a quorum is a small set of parties, most of which are trustworthy. We describe the advantages and disadvantages of these scalable algorithms, and we propose new ideas for improving practicality of current techniques. Finally, we conduct simulations to measure bandwidth cost for several current MPC algorithms.

We initiate the study of good rate homomorphic encryption schemes. Based on previous work on securely evaluating (binary I/O) branching programs, we propose a leveled homomorphic encryption scheme for {\em large-output} polynomial-size branching programs (which we call $\mathbf{L/poly}$) that possesses near optimal-rate. The rate analysis of the new scheme is intricate: the best rate is achieved if a certain parameter $s$ is set equal to the only positive root of a degree-$m$ polynomial, where $m$ is the length of the branching program. We employ the Newton-Puiseux algorithm to find a Puiseux series for this parameter, and based on this, propose a $\Theta (\log m)$-time algorithm to find an integer approximation to $s$. We also describe a rate-optimal 1-out-of-$n$ CPIR based on rate-optimal homomorphic encryption. In concrete terms, when applied to say, a movie database with $n = 2^{16}$ elements of $\ell = 3.8 \cdot 10^{9}$-bits, the client can privately download a movie with a communication rate of almost $0.99$, hence sacrificing only about $1\%$ of bandwidth for privacy. We also analyze the optimality of the rate efficiency of our scheme in a novel model that may be of independent interest. Our $1$-out-of-$n$ CPIR has rate $ 1- 1.72 \sqrt{k / \ell} \cdot \log_{2} n + O_\ell(\ell^{-1})$, while we show that no black-box construction surpasses $1 - \sqrt{k / \ell} (\log n/ \log \log n) + O_\ell(\ell^{-1})$ in terms of rate, where $\ell$ is the length of the database elements and $k$ the security parameter.

In this paper we study the question of key management and practical operational security in bitcoin digital currency storage systems. We study the security two most used bitcoin HD Wallet key management solutions (e.g. in BIP032 and in earlier systems). These systems have extensive audit capabilities but this property comes at a very high price. They are excessively fragile. One small security incident in a remote corner of the system and everything collapses, all private keys can be recovered and ALL bitcoins within the remit of the system can be stolen. Privilege escalation attacks on HD Wallet solutions are not new. In this paper we take it much further. We propose new more advanced combination attacks in which the security of keys hold in cold storage can be compromised without executing any software exploit on the cold system, but through security incidents at operation such as bad random number or related random events. In our new attacks all bitcoins over whole large security domains can be stolen by people who have the auditor keys which are typically stored in hot systems connected to the Internet and can be stolen easily. Our combination attacks allow to recover private keys which none of the earlier attacks in isolation could hope to recover. Classical bad random attacks typically concern only very few bitcoin accounts, and only some very lucky holders of bitcoins can actually steal other people's bitcoins. In this paper we go beyond identical random attacks and show several attacks which also work with related random events, which events are more probable and yet less likely to be detected before it is too late. We also present several attacks which work across distinct security domains which share no common setup, code or keys. Yet in certain circumstances all the bitcoins in each domain can be stolen. All our attacks are practical and realistic given the numerous relevant events have already happened in the bitcoin blockchain hundreds of times, some as recently as September 2014. It is not clear if this problem can be repaired, i.e. if there exists a key management solution with similar audit capabilities as BIP032 which would be immune against this sort of advanced combination attacks.

Currently, the Internet Research Task Force (IRTF) discusses requirements for new elliptic curves to be standardized in TLS and other internet protocols. This position paper discusses the view of the members of the ECC Brainpool on these requirements, in particular with respect to hardware implementations.

While password-authenticated key exchange (or PAKE) protocols have been deeply studied, a server corruption remains the main threat, with many concrete cases nowadays. Verifier-based PAKE (or VPAKE) protocols, initially called Augmented-PAKE, have been proposed to limit the impact of any leakage. However, no satisfactory security model has ever been proposed to quantify the actual security of a protocol in the standard model. The unique model proposed so far is an ideal functionality in the universal composability (\UC) framework, but is only meaningful in idealized models. In this paper, we first formally define some properties for the transform (password hashing) applied to the password for the storage on the server-side, for an efficient VPAKE use. A tight one-wayness is required to prevent improved password searches. We then enhance the Bellare-Pointcheval-Rogaway game-based model for PAKE to VPAKE protocols, in such a way that it allows a VPAKE protocol to be secure in the standard model. In addition, we show how to further extend this model to handle non-uniform and related passwords, both in case of PAKE and VPAKE. Finally, we propose very efficient constructions of password hashing and \VPAKE protocols, which are nearly as efficient as the best PAKE protocols to date.

An important problem in secure multi-party computation is the design of protocols that can tolerate adversaries that are capable of corrupting parties dynamically and learning their internal states. In this paper, we make significant progress in this area in the context of password-authenticated key exchange (PAKE) and oblivious transfer (OT) protocols. More precisely, we first revisit the notion of projective hash proofs and introduce a new feature that allows us to \emph{explain} any message sent by the simulator in case of corruption, hence the notion of \emph{Explainable Projective Hashing}. Next, we demonstrate that this new tool generically leads to efficient PAKE and OT protocols that are secure against semi-adaptive adversaries without erasures in the Universal Composability (UC) framework. We then show how to make these protocols secure even against adaptive adversaries, using \emph{non-committing encryption}, in a much more efficient way than generic conversions from semi-adaptive to adaptive security. Finally, we provide concrete instantiations of explainable projective hash functions that lead to the most efficient PAKE and OT protocols known so far, with UC-security against adaptive adversaries, with or without erasures, in the single global CRS setting. As an important side contribution, we also propose a new commitment scheme based on DDH, which leads to the construction of the first one-round PAKE adaptively secure under plain DDH without pairing, assuming reliable erasures, and also improves previous constructions of OT and two- or three-round PAKE schemes.

The article proposes an Online/Off-line Ring Signature Scheme in random oracle model.Security of the scheme relies on both Computational Diffie-Hellman and k-CAA problems. The proposed scheme is proven the two most important security goals Existential Unforgeability and Signer Ambiguity. Also it has robustness property where the misbehavior of the signer can be detected. Signing process is performed in two phases online and offline. All heavy computations are performed in Off-line stage. So the overall computational cost is reduced and very less than the traditional signature scheme. The scheme can be applied to Mobile Ad Hoc Networks (MANETs) that undergo node mobility.

In secure two-party computation protocols, the cut-and-choose paradigm is used to prevent the malicious party who constructs the garbled circuits from cheating. In previous realization of the cut-and-choose technique on the garbled circuits, the delivery of the random keys is divided into multiple stages. Thus, the round complexity is high and the consistency of cut-and-choose challenge should be proved. In this paper, we introduce a new primitive called cut-and-choose bilateral oblivious transfer, which transfers all necessary keys of garbled circuits in one process. Specifically, in our oblivious transfer protocol, the sender inputs two pairs $(x_0,x_1)$, $(y_0,y_1)$ and a bit $\tau$; the receiver inputs two bits $\sigma$ and $j$. After the protocol execution, the receiver obtains $x_{\tau},y_{\sigma}$ for $j=1$, and $x_0,x_1,y_0,y_1$ for $j=0$. By the introduction of this new primitive, the round complexity of secure two-party computation protocol can be decreased; the cut-and-choose challenge $j$ is no need to be opened anymore, therefore the consistency proof of $j$ is omitted. In addition, the primitive is of independent interest and could be useful in many cut-and-choose scenarios.

We construct a 3-move public coin special honest verifier zero-knowledge proof, a so-called Sigma-protocol, for a list of commitments having at least one commitment that opens to 0. It is not required for the prover to know openings of the other commitments. The proof system is efficient, in particular in terms of communication requiring only the transmission of a logarithmic number of commitments. We use our proof system to instantiate both ring signatures and zerocoin, a novel mechanism for bitcoin privacy. We use our Sigma-protocol as a (linkable) ad-hoc group identification scheme where the users have public keys that are commitments and demonstrate knowledge of an opening for one of the commitments to unlinkably identify themselves (once) as belonging to the group. Applying the Fiat-Shamir transform on the group identification scheme gives rise to ring signatures, applying it to the linkable group identification scheme gives rise to zerocoin. Our ring signatures are very small compared to other ring signature schemes and we only assume the users' secret keys to be the discrete logarithms of single group elements so the setup is quite realistic. Similarly, compared with the original zerocoin protocol we rely on a weak cryptographic assumption and do not require a trusted setup. A third application of our Sigma protocol is an efficient proof of membership of a secret committed value belonging to a public list.

A hierarchical key assignment scheme is a method to assign some private information and encryption keys to a set of classes in a partially ordered hierarchy, in such a way that the private information of a higher class can be used to derive the keys of all classes lower down in the hierarchy. In this paper we analyze the security of hierarchical key assignment schemes according to different notions: security with respect to key indistinguishability and against key recovery, as well as the two recently proposed notions of security with respect to strong key indistinguishability and against strong key recovery. We first explore the relations between all security notions and, in particular, we prove that security with respect to strong key indistinguishability is not stronger than the one with respect to key indistinguishability. Afterwards, we propose a general construction yielding a hierarchical key assignment scheme offering security against strong key recovery, given any hierarchical key assignment scheme which guarantees security against key recovery.

The SPEKE protocol is commonly considered one of the classic Password Authenticated Key Exchange (PAKE) schemes. It has been included in international standards (particularly, ISO/IEC 11770-4 and IEEE 1363.2) and deployed in commercial products (e.g., Blackberry). We observe that the original SPEKE specification is subtly different from those defined in the ISO/IEC 11770-4 and IEEE 1363.2 standards. We show that those differences have critical security implications by presenting two new attacks on SPEKE: an impersonation attack and a key-malleability attack. The first attack allows an attacker to impersonate a user without knowing the password by engaging in two parallel sessions with the victim. The second attack allows an attacker to manipulate the session key established between two honest users without being detected. Both attacks are applicable to the original SPEKE scheme, and are only partially addressed in the ISO/IEC 11770-4 and IEEE 1363.2 standards. We highlight deficiencies in both standards and suggest concrete changes.

Multi-Factor Authentication (MFA), often coupled with Key Exchange (KE), offers very strong protection for secure communication and has been recommended by many major governmental and industrial bodies for use in highly sensitive applications. Over the past few years many companies started to offer various MFA services to their users and this trend is ongoing. The MFAKE protocol framework presented in this paper offers \emph{à la carte} design of multi-factor authentication and key exchange protocols by mixing multiple \emph{types} and \emph{quantities} of authentication factors in a secure way: MFAKE protocols designed using our framework can combine any subset of multiple low-entropy (one-time) passwords/PINs, high-entropy private/public keys, and biometric factors. This combination is obtained in a modular way from efficient single-factor password-based, public key-based, and biometric-based authentication-only protocols that can be executed in concurrent sessions and bound to a single session of an unauthenticated key exchange protocol to guarantee forward secrecy. The modular approach used in the framework is particularly attractive for MFAKE solutions that require backward compatibility with existing single-factor authentication solutions or where new factors should be introduced gradually over some period of time. The framework is proven secure using the state-of-the art game-based security definitions where specifics of authentication factors such as dictionary attacks on passwords and imperfectness of the biometric matching processes are taken into account.

Recently, Worku et al. pointed out that the work “privacy-preserving public auditing for data storage security in cloud computing” proposed by Wang et al. is insecure and their second work “privacy- preserving public auditing for secure cloud the storage” is inefficient. Thus, they offered a secure and efficient-privacy public auditing scheme for cloud storage. They claimed that their system is provably secure in the random oracle model and the operation is effective. However, after crypto-analysis, we found that the scheme cannot reach the security goal, it has the existential forgery attack. We, therefore, alter it to incorporate the desired privacy preserving requirement, which is very significant in a privacy-preserving public auditing protocol for cloud storage.

Authentication plays an important role in an open network environment in order to authenticate two communication parties among each other. Authentication protocols should protect the sensitive information against a malicious adversary by providing a variety of services, such as authentication, user credentials' privacy, user revocation and re-registration, when the smart card is lost/stolen or the private key of a user or a server is revealed. Unfortunately, most of the existing multi-server authentication schemes proposed in the literature do not support the fundamental security property such as the revocation and re-registration with same identity. Recently, in 2014, He and Wang proposed a robust and efficient multi-server authentication scheme using biometrics-based smart card and elliptic curve cryptography (ECC). In this paper, we analyze the He-Wang's scheme and show that He-Wang's scheme is vulnerable to a known session-specific temporary information attack and impersonation attack. In addition, we show that their scheme does not provide strong user's anonymity. Furthermore, He-Wang's scheme cannot support the revocation and re-registration property. Apart from these, He-Wang's scheme has some design flaws, such as wrong password login and its consequences, and wrong password update during password change phase.

Despite two decades of intensive research, it remains a challenge to design a practical anonymous two-factor authentication scheme, for the designers are confronted with an impressive list of security requirements (e.g., resistance to smart card loss attack) and desirable attributes (e.g., local password update). Numerous solutions have been proposed, yet most of them are shortly found either unable to satisfy some critical security requirements or short of a few important features. To overcome this unsatisfactory situation, researchers often work around it in hopes of a new proposal (but no one has succeeded so far), while paying little attention to the fundamental question: whether or not there are inherent limitations that prevent us from designing an ``ideal'' scheme that satisfies all the desirable goals? In this work, we aim to provide a definite answer to this question. We first revisit two foremost proposals, i.e. Tsai et al.'s scheme and Li's scheme, revealing some subtleties and challenges in designing such schemes. Then, we systematically explore the inherent conflicts and unavoidable trade-offs among the design criteria. Our results indicate that, under the current widely accepted adversarial model, certain goals are beyond attainment. This also suggests a negative answer to the open problem left by Huang et al. in 2014. To the best of knowledge, the present study makes the first step towards understanding the underlying evaluation metric for anonymous two-factor authentication, which we believe will facilitate better design of anonymous two-factor protocols that offer acceptable trade-offs among usability, security and privacy.

Trusted Network Connect (TNC) requires both user authentication and integrity validation of an endpoint before it connects to the internet or accesses some web service. However, as the user authentication and integrity validation are usually done via independent protocols, TNC is vulnerable to the Man-in-the-Middle (MitM) attack. This paper analyzes TNC which uses keys with Subject Key Attestation Evidence (SKAE) extension to perform user authentication and the IF-T protocol binding to TLS to carry integrity measurement messages in the Universally Composable (UC) framework. Our analysis result shows that TNC using keys with SKAE extension can resist the MitM attack. In this paper, we introduce two primitive ideal functionalities for TNC: an ideal dual-authentication certification functionality which binds messages and both the user and platform identities, and an ideal platform attestation functionality which formalizes the integrity verification of a platform. We prove that the SKAE extension protocol and the basic TCG platform attestation protocol, both of which are defined by TCG specifications, UC-realizes the two primitive functionalities respectively. In the end, we introduce a general ideal TNC functionality and prove that the complete TNC protocol, combining the IF-T binding to TLS which uses keys with SKAE extension for client authentication and the basic TCG platform attestation platform protocol, securely realizes the TNC functionality in the hybrid model.

Privacy-enhancing attribute-based credentials (PABCs) are the core ingredient to privacy-friendly authentication systems, allowing users to obtain credentials on attributes and prove possession of these credentials in an unlinkable fashion while revealing only a subset of the attributes. To be useful in practice, however, PABCs typically need additional features such as i) revocation, ii) pooling prevention by binding credentials to users' secret keys, iii) pseudonyms as privacy-friendly user public keys, iv) proving equality of attributes without revealing their values, v) or advanced issuance where attributes can be "blindly" carried over into new credentials. Provably secure solutions exist for most of these features in isolation, but it is unclear how they can be securely combined into a full-fledged PABC system, or even which properties such a system would aim to fulfill. We provide a formal treatment of PABC systems supporting the mentioned features by defining their syntax and security properties, resulting in the most comprehensive definitional framework for PABCs so far. Unlike previous efforts, our definitions are not targeted at one specific use-case; rather, we try to capture generic properties that can be useful in a variety of scenarios. We believe that our definitions can also be used as a starting point for diverse application-dependent extensions and variations of PABCs. We present and prove secure a generic and modular construction of a PABC system from simpler building blocks, allowing for a "plug-and-play" composition based on different instantiations of the building blocks. Finally, we give secure instantiations for each of the building blocks, including in particular instantiations based on CL- and Brands-signatures which are the core of the Idemix and U-Prove protocols.

We consider the problem of constructing anonymous credentials for use in a setting where the issuer of credentials is also the verifier, or more generally where the issuer and verifier have a shared key. In this setting we can use message authentication codes (MACs) instead of public key signatures as the basis for the credential system. To this end, we construct two algebraic MACs in prime-order groups, along with efficient protocols for issuing credentials, asserting possession a credential, and proving statements about hidden attributes (e.g., the age of the credential owner). We prove the security of the first scheme in the generic group model, and prove the security of the second scheme -- using a dual-system-based approach -- under decisional Diffie-Hellman (DDH). Our MACs are of independent interest, as they are the only uf-cmva-secure MACs with efficient proofs of knowledge. Finally, we compare the efficiency of our new systems to two existing constructions of anonymous credentials: U-Prove and Idemix. We show that the performance of the new schemes is competitive with U-Prove (which is not provably secure, whereas ours is based on DDH), and many times faster than Idemix.

On top of the passively secure extension protocol of [IKNP03] we build a new construction secure against active adversaries. We can replace the invocation of the hash function that is used to check the receiver is well-behaved with the XOR of bit strings. This is possible by applying a cut-and-choose technique on the length of the bit strings that the receiver sends in the reversed OT. We also improve on the number of seeds required for the extension, both asymptotically and practically. Moreover, the protocol used to test receiver's behaviour enjoys unconditional security.

We consider the following problem: Assuming that Alice and Bob have an integer interval $[a, e]$ and an integer $b$ respectively, for a commitment $c$ to $b$, Alice and Bob jointly check whether $b$ is within $[a, e]$ without revealing their inputs, where either party may behave maliciously. A special case of the problem is the secure integer comparison in the malicious model. This problem mainly arises from location-based access control systems where one party needs to assure to the other party that its location is within some definite area. Our main result is a constant-round protocol that exhibit the square of $\log e$ communication and the square of $\log e$ exponentiations with simulation-based security. At the heart of the construction is perfect $k$-ary index and corresponding zero-knowledge proof techniques. We consider a more general case of the problem where the interval is substituted by a union of intervals.

We remark that the Bellare-Rivest protocol for translucent cryptography [J. Cryptology (1999) 12: 117-139] can not truly enable the government to decrypt partial encrypted communications.

With the emergence of cloud computing services, a resource-constrained client can outsource its computationally-heavy tasks to cloud providers. Because such service providers might not be fully trusted by the client, the need to verify integrity of the returned computation result arises. The ability to do so is called verifiable delegation or verifiable outsourcing. Furthermore, the data used in the computation may be sensitive and it is often desired to protect it from the cloud throughout the computation. In this work, we put forward solutions for verifiable outsourcing of matrix multiplications that favorably compare with the state of the art. The cost of verifying the result of computation consists of a single modulo exponentiation and can be further reduced if the cloud is rational (or lazy). A lazy cloud tries to minimize its work by skipping the computation, but does not maliciously corrupt the data. Our solutions achieve several desired features such as data protection, public verifiability, and computation chaining.

Protocols for secure two-party computation enable a pair of mistrusting parties to compute a joint function of their private inputs without revealing anything but the output. One of the fundamental techniques for obtaining secure computation is that of Yao's garbled circuits. In the setting of malicious adversaries, where the corrupted party can follow any arbitrary (polynomial-time) strategy in an attempt to breach security, the cut-and-choose technique is used to ensure that the garbled circuit is constructed correctly. The cost of this technique is the construction and transmission of multiple circuits; specifically, $s$ garbled circuits are used in order to obtain a maximum cheating probability of $2^{-s}$. In this paper, we show how to reduce the amortized cost of cut-and-choose based secure two-party computation to ${\cal O}\(\frac{s}{\log N}\)$ garbled circuits when $N$ secure computations are run. We use this method to construct a secure protocol in the batch setting. Next, we show how the cut-and-choose method on garbled circuits can be used in an online/offline setting in order to obtain a very fast online phase with very few exponentiations, and we apply our amortization method to this setting as well. Our online/offline protocols are competitive with the TinyOT and SPDZ protocols due to the minimal interaction in the online phase (previous protocols require only information-theoretic operations in the online phase and are therefore very efficient; however, they also require many rounds of communication which increases latency). Although ${\cal O}(\frac{s}{\log N})$ may seem to be a mild efficiency improvement asymptotically, it is a \emph{dramatic improvement} for concrete parameters since $s$ is a statistical security parameter and so is typically small. Specifically, instead of $40$ circuits to obtain an error of $2^{-40}$, when running $2^{10}$ executions we need only $7.06$ circuits on average per secure computation, and when running $2^{20}$ executions this is reduced to an average of just $4.08$. In addition, in the online/offline setting, the online phase per secure computation consists of evaluating only $6$ garbled circuits for $2^{10}$ executions and $4$ garbled circuits for $2^{20}$ executions (plus some small additional overhead). In practice, when using fast implementations (like the JustGarble framework of Bellare et al.), the resulting protocol is remarkably fast. We present a number of variants of our protocols with different assumptions and efficiency levels. Our basic protocols rely on the DDH assumption alone, while our most efficient variants are proven secure in the random-oracle model. Interestingly, the variant in the random-oracle model of our protocol for the online/offline setting has online communication that is independent of the size of the circuit in use. None of the previous protocols in the online/offline setting achieves this property, which is very significant since communication is usually a dominant cost in practice.

In response to the need for secure one-round authenticated key exchange protocols providing both perfect forward secrecy and full deniability, we put forward a new paradigm for constructing protocols from a Diffie-Hellman type protocol plus a non-interactive designated verifier proof of knowledge (DV-PoK) scheme. We define the notion of DV-PoK which is a variant of non-interactive zero-knowledge proof of knowledge, and provide an efficient DV-PoK scheme as a central technical building block of our protocol. The DV-PoK scheme possesses nice properties such as unforgeability and symmetry which help our protocol to achieve perfect forward secrecy and full deniability respectively. Moreover, the security properties are formally proved in the Canetti-Krawczyk model under the Gap Diffie-Hellman assumption. In sum, our protocol offers a remarkable combination of salient security properties and efficiency, and the notion of DV-PoK is of independent interests.

We consider the task of constructing interactive proofs for NP which can provide meaningful security for a prover even in the presence of continual memory leakage. We imagine a setting where an adversarial verifier participates in multiple sequential interactive proof executions for a fixed NP statement x. In every execution, the adversarial verifier is additionally allowed to leak a fraction of the (secret) memory of the prover. This is in contrast to the recently introduced notion of leakage-resilient zero-knowledge (Garg-Jain-Sahai'11) where there is only a single execution. Under multiple executions, in fact the entire prover witness might end up getting leaked thus leading to a complete compromise of prover security. Towards that end, we define the notion of non-transferable proofs for all languages in NP. In such proofs, instead of receiving w as input, the prover will receive an "encoding'' of the witness w such that the encoding is sufficient to prove the validity of x; further, this encoding can be "updated'' to a fresh new encoding for the next execution. We then require that if (x,w) are sampled from a "hard'' distribution, then no PPT adversary A* can gain the ability to prove x (on its own) to an honest verifier, even if A* has participated in polynomially many interactive proof executions (with leakage) with an honest prover whose input is (x,w). Non-transferability is a strong security guarantee which suffices for many cryptographic applications (and in particular, implies witness hiding). We show how to construct non-transferable proofs for all languages in NP which can tolerate leaking a constant fraction of prover's secret-state during each execution. Our construction is in the common reference string (CRS) model. To obtain our results, we build a witness-encoding scheme which satisfies the following continual-leakage-resilient (CLR) properties: - The encodings can be randomized to yield a fresh new encoding, - There does not exist any efficient adversary, who receiving only a constant fraction of leakage on polynomially many fresh encodings of the same witness w, can output a valid encoding provided that the witness w along with its corresponding input instance x were sampled from a hard distribution. Our encoding schemes are essentially re-randomizable non-interactive zero-knowledge (NIZK) proofs for circuit satisfiability, with the aforementioned CLR properties. We believe that our CLR-encodings, as well as our techniques to build them, may be of independent interest.

In a Password-Protected Secret Sharing (PPSS) scheme with parameters (t,n) (formalized by Bagherzandi et al), a user Alice stores secret information s among n servers so that she can later recover the information solely on the basis of her password. The security requirement is similar to a (t,n)-threshold secret sharing, i.e., Alice can recover her secret as long as she can communicate with t + 1 honest servers but an attacker gaining access to t servers cannot learn information about the secret. In particular, the system is secure against o-line attacks by an attacker controlling up to t servers. On the other hand, accounting for inevitable on-line attacks one allows the attacker an advantage proportional to the fraction of dictionary passwords tested in on-line interactions with the user and servers. We present the first round-optimal PPSS scheme, requiring just one message from user to server, and from server to user, and that works in the password-only setting where users do not have access to an authenticated public key. The scheme uses an Oblivious PRF whose security we define using a UC-style ideal functionality and denote as V-OPRF due to its verifiability, and for which we show concrete, very practical realizations in the random oracle model, as well as standard-model instantiations. As an important application we use this scheme to build the first single-round password-only Threshold-PAKE protocol in the CRS and ROM models for arbitrary (t,n) parameters with no PKI requirements for any party (clients or servers) and no inter-server communication. Our T-PAKE protocols are built by combining suitable key exchange protocols on top of our V-OPRF-based PPSS schemes. We prove T-PAKE security via a generic composition theorem showing the security of any such composed protocol.

We construct the first schemes that allow a client to privately outsource arbitrary program executions to a remote server while ensuring that: (I) the client's work is small and essentially independent of the complexity of the computation being outsourced, and (II) the server's work is only proportional to the run-time of the computation on a random access machine (RAM), rather than its potentially much larger circuit size. Furthermore, our solutions are non-interactive and have the structure of reusable garbled RAM programs, addressing an open question of Lu and Ostrovsky (Eurocrypt 2013). We also construct schemes for an augmented variant of the above scenario, where the client can initially outsource a large private and persistent database to the server, and later outsource arbitrary program executions with read/write access to this database. Our solutions are built from non-reusable garbled RAM in conjunction with new types of reusable garbled circuits that are more efficient than prior solutions but only satisfy weaker security. For the basic setting without a persistent database, we can instantiate the required reusable garbled circuits using indistinguishability obfuscation. For the more complex setting with a persistent database we need stronger notions of obfuscation. Our basic solution also requires the client to perform a one-time preprocessing step to garble a program at the cost of its RAM run-time, and we can avoid this cost using stronger notions of obfuscation. It remains an open problem to instantiate these new types of reusable garbled circuits under weaker assumptions, possibly avoiding obfuscation altogether.

Garg, Jain, and Sahai first consider zero knowledge proofs in the presence of leakage on the local state of the prover, and present a leakage-resilient-zero-knowledge proof system for HC (Hamiltonian Cycle) problem. Their construction is called $(1+\varepsilon)$-leakage-resilient zero-knowledge, for any constant $\varepsilon>0$, because the total length of the leakage the simulator needs is $(1+\varepsilon)$ times as large as that of the leakage received by the verifier. In recent, Pandey provides a constant-round leakage-resilient zero-knowledge argument satisfying the ideal requirement of $\varepsilon=0$. Whether there exist constant round leakage-resilient zero-knowledge arguments of knowledge for all NP languages is an interesting problem. This paper focuses on this problem and presents a constant-round construction of leakage-resilient zero-knowledge arguments of knowledge for the HC problem.

The traditional setting for concurrent zero knowledge considers a server that proves a statement in zero-knowledge to multiple clients in multiple concurrent sessions, where the server's actions in a session are independent of all other sessions. Persiano and Visconti [ICALP 05] show how keeping a limited amount of global state across sessions allows the server to significantly reduce the overall complexity while retaining the ability to interact concurrently with an unbounded number of clients. Specifically, they show a protocol that has only slightly super-constant number of rounds; however the communication complexity in each session of their protocol depends on the number of other sessions and has no a priori bound. This has the drawback that the client has no way to know in advance the amount of resources required for completing a session of the protocol up to the moment where the session is completed. We show a protocol that does not have this drawback. Specifically, in our protocol the client obtains a bound on the communication complexity of each session at the start of the session. Additionally the protocol is constant-rounds. Our protocol is fully concurrent, and assumes only collision-resistant hash functions. The proof requires considerably different techniques than those of Persiano and Visconti. Our main technical tool is an adaptation of the "committed-simulator" technique of Deng et. al [FOCS 09].

We present oblivious implementations of several data structures for secure multiparty computation (MPC) such as arrays, dictionaries, and priority queues. The resulting oblivious data structures have only polylogarithmic overhead compared with their classical counterparts. To achieve this, we give secure multiparty protocols for the ORAM of Shi et al. (Asiacrypt `11) and the Path ORAM scheme of van Dijk et al. (CCS `13), and we compare the resulting implementations. We subsequently use our oblivious priority queue for secure computation of Dijkstra's shortest path algorithm on general graphs, where the graph structure is secret. To the best of our knowledge, this is the first implementation of a non-trivial graph algorithm in multiparty computation with polylogarithmic overhead. We implemented and benchmarked all of our protocols using the SPDZ protocol of Damgaard et al. (Crypto `12), which works in the preprocessing model and ensures active security against an adversary corrupting all but one players. For two parties, the access time for an oblivious array of size 1 million is under 250 ms.

Verifiable computation (VC) enables thin clients to efficiently verify the computational results produced by a powerful server. Although VC was initially considered to be mainly of theoretical interest, over the last two years, impressive progress has been made on implementing VC. Specifically, we now have open-source implementations of VC systems that can handle all classes of computations expressed either as circuits or in the RAM model. However, despite this very encouraging progress, new enhancements in the design and implementation of VC protocols are required in order to achieve truly practical VC for real-world applications. In this work, we show that for functionalities that can be expressed efficiently in terms of set operations (e.g., a subset of SQL queries) VC can be enhanced to become drastically more practical: we present the design and prototype implementation of a novel VC scheme that achieves orders of magnitude speed-up in comparison with the state of the art. Specifically, we build and evaluate TRUESET, a system that can verifiably compute any polynomial-time function expressed as a circuit consisting of \set gates" such as union, intersection, difference and set cardinality. Moreover, TRUESET supports hybrid circuits consisting of both set gates and traditional arithmetic gates. Therefore, it does not lose any of the expressiveness of the previous schemes|this also allows the user to choose the most efficient way to represent different parts of a computation. By expressing set computations as polynomial operations and introducing a novel Quadratic Polynomial Program technique, TRUESET achieves prover performance speed-up ranging from 30x to 150x and yields up to 97% evaluation key size reduction.

A threshold password-authenticated key exchange (T-PAKE) protocol allows a set of n servers to collectively authenticate a client with a human-memorizable password such that any subset of size greater than a threshold t can authenticate the client, while smaller subsets of servers learn no information about the password. With its protection against offline dictionary attacks, T-PAKE provides a practical solution for an important real-life problem with password authentication. However, the proposed T-PAKE constructions cannot tolerate any misbehavior---not even a crash---by a participating server during a protocol execution; the protocol has to be re-executed until all participating servers behave correctly. This not only presents a fault management challenge for the servers, but more importantly also can leave the clients frustrated for being denied access even after entering a correct password. In this work, we present a novel T-PAKE protocol which solves the above fault management problem by employing a batched and offline phase of distributed key generation (DKG). Our protocol is secure against any malicious behavior from up to any t < n servers under the decisional Diffie-Hellman assumption in the random oracle model, and it ensures protocol completion for t < n/2. Moreover, it is efficient (16n + 7 exponentiations per client, 20n + 14 per server), performs explicit authentication in three communication rounds, and requires a significantly lesser number of broadcast rounds compared to previous secure T-PAKE constructions. We have implemented our protocol, and have verified its efficiency using micro-benchmark experiments. Our experimental results show that the protocol only introduces a computation overhead of few milliseconds at both the client and the server ends, and it is practical for use in real-life authentication scenarios.

Membership encryption is a newly developed cryptographic primitive that combines membership proof and encryption into an unified setting. This paper presents a new flexible membership encryption scheme which is provably secure and significantly more efficient than the previous scheme. Further we apply our proposed membership encryption to construct a round optimal 1-out-of-$n$ priced oblivious transfer (POT) protocol which, unlike the existing 1-out-of-n POT schemes,is proven secure under the universally composable (UC) security model and thus preserves security when it is executed with multiple protocol instances that run concurrently in an adversarily controlled way. Moreover, using our membership encryption, the POT protocol exhibits constant communication complexity on the buyer's side and $O(n)$ communication cost on the vendor's side, which is so far the best known in the literature.

Private set intersection (PSI) allows two parties to compute the intersection of their sets without revealing any information about items that are not in the intersection. It is one of the best studied applications of secure computation and many PSI protocols have been proposed. However, the variety of existing PSI protocols makes it difficult to identify the solution that performs best in a respective scenario, especially since they were not all implemented and compared in the same setting. In this work, we give an overview on existing PSI protocols that are secure against semi-honest adversaries. We take advantage of the most recent efficiency improvements in OT extension to propose significant optimizations to previous PSI protocols and to suggest a new PSI protocol whose runtime is superior to that of existing protocols. We compare the performance of the protocols both theoretically and experimentally, by implementing all protocols on the same platform, and give recommendations on which protocol to use in a particular setting.

We define a notion of semantic security of multilinear (a.k.a. graded) encoding schemes, which stipulates security of class of algebraic ``decisional'' assumptions: roughly speaking, we require that for every nuPPT distribution $D$ over two \emph{constant-length} sequences $\vec{m}_0,\vec{m}_1$ and auxiliary elements $\vec{z}$ such that all arithmetic circuits (respecting the multilinear restrictions and ending with a zero-test) are \emph{constant} with overwhelming probability over $(\vec{m}_b, \vec{z})$, $b \in \{0,1\}$, we have that encodings of $\vec{m}_0, \vec{z}$ are computationally indistinguishable from encodings of $\vec{m}_1, \vec{z}$. Assuming the existence of semantically secure multilinear encodings and the LWE assumption, we demonstrate the existence of indistinguishability obfuscators for all polynomial-size circuits. We additionally show that if we assume subexponential hardness, then it suffices to consider a \emph{single} (falsifiable) instance of semantical security (i.e., that semantical security holds w.r.t to a particular distribution $D$) to obtain the same result. We rely on the beautiful candidate obfuscation constructions of Garg et al (FOCS'13), Brakerski and Rothblum (TCC'14) and Barak et al (EuroCrypt'14) that were proven secure only in idealized generic multilinear encoding models, and develop new techniques for demonstrating security in the standard model, based only on semantic security of multilinear encodings (which trivially holds in the generic multilinear encoding model). We also investigate various ways of defining an ``uber assumption'' (i.e., a super-assumption) for multilinear encodings, and show that the perhaps most natural way of formalizing the assumption that ``any algebraic decision assumption that holds in the generic model also holds against nuPPT attackers'' is false.

An extended permutation is a function f : {1,...,m} -> {1,...,n}, used to map an n-element vector a to an m-element vector b by b_i = a_{f(i)}. An oblivious extended permutation allows this mapping to be done while preserving the privacy of a, b and f in a secure multiparty computation protocol. Oblivious extended permutations have several uses, with private function evaluation (PFE) being the theoretically most prominent one. In this paper, we propose a new technique for oblivious evaluation of extended permutations. Our construction is at least as efficient as the existing techniques, conceptually simpler, and has wider applicability. Our technique allows the party providing the description of f to be absent during the computation phase of the protocol. Moreover, that party does not even have to exist - we show how to compute the private representation of f from private data that may itself be computed from the inputs of parties. In other words, our oblivious extended permutations can be freely composed with other privacy-preserving operations in a multiparty computation.

In recent years, \emph{lattice-based} cryptography has been recognized for its many attractive properties, such as strong provable security guarantees and apparent resistance to quantum attacks, flexibility for realizing powerful tools like fully homomorphic encryption, and high asymptotic efficiency. Indeed, several works have demonstrated that for basic tasks like encryption and authentication, lattice-based primitives can have performance competitive with (or even surpassing) those based on classical mechanisms like RSA or Diffie-Hellman. However, there still has been relatively little work on developing lattice cryptography for deployment in \emph{real-world} cryptosystems and protocols. In this work we take a step toward that goal, by giving efficient and practical lattice-based protocols for key transport, encryption, and authenticated key exchange that are suitable as ``drop-in'' components for proposed Internet standards and other open protocols. The security of all our proposals is provably based (sometimes in the random-oracle model) on the well-studied ``learning with errors over rings'' problem, and hence on the conjectured worst-case hardness of problems on ideal lattices (against quantum algorithms). One of our main technical innovations (which may be of independent interest) is a simple, low-bandwidth \emph{reconciliation} technique that allows two parties who ``approximately agree'' on a secret value to reach \emph{exact} agreement, a setting common to essentially all lattice-based encryption schemes. Our technique reduces the ciphertext length of prior (already compact) encryption schemes nearly twofold, at essentially no cost.

Several papers have studied fault attacks on computing a pairing value e(P,Q), where P is a public point and Q is a secret point. In this paper, we observe that these attacks are in fact effective only on a small number of pairing-based protocols, and that too only when the protocols are implemented with specific symmetric pairings. We demonstrate the effectiveness of the fault attacks on a public-key encryption scheme, an identity-based encryption scheme, and an oblivious transfer protocol when implemented with a symmetric pairing derived from a supersingular elliptic curve with embedding degree 2.

Attacks on cryptographic protocols are usually modeled by allowing an adversary to ask queries to an oracle. Security is then defined by requiring that as long as the queries satisfy some constraint, there is some problem the adversary cannot solve, such as compute a certain piece of information. Even if the protocol is quantum, the queries are typically classical, such as a choice of subset of players to corrupt. In this paper, we introduce a fundamentally new model of quantum attacks on protocols, where the adversary is allowed to ask several classical queries in quantum superposition. This is a strictly stronger attack than the standard one, and we consider the security of several primitives in this model. We show that a secret-sharing scheme that is secure with threshold $t$ in the standard model is secure against superposition attacks if and only if the threshold is lowered to $t/2$. This holds for all classical as well as a large class of quantum secret sharing schemes. We then consider zero-knowledge and first show that known protocols are not, in general, secure in our model by designing a superposition attack on the well-known zero-knowledge protocol for graph isomorphism. We then use our secret-sharing result to design zero-knowledge proofs for all of NP in the common reference string model. While our protocol is classical, it is sound against a cheating unbounded quantum prover and computational zero-knowledge even if the verifier is allowed a superposition attack. Finally, we consider multiparty computation and give a characterization of a class of protocols that can be shown secure, though not necessarily with efficient simulation. We show that this class contains non-trivial protocols that cannot be shown secure by running a classical simulator in superposition.

We show a construction of a quantum ramp secret sharing scheme from a nested pair of linear codes. Necessary and sufficient conditions for qualified sets and forbidden sets are given in terms of combinatorial properties of nested linear codes. An algebraic geometric construction for quantum secret sharing is also given.

Group signatures are cryptographic primitives where users can anonymously sign messages in the name of a population they belong to. Gordon et al. (Asiacrypt 2010) suggested the first realization of group signatures based on lattice assumptions in the random oracle model. A significant drawback of their scheme is its linear signature size in the cardinality $N$ of the group. A recent extension proposed by Camenisch et al. (SCN 2012) suffers from the same overhead. In this paper, we describe the first lattice-based group signature schemes where the signature and public key sizes are essentially logarithmic in $N$ (for any fixed security level). Our basic construction only satisfies a relaxed definition of anonymity (just like the Gordon et al. system) but readily extends into a fully anonymous group signature (i.e., that resists adversaries equipped with a signature opening oracle). We prove the security of our schemes in the random oracle model under the SIS and LWE assumptions.

Secure two-party computation allows two mutually distrusting parties to jointly compute an arbitrary function on their private inputs without revealing anything but the result. An interesting target for deploying secure computation protocols are mobile devices as they contain a lot of sensitive user data. However, their resource restriction makes the deployment of secure computation protocols a challenging task. In this work, we optimize and implement the secure computation protocol by Goldreich-Micali-Wigderson (GMW) on mobile phones. To increase performance, we extend the protocol by a trusted hardware token (i.e., a smartcard). The trusted hardware token allows to pre-compute most of the workload in an initialization phase, which is executed locally on one device and can be pre-computed independently of the later communication partner. We develop and analyze a proof-of-concept implementation of generic secure two-party computation on Android smart phones making use of a microSD smartcard. Our use cases include private set intersection for finding shared contacts and private scheduling of a meeting with location preferences. For private set intersection, our token-aided implementation on mobile phones is up to two orders of magnitude faster than previous generic secure two-party computation protocols on mobile phones and even as fast as previous work on desktop computers.

Two parties, $P_1$ and $P_2$, wish to jointly compute some function $f(x,y)$ where $P_1$ only knows $x$, whereas $P_2$ only knows $y$. Furthermore, and most importantly, the parties wish to reveal only what the output suggests. Function $f$ is said to be computable with \emph{complete fairness} if there exists a protocol computing $f$ such that whenever one of the parties obtains the correct output, then both of them do. The only protocol known to compute functions with complete fairness is the one of Gordon et al (STOC 2008). The functions in question are finite, Boolean, and the output is shared by both parties. The classification of such functions up to fairness may be a first step towards the classification of all functionalities up to fairness. Recently, Asharov (TCC 2014) identifies two families of functions that are computable with fairness using the protocol of Gordon et al and another family for which the protocol (potentially) falls short. Surprisingly, these families account for almost all finite Boolean functions. In this paper, we expand our understanding of what can be computed fairly with the protocol of Gordon et al. In particular, we fully describe which functions the protocol computes fairly and which it (potentially) does not. Furthermore, we present a new class of functions for which fair computation is outright impossible. Finally, we confirm and expand Asharov's observation regarding the fairness of finite Boolean functions: almost all functions $f:X\times Y\rightarrow \{0,1\}$ for which $|X|\neq |Y|$ are fair, whereas almost all functions for which $|X|= |Y|$ are not.

We present a secure honest majority MPC protocol, against a static adversary, which aims to reduce the communication cost in the situation where there are a large number of parties and the number of adversarially controlled parties is relatively small. Our goal is to reduce the usage of point-to-point channels among the parties, thus enabling them to run multiple different protocol executions. Our protocol has highly efficient theoretical communication cost when compared with other protocols in the literature; specifically the circuit-dependent communication cost, for circuits of suitably large depth, is $\Order(|\Circuit|\kappa^7)$, for security parameter $\kappa$~and circuit size $|\Circuit|$. Our protocol finds application in cloud computing scenario, where the fraction of corrupted parties is relatively small. By minimizing the usage of point-to-point channels, our protocol can enable a cloud service provider to run multiple MPC protocols.

In this paper, we address the problem of privacy preserving delegated word search in the cloud. We consider a scenario where a data owner outsources its data to a cloud server and delegates the search capabilities to a set of third party users. In the face of semi-honest cloud servers, the data owner does not want to disclose any information about the outsourced data; yet it still wants to benefit from the highly parallel cloud environment. In addition, the data owner wants to ensure that delegating the search functionality to third parties does not allow these third parties to jeopardize the confidentiality of the outsourced data, neither does it prevent the data owner from efficiently revoking the access of these authorized parties. To these ends, we propose a word search protocol that builds upon techniques of keyed hash functions, oblivious pseudo-random functions and Cuckoo hashing to construct a searchable index for the outsourced data, and uses private information retrieval of short information to guarantee that word search queries do not reveal any information about the data to the cloud server. Moreover, we combine attribute-based encryption and oblivious pseudo-random functions to achieve an efficient revocation of authorized third parties. The proposed scheme is suitable for the cloud as it can be easily parallelized.

With relatively few exceptions, the literature on efficient (practical) secure computation has focused on secure two-party computation (2PC). It is, in general, unclear whether the techniques used to construct practical 2PC protocols - in particular, the cut-and-choose approach - can be adapted to the multi-party setting. In this work we explore the possibility of using cut-and-choose for practical secure three-party computation. The three-party case has been studied in prior work in the semi-honest setting, and is motivated by the observation that real-world deployments of multi-party computation are likely to involve few parties. We propose a constant-round protocol for three-party computation tolerating any number of malicious parties, whose computational cost is essentially only a small constant worse than that of state-of-the-art two-party protocols.

We introduce EyeDecrypt, a novel technology for privacy-preserving human-computer interaction. EyeDecrypt allows only authorized users to decipher data shown on a display, such as an electronic screen or plain printed material; in the former case, the authorized user can then interact with the system (e.g., by pressing buttons on the screen), without revealing the details of the interaction to others who may be watching or to the system itself. The user views the decrypted data on a closely-held personal device, such as a pair of smart glasses with a camera and heads-up display, or a smartphone. The data is displayed as an image overlay on the personal device, which we assume cannot be viewed by the adversary. The overlay is a form of augmented reality that not only allows the user to view the protected data, but also to securely enter input into the system by randomizing the input interface. EyeDecrypt consists of three main components: a visualizable encryption scheme; a dataglyph-based visual encoding scheme for the ciphertexts generated by the encryption scheme; and a randomized input and augmented reality scheme that protects user inputs without harming usability. We describe all aspects of EyeDecrypt, from security definitions, constructions and analysis, to implementation details of a prototype developed on a smartphone.

One of the interesting types of RFID application is RFID searching which aims to hear a specific RFID tag from a large group of tags, i.e. ability of detecting whether a target RFID tag is nearby. Very recently, a lightweight protocol using error-correcting codes has been proposed by Chen et al. to provide a solution to needs in this field. The authors give a detailed analysis of their protocol in terms of security, privacy, communication overhead, hardware cost and they claim that it is a realizable scheme with fulfilling security and privacy requirements. In this study, however, we investigate security of this protocol and clearly demonstrate its security flaws that completely allow an adversary to exploit the system. In particular, by using linear properties of error correcting coding we firstly describe a tag tracing attack that undermines untraceability property which is one its design objectives. Then along with its implementation details we present a key recovery attack that reduces dramatically search space of a tag's secret key and show that an adversary can compromise it in practical time by only querying this tag for several times. As an illustrative example we retrieve the secret key of the protocol in two hours for the adopted linear block code C(47,24,11) which is one of the suggested codes.

Privacy-enhancing attribute-based credentials (PABCs) allow users to authenticate to verifiers in a data-minimizing way, in the sense that users are unlinkable between authentications and only disclose those attributes from their credentials that are relevant to the verifier. We propose a practical scheme to apply the same data minimization principle when the verifiers’ authentication logs are subjected to external audits. Namely, we propose an extended PABC scheme where the verifier can further remove attributes from presentation tokens before handing them to an auditor, while preserving the verifiability of the audited tokens. We present a generic construction based on a signature, a signature of knowledge and a trapdoor commitment scheme, prove it secure in the universal composability framework, and give efficient instantiations based on the strong RSA and Decision Composite Residuosity (DCR) assumptions in the random-oracle model.

Multiparty computation (MPC) among n parties can tolerate up to t<n/2 active corruptions in a synchronous communication setting; however, in an asynchronous communication setting, the resiliency bound decreases to only t<n/3 active corruptions. We improve the resiliency bound for asynchronous MPC (AMPC) to match synchronous MPC using non-equivocation. Non-equivocation is a message authentication mechanism to restrict a corrupted sender from making conflicting statements to different (honest) parties. It can be implemented using an increment-only counter and a digital signature oracle, realizable with trusted hardware modules readily available in commodity computers and smartphone devices. A non-equivocation mechanism can also be transferable and allow a receiver to verifiably transfer the authenticated statement to other parties. In this work, using transferable non-equivocation, we present an AMPC protocol tolerating t<n/2 faults. From a practical point of view, our AMPC protocol requires fewer setup assumptions than the previous AMPC protocol with t<n/2 by Beerliovä-Trub\'ıniovä, Hirt and Nielsen [PODC 2010]: unlike their AMPC protocol, it does not require any synchronous broadcast round at the beginning of the protocol and avoids the threshold homomorphic encryption setup assumption. Moreover, our AMPC protocol is also efficient and provides a gain of \Theta(n) in the communication complexity per multiplication gate, over the AMPC protocol of Beerliovä-Trub\'ıniovä et al. In the process, using non-equivocation, we also define the first asynchronous verifiable secret sharing (AVSS) scheme with t<n/2, which is of independent interest to threshold cryptography.

Most implementations of Yao's garbled circuit approach for 2-party secure computation use the {\em free-XOR} optimization of Kolesnikov \& Schneider (ICALP 2008). We introduce an alternative technique called {\em flexible-XOR} (fleXOR) that generalizes free-XOR and offers several advantages. First, fleXOR can be instantiated under a weaker hardness assumption on the underlying cipher/hash function (related-key security only, compared to related-key and circular security required for free-XOR) while maintaining most of the performance improvements that free-XOR offers. Alternatively, even though XOR gates are not always ``free'' in our approach, we show that the other (non-XOR) gates can be optimized more heavily than what is possible when using free-XOR. For many circuits of cryptographic interest, this can yield a significantly (over 30\%) smaller garbled circuit than any other known techniques (including free-XOR) or their combinations.

We propose a new protocol for a cryptocurrency, that builds upon the Bitcoin protocol by combining its Proof of Work component with a Proof of Stake type of system. Our Proof of Activity (PoA) protocol offers good security against possibly practical future attacks on Bitcoin, and has a relatively low penalty in terms of network communication and storage space. We explore various attack scenarios and suggest remedies to potential vulnerabilities of the PoA protocol, as well as evaluate the performance of its core subroutine.

Performance of secure computation is still often an obstacle to its practical adaption. There are different protocols for secure computation that compete for the best performance. In this paper we propose automatic protocol selection which selects a protocol for each operation resulting in a mix with the best performance so far. Based on an elaborate performance model, we propose an optimization algorithm and an efficient heuristic for this selection problem. We show that our mixed protocols achieve the best performance on a set of use cases. Furthermore, our results underpin that the selection problem is so complicated and large in size, that a programmer is unlikely to manually make the optimal selection. Our proposed algorithms nevertheless can be integrated into a compiler in order to yield the best (or near-optimal) performance.

Non-interactive verifiable outsourced computation enables a computationally weak client to outsource the computation of a function $f$ on input $x$ to a more powerful but untrusted server, who will return the result of the function evaluation as well as a proof that the computation is performed correctly. A basic requirement of a verifiable outsourced computation scheme is that the client should invest less time in preparing the inputs and verifying the proof than computing the function by himself. One of the best solutions of such non-interactive schemes are based on Yao's garble circuit and full homomorphic encryption, which leads to invest $poly(T)$ running time in offline stage and $poly(log T)$ time in online stage of the client, where $T$ is the time complexity to compute $f$. In this paper, we'll present a scheme which does not need to use garble circuit, but to use a very simple technique to confuse the function we are going to compute, and only invests $poly(log T)$ running time in the offline stage.

Passwords are inherently vulnerable to dictionary attacks, but are quite secure if guessing attempts can be slowed down, for example by an online server. If this server gets compromised, however, the attacker can again perform an offline attack. The obvious remedy is to distribute the password verification process over multiple servers, so that the password remains secure as long as no more than a threshold of the servers are compromised. By letting these servers additionally host shares of a strong secret that the user can recover upon entering the correct password, the user can perform further cryptographic tasks using this strong secret as a key, e.g., encrypting data in the cloud. Threshold password-authenticated secret sharing (TPASS) protocols provide exactly this functionality, but the two only known schemes by Bagherzandi et al. (CCS 2011) and Camenisch et al. (CCS 2012) leak the password if a user mistakenly executes the protocol with malicious servers. Authenticating to the wrong servers is a common scenario when users are tricked in phishing attacks. We propose the first t-out-of-n TPASS protocol for any n > t that does not suffer from this shortcoming. We prove our protocol secure in the UC framework, which for the particular case of password-based protocols offers important advantages over property-based definitions, e.g., by correctly modeling typos in password attempts.

Oblivious RAM (ORAM) has received increasing attention in the past few years. The goal of oblivious RAM is to enable a client, that can locally store only a small (preferably constant) amount of data, to store remotely N data items, and access them while hiding the identities of the items that are being accessed. Most of the earlier ORAM constructions were based on the hierarchical data structure of Goldreich and Ostrovsky. Shi et al. introduced a binary tree ORAM, which is simpler and more efficient than the classical hierarchical ORAM. Gentry et al. have improved the scheme. In this work, we improve these two constructions. Our scheme asymptotically outperforms all previous tree based ORAM schemes that have constant client memory, with an overhead of O(log^{2+eps}(N) * log^2(log(N))) per operation for a O(N) storage server. Although the best known asymptotic result for ORAM is due to the hierarchical structure of Kushilevitz et al. (O(log^2(N)/log(log(N)))), tree based ORAM constructions are much simpler

Oblivious RAM (ORAM) is a cryptographic primitive that hides memory access patterns to untrusted storage. ORAM may be used in secure processors for encrypted computation and/or software protection. While recursive Path ORAM is currently the most practical ORAM for secure processors, it still incurs large performance and energy overhead and is the performance bottleneck of recently proposed secure processors. In this paper, we propose two optimizations to recursive Path ORAM. First, we identify a type of program locality in its operations to improve performance. Second, we use pseudorandom function to compress the position map. But applying these two techniques in recursive Path ORAM breaks ORAM security. To securely take advantage of the two ideas, we propose unified ORAM. Unified ORAM improves performance both asymptotically and empirically. Empirically, our experiments show that unified ORAM reduces data movement from ORAM by half and improves benchmark performance by 61% as compared to recursive Path ORAM.

We extend the Tiny-OT two party protocol of Nielsen et al (CRYPTO 2012) to the case of $n$ parties in the dishonest majority setting. This is done by presenting a novel way of transferring pairwise authentications into global authentications. As a by product we obtain a more efficient manner of producing globally authenticated shares, which in turn leads to a more efficient two party protocol than that of Nielsen et al.

We are interested in secure computation protocols in settings where the number of parties is huge and their data even larger. Assuming the existence of a single-use broadcast channel (per player), we demonstrate statistically secure computation protocols for computing (multiple) arbitrary dynamic RAM programs over parties' inputs, handling (1/3-eps) fraction static corruptions, while preserving up to polylogarithmic factors the computation and memory complexities of the RAM program. Additionally, our protocol is load balanced and has polylogarithmic communication locality.

Secure multiparty computation systems are commonly built form a small set of primitive components. Composability of security notions has a central role in the analysis of such systems, since it allows us to deduce security properties of complex protocols from the properties of its components. We show that the standard notions of universally composable security are overly restrictive in this context and can lead to protocols with sub-optimal performance. As a remedy, we introduce a weaker notion of privacy that is satisfied by simpler protocols and is preserved by composition. After that we fix a passive security model and show how to convert a private protocol into a universally composable protocol. As a result, we obtain modular security proofs without performance penalties.

We use various laws of classical physics to offer several solutions of Yao's millionaires' problem without using any one-way functions. We also describe several informationally secure public key encryption protocols, i.e., protocols secure against passive computationally unbounded adversary. This introduces a new paradigm of decoy-based cryptography, as opposed to ``traditional" complexity-based cryptography. In particular, our protocols do not employ any one-way functions.

State-of-the-art authenticated key exchange (AKE) protocols are proven secure in game-based security models. These models have considerably evolved in strength from the original Bellare-Rogaway model. However, so far only informal impossibility results, which suggest that no protocol can be secure against stronger adversaries, have been sketched. At the same time, there are many different security models being used, all of which aim to model the strongest possible adversary. In this paper we provide the first systematic analysis of the limits of game-based security models. Our analysis reveals that different security goals can be achieved in different relevant classes of AKE protocols. From our formal impossibility results, we derive strong security models for these protocol classes and give protocols that are secure in them. In particular, we analyse the security of AKE protocols in the presence of adversaries who can perform attacks based on chosen randomness, in which the adversary controls the randomness used in protocol sessions. Protocols that do not modify memory shared among sessions, which we call stateless protocols, are insecure against chosen-randomness attacks. We propose novel stateful protocols that provide resilience even against this worst case randomness failure, thereby weakening the security assumptions required on the random number generator.

A three-factor authentication combines biometrics information with user password and smart card to provide security-enhanced user authentication. An proposed user authentication scheme improved Das’s scheme. But An’s scheme is not secure against denial of service attack in login phase, forgery attack. Li et al. pointed out them and proposed three-factor remote user authentication scheme with key agreement. However, Li et al’s scheme still has some security problem. In this paper, we present a cryptanalysis and improvement of Li et al.’s remote user authentication scheme.

All known protocols implementing broadcast from synchronous point-to-point channels tolerating any $t < n$ Byzantine corruptions have communication complexity at least $\Omega(\ell n^2)$. We give cryptographically secure and information-theoretically secure protocols for $t < n$ that communicate $O(\ell n)$ bits in order to broadcast sufficiently long $\ell$ bit messages. This matches the optimal communication complexity bound for any protocol allowing to broadcast $\ell$ bit messages. While broadcast protocols with the optimal communication complexity exist in cases where $t < n/3$ (by Liang and Vaidya in PODC '11) or $t < n/2$ (by Fitzi and Hirt in PODC '06), this paper is the first to present such protocols for $t < n$.

Most existing symmetric searchable encryption schemes aim at allowing a user to outsource her encrypted data to a cloud server and delegate the latter to search on her behalf. These schemes do not qualify as a secure and scalable solution for the multi-party setting, where users outsource their encrypted data to a cloud server and selectively authorize each other to search. Due to the possibility that the cloud server may collude with some malicious users, it is a challenge to have a secure and scalable multi-party searchable encryption (MPSE) scheme. This is shown by our analysis on the Popa-Zeldovich scheme, which says that an honest user may leak all her search patterns even if she shares only one of her documents with another malicious user. Based on our analysis, we present a new security model for MPSE by considering the worst-case and average-case scenarios, which capture different server-user collusion possibilities. We then propose a MPSE scheme by employing the bilinear property of Type-3 pairings, and prove its security based on the Bilinear Diffie-Hellman Variant (BDHV) and Symmetric eXternal Diffie-Hellman (SXDH) assumptions in the random oracle model.

In this paper, we review three problematic key management(KM) schemes recently proposed, including Kayam’s scheme for groups with hierarchy [9], Piao’s group KM scheme [13], Purushothama’s group KM schemes [15]. We point out the problems in each scheme. Kayam’s scheme is not secure to collusion attack. Piao’s group KM scheme is not secure and has a bad primitive. The hard problem it bases is not really hard. Purushothama’s scheme has a redundant design that costs lots of resources and doesn’t give an advantage to the security evel and dynamic efficiency of it. We also briefly analyze the underlying reasons why these problem emerge.

The hierarchical access control scheme based on Chinese Reminder Theorem [49] (CRTHACS) was supposed to be capable of hiding hierarchical structure, but Geiselmann et al. [18] showed practical attacks on CRTHACS to reveal the hierarchies it hides. Then, Zou et al. modified it, and gave a new CRTHACS [50] to resist those attacks. Nevertheless, we find that the modified version is still defective if it permits changes of structure, i.e. the scheme works in a dynamic scenario. In this paper, we describe our attack on the modified version of CRTHACS. We extend the description of the CRTHACS in a more proper form making it easier for us to look into the problem it has. We find the key character of the vulnerability which we name as double-invariance. We generalize our attack in an algebraic form and apply it to a series of hierarchical cryptographic access control schemes that share the same vulnerability with CRTHACS. We also give the countermeasure to fix this vulnerability.

One of the most well known micropayment scheme is the PayWord scheme. It is designed to be onevendor, so if we apply it for multiple vendors, it does not protect against double spending. We extended the PayWord scheme, it supports shopping at multiple vendors without an on-line broker or an on-line secure database. The proposed credit-based system uses one hash chain, hence besides the secret signature key only the seed and a random value should be securely stored. Our scheme is analyzed in applied pi calculus, we prove that it fulfills payment approval, secure payment authorization, secrecy of payment information and unreusability.

This paper combines cryptographic voting and web page ranking and proves that it is possible to hold elections so as not to limit a voter by a list of candidates, to benefit from voter's personal experience in dealing with people, to make wide and proportional representation, and to achieve secrecy, including incoercibility, and verifiability of cryptographic voting systems.

Smooth projective hash functions have been used as building block for various cryptographic applications, in particular for password-based authentication. In this work we propose the extended concept of distributed smooth projective hash functions where the computation of the hash value is distributed across $n$ parties and show how to instantiate the underlying approach for languages consisting of Cramer-Shoup ciphertexts. As an application of distributed smooth projective hashing we build a new framework for the design of two-server password authenticated key exchange protocols, which we believe can help to "explain" the design of earlier two-server password authenticated key exchange protocols.

Bitcoin is the first digital currency to see widespread adoption. While payments are conducted between pseudonyms, Bitcoin cannot offer strong privacy guarantees: payment transactions are recorded in a public decentralized ledger, from which much information can be deduced. Zerocoin (Miers et al., IEEE S&P 2013) tackles some of these privacy issues by unlinking transactions from the payment's origin. Yet, it still reveals payments' destinations and amounts, and is limited in functionality. In this paper, we construct a full-fledged ledger-based digital currency with strong privacy guarantees. Our results leverage recent advances in zero-knowledge Succinct Non-interactive ARguments of Knowledge (zk-SNARKs). First, we formulate and construct decentralized anonymous payment schemes (DAP schemes). A DAP scheme enables users to directly pay each other privately: the corresponding transaction hides the payment's origin, destination, and transferred amount. We provide formal definitions and proofs of the construction's security. Second, we build Zerocash, a practical instantiation of our DAP scheme construction. In Zerocash, transactions are less than 1 kB and take under 6 ms to verify --- orders of magnitude more efficient than the less-anonymous Zerocoin and competitive with plain Bitcoin.

Mix nets with randomized partial checking (RPC mix nets) have been introduced by Jakobsson, Juels, and Rivest as particularly simple and efficient verifiable mix nets. These mix nets have been used in several implementations of prominent e-voting systems to provide vote privacy and verifiability. In RPC mix nets, higher efficiency is traded for a lower level of privacy and verifiability. However, these mix nets have never undergone a rigorous formal analysis. Recently, Kahazei and Wikstroem even pointed out several severe problems in the original proposal and in implementations of RPC mix nets in e-voting systems, both for so-called re-encryption and Chaumian RPC mix nets. While Kahazei and Wikstroem proposed several fixes, the security status of Chaumian RPC mix nets (with the fixes applied) has been left open; re-encryption RPC mix nets, as they suggest, should not be used at all. In this paper, we provide the first formal security analysis of Chaumian RPC mix nets. We propose security definitions that allow one to measure the level of privacy and verifiability RPC mix nets offer, and then based on these definitions, carry out a rigorous analysis. Altogether, our results show that these mix nets provide a reasonable level of privacy and verifiability, and that they are still an interesting option for the use in e-voting systems.

We present a general framework for efficient, universally composable oblivious transfer (OT) protocols in which a single, global, common reference string (CRS) can be used for multiple invocations of oblivious transfer by arbitrary pairs of parties. In addition: - Our framework is round-efficient. E.g., under the DLIN or SXDH assumptions we achieve round-optimal protocols with static security, or 3-round protocols with adaptive security (assuming erasure). - Our resulting protocols are more efficient than any known previously, and in particular yield protocols for string OT using O(1) exponentiations and communicating O(1) group elements. Our result improves on that of Peikert et al. (Crypto 2008), which uses a CRS whose length depends on the number of parties in the network and achieves only static security. Compared to Garay et al. (Crypto 2009), we achieve adaptive security with better round complexity and efficiency.

A multiparty computation (MPC) protocol allows a set of players to compute a function of their inputs while keeping the inputs private and at the same time securing the correctness of the output. Most MPC protocols assume that the adversary can corrupt up to a fixed fraction of the number of players. Hirt and Maurer initiated the study of MPC under more general corruption patterns, in which the adversary is allowed to corrupt any set of players in some pre-defined collection of sets [6]. In this paper we consider this important direction of research and present significantly improved communication complexity of MPC protocols for general adversary structures. More specifically, ours is the first unconditionally secure protocol that achieves linear communication in the size of Monotone Span Program representing the adversary structure in the malicious setting against any Q2 adversary structure, whereas all previous protocols were at least cubic.

We show that a recently proposed password authentication scheme based on geometric hashing has several security weaknesses, and that the use of this scheme should be avoided in practice.

We consider unconditionally secure leakage resilient two-party computation, where security means that the leakage obtained by an adversary can be simulated using a similar amount of leakage from the private inputs or outputs. A related problem is known as circuit compilation, where there is only one device doing a computation on public input and output. Here the goal is to ensure that the adversary learns only the input/output behaviour of the computation, even given leakage from the internal state of the device. We study these problems in an enhanced version of the ``only computation leaks'' model, where the adversary is additionally allowed a bounded amount of {\em global} leakage from the state of the entity under attack. In this model, we show the first unconditionally secure leakage resilient two-party computation protocol. The protocol assumes access to correlated randomness in the form of a functionality $\fOrt$ that outputs pairs of orthogonal vectors $(\vec{u}, \vec{v})$ over some finite field, where the adversary can leak independently from $\vec{u}$ and from $\vec{v}$. We also construct a general circuit compiler secure in the same leakage model. Our constructions work, even if the adversary is allowed to corrupt a constant fraction of the calls to $\fOrt$ and decide which vectors should be output. On the negative side, we show that unconditionally secure two-party computation and circuit compilation are in general impossible in the plain version of our model. For circuit compilation we need a computational assumption to exhibit a function that cannot be securely computed, on the other hand impossibility holds even if global leakage is not allowed. It follows that even a somewhat unreliable version of $\fOrt$ cannot be implemented with unconditional security in the plain leakage model, using classical communication. However, we show that an implementation using quantum communication does exist. In particular, we propose a simple ``prepare-and-measure'' type protocol which we show secure using a new result on sampling from a quantum population. Although the protocol may produce a small number of incorrect pairs, this is sufficient for leakage resilient computation by our other results.

This memo describes new cryptographic weakness of the passkey-based pairing of Bluetooth Low Energy (also known as Bluetooth Smart). The vulnerability discussed here extends the set of possible attacking scenarios that were already elaborated before by Mike Ryan at Shmoocon 2013. Instead of the passive sniffing attack on pairing secrets, we show how an active fraudulent Responder can gracefully bypass passkey authentication, despite it being possibly based on even one-time generated PIN.

Privacy-preserving set operations, and set intersection in particular, are a popular research topic. Despite a large body of literature, the great majority of the available solutions are two-party protocols and are not composable. In this work we design a comprehensive suite of secure multi-party protocols for set and multiset operations that are composable, do not assume any knowledge of the sets by the parties carrying out the secure computation, and can be used for secure outsourcing. All of our protocols have communication and computation complexity of $O(m \log m)$ for sets or multisets of size $m$, which compares favorably with prior work. Furthermore, we are not aware of any results that realize composable operations. Our protocols are secure in the information theoretic sense and are designed to minimize the round complexity. Practicality of our solutions is shown through experimental results.

We describe an automatic analysis to check secure multiparty computation protocols against privacy leaks. The analysis is sound --- a protocol that is deemed private does not leak anything about its private inputs, even if active attacks are performed against it. Privacy against active adversaries is an essential ingredient in constructions aiming to provide security (privacy + correctness) in adversarial models of intermediate (between passive and active) strength. Using our analysis we are able to show that the protocols used by the Sharemind secure multiparty computation platform are actively private.

Oblivious RAM (ORAM) is an established technique to hide the access pattern to an untrusted storage system. With ORAM, a curious adversary cannot tell what data address the user is accessing when observing the bits moving between the user and the storage system. All existing ORAM schemes achieve obliviousness by adding redundancy to the storage system, i.e., each access is turned into multiple random accesses. Such redundancy incurs a large performance overhead. Though traditional data prefetching techniques successfully hide memory latency in DRAM based systems, it turns out that they do not work well for ORAM. In this paper, we exploit ORAM locality by taking advantage of the ORAM internal structures. Though it might seem apparent that obliviousness and locality are two contradictory concepts, we challenge this intuition by exploiting data locality in ORAM without sacrificing provable security. In particular, we propose an ORAM prefetching technique called dynamic super block scheme and comprehensively explore its design space. The dynamic super block scheme detects data locality in the program's working set at runtime, and exploits the locality in a data-independent way. % based on the key observation that position map ORAMs have better locality than the data ORAM. Our simulation results show that with dynamic super block scheme, ORAM performance without super blocks can be significantly improved. After adding timing protection to ORAM, the average performance gain is 25.5\% (up to 49.4\%) over the baseline ORAM and 16.6\% (up to 30.1\%) over the best ORAM prefetching technique proposed previously.

Client-side deduplication is a very effective mechanism to reduce both storage and communication cost in cloud storage service. Halevi~\emph{et al.} (CCS '11) discovered security vulnerability in existing implementation of client-side deduplication and proposed a cryptographic primitive called ``proofs of ownership'' (PoW) as a countermeasure. In a proof of ownership scheme, any owner of the same file can prove to the cloud storage server that he/she owns that file in an efficient and secure manner, even if a bounded amount of any efficiently extractable information of that file has been leaked. We revisit Halevi~\emph{et al.}'s formulation of PoW and significantly improve the understanding and construction of PoW. Our contribution is twofold: \begin{itemize} \item Firstly, we propose a generic and conceptually simple approach to construct \emph{Privacy-Preserving} Proofs of Ownership scheme, by leveraging on well-known primitives (i.e. Randomness Extractor and Proofs of Retrievability) and technique (i.e. sample-then-extract). Our approach can be roughly described as \textsf{Privacy-Preserving PoW = Randomness Extractor $+$ Proofs of Retrievability}. \item Secondly, in order to provide a better instantiation of Privacy-Preserving-PoW, we propose a novel design of randomness extractor with large output size, which improves the state of art by reducing both the random seed length and entropy loss (i.e. the difference between the entropy of input and output) simultaneously. \end{itemize}

In 2000 Ko gave potential hard problem is proposed called the Markov problem. We give an algorithm, for certain parameters, for solution of the Markov problem. The Markov problem is related to the knot recognition problem. Hence we also a new algorithm the knot recognition problem. This knot recognition algorithm may be used for previously proposed cryptosystem that uses knots.

We describe a general Multi-Party Computation (MPC) protocol for arithmetic circuits that is secure against a static malicious adversary corrupting up to a 1/10 fraction of the parties. The protocol requires each party to send an average of soft-O(m/n) bits, and compute soft-O(m/n) operations in a network of size n, where m is the size of circuit. This is achieved by increasing latency from constant to O(d) , where d is the depth of the circuit. Our protocol has a setup phase that is independent of the circuit and relies on Threshold Fully Homomorphic Encryption (TFHE). The setup requires each party to send soft-O(k^2) messages and compute soft-O(k^2) operations, where k is the security parameter. We provide results from microbenchmarks conducted over a sorting network showing that our protocol may be practical for deployment in large networks. For example, we consider a network of size 2^25 (over 33 million), where each party has an input item of size 20 bytes. To securely sort the items, our protocol requires each party on average to send only 5 kilobytes per item sorted.

In this work we consider two protocols for performing cryptanalysis and security enhancement. The first one by Jiang et al., is a password-based authentication scheme which does not use smart cards. We note that this scheme is an improvement over Chen et al.'s scheme shown vulnerable to the off-line dictionary attack by Jiang et al. We perform a cryptanalysis on Jiang at al.'s improved protocol and observe that it is prone to the clogging attack, a kind of denial of service (DoS) attack. We then suggest an improvement on the protocol to prevent the clogging attack. The other protocol we consider for analysis is by Wang et al. This is a smart card based authentication protocol. We again perform the clogging (DoS) attack on this protocol via replay. We observe that all smart card based authentication protocols which precede the one by Wang et al., and require the server to compute the computationally intensive modular exponentiation are prone to the clogging attack. We suggest (another) improvement on the protocol to prevent the clogging attack, which also applies to the protocol by Jiang et. al.

We aim at constructing adaptive oblivious transfer protocols, enjoying fully simulatable security, from various well-known assumptions such as DDH, $d$-Linear, QR, DCR, and LWE. To this end, we present two generic constructions of adaptive OT, one of which utilizes verifiable shuffles together with threshold decryption schemes, while the other uses permutation networks together with what we call {\em loosely-homomorphic} key encapsulation schemes. We then show that specific choices of the building blocks lead to concrete adaptive OT protocols with fully simulatable security in the standard model under the targeted assumptions. Our generic methods can be extended to build universally composable (UC) secure, and leakage-resilient OT protocols.

We initiate the study of the following problem: Suppose Alice and Bob would like to outsource their encrypted private data sets to the cloud, and they also want to conduct the set intersection operation on their plaintext data sets. The straightforward solution for them is to download their outsourced ciphertexts, decrypt the ciphertexts locally, and then execute a commodity two-party set intersection protocol. Unfortunately, this solution is not practical. We therefore motivate and introduce the novel notion of {\em Verifiable Delegated Set Intersection on outsourced encrypted data} (VDSI). The basic idea is to delegate the set intersection operation to the cloud, while (i) not giving the decryption capability to the cloud, and (ii) being able to hold the misbehaving cloud accountable. We formalize security properties of VDSI and present a construction. In our solution, the computational and communication costs on the users are linear to the size of the intersection set, meaning that the efficiency is optimal up to a constant factor.

We present the first automated proof of the authorization protocols in TPM 2.0 in the computational model. The Trusted Platform Module(TPM) is a chip that enables trust in computing platforms and achieves more security than software alone. The TPM interacts with a caller via a predefined set of commands. Many commands reference TPM-resident structures, and use of them may require authorization. The TPM will provide an acknowledgement once receiving an authorization. This interact ensure the authentication of TPM and the caller. In this paper, we present a computationally sound mechanized proof for authorization protocols in the TPM 2.0. We model the authorization protocols using a probabilistic polynomial-time calculus and prove authentication between the TPM and the caller with the aid of the tool CryptoVerif, which works in the computational model. In addition, the prover gives the upper bounds to break the authentication between them.

We formalize the notion of Verifiable Oblivious Storage (VOS), where a client outsources the storage of data to a server while ensuring data confidentiality, access pattern privacy, and integrity and freshness of data accesses. VOS generalizes the notion of Oblivious RAM (ORAM) in that it allows the server to perform computation, and also explicitly considers data integrity and freshness. We show that allowing server-side computation enables us to construct asymptotically more efficient VOS schemes whose bandwidth overhead cannot be matched by any ORAM scheme, due to a known lower bound by Goldreich and Ostrovsky. Specifically, for large block sizes we can construct a VOS scheme with constant bandwidth per query; further, answering queries requires only poly-logarithmic server computation. We describe applications of VOS to Dynamic Proofs of Retrievability, and RAM-model secure multi-party computation.

We propose a simple and efficient sorting algorithm for secure multi-party computation (MPC). The algorithm is designed to be efficient when the number of parties and the size of the underlying field are small. For a constant number of parties and a field with a constant size, the algorithm has $O(\gm\log\gm)$ communication complexity, which is asymptotically the same as the best previous algorithm but achieves $O(1)$ round complexity, where $\gm$ is the number of items. The algorithm is constructed with the help of a new technique called ``shuffle-and-reveal.'' This technique can be seen as an analogue of the frequently used technique of ``add random number and reveal.'' The feasibility of our algorithm is demonstrated by an implementation on an MPC scheme based on Shamir's secret-sharing scheme with three parties and corruption tolerance of $1$. Our implementation sorts 1 million 32-bit word secret-shared values in 197 seconds.

Security models for two-party authenticated key exchange (AKE) protocols have developed over time to prove the security of AKE protocols even when the adversary learns certain secret values. In this work, we address more granular leakage: partial leakage of long-term secrets of protocol principals, even after the session key is established. We introduce a generic key exchange security model, which can be instantiated allowing bounded or continuous leakage, even when the adversary learns certain ephemeral secrets or session keys. Our model is the strongest known partial-leakage-based security model for key exchange protocols. We propose a generic construction of a two-pass leakage-resilient key exchange protocol that is secure in the proposed model, by introducing a new concept: the leakage-resilient NAXOS trick. We identify a special property for public-key cryptosystems: pair generation indistinguishability, and show how to obtain the leakage-resilient NAXOS trick from a pair generation indistinguishable leakage-resilient public-key cryptosystem.

Large-scale storage systems often attempt to achieve two seemingly conflicting goals: (1) the systems need to reduce the copies of redundant data to save space, a process called deduplication; and (2) users demand encryption of their data to ensure privacy. Conventional encryption makes deduplication on ciphertexts ineffective, as it destroys data redundancy. A line of work, originated from Convergent Encryption [28], and evolved into Message Locked Encryption [12], strives to solve this problem. The latest work, DupLESS [11], proposes a server-aided architecture that provides the strongest privacy. The DupLESS architecture relies on a key server to help the clients generate encryption keys that result in convergent ciphertexts. In this paper, we first provide a rigorous proof of security, in the random oracle model, for the DupLESS architecture which is lacking in the original paper. Our proof shows that using additional secret, other than the data itself, for generating encryption keys achieves the best possible security under current deduplication paradigm.We then introduce a distributed protocol that eliminates the need for a key server and allows less managed systems such as P2P systems to enjoy the high security level. Implementation and evaluation show that the scheme is both robust and practical.

We study a model of fairness in secure computation in which an adversarial party that aborts on receiving output is forced to pay a mutually predefined monetary penalty. We then show how the Bitcoin network can be used to achieve the above notion of fairness in the two-party as well as the multiparty setting (with a dishonest majority). In particular, we propose new ideal functionalities and protocols for fair secure computation and fair lottery in this model. One of our main contributions is the definition of an ideal primitive, which we call $\mathcal{F}_{\mathrm{CR}}^\star$ ($\mathrm{CR}$ stands for ``claim-or-refund''), that formalizes and abstracts the exact properties we require from the Bitcoin network to achieve our goals. Naturally, this abstraction allows us to design fair protocols in a hybrid model in which parties have access to the $\mathcal{F}_{\mathrm{CR}}^\star$ functionality, and is otherwise independent of the Bitcoin ecosystem. We also show an efficient realization of $\mathcal{F}_{\mathrm{CR}}^\star$ that requires only two Bitcoin transactions to be made on the network. Our constructions also enjoy high efficiency. In a multiparty setting, our protocols only require a constant number of calls to $\mathcal{F}_{\mathrm{CR}}^\star$ per party on top of a standard multiparty secure computation protocol. Our fair multiparty lottery protocol improves over previous solutions which required a quadratic number of Bitcoin transactions.

In 2009, Abdalla et al. proposed a reasonably practical password-authenticated key exchange (PAKE) secure against adaptive adversaries in the universal composability (UC) framework. It exploited the Canetti-Fischlin methodology for commitments and the Cramer-Shoup smooth projective hash functions (SPHFs), following the Gennaro-Lindell approach for PAKE. In this paper, we revisit the notion of non-interactive commitments, with a new formalism that implies UC security. In addition, we provide a quite efficient instantiation. We then extend our formalism to SPHF-friendly commitments. We thereafter show that it allows a blackbox application to one-round PAKE and oblivious transfer (OT), still secure in the UC framework against adaptive adversaries, assuming reliable erasures and a single global common reference string, even for multiple sessions. Our instantiations are more efficient than the Abdalla et al. PAKE in Crypto 2009 and the recent OT protocol proposed by Choi~et al. in PKC 2013. Furthermore, the new PAKE instantiation is the first one-round scheme achieving UC security against adaptive adversaries.

We present a quantum position verification scheme in the random oracle model. In contrast to prior work, our scheme does not require bounded storage/retrieval/entanglement assumptions. We also give an efficient position-based authentication protocol. This enables secret and authenticated communication with an entity that is only identified by its position in space.

The well known impossibility result of Cleve (STOC 1986) implies that in general it is impossible to securely compute a function with \emph{complete fairness} without an honest majority. Since then, the accepted belief has been that \emph{nothing} non-trivial can be computed with complete fairness in the two party setting. The surprising work of Gordon, Hazay, Katz and Lindell (STOC 2008) shows that this belief is false, and that there exist \emph{some} non-trivial (deterministic, finite-domain) boolean functions that can be computed fairly. This raises the fundamental question of characterizing complete fairness in secure two-party computation. In this work we show that not only that some or few functions can be computed fairly, but rather an \emph{enormous number} of functions can be computed fairly. In fact, \emph{almost all} boolean functions with distinct domain sizes can be computed with complete fairness (for instance, more than $99.999\%$ of the boolean functions with domain sizes $31 \times 30$). The class of functions that is shown to be possible includes also rather involved and highly non-trivial tasks, such as set-membership, evaluation of a private (boolean) function, private matchmaking and set-disjointness. In addition, we demonstrate that fairness is not restricted to the class of symmetric boolean functions where both parties get the same output, which is the only known feasibility result. Specifically, we show that fairness is also possible for asymmetric boolean functions where the output of the parties is not necessarily the same. Moreover, we consider the class of functions with \emph{non-binary} output, and show that fairness is possible \emph{for any finite range}. The constructions are based on the protocol of Gordon et.~al, and its analysis uses tools from convex geometry.

Secure two-party computation allows two untrusting parties to jointly compute an arbitrary function on their respective private inputs while revealing no information beyond the outcome. Existing cryptographic compilers can automatically generate secure computation protocols from high-level specifications, but are often limited in their use and efficiency of generated protocols as they are based on either garbled circuits or (additively) homomorphic encryption only. In this paper we present TASTY, a novel tool for automating, i.e., describing, generating, executing, benchmarking, and comparing, efficient secure two-party computation protocols. TASTY is a new compiler that can generate protocols based on homomorphic encryption and efficient garbled circuits as well as combinations of both, which often yields the most efficient protocols available today. The user provides a high-level description of the computations to be performed on encrypted data in a domain-specific language. This is automatically transformed into a protocol. TASTY provides most recent techniques and optimizations for practical secure two-party computation with low online latency. Moreover, it allows to efficiently evaluate circuits generated by the well-known Fairplay compiler. We use TASTY to compare protocols for secure multiplication based on homomorphic encryption with those based on garbled circuits and highly efficient Karatsuba multiplication. Further, we show how TASTY improves the online latency for securely evaluating the AES functionality by an order of magnitude compared to previous software implementations. TASTY allows to automatically generate efficient secure protocols for many privacy-preserving applications where we consider the use cases for private set intersection and face recognition protocols.

TLS is the most widely-used cryptographic protocol on the Internet. It comprises the TLS Handshake Protocol, responsible for authentication and key establishment, and the TLS Record Protocol, which takes care of subsequent use of those keys to protect bulk data. TLS has proved remarkably stubborn to analysis using the tools of modern cryptography. This is due in part to its complexity and its flexibility. In this paper, we present the most complete analysis to date of the TLS Handshake protocol and its application to data encryption (in the Record Protocol). We show how to extract a key-encapsulation mechanism (KEM) from the TLS Handshake Protocol, and how the security of the entire TLS protocol follows from security properties of this KEM when composed with a secure authenticated encryption scheme in the Record Protocol. The security notion we achieve is a variant of the ACCE notion recently introduced by Jager et al. (Crypto ’12). Our approach enables us to analyse multiple different key establishment methods in a modular fashion, including the first proof of the most common deployment mode that is based on RSA PKCS #1v1.5 encryption, as well as Diffie-Hellman modes. Our results can be applied to settings where mutual authentication is provided and to the more common situation where only server authentication is applied.

The article proposes one-pass authenticated key establishment protocol in random oracles for Wireless Sensor Networks. Security of the protocol relies on Computational Diffie-Hellman Problem on Bilinear Pairings. In one-pass key establishment protocol, the initiator computes a session key and a related message. The key token is to be sent to the intended receiver using receiver’s public key and sender secret key. From the received key token the receiver compute the session key, which is the same as the one computed by the sender, using sender public key and receiver’s secret key. Because of low communication overhead, the scheme is better suited for Wireless Sensor Networks(WSNs) than the traditional key establishment protocol to establish the session key between two adjacent nodes.

Abstract—Recent research results on tree-based Oblivious RAM by Shi et al. [15] obtain communication complexity of O(l · log3(N)) in the worst-case for an N-capacity storage with blocks size l. The individual nodes in the tree, however, are constructed using traditional ORAMs which have worst-case communication complexity linear in their capacity and block size. PIR protocols are able to provide better worst-case bounds (decoupling capacity from block size), but have traditionally been less practical than ORAM due to the fact that they require O(N) computational complexity on the server. This paper presents Path-PIR, a hybrid ORAM construction, using techniques from PIR, that overcomes the individual weaknesses of each. Path-PIR significantly reduces communication complexity when the block size of the ORAM is large. Compared to existing work, this leads to smaller data transfer costs by orders of magnitude for practical sized databases and achieves worst-case communication complexity of O(l · log2 (N)) for large block sizes. Additionally, the typically high computational cost of PIR is negated by the tree structure of the ORAM, which requires only a small fraction of the database to be operated on for each query. We also investigate the concept of an ORAM’s latency, which is the amount of communication required before users receive the result of their query. We show that Path-PIR achieves lower latency than any existing scheme, only about four times the block size. Using Amazon EC2 as an example, we demonstrate that even with the additional cost of PIR computation, Path-PIR provides a significant monetary saving compared to related work.

We show the first deterministic construction of an unconditionally secure multiparty computation (MPC) protocol in the passive adversarial model over black-box non-Abelian groups which is both optimal and has subexponential complexity of construction. More specifically, following the result of Desmedt et al. (2012) that the problem of MPC over non-Abelian groups can be reduced to finding a $t$-reliable $n$-coloring of planar graphs, we show the construction of such a graph which allows a path from the input nodes to the output nodes when any $t$-party subset is in the possession of the adversary. Unlike the (deterministic) constructions from Desmedt et al. (2012) our construction is subexponential and optimal at the same time, i.e., it is secure for any $t < \frac{n}{2}$.