Private Information Retrieval (PIR) allows for retrieval of bits from a database in a way that hides a user's access pattern from the server. However, its practicality in a cloud computing setting has recently been questioned. In such a setting, PIR's enormous computation and communication overhead is expected to outweigh any cost saving advantages of cloud computing. This paper presents PIRMAP, a practical, highly efficient protocol for PIR in MapReduce, a widely supported cloud computing API. PIRMAP focuses especially on the retrieval of large files from the cloud, where it achieves close to optimal communication complexity with query times significantly faster than previous schemes. To achieve this, PIRMAP uses a special case of Lipmaa's PIR protocol that allows for optimal parallel computation during the "Map" phase of MapReduce, and homomorphic aggregation in the "Reduce" phase. To improve computational cost, we also use newer, faster homomorphic encryption which makes our scheme practical for databases of useful size, while keeping the communication costs low. PIRMAP has been implemented and tested in Amazon's public cloud with total database sizes of up to 1~TByte. Our performance evaluations show that PIRMAP is more than one order of magnitude cheaper and faster than "trivial PIR" on Amazon and adds only 20% overhead to a theoretical optimal PIR.

We revisit the problem of cross-domain secure communication between two users belonging to different security domains within an open and distributed environment. Existing approaches presuppose that either the users are in possession of public key certificates issued by a trusted certificate authority (CA), or the associated domain authentication servers share a long-term secret key. In this paper, we propose a variety of four-party password-based authenticated key exchange (4PAKE) protocols that take a different approach from previous work. The users are not required to have public key certificates, but they simply reuse their login passwords they share with their respective domain authentication servers. On the other hand, the authentication servers, assumed to be part of a standard PKI, act as ephemeral CAs that "certify'' some key materials that the users can subsequently use to exchange and agree on a session key. Moreover, we adopt a compositional approach. That is, by treating any secure two-party password-based key exchange (2PAKE) protocol and two-party asymmetric-key/symmetric-key based key exchange (2AAKE/2SAKE) protocol as black boxes, we combine them to obtain generic and provably secure 4PAKE protocols. We also show that one can derive a 4PAKE protocol from just a 2PAKE protocol.

