Applying cut-and-choose techniques to Yao's garbled circuit protocol has been a promising approach for designing efficient Two-Party Computation (2PC) with malicious and covert security, as is evident from various optimizations and software implementations in the recent years. We revisit the security and efficiency properties of this popular approach and propose alternative constructions and a new definition that are more suitable for use in practice. * We design an efficient fully-secure 2PC protocol for two-output functions that only requires $O(t|C|)$ symmetric-key operations (with small constant factors, and ignoring factors that are independent of the circuit in use) in the Random Oracle Model, where $|C|$ is the circuit size and $t$ is a statistical security parameter. This is essentially the {\em optimal} complexity for protocols based on cut-and-choose, resolving a main question left open by the previous work on the subject. Our protocol utilizes novel techniques for enforcing \emph{garbler's input consistency} and handling \emph{two-output functions} that are more efficient than all prior solutions. * Motivated by the goal of eliminating the \emph{all-or-nothing} nature of 2PC with covert security (that privacy and correctness are fully compromised if the adversary is not caught in the challenge phase), we propose a new security definition for 2PC that strengthens the guarantees provided by the standard covert model, and offers a smoother security vs. efficiency tradeoff to protocol designers in choosing the \emph{right deterrence factor}. In our new notion, correctness is always guaranteed, privacy is fully guaranteed with probability ($1-\epsilon$), and with probability $\epsilon$ (i.e. the event of undetected cheating), privacy is only ``partially compromised" with at most a {\em single bit} of information leaked, in \emph{case of an abort}. We present two efficient 2PC constructions achieving our new notion. Both protocols are competitive with the previous covert 2PC protocols based on cut-and-choose. A distinct feature of the techniques we use in all our constructions is to check consistency of inputs and outputs using new gadgets that are themselves \emph{garbled circuits}, and to verify validity of these gadgets using \emph{multi-stage} cut-and-choose openings.

Akleylek et al. [S. Akleylek, L. Emmungil and U. Nuriyev, A modified algorithm for peer-to-peer security, \textit{journal of Appl. Comput. Math.}, vol. 6(2), pp.258-264, 2007.], introduced a modified public-key encryption scheme with steganographic approach for security in peer-to-peer (P2P) networks. In this cryptosystem, Akleylek et al. attempt to increase security of the P2P networks by mixing ElGamal cryptosystem with knapsack problem. In this paper, we present a ciphertext-only attack against their system to recover message. In addition, we show that for their scheme \textit{completeness} property is not holds, and therefore, the receiver cannot \textit{uniquely} decrypts messages. Furthermore, we also show that this system is not chosen-ciphertext secure, thus the proposed scheme is vulnerable to man-in-the-middle-attack, one of the most pernicious attacks against P2P networks. Therefore, this scheme is not suitable to implement in the P2P networks. We modify this cryptosystem in order to increase its security and efficiency. Our construction is the efficient CCA2-secure variant of the Akleylek et al.'s encryption scheme in the standard model, the \textit{de facto} security notion for public-key encryption schemes.

Since its introduction in 1994 the Secure Socket Layer (SSL) protocol (later renamed to Transport Layer Security (TLS)) evolved to the de facto standard for securing the transport layer. SSL/TLS can be used for ensuring data confidentiality, integrity and authenticity during transport. A main feature of the protocol is its flexibility. Modes of operation and security aims can easily be configured through different cipher suites. During its evolutionary development process several flaws were found. However, the flexible architecture of SSL/TLS allowed efficient fixes in order to counter the issues. This paper presents an overview on theoretical and practical attacks of the last 15 years, in chronological order and four categories: Attacks on the TLS Handshake protocol, on the TLS Record and Application Data Protocols, on the PKI infrastructure of TLS, and on various other attacks. We try to give a short ”Lessons Learned” at the end of each paragraph.

The continuous rise of static power consumption in modern CMOS technologies has led to the creation of a novel class of security attacks on cryptographic systems. The latter exploits the correlation between leakage current and the input patterns to infer the secret key; it is called leakage power analysis (LPA). The use power-balanced (m-of-n) logic is a promising solution that provides an answer to this problem, such circuits are designed to consume constant amount of power regardless of data being processed. This work evaluates the security of cryptographic circuits designed with this technology against the newly developed LPA. Two forms of LPA are investigated, one is based on differential power analysis (LDPA) and the other based on Hamming weight analysis (LHPA). Simulations performed at 90nm CMOS technology reveal that (m-of-n) circuits are totally resilient to LHPA and have a higher security level against LDPA than standard logic circuits.

Superpolynomial lower bounds on the average information ratio of linear secret sharing scheme are presented in this note for the first time. The previously known superpolynomial lower bounds applied only to the average information ratio of linear schemes in which the secret is a single field element. The new bounds are obtained by a simple adaptation of the techniques in those previous works.

We describe, and implement, a maliciously secure protocol for two-party computation in a parallel computational model. The protocol is based on cut-and-choose of Yao’s garbled circuit and an efficient oblivious transfer extension. The implementation is done using CUDA and yields fast results in a financially feasible and practical setting by using a consumer grade CPU and GPU. Our protocol introduces a novel construction in order to verify consistency of the garbled circuit constructor’s input in a parallel and maliciously secure setting.

With the rising trend of outsourcing databases to the cloud, it is important to allow clients to securely verify that their queries on the outsourced databases are correctly executed by the cloud. Existing solutions on this issue either suffer from a high communication cost, or introduce too much computational cost on the client side. Besides, so far only four types of SQL queries (i.e., selection query, projection query, join query and weighted sum query) are supported in existing solutions. It still remains challenging to design a verifiable SQL query scheme that introduces affordable storage overhead, communication and computational cost, and supports more SQL queries used in practice. This paper investigates this problem and proposes an efficient verifiable SQL query scheme for dynamic databases outsourced to the cloud. Our proposed scheme makes several major progresses: 1) it reduces the communication complexity (excluding the query results) to a logarithmic level (i.e., $O(log~n)$, where $n$ is the number of tuples in a table), while existing schemes all have a linear or quadratic complexity; 2) it constrains the computational complexity on the client side, in terms of expensive operations such as exponentiation, to a constant level, which is of linear level in existing schemes; 3) in addition to the queries supported by existing schemes, our proposed scheme also supports more practical query types including polynomial queries of any degrees, variance query and many other linear queries. Our design exploits techniques such as Merkle hash tree and constant size polynomial commitment. We shows the efficiency and scalability of our scheme through extensive numerical analysis. Based on the Strong Diffie-Hellman assumption, the Bilinear Strong Diffie-Hellman assumption and the Computational Diffie-Hellman problem, we show that our scheme is provably secure.

The rise of cloud computing and the proliferation of mobile devices make computation outsourcing popular. However, the servers are not fully trusted, and a critical problem is the verifiability and privacy of such computations. Although some computation outsoucing schemes provided a general method, the complicated cryptographic tools involved result in great inefficiency. The existing efficient computation outsourcing schemes however aim only at a specific computation task, lacking in generality. In this paper, we show how to construct a generic outsourcing computation scheme for inverting a class of homomorphic functions with computation disequilibrium. Extensive analysis shows that many cryptographic computations fall into this category. The formal security analysis proves that our scheme satisfies verifiability, input and output privacy in information-theoretic sense. Since the construction of our scheme tactfully takes advantage of the intrinsic property of the computation task being outsourced, no public key operations are used in the scheme, thus our solution clearly outperforms the existing schemes in terms of efficiency. In addition, we instantiate our generic construction with concrete examples, and the experimental result testifies the efficiency of our construction.

PRINCE is a new lightweight block cipher proposed at the ASIACRYPT'2012 conference. In this paper two observations on the linear layer of the cipher are presented. Based on the observations a differential fault attack is applied to the cipher under a random nibble-level fault model. The attack uniquely determines the 128-bit key of the cipher using less than 7 fault injections averagely. In the case with 4 fault injections, the attack limits the key to a space of size less than $2^{18}$ statistically.

The central objects of secure multiparty computation are the “multiparty functions” (or functionalities) that it seeks to securely realize. In this article we survey a set of results that constitute a Cryptographic Complexity Theory. This theory classifies and compares multiparty functions according to their secure computability and reducibility to each other. The basic questions studied, under various notions of security and reducibility, include: • Which functionalities are securely realizable (or are “trivial” – i.e., can be reduced to any functionality)? • Which functionalities are “complete” – i.e., those to which any functionality can be reduced? • More generally, which functionalities are reducible to which? Outside of triviality and completeness, this question is relatively less explored. Reductions yield relative measures of complexity among various functionalities. In the information- theoretic setting, absolute complexity measures have also been considered. In particular, we discuss results regarding which functions have t-private protocols (in which security is required against a passive adversary corrupting t out of n players) and how this set changes as t increases from 1 to n. We treat separately the results on two-party functionalities, for which the cryptographic complexity is much better understood. In particular, we present unified combinatorial characterizations of completeness and triviality for secure function evaluation using notions of isomorphism and the common information functionality (called the kernel) of a given functionality. Beyond completeness and triviality, we also discuss results on general reducibility, and, in the computationally bounded setting, the connection between these reductions and computational hardness assumptions. We briefly discuss results on reactive functionalities, which are much less studied than non-reactive (secure function evaluation) functionalities. Finally, we conclude with a selection of open problems.

Efficient computation of $r$-th root in $\mathbb F_q$ has many applications in computational number theory and many other related areas. We present a new $r$-th root formula which generalizes Müller's result on square root, and which provides a possible improvement of the Cipolla-Lehmer algorithm for general case. More precisely, for given $r$-th power $c\in \mathbb F_q$, we show that there exists $\alpha \in \mathbb F_{q^r}$ such that $Tr\left(\alpha^\frac{(\sum_{i=0}^{r-1}q^i)-r}{r^2}\right)^r=c$ where $Tr(\alpha)=\alpha+\alpha^q+\alpha^{q^2}+\cdots +\alpha^{q^{r-1}}$ and $\alpha$ is a root of certain irreducible polynomial of degree $r$ over $\mathbb F_q$.

Recently, a few chosen-ciphertext secure (CCA2-secure) variants of the McEliece public-key encryption (PKE) scheme in the standard model were introduced. All the proposed schemes are based on encryption repetition paradigm and use general transformation from CPA-secure scheme to a CCA2-secure one. Therefore, the resulting encryption scheme needs \textit{separate} encryption and has \textit{large} key size compared to the original scheme, which complex public key size problem in the code-based PKE schemes. Thus, the proposed schemes are not sufficiently efficient to be used in practice. In this work, we propose an efficient CCA2-secure variant of the McEliece PKE scheme in the standard model. The main novelty is that, unlike previous approaches, our approach is a generic conversion and can be applied to \textit{any} one-way trapdoor function (OW-TDF), the lowest-level security notion in the context of public-key cryptography, resolving a big fundamental and central problem that has remained unsolved in the past two decades.

