Oblivious transfer is one of the most basic and important building blocks in cryptography. As such, understanding its cost is of prime importance. Beaver (STOC 1996) showed that it is possible to obtain $\poly(n)$ oblivious transfers given only $n$ actual oblivious transfer calls and using one-way functions, where $n$ is the security parameter. In addition, he showed that it is impossible to extend oblivious transfer information theoretically. The notion of extending oblivious transfer is important theoretically (to understand the complexity of computing this primitive) and practically (since oblivious transfers can be expensive and thus extending them using only one-way functions is very attractive). Despite its importance, very little is known about the feasibility of extending oblivious transfer, beyond the fact that it is impossible information theoretically. Specifically, it is not known whether or not one-way functions are actually necessary for extending oblivious transfer, whether or not it is possible to extend oblivious transfers with adaptive security, and whether or not it is possible to extend oblivious transfers when starting with just a few. In this paper, we address these questions and provide almost complete answers to all of them. We show that the existence of any oblivious transfer extension protocol with security for static semi-honest adversaries implies one-way functions, that an oblivious transfer extension protocol with adaptive security implies oblivious transfer with static security, and that the existence of an oblivious transfer extension protocol from only $O(\log n)$ oblivious transfers implies oblivious transfer itself.

Up to now, several non-delegatable identity-based (strong) designated verifier signature schemes using bilinear pairings are proposed. In these identity-based (strong) designated verifier signature schemes, bilinear pairings are employed either in signing and verifying steps or only in the verifying step. However, the computation cost of pairings at a security level equivalent to a 128-bit symmetric key of AES is approximately 20 times higher than that of exponentiation over an elliptic curve group. Hence, presenting a (strong) designated verifier signature scheme which is identity-based without pairings and supports non-delegatability as well is vital. In this study, a non-delegatable identity-based designated verifier signature scheme without bilinear pairings using two concatenated Schnorr signatures is proposed. Our construction not only is approximately 40 times more efficient compared to the existing non-delegatable identity-based (strong) designated verifier signature schemes due to the avoiding bilinear pairings but also it is provable secure in the random oracle.

Authentication codes (A-codes) are a well studied technique to provide unconditionally secure authentication. An A-code is defined by a map that associates a pair formed by a message and a key to a tag. A-codes linear in the keys have been studied for application to distributed authentication schemes. In this paper, we address the dual question, namely the study of A-codes that are linear in the messages. This is usually an undesired property, except in the context of network coding. Regarding these A-codes, we derive some lower bounds on security parameters when key space is known. We also show a lower bound on key size when security parameter values are given (with some special properties) and construct some codes meeting the bound. We finally present a variant of these codes that authenticate multiple messages with a same key while preserving unconditional security.

We study signed bitwise differences and modular differences. We find a way to reduce signed bitwise differences that can be transformed into same modular differences. In this way, it needs arithmetic difference. We establish one-one relationship between modular differences and arithmetic difference. And establish one-one relationship between signed bitwise differences and arithmetic difference. Then it will reduce signed bitwise differences that can be transformed into same arithmetic difference. In this paper, we design a construction with ways we find. Given modular differences, some signed bitwise difference is uniquely determined.

Elliptic curve cryptography (ECC) is an efficient public cryptosystem with a short key size. For this reason it is suitable for implementing on memory-constraint devices such as smart cards, mobile devices, etc. However, these devices leak information about their private key through side channels (power consumption, electromagnetic radiation, timing etc) during cryptographic processing. In this paper we have examined countermeasures against a specific class of side channel attacks (power analysis) called Zero-Value Point Attack (ZVP), using elliptic curve isomorphism and isogeny. We found that these methods are an efficient way of securing cryptographic devices using ECC against ZVP attack. Our main contribution is to extend the work of Akishita and Takagi [3,2] to binary fields. We also provide a more detail analysis of the ZVP attack over prime fields.

We propose a new multivariate probabilistic encryption scheme with decryption errors MQQ-ENC that belongs to the family of MQQ-based public key schemes. Similarly to MQQ-SIG, the trapdoor is constructed using quasigroup string transformations with multivariate quadratic quasigroups, and a minus modifier with relatively small and fixed number of removed equations. To make the decryption possible and also efficient, we use a universal hash function to eliminate possibly wrong plaintext candidates. We show that, in this way, the probability of erroneous decryption becomes negligible. MQQ-ENC is defined over the fields $\mathbb{F}_{2^k}$ for any $k \geq 1$, and can easily be extended to any $\mathbb{F}_{p^k}$, for prime $p$. One important difference from MQQ-SIG is that in MQQ-ENC we use left MQQs (LMQQs) instead of bilinear MQQs. Our choice can be justified by our extensive experimental analysis that showed the superiority of the LMQQs over the bilinear MQQs for the design of MQQ-ENC. We apply the standard cryptanalytic techniques on MQQ-ENC, and from the results, we pose a plausible conjecture that the instances of the MQQ-ENC trapdoor are hard instances with respect to the MQ problem. Under this assumption, we adapt the Kobara-Imai conversion of the McEliece scheme for MQQ-ENC and prove that it provides $\mathsf{IND-CCA}$ security despite the negligible probability of decryption errors. We also recommend concrete parameters for MQQ-ENC for encryption of blocks of 128 bits for a security level of $\mathcal{O}(2^{128})$.

One of the key problems in Radio Frequency Identification(RFID) is security and privacy. Many RFID authentication protocols have been proposed to preserve security and privacy of the system. Nevertheless, most of these protocols are analyzed and it is shown that they can not provide security against some RFID attacks. RAPP is a new ultralightweight authentication protocol with permutation. In RAPP, only three operations are involved: bitwise XOR, left rotation and permutation. In this paper, we give an active attack on RAPP. We first collect some authentication messages through impersonating valid tag and readers; Then we forge valid reader to communicate with the tag about times. Using the property of the left rotation and permutation operation, we can deduce the relationship of bits of random number or secret keys at different positions, thus obtain all the secret shared by the reader and the tag.

We develop a new methodology for utilizing the prior techniques to prove selective security for functional encryption systems as a direct ingredient in devising proofs of full security. This deepens the relationship between the selective and full security models and provides a path for transferring the best qualities of selectively secure systems to fully secure systems. In particular, we present a Ciphertext-Policy Attribute-Based Encryption scheme that is proven fully secure while matching the efficiency of the state of the art selectively secure systems.

In this paper, we consider the spectra of Boolean functions with respect to the action of unitary transforms obtained by taking tensor products of the Hadamard, denoted by $H$, and the nega--Hadamard, denoted by $N$, kernels. The set of all such transforms is denoted by $\{H, N\}^n$. A Boolean function is said to be bent$_4$ if its spectrum with respect to at least one unitary transform in $\{H, N\}^n$ is flat. We prove that the maximum possible algebraic degree of a bent$_4$ function on $n$ variables is $\lceil \frac{n}{2} \rceil$, and hence solve an open problem posed by Riera and Parker [cf. IEEE-IT: 52(2)(2006) 4142--4159]. We obtain a relationship between bent and bent$_4$ functions which is a generalization of the relationship between bent and negabent Boolean functions proved by Parker and Pott [cf. LNCS: 4893(2007) 9--23].

3D integration is a promising advanced manufacturing process offering a variety of new hardware security protection opportunities. This paper presents a way of securing 3D ICs using Hamiltonian paths as hardware integrity verification sensors. As 3D integration consists in the stacking of many metal layers, one can consider surrounding a security-sensitive circuit part by a wire cage. After exploring and comparing different cage construction strategies (and reporting preliminary implementation results on silicon), we introduce a "hardware canary". The canary is a spatially distributed chain of functions $F_i$ positioned at the vertices of a 3D cage surrounding a protected circuit. A correct answer $(F_n \circ \ldots \circ F_1)(m)$ to a challenge $m$ attests the canary's integrity.

We demonstrate that by using a recently proposed somewhat homomorphic encryption (SHE) scheme it is possible to delegate the execution of a machine learning (ML) algorithm to a compute service while retaining confidentiality of the training and test data. Since the computational complexity of the SHE scheme depends primarily on the number of multiplications to be carried out on the encrypted data, we devise a new class of machine learning algorithms in which the algorithm's predictions viewed as functions of the input data can be expressed as polynomials of bounded degree. We propose confidential ML algorithms for binary classification based on polynomial approximations to least-squares solutions obtained by a small number of gradient descent steps. We present experimental validation of the confidential ML pipeline and discuss the trade-offs regarding computational complexity, prediction accuracy and cryptographic security.

A hash function maps a variable length input into a fixed length output. The hash functions that are used in the information security related applications are referred as cryptographic hash functions. Hash functions are being used as building blocks of many complex cryptographic mechanisms and protocols. Construction of a hash function consists of two components. First component is a compression function and the second component is a domain extender. The various hash function design philosophies try to design the compression function from different angles. Two major categories of hash functions are: dedicated hash functions, and block cipher-based hash functions. These two kinds of design philosophies have been revisited in this paper. Two dedicated has functions from MD4 family - MD4, and SHA-256 constructions have been detailed in this paper. To limit the scope of this paper in this framework, discussions on attacks on hash functions, and SHA-3 finalists have been excluded here. Keywords:

DECT is a standard for cordless phones. The intent of this thesis is to evaluate DECT security in a comprehensive way. To secure conversations over the air, DECT uses two proprietary algorithms, namely the DECT Standard Authentication Algorithm (DSAA) for authentication and key derivation, and the DECT Standard Cipher (DSC) for encryption. Both algorithms have been kept secret and were only available to DECT device manufacturers under a None Disclosure Agreement (NDA). The reader is first introduced into the DECT standard. The two algorithms DSAA and DSC have been reverse engineered and are then described in full detail. At first, attacks against DECT devices are presented, that are based on faults made by the manufacturers while implementing the DECT standard. In the next Chapters, attacks against the DSAA and the DSC algorithm are described, that recover the secret keys used by these algorithms faster than by brute force. Thereafter, a attack against the DECT radio protocol is described, that decrypts encrypted DECT voice calls. Finally, an outlook over the next release of the DECT standard is presented, that is expected to counter all attacks against DECT, that are described in this thesis.