In this paper, by modifying a subclass of bent functions in $\mathcal P S_{ap}$, we construct another subclass of bent functions in $\mathcal P S^+$ with maximum algebraic degree. We demonstrate that the algebraic immunity of the constructed functions is maximum. The result is proved by using the well known conjecture proposed by Tu and Deng (Des. Codes Cryptogr. 60(1), pp. 1-14, 2011) which has been proved recently by Cohen and Flori (http://eprint.iacr.org/ 2011/400.pdf). Finally, we identify a class of $\cD_0$ type bent functions constructed by modifying Dillon functions whose lower bound on second-order nonlinearity is very high.

Group key agreement (GKA) protocols Play a main role in constructing secure multicast channels. These protocols are algorithms that describe how a group of parties communicating over a public network can gain a common secret key. ID-based authenticated group key agreement (AGKA) cryptosystems based on bilinear pairings are update researching subject because of the simplicity of their public key management and their efficiency. The key agreement protocol is a good way to establish a common session key for communication. But in a group of member’s communication, we not only need to establish a common session key, but also need to concern the member changing situation. In this paper we propose a protocol based on Weil pairing, ID-based authentication and complete ternary tree architecture. We show that our protocol satisfies all known security requirements, and therefore it is more secure and efficient than the compared group key exchange protocols that we discuss in this article.

In this article we propose an identity based key agreement protocol based on elliptic curve cryptography (ECC) between users of different networks with independent private key generations (PKGs). Our protocol is based on Cao et al.'s protocol ,proposed in 2010, in which instead of bilinear pairings, elliptic curves are used for constructing an ID-based key agreement protocol . Our protocol develops Cao et al's protocol for situations that two users of independent organizations or networks with separate servers (that in this article, are named PKGs, because their main duty is generating private keys for the users) want to share a secret key via an insecure link. We also prove the security of the protocol in the random oracle model.

Certificateless cryptosystems were proposed by Al-Riyami and Paterson in 2003 [1] to solve problems of public key cryptosystems based on PKI and based on identity. Up to now, various types of certificateless cryptographic primitives as encryption functions, signature schemes, key agreement protocols and etc, have been designed. But to the best of our knowledge, multiple-key agreement protocols have not been proposed based on certificateless cryptosystem yet. So in this paper we propose a certificateless authenticated multiple-key agreement protocol with bilinear pairings.

Designing an ID based signcryption scheme in the standard model is among the most interesting and important problems in cryptography. However, all the existing systems in the ID based setting, in the standard model, do not have either the unforgeability property or the indistinguishability property or both of them. In this paper, we present the first provably secure ID based signcryption scheme in the standard model with both these properties. The unforgeability property of this scheme is based on the hardness of Computational Diffie-Hellman problem and the indistinguishability property of this scheme is based on the hardness of Decisional Bilinear Diffie-Hellman problem. Our scheme is strongly unforgeable in the strong attack mode called insider security. Moreover, our scheme possess an interesting property called public verifiability of the ciphertext. Our scheme integrates cleverly, a modified version of Waters' IBE and a suitably modified version of the ID based signature scheme in the standard model proposed by Paterson et al. However, our security reductions are more efficient. Specifically, while the security reductions for indistinguishability is similar to the bounds of Waters' scheme, the unforgeability reductions are way better than the bounds for Paterson et al.'s scheme.

Privacy of RFID systems is receiving increasing attentions in the RFID community and an important issue required as to the security of RFID system. Backward privacy means the adversary can not trace the tag later even if he reveals the internal states of the tag sometimes before. In this paper, we analyze two recently proposed RFID authentication schemes: Randomized GPS and Randomized Hashed GPS scheme. We show both of them can not provide backward privacy in Juels and Weis privacy model, which allows the adversary to know whether the reader authenticates the tag successfully or not. In addition, we present a new protocol, called Challenge-Hiding GPS, based on the Schnorr identification scheme. The challenge is hidden from the eavesdropping through the technique of Diffie-Hellman key agreement protocol. The new protocol can satisfy backward privacy, and it has less communication overheads and almost the same computation, compared with the two schemes analyzed.

In this paper we propose an efficient and regular ternary algorithm for scalar multiplication on elliptic curves over finite fields of characteristic three. This method is based on full signed ternary expansion of a scalar to be multiplied. The cost per bit of this algorithm is lower than that of all previous ones.

We present the first wide-forward-insider and wide-strong RFID identification protocols that are based on zero-knowledge. Until now these notions have only been achieved by schemes based on IND-CCA2 encryption. We discuss why wide-forward-insider privacy is sufficient for most practical applications. Rigorous proofs in the standard model are provided for the security and privacy properties of our protocols. Furthermore, our protocols are the most efficient solution presented in the literature. Using only Elliptic Curve Cryptography (ECC), the required circuit area can be minimized such that our protocol even fits on small RFID tags. Concerning computation on the tag, we only require two scalar-EC point multiplications for the wide-forward-insider protocol.

We introduce the notion of {\em arithmetic codex}, or {\em codex} for short. It encompasses several well-established notions from cryptography (arithmetic secret sharing schemes, i.e., enjoying additive as well as multiplicative properties) and algebraic complexity theory (bilinear complexity of multiplication) in a natural mathematical framework. Arithmetic secret sharing schemes have important applications to secure multiparty computation and even to {\em two}-party cryptography. Interestingly, several recent applications to two-party cryptography rely crucially on the existing results on ``{\em asymptotically good} families'' of suitable such schemes. Moreover, the construction of these schemes requires asymptotically good towers of function fields over finite fields: no elementary (probabilistic) constructions are known in these cases. Besides introducing the notion, we discuss some of the constructions, as well as some limitations.

We present a generalized learning with errors (LWE) problem, which is essentially a simple and direct extension of the original LWE problem to the case of matrices. Then we use this new version of LWE problem, which we call matrix LWE problem to build new cryptographic schemes, which include a new scalable key distribution scheme, a new key exchanges scheme and a new simple identity-based encryption scheme.

In 2010, Sood-Sarje-Singh proposed a dynamic ID-based remote user authentication scheme and claimed that their scheme is more secure than Das et al.’s scheme and Liao et al.’s scheme. However, we show that Sood et al.’s scheme is still vulnerable to malicious user attack, man-in-the-middle attack, stolen smart card attack, off-line ID guessing attack, impersonation attack, and server spoofing attack, making the scheme unfeasible for practical implementation.

Instead of purchasing and maintaining their own computing infrastructure, scientists can now run data-intensive scientific applications in a hybrid environment such as cloud computing by facilitating its vast storage and computation capabilities. During the scheduling of such scientific applications for execution, various computation data flows will happen between the controller and computing server instances. Amongst various quality-of-service (QoS) metrics, data security is always one of the greatest concerns to scientists because their data may be intercepted or stolen by malicious parties during those data flows, especially for less secure hybrid cloud systems. An existing typical method for addressing this issue is to apply Internet Key Exchange (IKE) scheme to generate and exchange session keys, and then to apply these keys for performing symmetric-key encryption which will encrypt those data flows. However, the IKE scheme suffers from low efficiency due to its low performance of asymmetric-key cryptological operations over a large amount of data and high-density operations which are exactly the characteristics of scientific applications. In this paper, we propose Cloud Computing Background Key Exchange (CCBKE), a novel authenticated key exchange scheme that aims at efficient security-aware scheduling of scientific applications. Our scheme is designed based on randomness-reuse strategy and Internet Key Exchange (IKE) scheme. Theoretical analyses and experimental results demonstrate that, compared with the IKE scheme, our CCBKE scheme can significantly improve the efficiency by dramatically reducing time consumption and computation load without sacrificing the level of security.

We provide a functional encryption system that supports functionality for regular languages. In our system a secret key is associated with a Deterministic Finite Automata (DFA) M. A ciphertext, CT, encrypts a message m and is associated with an arbitrary length string w. A user is able to decrypt the ciphertext CT if and only if the DFA M associated with his private key accepts the string w. Compared with other known functional encryption systems, this is the first system where the functionality is capable of recognizing an unbounded language. For example, in (Key-Policy) Attribute-Based Encryption (ABE) a private key SK is associated with a single boolean formula which operates over a fixed number of boolean variables from the ciphertext. In contrast, in our system a DFA M will meaningfully operate over an arbitrary length input w. We propose a system that utilizes bilinear groups. Our solution is a "public index" system, where the message m is hidden, but the string w is not. We prove security in the selective model under a variant of the decision l-Bilinear Diffie-Hellman Exponent (BDHE) assumption that we call the decision l-Expanded BDHE problem.

In this paper, we revisit formalizations of information-theoretic security for symmetric-key encryption and key agreement protocols which are very fundamental primitives in cryptography. In general, we can formalize information-theoretic security in various ways: some of them can be formalized as stand-alone security by extending (or relaxing) Shannon's perfect secrecy; some of them can be done based on composable security. Then, a natural question about this is: what is the gap between the formalizations? To answer the question, we investigate relationships between several formalizations of information-theoretic security for symmetric-key encryption and key agreement protocols. Specifically, for symmetric-key encryption protocols which may have decryption-errors, we deal with the following formalizations of security: formalizations extended (or relaxed) from Shannon's perfect secrecy by using mutual information and statistical distance; information-theoretic analogue of indistinguishability by Goldwasser and Micali; and the ones of composable security by Maurer et al. and Canetti. Then, we explicitly show that those formalizations are essentially equivalent under both one-time and multiple-use models. Under the both models, we also derive lower bounds on the adversary's (or distinguisher's) advantage and secret-key size required under all of the above formalizations. Although some of them may be already known, we can explicitly derive them all at once through our relationships between the formalizations. In addition, we briefly observe impossibility results which easily follow from the lower bounds. The similar results are also shown for key agreement protocols which may have agreement-errors.

We extend the work of Bellare, Boldyreva and Staddon on the systematic analysis of randomness reuse to construct multi-recipient encryption schemes to the case where randomness is reused across different cryptographic primitives. We find that through the additional binding introduced through randomness reuse, one can actually obtain a security amplification with respect to the standard black-box compositions, and achieve a stronger level of security. We introduce stronger notions of security for encryption and signatures, where challenge messages can depend in a restricted way on the random coins used in encryption, and show that two variants of the KEM/DEM paradigm give rise to encryption schemes that meet this enhanced notion of security. We obtain a very efficient signcryption scheme that is secure against insider attackers without random oracles.

Since the introducing of extended Canetti-Krawczyk~(eCK) security model for two party key exchange, many protocols have been proposed to provide eCK security. However, most of those protocols are provably secure in the random oracle model or rely on special design technique well-known as the NAXOS trick. In contrast to previous schemes, we present an eCK secure protocol in the standard model, without NAXOS trick and without knowledge of secret key (KOSK) assumption for public key registration. The security proof of our scheme is based on standard pairing assumption, collision resistant hash functions, Bilinear Decision Diffie-Hellman (BDDH) and Decision Linear Diffie-Hellman (DLIN) assumptions, and pseudo-random functions with pairwise independent random source. Although our proposed protocol is based on bilinear groups, it doesn't need any pairing operations during protocol execution.

Following both theoretical and practical arguments, we construct UC-secure bit-commitment protocols that place their strength on the sender’s side and are built using tamper-evident devices, e.g., a type of distinguishable, sealed envelopes. We show that by using a second formalisation of tamper-evident distinguishable envelopes we can attain better security guarantees, i.e., EUC-security. We show the relations between several flavours of weak bit-commitments, bit-commitments and distinguishable tamper-evident envelopes. We focus, at all points, on the lightweight nature of the underlying mechanisms and on the end-to-end human verifiability.