Lattice-based cryptography is one of the candidates in the area of post-quantum cryptography. Cryptographic schemes with security reductions to hard lattice problems (like the Shortest Vector Problem SVP) offer an alternative to recent number theory-based schemes. In order to guarantee asymptotic efficiency, most lattice-based schemes are instantiated using polynomial rings over integers. These lattices are called 'ideal lattices'. It is assumed that the hardness of lattice problems in lattices over integer rings remains the same as in regular lattices. In order to prove or disprove this assumption, we instantiate random ideal lattices that allow to test algorithms that solve SVP and its approximate version. The Ideal Lattice Challenge allows online submission of short vectors to enter a hall of fame for full comparison. We adjoin a set of first experiments and a first comparison of ideal and regular lattices.

In a {verifiable data streaming} protocol, the client streams a long string to the server who stores it in its database. The stream is verifiable in the sense that the server can neither change the order of the elements nor manipulate them. The client may also retrieve data from the database and update them. The content of the database is publicly verifiable such that any party in possession of some value $s$ and a proof $\pi$ can check that $s$ is indeed in the database. We introduce the notion of verifiable data streaming and present an efficient instantiation that supports an exponential number of values based on general assumptions. Our main technique is an authentication tree in which the leaves are not fixed in advanced such that the user, knowing some trapdoor, can authenticate a new element on demand \emph{without} pre- or re-computing all other leaves. We call this data structure \emph{chameleon authentication tree} (CAT). We instantiate our scheme with primitives that are secure under the discrete logarithm assumption. The algebraic properties of this assumption allow us to obtain a very efficient verification algorithm. As a second application of CATs, we present a new transformation from any one-time to many-time signature scheme that is more efficient than previously known solutions.

This article proposes a provably secure aggregate signcryption scheme in random oracles. Security of the scheme is based on computational infesibility of solving Decisional Bilinear Diffie-Hellman Problem and Discrete Logarithm Problems. Confidentiality and authenticity are two fundamental security requirement of Public key Cryptography. These are achieved by encryption scheme and digital signatures respectively. Signcryption scheme is a cryptographic primitive that performs signature and encryption simultaneously in a single logical steps. An aggregate signcryption scheme can be constructed of the aggregation of individual signcryption. The aggreagtion is done taking n distinct signcryptions on n messages signed by n distinct users.

We extend the fully homomorphic encryption scheme over the integers of van Dijk et al. (DGHV) to batch fully homomorphic encryption, i.e. to a scheme that supports encrypting and homomorphically processing a vector of plaintext bits as a single ciphertext. Our variant remains semantically secure under the (error-free) approximate GCD problem. We also show how to perform arbitrary permutations on the underlying plaintext vector given the ciphertext and the public key. Our scheme offers competitive performance: we describe an implementation of the fully homomorphic evaluation of AES encryption, with an amortized cost of about 12 minutes per AES ciphertext on a standard desktop computer; this is comparable to the timings presented by Gentry et al. at Crypto 2012 for their implementation of a Ring-LWE based fully homomorphic encryption scheme.

A protocol for NFC mobile authentication and transaction is recently proposed by W. Chen et al. This protocol is used for micropayments, where the Mobile Network Operator (MNO) pays for its customers. The main advantage of this protocol is its compatibility with the existing GSM network. This paper suggests some improvements in this protocol from security point of view. As this protocol is used for monetary transactions, it should be as secure as possible. This paper presents an improved version of the existing protocol with a detailed analysis at the end. The user interaction with the system is improved making it more user friendly. An additional layer of security has been added by introducing PIN authentication by the user. Mutual authentication is improved by adding freshness by the mobile device in order to resist replay attack. We also add digital signatures with the transaction messages for data integrity and non-repudiation.

Password-Authenticated Key Exchange (PAKE) has received deep attention in the last few years, with a recent improvement by Katz-Vaikuntanathan, and their one-round protocols: the two players just have to send simultaneous flows to each other, that depend on their own passwords only, to agree on a shared high entropy secret key. To this aim, they followed the Gennaro-Lindell approach, with a new kind of Smooth-Projective Hash Functions (SPHF). They came up with the first concrete one-round PAKE, secure in the Bellare-Pointcheval-Rogaway model, but at the cost of a simulation-sound NIZK, which makes the overall construction not really efficient. This paper follows their path with a new efficient instantiation of SPHF on Cramer-Shoup ciphertexts. It then leads to the design of the most efficient PAKE known so far: a one-round PAKE with two simultaneous flows consisting of 6 group elements each only, in any DDH-group without any pairing. We thereafter show a generic construction for SPHFs, in order to check the validity of complex relations on encrypted values. This allows to extend this work on PAKE to the more general family of protocols, termed Langage-Authenticated Key Exchange (LAKE) by Ben Hamouda-Blazy-Chevalier-Pointcheval-Vergnaud, but also to blind signatures.

In this paper, we introduce a general paradigm called identity-based extractable hash proof system (IB-EHPS), which is an extension of extractable hash proof system (EHPS) proposed by Wee (CRYPTO ’10). We show how to construct identity-based key encapsulation mechanism (IB-KEM) from IB-EHPS in a simple and modular fashion. Our construction provides a generic method of building and interpreting CCA-secure IB-KEMs based on computational assumptions. As instantiations, we realize IB-EHPS from the bilinear Diffie-Hellman assumption and the modified bilinear Diffie-Hellman assumption, respectively.

In this paper, we consider both theoretical and practical aspects of robust NI-PE (non-interactive polynomial evaluation with detection of cheaters). First, we give a necessary condition of adversary structures for which perfectly robust NI-PE with small communication complexity exists. More precisely, we show that for any positive integers $n$, $m$ and $d>1$, an $n$-player access structure $U$, and an $n$-player adversary structure $T$, there exists a $U$-participating NI-PE scheme for $m$-variate polynomials over a finite field $F$ with $T$-private inputs such that (1) perfectly robust (i.e., successful cheating probability $\epsilon=0$), (2) any polynomial of degree $d$ can be evaluated, and (3) the total size of shares of the output for some participating set is $o(m)\times \log |F|$, {\em only if} $T$ is of type $Q_{d+1}$ for $U$, meaning that no $d+1$ sets in $T$ cover any set in $U$. Second, we give constructions of perfectly robust NI-PE schemes against threshold adversary and general adversary, respectively. All the proposed schemes ensure perfect robustness against $Q_{d+1}$ adversary, and computability of arbitrary polynomial of degree $d$. Third, we show that efficient robust NI-PE schemes against general adversary can be constructed by allowing cheaters very small chance of successful cheating. Namely, we construct two robust NI-PE schemes with $\epsilon=1/|F|$ and the total size for shares of the output is only three times larger compared to the perfectly robust NI-PE scheme against threshold adversary.

With over 1.6~billion debit and credit cards in use worldwide, the EMV system (a.k.a. ``Chip-and-PIN'') has become one of the most important deployed cryptographic protocol suites. Recently, the EMV consortium has decided to upgrade the existing RSA based system with a new system relying on Elliptic Curve Cryptography (ECC). One of the central components of the new system is a protocol that enables a card to establish a secure channel with a card reader. In this paper we provide a security analysis of the proposed protocol, we propose minor changes/clarifications to the ``Request for Comments'' issued in Nov 2012, and demonstrate that the resulting protocol meets the intended security goals. The structure of the protocol is one commonly encountered in practice: first run a key-exchange to establish a shared key (which performs authentication and key confirmation), only then use the channel to exchange application messages. Although common in practice, this structure takes the protocol out of the reach of most standard security models for key-exchange. Unfortunately, the only models that can cope with the above structure suffer from some drawbacks that make them unsuitable for our analysis. Our second contribution is to provide new security models for channel establishment protocols. Our models have a more inclusive syntax, are quite general, deal with a realistic notion of authentication (one-sided authentication as required by EMV), and do not suffer from the drawbacks that we identify in prior models.

Recently, Islam and Biswas proposed a pairing-free identity-based authenticated group key agreement protocol for imbalanced mobile networks. However, in this letter, we point out that this protocol cannot resist passive attack, and cannot provide forward secrecy for joining operation and backward secrecy for leaving operation.

In this paper we describe several ideas related to Differential Fault Attack (DFA) on MICKEY 2.0, a stream cipher from eStream hardware profile. Using the standard assumptions for fault attacks, we first show that if the adversary can induce random single bit faults in the internal state of the cipher, then by injecting around $2^{16.7}$ faults and performing $2^{32.5}$ computations on an average, it is possible to recover the entire internal state of MICKEY at the beginning of the key-stream generation phase. We further consider the scenario where the fault may affect more than one (at most three) neighbouring bits and in that case we require around $2^{18.4}$ faults on an average to mount the DFA. We further show that if the attacker can solve multivariate equations (say, using SAT solvers) then the attack can be carried out using around $2^{14.7}$ faults in the single-bit fault model and $2^{16.06}$ faults for the multiple-bit scenario.

In this paper we investigate the linear hull effect in the light-weight block cipher EPCBC. We give an efficient method of computing linear hulls with high capacity. We then apply found hulls to derive attacks on the full 32 rounds of EPCBC--96 and 20 rounds of EPCBC-48. Using the developed methods we revise the work of J.Y. Cho from 2010 and obtain an attack based on multidimensional linear approximations on 26 rounds of PRESENT--128. The results show that designers of block ciphers should take seriously the threat coming from the linear hull attacks and not just limit themselves to proving bounds based solely on linear characteristics.

The UMTS/LTE protocol for mobile phone networks has been designed to offer a limited form of anonymity for mobile phone uses. In this paper we quantify precisely what this limited form of anonymity actually provides via a formal security model. The model considers an execution where the home and roaming network providers are considered as one entity. We consider two forms of anonymity, one where the mobile stations under attacked are statically selected before the execution, and a second one where the adversary selects these stations adaptively. We prove that the UMTS/LTE protocol meets both of these security definitions. Our analysis requires new assumptions on the underlying keyed functions for UMTS, which whilst probably true have not previously been brought to the fore.

SAT solvers are being used more and more in Cryptanalysis. Their efficiency varies depending on the structure of the algorithm they are applied to. However, when it comes to integer factorization, or more specially the RSA problem, SAT solvers prove to be at least inefficient. The running times are too long to be compared with any well known integer factorization algorithm, even when it comes to small RSA moduli numbers. The recent work on cold boot attacks has sparkled again the interest on partial key exposure attacks and RSA key reconstruction. In this work, contrary to the search tree or lattice-based approaches that most of these works use, SAT solvers are used. The focus is on the study of two scenarios, one where there is disclosure of random bits of $p$ and $q$ and one for the case where the public exponent $e$ is equal to three. In both cases, we provide a more efficient modeling of RSA as an instance of a satisfiability problem, and manage to reconstruct the private key, given a part of the key, even for public keys of 1024 bits in few seconds.