Bergman's Ring $E_p$, parameterized by a prime number $p$, is a ring with $p^5$ elements that cannot be embedded in a ring of matrices over any commutative ring. This ring was discovered in 1974. In 2011, Climent, Navarro and Tortosa described an efficient implementation of $E_p$ using simple modular arithmetic, and suggested that this ring may be a useful source for intractable cryptographic problems. We present a deterministic polynomial time reduction of the Discrete Logarithm Problem in $E_p$ to the classical Discrete Logarithm Problem in $\Zp$, the $p$-element field. In particular, the Discrete Logarithm Problem in $E_p$ can be solved, by conventional computers, in sub-exponential time. Along the way, we collect a number of useful basic reductions for the toolbox of discrete logarithm solvers.

We consider the class of secret sharing schemes where there is no a priori bound on the number of players $n$ but where each of the $n$ share-spaces has fixed cardinality~$q$. We show two fundamental lower bounds on the {\em threshold gap} of such schemes. The threshold gap $g$ is defined as $r-t$, where $r$ is minimal and $t$ is maximal such that the following holds: for a secret with arbitrary a priori distribution, each $r$-subset of players can reconstruct this secret from their joint shares without error ($r$-reconstruction) and the information gain about the secret is nil for each $t$-subset of players jointly ($t$-privacy). Our first bound, which is completely general, implies that if $1\leq t<r\leq n$, then $g \geq \frac{n-t+1}{q}$ independently of the cardinality of the secret-space. Our second bound pertains to $\FF_q$-linear schemes with secret-space $\Fq^k$ ($k\geq 2$). It improves the first bound when $k$ is large enough. Concretely, it implies that $g\geq\frac{n-t+1}{q}+f(q,k,t,n)$, for some function $f$ that is strictly positive when $k$ is large enough. Moreover, also in the $\FF_q$-linear case, bounds on the threshold gap {\em independent} of $t$ or $r$ are obtained by additionally employing a dualization argument. As an application of our results, we answer an open question about the asymptotics of {\em arithmetic secret sharing schemes} and prove that the asymptotic optimal corruption tolerance rate is strictly smaller than~1.

AES-128, the NIST P-256 elliptic curve, DSA-3072, RSA-3072, and various higher-level protocols are frequently conjectured to provide a security level of 2^128. Extensive cryptanalysis of these primitives appears to have stabilized sufficiently to support such conjectures. In the literature on provable concrete security it is standard to define 2^b security as the nonexistence of high-probability attack algorithms taking time \le 2^b. However, this paper provides overwhelming evidence for the existence of high-probability attack algorithms against AES-128, NIST P-256, DSA-3072, and RSA-3072 taking time considerably below 2^128, contradicting the standard security conjectures. These attack algorithms are not realistic; do not indicate any actual security problem; do not indicate any risk to cryptographic users; and do not indicate any failure in previous cryptanalysis. Any actual use of these attack algorithms would be much more expensive than the conventional 2^128 attack algorithms. However, this expense is not visible to the standard definitions of security. Consequently the standard definitions of security fail to accurately model actual security. The underlying problem is that the standard set of algorithms, namely the set of algorithms taking time \le 2^b, fails to accurately model the set of algorithms that an attacker can carry out. This paper analyzes this failure in detail, and analyzes several ideas for fixing the security definitions.

Recent years have seen significant progress in the development of lightweight symmetric cryptoprimitives. The main concern of the designers of these primitives has been to minimize the number of gate equivalents (GEs) of the hardware implementation. However, there are numerous additional requirements that are present in real-life RFID systems. We give an overview of requirements emerging or already present in the widely deployed EPCGlobal Gen2 and ISO / IEC 18000-63 passive UHF RFID air interface standards. Lightweight stateful authenticated encryption algorithms seem to offer the most complete set of features for this purpose. In this work we give a Gen2-focused ”lessons learned” overview of the challenges and related developments in RFID cryptography and propose what we see as appropriate design criteria for a cipher (dubbed “Do-It-All-Cipher” or DIAC) for the Internet of Things. We also comment on the applicability of NSA’s new SIMON and SPECK proposals for this purpose.

In this paper we show that the recent technique of computationally complete symbolic attackers proposed by Bana and Comon-Lundh for computationally sound verification is powerful enough to verify actual protocols, such as the Needham-Schroeder-Lowe Protocol. In their model, one does not define explicit Dolev-Yao adversarial capabilities but rather the limitations of the adversarial capabilities. In this paper we present a set of axioms sufficient to show that no symbolic adversary compliant with these axioms can successfully violate secrecy or authentication in case of the NSL protocol. Hence all implementations for which these axioms are sound – namely, implementations using CCA2 encryption, and satisfying a minimal parsing requirement for pairing – exclude the possibility of successful computational attacks.

A visual cryptography scheme (VCS) is a secret sharing method, for which the secret can be decoded by human eyes without needing any cryptography knowledge nor any computation. Variance is first introduced by Hou et al. in 2005 and then thoroughly verified by Liu et al. in 2012 to evaluate the visual quality of size invariant VCS. In this paper, we introduce the idea of using variance as an error-detection measurement, by which we find the security defect of Hou et al.'s multi-pixel encoding method. On the other hand, we find that variance not only effects the visual quality of size invariant VCS, but also effects the visual quality of VCS. At last, average contrast associated with variance is used as a new criterion to evaluate the visual quality of VCS.

The nonlinear feedback shift registers (NLFSR) are used to construct pseudorandom generators for stream ciphers. Their theory is not so complete as that of the linear feedback shift registers (LFSR). In general, it is not known how to construct NLFSRs with maximum period. The direct method is to search for such registers with suitable properties. We used the implementation of NLFSRs in Field Programmable Gate Arrays (FPGA) to perform a corresponding search. We also investigated local statistical properties of the binary sequences ganerated by NLFSRs of order 25 and 27.

The concept of proxy signature was introduced in 1996, up to now many proxy signature schemes have been proposed. In order to protect the proxy signer's privacy, the concept of anonymous proxy signature, which is also called proxy ring signature, was introduced in 2003. Some anonymous proxy signature schemes, which are provable secure in the random oracle model, have been proposed. However, provable security in the random oracle model is doubtful when the random oracles are instantiated with hash functions in their implementation. Hence, we propose the first secure anonymous proxy signature scheme without random oracles.

Recently, Chien et al. proposed a gateway-oriented password-based authenticated key exchange (GPAKE) protocol, through which a client and a gateway could generate a session key for future communication with the help of an authentication server. They also demonstrated that their scheme is provably secure in a formal model. However, in this letter, we will show that Chien et al.’s protocol is vulnerable to the off-line password guessing attack. To overcome the weakness, we also propose an efficient countermeasure.

We construct the first public-key encryption scheme whose chosen-ciphertext (i.e., IND-CCA) security can be proved under a standard assumption and does not degrade in either the number of users or the number of ciphertexts. In particular, our scheme can be safely deployed in unknown settings in which no a-priori bound on the number of encryptions and/or users is known. As a central technical building block, we devise the first structure-preserving signature scheme with a tight security reduction. (This signature scheme may be of independent interest.) Combining this scheme with Groth-Sahai proofs yields a tightly simulation-sound non-interactive zero-knowledge proof system for group equations. If we use this proof system in the Naor-Yung double encryption scheme, we obtain a tightly IND-CCA secure public-key encryption scheme from the Decision Linear assumption. We point out that our techniques are not specific to public-key encryption security. Rather, we view our signature scheme and proof system as general building blocks that can help to achieve a tight security reduction.

In this paper, we specify a class of mathematical problems, which we refer to as ``Function Density Problems'' (FDPs, in short), and point out novel connections of FDPs to the following two cryptographic topics; theoretical security evaluations of keyless hash functions (such as SHA-1), and constructions of provably secure pseudorandom generators (PRGs) with some enhanced security property introduced by Dubrov and Ishai [STOC 2006]. Our argument aims at proposing new theoretical frameworks for these topics (especially for the former) based on FDPs, rather than providing some concrete and practical results on the topics. We also give some examples of mathematical discussions on FDPs, which would be of independent interest from mathematical viewpoints. Finally, we discuss possible directions of future research on other cryptographic applications of FDPs and on mathematical studies on FDPs themselves.

&#8233;Elliptic curve cryptosystems have improved greatly in speed over the past few years. In this paper we outline a new elliptic curve signature and key agreement implementation which achieves record speeds while remaining relatively compact. For example, on Intel Sandy Bridge, a curve with about $2^{250}$ points produces a signature in just under 60k clock cycles, verifies in under 169k clock cycles, and computes a Diffie-Hellman shared secret in under 153k clock cycles. Our implementation has a small footprint: the library is under 55kB. We also post competitive timings on ARM processors, verifying a signature in under 626k Tegra-2 cycles. We introduce faster field arithmetic, a new point compression algorithm, an improved fixed-base scalar multiplication algorithm and a new way to verify signatures without inversions or coordinate recovery. Some of these improvements should be applicable to other systems.

Verified security provides a firm foundation for cryptographic proofs by means of rigorous programming language techniques and verification methods. EasyCrypt is a framework that realizes the verified security paradigm and supports the machine-checked construction and verification of cryptographic proofs using state-of-the-art SMT solvers, automated theorem provers and interactive proof assistants. Previous experiments have shown that EasyCrypt is effective for a posteriori validation of cryptographic systems. In this paper, we report on the first application of verified security to a novel cryptographic construction, with strong security properties and interesting practical features. Specifically, we use EasyCrypt to prove the IND-CCA security of a redundancy-free public-key encryption scheme based on trapdoor one-way permutations. Somewhat surprisingly, we show that even with a zero-length redundancy, Boneh's SAEP scheme (an OAEP-like construction with a single-round Feistel network rather than two) converts a trapdoor one-way permutation into an IND-CCA-secure scheme, provided the permutation satisfies two additional properties. We then prove that the Rabin function and RSA with short exponent enjoy these properties, and thus can be used to instantiate the construction we propose to obtain efficient encryption schemes. The reduction that justifies the security of our construction is tight enough to achieve practical security with reasonable key sizes.