We present a general framework for constructing non-interactive universally composable (UC) commitment schemes that are secure against adaptive adversaries in the non-erasure model under a re-usable common reference string. Previously, such ``fully-equipped'' UC commitment schemes have been known only in [CF01,CLOS02], with strict expansion factor O(k); meaning that to commit L bits, communication strictly requires O(Lk)$ bits, where k denotes the security parameter. Efficient construction of a fully-equipped UC commitment scheme is a long-standing open problem. We introduce new abstraction, called all-but-many encryption (ABME), and prove that it captures fully-equipped UC commitment schemes. We propose the first fully-equipped UC commitment scheme with optimal expansion factor O(1) from our ABME scheme related to the DCR assumption. We also provide an all-but-many lossy trapdoor function (ABM-LTF)[Hof12] from our DCR-based ABME scheme, with a better lossy rate than [Hof12].

Motivated by the recent widespread emergence of location-based services (LBS) over mobile devices, we explore efficient protocols for proximity-testing. Such protocols allow a group of friends to discover if they are all close to each other in some physical location, without revealing their individual locations to each other. We focus on hand-held devices and aim at protocols with very small communication complexity and a small number of rounds. The proximity-testing problem can be reduced to the private equality testing (PET) problem, in which parties find out whether or not they hold the same input (drawn from a low-entropy distribution) without revealing any other information about their inputs to each other. While previous works analyze the 2-party PET special case (and its LBS application), in this work we consider highly-efficient schemes for the multiparty case with no honest majority. We provide schemes for both a direct-communication setting and a setting with a honest-but-curious mediating server that does not learn the users’ inputs. Our most efficient scheme takes 2 rounds, where in each round each user sends only a couple of ElGamal ciphertexts.

Distributed key generation (DKG) has been studied extensively in the cryptographic literature. However, it has never been examined outside of the synchronous setting, and the known DKG protocols cannot guarantee safety or liveness over the Internet. In this work, we present the first realistic DKG protocol for use over the Internet. We propose a practical system model for the Internet and define an efficient verifiable secret sharing (VSS) scheme in it. We observe the necessity of Byzantine agreement for asynchronous DKG and analyze the difficulty of using a randomized protocol for it. Using our VSS scheme and a leader-based agreement protocol, we then design a provably secure DKG protocol. We also consider and achieve cryptographic properties such as uniform randomness of the shared secret and compare static versus adaptive adversary models. Finally, we implement our DKG protocol, and establish its efficiency and reliability by extensively testing it on the PlanetLab platform. Counter to a general non-scalability perception about asynchronous systems, our experiments demonstrate that our asynchronous DKG protocol scales well with the system size and it is suitable for realizing multiparty computation and threshold cryptography over the Internet.