The universal composability paradigm allows for the modular design and analysis of cryptographic protocols. It has been widely and successfully used in cryptography. However, devising a coherent yet simple and expressive model for universal composability is, as the history of such models shows, highly non-trivial. For example, several partly severe problems have been pointed out in the literature for the UC model. In this work, we propose a coherent model for universal composability, called the IITM model (``Inexhaustible Interactive Turing Machine''). A main feature of the model is that it is stated without a priori fixing irrelevant details, such as a specific way of addressing of machines by session and party identifiers, a specific modeling of corruption, or a specific protocol hierarchy. In addition, we employ a very general notion of runtime. All reasonable protocols and ideal functionalities should be expressible based on this notion in a direct and natural way, and without tweaks, such as (artificial) padding of messages or (artificially) adding extra messages. Not least because of these features, the model is simple and expressive. Also the general results that we prove, such as composition theorems, hold independently of how such details are fixed for concrete applications. Being inspired by other models for universal composability, in particular the UC model and because of the flexibility and expressivity of the IITM model, conceptually, results formulated in these models directly carry over to the IITM model.

In this paper, we present a new cube root algorithm in finite field $\mathbb{F}_{q}$ with $q$ a power of prime, which extends the Cipolla-Lehmer type algorithms \cite{Cip,Leh}. Our cube root method is inspired by the work of Müller \cite{Muller} on quadratic case. For given cubic residue $c \in \mathbb{F}_{q}$ with $q \equiv 1 \pmod{9}$, we show that there is an irreducible polynomial $f(x)=x^{3}-ax^{2}+bx-1$ with root $\alpha \in \mathbb{F}_{q^{3}}$ such that $Tr(\alpha^{\frac{q^{2}+q-2}{9}})$ is a cube root of $c$. Consequently we find an efficient cube root algorithm based on third order linear recurrence sequence arising from $f(x)$. Complexity estimation shows that our algorithm is better than previously proposed Cipolla-Lehmer type algorithms.