Broadcast encryption aims at sending a content to a large arbitrary group of users at once. Currently, the most efficient schemes provide constant-size headers, that encapsulate ephemeral session keys under which the payload is encrypted. However, in practice, and namely for pay-TV, providers have to send various contents to different groups of users. Headers are thus specific to each group, one for each channel: as a consequence, the global overhead is linear in the number of channels. Furthermore, when one wants to zap to and watch another channel, one has to get the new header and decrypt it to learn the new session key: either the headers are sent quite frequently or one has to store all the headers, even if one watches one channel only. Otherwise, the zapping time becomes unacceptably long. In this paper, we consider encapsulation of several ephemeral keys, for various groups and thus various channels, in one header only, and we call this new primitive Multi-Channel Broadcast Encryption: one can hope for a much shorter global overhead and a short zapping time since the decoder already has the information to decrypt any available channel at once. Our candidates are private variants of the Boneh-Gentry-Waters scheme, with a constant-size global header, independently of the number of channels. In order to prove the CCA security of the scheme, we introduce a new dummy-helper technique and implement it in the random oracle model.

In this paper, we investigate on threshold proofs, a framework for distributing the prover’s side of interactive proofs of knowledge over multiple parties. Interactive proofs of knowledge (PoK) are widely used primitives of cryptographic protocols, including important user-centric protocols, such as identification schemes, electronic cash (e-cash), and anonymous credentials. We present a security model for threshold proofs of knowledge and develop threshold versions of well-known primitives such as range proofs, zero-knowledge proofs for preimages of homomorphisms (which generalizes PoKs of discrete logarithms, representations, p-th roots, etc.), as well as OR statements. These building blocks are proven secure in our model. Furthermore, we apply the developed primitives and techniques in the context of user-centric protocols. In particular, we construct distributed-user variants of Brands’ e-cash system and the bilinear anonymous credential scheme by Camenisch and Lysyanskaya. Distributing the user party in such protocols has several practical advantages: First, the security of a user can be increased by sharing secrets and computations over multiple devices owned by the user. In this way, losing control of a single device does not result in a security breach. Second, this approach also allows groups of users to jointly control an application (e.g., a joint e-cash account), not giving a single user full control. The distributed versions of the protocols we propose in this paper are relatively efficient (when compared to a general MPC approach). In comparison to the original protocols only the prover’s (or user’s) side is modified while the other side stays untouched. In particular, it is oblivious to the other party whether it interacts with a distributed prover (or user) or one as defined in the original protocol.

In the classical model of traitor tracing, one assumes that a traitor contributes its entire secret key to build a pirate decoder. However, new practical scenarios of pirate has been considered, namely Pirate Evolution Attacks at Crypto 2007 and Pirates 2.0 at Eurocrypt 2009, in which pirate decoders could be built from sub-keys of users. The key notion in Pirates 2.0 is the anonymity level of traitors: they can rest assured to remain anonymous when each of them only contributes a very small fraction of its secret information. This scenario encourages dishonest users to participate in collusion and the size of collusion could become very large, possibly beyond the considered threshold in the classical model. There are numerous attempts to deal with Pirates 2.0 each of which only considers a particular form of Pirates 2.0. In this paper, we propose a method for fighting Pirates 2.0 in any form. Our method is based on the researches in key-leakage resilience. It thus gives an interesting and rather surprised connection between the rich domain of key-leakage resilient cryptography and Pirates 2.0. We first formalize the notion of key-leakage resilient revoke system and then identify sufficient conditions so that a key-leakage resilient revoke scheme can resist Pirates 2.0 in any form. We finally propose a construction of a secure key-leakage resilient identity-based revoke system that fulfills the required conditions. The main ingredient in the construction relies on the identity-based encryption with wildcards ($\WIBE$) and our construction of key-leakage resilient $\WIBE$ could be useful in its own right.

We provide the first two-party protocol allowing Alice and Bob to evaluate privately even against active adversaries any completely positive, trace-preserving map F, given as a quantum circuit, upon their joint quantum input state. Our protocol leaks no more to any active adversary than an ideal functionality for F provided Alice and Bob have the cryptographic resources for active secure two-party classical computation. Our protocol is constructed from the protocol for the same task secure against specious adversaries presented in [DNS10].

Despite the fact that we evidently have very good block ciphers at hand today, some fundamental questions on their security are still unsolved. One such fundamental problem is to precisely assess the security of a given block cipher with respect to linear cryptanalysis. In by far most of the cases we have to make (clearly wrong) assumptions, e.g., assume independent round-keys. Besides being unsatisfactory from a scientific perspective, the lack of fundamental understanding might have an impact on the performance of the ciphers we use. As we do not understand the security sufficiently enough, we often tend to embed a security margin -- from an efficiency perspective nothing else than wasted performance. The aim of this paper is to stimulate research on these foundations of block ciphers. We do this by presenting three examples of ciphers that behave differently to what is normally assumed. Thus, on the one hand these examples serve as counter examples to common beliefs and on the other hand serve as a guideline for future work.

The UC approach of Canetti offers the advantage of stand-alone analysis while keeping security guaranties for arbitrary complex environment. When we implement by this approach first we have to ensure secure instance separation and based on this condition, we are allowed to carry out a stand-alone analysis. In this report we propose three issues related to instance separation in UC-context: We consider the problem of universal composability in cases, when we cannot assume independence of instances. Next we formalize the interleaving attack and a related security notion. In time-aware protocols time-based separation of instances is one of the standard implementation techniques. We propose an event-driven clock model towards purely symbolic analysis of time-aware protocols.

In TCC 2007, Adida and Wikström proposed a novel approach to shuffle, called a public shuffle, in which a shuffler can perform shuffle publicly without needing information kept secret. Their scheme uses an encrypted permutation matrix to shuffle ciphertexts publicly. This approach significantly reduces the cost of constructing a mix-net to verifiable joint decryption. Though their method is successful in making shuffle to be a public operation, their scheme still requires that some trusted parties should choose a permutation to be encrypted and construct zero-knowledge proofs on the well-formedness of this permutation. In this paper, we propose a method to construct a public shuffle without relying on permutations and randomizers generated privately: Given an $n$-tuple of ciphertext $(c_1,\dots,c_n)$, our shuffle algorithm computes $f_i(c_1,\dots,c_n)$ for $i=1,\dots,\ell$ where each $f_i(x_1,\dots,x_n)$ is a symmetric polynomial in $x_1,\dots,x_n$. Depending on the symmetric polynomials we use, we propose two concrete constructions. One is to use ring homomorphic encryption with constant ciphertext complexity and the other is to use simple ElGamal encryption with linear ciphertext complexity in the number of senders. Both constructions are free of zero-knowledge proofs and publicly verifiable.

Side-channel attacks have proven many hardware implementations of cryptographic algorithms to be vulnerable. A recently proposed masking method, based on secret sharing and multi-party computation methods, introduces a set of sufficient requirements for implementations to be provably resistant against first-order DPA with minimal assumptions on the hardware. The original paper doesn't describe how to construct the Boolean functions that are to be used in the implementation. In this paper, we derive the functions for all invertible $3 \times 3$, $4 \times 4$ S-boxes and the $6 \times 4$ DES S-boxes. Our methods and observations can also be used to accelerate the search for sharings of larger (e.g. $8 \times 8$) S-boxes. Finally, we investigate the cost of such protection.

Stream cipher ZUC plays a crucial role in the next generation of mobile communication as it has already been included by the 3GPP LTE-Advanced, which is a candidate standard for the 4G network. Through a long-time evaluation program, ZUC algorithm is thought to be robust enough to resist many existing cryptanalyses, but not for DPA, one of the most powerful threat of SCAs(Side Channel Analysis).Up to the present, almost all the work on DPA is for block ciphers, such as DES and AES, a very few work has been done on stream ciphers, such as ZUC algorithm, for particular reasons that would be illustrated in the later section. In this paper, we generally study the security of unprotected ZUC hardware implementation against DPA. Our theoretical analysis and experimental results show that ZUC algorithm is potentially vulnerable to this kind of attack. Furthermore, kinds of common countermeasures are discussed when we try to apply them to ZUC hardware implementations, both the security and tradeoffs are considered. The experiments are given in the last section to verify our conclusions, which would undoubtedly provide some guidance to the corresponding designers.

We define and propose an efficient and provably secure construction of blind signatures with attributes. Prior notions of blind signatures did not yield themselves to the construction of anonymous credential systems, not even if we drop the unlinkability requirement of anonymous credentials. Our new notion in contrast is a convenient building block for anonymous credential systems. The construction we propose is efficient: it requires just a few exponentiations in a prime-order group in which the decisional Diffie-Hellman problem is hard. Thus, for the &#64257;rst time, we give a provably secure construction of anonymous credentials that can work in the elliptic group setting without bilinear pairings. In contrast, prior provably secure constructions were based on the RSA group or on groups with pairings, which made them prohibitively inefficient for mobile devices, RFIDs and smartcards. The only prior efficient construction that could work in such elliptic curve groups, due to Brands, does not have a proof of security.