We present the first formal mathematical presentation of the generalized Russian cards problem, and provide rigorous security definitions that capture both basic and extended versions of weak and perfect security notions. In the generalized Russian cards problem, three players, Alice, Bob, and Cathy, are dealt a deck of $n$ cards, each given $a$, $b$, and $c$ cards, respectively. The goal is for Alice and Bob to learn each other's hands via public communication, without Cathy learning the fate of any particular card. The basic idea is that Alice announces a set of possible hands she might hold, and Bob, using knowledge of his own hand, should be able to learn Alice's cards from this announcement, but Cathy should not. Using a combinatorial approach, we are able to give a nice characterization of informative strategies (i.e., strategies allowing Bob to learn Alice's hand), having optimal communication complexity, namely the set of possible hands Alice announces must be equivalent to a large set of $t-(n, a, 1)$-designs, where $t=a-c$. We also provide some interesting necessary conditions for certain types of deals to be simultaneously informative and secure. That is, for deals satisfying $c = a-d$ for some $d \geq 2$, where $b \geq d-1$ and the strategy is assumed to satisfy a strong version of security (namely perfect $(d-1)$-security), we show that $a = d+1$ and hence $c=1$. We also give a precise characterization of informative and perfectly $(d-1)$-secure deals of the form $(d+1, b, 1)$ satisfying $b \geq d-1$ involving $d-(n, d+1, 1)$-designs.

This paper introduces a special type of symmetric cryptosystem called multi-encryption scheme. It allows users to encrypt multiple plaintexts into a single ciphertext. Each plaintext is protected with its own secret key, meaning that they can be decrypted individually by applying the decryption function with the corresponding key to the ciphertext. Compared to encrypting the ciphertexts one-by-one using a standard symmetric cryptosystem, the main advantage of using a multi-encryption scheme is the no-search property, which guarantees that knowing the key is sufficient for decrypting a single plaintext. We show how to construct a multi-encryption scheme based on polynomials over finite fields. A possible application area is coercion-resistant electronic voting. To ensure a strong form of privacy, voters are equipped with multiple fake credentials, which are indistinguishable from the proper one. While theoretically sound, this requires a voter to perfectly recall multiple lengthy random numbers, and to know which of them is the proper one. To ensure 100\% recall, users need to manage these numbers and keep them secret. A multi-encryption scheme is an elegant solution for this problem.

With the launch of Mac OS X 10.7 (Lion), Apple has introduced a volume encryption mechanism known as FileVault 2. Apple only disclosed marketing aspects of the closed-source software, e.g. its use of the AES-XTS tweakable encryption, but a publicly available security evaluation and detailed description was unavailable until now. We have performed an extensive analysis of FileVault 2 and we have been able to find all the algorithms and parameters needed to successfully read an encrypted volume. This allows us to perform forensic investigations on encrypted volumes using our own tools. In this paper we present the architecture of FileVault 2, giving details of the key derivation, encryption process and metadata structures needed to perform the volume decryption. Besides the analysis of the system, we have also built a library that can mount a volume encrypted with FileVault 2. As a contribution to the research and forensic communities we have made this library open source. Additionally, we present an informal security evaluation of the system and comment on some of the design and implementation features. Among others we analyze the random number generator used to create the recovery password. We have also analyzed the entropy of each 512-byte block in the encrypted volume and discovered that part of the user data was left unencrypted.

We consider distributed private data analysis, where $n$ parties each holding some sensitive data wish to compute some aggregate statistics over all parties' data. We prove a tight lower bound for the private distributed summation problem. Our lower bound is strictly stronger than the prior lower-bound result by Beimel, Nissim, and Omri published in CRYPTO 2008. In particular, we show that any $n$-party protocol computing the sum with sparse communication graph must incur an additive error of $\Omega(\sqrt{n})$ with constant probability, in order to defend against potential coalitions of compromised users. Furthermore, we show that in the client-server communication model, where all users communicate solely with an untrusted server, the additive error must be $\Omega(\sqrt{n})$, regardless of the number of messages or rounds. Both of our lower-bounds, for the general setting and the client-to-server communication model, are strictly stronger than those of Beimel, Nissim and Omri, since we remove the assumption on the number of rounds (and also the number of messages in the client-to-server communication model). Our lower bounds generalize to the $(\epsilon, \delta)$ differential privacy notion, for reasonably small values of $\delta$.

We study the slow diffusion of the AES key schedule for 256-bit keys and find weakness which can be used in the preimage attack on its Davis-Meyer mode. Our preimage attack works for 8 rounds of AES-256 with the computational complexity of $2^{124.9}$, while the best previous attack works for 7 rounds of AES-256. It is also extended to the preimage attack on some well-known double-block-length hash modes assuming the underlying block cipher is 8-round AES-256, whose computational complexity is $2^{252.9}$.

We describe a method for efficiently hashing multiple messages of different lengths. Such computations occur in various scenarios, and one of them is when an operating system checks the integrity of its components during boot time. These tasks can gain performance by parallelizing the computations and using SIMD architectures. For such scenarios, we compare the performance of a new 4-buffers SHA-256 S-HASH implementation, to that of the standard serial hashing. Our results are measured on the 2nd Generation Intel® Core™ Processor, and demonstrate SHA-256 processing at effectively ~5.2 Cycles per Byte, when hashing from any of the three cache levels, or from the system memory. This represents speedup by a factor of 3.42x compared to OpenSSL (1.0.1), and by 2.25x compared to the recent and faster n-SMS method. For hashing from a disk, we show an effective rate of ~6.73 Cycles/Byte, which is almost 3 times faster than OpenSSL (1.0.1) under the same conditions. These results indicate that for some usage models, SHA-256 is significantly faster than commonly perceived.

The Boneh-Gentry-Waters (BGW) scheme is one of the most efficient broadcast encryption scheme regarding the overhead size. This performance relies on the use of a pairing. Hence this protocol can benefit from public key improvements. The ciphertext is of constant size, whatever the proportion of revoked users is. The main lasting constraint is the computation time at receiver end as it depends on the number of revoked users. In this paper we describe two modifications to improve the BGW bandwidth and time complexity. First we rewrite the protocol and its security proof with an asymmetric pairing over the Barreto-Naehrig (BN) curves instead of a symmetric one over supersingular curves. This modification leads to a practical gain of 60 % in speed and 84 % in bandwidth. The second tweaks allows to reduce the computation time from $O(n-r)$ to $\min(O(r),O(n-r))$ for the worst case (and better for the average case). We give performance measures of our implementation for a 128-bit security level of the modified protocol on a smartphone.

We give details of the factorization of RSA-704 with CADO-NFS. This is a record computation with publicly available software tools. The aim of this experiment was to stress CADO-NFS - which was originally designed for 512-bit factorizations - for larger inputs, and to identify possible rooms of improvement.

In this paper we present a comprehensive comparison of all Round 3 SHA-3 candidates and the current standard SHA-2 from the point of view of hardware performance in modern FPGAs. Each algorithm is implemented using multiple architectures based on the concepts of iteration, folding, unrolling, pipelining, and circuit replication. Trade-offs between speed and area are investigated, and the best architecture from the point of view of the throughput to area ratio is identified. Finally, all algorithms are ranked based on their overall performance in FPGAs. The characteristic features of each algorithm important from the point of view of its implementation in hardware are identified.

Let $\G$ be a group of prime order $q$, and let $g_1,\ldots,g_n$ be random elements of $\G$. We say that a vector $\vecx = (x_1,\ldots,x_n)\in \Z_q^n$ is a {\em discrete log representation} of some some element $y\in\G$ (with respect to $g_1,\ldots,g_n$) if $g_1^{x_1}\cdots g_n^{x_n} = y$. Any element $y$ has many discrete log representations, forming an affine subspace of $\Z_q^n$. We show that these representations have a nice {\em continuous leakage-resilience} property as follows. Assume some attacker $\A(g_1,\ldots,g_n,y)$ can repeatedly learn $L$ bits of information on arbitrarily many random representations of $y$. That is, $\A$ adaptively chooses polynomially many leakage functions $f_i:\Z_q^n\rightarrow \{0,1\}^L$, and learns the value $f_i(\vecx_i)$, where $\vecx_i$ is a {\em fresh and random} discrete log representation of $y$. $\A$ wins the game if it eventually outputs a valid discrete log representation $\vecx^*$ of $y$. We show that if the discrete log assumption holds in $\G$, then no polynomially bounded $\A$ can win this game with non-negligible probability, as long as the leakage on each representation is bounded by $L\approx (n-2)\log q = (1-\frac{2}{n})\cdot |\vecx|$. As direct extensions of this property, we design very simple continuous leakage-resilient (CLR) one-way function (OWF) and public-key encryption (PKE) schemes in the so called ``invisible key update'' model introduced by Alwen et al. at CRYPTO'09. Our CLR-OWF is based on the standard Discrete Log assumption and our CLR-PKE is based on the standard Decisional Diffie-Hellman assumption. Prior to our work, such schemes could only be constructed in groups with a bilinear pairing. As another surprising application, we show how to design the first leakage-resilient {\em traitor tracing} scheme, where no attacker, getting the secret keys of a small subset of decoders (called ``traitors'') {\em and} bounded leakage on the secret keys of all other decoders, can create a valid decryption key which will not be traced back to at least one of the traitors.

We present a compiler that converts any circuit into one that remains secure even if a constant fraction of its wires are tampered with. Following the seminal work of Ishai et al. (Eurocrypt 2006), we consider adversaries who may choose an arbitrary set of wires to corrupt, and may set each such wire to 0 or to 1, or may toggle with the wire. We prove that such adversaries, who continuously tamper with the circuit, can learn at most logarithmically many bits of secret information (in addition to black-box access to the circuit). Our results are information theoretic.

In cloud storage service, clients upload their data together with authentication information to cloud storage server. To ensure the availability and integrity of clients' stored data, cloud server(CS) must prove to a verifier that he is actually storing all of the client's data unchanged. And, enabling public auditability for cloud storage is of critical importance to users with constrained computing resources, who can resort to a third party auditor (TPA) to check the integrity of outsourced data. However, most of the existing proofs of retrievability schemes or proof of data possession schemes do not consider data privacy problem. Zero knowledge privacy requires TPA or the adversary can not deduce any information of the file data from auditing system. In this paper, after giving a new construction of a recently proposed cryptographic primitive named aggregatable signature based broadcast (ASBB) encryption scheme, we present an efficient public auditing scheme with zero knowledge privacy. The new scheme is as efficient as the scheme presented by Shacham and Waters without considering privacy and is secure in the random oracle model.

We construct zero-knowledge proofs of plaintext knowledge (PoPK) and correct multiplication (PoPC) for the Regev encryption scheme with low amortized communication complexity. Previous constructions of both PoPK and PoPC had communication cost linear in the size of the public key (roughly quadratic in the lattice dimension, ignoring logarithmic factors). Furthermore, previous constructions of PoPK suffered from one of the following weaknesses: either the message and randomness space were restricted, or there was a super-polynomial gap between the size of the message and randomness that an honest prover chose and the size of which an accepting verifier would be convinced. The latter weakness was also present in the existent PoPC protocols. In contrast, O(n) proofs (for lattice dimension n) in our PoPK and PoPC protocols have communication cost linear in the public key. Thus, we improve the amortized communication cost of each proof by a factor linear in the security parameter. Furthermore, we allow the message space to be \Z_p and the randomness distribution to be the discrete Gaussian, both of which are natural choices for the Regev encryption scheme. Finally, in our schemes there is no gap between the the size of the message and randomness that an honest prover chooses and the size of which an accepting verifier is convinced. Our constructions use the ``MPC-in-the-head'' technique of Ishai et al. (STOC 2007). At the heart of our constructions is a protocol for proving that a value is bounded by some publicly known bound. This uses Lagrange's Theorem that states that any positive integer can be expressed as the sum of four squares (an idea previously used by Boudot (EUROCRYPT 2000)), as well as techniques from Cramer and Damgård (CRYPTO 2009).

In the recent years, several hash constructions have been introduced that aim at achieving enhanced security margins by strengthening the Merkle-Damgård mode. However, their security analysis have been conducted independently and using a variety of proof methodologies. This paper unifies these results by proposing a unique indifferentiability proof that considers a broadened form of the general compression function introduced by Stam at FSE09. This general definition enables us to capture in a realistic model most of the features of the mode of operation ({\em e.g.}, message encoding, blank rounds, message insertion,...) within the pre-processing and post-processing functions. Furthermore, it relies on an inner primitive which can be instantiated either by an ideal block cipher, or by an ideal permutation. Then, most existing hash functions can be seen as the Chop-MD construction applied to some compression function which fits the broadened Stam model. Our result then gives the tightest known indifferentiability bounds for several general modes of operations, including Chop-MD, Haifa or sponges. Moreover, we show that it applies in a quite automatic way, by providing the security bounds for 7 out of the 14 second round SHA-3 candidates, which are in some cases improved over previously known ones.

Recently there has been a huge emphasis on constructing cryptographic protocols that maintain their security guarantees even in the presence of side channel attacks. Such attacks exploit the physical characteristics of a cryptographic device to learn useful information about the internal state of the device. Designing protocols that deliver meaningful security even in the presence of such leakage attacks is a challenging task. The recent work of Garg, Jain, and Sahai formulates a meaningful notion of zero-knowledge in presence of leakage; and provides a construction which satisfies a weaker variant of this notion called (1+e)-leakage-resilient-zero-knowledge, for every constant e>0. In this weaker variant, roughly speaking, if the verifier learns L bits of leakage during the interaction, then the simulator is allowed to access (1+e).L bits of leakage. The round complexity of their protocol is n/e. In this work, we present the first construction of leakage-resilient zero-knowledge satisfying the ideal requirement of e=0. While our focus is on a feasibility result for e=0, our construction also enjoys a constant number of rounds. At the heart of our construction is a new ``public-coin preamble'' which allows the simulator to recover arbitrary information from a (cheating) verifier in a ``straight line.'' We use non-black-box simulation techniques to accomplish this goal.

Key establishment is a crucial primitive for building secure channels: in a multi-party setting, it allows two parties using only public authenticated communication to establish a secret session key which can be used to encrypt messages. But if the session key is compromised, the confidentiality of encrypted messages is typically compromised as well. Without quantum mechanics, key establishment can only be done under the assumption that some computational problem is hard. Since digital communication can be easily eavesdropped and recorded, it is important to consider the secrecy of information anticipating future algorithmic and computational discoveries which could break the secrecy of past keys, violating the secrecy of the confidential channel. Quantum key distribution (QKD) can be used generate secret keys that are secure against any future algorithmic or computational improvements. QKD protocols still require authentication of classical communication, however, which is most easily achieved using computationally secure digital signature schemes. It is generally considered folklore that QKD when used with computationally secure authentication is still secure against an unbounded adversary, provided the adversary did not break the authentication during the run of the protocol. We describe a security model for quantum key distribution based on traditional classical authenticated key exchange (AKE) security models. Using our model, we characterize the long-term security of the BB84 QKD protocol with computationally secure authentication against an eventually unbounded adversary. By basing our model on traditional AKE models, we can more readily compare the relative merits of various forms of QKD and existing classical AKE protocols. This comparison illustrates in which types of adversarial environments different quantum and classical key agreement protocols can be secure.

Recent block ciphers have been designed to be resistant against differential cryptanalysis. Nevertheless it has been shown that such resistance claims may not be as tight as wished due to recent advances in this field. One of the main improvements to differential cryptanalysis is the use of many differentials to reduce the data complexity. In this paper we propose a general model for understanding multiple differential cryptanalysis and propose new attacks based on tools used in multidimensional linear cryptanalysis (namely \LLR and $\CHI$ statistical tests). Practical cases are considered on a reduced version of the cipher PRESENT to evaluate different approaches for selecting and combining the differentials considered. We also consider the tightness of the theoretical estimates corresponding to these attacks.

We argue that it is unnatural and undesirable to use the non-uniform model of complexity for practice-oriented security reductions in cryptography.

Many papers deal with the problem of constructing an efficient masking scheme for existing block ciphers. We take the reverse approach: that is, given a proven masking scheme (Rivain and Prouff, CHES 2010) we design a block cipher that fits well the masking constraints. The difficulty of implementing efficient masking for a block cipher comes mainly from the S-boxes. Therefore the choice of an adequate S-box is the first and most critical step of our work. The S-box we selected is non-bijective; we discuss the resulting design and security problems. A complete design of the cipher is given, as well as some implementation results.

In many applications, where encrypted traffic flows from an open (public) domain to a protected (private) domain, there exists a gateway that bridges the two domains and faithfully forwards the incoming traffic to the receiver. We observe that indistinguishability against (adaptive) chosen-ciphertext attacks (IND-CCA), which is a mandatory goal in face of active attacks in a public domain, can be essentially relaxed to indistinguishability against chosen-plaintext attacks (IND-CPA) for ciphertexts once they pass the gateway that acts as an IND-CCA/CPA filter by first checking the validity of an incoming IND-CCA ciphertext, then transforming it (if valid) into an IND-CPA ciphertext, and forwarding the latter to the recipient in the private domain. ``Non-trivial filtering'' can result in reduced decryption costs on the receivers' side. We identify a class of encryption schemes with \emph{publicly verifiable ciphertexts} that admit generic constructions of (non-trivial) IND-CCA/CPA filters. These schemes are characterized by existence of public algorithms that can distinguish between valid and invalid ciphertexts. To this end, we formally define (non-trivial) public verifiability of ciphertexts for general encryption schemes, key encapsulation mechanisms, and hybrid encryption schemes, encompassing public-key, identity-based, and tag-based encryption flavours. We further analyze the security impact of public verifiability and discuss generic transformations and concrete constructions that enjoy this property.

Anonymous authentication schemes such as group signatures and anonymous credentials are important privacy-protecting tools in electronic communications. The only currently known scheme based on assumptions that resist quantum attacks is the group signature scheme by Gordon et al. (ASIACRYPT 2010). We present a generalization of group signatures called *anonymous attribute tokens* where users are issued attribute-containing credentials that they can use to anonymously sign messages and generate tokens revealing only a subset of their attributes. We present two lattice-based constructions of this new primitive, one with and one without opening capabilities for the group manager. The latter construction directly yields as a special case the first lattice-based group signature scheme offering full anonymity (in the random-oracle model), as opposed to the practically less relevant notion of chosen-plaintext anonymity offered by the scheme of Gordon et al. We also extend our scheme to protect users from framing attacks by the group manager, where the latter creates tokens or signatures in the name of honest users. Our constructions involve new lattice-based tools for aggregating signatures and verifiable CCA2-secure encryption.

``Lapin'' is a new RFID authentication protocol proposed at FSE 2012. ``Ring-LPN'' (Ring-Learning-Parity-with-Noise) is a new computational problem proposed in the same paper; there is a proof relating the security of Lapin to the difficulty of Ring-LPN. This paper presents an attack against Ring-LPN-512 and Lapin-512.The attack is not practical but nevertheless violates specific security claims in the FSE 2012 paper.

A $(k,l)$ hash-function combiner for property $P$ is a construction that, given access to $l$ hash functions, yields a single cryptographic hash function which has property $P$ as long as at least $k$ out of the $l$ hash functions have that property. Hash function combiners are used to hedge against the failure of one or more of the individual components. One example of the application of hash function combiners are the previous versions of the TLS and SSL protocols \cite{RFC:6101,RFC:5246}. The concatenation combiner which simply concatenates the outputs of all hash functions is an example of a robust combiner for collision resistance. However, its output length is, naturally, significantly longer than each individual hash-function output, while the security bounds are not necessarily stronger than that of the strongest input hash-function. In 2006 Boneh and Boyen asked whether a robust black-box combiner for collision resistance can exist that has an output length which is significantly less than that of the concatenation combiner \cite{C:BonBoy06}. Regrettably, this question has since been answered in the negative for fully black-box constructions (where hash function and adversary access is being treated as black-box), that is, combiners (in this setting) for collision resistance roughly need at least the length of the concatenation combiner to be robust \cite{C:BonBoy06,C:CRSTVW07,EC:Pietrzak07,C:Pietrzak08}. In this paper we examine weaker notions of collision resistance, namely: \emph{second pre-image resistance} and \emph{target collision resistance} \cite{FSE:RogShr04} and \emph{pre-image resistance}. As a generic brute-force attack against any of these would take roughly $2^n$ queries to an $n$-bit hash function, in contrast to only $2^{n/2}$ queries it would take to break collision resistance (due to the birthday bound), this might indicate that combiners for weaker notions of collision resistance can exist which have a significantly shorter output than the concatenation combiner (which is, naturally, also robust for these properties). Regrettably, this is not the case.

The use of field programmable devices in security-critical applications is growing in popularity; in part, this can be attributed to their potential for balancing metrics such as efficiency and algorithm agility. However, in common with non-programmable alternatives, physical attack techniques such as fault and power analysis are a threat. We investigate a family of next-generation field programmable devices, specifically those based on the concept of time sharing,within this context: our results support the premise that extra, inherent flexibility in such devices can offer a range of possibilities for low-overhead, generic countermeasures against physical attack.

Collision resistant one-way hashing schemes are the basic building blocks of almost all crypto-systems. Use of graph-structured data models are on the rise -- in graph databases, representation of biological and healthcare data as well as in modeling systems for representing system topologies. Therefore, the problem of hashing graphs with respect to crypto-systems needs to be studied and addressed. The traditional Merkle Hash technique cannot be applied as it is because graphs are more complex data structures than trees. In this paper, we make the following contributions: (1) we define the formal security model of hashing schemes for graphs, (2) we define the formal security model of leakage-free hashing schemes for graphs, (3) we describe a hashing scheme for hashing directed and undirected graphs that uses Merkle hash technique, (4) and a hashing scheme that uses structural information instead of Merkle hash technique, (5) we define leakage-free hashing schemes for graphs. Our constructions use graph traversal techniques and are highly efficient with respect to updates to graphs: they require as little as two (O(1)) hash values to be updated to refresh the hash of the graph, while the Merkle Hash Technique and Search DAG schemes for trees and DAGs respectively require as many as O(|V|) and O(|V|+|E|).

SipHash is a family of pseudorandom functions optimized for short inputs. Target applications include network traffic authentication and hash-table lookups protected against hash-flooding denial-of-service attacks. SipHash is simpler than MACs based on universal hashing, and faster on short inputs. Compared to dedicated designs for hash-table lookup, SipHash has well-defined security goals and competitive performance. For example, SipHash processes a 16-byte input with a fresh key in 140 cycles on an AMD FX-8150 processor, which is much faster than state-of-the-art MACs. We propose that hash tables switch to SipHash as a hash function.

Order-preserving encryption (OPE) preserves the order of data in their ciphertexts and, hence, allows range search on the encrypted data without needing to decrypt them. Security analysis of OPE schemes is very important because OPE is not a perfect encryption algorithm (the ciphertexts leak the ordering information of the plaintexts). Most of the existing security analysis for the OPE schemes are informal: they are either based on author-defined attacks or experiments. The authors in \cite{Bol09} initiate the cryptographic study of the OPE scheme. They define the security notion POPF-CCA to qualify the security of OPE. In POPF-CCA, the ``ideal" OPE object is defined where the encryption function is uniformly randomly selected from all order-preserving functions (generally the ``ideal" OPE object is not computationally feasible), and a (constructed) ``real" OPE scheme is secure under POPF-CCA if it is computationally indistinguishable from the ideal object. In other words, although the ``ideal" OPE object is not computationally feasible, it is used as the security goal, and a (constructed) ``real" OPE scheme is secure if it is as secure as the ``ideal" OPE object. Such approach conceives the assumption (but not clearly stated and proved) that the ``ideal" OPE object is the most secure OPE. But the correctness of the assumption is an easily ignored problem. In this paper, we investigate the security of the OPE in more depth. We first give example to show that the ``ideal" OPE object may not always be the most secure OPE. It indicates that we need to use the ``ideal" encryption object more cautiously in the security analysis of OPE. Additionally we extend the concept of OPE to generalized OPE (GOPE). Unlike OPE, the ciphertexts of GOPE may not be numbers, but GOPE still enables the comparisons on the encrypted data without needing to decrypt them. We present two GOPEs in polynomial-sized and superpolynomial-sized domains that satisfy stronger notions of security than that of the ideal OPE object, respectively.