We present a new practical Identity-Based Encryption (IBE) system that can be another candidate for standard IBE techniques. Our construction is based on a new framework for realizing an IBE trapdoor from pairing-based groups, which is motivated from the `two equation' revocation technique suggested by Lewko, Sahai, and Waters. The new framework enables our IBE system to achieve a tight security reduction to the Decision Bilinear Diffie-Hellman assumption. Due to its the tightness, our system can take as input the shorter size of security parameters than the previous practical BF, SK, and BB$_{1}$ systems, which provides better efficiency to our system in terms of computational cost. With appropriate parametrization at 80-bit security level (considering security loss), our IBE system can obtain 11 times faster decryption than the previous ones and 77 times faster encryption than the BF system. We prove that our system is fully secure against chosen ciphertext attacks in the random oracle model. From computational variant of Naor's observation, we can also suggest a new signature scheme that features a tight security reduction to the Computational Diffie-Hellman assumption and provides strong unforgeability simultaneously.

We utilise a simulated annealing algorithm to find several nonlinear approximations to various S-boxes which can be used to replace the linear approximations in the outer rounds of existing attacks. We propose three variants of a new nonlinear cryptanalytic algorithm which overcomes the main issues that prevented the use of nonlinear approximations in previous research, and we present the statistical frameworks for calculating the complexity of each version. We present new attacks on 11-round Serpent with better data complexity than any other known-plaintext or chosen-plaintext attack, and with the best overall time complexity for a 256-bit key.

We introduce the notion of rate-limited secure function evaluation (RL-SFE). Loosely speaking, in an RL-SFE protocol participants can monitor and limit the number of distinct inputs (i.e., rate) used by their counterparts in multiple executions of an SFE, in a private and verifiable manner. The need for RL-SFE naturally arises in a variety of scenarios: e.g., it enables service providers to ``meter'' their customers' usage without compromising their privacy, or can be used to prevent oracle attacks against SFE constructions. We consider three variants of RL-SFE providing different levels of security. As a stepping stone, we also formalize the notion of commit-first SFE (cf-SFE) wherein parties are committed to their inputs before each SFE execution. We provide compilers for transforming any cf-SFE protocol into each of the three RL-SFE variants. Our compilers are accompanied with simulation-based proofs of security in the standard model and show a clear tradeoff between the level of security offered and the overhead required. Moreover, motivated by the fact that in many client-server applications clients do not keep state, we also describe a general approach for transforming the resulting RL-SFE protocols into stateless ones. As a case study, we take a closer look at the oblivious polynomial evaluation (OPE) protocol of Hazay and Lindell, show that it is commit-first and instantiate efficient rate-limited variants of it.

Aggregate signatures provide bandwidth-saving aggregation of ordinary signatures. We present the first unrestricted instantiation in the standard model, Moreover, our construction yields a multisignature scheme where a single message is signed by a number of signers. Our second result is an application to verifiably encrypted signatures. There, signers encrypt their signature under the public key of a trusted third party and output a proof that the signature is inside. Upon dispute between signer and verifier, the trusted third party is able to recover the signature. These schemes are provably secure in the standard model.

Cascading-based constructions represent the predominant approach to the problem of key-length extension for block ciphers. Besides the plain cascade, existing works also consider its modification containing key-whitening steps between the invocations of the block cipher, called randomized cascade or XOR-cascade. We contribute to the understanding of the security of these two designs by giving the following attacks and security proofs, assuming an underlying ideal block cipher with key length $k$ and block length $n$: - For the plain cascade of odd (resp. even) length $l$ we present a generic attack requiring roughly $2^{k+\frac{l-1}{l+1}n}$ (resp. $2^{k+\frac{l-2}{l}n}$) queries, being a generalization of both the meet-in-the-middle attack on double encryption and the best known attack on triple cascade. - For XOR-cascade of odd (resp. even) length $l$ we prove security up to $2^{k+\frac{l-1}{l+1}n}$ (resp. $2^{k+\frac{l-2}{l}n}$) queries and also an improved bound $2^{k+\frac{l-1}{l}n}$ for the special case $l\in\{3,4\}$ by relating the problem to the security of key-alternating ciphers in the random-permutation model. - Finally, for a natural class of sequential constructions where block-cipher encryptions are interleaved with key-dependent permutations, we show a generic attack requiring roughly $2^{k+\frac{l-1}{l}n}$ queries. Since XOR-cascades are sequential, this proves tightness of our above result for XOR-cascades of length $l\in\{3,4\}$ as well as their optimal security within the class of sequential constructions. These results suggest that XOR-cascades achieve a better security/efficiency trade-off than plain cascades and should be preferred.

In the public key cryptosystems, revocation functionality is required when a secret key is corrupted by hacking or the period of a contract expires. In the public key infrastructure setting, numerous solutions have been proposed, and in the Identity Based Encryption (IBE) setting, a recent series of papers proposed revocable IBE schemes. Delegation of key generation is also an important functionality in cryptography from a practical standpoint since it allows reduction of excessive workload for a single key generation authority. Although fficient solutions for either revocation or delegation of key generation in IBE systems have been proposed, an important open problem is efficiently delegating both the key generation and revocation functionalities in IBE systems. Libert and Vergnaud, for instance, left this as an open problem in their CT-RSA 2009 paper. In this paper, we propose the first solution for this problem. We prove the selective-ID security of our proposal under the Decisional Bilinear Diffie-Hellman assumption in the standard model.

This paper provides the provable-security treatment of path vector routing protocols. We first design a security definition for routing path vector protocols by studying, generalizing, and formalizing numerous known threats. Our model incorporates three major security goals. It is quite strong, yet simple to use. We prove by reduction that S-BGP satisfies two out of the security model’s three goals, assuming the underlying signature scheme is secure. Under the same assumption, we next show how the protocol can be modified to meet all three security goals simultaneously. We also analyze SoBGP and show that it fails to meet two security goals. Finally, we study security of partial PKI deployment of path vector protocols when not all nodes have public keys. We investigate the possibilities of relaxing the PKI requirement and relying on non-cryptographic physical security of networks that use the protocol in order to achieve possibly weaker, but still well-defined, notions of security. We also present the necessary and sufficient conditions to achieve full security in the partial PKI deployment scenario. We believe our conclusions will prove useful for protocol developers, standards bodies and government agencies.

In ACM CCS 2008, Boldyreva et al. proposed an elegant way of achieving an Identity-based Encryption (IBE) with {\em efficient} revocation, which we call revocable IBE (RIBE). One of the significant benefit of their construction is scalability, where the overhead of the trusted authority is logarithmically increased in the number of users, whereas that in the Boneh-Franklin naive revocation way is linearly increased. All subsequent RIBE schemes follow the Boldyreva et al. security model and syntax. In this paper, we first revisit the Boldyreva et al. security model, and aim at capturing the exact notion for the security of the naive but non-scalable Boneh-Franklin RIBE scheme. To this end, we consider a realistic threat, which we call {\em decryption key exposure}. We also show that all prior RIBE constructions except for the Boneh-Franklin one are vulnerable to decryption key exposure. As the second contribution, we revisit approaches to achieve (efficient and adaptively secure) scalable RIBE schemes, and propose a simple RIBE scheme, which is the first scalable RIBE scheme with decryption key exposure resistance, and is more efficient than previous (adaptively secure) scalable RIBE schemes. In particular, our construction has the shortest ciphertext size and the fastest decryption algorithm even compared with all scalable RIBE schemes without decryption key exposure resistance.

We analyze four recently proposed normal forms for elliptic curves. Though these forms are mathematically appealing and exhibit some cryptographically desirable properties, they nonetheless fall short of cryptographic viability, especially when compared to various types of Edwards Curves. In this paper, we present these forms and demonstrate why they fail to measure up to the standards set by Edwards Curves.

In this paper, we address the problem of formal and automated security verification of WSN transport protocols that may perform cryptographic operations. The verification of this class of protocols is difficult because they typically consist of complex behavioral characteristics, such as real-time, probabilistic, and cryptographic operations. To solve this problem, we propose a probabilistic timed calculus for cryptographic protocols, and demonstrate how to use this formal language for proving security or vulnerability of protocols. The main advantage of the proposed language is that it supports an expressive syntax and semantics, including bisimilarities that supports real-time, probabilistic, and cryptographic issues at the same time. Hence, it can be used to verify the systems that involve these three property in a more convenient way. In addition, we propose an automatic verification method, based on the well-known PAT process analysis toolkit, for this class of protocols. For demonstration purposes, we apply the proposed manual and automatic proof methods for verifying the security of DTSN and SDTP, which are two of the recently proposed WSN tranport protocols.

Secure Multiparty Computation (SMC) enables a set of users to evaluate certain functionalities on their respective inputs while keeping these inputs encrypted throughout the computation. In many scenarios, however, outsourcing these computations to an untrusted server is desirable, so that the server can perform the computation on behalf of the users. Unfortunately, existing solutions are either inefficient, rely heavily on user interaction, or require the inputs to be encrypted under the same key - drawbacks making the employment in practice very limited. We propose the first general-purpose construction that avoids all these drawbacks: it is efficient, it requires no user interaction whatsoever (except for data up- and download), and it allows evaluating any dynamically chosen function on inputs encrypted under different independent public keys. Our solution assumes the existence of two non-colluding but untrusted servers that jointly perform the computation by means of a cryptographic protocol. This protocol is provably secure in the semi-honest model. We demonstrate the applicability of our result in two real-world scenarios from different domains: Privacy-Preserving Face Recognition and Private Smart Metering. Finally, we give a performance analysis of our general-purpose construction to highlight its practicability.

We employ tropical algebras as platforms for several cryptographic schemes that would be vulnerable to linear algebra attacks were they based on ``usual" algebras as platforms.

Using simulated annealing, we derive several equivalence classes of balanced Boolean functions with optimum algebraic immunity, fast algebraic resistance, and maximum possible algebraic degree. For numbers n of input bits less than 16, these functions also possess superior nonlinearity to all Boolean functions so far obtained with said properties.

In this short note, we demonstrate that the existence of one-way functions implies the existence of an $\omega(1)$-round simultaneously resettable witness indistinguishable argument.

An ever-increasing number of personal photos is stored online. This trend can be problematic, because face recognition software can undermine user privacy in unexpected ways. Face de-identification aims to prevent automatic recognition of faces thus improving user privacy, but previous work alters the image in a way that makes them indistinguishable for both computers and humans, which prevents a wide-spread use. We propose a method for de-identification of images that effectively prevents face recognition software (using the most popular and effective algorithms) from identifying people, but still allows human recognition. We evaluate our method experimentally by adapting the CSU framework and using the FERET database. We show that we are able to achieve strong de-identification while maintaining reasonable image quality.

The simulation paradigm, introduced by Goldwasser, Micali and Rackoff, is of fundamental importance to modern cryptography. In a breakthrough work from 2001, Barak (FOCS'01) introduced a novel non-black-box simulation technique. This technique enabled the construction of new cryptographic primitives, such as resettably-sound zero-knowledge arguments, that cannot be proven secure using just black-box simulation techniques. The work of Barak and its follow-ups, however, all require stronger cryptographic hardness assumptions than the minimal assumption of one-way functions: the work of Barak requires the existence of collision-resistant hash functions, and a very recent result by Bitansky and Paneth (FOCS'12) instead requires the existence of an Oblivious Transfer protocol. In this work, we show how to perform non-black-box simulation assuming just the existence of one-way functions. In particular, we demonstrate the existence of a constant-round resettably-sound zero-knowledge argument based only on the existence of one-way functions. Using this technique, we determine necessary and sufficient assumptions for several other notions of resettable security of zero-knowledge proofs. An additional benefit of our approach is that it seemingly makes practical implementations of non-black-box zero-knowledge viable.

We find a one to one correspondence between quadratic APN functions without linear or constant terms and a special kind of matrices (We call such matrices as QAMs). Based on the nice mathematical structures of the QAMs, we have developed efficient algorithms to construct quadratic APN functions. On $\mathbb{F}_{2^7}$, we have found more than 470 classes of new CCZ-inequivalent quadratic APN functions, which is 20 times more than the known ones. Before this paper, there are only 23 classes of CCZ-inequivalent APN functions on $\mathbb{F}_{2^{8}}$ have been found. With our method, we have found more than 2000 classes of new CCZ-inequivalent quadratic APN functions, and this number is still increasing quickly.

Recently, Isalam and Biswas proposed a new group key agreement (GKA) protocol for imbalanced mobile networks. In this letter, we will show that Isalam et al.’s GKA protocol is not secure.

This paper is devoted to the design of a 258- bit multiplier for computing pairings over Barreto-Naehrig (BN) curves at 128-bit security level. The proposed design is optimized for Xilinx field programmable gate array (FPGA). Each 258-bit integer is represented as a polynomial with five,65 bit signed integer, coefficients . Exploiting this splitting we designed a pipelined 65-bit multiplier based on new Karatsuba-Ofman variant using non-standard splitting to fit to the Xilinx embedded digital signal processor (DSP) blocks. Our architecture is able to compute 258-bit multiplication suitable for BN curves using only 11 in-built DSP blocks available on Virtex-6 Xilinx FPGA devices. It is the least DSP blocks consumption in the known literature. This work can be extended to efficiently compute pairings at higher security levels.

NTRUEncrypt, proposed in 1996 by Hoffstein, Pipher and Silverman, is the fastest known lattice-based encryption scheme. Its moderate key-sizes, excellent asymptotic performance and conjectured resistance to quantum computers make it a desirable alternative to factorisation and discrete-log based encryption schemes. However, since its introduction, doubts have regularly arisen on its security and that of its digital signature counterpart. In the present work, we show how to modify NTRUEncrypt and NTRUSign to make them provably secure in the standard (resp. random oracle) model, under the assumed quantum (resp. classical) hardness of standard worst-case lattice problems, restricted to a family of lattices related to some cyclotomic fields. Our main contribution is to show that if the secret key polynomials of the encryption scheme are selected from discrete Gaussians, then the public key, which is their ratio, is statistically indistinguishable from uniform over its range. We also show how to rigorously extend the encryption secret key into a signature secret key. The security then follows from the already proven hardness of the R-SIS and R-LWE problems.

Algebraic expressions of the Bernstein-Rabin-Winograd-polynomials, when defined over the field of the rational numbers, are obtained by recursion.

In this work, we generalize the paradigm of hash proof system (HPS) proposed by Cramer and Shoup [CS02]. In the central of our generalization, we lift subset membership problem to distribution distinguish problem. Our generalized HPS clarifies and encompass all the known public-key encryption (PKE) schemes that essentially implement the idea of hash proof system. Moreover, besides existing smoothness property, we introduce an additional property named anonymity for HPS. As a natural application, we consider anonymity for PKE in the presence of key-leakage, and provide a generic construction of leakage-resilient anonymous PKE from anonymous HPS. We then extend our generalization to the identity-based setting. Concretely, we generalize the paradigm of identity-based hash proof system (IB-HPS) proposed by Boneh et al. [BGH07] and Alwen et al. [ADN+ 10], and introduce anonymity for it. As an interesting application of anonymous IB-HPS, we consider security for public-key encryption with keyword search (PEKS) in the presence of token-leakage, and provide a generic construction of leakage-resilient secure PEKS from leakage-resilient anonymous IBE, which in turn is based on anonymous IB-HPS.

We show how to efficiently compile any given circuit C into a leakage-resilient circuit C' such that any function on the wires of C' that leaks information during a computation C'(x) yields advantage in computing the product of |C'|^{Omega(1)} elements of the alternating group A_u. Our construction resists NC^1 leakage assuming L \neq NC^1, as was conjectured here and proven later [Miles, ITCS '14]. Also, in combination with new compression bounds for A_u products obtained here, C' withstands leakage from virtually any class of functions against which average-case lower bounds are known. This includes communication protocols, and AC^0 circuits augmented with few arbitrary symmetric gates. In addition, we extend the construction to the multi-query setting by relying on a simple secure hardware component. We build on Barrington's theorem [JCSS '89] and on the previous leakage-resilient constructions by Ishai et al. [Crypto '03] and Faust et al. [Eurocrypt '10]. Our construction exploits properties of A_u beyond what is sufficient for Barrington's theorem.

Garbled circuits, introduced by Yao in the mid 80s, allow computing a function f on an input x without leaking anything about f or x besides f(x). Garbled circuits found numerous applications, but every known construction suffers from one limitation: it offers no security if used on multiple inputs x. In this paper, we construct for the first time reusable garbled circuits. The key building block is a new succinct single-key functional encryption scheme. Functional encryption is an ambitious primitive: given an encryption Enc(x) of a value x, and a secret key sk_f for a function f, anyone can compute f(x) without learning any other information about x. We construct, for the first time, a succinct functional encryption scheme for any polynomial-time function f where succinctness means that the ciphertext size does not grow with the size of the circuit for f, but only with its depth. The security of our construction is based on the intractability of the Learning with Errors (LWE) problem and holds as long as an adversary has access to a single key sk_f (or even an a priori bounded number of keys for different functions). Building on our succinct single-key functional encryption scheme, we show several new applications in addition to reusable garbled circuits, such as a paradigm for general function obfuscation which we call token-based obfuscation, homomorphic encryption for a class of Turing machines where the evaluation runs in input-specific time rather than worst-case time, and a scheme for delegating computation which is publicly verifiable and maintains the privacy of the computation.

Non-interactive key exchange (NIKE) is a fundamental but much-overlooked cryptographic primitive. It appears as a major contribution in the ground-breaking paper of Diffie and Hellman, but NIKE has remained largely unstudied since then. In this paper, we provide different security models for this primitive and explore the relationships between them. We then give constructions for secure NIKE in the Random Oracle Model based on the hardness of factoring and in the standard model based on the hardness of a variant of the decisional Bilinear Diffie Hellman Problem for asymmetric pairings. We also study the relationship between NIKE and public key encryption (PKE), showing that a secure NIKE scheme can be generically converted into an IND-CCA secure PKE scheme. This conversion also illustrates the fundamental nature of NIKE in public key cryptography.

In this work we consider generic algorithms to find near-collisions for a hash function. If we consider only hash computations, it is easy to compute a lower-bound for the complexity of near-collision algorithms, and to build a matching algorithm. However, this algorithm needs a lot of memory, and makes than 2^{n/2} memory accesses. Recently, several algorithms have been proposed without this memory requirement; they require more hash evaluations, but the attack is actually more practical. They can be divided in two main categories: some are based on truncation, and some are based on covering codes. In this paper, we give a new insight to the generic complexity of a near-collision attack. First, we consider time-memory trade-offs for truncation-based algorithms. For a practical implementation, it seems reasonable to assume that some memory is available and we show that taking advantage of this memory can significantly reduce the complexity. Second, we show a new method combining truncation and covering codes. The new algorithm is always at least as good as the previous works, and often gives a significant improvement. We illustrate our results by giving a 10-near collision for MD5: our algorithm has a complexity of 2^45.4 using 1TB of memory while the best previous

Wireless Sensor Networks (WSNs) pose a number of unique security challenges that demand innovation in several areas including the design of cryptographic primitives and protocols. Despite recent progress, the efficient implementation of Elliptic Curve Cryptography (ECC) for WSNs is still a very active research topic and techniques to further reduce the time and energy cost of ECC are eagerly sought. This paper presents an optimized ECC implementation that we developed from scratch to comply with the severe resource constraints of 8-bit sensor nodes such as the MICAz and IRIS motes. Our ECC software uses Optimal Prime Fields (OPFs) as underlying algebraic structure and supports two different families of elliptic curves, namely Weierstraß-form and twisted Edwards-form curves. Due to the combination of efficient field arithmetic and fast group operations, we achieve an execution time of $5.8 \cdot 10^6$ clock cycles for a full 158-bit scalar multiplication on an 8-bit ATmega128 microcontroller, which is 2.78 times faster than the widely-used TinyECC library. Our implementation also shows that the energy cost of scalar multiplication on a MICAz (or IRIS) mote amounts to just 19 mJ when using a twisted Edwards curve over a 160-bit OPF. This result compares fairly well with the energy figures of two recently-presented hardware designs of ECC based on twisted Edwards curves.

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

This paper considers the transfer of digital data over {\sl leaky and noisy} communication channels. We develop defensive strategies exploiting the fact that noise prevents the attacker from accurately measuring leakage. The defense strategy described in this paper pairs each useful data element $k$ with a camouflage value $v$ and simultaneously transmits both $k$ and $v$ over the channel. This releases an emission $e(k,v)$. We wish to select the camouflage values $v(k)$ as a function of $k$ in a way that makes the quantities $e(k,v(k))$ as {\sl indistinguishable} as possible from each other. We model the problem and show that optimal camouflage values can be computed from side-channels under very weak physical assumptions. The proposed technique is hence applicable to a wide range of readily available technologies. We propose algorithms for computing optimal camouflage values when the number of samples per trace is moderate (typically $\leq 6$) and justify our models by a statistical analysis. We also provide experimental results obtained using FPGAs.

The primitive of deniable encryption was first introduced by Canetti et al. (CRYPTO, 1997). Deniable encryption is a regular public key encryption scheme with the added feature that after running the protocol honestly and transmitting a message $m$, both Sender and Receiver may produce random coins showing that the transmitted ciphertext was an encryption of any message $m'$ in the message space. Deniable encryption is a key tool for constructing incoercible protocols, since it allows a party to send one message and later provide apparent evidence to a coercer that a different message was sent. In addition, deniable encryption may be used to obtain \emph{adaptively}-secure multiparty computation (MPC) protocols and is secure under \emph{selective-opening} attacks. Different flavors such as sender-deniable and receiver-deniable encryption, where only the Sender or Receiver can produce fake random coins, have been considered. Recently, several open questions regarding the feasibility of deniable encryption have been resolved (c.f. (O'Neill et al., CRYPTO, 2011), (Bendlin et al., ASIACRYPT, 2011)). A fundamental remaining open question is whether it is possible to construct sender-deniable Encryption Schemes with super-polynomial security, where an adversary has negligible advantage in distinguishing real and fake openings. The primitive of simulatable public key encryption (PKE), introduced by Damgård and Nielsen (CRYPTO, 2000), is a public key encryption scheme with additional properties that allow oblivious sampling of public keys and ciphertexts. It is one of the low-level primitives used to construct adaptively-secure MPC protocols and was used by O'Neill et al. in their construction of bi-deniable encryption in the multi-distributional model (CRYPTO, 2011). Moreover, the original construction of sender-deniable encryption with polynomial security given by Canetti et al. can be instantiated with simulatable PKE. Thus, a natural question to ask is whether it is possible to construct sender-deniable encryption with \emph{super-polynomial security} from simulatable PKE. In this work, we investigate the possibility of constructing sender-deniable public key encryption from the primitive of simulatable PKE in a black-box manner. We show that, in fact, there is no black-box construction of sender-deniable encryption with super-polynomial security from simulatable PKE. This indicates that the original construction of sender-deniable public key encryption given by Canetti et al. is in some sense optimal, since improving on it will require the use of non-black-box techniques, stronger underlying assumptions or interaction.

This paper presents some proposals of protocols for two types of schemes such as verifiable delegation of computation and remote electronic voting, based on polynomial properties. Our protocols for verifiable delegation of computation are aimed to the efficient evaluation of polynomials, working on schemes where the polynomial and/or the input are kept secret to the server. Our proposal for remote electronic voting allows the verification of vote well-formation upon reception at the voting server, with little overhead of computations for the voter.

Recently, He et al. (Computers and Mathematics with Applications, 2012, 64(6): 1914-1926) proposed a new efficient certificateless two-party authenticated key agreement protocol. They claimed their protocol was provably secure in the extended Canetti-Krawczyk (eCK) model. In this paper, we will show that their protocol is insecure. A type I adversary, who obtains one party's ephemeral private key, can impersonate the party to cheat the other party and compute the shared session key successfully. For overcoming this weakness, we also propose a simple countermeasure.

Inspired by cold boot attacks, Heninger and Shacham (Crypto 2009) initiated the study of the problem of how to recover an RSA private key from a noisy version of that key. They gave an algorithm for the case where some bits of the private key are known with certainty. Their ideas were extended by Henecka, May and Meurer (Crypto 2010) to produce an algorithm that works when all the key bits are subject to error. In this paper, we bring a coding-theoretic viewpoint to bear on the problem of noisy RSA key recovery. This viewpoint allows us to cast the previous work as part of a more general framework. In turn, this enables us to explain why the previous algorithms do not solve the motivating cold boot problem, and to design a new algorithm that does (and more). In addition, we are able to use concepts and tools from coding theory -- channel capacity, list decoding algorithms, and random coding techniques -- to derive bounds on the performance of the previous algorithms and our new algorithm.

In order to prevent the SPA (Simple Power Analysis) attack against modular exponentiation algorithms, a multiply-always implementation is generally used. Witteman et al. introduced in \cite{WI} a new cross-correlation power analysis attack against the multiply-always implementation. We suggest two new algorithms, resistant to this attack and also to other known attacks. The first algorithm is an alternative approach to exponentiation algorithms used in cryptography, which usually receive as an input some representation (e.g. binary) of the exponent. In our approach both the exponent and the result are functions (not necessarily easily invertible) of the exponentiation algorithm input. We show that this approach can have a good performance and that it is also resistant to several known attacks, especially to the cross-correlation power analysis. It is particularly relevant for cryptographic schemes in which the private exponent can be chosen arbitrarily. Another exponentiation algorithm that we present here may be preferable for use with RSA in certain settings. It is resistant to the cross-correlation power analysis attack, C safe error attack, and other attacks; although it involves squaring operations.

The focus of this work is hardness-preserving transformations of somewhat limited pseudorandom functions families (PRFs) into ones with more versatile characteristics. Consider the problem of domain extension of pseudorandom functions: given a PRF that takes as input elements of some domain $\mathcal{U}$, we would like to come up with a PRF over a larger domain. Can we do it with little work and without significantly impacting the security of the system? One approach is to first hash the larger domain into the smaller one and then apply the original PRF. Such a reduction, however, is vulnerable to a "birthday attack": after $\sqrt{|\mathcal{U}|}$ queries to the resulting PRF, a collision (i.e., two distinct inputs having the same hash value) is very likely to occur. As a consequence, the resulting PRF is insecure against an attacker making this number of queries. In this work we show how to go beyond the aforementioned birthday attack barrier by replacing the above simple hashing approach with a variant of cuckoo hashing, a hashing paradigm that resolves collisions in a table by using two hash functions and two tables, cleverly assigning each element to one of the two tables. We use this approach to obtain: (i) a domain extension method that requires just two calls to the original PRF, can withstand as many queries as the original domain size, and has a distinguishing probability that is exponentially small in the amount of non-cryptographic work; and (ii) a security-preserving reduction from non-adaptive to adaptive PRFs.

The Fiat-Shamir paradigm was proposed as a way to remove interaction from 3-round proof of knowledge protocols and derive secure signature schemes. This generic transformation leads to very efficient schemes and has thus grown quite popular. However, this transformation is proven secure only in the random oracle model. In FOCS 2003, Goldwasser and Kalai showed that this transformation is provably insecure in the standard model by presenting a counterexample of a 3-round protocol, the Fiat-Shamir transformation of which is (although provably secure in the random oracle model) insecure in the standard model, thus showing that the random oracle is uninstantiable. In particular, for every hash function that is used to replace the random oracle, the resulting signature scheme is existentially forgeable. This result was shown by relying on the non-black-box techniques of Barak (FOCS 2001). An alternative to the Fiat-Shamir paradigm was proposed by Fischlin in Crypto 2005. Fischlin\rq{}s transformation can be applied to any so called 3-round ``Fiat-Shamir proof of knowledge\rq{}\rq{} and can be used to derive non-interactive zero-knowledge proofs of knowledge as well as signature schemes. An attractive property of this transformation is that it provides online extractability (i.e., the extractor works without having to rewind the prover). Fischlin remarks that in comparison to the Fiat-Shamir transformation, his construction tries to ``decouple the hash function from the protocol flow" and hence, the counterexample in the work of Goldwaaser and Kalai does not seem to carry over to this setting. In this work, we show a counterexample to the Fischlin's transformation. In particular, we construct a 3-round Fiat-Shamir proof of knowledge (on which Fischlin's transformation is applicable), and then, present an adversary against both - the soundness of the resulting non-interactive zero-knowledge, as well as the unforegeability of the resulting signature scheme. Our attacks are successful except with negligible probability for any hash function, that is used to instantiate the random oracle, provided that there is an apriori (polynomial) bound on the running time of the hash function. By choosing the right bound, secure instantiation of Fischlin transformation with most practical cryptographic hash functions can be ruled out. The techniques used in our work are quite unrelated to the ones used in the work of Goldwasser and Kalai. Our primary technique is to bind the protocol flow with the hash function if the code of the hash function is available. We believe that our ideas are of independent interest and maybe applicable in other related settings.

Many index calculus algorithms generate multiplicative relations between smoothness basis elements by using a process called {\it Sieving}. This process allows to filter potential candidate relations very quickly, without spending too much time to consider bad candidates. However, from an asymptotic point of view, there is not much difference between sieving and straightforward testing of candidates. The reason is that even when sieving, some small amount time is spend for each bad candidates. Thus, asymptotically, the total number of candidates contributes to the complexity. In this paper, we introduce a new technique: {\it Pinpointing}, which allows us to construct multiplicate relations much faster, thus reducing the asymptotic complexity of relations' construction. Unfortunately, we only know how to implement this technique for finite fields which contain a medium-sized subfield. When applicable, this method improves the asymptotic complexity of the index calculus algorithm in the cases where the sieving phase dominates. In practice, it gives a very interesting boost to the performance of state-of-the-art algorithms. We illustrate the feasability of the method with a discrete logarithm record in medium prime finite fields of sizes 1175~bits and 1425~bits.

How to construct an ideal multi-secret sharing scheme for general access structures is difficult. In this paper, we solve an open problem proposed by Spiez et al.recently [Finite Fields and Their Application, 2011(17) 329-342], namely to design an algorithm of privileged coalitions of any length if such coalitions exist. Furthermore, in terms of privileged coalitions, we show that most of the existing multi-secret sharing schemes based on Shamir threshold secret sharing are not perfect by analyzing Yang et al.'s scheme and Pang et al.'s scheme. Finally, based on the algorithm mentioned above, we devise an ideal multi-secret sharing scheme for families of access structures, which possesses more vivid authorized sets than that of the threshold scheme.

\emph{Succinct non-interactive arguments} (SNARGs) enable verifying NP statements with lower complexity than required for classical NP verification. Traditionally, the focus has been on minimizing the length of such arguments; nowadays researches have focused also on minimizing verification time, by drawing motivation from the problem of delegating computation. A common relaxation is a \emph{preprocessing} SNARG, which allows the verifier to conduct an expensive offline phase that is independent of the statement to be proven later. Recent constructions of preprocessing SNARGs have achieved attractive features: they are publicly-verifiable, proofs consist of only $O(1)$ encrypted (or encoded) field elements, and verification is via arithmetic circuits of size linear in the NP statement. Additionally, these constructions seem to have ``escaped the hegemony'' of probabilistically-checkable proofs (PCPs) as a basic building block of succinct arguments. We present a general methodology for the construction of preprocessing SNARGs, as well as resulting concrete efficiency improvements. Our contribution is three-fold: (1) We introduce and study a natural extension of the interactive proof model that considers \emph{algebraically-bounded} provers; this new setting is analogous to the common study of algebraically-bounded ``adversaries'' in other fields, such as pseudorandomness and randomness extraction. More concretely, in this work we focus on linear (or affine) provers, and provide several constructions of (succinct two-message) \emph{linear-interactive proofs} (LIPs) for NP. Our constructions are based on general transformations applied to both \emph{linear} PCPs (LPCPs) and traditional ``unstructured" PCPs. (2) We give conceptually simple cryptographic transformations from LIPs to preprocessing SNARGs, whose security can be based on different forms of \emph{linear targeted malleability} (implied by previous knowledge assumptions). Our transformations convert arbitrary (two-message) LIPs into designated-verifier SNARGs, and LIPs with degree-bounded verifiers into publicly-verifiable SNARGs. We also extend our methodology to obtain \emph{zero-knowledge} LIPs and SNARGs. Our techniques yield SNARGs \emph{of knowledge} and thus can benefit from known recursive composition and bootstrapping techniques. (3) Following this methodology, we exhibit several constructions achieving new efficiency features, such as ``single-ciphertext preprocessing SNARGs" and improved succinctness-soundness tradeoffs. We also offer a new perspective on existing constructions of preprocessing SNARGs, revealing a direct connection of these to LPCPs and LIPs.

Password-authenticated secret sharing (PASS) schemes, first introduced by Bagherzandi et al. at CCS 2011, allow users to distribute data among several servers so that the data can be recovered using a single humanmemorizable password, but no single server (or collusion of servers up to a certain size) can mount an off-line dictionary attack on the password or learn anything about the data. We propose a new, universally composable (UC) security definition for the two-server case (2PASS) in the public-key setting that addresses a number of relevant limitations of the previous, non-UC definition. For example, our definition makes no prior assumptions on the distribution of passwords, preserves security when honest users mistype their passwords, and guarantees secure composition with other protocols in spite of the unavoidable non-negligible success rate of online dictionary attacks. We further present a concrete 2PASS protocol and prove that it meets our definition. Given the strong security guarantees, our protocol is surprisingly efficient: in its most efficient instantiation under the DDH assumption in the random-oracle model, it requires fewer than twenty elliptic-curve exponentiations on the user's device. We achieve our results by careful protocol design and by exclusively focusing on the two-server public-key setting.

We introduce a broad lattice manipulation technique for expressive cryptography, and use it to realize functional encryption for access structures from post-quantum hardness assumptions. Specifically, we build an efficient key-policy attribute-based encryption scheme, and prove its security in the selective sense from learning-with-errors intractability in the standard model.

SAFER\scriptsize + \normalsize was a candidate block cipher for AES with 128-bit block size and a variable key sizes of 128, 192 or 256 bits. Bluetooth uses customized versions of SAFER\scriptsize + \normalsize for security. The numbers of rounds for SAFER\scriptsize + \normalsize with key sizes of 128, 192 and 256 are 8, 12 and 16, respectively. SAFER\scriptsize ++\normalsize, a variant of SAFER\scriptsize +\normalsize, was among the cryptographic primitives selected for the second phase of the NESSIE project. The block size is 128 bits and the key size can take either 128 or 256 bits. The number of rounds are 7 for SAFER\scriptsize ++ \normalsize/128 and 10 for SAFER\scriptsize ++ \normalsize/256. Both ciphers use PHT as their linear transformations. In this paper, we take advantage of properties of PHT and S-boxes to identify 3.75-round impossible differentials for SAFER\scriptsize ++ \normalsize and 2.75-round impossible differentials for SAFER\scriptsize +\normalsize, which result in impossible differential attacks on 4-round SAFER\scriptsize +\normalsize/128(256), 5-round SAFER\scriptsize ++\normalsize/128 and 5.5-round SAFER\scriptsize ++\normalsize/256. Our attacks significantly improve previously known impossible differential attacks on 3.75-round SAFER\scriptsize +\normalsize/128(256) and SAFER\scriptsize ++\normalsize/128(256). Our attacks on SAFER\scriptsize +\normalsize/128(256) and SAFER\scriptsize ++\normalsize/256 represent the best currently known attack in terms of the number of rounds.

The classic Leftover Hash Lemma (LHL) is one of the most useful tools in cryptography, and is often used to argue that certain distributions arising from modular subset-sums are close to uniform over some finite domain. Though extremely useful and powerful in general, the applicability of the leftover hash lemma to lattice based cryptography is limited for two reasons. First, typically the distributions we care about in lattice-based cryptography are {\em discrete Gaussians}, not uniform. Second, the elements chosen from these discrete Gaussian distributions lie in an infinite domain: a lattice rather than a finite field. In this work we prove a ``lattice world" analog of LHL over infinite domains, proving that certain ``generalized subset sum'' distributions are statistically close to well behaved discrete Gaussian distributions, even without any modular reduction. Specifically, given many vectors $\{\vec x_i\}_{i=1}^m$ from some lattice $L\subset\R^n$, we analyze the probability distribution $\sum_{i=1}^m z_i \vec x_i$ where the integer vector $\vec z \in \Z^m$ is chosen from a discrete Gaussian distribution. We show that when the $\vec x_i$'s are ``random enough'' and the Gaussian from which the $\vec z$'s are chosen is ``wide enough'', then the resulting distribution is statistically close to a near-spherical discrete Gaussian over the lattice $L$. Beyond being interesting in its own right, this ``lattice-world" analog of LHL has applications for the new construction of multilinear maps \cite{GGH12}, where it is used to sample Discrete Gaussians obliviously. Specifically, given encoding of the $\vec x_i$'s, it is used to produce an encoding of a near-spherical Gaussian distribution over the lattice. We believe that our new lemma will have other applications, and sketch some plausible ones in this work.

Embedded computing devices (such as actuators, controllers and sensors of various sizes) increasingly permeate many aspects of modern life: from medical to automotive, from building and factory automation to weapons, from critical infrastructures to home entertainment. Despite their specialized nature as well as limited resources and connectivity, these devices are now becoming increasingly popular and attractive targets for various attacks, especially, remote malware infestations. There has been a number of research proposals to detect and/or mitigate such attacks. They vary greatly in terms of application generality and underlying assumptions. However, one common theme is the need for Remote Attestation, a distinct security service that allows a trusted party (verifier) to check the internal state of a remote untrusted embedded device (prover). This paper provides a systematic treatment of Remote Attestation, starting with a precise definition of the desired service and proceeding to its systematic deconstruction into necessary and sufficient properties. These properties are, in turn, mapped into a minimal collection of hardware and software components that results in secure Remote Attestation. One distinguishing feature of this line of research is the need to prove (or, at least argue) architectural minimality; this is rarely encountered in security research. This work also offers some insights into vulnerabilities of certain prior techniques and provides a promising platform for attaining more advanced security services and guarantees.

PRINCE is a modern involutive lightweight cipher which was proposed by Rechberger et al. in 2012. PRINCE uses 64-bit core cipher, which holds the major encryption logic and is wrapped by two key additions. Thus, the security of the cipher is mainly depending on the security properties of the core. In this paper, we present an independent-biclique attack on the full version and also a differential inside-out cryptanalysis on the round-reduced version of the core of PRINCE.

Goldreich and Oren (JoC'94) show that only languages in BPP have 2-message zero-knowledge arguments. In this paper we consider weaker, super-polynomial simulation (SPS), notions of zero-knowledge. We present barriers to using black-box reductions for demonstrating soundness of 2-message protocols with efficient prover strategies satisfying SPS zero-knowledge. More precisely, if $poly(T(n))$-hard one-way functions exist for a super-polynomial $T(n)$, the following holds about 2-message efficient prover arguments over statements of length $n$. 1. Black-box reductions cannot prove soundness of 2-message $T(n)$-simulatable arguments based on any polynomial-time intractability assumption, unless the assumption can be broken in polynomial time. This complements known 2-message quasi-polynomial-time simulatable arguments using a quasi-polynomial-time reduction (Pass'03), and 2-message exponential-time simulatable proofs using a polynomial-time reduction (Dwork-Naor'00, Pass'03). 2. Back-box reductions cannot prove soundness of 2-message strong $T(n)$-simulatable arguments, even if the reduction and the challenger both can run in $poly(T(n))$-time, unless the assumption can be broken in $poly(T(n))$ time. Strong $T(\cdot)$-simulatability means that the output of the simulator is indistinguishable also for $poly(T(\cdot))$-size circuits, with a $negl(T(\cdot))$ indistinguishability gap. This complements known 3-message strong quasi-polynomial-time simulatable proofs (Blum'86, Canetti et~al'~00), or 2-message quasi-polynomial-time simulatable arguments (Khurana-Sahai'17, Kalai-Khurana-Sahai'18) satisfying a relaxed notion of strong simulation where the distinguisher's size can be large, but the distinguishing gap is negligible in $n$.

The Random Oracle Model, introduced by Bellare and Rogaway, provides a method to heuristically argue about the security of cryptographic primitives and protocols. The basis of this heuristic is that secure hash functions are close enough to random functions in their behavior, and so, a primitive that is secure using a random function should continue to remain secure even when the random function is replaced by a real hash function. In the security proof, this setting is realized by modeling the hash function as a random oracle. However, this approach in particular also enables any reduction, reducing a hard problem to the existence of an adversary, to \emph{observe} the queries the adversary makes to its random oracle and to \emph{program} the responses that the oracle provides to these queries. While, the issue of programmability of query responses has received a lot of attention in the literature, to the best of our knowledge, observability of the adversary's queries has not been identified as an artificial artefact of the Random Oracle Model. In this work, we study the security of several popular schemes when the security reduction cannot ``observe'' the adversary's queries to the random oracle, but can (possibly) continue to ``program'' the query responses. We first show that RSA-PFDH and Schnorr's signatures continue to remain secure when the security reduction is non observing (NO reductions), which is not surprising as their proofs in the random oracle model rely on programmability. We also provide two example schemes, namely, Fischlin's NIZK-PoK \cite{Fischlin05} and non interactive extractable commitment scheme, extractor algorithms of which seem to rely on observability in the random oracle model. While we prove that Fischlin's online extractors cannot exist when they are non observing, our extractable commitment scheme continues to be secure even when the extractors are non observing. We also introduce Non Observing Non Programming reductions which we believe are closest to standard model reductions.

This paper studies the distinctness of primitive sequences over Z/(M) modulo 2, where M is an odd integer that is composite and square-free, and Z/(M) is the integer residue ring modulo M. A new sufficient condition is given for ensuring that primitive sequences generated by a primitive polynomial f(x) over Z/(M) are pairwise distinct modulo 2. Such result improves a recent result obtained in our previous paper [27] and consequently the set of primitive sequences over Z/(M) that can be proven to be distinct modulo 2 is greatly enlarged.

We introduce the notion of covert security with public verifiability, building on the covert security model introduced by Aumann and Lindell (TCC 2007). Protocols that satisfy covert security guarantee that the honest parties involved in the protocol will notice any cheating attempt with some constant probability $\epsilon$. The idea behind the model is that the fear of being caught cheating will be enough of a deterrent to prevent any cheating attempt. However, in the basic covert security model, the honest parties are not able to persuade any third party (say, a judge) that a cheating occurred. We propose (and formally define) an extension of the model where, when an honest party detects cheating, it also receives a certificate that can be published and used to persuade other parties, without revealing any information about the honest party's input. In addition, malicious parties cannot create fake certificates in the attempt of framing innocents. Finally, we construct a secure two-party computation protocol for any functionality $f$ that satisfies our definition, and our protocol is almost as efficient as the one of Aumann and Lindell. We believe that the fear of a public humiliation or even legal consequences vastly exceeds the deterrent given by standard covert security. Therefore, even a small value of the deterrent factor $\epsilon$ will suffice in discouraging any cheating attempt. As the overall complexity of covert security and the parameter $\epsilon$ are inversely proportional to each other, we believe that the small price to pay to get the public verifiability property on top of covert security will be dominated by the efficiency gain obtained by using a smaller value $\epsilon$.

WIDEA is a family of block ciphers designed by Junod and Macchetti in 2009 as an extension of IDEA to larger block sizes (256 and 512 bits for the main instances WIDEA-4 and WIDEA-8) and key sizes (512 and 1024 bits), with a focus on using them to design a hash function. WIDEA is based on the trusted IDEA design, and was expected to inherit its good security properties. WIDEA-w is composed of w parallel copies of the IDEA block cipher, with an MDS matrix to provide diffusion between them. In this paper we present low complexity attacks on WIDEA based on truncated differentials. We show a distinguisher for the full WIDEA with complexity only 2^65, and we use the distinguisher in a key-recovery attack with complexity w·2^68. We also show a collision attack on WIDEA-8 if it is used to build a hash function using the Merkle-Damgård mode of operation. The attacks exploit the parallel structure of WIDEA and the limited diffusion between the IDEA instances, using differential trails where the MDS diffusion layer is never active. In addition, we use structures of plaintext to reduce the data complexity.

The Fiat-Shamir paradigm [CRYPTO'86] is a heuristic for converting 3-round identification schemes into signature schemes, and more generally, for collapsing rounds in public-coin interactive protocols. This heuristic is very popular both in theory and in practice, and many researchers have studied its security (and insecurity). In this work, we continue this study. As our main result, we show that for many well studied interactive *proofs* (and arguments) the soundness of the Fiat-Shamir heuristic cannot be proven via a black-box reduction to any falsifiable assumption. Previously, the insecurity of this paradigm was exemplified only when applied to interactive arguments (as opposed to proofs). Using similar techniques, we also show a black-box impossibility result for Micali's CS-proofs [FOCS'94]. Namely, we prove that there exist PCPs such that for "sufficiently hard'' NP languages, Micali's CS-proof cannot be proven sound via black-box reduction to any falsifiable assumption. These results are obtained by extending the impossibility of two-message zero knowledge protocols due to Goldreich and Oren [J. Cryptology'94].

The Fiat-Shamir heuristic (CRYPTO '86) is used to convert any 3-message public-coin proof or argument system into a non-interactive argument, by hashing the prover's first message to select the verifier's challenge. It is known that this heuristic is sound when the hash function is modeled as a random oracle. On the other hand, the surprising result of Goldwasser and Kalai (FOCS '03) shows that there exists a computationally sound argument on which the Fiat-Shamir heuristic is never sound, when instantiated with any actual efficient hash function. This leaves us with the following interesting possibility: perhaps there exists a hash function that securely instantiates the Fiat-Shamir heuristic for all 3-message public-coin statistically sound proofs, even if it can fail for some computationally sound arguments. Indeed, the existence of such hash functions has been conjectured by Barak, Lindell and Vadhan (FOCS '03), who also gave a seemingly reasonable and sufficient condition under which such hash functions exist. However, we do not have any provably secure construction of such hash functions, under any standard assumption such as the hardness of DDH, RSA, QR, LWE, etc. In this work we give a broad black-box separation result, showing that the security of such hash functions cannot be proved under virtually any standard cryptographic assumption via a black-box reduction.

The Fiat-Shamir transform is a well studied paradigm for removing interaction from public-coin protocols. We investigate whether the resulting non-interactive zero-knowledge (NIZK) proof systems also exhibit non-malleability properties that have up to now only been studied for NIZK proof systems in the common reference string model: first, we formally define simulation soundness and a weak form of simulation extraction in the random oracle model (ROM). Second, we show that in the ROM the Fiat-Shamir transform meets these properties under lenient conditions. A consequence of our result is that, in the ROM, we obtain truly efficient non malleable NIZK proof systems essentially for free. Our definitions are sufficient for instantiating the Naor-Yung paradigm for CCA2-secure encryption, as well as a generic construction for signature schemes from hard relations and simulation-extractable NIZK proof systems. These two constructions are interesting as the former preserves both the leakage resilience and key-dependent message security of the underlying CPA-secure encryption scheme, while the latter lifts the leakage resilience of the hard relation to the leakage resilience of the resulting signature scheme.

An embedded cryptographic device performs operation on sensitive data and as such, is vulnerable to side-channel attacks. This forces smart-card manufacturers to carefully consider development of security mechanisms. To accelerate this procedure, the use of power and electromagnetic simulator can be relevant and saves non negligible time. Based on a high level simulator, we propose to use profiled abstract models to gain accuracy on the simulated traces. These abstract models are obtained by profiling some parts of the target device which is physically available by the evaluator.

Tian et al. proposed a novel ultralightweight RFID mutual authentication protocol [4] that has recently been analyzed in [1], [2], [5]. In this letter, we first propose a desynchronization attack that succeeds with probability almost 1, which improves upon the 0.25 given by the attack in [1]. We also show that the bad properties of the proposed permutation function can be exploited to disclose several bits of the tag’s secret (rather than just one bit as in [2]), which increases the power of a traceability attack. Finally, we show how to extend the above attack to run a full disclosure attack, which requires to eavesdrop less protocol runs than the attack described in [5] (i.e., 192 << 230).

We discuss how to recover RSA secret keys from noisy key bits with erasures and errors. There are two known algorithms recovering original secret keys from noisy keys. At Crypto 2009, Heninger and Shacham proposed a method for the case where an erroneous version of secret keys contains only erasures. Subsequently, Henecka et al. proposed a method for an erroneous version containing only errors at Crypto2010. For physical attacks such as side-channel and cold boot attacks, we need to study key recovery from a noisy secret key containing both erasures and errors. In this paper, we propose a method to recover a secret key from such an erroneous version and analyze the condition for error and erasure rates so that our algorithm succeeds in finding the correct secret key in polynomial time. We also evaluate a theoretical bound to recover the secret key and discuss to what extent our algorithm achieves this bound.

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.

We conduct a study of public-key cryptosystems based on variants of the Learning Parity with Noise (LPN) problem. The main LPN variant in consideration was introduced by Alekhnovich (FOCS 2003), and we describe several improvements to the originally proposed scheme, inspired by similar existing variants of Regev's LWE-based cryptosystem. To achieve further efficiency, we propose the first public-key cryptosystem based on the ring-LPN problem, which is a more recently introduced LPN variant that makes for substantial improvement in terms of both time and space. We also introduce a variant of this problem called the transposed Ring-LPN problem. Our public-key scheme based on this problem is even more efficient. For all cases, we compute the parameters required for various security levels in practice, given the best currently known attacks. Our conclusion is that the basic LPN-based scheme is in several respects not competitive with existing practical schemes, as the public key, ciphertexts and encryption time become very large already for 80-bit security. On the other hand, the scheme based on transposed Ring-LPN is far better in all these respects. Although the public key and ciphertexts are still larger than for, say, RSA at comparable security levels, they are not prohibitively large; moreover, for decryption, the scheme outperforms RSA for security levels of 112 bits or more. The Ring-LPN based scheme is less efficient, however. Thus, LPN-based public-key cryptography seems to be somewhat more promising for practical use than has been generally assumed so far.

In this paper we consider the problem of secure pattern matching that allows single-character wildcards and substring matching in the malicious (stand-alone) setting. Our protocol, called 5PM, is executed between two parties: Server, holding a text of length $n$, and Client, holding a pattern of length $m$ to be matched against the text, where our notion of matching is more general and includes non-binary alphabets, non-binary Hamming distance and non-binary substring matching. 5PM is the first secure expressive pattern matching protocol designed to optimize round complexity by carefully specifying the entire protocol round by round. In the malicious model, 5PM requires $O((m+n)k^2)$ bandwidth and $O(m+n)$ encryptions, where $m$ is the pattern length and $n$ is the text length. Further, 5PM can hide pattern size with no asymptotic additional costs in either computation or bandwidth. Finally, 5PM requires only two rounds of communication in the honest-but-curious model and eight rounds in the malicious model. Our techniques reduce pattern matching and generalized Hamming distance problems to a novel linear algebra formulation that allows for generic solutions based on any additively homomorphic encryption. We believe our efficient algebraic techniques are of independent interest.

In order to guarantee a fair and transparent voting process, electronic voting schemes must be verifiable. Most of the time, however, it is important that elections also be anonymous. The notion of a verifiable shuffle describes how to satisfy both properties at the same time: ballots are submitted to a public bulletin board in encrypted form, verifiably shuffled by several mix servers (thus guaranteeing anonymity), and then verifiably decrypted by an appropriate threshold decryption mechanism. To guarantee transparency, the intermediate shuffles and decryption results, together with proofs of their correctness, are posted on the bulletin board throughout this process. In this paper, we present a verifiable shuffle and threshold decryption scheme in which, for security parameter k, L voters, M mix servers, and N decryption servers, the proof that the end tally corresponds to the original encrypted ballots is only O(k(L + M + N)) bits long. Previous verifiable shuffle constructions had proofs of size O(kLM + kLN), which, for elections with thousands of voters, mix servers, and decryption servers, meant that verifying an election on an ordinary computer in a reasonable amount of time was out of the question. The linchpin of each construction is a controlled-malleable proof (cm-NIZK), which allows each server, in turn, to take a current set of ciphertexts and a proof that the computation done by other servers has proceeded correctly so far. After shuffling or partially decrypting these ciphertexts, the server can also update the proof of correctness, obtaining as a result a cumulative proof that the computation is correct so far. In order to verify the end result, it is therefore sufficient to verify just the proof produced by the last server.

RAKAPOSHI is a hardware oriented stream cipher designed by Carlos Cid et al. in 2009. The stream cipher is based on Dynamic Linear Feedback Shift Registers, with a simple and potentially scalable design, and is particularly suitable for hardware applications with restricted resources. The RAKAPOSHI stream cipher offers 128-bit security. In this paper, we point out some weaknesses in the cipher. Firstly, it shows that there are 2^192 weak (key, IV) pairs in RAKAPOSHI stream cipher. Secondly, for weak (key, IV) pairs of RAKAPOSHI, they are vulnerable to linear distinguishing attack and algebraic attack. Finally, we propose a real time related key chosen IV attack on RAKAPOSHI. The attack on RAKAPOSHI recovers the 128-bit secret key of with a computational complexity of 2^37, requiring 47 related keys, 2^8 chosen IVs and 2^14.555 keystream bits. The success probability of this attack is 0.999, which is quite close to 1. The experimental results corroborate our assertion.

Computer-aided verification provides effective means of analyzing the security of cryptographic primitives. However, it has remained a challenge to achieve fully automated analyses yielding guarantees that hold against computational (rather than symbolic) attacks. This paper meets this challenge for public-key encryption schemes built from trapdoor permutations and hash functions. Using a novel combination of techniques from computational and symbolic cryptography, we present proof systems for analyzing the chosen-plaintext and chosen-ciphertext security of such schemes in the random oracle model. Building on these proof systems, we develop a toolset that bundles together fully automated proof and attack finding algorithms. We use this toolset to build a comprehensive database of encryption schemes that records attacks against insecure schemes, and proofs with concrete bounds for secure ones.

In this paper we cryptanalyze two protocols: Grigoriev-Shpilrain authentication protocol and Wang et al. public key encryption protocols that use computational hardness of some variations of the conjugacy search problem in noncommutative monoids. We devise a practical heuristic algorithm solving those problems. As a conclusion we claim that these protocols are insecure for the proposed parameter values.

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

In this paper we investigate the topic of integrated public-key encryption (PKE) and public-key encryption with keyword search (PEKS) schemes (PKE-PEKS as shorthand). We first formalize the strongest security notion to date for PKE-PEKS schemes, named joint CCA-security. We then propose two simple constructions of jointly CCA-secure PKE- PEKS schemes from anonymous (hierarchical) identity-based encryption schemes. Besides, we also define the notion of consistency for PKE-PEKS schemes, as well as revisit its related notions (including consistency of PEKS schemes, robustness and collision-freeness of IBE schemes), which may be of independent interest.

The general number field sieve (GNFS) is the most efficient algorithm known for factoring large integers. It consists of several stages, the first one being polynomial selection. The quality of the chosen polynomials in polynomial selection can be modelled in terms of size and root properties. In this paper, we describe some algorithms for selecting polynomials with very good root properties.

In this paper, we concentrate on the security issues of the integrity protection of LTE and present two different forgery attacks. For the first attack, referred to as a {\em linear forgery attack}, EIA1 and EIA3, two integrity protection algorithms of LTE, are insecure if the initial value (IV) can be repeated twice during the life cycle of an integrity key (IK). Because of the linearity of EIA1 and EIA3, given two valid Message Authentication Codes (MACs) our algorithm can forge up to $2^{32}$ valid MACs. Thus, the probability of finding a valid MAC is dramatically increased. Although the combination of IV and IK never repeats in the ordinary case, in our well-designed scenario, the attacker can make the same combination occur twice. The duplication provides the opportunity to conduct our linear forgery attack, which may harm the security of communication. To test our linear forgery attack algorithm, we generate two counter check messages and successfully forge the third one. We also examine the attack timing by simulating real communication. From the experimental results, our attack is applicable. The second attack is referred to as a {\em trace extension forgery attack}, which works only in theory. However, this attack is more general than the linear forgery attack. Known only one MAC and message pair, we can construct a different message, who has the same MAC as the original one, with the probability $\frac{1}{2^{16}}$. In this attack, trace function is applied to the message to shrink the guessing space.

A \captcha is a puzzle that is easy for humans but hard to solve for computers. A formal framework, modelling \captcha puzzles (as hard AI problems), was introduced by Ahn, Blum, Hopper, and Langford (\cite{AhnBHL03}, Eurocrypt 2003). Despite their attractive features and wide adoption in practice, the use of \captcha puzzles for general cryptographic applications has been limited. In this work, we explore various ways to formally model \captcha puzzles and their human component and explore new applications for \captcha. We show that by defining \captcha with additional (strong but realistic) properties, it is possible to broaden \captcha applicability, including using it to learning a machine's ``secret internal state.'' To facilitate this, we introduce the notion of an human-extractable \captcha, which we believe may be of independent interest. We show that this type of \captcha yields a \emph{constant round} protocol for \emph{fully} concurrent non-malleable zero-knowledge. To enable this we also define and construct a \captcha -based commitment scheme which admits ``straight line'' extraction. We also explore \captcha definitions in the setting of Universal Composability (UC). We show that there are two (incomparable) ways to model \captcha within the UC framework that lead to different results. In particular, we show that in the so called \emph{indirect access model}, for every polynomial time functionality $\calf$ there exists a protocol that UC-realizes $\calf$ using human-extractable \captcha, while for the so-called \emph{direct access model}, UC is impossible, even with the help of human-extractable \captcha. The security of our constructions using human-extractable \captcha is proven against the (standard) class of all polynomial time adversaries. In contrast, most previous works guarantee security only against a very limited class of adversaries, called the \emph{conservative} adversaries.

We use the learning with errors (LWE) problem to build a new simple and provably secure key exchange scheme. The basic idea of the construction can be viewed as certain extension of Diffie-Hellman problem with errors. The mathematical structure behind comes from the commutativity of computing a bilinear form in two different ways due to the associativity of the matrix multiplications:$$(\mathbf{x}^t \times \mathbf{A})\times \mathbf{y}=\mathbf{x}^t \times (\mathbf{A}\times \mathbf{y}),$$ where $\mathbf{x,y}$ are column vectors and $\mathbf{A}$ is a square matrix. We show that our new schemes are more efficient in terms of communication and computation complexity compared with key exchange schemes or key transport schemes via encryption schemes based on the LWE problem. Furthermore, we extend our scheme to the ring learning with errors (RLWE) problem, resulting in small key size and better efficiency.

Over the past decade bilinear maps have been used to build a large variety of cryptosystems. In addition to new functionality, we have concurrently seen the emergence of many strong assumptions. In this work, we explore how to build bilinear map cryptosystems under progressively weaker assumptions. We propose $k$-BDH, a new family of progressively weaker assumptions that generalizes the decisional bilinear Diffie-Hellman (DBDH) assumption. We give evidence in the generic group model that each assumption in our family is strictly weaker than the assumptions before it. DBDH has been used for proving many schemes secure, notably identity-based and functional encryption schemes; we expect that our $k$-BDH will lead to generalizations of many such schemes. To illustrate the usefulness of our $k$-BDH family, we construct a family of selectively secure Identity-Based Encryption (IBE) systems based on it. Our system can be viewed as a generalization of the Boneh-Boyen IBE, however, the construction and proof require new ideas to fit the family. We then extend our methods to produces hierarchical IBEs and CCA security; and give a fully secure variant. In addition, we discuss the opportunities and challenges of building new systems under our weaker assumption family.

Grøstl is one of the five finalists in the third round of SHA-3 competition hosted by NIST. In this paper, we use many techniques to improve the pseudo preimage attack on Grøstl hash function, such as subspace preimage attack and guess-and-determine technique. We present improved pseudo preimage attacks on 5-round Grøstl-256 and 8-round Grøstl-512 respectively. The complexity of the above two attacks are ($2^{239.90},2^{240.40}$) (in time and memory) and ($2^{499.50},2^{499}$) respectively. Furthermore, we propose pseudo preimage attack and pseudo second preimage attack on 6-round Grøstl-256. The complexity of our 6-round pseudo preimage and second preimage attack is ($2^{253.26},2^{253.67}$) and ($2^{251.0},2^{252.0}$) respectively. As far as we know, these are the best known attacks on round-reduced Grøstl hash function.

This paper presents a comprehensive study of the computation of square roots over finite extension fields. We propose two novel algorithms for computing square roots over even field extensions of the form $\F_{q^{2}}$, with $q=p^n,$ $p$ an odd prime and $n\geq 1$. Both algorithms have an associate computational cost roughly equivalent to one exponentiation in $\F_{q^{2}}$. The first algorithm is devoted to the case when $q\equiv 1 \bmod 4$, whereas the second one handles the case when $q\equiv 3 \bmod 4$. Numerical comparisons show that the two algorithms presented in this paper are competitive and in some cases more efficient than the square root methods previously known.