It is notoriously difficult to create hardware that is immune from side channel and tampering attacks. A lot of recent literature, therefore, has instead considered \emph{algorithmic} defenses from such attacks. In this paper, we show how to algorithmically secure any cryptographic functionality from continual split-state leakage and tampering attacks. A split-state attack on cryptographic hardware is one that targets separate parts of the hardware separately. Our construction does not require the hardware to have access to randomness. In contrast, prior work on protecting from continual combined leakage and tampering required true randomness for each update. Our construction is in the common reference string (CRS) model; the CRS must be hard-wired into the device. We note that prior negative results show that it is impossible to algorithmically secure a cryptographic functionality against a combination of arbitrary continual leakage and tampering attacks without true randomness; therefore restricting our attention to the split-state model is justified. Our construction is simple and modular, and relies on a new construction, in the CRS model, of non-malleable codes with respect to split-state tampering functions, which may be of independent interest.

This paper is a short summary of a real world AES key extraction performed on a military grade FPGA marketed as 'virtually unbreakable' and 'highly secure'. We demonstrated that it is possible to extract the AES key from the Actel/Microsemi ProASIC3 chip in a time of 0.01 seconds using a new side-channel analysis technique called Pipeline Emission Analysis (PEA). This new technique does not introduce a new form of side-channel attacks (SCA), it introduces a substantially improved method of waveform analysis over conventional attack technology. It could be used to improve upon the speed at which all SCA can be performed, on any device and especially against devices previously thought to be unfeasible to break because of the time and equipment cost. Possessing the AES key for the ProASIC3 would allow an attacker to decrypt the bitstream or authenticate himself as a legitimate user and extract the bitstream from the device where no read back facility exists. This means the device is wide open to intellectual property theft, fraud and reverse engineering of the design to allow the introduction of a backdoor or Trojan. We show that with a very low cost hardware setup made with parts obtained from a local electronics distributor you can improve upon existing SCA up to a factor of x1,000,000 in time and at a fraction of the cost of existing SCA equipment.

We present a formalisation of a category of schemes which we call Broadcast-enhanced Key Predistribution Schemes (BEKPSs). These schemes are suitable for networks with access to a trusted base station and an authenticated broadcast channel. We demonstrate that the access to these extra resources allows for the creation of BEKPSs with advantages over key predistribution schemes such as flexibility and more efficient revocation. There are many possible ways to implement BEKPSs, and we propose a framework for describing and analysing them. In their paper `From key predistribution to key redistribution', Cichoń, Go{\l}ȩbiewski and Kuty{\l}owski propose a scheme for `redistributing' keys to a wireless sensor network using a broadcast channel after an initial key predistribution. We classify this as a BEKPS and analyse it in that context. We provide simpler proofs of some results from their paper, give a precise analysis of the resilience of their scheme, and discuss possible modifications. We then study two scenarios where BEKPSs may be particularly desirable and propose a suitable family of BEKPSs for each case. We demonstrate that they are practical and efficient to implement, and our analysis shows their effectiveness in achieving suitable trade-offs between the conflicting priorities in resource-constrained networks.

Pollard's rho algorithm, along with parallelized, vectorized, and negating variants, is the standard method to compute discrete logarithms in generic prime-order groups. This paper presents two reasons that Pollard's rho algorithm is farther from optimality than generally believed. First, ``higher-degree local anti-collisions'' make the rho walk less random than the predictions made by the conventional Brent--Pollard heuristic. Second, even a truly random walk is suboptimal, because it suffers from ``global anti-collisions'' that can at least partially be avoided. For example, after (1.5+o(1))\sqrt(l) additions in a group of order l (without fast negation), the baby-step-giant-step method has probability 0.5625+o(1) of finding a uniform random discrete logarithm; a truly random walk would have probability 0.6753\ldots+o(1); and this paper's new two-grumpy-giants-and-a-baby method has probability 0.71875+o(1).

We prove three optimal transference theorems on lattices possessing $n^{\epsilon}$-unique shortest vectors which relate to the successive minima, the covering radius and the minimal length of generating vectors respectively. The theorems result in reductions between GapSVP$_{\gamma'}$ and GapSIVP$_\gamma$ for this class of lattices. Furthermore, we prove a new transference theorem giving an optimal lower bound relating the successive minima of a lattice with its dual. As an application, we compare the respective advantages of current upper bounds on the smoothing parameter of discrete Gaussian measures over lattices and show a more appropriate bound for lattices whose duals possess $\sqrt{n}$-unique shortest vectors.

Certain block cipher confidentiality modes are susceptible to an adaptive chosen-ciphertext attack against the underlying format of the plaintext. When the application decrypts altered ciphertext and attempts to process the manipulated plaintext, it may disclose information about intermediate values resulting in an oracle. In this paper we describe how to recognize and exploit such an oracle to decrypt ciphertext and control the decryption to result in arbitrary plaintext. We also discuss ways to mitigate and remedy the issue.

The emergence and wide availability of remote storage service providers prompted work in the security community that allows a client to verify integrity and availability of the data that she outsourced to an untrusted remove storage server at a relatively low cost. Most recent solutions to this problem allow the client to read and update (i.e., insert, modify, or delete) stored data blocks while trying to lower the overhead associated with verifying the integrity of the stored data. In this work we develop a novel scheme, performance of which favorably compares with the existing solutions. Our solution enjoys a number of new features such as a natural support for operations on ranges of blocks, revision control, and support for multiple user access to shared content. The performance guarantees that we achieve stem from a novel data structure termed a balanced update tree and removing the need to verify update operations.

We define and construct fully homomorphic message authenticators. In such a scheme, anybody can perform arbitrary computations over authenticated data and produce a short tag that authenticates the result of the computation. The user verifies this tag with her private key to ensure that the claimed result is indeed the correct output of the specified computation over previously authenticated data, without needing to know the underlying data itself. For example, a user can outsource the storage of large amounts of authenticated data to a remote server, and the server can later non-interactively certify the outputs of various computations over this data with only a short tag. Our construction uses fully homomorphic encryption in a novel way.

In many applications of group signatures, not only a signer's identity but also which group the signer belongs to is sensitive information regarding signer privacy. In this paper, we study these applications and combine a group signature with a ring signature to create a ring group signature, which specifies a set of possible groups without revealing which member of which group produced the signature. The main contributions of this paper are a formal definition of a ring group signature scheme and its security model, a generic construction and a concrete example of such a scheme. Both the construction and concrete scheme are provably secure if the underlying group signature and ring signature schemes are secure.

We propose a protocol to exchange Boneh-Boyen short signatures in a fair way, without relying on a trusted third party. Our protocol is quite practical and is the first of the sort to the best of our knowledge. Our construction uses a new non-interactive zero-knowledge (NIZK) argument to prove that a commitment is the encryption of a bit vector. We also design a NIZK argument to prove that a commitment toa bit vector $v=(b_1,b_2,...,b_\secparam)$ is such that $\sum_{i \in [\secparam]}b_i2^{i-1}=\Blinding$ where $\Blinding$ is the discrete logarithm of some public value $D=g^\Blinding$. These arguments may be of independent interest.

In this work, we re-examine some fundamental group key-exchange and identity-based key-exchange protocols, specifically the Burmester-Desmedet group key-exchange protocol [7] (re-ferred to as the BD-protocol) and the Chen-Kudla identity-based key-exchange protocol [9] (referred to as the CK-protocol). We identify some new attacks on these protocols, showing in particular that these protocols are not computationally fair. Specifically, with our attacks, an adversary can do the following damages: (1) It can compute the session-key output with much lesser computational complexity than that of the victim honest player, and can maliciously nullify the contributions from the victim honest players. (2) It can set the session-key output to be some pre-determined value, which can be efficiently and publicly computed without knowing any secrecy supposed to be held by the attacker. We remark these attacks are beyond the traditional security models for group key-exchange and identity-based key-exchange. Then, based on the computationally fair Diffie-Hellman key- exchange in [21], we present some fixing approaches, and prove that the fixed protocols are computationally fair.

In this paper we propose a new differential fault analysis (DFA) on CLEFIA of 128-bit key. The proposed attack requires to induce byte faults at the fourteenth round of CLEFIA encryption. The attack uses only two pairs of fault-free and faulty ciphertexts and uniquely determines the 128-bit secret key. The attacker does not need to know the plaintext. The most efficient reported fault attack on CLEFIA, needs fault induction at the fifteenth round of encryption and can be performed with two pairs of fault-free and faulty ciphertexts and brute-force search of around 20 bits. Therefore, the proposed attack can evade the countermeasures against the existing DFAs which only protect the last four rounds of encryption. Extensive simulation results have been presented to validate the proposed attack. The simulation results show that the attack can retrieve the 128-bit secret key in around one minute of execution time. To the best of authors’ knowledge the proposed attack is the most efficient attack in terms of both the input requirements as well as the complexity.

This paper presents efficient structure-preserving signature schemes based on assumptions as simple as Decision-Linear. We first give two general frameworks for constructing fully secure signature schemes from weaker building blocks such as two-tier signatures and random-message secure signatures. They can be seen as refinements of the Even-Goldreich-Micali framework, and preserve many desirable properties of the underlying schemes such as constant signature size and structure preservation. We then instantiate them based on simple (i.e., not q-type) assumptions over symmetric and asymmetric bilinear groups. The resulting schemes are structure-preserving and yield constant-size signatures consisting of 11 to 17 group elements, which compares favorably to existing schemes relying on q-type assumptions for their security.

\emph{Authenticated Key Exchange} (AKE) protocols enable two parties to establish a shared, cryptographically strong key over an insecure network using various authentication means, such as cryptographic keys, short (\emph{i.e.}, low-entropy) secret keys or \emph{credentials}. In this paper, we provide a general framework, that encompasses several previous AKE primitives such as \emph{(Verifier-based) Password-Authenticated Key Exchange} or \emph{Secret Handshakes}, we call \emph{LAKE} for \emph{Language-Authenticated Key Exchange}. We first model this general primitive in the \emph{Universal Composability} (UC) setting. Thereafter, we show that the Gennaro-Lindell approach can efficiently address this goal. But we need \emph{smooth projective hash functions} on new languages, whose efficient implementations are of independent interest. We indeed provide such hash functions for languages defined by combinations of linear pairing product equations. Combined with an efficient commitment scheme, that is derived from the highly-efficient UC-secure Lindell's commitment, we obtain a very practical realization of Secret Handshakes, but also \emph{Credential-Authenticated Key Exchange protocols}. All the protocols are UC-secure, in the standard model with a common reference string, under the classical Decisional Linear assumption.

In this paper, we generalize some existing results on Boolean functions to the $q$-ary functions defined over $\BBZ_q$, where $q\geq 2$ is an integer, and obtain some new characterization of $q$-ary functions based on spectral analysis. We provide a relationship between Walsh-Hadamard spectra of two $p$-ary functions $f$ and $g$ (for $p$ a prime) and their derivative $D_{f, g}$. We provide a relationship between the Walsh-Hadamard spectra and the decompositions of any two $p$-ary functions. Further, we investigate a relationship between the Walsh-Hadamard spectra and the autocorrelation of any two $q$-ary functions.

Recently proposed algebraic attack has been shown to be very effective on several stream ciphers. In this paper, we have investigated the resistance of PingPong family of stream ciphers against algebraic attacks. This stream cipher was proposed in 2008 to enhance the security of the improved summation generator against the algebraic attack. In particular, we focus on the PingPong-128 stream cipher’s resistance against algebraic attack in this paper. In our analysis, it is found that an algebraic attack on PingPong family of stream ciphers require much more operations compare to the exhaustive key search on the internal state of the LFSRs. It will be shown that due to the irregular and mutual clock controlling in PingPong stream cipher the degree of the generated equation tends to grow up with each successive clock which in turn increases the overall complexity of an algebraic attack. Along with the PingPong 128 stream cipher the other instances of PingPong family stream ciphers are also investigated against the algebraic attack. Our analysis shows that, PingPong family stream ciphers are highly resistant against the algebraic attack due to their mutual and irregular clocking function.

Outsourced computations (where a client requests a server to perform some computation on its behalf) are becoming increasingly important due to the rise of Cloud Computing and the proliferation of mobile devices. Since cloud providers may not be trusted, a crucial problem is the verification of the integrity and correctness of such computation, possibly in a {\em public} way, i.e., the result of a computation can be verified by any third party, and requires no secret key -- akin to a digital signature on a message. We present new protocols for publicly verifiable secure outsourcing of {\em Evaluation of High Degree Polynomials} and {\em Matrix Multiplication}. Compared to previously proposed solutions, ours improve in efficiency and offer security in a stronger model. The paper also discusses several practical applications of our protocols.

The Square attack as a means of attacking reduced round variants of AES was described in the initial description of the Rijndael block cipher. This attack can be applied to AES, with a relatively small number of chosen plaintext-ciphertext pairs, reduced to less than six rounds in the case of AES-128 and seven rounds otherwise and several extensions to this attack have been described in the literature. In this paper we describe new variants of these attacks that have a smaller time complexity than those present in the literature. Specifically, we demonstrate that the quantity of chosen plaintext-ciphertext pairs can be halved producing the same reduction in the time complexity. We also demonstrate that the time complexity can be halved again for attacks applied to AES-128 and reduced by a smaller factor for attacks applied to AES-192. This is achieved by eliminating hypotheses on-the-fly when bytes in consecutive subkeys are related because of the key schedule.

In this paper, we put forward the Bounded Player Model for secure computation. In this new model, the number of players that will ever be involved in secure computations is bounded, but the number of computations has no a priori bound. Indeed, while the number of devices and people on this planet can be realistically estimated and bounded, the number of computations these devices will run can not be realistically bounded. We stress that in the Bounded Player model}, in addition to no a priori bound on the number of sessions, there is no synchronization barrier, no trusted party, and simulation must be performed in polynomial time. In this setting, we achieve concurrent Zero Knowledge (cZK) with sub-logarithmic round complexity. Our security proof is (necessarily) non-black-box, our simulator is "straight-line" and works as long as the number of rounds is \omega(1). We further show that unlike previously studied relaxations of the standard model (e.g., bounded number of sessions, timing assumptions, super-polynomial simulation), concurrent-secure computation is still impossible to achieve in the Bounded Player model. This gives evidence that our model is "closer" to the standard model than previously studied models, and study of this model might shed light on constructing round efficient concurrent zero-knowledge in the standard model as well.