The $32$-bit MAC of Grain-128a is a linear combination of the first 64 and then the alternative keystream bits. In this paper we describe a successful differential fault attack on Grain-128a, in which we recover the secret key by observing the correct and faulty MACs of certain chosen messages. The attack works due to certain properties of the Boolean functions and corresponding choices of the taps from the LFSR. We present methods to identify the fault locations and then construct set of linear equations to obtain the contents of the LFSR and the NFSR. Our attack requires less than $2^{11}$ fault injections and invocations of less than $2^{12}$ MAC generation routines.

The notion of oblivious transfer with hidden access control policies (HACOT) was recently proposed by Camenisch et al.~(Public-Key Cryptography~2011). This primitive allows a user to anonymously query a database where each record is protected by a hidden attribute-based access control policy. At each query, the user either learns the value of a single record if the attributes in his key satisfy the policy, or the mere fact that his attributes do not satisfy the policy. The database, even when colluding with the key issuer, learns nothing about the identity of the user, the index or the access policy of the record, or whether access was granted or denied. At the same time, the database can keep an eye on the overall access frequency to prevent the data from being ``crawled''. In this paper, we present a new HACOT scheme which is more efficient and offers more expressive policies than the scheme presented by Camenisch et al. We construct our HACOT protocol based on a hidden ciphertext-policy attribute-based encryption (HP-ABE) scheme by Nishide et al.: users are issued HACOT decryption keys based on HP-ABE attributes and HACOT records are encrypted under HP-ABE policies. However, as we will see, this simple approach does not work and we need to extend the Nishide et al.\ scheme as follows. First, we add protocols that allows users to verify that the public key of the issuer and ciphertexts are correctly formed. Second, we reserve one attribute and give the corresponding decryption key only to the database. Thereby users can no longer decrypt records by themselves but require the help of the database. Third, we provide a joint decryption protocol between the user and the database, so that the database does not learn which ciphertext is decrypted. The latter will also allow one to optionally add revocation of the users' access. We prove our construction secure by a reduction to the security of Nishide et al.'s scheme, the Symmetric External Diffie-Hellman (SXDH) and Simultaneous Flexible Pairing (SFP) assumptions.

This paper proposes a new fault attack technique on the LED block cipher using a single fault injection by combining algebraic side-channel attack (ASCA) and differential fault attack (DFA). We name it as algebraic differential fault attack (ADFA). Firstly, a boolean equation set is constructed for LED using algebraic techniques. Then, the fault differences of the S-Box inputs in the last round of LED are deduced by DFA and represented using algebraic equations by the multiple deductions-based ASCA (MDASCA) technique proposed in COSADE 2012. Finally, the key is recovered by solving the equation set with the CryptoMiniSat solver. We show that, as to ADFA on LED under the single nibble-based fault model, the 64-bit key can be recovered within one minute on a common PC with a success rate of 79\%, which is more efficient than previous work. We modify the CryptoMiniSat solver to count and output multiple solutions for the key, and conduct ADFA to calculate the reduced key search space for DFA. The key search space of LED is reduced to $2^6 \sim 2^{17}$, which is different from previous work. We also successfully extend ADFA on LED to other fault models using a single fault injection, such as byte based fault model and nibble based diagonal fault model, where traditional DFAs are difficult to work. The results show that ADFA is an efficient and generic fault analysis technique which significantly improves DFA.

In this paper, we present an Edwards model for elliptic curves which is defined over any perfect field and in particular over finite fields. This Edwards model is birationally equivalent to the well known Edwards model over non-binary fields and is ordinary over binary fields. For this, we use theta functions of level four to obtain an intermediate model that we call a level $4$ theta model. This model enables us to obtain the new Edwards model with a complete and unified. Over binary fields, we present an efficient arithmetic of these curves. We also provide competitive differential addition formulas over any perfect field.