Indifferentiability security of a hash mode of operation guarantees the mode's resistance against all (meaningful) generic attacks. It is also useful to establish the security of protocols that use hash functions as random functions. The JH hash function is one of the five finalists in the ongoing NIST SHA-3 hash function competition. Despite several years of analysis, the indifferentiability security of the JH mode (with n-bit digest and 2n-bit permutation) has remained remarkably low, only at n/3 bits (FSE 2010), while the other four finalist modes -- with comparable parameter values -- offer a security guarantee of n/2 bits. In this paper, we improve the indifferentiability security bound for the JH mode to n/2 bits (e.g. from 171 to 256 bits when n=512). To put this into perspective, our result guarantees the absence of attacks on both JH-256 and JH-512 hash functions with time less than approximately 2^{256} computations of the underlying 1024-bit permutation, under the assumption that the basic permutation is structurally strong. Our bounds are optimal for JH-256, and the best, so far, for JH-512. We obtain this improved bound by establishing an isomorphism of certain query-response graphs through a careful design of the simulators and the bad events. Our experimental data strongly supports the theoretically obtained results.

This work fall within the cadre of Cryptanalysis. Because, under certain condition, we would give a fairly simple method to solve the CDHP (the Problem Computational of Diffie and Hellman) and others problems associated to it. Since, solving this problem, will help us to provide a solution to the BDH (Problem Bilinear of Diffie and Hellman). The CDHP and BDHP are the heart of many cryptosystems in the point of view security, so solving it may be a threat to this cryptosystem’s. To elucidate this, we use a concept of geometry algebraic named Tate Pairing. This work is purely theoretical, we give firstly an overview on the idea and we illustrate it by an examples to see its efficiency.

Static and dynamic proof of storage schemes have been proposed for use in secure cloud storage scenarios. In this setting, a client outsources storage of her data to a server, who may, willingly or not, corrupt the data (e.g., due to hardware or software failures), or delete infrequently accessed parts to save space. Most of the existing schemes only solve part of this problem: The client may ask for a cryptographic proof of integrity from the server. But what happens if this proof fails to verify? We argue that in such a case, both the client and the server should be able to contact an official court, providing cryptographic proofs, so that the Judge can resolve this dispute. We show that this property is stronger than what has been known as public verifiability in the sense that official arbitration should handle a malicious client as well. We clearly show this formalization difference, and then present multiple schemes that work for various static and dynamic storage solutions in a generic way. We implement our schemes and show that they are very efficient, diminishing the validity of arguments against their use, where the overhead for adding the ability to resolve such disputes at a court is only 2 ms and 80 bytes for each update on the stored data, using standard desktop hardware. Finally, we note that disputes may arise in many other situations, such as when two parties exchange items (e.g., e-commerce) or agree on something (e.g., contract-signing). We show that it is easy to extend our official arbitration protocols for a general case, including dynamic authenticated data structures.

In 2013 Intel will release the AVX2 instructions, which introduce 256-bit single-instruction multiple-data (SIMD) integer arithmetic. This will enable desktop and server processors from this vendor to support 4-way SIMD computation of 64-bit add-rotate-xor algorithms, as well as 8-way 32-bit SIMD computations. AVX2 also includes interesting instructions for cryptographic functions, like any-to-any permute and vectorized table-lookup. In this paper, we explore the potential of AVX2 to speed-up the SHA-3 finalist BLAKE, and present the first working assembly implementations of BLAKE-256 and BLAKE-512 with AVX2. We then investigate the potential of the recent AVX and XOP instructions to accelerate BLAKE, and report new speed records on Sandy Bridge and Bulldozer microarchitectures (7.47 and 11.64 cycles per byte for BLAKE-256, 5.71 and 6.95 for BLAKE-512).

SM3 is a hash function designed by Xiaoyun Wang et al., and published by the Chinese Commercial Cryptography Administration Office for the use of electronic authentication service system. The design of SM3 builds upon the design of the SHA-2 hash function, but introduces additional strengthening features. In this paper, using a higher order differential cryptanalysis approach, we present a practical 4-sum distinguisher against the compression function of SM3 reduced to 32 rounds. In addition, we point out a slide-rotational property of SM3-XOR, which exists due to the fact that constants used in the rounds are not independent.

In this work, we study a new multivariate quadratic (MQ) assumption that can be used to construct public-key encryption schemes. In particular, we research in the following two directions: We establish a precise \emph{asymptotic} formulation of a family of hard MQ problems, and provide empirical evidence to confirm the hardness. %Since there are many practical solvers studied and implemented during the studies of algebraic attacks, we use We construct public-key encryption schemes, and prove their security under the hardness assumption of this family. Also, we provide a new \emph{perspective} to look at MQ systems that plays a key role to our design and proof of security. As a consequence, we construct the \emph{first} public-key encryption scheme that is \emph{provably secure} under the MQ assumption. Moreover, our public-key encryption scheme is efficient in the sense that it only needs a ciphertext length $L + \poly(k)$ to encrypt a message $M\in \{0, 1 \}^{L}$ for any un-prespecified polynomial $L$, where $k$ is the security parameter. This is essentially \emph{optimal} since an additive overhead is the best we can hope for.

The goal of Multi-Party Computation (MPC) is to perform an arbitrary computation in a distributed, private, and fault-tolerant way. For this purpose, a fixed set of n parties runs a protocol that tolerates an adversary corrupting a subset of the parties, preserving certain security guarantees like correctness, secrecy, robustness, and fairness. Corruptions can be either passive or active: A passively corrupted party follows the protocol correctly, but the adversary learns the entire internal state of this party. An actively corrupted party is completely controlled by the adversary, and may deviate arbitrarily from the protocol. A mixed adversary may at the same time corrupt some parties actively and some additional parties passively. In this work, we consider the statistical setting with mixed adversaries and study the exact consequences of active and passive corruptions on secrecy, correctness, robustness, and fairness separately (i.e., hybrid security). Clearly, the number of passive corruptions affects the thresholds for secrecy, while the number of active corruptions affects all thresholds. It turns out that in the statistical setting, the number of passive corruptions in particular also affects the threshold for correctness, i.e., in all protocols there are (tolerated) adversaries for which a single additional passive corruption is sufficient to break correctness. This is in contrast to both the perfect and the computational setting, where such an influence cannot be observed. Apparently, this effect arises from the use of information-theoretic signatures, which are part of most (if not all) statistical protocols.

In this paper, we introduce a new kind of homomorphic signature, which is suitable for identity authentication in cloud computing. User firstly gives his full signature (involves all his identity attributes) to the identity authentication server. During the valid period of his full signature, if the user wants to require a cloud service on a special identity (only involves part of identity attributes), he only needs to secretly send a $\{0,1\}^n$ vector to the identity authentication server. The identity authentication server who doesn't know the secret key can compute the partial signature on the special identity, and then signs it to the cloud server. We give a formal secure definition of this homomorphic signature, and construct a scheme from GHR signature. We prove that our scheme is secure under strong RSA assumption.