There are many useful cryptographic schemes, such as ID-based encryption, short signature, keyword searchable encryption, attribute-based encryption, functional encryption, that use a bilinear pairing. It is important to estimate the security of such pairing-based cryptosystems in cryptography. The most essential number-theoretic problem in pairing-based cryptosystems is the discrete logarithm problem (DLP) because pairing-based cryptosystems are no longer secure once the underlining DLP is broken. One efficient bilinear pairing is the $\eta_T$ pairing defined over a supersingular elliptic curve $E$ on the finite field $GF(3^n)$ for a positive integer $n$. The embedding degree of the $\eta_T$ pairing is $6$; thus, we can reduce the DLP over $E$ on $GF(3^n)$ to that over the finite field $GF(3^{6n})$. In this paper, for breaking the $\eta_T$ pairing over $GF(3^n)$, we discuss solving the DLP over $GF(3^{6n})$ by using the function field sieve (FFS), which is the asymptotically fastest algorithm for solving a DLP over finite fields of small characteristics. We chose the extension degree $n=97$ because it has been intensively used in benchmarking tests for the implementation of the $\eta_T$ pairing, and the order (923-bit) of $GF(3^{6\cdot 97})$ is substantially larger than the previous world record (676-bit) of solving the DLP by using the FFS. We implemented the FFS for the medium prime case (JL06-FFS), and propose several improvements of the FFS, for example, the lattice sieve for JL06-FFS and the filtering adjusted to the Galois action. Finally, we succeeded in solving the DLP over $GF(3^{6\cdot 97})$. The entire computational time of our improved FFS requires about 148.2 days using 252 CPU cores. Our computational results contribute to the secure use of pairing-based cryptosystems with the $\eta_T$ pairing.

In this paper, we present a new class of knapsack type PKC referred to as K(II)$\Sigma\Pi$PKC. In K(II)$\Sigma\Pi$PKC, Bob randomly constructs a very small subset of Alice's set of public key whose order is very large, under the condition that the coding rate $\rho$ satisfies $0.01 < \rho < 0.5$. In K(II)$\Sigma\Pi$PKC, no secret sequence such as super-increasing sequence or shifted-odd sequence but the sequence whose component is constructed by a product of the same number of many prime numbers of the same size, is used. We show that K(II)$\Sigma\Pi$PKC is secure against the attacks such as LLL algorithm, Shamir's attack etc. , because a subset of Alice's public keys is chosen entirely in a probabilistic manner at the sending end. We also show that K(II)$\Sigma\Pi$PKC can be used as a member of the class of common key cryptosystems because the list of the subset randomly chosen by Bob can be used as a common key between Bob and Alice, provided that the conditions given in this paper are strictly observed, without notifying Alice of his secret key through a particular secret channel.

Introduced in 1996 and greatly developed over the last few years, Lattice-based cryptography oers a whole set of primitives with nice features, including provable security and asymptotic efficiency. Going from \asymptotic" to \real-world" efficiency seems important as the set of available primitives increases in size and functionality. In this present paper, we explore the improvements that can be obtained through the use of an FPGA architecture for implementing an ideal-lattice based cryptographic primitive. We chose to target two of the simplest, yet powerful and useful, lattice-based primitives, namely the SWIFFT and SWIFFTX primitives. Apart from being simple, those are also of central use for future primitives as Lyubashevsky's lattice-based signatures. We present a high-throughput FPGA architecture for the SWIFFT and SWIFFTX primitives. One of the main features of this implementation is an efficient implementation of a variant of the Fast Fourier Transform of order 64 on Z257. On a Virtex-5 LX110T FPGA, we are able to hash 0.6GB/s, which shows a ca. 16x speedup compared to SIMD implementations of the literature. We feel that this demonstrates the revelance of FPGA as a target architecture for the implementation of ideal-lattice based primitives.

An electric vehicle is a promising and futuristic automobile propelled by electric motor(s), using electrical energy stored in batteries or another energy storage device. Due to the need of battery recharging, the cars will be required to visit recharging infrastructure very frequently. This may disclose the users' private information, such as their location, which may expose users' privacy. In this paper, we provide mechanisms to enhance location privacy of electric vehicles at the right time, by proposing an anonymous payment system with privacy protection support. Our technique further allows traceability in the case where the cars are stolen.

In this paper, we propose an efficient, standard model, semi-generic transformation of selective-secure (Hierarchical) Identity-Based Encryption schemes into fully secure ones. The main step is a procedure that uses admissible hash functions (whose existence is implied by collision-resistant hash functions) to convert any selective-secure \emph{wildcarded} identity-based encryption (WIBE) scheme into a fully secure (H)IBE scheme. Since building a selective-secure WIBE, especially with a selective-secure HIBE already in hand, is usually much less involved than directly building a fully secure HIBE, this transform already significantly simplifies the latter task. This black-box transformation easily extends to schemes secure in the Continual Memory Leakage (CML) model of Brakerski et al. (FOCS 2010), which allows us obtain a new fully secure IBE in that model. We furthermore show that if a selective-secure HIBE scheme satisfies a particular security notion, then it can be generically transformed into a selective-secure WIBE. We demonstrate that several current schemes already fit this new definition, while some others that do not obviously satisfy it can still be easily modified into a selective-secure WIBE.

We propose a new, widely applicable model for analyzing knowledge-based (epistemic) and strategic properties of cryptographic protocols. We prove that the corresponding model checking problem with respect to an expressive epistemic strategic logic is decidable. As corollaries, we obtain decidability of complex security properties including coercion-resistance of voting protocols, accountability of protocols using a trusted third party, and abuse-freeness of contract signing protocols.

In this paper we present two known plaintext attacks on a stream cipher which was developed by John Nash in the early 1950's but whose design was declassified by the NSA only in 2012. The main attack reduces the claimed security of the scheme from $\left(\left(n-1\right)!\cdot2^{n}\right)^{2}$ to $O\left(n^{2}\log^{3}n\right)$, where $n$ is a security parameter. This attack succeeds with high probability for randomly chosen keys even when the only thing we know about the plaintext is that a small fraction of isolated plaintext bits are slightly biased, but always fails for a certain well defined class of keys which is exponentially large but a negligibly small fraction of all the possible keys. To show that it would not suffice to simply restrict the choice of keys to this class, we develop a different attack which works best for the subset of keys which are hardest to find by the first attack. This attack reduces the security of the scheme from $2^{O\left(n\right)}$ to $O\left(n^{2}\right)$. Both attacks were verified with actual simulations, finding cryptographic keys which are thousands of bits long in just a few minutes on a single PC.

The general principle for algebraic attack for multi-output stream ciphers was proposed by Courtois [6]. Furthermore, Armknecht, and Krause gave a definition of algebraic immunity for multi-output Boolean functions in [2], and investigated some construction methods of multi-output Boolean functions with maximal algebraic immunity. In this note, several new characterizations of algebraic immunity for multi-output Boolean functions are given, and some related invariants and their relations are also investigated. Some examples are given to illustrate the usefulness of these results.

Broadcast Encryption (BE) is an important technique for digital rights management (DRM). Two key parameters of a BE scheme are the average size of the transmission overhead and the size of the secret information to be stored by the users. The most important BE scheme till date is the subset difference (SD) scheme proposed by Naor, Naor and Lotspiech in 2001 which achieves a good balance of these two parameters. A year later, Halevy and Shamir proposed a variant of the SD scheme called the layered SD (LSD) scheme which allowed to reduce the size of user storage at the cost of increasing the transmission overhead. Since then, there has been no further study of other possible trade-offs between transmission overhead and user storage that can be obtained from the SD scheme. In this work, we introduce several simple ideas to obtain new layering strategies with different trade-offs between user storage and transmission overhead. At one end, we introduce the notion of storage minimal layering, show that the Halevy-Shamir layering does not achieve minimal storage and describe a dynamic programming algorithm to compute layering strategies for which user storage is guaranteed to be the minimum possible. This results in user storage being 18\% to 24\% lower than that required by Halevy-Shamir layering schemes. At the other end, we consider the constrained minimization problem and show how to obtain BE schemes whose transmission overhead is not much more than that of the SD scheme but, whose user storage is still significantly lower than that of the SD scheme. The original SD and the LSD algorithms are defined only when the number of users is a power of two. In an earlier work, we have shown how to handle arbitrary number of users in the SD scheme. Here this is extended to the LSD scheme. Finally, we obtain an $O(r\log^2 n)$ time algorithm to compute the average transmission overhead in any layering based SD scheme with $n$ users out of which $r$ are revoked.

In this paper, secure two-party protocols are provided in order to securely generate a random $k$-bit RSA modulus $n$ keeping its factorization secret. We first show that most existing two-party protocols based on Boneh's test are not correct: an RSA modulus can be output in the malicious case. Recently, Hazay et al. proposed the first proven secure protocol against any polynomial active adversary. However, their protocol is very costly: several hours are required to output a 1024-bit RSA modulus on a standard platform. In this paper, we propose an other approach consisting of post-processing efficient existing Boneh's based protocols. The running time of this post-processing can be neglected with respect to the running time of the whole protocol.

In this paper, we construct a class of vectorial Boolean functions over $\mathbb{F}_{2^{n}}$ with high algebraic immunity based on the decomposition of the multiplicative group of $\mathbb{F}_{2^n}$. By viewing $\mathbb{F}_{2^{n}}$ as $G_1G_2\bigcup \{0\} $ (where $G_1$ and $G_2$ are subgroups of $\mathbb{F}_{2^{n}}^{*},~(\#G_1,\#G_2)=1$ and $\#G_1\times \#G_2=2^{2k}-1$), we give a generalized description for constructing vectorial Boolean functions with high algebraic immunity. Moreover, when $n$ is even, we provide two special classes of vectorial Boolean functions with high(sometimes optimal) algebraic immunity, one is hyper-bent, and the other is of balancedness and optimal algebraic degree .

Widespread adoption of RFID technology in all aspects of our life mainly depends on the fixing the privacy concerns of this technology's customers. Using a tagged object should not lead to existence of the tracing possibility. This concern is a challenging issue that has motivated the researchers to propose several authentication protocols to fix the traceability problem in RFID systems and also provide other security requirements. In this paper, we analyze the security of three authentication protocols which have recently been proposed by Morshed et al. Our security analysis clearly highlights important security pitfalls in these protocols which leads to their vulnerability against traceability. The complexity of the proposed attacks are only several runs of the protocols while the adversary's advantages to trace the tagged object are maximal.

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.