The Rainbow Signature Scheme is a non-trivial generalization of the well known Unbalanced Oil and Vinegar Signature Scheme (Eurocrypt '99) minimizing the length of the signatures. Recently a new variant based on non-commutative rings, called NC-Rainbow, was introduced at CT-RSA 2012 to further minimize the secret key size. We disprove the claim that NC-Rainbow is as secure as Rainbow in general and show how to reduce the complexity of MinRank attacks from 2^288 to 2^112 and of HighRank attacks from 2^128 to 2^96 for the proposed instantiation over the ring of Quaternions. We further reveal some facts about Quaternions that increase the complexity of the signing algorithm. We show that NC-Rainbow is just a special case of introducing further structure to the secret key in order to decrease the key size. As the results are comparable with the ones achieved by equivalent keys, which provably do not decrease security, and far worse than just using a PRNG, we recommend not to use NC-Rainbow.

Recent research has shown that many popular web applications are vulnerable to side-channel attacks on encrypted streams of network data produced by the interaction of a user with an application. As a result, private user data is susceptible to being recovered by a side-channel adversary. A recent focus has been on the development of tools for the detection and quantification of side-channel information leaks from such web applications. In this work we describe a model for these web applications, analyse the effectiveness of previous approaches for the quantification of information leaks, and describe a robust, effective and generically applicable metric based on a statistical estimation of the mutual information between the user inputs made in the application and subsequent observable side-channel information. We use our proposed metric to construct a test capable of analysing sampled traces of packets to detect information leaks, and demonstrate the application of our test on a real-world web application.

In this paper we study public-key encryption schemes based on error-correcting codes that are IND-CCA2 secure in the standard model. In particular, we analyze a protocol due to Dowsley, Muller-Quade and Nascimento, based on a work of Rosen and Segev. The original formulation of the protocol contained some ambiguities and incongruences, which we point out and correct; moreover, the protocol deviates substantially from the work it is based on. We then present a construction which resembles more closely the original Rosen-Segev framework, and show how this can be instantiated with the McEliece scheme.

A self-pairing is a pairing computation where both inputs are the same group element. Self-pairings are used in some cryptographic schemes and protocols. In this paper, we show how to compute the Tate-Lichtenbaum pairing (D,\phi(D)) on a curve more efficiently than the general case. The speedup is obtained by requiring a simpler final exponentiation. We also discuss how to use this pairing in cryptographic applications.

Fully homomorphic encryption (FHE) techniques are capable of performing encrypted computation on Boolean circuits, i.e., the user specifies encrypted inputs to the program, and the server computes on the encrypted inputs. Applying these techniques to general programs with recursive procedures and data-dependent loops has not been a focus of attention. In this paper, we take a first step toward building a compiler that, given programs with complex control flow, generates efficient code suitable for the application of FHE schemes. We first describe how programs written in a small Turing-complete instruction set can be executed with encrypted data and point out inefficiencies in this methodology. We then provide examples of transforming (a) the greatest common divisor (GCD) problem using Euclid’s algorithm and (b) the 3-Satisfiability (3SAT) problem using a recursive backtracking algorithm into a path-levelized form to which FHE can be applied. We describe how path levelization reduces control flow ambiguity and improves encrypted computation efficiency. Using these techniques and data-dependent loops as a starting point, we then build support for hierarchical programs made up of phases, where each phase corresponds to a fixed point computation that can be used to further improve the efficiency of encrypted computation. In our setting, the adversary learns an estimate of the number of steps required to complete the computation, which we show is the least amount of leakage possible.

Garbled circuits, a classical idea rooted in the work of Andrew Yao, have long been understood as a cryptographic technique, not a cryptographic goal. Here we cull out a primitive corresponding to this technique. We call it a garbling scheme. We provide a provable-security treatment for garbling schemes, endowing them with a versatile syntax and multiple security definitions. The most basic of these, privacy, suffices for two-party secure function evaluation (SFE) and private function evaluation (PFE). Starting from a PRF, we provide an efficient garbling scheme achieving privacy and we analyze its concrete security. We next consider obliviousness and authenticity, properties needed for private and verifiable outsourcing of computation. We extend our scheme to achieve these ends. We provide highly efficient blockcipher-based instantiations of both schemes. Our treatment of garbling schemes presages more efficient garbling, more rigorous analyses, and more modularly designed higher-level protocols.

In this article, we study the security of the IDEA block cipher when it is used in various simple-length or double-length hashing modes. Even though this cipher is still considered as secure, we show that one should avoid its use as internal primitive for block cipher based hashing. In particular, we are able to generate instantaneously free-start collisions for most modes, and even semi-free-start collisions, pseudo-preimages or hash collisions in practical complexity. This work shows a practical example of the gap that exists between secret-key and known or chosen-key security for block ciphers. Moreover, we also settle the 20-year-old standing open question concerning the security of the Abreast-DM and Tandem-DM double-length compression functions, originally invented to be instantiated with IDEA. Our attacks have been verified experimentally and work even for strengthened versions of IDEA with any number of rounds.

In the past twenty years, the study of the conjunction of chaos and cryptography has attracted much interest but also met with many problems. Today the security of chaos-based encryptions is usually not considered comparable to those based on number theoretic functions. In this paper, instead of making an encryption system, we focus on the more fundamental notion of one-way function, which is a well-defined function that is easy to evaluate but hard to invert. We see that it is more natural to compare chaotic systems with one-way functions, and such a study could possibly give new insights for chaos-based cryptosystems. We propose a function based on Chebyshev polynomials, and we argue it is likely a one-way function.

We describe an implementation of the protocol of Damgard, Pastro, Smart and Zakarias (SPDZ/Speedz) for multi-party computation in the presence of a dishonest majority of active adversaries. We present a number of modifications to the protocol; the first reduces the security to covert security, but produces significant performance enhancements; the second enables us to perform bit-wise operations in characteristic two fields. As a bench mark application we present the evaluation of the AES cipher, a now standard bench marking example for multi-party computation. We need examine two different implementation techniques, which are distinct from prior MPC work in this area due to the use of MACs within the SPDZ protocol. We then examine two implementation choices for the finite fields; one based on finite fields of size $2^8$ and one based on embedding the AES field into a larger finite field of size $2^{40}$.

In this paper, we introduce the abstraction of Dual Form Signatures as a useful framework for proving security (existential unforgeability) from static assumptions for schemes with special structure that are used as a basis of other cryptographic protocols and applications. We demonstrate the power of this framework by proving security under static assumptions for close variants of pre-existing schemes: \begin{itemize} \item the LRSW-based Camenisch-Lysyanskaya signature scheme \item the identity-based sequential aggregate signatures of Boldyreva, Gentry, O'Neill, and Yum. \end{itemize} The Camenisch-Lysyanskaya signature scheme was previously proven only under the interactive LRSW assumption, and our result can be viewed as a static replacement for the LRSW assumption. The scheme of Boldyreva, Gentry, O'Neill, and Yum was also previously proven only under an interactive assumption that was shown to hold in the generic group model. The structure of the public key signature scheme underlying the BGOY aggregate signatures is quite distinctive, and our work presents the first security analysis of this kind of structure under static assumptions. We view our work as enhancing our understanding of the security of these signatures, and also as an important step towards obtaining proofs under the weakest possible assumptions. Finally, we believe our work also provides a new path for proving security of signatures with embedded structure. Examples of these include: attribute-based signatures, quoteable signatures, and signing group elements.

In this paper, we point out a new weakness of the AES key schedule by revisiting an old observation exploited by many known attacks. We also discover a major cause for this weakness is that the column-by-column word-wise property in the key schedule matches nicely with the MixColumns operation in the cipher's diffusion layer. Then we propose a new key schedule by minor modification to increase the security level for AES. First, it reduces the number of rounds that some attacks are effective, such as SQUARE attacks and meet-in-the-middle attacks; Second, it is interesting that our new key schedule also protects AES from the most devastating related-key differential type attacks, which work against AES-192 and AES-256 with the full number of rounds. Compared with the original key schedule, ours just does a transposition on the output matrix of the subkeys. Compared with other proposed modifications of AES key schedule, our modification adds no non-linear operations, no need to complicate the diffusion method, or complicate the iteration process of generating subkeys. Finally, our results suggest that the route of diffusion propagation should get more attention in the design of key schedules.

In this study, a novel pairing based strong designated verifier signature scheme based on non-interactive zero knowledge proofs is proposed. The security of the proposal is presented by sequences of games without random oracles; furthermore, this scheme has a security proof for the property of privacy of the signer’s identity in comparison with the scheme proposed by Zhang et al. in 2007. In addition, this proposal compared to the scheme presented by Huang et al. in 2011 supports non-delegatability. The non-delegatability of our proposal is achieved since we do not use the common secret key shared between the signer and the designated verifier in our construction. Furthermore, if a signer delegates her signing capability which is derived from her secret key on a specific message to a third party, then, the third party cannot generate a valid designated verifier signature due to the relaxed special soundness of the non-interactive zero knowledge proof. To the best of our knowledge, this construction is the first attempt to generate a designated verifier signature scheme with non-delegatability in the standard model, while satisfying of non-delegatability property is loose.

Developers building cryptography into security-sensitive applications face a daunting task. Not only must they understand the security guarantees delivered by the constructions they choose, they must also implement and combine them correctly and efficiently. Cryptographic compilers free developers from having to implement cryptography on their own by turning high-level specifications of security goals into efficient implementations. Yet, trusting such tools is risky as they rely on complex mathematical machinery and claim security properties that are subtle and difficult to verify. In this paper, we present ZKCrypt, an optimizing cryptographic compiler that achieves an unprecedented level of assurance without sacrificing practicality for a comprehensive class of cryptographic protocols, known as Zero-Knowledge Proofs of Knowledge. The pipeline of ZKCrypt tightly integrates purpose-built verified compilers and verifying compilers producing formal proofs in the CertiCrypt framework. By combining the guarantees delivered by each stage in the pipeline, ZKCrypt provides assurance that the implementation it outputs securely realizes the high-level proof goal given as input. We report on the main characteristics of ZKCrypt, highlight new definitions and concepts at its foundations, and illustrate its applicability through a representative example of an anonymous credential system.

The Galois configuration of Nonlinear Feedback Shift Registers (NLFSRs) is attractive for stream ciphers for which high throughput is very important. In this paper, we prove that any Galois NLFSR can be transformed into an equivalent NLFSR in the Fibonacci configuration, which is the conventional conguration of NLFSRs. The transformation is mentioned in the proof. The mapping between the initial states of the Galois NLFSR and its equivalent Fibonacci configuration is also derived. Moreover, some properties of Galois NLFSRs are presented.

A generic DPA strategy is one which is able to recover secret information from physically observable device leakage without any a priori knowledge about the device's leakage characteristics. Here we provide much-needed clarification on results emerging from the existing literature, demonstrating precisely that such methods (strictly defined) are inherently restricted to a very limited selection of target functions. Continuing to search related techniques for a `silver bullet' generic attack appears a bootless errand. However, we find that a minor relaxation of the strict definition---the incorporation of some minimal non-device-specific intuition---produces scope for generic-emulating strategies, able to succeed against a far wider range of targets. We present stepwise regression as an example of such, and demonstrate its effectiveness in a variety of scenarios. We also give some evidence that its practical performance matches that of `best bit' DoM attacks which we take as further indication for the necessity of performing profiled attacks in the context of device evaluations.

Yao's garbled circuit construction transforms a boolean circuit $C:\{0,1\}^n\to\{0,1\}^m$ into a ``garbled circuit'' $\hat{C}$ along with $n$ pairs of $k$-bit keys, one for each input bit, such that $\hat{C}$ together with the $n$ keys corresponding to an input $x$ reveal $C(x)$ and no additional information about $x$. The garbled circuit construction is a central tool for constant-round secure computation and has several other applications. Motivated by these applications, we suggest an efficient arithmetic variant of Yao's original construction. Our construction transforms an arithmetic circuit $C : \mathbb{Z}^n\to\mathbb{Z}^m$ over integers from a bounded (but possibly exponential) range into a garbled circuit $\hat{C}$ along with $n$ affine functions $L_i : \mathbb{Z}\to \mathbb{Z}^k$ such that $\hat{C}$ together with the $n$ integer vectors $L_i(x_i)$ reveal $C(x)$ and no additional information about $x$. The security of our construction relies on the intractability of the learning with errors (LWE) problem.

We propose a novel small-domain pseudo-random permutation, also referred to as a small-domain cipher or small-domain (deterministic) encryption. We prove that our construction achieves "strong security", i.e., is indistinguishable from a random permutation even when an adversary has observed all possible input-output pairs. More importantly, our construction is 1,000 to 8,000 times faster in most realistic scenarios, in comparison with the best known construction (also achieving strong security). Our implementation leverages the extended instruction sets of modern processors, and we also introduce a smart caching strategy to freely tune the tradeoff between time and space.

Recently, He et al. [D. He, J. Chen, J. Hu, A pairing-free certificateless authenticated key agreement protocol, International Journal of Communication Systems, 25(2), pp. 221-230, 2012] proposed a pairing-free certificateless authenticated key agreement protocol and demonstrated that their protocol is provable security in the random oracle model. However, in this paper, we show that t He et al. protocol is completely broken.

A private set intersection (PSI) protocol allows two parties to compute the intersection of their input sets privately. Most of the previous PSI protocols only output the result to one party and the other party gets nothing from running the protocols. However, a mutual PSI protocol in which both parties can get the output is highly desirable in many applications. A major obstacle in designing a mutual PSI protocol is how to ensure fairness. In this paper we present the first fair mutual PSI protocol which is efficient and secure. Fairness of the protocol is obtained in an optimistic fashion, i.e. by using an offline third party arbiter. In contrast to many optimistic protocols which require a fully trusted arbiter, in our protocol the arbiter is only required to be semi-trusted, in the sense that we consider it to be a potential threat to both parties’ privacy but believe it will follow the protocol. The arbiter can resolve disputes without knowing any private information belongs to the two parties. This feature is appealing for a PSI protocol in which privacy may be of ultimate importance.

The Linux pseudorandom number generator (PRNG) is a PRNG with entropy inputs which is widely used in many security related applications and protocols. This PRNG is written as an open source code which is subject to regular changes. It was last analyzed in the work of Gutterman et al. in 2006 [GPR06] but since then no new analysis has been made available, while in the meantime several changes have been applied to the code, among others, to counter the attacks presented [GPR06]. Our work describes the Linux PRNG of kernel versions 2.6.30.7 and upwards. We detail the PRNG architecture in the Linux system and provide its first accurate mathematical description and a precise analysis of the building blocks, including entropy estimation and extraction. Subsequently, we give a security analysis including the feasibility of cryptographic attacks and an empirical test of the entropy estimator.. Finally, we underline some important changes to the previous versions and their consequences.

Identity based encryption (IBE) has received great attention since Boneh and Franklin's breakthrough work on bilinear group based IBE [4]. Till now, many IBE schemes relying on bilinear groups with diff erent properties have been proposed [5, 25, 29, 14]. However, one part of the user's private key in all these IBE schemes is constructed as y = f(msk), where msk is the master key and y is an element in the underlying bilinear group G. In this paper, we propose a new IBE: one part of the private key is y = f(msk), where msk is the master key and y is an element in Z_p . Here p is the underlying bilinear group's prime order. By using some novel techniques, we prove this new IBE is semantic secure under the selective identity chosen plaintext attacks (IND-sID-CPA) in the standard model. Based on this IBE scheme, we construct an IND-ID-CCA secure identity based proxy re-encryption (IBPRE) scheme which is master secret secure and efficient for the proxy compared with other IND-ID-CCA (IBPRE) schemes.

The Tardos code is a much studied collusion-resistant fingerprinting code, with the special property that it has asymptotically optimal length $m\propto c_0^2$, where $c_0$ is the number of colluders. In this paper we give alternative security proofs for the Tardos code, working with the assumption that the strongest coalition strategy is position-independent. We employ the Bernstein inequality and Bennett inequality instead of the typically used Markov inequality. This proof technique requires fewer steps and slightly improves the tightness of the bound on the false negative error probability. We present new results on code length optimization, for both small and asymptotically large coalition sizes.

Bitcoin is a decentralized payment system that is based on Proof-of-Work. Bitcoin is currently gaining popularity as a digital currency; several businesses are starting to accept Bitcoin transactions. An example case of the growing use of Bitcoin was recently reported in the media; here, Bitcoins were used as a form of fast payment in a local fast-food restaurant. In this paper, we analyze the security of using Bitcoin for fast payments, where the time between the exchange of currency and goods is short (i.e., in the order of few seconds). We focus on double- spending attacks on fast payments and demonstrate that these attacks can be mounted at low cost on currently deployed versions of Bitcoin. We further show that the measures recommended by Bitcoin developers for the use of Bitcoin in fast transactions are not always effective in resisting double-spending; we show that if those recommendations are integrated in future Bitcoin implementations, double-spending attacks on Bitcoin will still be possible. Finally, we leverage on our findings and propose a lightweight countermeasure that enables the detection of double-spending attacks in fast transactions.

In implementation of elliptic curve cryptography, three kinds of finite fields have been widely studied, i.e. prime field, binary field and optimal extension field. In pairing-based cryptography, however, pairing-friendly curves are usually chosen among ordinary curves over prime fields and supersingular curves over extension fields with small characteristics. In this paper, we study pairings on elliptic curves over extension fields from the point of view of accelerating the Miller's algorithm to present further advantage of pairing-friendly curves over extension fields, not relying on the much faster field arithmetic. We propose new pairings on elliptic curves over extension fields can make better use of the multi-pairing technique for the efficient implementation. By using some implementation skills, our new pairings could be implemented much more efficiently than the optimal ate pairing and the optimal twisted ate pairing on elliptic curves over extension fields. At last, we use the similar method to give more efficient pairings on Estibals's supersingular curves over composite extension fields in parallel implementation.

A $(t,n)$-threshold secret sharing scheme is a method to distribute a secret among $n$ participants in such a way that any $t$ participants can recover the secret, but no $t-1$ participants can. In this paper, we propose two secret sharing schemes using non-abelian groups. One scheme is the special case where all the participants must get together to recover the secret. The other one is a $(t,n)$-threshold scheme that is a combination of Shamir's scheme and the group-theoretic scheme proposed in this paper.

A cumulative assignment scheme (CAS for short) is a special type of secret sharing schemes. For any given access structure (AS), a CAS which minimizes the cardinality of the primitive share set (the average information rate, or the worst information rate) is called an optimal CAS and can be constructed via solving some binary integer programming (BIP). The problem of finding optimal CAS's for complete AS's is solved. We consider in this paper the problem of finding optimal CAS's for incomplete AS's. The paper introduces some notions including the connected-super-forbidden-family and the lower-forbidden-family for AS's. We show that an optimal CAS can be derived from some smaller sized BIP whose variables (constraints, resp.) are based on the connected-super-forbidden-family (lower-forbidden-family, resp.) of the given AS. The paper further builds the close relationship between the problem of finding optimal CAS's and the set covering problem (SCP). We prove that the problem of finding a CAS with minimum cardinality of the primitive share set (or minimum average information rate) is equivalent to the SCP, and thus is NP-hard. Other contributions of the paper include: 1) two types of AS's are recognized so that we can construct the corresponding optimal CAS's directly; and 2) a greedy algorithm is proposed to find CAS's with smaller worst information rate.

This manuscript describes a proposal for a new trap-door one-way function of the multivariate-quadratic type. It was first posted to the IACR preprint server in May 2012. Subsequently, Enrico Thomae and Christopher Wolf were able to to determine that a small-minors MinRank attack works against this scheme. I would like to thank them for their close study of the proposal. The manuscript follows as originally posted, with the addition of a few references and a brief description of the successful attack (end of Section 4.1).

In this work we deal with the problem of how to squeeze multiple ciphertexts without losing original message information. To do so, we formalize the notion of decompos- ability for public-key encryption and investigate why adding decomposability is challenging. We construct an ElGamal encryption scheme over extension fields, and show that it supports the efficient decomposition. We then analyze security of our scheme under the standard DDH assumption, and evaluate the performance of our construction.

Although they do not suffer from clear attacks, various key agreement protocols (for example that used within the TLS protocol) are deemed as insecure by existing security models for key exchange. The reason is that the derived keys are used within the key exchange step, violating the common key indistinguishability requirement. In this paper we propose a new security definition for key exchange protocols that offers two important benefits. Our notion is weaker than the more established ones and thus allows the analysis of a larger class of protocols. Furthermore, security in the sense that we define enjoys rather general composability properties. In addition our composability properties are derived within game based formalisms, and do not appeal to any simulation based paradigm. Specifically, for protocols whose security relies exclusively on some underlying symmetric primitive we show that they can be securely composed with key exchange protocols provided that two main requirements hold: 1) no adversary can break the underlying {\em primitive}, even when the primitive uses keys obtained from executions of the key exchange protocol in the presence of the adversary (this is essentially the security requirement that we introduce and formalize in this paper), and 2) the security of the protocol can be reduced to that of the primitive, no matter how the keys for the primitive are distributed. Proving that the two conditions are satisfied, and then applying our generic theorem, should be simpler than performing a monolithic analysis of the composed protocol. We exemplify our results in the case of a profile of the TLS protocol. Our definition and results are set entirely within the framework of cryptographic games (and thus avoid the use of simulation).

I propose the new key distribution system and attribute-based encryption scheme on non-commutative ring where the complexity required for enciphering and deciphering is small. As in this system encryption keys and decryption keys involve the attributes of each user, the system is adaptive for cloud computing systems. The security of this system is based on the complexity for solving the multivariate algebraic equations of high degree over finite field, that is, one of NP complete problems. So this system is immune from the Gröbner basis attacks. The key size of this system becomes to be small enough to handle.

The security of contemporary homomorphic encryption schemes over cyclotomic number field relies on fields of very large dimension. This large dimension is needed because of the large modulus-to-noise ratio in the key-switching matrices that are used for the top few levels of the evaluated circuit. However, a smaller modulus-to-noise ratio is used in lower levels of the circuit, so from a security standpoint it is permissible to switch to lower-dimension fields, thus speeding up the homomorphic operations for the lower levels of the circuit. However, implementing such field-switching is nontrivial, since these schemes rely on the field algebraic structure for their homomorphic properties. A basic ring-switching operation was used by Brakerski, Gentry and Vaikuntanathan, over rings of the form $\Z[X]/(X^{2^n}+1)$, in the context of bootstrapping. In this work we generalize and extend this technique to work over any cyclotomic number field, and show how it can be used not only for bootstrapping but also during the computation itself (in conjunction with the ``packed ciphertext'' techniques of Gentry, Halevi and Smart).

In~\cite{SSH} a Zero-Knowledge scheme $ZK(2)$ was designed from a solution of a set of multivariate quadratic equations over a finite field. In this paper we will give two methods to generalize this construction for polynomials of any degree $d$, i.e. we will design two Zero-Knowledge schemes $ZK(d)$ and $\tilde {ZK}(d)$ from a set of polynomial equations of degree $d$. We will show that $\tilde {ZK} (d)$ is optimal in term of the number of computations to be performed and that $ZK(d)$ is optimal in term of the number of bits to be send. Moreover this property is still true for all kinds of polynomials: for example if the polynomials are sparse or dense. Finally, we will present two examples of applications: with Brent equations, or with morphisms of polynomials.

The hash function Skein is one of the five finalists of the NIST SHA-3 competition;it is based on the block cipher Threefish which only uses three primitive operations: modular addition, rotation and bitwise XOR (ARX). This paper studies the boomerang attacks on Skein-512. Boomerang distinguishers on the compression function reduced to 32 and 36 rounds are proposed, with complexities 2^{104.5} and 2^{454} respectively. Examples of the distinguishers on 28-round and 31-round are also given. In addition, the boomerang distinguishers are applicable to the key-recovery attacks on reduced Threefish-512. The complexities for key-recovery attacks reduced to 32-/33-/34-round are about 2^{181}, 2^{305} and 2^{424}. Because Laurent et al. [14] pointed out that the previous boomerang distinguishers for Threefish-512 are in fact not compatible, our attacks are the first valid boomerang attacks for the final round Skein-512.

We present in these papers a scheme, which bypasses the weakness presented in the existed scheme of IBE with random oracle. We propose, a secure scheme which project into Zp contrary to elliptic curve as with Boneh and Franklin. More, our scheme is basing in its study of simulation in the problem 4-EBDHP which is more efficient than q-BDHIP used by Skai Kasarah. We provide the prove of security of our scheme and we show its efficiency by comparison with the scheme declared above. Even if it we have a little cost in complexity, but as in the field cryptography we are more interested to the security, this makes our proposition more efficient.

We exhibit the precise security guarantees that a public key encryption scheme needs to satisfy to guarantee ballot privacy when used in a large class of voting systems. We also identify new security notions for public key encryption that characterize the number of times that a public key can be used in different elections, and show that the most common ballot preparation approach that consists in encrypting the vote and adding a NIZK proof of its validity is sound, even without hardwiring the voter identity in the proof. Our results provide important steps towards proving the privacy of the ballot submission procedure in the widely deployed Helios voting system.

The Ring-LWE problem, introduced by Lyubashevsky, Peikert, and Regev (Eurocrypt 2010), has been steadily finding many uses in numerous cryptographic applications. Still, the Ring-LWE problem defined in [LPR10] involves the fractional ideal $R^\vee$, the dual of the ring $R$, which is the source of many theoretical and implementation technicalities. Until now, getting rid of $R^\vee$, required some relatively complex transformation that substantially increase the magnitude of the error polynomial and the practical complexity to sample it. It is only for rings $R=\Z[X]/(X^n+1)$ where $n$ a power of $2$, that this transformation is simple and benign. In this work we show that by applying a different, and much simpler transformation, one can transfer the results from [LPR10] into an ``easy-to-use'' Ring-LWE setting ({\em i.e.} without the dual ring $R^\vee$), with only a very slight increase in the magnitude of the noise coefficients. Additionally, we show that creating the correct noise distribution can also be simplified by generating a Gaussian distribution over a particular extension ring of $R$, and then performing a reduction modulo $f(X)$. In essence, our results show that one does not need to resort to using any algebraic structure that is more complicated than polynomial rings in order to fully utilize the hardness of the Ring-LWE problem as a building block for cryptographic applications.

Collision resistance is a fundamental property required for cryptographic hash functions. One way to ensure collision resistance is to use hash functions based on public key cryptography (PKC) which reduces collision resistance to a hard mathematical problem, but such primitives are usually slow. A more practical approach is to use symmetric-key design techniques which lead to faster schemes, but collision resistance can only be heuristically inferred from the best probability of a single differential characteristic path. We propose a new hash function design with variable hash output sizes of 128, 256, and 512 bits, that reduces this gap. Due to its inherent Substitution-Permutation Network (SPN) structure and JH mode of operation, we are able to compute its differential collision probability using the concept of differentials. Namely, for each possible input differences, we take into account all the differential paths leading to a collision and this enables us to prove that our hash function is secure against a differential collision attack using a single input difference. None of the SHA-3 finalists could prove such a resistance. At the same time, our hash function design is secure against pre-image, second pre-image and rebound attacks, and is faster than PKC-based hashes. Part of our design includes a generalization of the optimal diffusion used in the classical wide-trail SPN construction from Daemen and Rijmen, which leads to near-optimal differential bounds when applied to non-square byte arrays. We also found a novel way to use parallel copies of a serial matrix over the finite field GF(2^4), so as to create lightweight and secure byte-based diffusion for our design. Overall, we obtain hash functions that are fast in software, very lightweight in hardware (about 4625 GE for the $256$-bit hash output) and that provide much stronger security proofs regarding collision resistance than any of the SHA-3 finalists.