A function $F$ from \textbf{F}$_{p^n}$ to itself is planar if for any $a\in$\textbf{F}$_{p^n}^*$ the function $F(x+a)-F(x)$ is a permutation. CCZ-equivalence is the most general known equivalence relation of functions preserving planar property. This paper considers two possible extensions of CCZ-equivalence for functions over fields of odd characteristics, one proposed by Coulter and Henderson and the other by Budaghyan and Carlet, and we show that they in fact coincide with CCZ-equivalence. We prove that two finite commutative presemifields of odd order are isotopic if and only if they are strongly isotopic. This result implies that two isotopic commutative presemifields always define CCZ-equivalent planar functions (this was unknown for the general case). Further we prove that, for any odd prime $p$ and any positive integers $n$ and $m$, the indicators of the graphs of functions $F$ and $F'$ from \textbf{F}$_{p^n}$ to \textbf{F}$_{p^m}$ are CCZ-equivalent if and only if $F$ and $F'$ are CCZ-equivalent. We also prove that, for any odd prime $p$, CCZ-equivalence of functions from \textbf{F}$_{p^n}$ to \textbf{F}$_{p^m}$, is strictly more general than EA-equivalence when $n\ge3$ and $m$ is greater or equal to the smallest positive divisor of $n$ different from 1.

In PKC 2010, Matsuda, Nishimaki and Tanaka proposed a bidirectional proxy re-encryption (PRE) scheme without bilinear maps, and claimed that their scheme is chosen-ciphertext secure in the standard model. However, by giving a concrete attack, in this paper we indicate that their PRE scheme fails to achieve the chosen-ciphertext security. The purpose of this paper is to clarify the fact that, it is still an open problem to come up with a chosen-ciphertext secure PRE scheme without bilinear maps in the standard model.

Multiparty computation protocols have been known for more than twenty years now, but due to their lack of efficiency their use is still limited in real-world applications: the goal of this paper is the design of efficient two and multi party computation protocols aimed to fill the gap between theory and practice. We propose a new protocol to securely evaluate reactive arithmetic circuits, that offers security against an active adversary in the universally composable security framework. Instead of the ``do-and-compile'' approach (where the parties use zero-knowledge proofs to show that they are following the protocol) our key ingredient is an efficient version of the ``cut-and-choose'' technique, that allow us to achieve active security for just a (small) constant amount of work more than for passive security.

In 2001, Gottesman and Chuang proposed a quantum signature scheme. Unlike classical signature schemes, the public keys in the scheme can only be used once. The authors claim that the scheme is somewhat cumbersome but it serves as a good model and suggests novel research directions for the field of quantum cryptography. In this note, we remark that the Gottesman-Chuang quantum signature scheme is so commonplace and cumbersome that it can not suggest the potential for quantum public key cryptography. The authors ignore an ultimate fact, namely, the cost to grantee the authenticity of a user's public key is expensive in the scenario of Public Key Infrastructure. It entails that a user's public key should be repeatedly usable in the life duration.

We propose a new protocol providing cryptographically secure authentication to unaided humans against passive adversaries. We also propose a new generic passive attack on human identification protocols. The attack is an application of Coppersmith's baby-step giant-step algorithm on human identification protcols. Under this attack, the achievable security of some of the best candidates for human identification protocols in the literature is further reduced. We show that our protocol preserves similar usability while achieves better security than these protocols. A comprehensive security analysis is provided which suggests parameters guaranteeing desired levels of security.

In this paper, a thorough bottom-up optimization process (field, point and scalar arithmetic) is used to speed up the computation of elliptic curve point multiplication and report new speed records on modern x86-64 based processors. Our different implementations include elliptic curves using Jacobian coordinates, extended Twisted Edwards coordinates and the recently proposed Galbraith-Lin-Scott (GLS) method. Compared to state-of-the-art implementations on identical platforms the proposed techniques provide up to 30% speed improvements. Additionally, compared to the best previous published results on similar platforms improvements up to 31% are observed. This research is crucial for advancing high speed cryptography on new emerging processor architectures.

The security of a password authentication scheme using smart cards proposed by Khan et al. is analyzed. Four kinds of attacks are presented in different scenarios. The analyses show that the scheme is insecure for practical application.

We analyze how fast we can solve general systems of multivariate equations of various low degrees over \GF{2}; this is a well known hard problem which is important both in itself and as part of many types of algebraic cryptanalysis. Compared to the standard exhaustive-search technique, our improved approach is more efficient both asymptotically and practically. We implemented several optimized versions of our techniques on CPUs and GPUs. Modern graphic cards allows our technique to run more than 10 times faster than the most powerful CPU available. Today, we can solve 48+ quadratic equations in 48 binary variables on a NVIDIA GTX 295 video card (USD 500) in 21 minutes. With this level of performance, solving systems of equations supposed to ensure a security level of 64 bits turns out to be feasible in practice with a modest budget. This is a clear demonstration of the power of GPUs in solving many types of combinatorial and cryptanalytic problems.

Recently, Liu proposed two authenticated multiple key exchange protocols using pairings, and claimed two protocols featured many security attributes. In this paper, we show that Liu’s protocols are insecure. Both of Liu’s protocols cannot provide perfect forward secrecy.

In this paper we combine the residue number system (RNS) representation and the leak-resistant arithmetic on elliptic curves. These two techniques are relevant for implementation of elliptic curve cryptography on embedded devices.\\ % since they have leak-resistance properties. It is well known that the RNS multiplication is very efficient whereas the reduction step is costly. Hence, we optimize formulae for basic operations arising in leak-resistant arithmetic on elliptic curves (unified addition, Montgomery ladder) in order to minimize the number of modular reductions. We also improve the complexity of the RNS modular reduction step. As a result, we show how to obtain a competitive secured implementation.\\ Finally, %we recall the main advantages of the RNS representation, %especially in hardware and for embedded devices, and we show that, contrary to other approaches, ours takes optimally the advantage of a dedicated parallel architecture.

In this article it's discussed the analytic property of $\zeta(s)$. The popular opinion is denied.

Meloni recently introduced a new type of arithmetic on elliptic curves when adding projective points sharing the same Z-coordinate. This paper presents further co-Z addition formulae (and register allocations) for various point additions on Weierstrass elliptic curves. It explains how the use of conjugate point addition and other implementation tricks allow one to develop efficient scalar multiplication algorithms making use of co-Z arithmetic. Specifically, this paper describes efficient co-Z based versions of Montgomery ladder and Joye’s double-add algorithm. Further, the resulting implementations are protected against a large variety of implementation attacks.

A collective signature scheme aims to solve the problem of signing a message by multiple signers. Recently, Moldovyan and Moldovyan [1] proposed a scheme for collective signatures based on Schnorr signatures. We show some security weaknesses of the scheme.

Impossible differential cryptanalysis is a very popular tool for analyzing the security of modern block ciphers and the core of such attack is based on the existence of impossible differentials. Currently, most methods for finding impossible differentials are based on the miss-in-the-middle technique and they are very ad-hoc. In this paper, we concentrate SPN ciphers whose diffusion layer is defined by a linear transformation $P$. Based on the theory of linear algebra, we propose several criteria on $P$ and its inversion $P^{-1}$ to characterize the existence of $3/4$-round impossible differentials. We further discuss the possibility to extend these methods to analyze $5/6$-round impossible differentials. Using these criteria, impossible differentials for reduced-round Rijndael are found that are consistent with the ones found before. New $4$-round impossible differentials are discovered for block cipher ARIA. And many $4$-round impossible differentials are firstly detected for a kind of SPN cipher that employs a $32\times32$ binary matrix proposed at ICISC 2006 as its diffusion layer. It is concluded that the linear transformation should be carefully designed in order to protect the cipher against impossible differential cryptanalysis.

The security of a password authentication scheme using smart cards proposed by Rhee et al. is analyzed. A kind of impersonation attack is presented. The analyses show that the scheme is insecure for practical application. In order to eliminate the security vulnerability, an efficient countermeasure is proposed.

Cloud computing denotes an architectural shift toward thin clients and conveniently centralized provision of computing resources. Clients’ lack of direct resource control in the cloud prompts concern about the potential for data privacy violations, particularly abuse or leakage of sensitive information by service providers. Cryptography is an oft-touted remedy. Among its most powerful primitives is fully homomorphic encryption (FHE), dubbed by some the field’s “Holy Grail,” and recently realized as a fully functional construct with seeming promise for cloud privacy. We argue that cryptography alone can’t enforce the privacy demanded by common cloud computing services, even with such powerful tools as FHE.We formally define a hierarchy of natural classes of private cloud applications, and show that no cryptographic protocol can implement those classes where data is shared among clients. We posit that users of cloud services will also need to rely on other forms of privacy enforcement, such as tamperproof hardware, distributed computing, and complex trust ecosystems.

SIMD is one of the second round candidates of the SHA-3 competition hosted by NIST. In this paper, we present some results on the compression function of SIMD 1.1 (the tweaked version) using the modular difference method. For SIMD-256, We give a free-start near collision attack on the compression function reduced to 20 steps with complexity $2^{-107}$. And for SIMD-512, we give a free-start near collision attack on the 24-step compression function with complexity $2^{208}$. Furthermore, we give a distinguisher attack on the full compression function of SIMD-512 with complexity $2^{398}$. Our attacks are also applicable for the final compression function of SIMD.

Canetti and Herzog (TCC'06) show how to efficiently perform fully automated, computationally sound security analysis of key exchange protocols with an unbounded number of sessions. A key tool in their analysis is {\em composability}, which allows deducing security of the multi-session case from the security of a single session. However, their framework only captures protocols that use public key encryption as the only cryptographic primitive, and only handles static corruptions. We extend the [CH'06] modeling in two ways. First, we handle also protocols that use digital signatures and Diffie-Hellman exchange. Second, we handle also forward secrecy under fully adaptive party corruptions. This allows us to automatically analyze systems that use an unbounded number of sessions of realistic key exchange protocols such as the ISO 9798-3 or TLS protocol. A central tool in our treatment is a new abstract modeling of plain Diffie-Hellman key exchange. Specifically, we show that plain Diffie-Hellman securely realizes an idealized version of Key Encapsulation.

Since the introduction of the concept of provable security, there has been the steady search for suitable problems that can be used as a foundation for cryptographic schemes. Indeed, identifying such problems is a challenging task. First, it should be open and investigated for a long time to make its hardness assumption plausible. Second, it should be easy to construct hard problem instances. Third, it should allow to build cryptographic applications on top of them. Not surprisingly, only a few problems are known today that satisfy all conditions, e.g., factorization, discrete logarithm, and lattice problems. In this work, we introduce another candidate: the Inhomogeneous Simultaneous Approximation Problem (ISAP), an old problem from the field of analytic number theory that dates back to the 19th century. Although the Simultaneous Approximation Problem (SAP) is already known in cryptography, it has mainly been considered in its homogeneous instantiation for attacking schemes. We take a look at the hardness and applicability of ISAP, i.e., the inhomogeneous variant, for designing schemes. More precisely, we define a decisional problem related to ISAP, called DISAP, and show that it is NP-complete. With respect to its hardness, we review existing approaches for computing a solution and give suggestions for the efficient generation of hard instances. Regarding the applicability, we describe as a proof of concept a bit commitment scheme where the hiding property is directly reducible to DISAP. An implementation confirms its usability in principle (e.g., size of one commitment is slightly more than 6 KB and execution time is in the milliseconds).

We prove beyond-birthday-bound security for the well-known types of generalized Feistel networks, including: (1) unbalanced Feistel networks, where the $n$-bit to $m$-bit round functions may have $n\ne m$; (2) alternating Feistel networks, where the round functions alternate between contracting and expanding; (3) type-1, type-2, and type-3 Feistel networks, where $n$-bit to $n$-bit round functions are used to encipher $kn$-bit strings for some $k\ge2$; and (4) numeric variants of any of the above, where one enciphers numbers in some given range rather than strings of some given size. Using a unified analytic framework we show that, in any of these settings, for any $\varepsilon>0$, with enough rounds, the subject scheme can tolerate CCA attacks of up to $q\sim N^{1-\varepsilon}$ adversarial queries, where $N$ is the size of the round functions' domain (the size of the larger domain for alternating Feistel). This is asymptotically optimal. Prior analyses for generalized Feistel networks established security to only $q\sim N^{0.5}$ adversarial queries.

In this paper, we propose the minimal joint Hamming weight conversion for any binary expansions of $d$ integers. With redundant representations, we may represent a number by many expansions, and the minimal joint Hamming weight conversion is the algorithm to select the expansion that has the least joint Hamming weight. As the computation time of the cryptosystem strongly depends on the joint Hamming weight, the conversion can make the cryptosystem faster. Most of existing conversions are limited to some specific representations, and are difficult to apply to other representations. On the other hand, our conversion is applicable to any binary expansions. The proposed can explore the minimal average weights in a class of representation that have not been found. One of the most interesting results is that, for the expansion of integer pairs when the digit set is $\{0, \pm 1, \pm 3\}$, we show that the minimal average joint Hamming weight is $0.3575$. This improves the upper bound value, $0.3616$, proposed by Dahmen, Okeya, and Takagi.

We describe two improvements to Gentry's fully homomorphic scheme based on ideal lattices and its analysis: we provide a more aggressive analysis of one of the hardness assumptions (the one related to the Sparse Subset Sum Problem) and we introduce a probabilistic decryption algorithm that can be implemented with an algebraic circuit of low multiplicative degree. Combined together, these improvements lead to a faster fully homomorphic scheme, with a~$\softO(\lambda^{3.5})$ bit complexity per elementary binary add/mult gate, where~$\lambda$ is the security parameter. These improvements also apply to the fully homomorphic schemes of Smart and Vercauteren [PKC'2010] and van Dijk et al.\ [Eurocrypt'2010].

The notion of indifferentiability, introduced by Maurer et al., is an important criterion for the security of hash functions. Concretely, it ensures that a hash function has no structural design flaws and thus guarantees security against generic attacks up to the exhibited bounds. In this work we prove the indifferentiability of Grøstl, a second round SHA-3 hash function candidate. Grøstl combines characteristics of the wide-pipe and chop-Merkle-Damgård iterations and uses two distinct permutations P and Q internally. Under the assumption that P and Q are random l-bit permutations, where l is the iterated state size of Grøstl, we prove that the advantage of a distinguisher to differentiate Grøstl from a random oracle is upper bounded by O((Kq)^4/2^l), where the distinguisher makes at most q queries of length at most K blocks. For the specific Grøstl parameters, this result implies that Grøstl behaves like a random oracle up to q=O(2^{n/2}) queries, where n is the output size. Furthermore, we show that the output transformation of Grøstl, as well as `Grøstail' (the composition of the final compression function and the output transformation), are clearly differentiable from a random oracle. This renders out indifferentiability proofs which rely on the idealness of a final state transformation.

Side-channel based collision attacks are a mostly disregarded alternative to DPA for analyzing unprotected implementations. The advent of strong countermeasures, such as masking, has made further research in collision attacks seemingly in vain. In this work, we show that the principles of collision attacks can be adapted to efficiently break some masked hardware implementation of the AES which still have first-order leakage. The proposed attack breaks an AES implementation based on the corrected version of the masked S-box of Canright and Batina presented at ACNS 2008 which is supposed to be resistant against firstorder attacks. It requires only six times the number of traces necessary for breaking a comparable unprotected implementation. At the same time, the presented attack has minimal requirements on the abilities and knowledge of an adversary. The attack requires no detailed knowledge about the design, nor does it require a training phase.

Many efficient attacks have appeared in recent years, which have led to serious blow for the traditional multivariate public key cryptosystems. For example, the signature scheme SFLASH was broken by Dubois et al. at CRYPTO'07, and the Square signature (or encryption) scheme by Billet et al. at ASIACRYPTO'09. Most multivariate schemes known so far are insecure, except maybe the sigature schemes UOV and HFEv-. Following these new developments, it seems that the general design principle of multivariate schemes has been seriously questioned, and there is a rather pressing desire to find new trapdoor construction or mathematical tools and ideal. In this paper, we introduce the hash authentication techniques and combine with the traditional MQ-trapdoors to propose a novel hash-based multivariate public key cryptosystems. The resulting scheme, called EMC (Extended Multivariate Cryptosystem), can also be seen as a novel hash-based cryptosystems like Merkle tree signature. And it offers the double security protection for signing or encrypting. By the our analysis, we can construct the secure and efficient not only signature scheme but also encryption scheme by using the EMC scheme combined some modification methods summarized by Wolf. And thus we present two new schems: EMC signature scheme (with the Minus method ``-") and EMC encryption scheme (with the Plus method ``+"). In addition, we also propose a reduced scheme of the EMC signature scheme (a light-weight signature scheme). Precise complexity estimates for these schemes are provided, but their security proofs in the random oracle model are still an open problem.

Many real-world protocols, such as SSL/TLS, SSH, IPsec, IEEE 802.11i, DNSSEC, and Kerberos, derive new keys from other keys. To be able to analyze such protocols in a composable way, in this paper we extend an ideal functionality for symmetric and public-key encryption proposed in previous work by a mechanism for key derivation. We also equip this functionality with message authentication codes (MACs) and ideal nonce generation. We show that the resulting ideal functionality can be realized based on standard cryptographic assumptions and constructions, hence, providing a solid foundation for faithful, composable cryptographic analysis of real-world security protocols. Based on this new functionality, we identify sufficient criteria for protocols to provide universally composable key exchange and secure channels. Since these criteria are based on the new ideal functionality, checking the criteria requires merely information-theoretic or even only syntactical arguments, rather than involved reduction arguments. As a case study, we use our method to analyze two central protocols of the IEEE 802.11i standard, namely the 4-Way Handshake Protocol and the CCM Protocol, proving composable security properties. As to the best of our knowledge, this constitutes the first rigorous cryptographic analysis of these protocols.

We give a new method for generating genus 2 curves over a finite field with a given number of points on the Jacobian of the curve. We define two new invariants for genus 2 curves as values of modular functions on the Hilbert moduli space and show how to compute them. We relate them to the usual three Igusa invariants on the Siegel moduli space and give an algorithm to construct curves using these new invariants. Our approach simplifies the complex analytic method for computing genus 2 curves for cryptography and reduces the amount of computation required.

\begin{abstract} In this paper we will study 2 security results ``above the birthday bound'' related to secret key cryptographic problems.\\ 1. The classical problem of the security of 4, 5, 6 rounds balanced Random Feistel Schemes.\\ 2. The problem of the security of unbalanced Feistel Schemes with contracting functions from $2n$ bits to $n$ bits. This problem was studied by Naor and Reingold~\cite{NR99} and by~\cite{YPL} with a proof of security up to the birthday bound.\\ These two problems are included here in the same paper since their analysis is closely related, as we will see. In problem 1 we will obtain security result very near the information bound (in $O(\frac {2^n}{n})$) with improved proofs and stronger explicit security bounds than previously known. In problem 2 we will cross the birthday bound of Naor and Reingold. For some of our proofs we will use~\cite{A2} submitted to Crypto 2010. \end{abstract}

In this paper, we present an efficient FPGA implementation of the SHA-3 hash function candidate Shabal. Targeted at the recent Xilinx Virtex-5 FPGA family, our design achieves a relatively high throughput of 2 Gbit/s at a cost of only 153 slices, yielding a throughput-vs.-area ratio of 13.4 Mbit/s per slice. Our work can also be ported to Xilinx Spartan-3 FPGAs, on which it supports a throughput of 800 Mbit/s for only 499 slices, or equivalently 1.6 Mbit/s per slice. According to the SHA-3 Zoo website, this work is among the smallest reported FPGA implementations of SHA-3 candidates, and ranks first in terms of throughput per area.

The weakness of an exquisite authentication scheme based on smart cards and passwords proposed by Liao et al. [C. H. Liao, H. C. Chen, and C. T. Wang, An Exquisite Mutual Authentication Scheme with Key Agreement Using Smart Card, Informatica, Vol. 33, No. 2, 2009, 125-132.] is analyzed. Five kinds of weakness are presented in different scenarios. The analyses show that Liao et al.’s scheme is insecure for practical application.

We examine several variants of the Diffie-Hellman and Discrete Log problems that are connected to the security of cryptographic protocols. We discuss the reductions that are known between them and the challenges in trying to assess the true level of difficulty of these problems, particularly if they are interactive or have complicated input.

We propose the first protocol for securely computing the inner product modulo an integer $m$ between two distrustful parties based on a trusted initializer, i.e. a trusted party that interacts with the players solely during a setup phase. We obtain a very simple protocol with universally composable security. As an application of our protocol, we obtain a solution for securely computing linear equations.

Motivated by the lattice basis delegation technique due to [8], we propose an adaptively secure identity-based broadcast encryption(IBBE) scheme based on the hard worst-case lattice problems. Our construction can be generalized to obtain a hierarchical IBBE (HIBBE) scheme easily. To the best of the authors' knowledge, our construction and its variants constitute the first adaptively secure IBBE schemes from lattices, which are believed secure in the post-quantum environment.

\begin{abstract} In this paper we will first study two closely related problems:\\ 1. The problem of distinguishing $f(x\Vert 0)\oplus f(x \Vert 1)$ where $f$ is a random permutation on $n$ bits. This problem was first studied by Bellare and Implagliazzo in~\cite{BI}.\\ 2. The so-called ``Theorem $P_i \oplus P_j$'' of Patarin (cf~\cite{P05}). Then, we will see many variants and generalizations of this ``Theorem $P_i \oplus P_j$'' useful in Cryptography. In fact all these results can be seen as part of the theory that analyzes the number of solutions of systems of linear equalities and linear non equalities in finite groups. We have nicknamed these analysis ``Mirror Theory'' due to the multiples induction properties that we have in it. \end{abstract}

In this paper we study the lower bounds of second-order nonlinearities of bent functions constructed by modifying certain cubic Maiorana-McFarland type bent functions.

In this paper, we present a preimage attack on reduced versions of Keccak hash functions. We use our recently developed toolkit CryptLogVer for generating CNF (conjunctive normal form) which is passed to the SAT solver PrecoSAT. We found preimages for some reduced versions of the function and showed that full Keccak function is secure against the presented attack.

Protocols for secure two-party computation enable a pair of parties to compute a function of their inputs while preserving security properties such as privacy, correctness and independence of inputs. Recently, a number of protocols have been proposed for the efficient construction of two-party computation secure in the presence of malicious adversaries (where security is proven under the standard simulation-based ideal/real model paradigm for defining security). In this paper, we present a protocol for this task that follows the methodology of using cut-and-choose to boost Yao's protocol to be secure in the presence of malicious adversaries. Relying on specific assumptions (DDH), we construct a protocol that is significantly more efficient and far simpler than the protocol of Lindell and Pinkas (Eurocrypt 2007) that follows the same methodology. We provide an exact, concrete analysis of the efficiency of our scheme and demonstrate that (at least for not very small circuits) our protocol is more efficient than any other known today.

Visual Cryptography is a secret sharing scheme that uses the human visual system to perform computations. This paper presents a recursive hiding scheme for 3 out of 5 secret sharing. The idea used is to hide smaller secrets in the shares of a larger secret without an expansion in the size of the latter.

The operations addition modulo 2^n and exclusive-or have recently been combined to obtain an efficient mechanism for nonlinearity in block cipher design. In this paper, we show that ciphers using this approach may be approximated by pseudo-linear expressions relating groups of contiguous bits of the round key, round input, and round output. The bias of an approximation can be large enough for known plaintext attacks. We demonstrate an application of this concept to a reduced-round version of the Threefish block cipher, a component of the Skein entry in the secure hash function competition.

Consider the following problem: a sender S and a receiver R are part of an unreliable, connected, distributed network. The distrust in the network is modelled by an entity called adversary, who has unbounded computing power and who can corrupt some of the nodes of the network (excluding S and R)in a variety of ways. S wishes to send to R a message m that consists of \ell elements, where \ell \geq 1, selected uniformly from a finite field F. The challenge is to design a protocol, such that after interacting with S as per the protocol, R should output m without any error (perfect reliability). Moreover, this hold irrespective of the disruptive actions done by the adversary. This problem is called reliable message transmission or RMT in short. The problem of secure message transmission or SMT in short requires an additional constraint that the adversary should not get any information about the message what so ever in information theoretic sense (perfect secrecy). Security against an adversary with infinite computing power is also known as non-cryptographic or information theoretic or Shannon security and this is the strongest notion of security. Notice that since the adversary has unbounded computing power, we cannot solve RMT and SMT problem by using classical cryptographic primitives such as public key cryptography, digital signatures, authentication schemes, etc as the security of all these primitives holds good only against an adversary having polynomially bounded computing power. RMT and SMT problem can be studied in various network models and adversarial settings. We may use the following parameters to describe different settings/models for studying RMT/SMT: \begin{enumerate} \item Type of Underlying Network --- Undirected Graph, Directed Graph, Hypergraph. \item Type of Communication --- Synchronous, Asynchronous. \item Adversary capacity --- Threshold Static, Threshold Mobile, Non-threshold Static, Non-threshold Mobile. \item Type of Faults --- Fail-stop, Passive, Byzantine, Mixed. \end{enumerate} Irrespective of the settings in which RMT/SMT is studied, the following issues are common: \begin{enumerate} \item Possibility: What are the necessary and sufficient structural conditions to be satisfied by the underlying network for the existence of any RMT/SMT protocol, tolerating a given type of adversary? \item Feasibility: Once the existence of a RMT/SMT protocol in a network is ascertained, the next natural question is, does there exist an efficient protocol on the given network? \item Optimality: Given a message of specific length, what is the minimum communication complexity (lower bound) needed by any RMT/SMT protocol to transmit the message and how to design a polynomial time RMT/SMT protocol whose total communication complexity matches the lower bound on the communication complexity (optimal protocol)? \end{enumerate} In this dissertation, we look into the above issues in several network models and adversarial settings. This thesis reports several new/improved/efficient/optimal solutions, gives affirmative/negative answers to several significant open problems and last but not the least, provides first solutions to several newly formulated problems.

This dissertation deals with three most important as well as fundamental problems in secure distributed computing, namely Verifiable Secret Sharing (VSS), Byzantine Agreement (BA) and Multiparty Computation (MPC). VSS is a two phase protocol (Sharing and Reconstruction) carried out among $n$ parties in the presence of a centralized adversary who can corrupt up to $t$ parties. Informally, the goal of the VSS protocol is to share a secret $s$, among the $n$ parties during the sharing phase in a way that would later allow for a unique reconstruction of this secret in the reconstruction phase, while preserving the secrecy of $s$ until the reconstruction phase. VSS is used as a key tool in MPC, BA and many other secure distributed computing problems. It can take many different forms, depending on the underlying network (synchronous or asynchronous), the nature (passive or active) and computing power (bounded or unbounded) of the adversary, type of security (cryptographic or information theoretic) etc. We study VSS in information theoretic setting over both synchronous as well as asynchronous network, considering an active unbounded powerful adversary. Our main contributions for VSS are: \begin{itemize} \item In synchronous network, we carry out in-depth investigation on the round complexity of VSS by allowing a probability of error in computation and show that existing lower bounds for the round complexity of error-free VSS can be circumvented by introducing a negligible probability of error. \item We study the communication and round efficiency of VSS in synchronous network and present a robust VSS protocol that is simultaneously communication efficient and round efficient. In addition, our protocol is the best known communication and round efficient protocol in the literature. \item In asynchronous network, we study the communication complexity of VSS and propose a number of VSS protocols. Our protocols are highly communication efficient and show significant improvement over the existing protocols in terms of communication complexity. \end{itemize} The next problem that we deal with is Byzantine Agreement (BA). BA is considered as one of the most fundamental primitives for fault tolerant distributed computing and cryptographic protocols. BA among a set of $n$ parties, each having a private input value, allows them to reach agreement on a common value even if some of the malicious parties (at most $t$) try to prevent agreement among the parties. Similar to the case of VSS, several models for BA have been proposed during the last three decades, considering various aspects like the underlying network, the nature and computing power of adversary, type of security. One of these models is BA over asynchronous network which is considered to be more realistic network than synchronous in many occasions. Though important, research in BA in asynchronous network has received much less attention in comparison to the BA protocols in synchronous network. Even the existing protocols for asynchronous BA involve high communication complexity and in general are very inefficient in comparison to their synchronous counterparts. We focus on BA in information theoretic setting over asynchronous network tolerating an active adversary having unbounded computing power and mainly work towards the communication efficiency of the problem. Our contributions for BA are as follows: \begin{itemize} \item We propose communication efficient asynchronous BA protocols that show huge improvement over the existing protocols in the same setting. Our protocols for asynchronous BA use our VSS protocols in asynchronous network as their vital building blocks. \item We also construct a communication optimal asynchronous BA protocol for sufficiently long message size. Precisely, our asynchronous BA communicates O(\ell n) bits for \ell bit message, for sufficiently large \ell. \end{itemize} The studies on VSS and BA naturally lead one towards MPC problems. The MPC can model almost any known cryptographic application and uses VSS as well as BA as building blocks. MPC enables a set of $n$ mutually distrusting parties to compute some function of their private inputs, such that the privacy of the inputs of the honest parties is guaranteed (except for what can be derived from the function output) even in the presence of an adversary corrupting up to $t$ of the parties and making them misbehave arbitrarily. Much like VSS and BA, MPC can also be studied in various models. Here, we attempt to solve MPC in information theoretic setting over synchronous as well as asynchronous network, tolerating an active unbounded powerful adversary. As for MPC, our main contributions are: \begin{itemize} \item Using one of our synchronous VSS protocol, we design a synchronous MPC that minimizes the communication and round complexity simultaneously, where existing MPC protocols try to minimize one complexity measure at a time (i.e the existing protocols minimize either communication complexity or round complexity). \item We study the communication complexity of asynchronous MPC protocols and design a number of protocols for the same that show significant gain in communication complexity in comparison to the existing asynchronous MPC protocols. \item We also study a specific instance of MPC problem called Multiparty Set Intersection (MPSI) and provide protocols for the same. \end{itemize} In brief, our work in this thesis has made significant advancement in the state-of-the-art research on VSS, BA and MPC by presenting several inherent lower bounds and efficient/optimal solutions for the problems in terms of their key parameters such as communication complexity and time/round complexity. Thus our work has made a significant contribution to the field of secure distributed computing by carrying out a foundation research on the three most important problems of this field.

In STOC'05, von Ahn, Hopper and Langford introduced the notion of covert computation. In covert computation, a party runs a secure computation protocol over a covert (or steganographic) channel without knowing if the other parties are participating as well or not. At the end of the protocol, if all parties participated in the protocol and if the function output is "favorable" to all parties, then the output is revealed (along with the fact that everyone participated). All covert computation protocols known so far require a large polynomial number of rounds. In this work, we first study the question of the round complexity of covert computation and obtain the following results: 1) There does not exist a constant round covert computation protocol with respect to black box simulation even for the case of two parties. (In comparison, such protocols are known even for the multi-party case if there is no covertness requirement.) 2) By relying on the two slot non-black-box simulation technique of Pass (STOC'04) and techniques from cryptography in NC^0 (Applebaum et al, FOCS'04), we obtain a construction of a constant round covert multi-party computation protocol. Put together, the above adds one more example to the growing list of tasks for which non-black-box simulation techniques (introduced in the work of Barak in FOCS'01) are necessary. Finally, we study the problem of covert multi-party computation in the setting where the parties only have point to point (covert) communication channels. We observe that our covert computation protocol for the broadcast channel inherits, from the protocol of Pass, the property of secure composition in the bounded concurrent setting. Then, as an application of this protocol, somewhat surprisingly we show the existence of covert multi-party computation with point to point channels (assuming that the number of parties is a constant).

In recent years, there has been a major effort to design cryptographic schemes that remain secure even if part of the secret key is leaked. This is due to a recent proliferation of side channel attacks which, through various physical means, can recover part of the secret key. We explore the possibility of achieving security even with continual leakage, i.e., even if some information is leaked each time the key is used. We show how to securely update a secret key while information is leaked: We construct schemes that remain secure even if an attacker, {\em at each time period}, can probe the entire memory (containing a secret key) and ``leak'' up to a $(1-o(1))$ fraction of the secret key. The attacker may also probe the memory during the updates, and leak $O(\log k)$ bits, where $k$ is the security parameter (relying on subexponential hardness allows $k^\epsilon$ bits of leakage during each update process). All of the above is achieved without restricting the model as is done in previous works (e.g. by assuming that ``only computation leaks information'' [Micali-Reyzin, TCC04]). Specifically, under the decisional linear assumption on bilinear groups (which allows for a leakage rate of $(1/2-o(1))$) or the symmetric external Diffie-Hellman assumption (which allows for a leakage rate of $(1-o(1))$), we achieve the above for public key encryption, identity-based encryption, and signature schemes. Prior to this work, it was not known how to construct public-key encryption schemes even in the more restricted model of [MR]. The main contributions of this work are (1) showing how to securely update a secret key while information is leaked (in the more general model) and (2) giving a public key encryption (and IBE) schemes that are resilient to continual leakage.

We propose an adaptively secure broadcast encryption scheme with short ciphertexts. That is the size of the broadcast encryption message is fixed, regardless of the size of the broadcast group. In our proposed scheme, members can join and leave the group without requiring any change to public parameters of the system or private keys of existing members. Our construction has a twofold improvement over best previously known broadcast encryption schemes. First, we propose a scheme that immediately yields adaptive security in the CCA model without any (sub-linear) increase in the size of ciphertexts or use of a random oracle. Secondly, the security model in our system includes decryption queries for any member, even including the members in the challenge set. This a more secure model, as it is closer to the adversary in real world.

The power of side-channel leakage attacks on cryptographic implementations is evident. Today's practical defenses are typically attack-specific countermeasures against certain classes of side-channel attacks. The demand for a more general solution has given rise to the recent theoretical research that aims to build provably leakage-resilient cryptography. This direction is, however, very new and still largely lacks practitioners' evaluation with regard to both efficiency and practical security. A recent approach, One-Time Programs (OTPs), proposes using Yao's Garbled Circuit (GC) and very simple tamper-proof hardware to securely implement oblivious transfer, to guarantee leakage resilience. Our main contributions are (i) a generic architecture for using GC/OTP modularly, and (ii) hardware implementation and efficiency analysis of GC/OTP evaluation. We implemented two FPGA-based prototypes: a system-on-a-programmable-chip with access to hardware crypto accelerator (suitable for smartcards and future smartphones), and a stand-alone hardware implementation (suitable for ASIC design). We chose AES as a representative complex function for implementation and measurements. As a result of this work, we are able to understand, evaluate and improve the practicality of employing GC/OTP as a leakage-resistance approach. Last, but not least, we believe that our work contributes to bringing together the results of both theoretical and practical communities.

In this work, we study position-based cryptography in the quantum setting. The aim is to use the geographical position of a party as its only credential. On the negative side, we show that if adversaries are allowed to share an arbitrarily large entangled quantum state, no secure position-verification is possible at all. We show a distributed protocol for computing any unitary operation on a state shared between the different users, using local operations and one round of classical communication. Using this surprising result, we break any position-verification scheme of a very general form. On the positive side, we show that if adversaries do not share any entangled quantum state but can compute arbitrary quantum operations, secure position-verification is achievable. Jointly, these results suggest the interesting question whether secure position-verification is possible in case of a bounded amount of entanglement. Our positive result can be interpreted as resolving this question in the simplest case, where the bound is set to zero. In models where secure positioning is achievable, it has a number of interesting applications. For example, it enables secure communication over an insecure channel without having any pre-shared key, with the guarantee that only a party at a specific location can learn the content of the conversation. More generally, we show that in settings where secure position-verification is achievable, other position-based cryptographic schemes are possible as well, such as secure position-based authentication and position-based key agreement.

In this paper, we redefine a cryptographic notion called Online/Offline Identity-Based Signcryption. It is an ``online/offline'' version of identity-based signcryption, where most of the computations are carried out offline while the online part does not require any heavy computations such as pairings or multiplications on elliptic curve. It is particularly suitable for power-constrained devices such as smart cards. We give a concrete implementation of online/offline identity-based signcryption, which is very efficient and flexible. Unlike all the previous schemes in the literature, our scheme does not require the knowledge of receiver's information (either public key or identity) in the offline stage. The receiver's identity and the message to be signcrypted are only needed in the online stage. This feature provides a great flexibility to our scheme and makes it practical to use in real-world applications. To our knowledge, our scheme is the first one in the literature to provide this kind of feature. We prove that the proposed scheme meets strong security requirements in the random oracle model, assuming the Strong Diffie-Hellman (SDH) and Bilinear Diffie-Hellman Inversion (BDHI) are computationally hard.

This paper provides three improvements over previous work on analyzing CubeHash, based on its classes of symmetric states: (1) We present a detailed analysis of the hierarchy of symmetry classes. (2) We point out some flaws in previously claimed attacks which tried to exploit the symmetry classes. (3) We present and analyze new multicollision and preimage attacks. For the default parameter setting of CubeHash, namely for a message block size of b = 32, the new attacks are slightly faster than 2^384 operations. If one increases the size of a message block by a single byte to b = 33, our multicollision and preimage attacks become much faster – they only require about 2^256 operations. This demonstrates how sensitive the security of CubeHash is, depending on minor changes of the tunable security parameter b.

This paper discusses a novel direction for multicore cryptographic software, namely the use of multicore to protect a design against side-channel attacks. We present a technique which is based on the principle of dual-rail pre-charge, but which can be completely implemented in software. The resulting protected software is called a Virtual Secure Circuit (VSC). Similar to the dual-rail pre-charge technique, a VSC executes as two complementary programs on two identical processor cores. Our key contributions include (1) the analysis of the security properties of a VSC, (2) the construction of a VSC AES prototype on a dual-PowerPC architecture, (3) the demonstration of VSC's protection effectiveness with real side-channel attack experiments. The attack results showed that the VSC protected AES needs 80 times more measurements than the unprotected AES to find the first correct key byte. Even one million measurements were not sufficient to fully break VSC protected AES, while unprotected AES was broken using only 40000 measurements. We conclude that VSC can provide a similar side-channel resistance as WDDL, the dedicated hardware equivalent of dual-rail pre-charge. However, in contrast to WDDL, VSC is a software technique, and therefore it is flexible.

In 1994, P. Shor showed that quantum computers will be able to break cryptosystems based on integer factorization and on the discrete logarithm, e.g. RSA or ECC. Code-based crytosystems are promising alternatives to public key schemes based on these problems, and they are believed to be secure against quantum computer attacks. In this paper, we solve the problem of selecting optimal parameters for the McEliece cryptosystem that provide security until a given year and give detailed recommendations. Our analysis is based on the lower bound complexity estimates by Sendrier and Finiasz, and the security requirements model proposed by Lenstra and Verheul.

We present a brief report on the factorization of RSA-180, currently smallest unfactored RSA number. We show that the numbers of similar size could be factored in a reasonable time at home using open source factoring software running on a few Intel Core i7 PCs.

In this paper,we proposed a efficient and laconic mode for iterative hash functions and tried to fix the flaws of the Merkle-Damgaard construction completely and certainly tried to prevent varieties of those generic attacks ,such as Multicollisions Attack,Second Preimage Attack and Herding Attack.The struc- ture of this new mode is different from HAIFA or any other proposal,it contains a new method “Locking Abutting Blocks”(LAB)with checksum ,it makes a larger size of connotative chaining value without requirements of intricate computing and larger memory and it allows for an online computation in one pass with a fixed memory independently .It’s also easy to avoid the generic attacks (presented by Praveen Gauravaram and John Kelsey) which apply on the hash functions with linear-XOR/additive checksum.

In this paper we study order-preserving encryption (OPE), a primitive in the database community for allowing efficient range queries on ecrypted data. OPE was suggested by Agrawal et al [1], and was throughly studied by Boldyreva et al [2]. In this paper we present a practical OPE scheme, which is a key-controlled algorithm, based on simple computation. A primary analysis shows that our algorithm is secure enough

Many authenticated multiple key exchange protocols were published in recent years. In 2008, Lee et al. presented an authenticated multiple key exchange protocol based on bilinear pairings. However, Vo et al. demonstrated an impersonation attack on the protocol , and it failed to provide authenticity and perfect forward secrecy as they had claimed. Later, Vo et al. proposed their enhancement protocol conforming which conforms to all desirable security properties. But, Vo's protocol required any party had held the public key each other, which required a large amount of storage. In this paper, we propose two new authenticated multiple key exchange protocols based on Lee's protocol, and makes them immune against Vo et al.'s attacks.

Bit-decomposition, which is proposed by Damgård \emph{et al.}, is a powerful tool for multi-party computation (MPC). Given a sharing of secret $x$, it allows the parties to compute the sharings of the bits of $x$ in constant rounds. With the help of bit-decomposition, constant-rounds protocols for various MPC problems can be constructed. However, bit-decomposition is relatively expensive, so constructing protocols for MPC problems without relying on bit-decomposition is a meaningful work. In multi-party computation, it remains an open problem whether the \emph{modulo reduction problem} can be solved in constant rounds without bit-decomposition. In this paper, we propose a protocol for (public) modulo reduction without relying on bit-decomposition. This protocol achieves constant round complexity and linear communication complexity. Moreover, we show a generalized bit-decomposition protocol which can, in constant rounds, convert the sharing of secret $x$ into the sharings of the digits of $x$, along with the sharings of the bits of every digit. The digits can be base-\emph{m} for any $m\geq2$. Obviously, when \emph{m} is a power of 2, this generalized protocol is just the original bit-decomposition protocol.

Proxy re-encryption (PRE), introduced by Blaze, Bleumer and Strauss in Eurocrypt'98, allows a semi-trusted proxy to convert a ciphertext originally intended for Alice into an encryption of the same message intended for Bob. PRE has recently drawn great interest, and many interesting PRE schemes have been proposed. However, up to now, it is still an important question to come up with a chosen-ciphertext secure unidirectional PRE in the adaptive corruption model. To address this problem, we propose a new unidirectional PRE scheme, and prove its chosen-ciphertext security in the adaptive corruption model without random oracles. Compared with the best known unidirectional PRE scheme proposed by Libert and Vergnaud in PKC'08, our schemes enjoys the advantages of both higher efficiency and stronger security.

In spite of the central role of key derivation functions (KDF) in applied cryptography, there has been little formal work addressing the design and analysis of general multi-purpose KDFs. In practice, most KDFs (including those widely standardized) follow ad-hoc approaches that treat cryptographic hash functions as perfectly random functions. In this paper we close some gaps between theory and practice by contributing to the study and engineering of KDFs in several ways. We provide detailed rationale for the design of KDFs based on the extract-then-expand approach; we present the first general and rigorous definition of KDFs and their security which we base on the notion of computational extractors; we specify a concrete fully practical KDF based on the HMAC construction; and we provide an analysis of this construction based on the extraction and pseudorandom properties of HMAC. The resultant KDF design can support a large variety of KDF applications under suitable assumptions on the underlying hash function; particular attention and effort is devoted to minimizing these assumptions as much as possible for each usage scenario. Beyond the theoretical interest in modeling KDFs, this work is intended to address two important and timely needs of cryptographic applications: (i) providing a single hash-based KDF design that can be standardized for use in multiple and diverse applications, and (ii) providing a conservative, yet efficient, design that exercises much care in the way it utilizes a cryptographic hash function. (The HMAC-based scheme presented here, named HKDF, is being standardized by the IETF.)

In this paper, we suggest a generalization of Coppersmith's method for finding integer roots of a multivariate polynomial. Our generalization allows finding integer solutions of a system of $k$ multivariate polynomial equations. We then apply our method to the so-called implicit factoring problem, which constitutes the main contribution of this paper. The problem is as follows: let $N_1 = p_1 q_1$ and $N_2 = p_2 q_2$ be two RSA moduli of same bit-size, where $q_1, q_2$ are $\alpha$-bit primes. We are given the \emph{implicit} information that $p_1$ and $p_2$ share $t$ most significant bits. We present a novel and rigorous lattice-based method that leads to the factorization of $N_1$ and $N_2$ in polynomial time as soon as $t \ge 2 \alpha + 3$. Subsequently, we heuristically generalize the method to $k$ RSA moduli $N_i = p_i q_i$ where the $p_i$'s all share $t$ most significant bits (MSBs) and obtain an improved bound on $t$ that converges to $t \ge \alpha + 3.55\ldots$ as $k$ tends to infinity. This paper extends the work of May and Ritzenhofen in \cite{DBLP:conf/pkc/MayR09}, where similar results were obtained when the $p_i$'s share least significant bits (LSBs). In \cite{sarkar2009further}, Sarkar and Maitra describe an alternative but heuristic method for only two RSA moduli, when the $p_i$'s share LSBs and/or MSBs, or bits in the middle. In the case of shared MSBs or bits in the middle and two RSA moduli, they get better experimental results in some cases, but we use much lower (at least 23 times lower) lattice dimensions. Our results rely on the following surprisingly simple algebraic relation in which the shared MSBs of p_1$ and $p_2$ cancel out: $q_1 N_2 - q_2 N_1 = q_1 q_2 (p_2 - p_1)$. This relation allows us to build a lattice whose shortest vector yields the factorization of the $N_i$'s.

This work analyzes the statistical properties of the SHA-3 candidate cryptographic hash algorithms CubeHash and Skein to try to find nonrandom behavior. Cube tests were used to probe each algorithm's internal polynomial structure for a large number of choices of the polynomial input variables. The cube test data were calculated on a 40-core hybrid SMP cluster parallel computer. The cube test data were subjected to three statistical tests: balance, independence, and off-by-one. Although isolated statistical test failures were observed, the balance and off-by-one tests did not find nonrandom behavior overall in either CubeHash or Skein. However, the independence test did find nonrandom behavior overall in both CubeHash and Skein.

Recent iterated ciphers have been designed to be resistant to differential cryptanalysis. This implies that cryptanalysts have to deal with differentials having so small probabilities that, for a fixed key, the whole codebook may not be sufficient to detect it. The question is then, do these theoretically computed small probabilities have any sense? We propose here a deep study of differential and differential trail probabilities supported by experimental results obtained on a reduced version of PRESENT.

The National Institute of Standards and Technology (NIST) has started a competition for a new secure hash standard. To make a significant comparison between the submitted candidates, third party implementations of all proposed hash functions are needed. This is one of the reasons why the SHA-3 candidate Gr\{o}stl has been chosen for a FPGA-based implementation. Mainly our work is motivated by actual and future developments of the automotive market (e.g. car-2-car communication systems), which will increase the necessity for a suitable cryptographic infrastructure in modern vehicles (cf. AUTOSAR project) even further. One core component of such an infrastructure is a secure cryptographic hash function, which is used for a lot of applications like challenge-response authentication systems or digital signature schemes. Another motivation to evaluate Gr\{o}stl is its resemblance to AES. The automotive market demands, like any mass market, low budget and therefore compact implementations, hence our evaluation of Gr\{o}stl focuses on area optimizations. It is shown that, while Gr\{o}stl is inherently quite large compared to AES, it is still possible to implement the Gr\{o}stl algorithm on small and low budget FPGAs like the second smallest available Spartan-3, while maintaining a reasonable high throughput.

In this paper we study linear codes for CDMA (Code Division Multiple Access).

In this paper we consider cubic bent functions obtained by Leander and McGuire (J. Comb. Th. Series A, 116 (2009) 960-970) which are concatenations of quadratic Gold functions. A lower bound of second-order nonlinearities of these functions is obtained. This bound is compared with the lower bounds of second-order nonlinearities obtained for functions belonging to some other classes of functions which are recently studied.

In this note we present the first attack with feasible complexity on the 13-round AES-256. The attack runs in the related-subkey scenario with four related keys, in 2^{76} time, data, and memory.

Certificateless cryptography eliminates the need of certificates in the PKI and solves the inherent key escrow problem in the ID-based cryptography. Recently, Du and Wen proposed a short certi¯cateless signature scheme without MapToPoint hash function, and the signature size is short enough with only half of the DSA signature. In this paper, after the detailing the formal of certificateless signature scheme, we show that the Du and Wen's short certificateless signature scheme is insecure which is broken by a type-I adversary who has the ability in replacing users' public keys and accessing to the signing oracles, and it also cannot resist on the universal forgery attack for any third user.

Boolean function in even number of variables is called {\it bent} if it is at the maximal possible Hamming distance from the class of all affine Boolean functions. We have proven that every isometric mapping of the set of all Boolean functions into itself that transforms bent functions into bent functions is a combination of an affine transform of coordinates and an affine shift.

XXTEA, or Corrected Block TEA, is a simple block cipher in Roger Needham and David Wheeler's TEA series of algorithms. We describe a chosen plaintext attack for XXTEA using about $2^{59}$ queries and negligible work.

We introduce a class of hash functions with the property that messages with the same hash are well separated in terms of their Hamming distance. We provide an example of such a function that uses cyclic codes and an elliptic curve group over a finite field. \smallskip A related problem is ensuring that the {\it consecutive distance} between messages with the same hash is as large as possible. We derive bounds on the c.d. separability factor of such hash functions.

Recently, Liu et al. proposed the first certificateless signcryption scheme without random oracles and proved it was semantically secure in the standard model. However, Selvi et al. launched a fatal attack to its confidentiality by replacing users' public keys, thus pointed out this scheme actually doesn't reach the semantic security as claimed. In this paper, we come up with a rescue scheme based on Liu et al.'s original proposal. A Schnorr-based one-time signature is added to each user's public key, which is used to resist Selvi et al.'s attack. In addition, according to the mistake made in Liu et al.'s security proof, we also show that our improvement is really secure in the standard model under the intractability of the decisional bilinear Diffie-Hellman assumption.

We show in this paper how several proposed Physical Unclonable Functions (PUFs) can be broken by numerical modeling attacks. Given a set of challenge-response pairs (CRPs) of a PUF, our attacks construct a computer algorithm which behaves indistinguishably from the original PUF on almost all CRPs. This algorithm can subsequently impersonate the PUF, and can be cloned and distributed arbitrarily. This breaks the security of essentially all applications and protocols that are based on the respective PUF. The PUFs we attacked successfully include standard Arbiter PUFs and Ring Oscillator PUFs of arbitrary sizes, and XOR Arbiter PUFs, Lightweight Secure PUFs, and Feed-Forward Arbiter PUFs of up to a given size and complexity. Our attacks are based upon various machine learning techniques, including Logistic Regression and Evolution Strategies. Our work will be useful to PUF designers and attackers alike.

We consider the \textit{rational secret sharing problem} introduced by Halpern and Teague\cite{ht04}, where players prefer to get the secret rather than not to get the secret and with lower preference, prefer that as few of the other players get the secret. Some positive results have been derived by Kol and Naor\cite{stoc08} by considering that players only prefer to learn. They have proposed an efficient $m$-out-of-$n$ protocol for rational secret sharing without using cryptographic primitives. Their solution considers that players are of two types; one player is the short player and the rest of the players are long players. But their protocol is susceptible to coalitions if the short player colludes with any of the long players. We extend their protocol, and propose a completely collusion free, $\varepsilon$-Nash equilibrium protocol, when $n \geq 2m -1 $, where $n$ is the number of players and $m$ is the number of shares needed to construct the secret.

We consider the concept of rational secret sharing, which was initially introduced by Halpern and Teague \cite{ht04}, where players' preferences are that they prefer to learn the secret than not, and moreover they prefer that as few others learn the secret as possible. This paper is an attempt to introduce a rational secret sharing scheme which defers from previous RSS schemes in that this scheme does not rely on broadcast to send messages but instead uses point to point transmissions. Not only that, but the protocol will not rely on any cryptographic primitives and is coalition resilient except for when the short player colludes with a long player.

While differential behavior of modern ciphers in a single secret key scenario is relatively well understood, and simple techniques for computation of security lower bounds are readily available, the security of modern block ciphers against related-key attacks is still very ad hoc. In this paper we make a first step towards provable security of block ciphers against related-key attacks by presenting an efficient search tool for finding differential characteristics both in the state and in the key (note that due to similarities between block ciphers and hash functions such tool will be useful in analysis of hash functions as well). We use this tool to search for the best possible (in terms of the number of rounds) related-key differential characteristics in AES, byte-Camellia, Khazad, FOX, and Anubis. We show the best related-key differential characteristics for 5, 11, and 14 rounds of AES-128, AES-192, and AES-256 respectively. We use the optimal differential characteristics to design the best related-key and chosen key attacks on AES-128 (7 out of 10 rounds), AES-192 (full 12 rounds), byte-Camellia (full 18 rounds) and Khazad (7 and 8 out of 8 rounds). We also show that ciphers FOX and Anubis have no related-key attacks on more than 4-5 rounds.

We propose a new encryption scheme that supports joint fingerprinting and decryption. The scheme is remarkably resistant to known-plaintext attack and collusion attack (e.g. average attack or other linear combination attack) on keys. Interestingly, the security of our scheme is relied on a lattice problem: Given a collection of random lattice points generated from a short basis of a lattice, find the short basis. The scheme can be used as a traitor-tracing scheme or a buyer-seller watermarking scheme.

Trust is a central concept in public-key cryptography infrastruc- ture and in security in general. We study its initial quantification and its spread patterns. There is empirical evidence that in trust-based reputation model for virtual communities, it pays to restrict the clusters of agents to small sets with high mutual trust. We propose and motivate a mathematical model, where this phenomenon emerges naturally. In our model, we separate trust values from their weights. We motivate this separation using real examples, and show that in this model, trust converges to the extremes, agreeing with and accentuating the observed phenomenon. Specifically, in our model, cliques of agents of maximal mutual trust are formed, and the trust between any two agents that do not maximally trust each other, converges to zero. We offer initial practical relaxations to the model that preserve some of the theoretical flavor.

Trust Based Collaborative Search is an interactive metasearch engine, presenting the user with clusters of results, based not only on the similarity of content, but also on the similarity of the recommending agents. The theory presented here is broad enough to cover search, browsing, recommendations, demographic profiling, and consumer targeting. We use the term search as an example. We developed a novel general trust theory. In this context, as a special case, we equate trust between agents with the similarity between their search-behaviors. The theory suggests that clusters should be close to maximal similarity within a tolerance dictated by the amount of uncertainty about the vectors of probabilities of attributes representing queries, pages and agents. In addition, we give a new theoretical analysis of clustering tolerances, enabling more judicial decisions about optimal tolerances. Specifically, we show that tolerances should at least be divided by a constant>1 as we descend from one layer in the hierarchical clustering to the next. We also show a promising connection between collaborative search and cryptography: A query plays the role of a cryptogram, the search engine is the cryptanalyst, and the user's intention is the cleartext. Shannon's unicity distance is the length of the search. It is needed to quantify the clustering-tolerance.

We are interested in the integrity of the query results from an outsourced database service provider. Alice passes a set $\set{D}$ of $d$-dimensional points, together with some authentication tag $\set{T}$, to an untrusted service provider Bob. Later, Alice issues some query over $\set{D}$ to Bob, and Bob should produce a query result and a proof based on $\set{D}$ and $\set{T}$. Alice wants to verify the integrity of the query result with the help of the proof, using only the private key. Xu J.~\emph{et al.}~\cite{maia-full} proposed an authentication scheme to solve this problem for multidimensional aggregate range query, including {\SUM, \COUNT, \MIN, \MAX} and {\MEDIAN}, and multidimensional range selection query, with $O(d^2)$ communication overhead. However, their scheme only applys to static database. This paper extends their method to support dynamic operations on the dataset, including inserting or deleting a point from the dataset. The communication overhead of our scheme is $O(d^2 \log N)$, where $N$ is the number of data points in the dataset.

This paper presents a construction for a class of 1-resilient Boolean functions with optimal algebraic immunity on an even number of variables by dividing them into two correlation classes, i.e. equivalence classes. From which, a nontrivial pair of functions has been found by applying the generating matrix. For $n$ is small (e.g. $n=6$), a part of these functions achieve almost optimal nonlinearity. Apart from their good nonlinearity, the functions reach Siegenthaler's \cite{Siegenthaler} upper bound of algebraic degree. Furthermore, a class of 1-resilient functions on any number $n>2$ of variables with at least sub-optimal algebraic immunity is provided.

With the rapid application of service-oriented technologies, service and data outsourcing has become a practical and useful computing paradigm. Combined use of access control and cryptography was proposed by many researchers to protect information in this outsourcing scenario. However, existing approaches often limit dynamical update of access control policy, or have security weakness in practical use. In this paper, we propose a new solution to realize efficient access control of sensitive data service in outsourcing scenarios by using a new re-encryption execution model. Our solution realizes selective access control, dynamical policy updating, simple key management, and collusion prevention of the outsourcee and customers. We also give some proofs of our implementation.

Following Gennaro, Gentry, and Parno (Cryptology ePrint Archive 2009/547), we use fully homomorphic encryption to design improved schemes for delegating computation. In such schemes, a delegator outsources the computation of a function $F$ on many, dynamically chosen inputs $x_i$ to a worker in such a way that it is infeasible for the worker to make the delegator accept a result other than $F(x_i)$. The "online stage" of the Gennaro et al. scheme is very efficient: the parties exchange two messages, the delegator runs in time $poly(log T)$, and the worker runs in time $poly(T)$, where $T$ is the time complexity of $F$. However, the "offline stage" (which depends on the function $F$ but not the inputs to be delegated) is inefficient: the delegator runs in time $poly(T)$ and generates a public key of length $poly(T)$ that needs to be accessed by the worker during the online stage. Our first construction eliminates the large public key from the Gennaro et al. scheme. The delegator still invests $poly(T)$ time in the offline stage, but does not need to communicate or publish anything. Our second construction reduces the work of the delegator in the offline stage to $poly(log T)$ at the price of a 4-message (offline) interaction with a $poly(T)$-time worker (which need not be the same as the workers used in the online stage). Finally, we describe a "pipelined" implementation of the second construction that avoids the need to re-run the offline construction after errors are detected (assuming errors are not too frequent).

The security of a password authentication scheme using smart cards proposed by Khan et al. is analyzed. Four kinds of attacks are presented in different scenarios. The analyses show that the scheme is insecure for practical application.

One round three-party authenticated key exchange protocols are extremely important to secure communications and are now extensively adopted in network communications. These protocols allow users to communicate securely over public networks simply by using easy-to-remember long-term private keys. In 2001, Harn and Lin proposed an authentication key exchange protocol in which two parties generate four shared keys in one round, and three of these keys can provide perfect forward secrecy.This work,which aims to generalize two-party multiple key agreement sets to three-party key agreement sets,presents a three-party multiple key exchange protocol based on bilinear pairing.The proposed protocol does not require server's public key and requires only a single round. Compared with existing protocols, the proposed protocol is more efficient and provide greater security.

A common problem in many markets is that competing firms cannot plan joint business strategies which are socially beneficial, as each firm has its own preferable business strategy which would yield higher profits for it and lower profits for the others. The solution to this problem becomes complex because each firm need not stick to its commitment to follow the pre-designated strategy. Game theory suggests to us a way to enforce this commitment, as when every player chooses his actions according to his observation of the value of a common public signal and, assuming that the others do not deviate, no player is willing to deviate from his recommended strategy. The players do not deviate from their recommended strategy as playing them would yield them a much higher expected pay-off than playing individually. The common public channel can be a trusted external mediator which may send each player his recommended strategy. This mediator can be simulated by a cryptographic protocol, which all the players agree to implement. This problem of suggesting the protocol is known as the \textit{Correlated Element Selection Problem}. The first two-player protocol was proposed by Dodis et. al\cite{dhr00} in Crypto 2000. The extension of the two-player protocol to an $n$-player protocol is highly prone to collusions, as two firms can collude and cheat the rest of the firms. The main contribution of the paper is the first $n$-player collusion free protocol for the \textit{correlated element selection problem} that does not use hardware primitives. We assume that players are honest but curious.

The Canetti--Krawczyk (CK) and extended Canetti--Krawczyk (eCK) security models, are widely used to provide security arguments for key agreement protocols. We discuss security shades in the (e)CK models, and some practical attacks unconsidered in (e)CK--security arguments. We propose a strong security model which encompasses the eCK one. We also propose a new protocol, called Strengthened MQV (SMQV), which in addition to provide the same efficiency as the (H)MQV protocols, is particularly suited for distributed implementations wherein a tamper--proof device is used to store long--lived keys, while session keys are used on an untrusted host machine. The SMQV protocol meets our security definition under the Gap Diffie--Hellman assumption and the Random Oracle model.

Many cryptographic tasks and protocols, such as non-repudiation, contract-signing, voting, auction, identity-based encryption, and certain forms of secure multi-party computation, involve the use of (semi-)trusted parties, such as notaries and authorities. It is crucial that such parties can be held accountable in case they misbehave as this is a strong incentive for such parties to follow the protocol. Unfortunately, there does not exist a general and convincing definition of accountability that would allow to assess the level of accountability a protocol provides. In this paper, we therefore propose a new, widely applicable definition of accountability, with interpretations both in symbolic and computational models. Our definition reveals that accountability is closely related to verifiability, for which we also propose a new definition. We prove that verifiability can be interpreted as a restricted form of accountability. Our findings on verifiability are of independent interest. As a proof of concept, we apply our definitions to the analysis of protocols for three different tasks: contract-signing, voting, and auctions. Our analysis unveils some subtleties and unexpected weaknesses, showing in one case that the protocol is unusable in practice. However, for this protocol we propose a fix to establish a reasonable level of accountability.

Motivated by the problem of establishing a session key among parties based on the possession of certain credentials only, we discuss a notion of attribute-based key establishment. A number of new issues arise in this setting that are not present in the usual settings of group key establishment where unique user identities are assumed to be publicly available. After detailing the security model, we give a two-round solution in the random oracle model. As main technical tool we introduce a notion of attribute-based signcryption, which may be of independent interest. We show that the type of signcryption needed can be realized through the encrypt-then-sign paradigm. Further, we discuss additional guarantees of the proposed protocol, that can be interpreted in terms of deniability and privacy.

Provable data possession is a technique for ensuring the integrity of data in outsourcing storage service. In this paper, we propose a cooperative provable data possession scheme in hybrid clouds to support scalability of service and data migration, in which we consider the existence of multiple cloud service providers to cooperatively store and maintain the clients' data. Our experiments show that the verification of our scheme requires a small, constant amount of overhead, which minimizes communication complexity.

Verifiable encryption allows to encrypt a signature and prove that the plaintext is valid. We introduce a new primitive called commuting signature that extends verifiable encryption in multiple ways: a signer can encrypt both signature and message and prove validity; more importantly, given a ciphertext, a signer can create a verifiably encrypted signature on the encrypted message; thus signing and encrypting commute. We instantiate commuting signatures using the proof system by Groth and Sahai (EUROCRYPT '08) and the automorphic signatures by Fuchsbauer (ePrint report 2009/320). As an application, we give an instantiation of delegatable anonymous credentials, a powerful primitive introduced by Belenkiy et al. (CRYPTO '09). Our instantiation is arguably simpler than theirs and it is the first to provide non-interactive issuing and delegation, which is a standard requirement for non-anonymous credentials. Moreover, the size of our credentials and the cost of verification are less than half of those of the only previous construction, and efficiency of issuing and delegation is increased even more significantly. All our constructions are proved secure in the standard model.

In secret sharing, the exact characterization of ideal access structures is a longstanding open problem. Brickell and Davenport (J. of Cryptology, 1991) proved that ideal access structures are induced by matroids. Subsequently, ideal access structures and access structures induced by matroids have attracted a lot of attention. Due to the difficulty of finding general results, the characterization of ideal access structures has been studied for several particular families of access structures. In all these families, all the matroids that are related to access structures in the family are representable and, then, the matroid-related access structures coincide with the ideal ones. In this paper, we study the characterization of representable matroids. By using the well known connection between ideal secret sharing and matroids and, in particular, the recent results on ideal multipartite access structures and the connection between multipartite matroids and discrete polymatroids, we obtain a characterization of a family of representable multipartite matroids, which implies a sufficient condition for an access structure to be ideal. By using this result and further introducing the reduced discrete polymatroids, we provide a complete characterization of quadripartite representable matroids, which was until now an open problem, and hence, all access structures related to quadripartite representable matroids are the ideal ones. By the way, using our results, we give a new and simple proof that all access structures related to unipartite, bipartite and tripartite matroids coincide with the ideal ones.

We demonstrate the feasibility of throughput-efficient routing in a highly unreliable network. Modeling a network as a graph with vertices representing nodes and edges representing the links between them, we consider two forms of unreliability: unpredictable edge-failures, and deliberate deviation from protocol specifications by corrupt nodes. The first form of unpredictability represents networks with dynamic topology, whose links may be constantly going up and down; while the second form represents malicious insiders attempting to disrupt communication by deliberately disobeying routing rules, by e.g. introducing junk messages or deleting or altering messages. We present a robust routing protocol for end-to-end communication that is simultaneously resilient to both forms of unreliability, achieving provably optimal throughput performance. Our proof proceeds in three steps: 1) We use competitive-analysis to find a lower-bound on the optimal throughput-rate of a routing protocol in networks susceptible to only edge-failures (i.e. networks with no malicious nodes); 2) We prove a matching upper bound by presenting a routing protocol that achieves this throughput rate (again in networks with no malicious nodes); and 3) We modify the protocol to provide additional protection against malicious nodes, and prove the modified protocol performs (asymptotically) as well as the original.

The game-based approach to security proofs in cryptography is a widely-used methodology for writing proofs rigorously. However a unifying language for writing games is still missing. In this paper we show how CSLR, a probabilistic lambda-calculus with a type system that guarantees that computations are probabilistic polynomial time, can be equipped with a notion of game indistinguishability. This allows us to dene cryptographic constructions, eective adversaries, security notions, computational assumptions, game transformations, and game-based security proofs in the unied framework provided by CSLR. Our code for cryptographic constructions is close to implementation in the sense that we do not assume primitive uniform distributions but use a realistic algorithm to approximate them. We illustrate our calculus on cryptographic constructions for public-key encryption and pseudorandom bit generation.

We define the BQS-UC model, a variant of the UC model, that deals with protocols in the bounded quantum storage model. We present a statistically secure commitment protocol in the BQS-UC model that composes concurrently with other protocols and an (a-priori) polynomially-bounded number of instances of itself. Our protocol has an efficient simulator which is important if one wishes to compose our protocol with protocols that are only computationally secure. Combining our result with prior results, we get a statistically BQS-UC secure protocol for general two-party computation without the need for any setup assumption. The round complexity of that protocol is linear in the circuit depth.

NFC is a standardised technology providing short-range RFID communication channels for mobile devices. Peer-to-peer applications for mobile devices are receiving increased interest and in some cases these services are relying on NFC communication. It has been suggested that NFC systems are particularly vulnerable to relay attacks, and that the attacker's proxy devices could even be implemented using off-the-shelf NFC-enabled devices. This paper describes how a relay attack can be implemented against systems using legitimate peer-to-peer NFC communication by developing and installing suitable MIDlets on the attacker's own NFC-enabled mobile phones. The attack does not need to access secure program memory nor use any code signing, and can use publicly available APIs. We go on to discuss how relay attack countermeasures using device location could be used in the mobile environment. These countermeasures could also be applied to prevent relay attacks on contactless applications using `passive' NFC on mobile phones.

In this note we describe a security weakness in pairing-based protocols when the group order is composite and the imbedding degree $k$ is greater than $2$.

The main results of this work are new public-key encryption schemes that, under the quadratic residuosity (QR) assumption (or Paillier's decisional composite residuosity (DCR) assumption), achieve key-dependent message security as well as high resilience to secret key leakage and high resilience to the presence of auxiliary input information. In particular, under what we call the {\it subgroup indistinguishability assumption}, of which the QR and DCR are special cases, we can construct a scheme that has: * Key-dependent message (circular) security. Achieves security even when encrypting affine functions of its own secret key (in fact, w.r.t. affine ``key-cycles'' of predefined length). Our scheme also meets the requirements for extending key-dependent message security to broader classes of functions beyond affine functions using previous techniques of [BGK, ePrint09] or [BHHI, Eurocrypt10]. * Leakage resiliency. Remains secure even if any adversarial low-entropy (efficiently computable) function of the secret key is given to the adversary. A proper selection of parameters allows for a ``leakage rate'' of $(1-o(1))$ of the length of the secret key. * Auxiliary-input security. Remains secure even if any sufficiently \emph{hard to invert} (efficiently computable) function of the secret key is given to the adversary. Our scheme is the first to achieve key-dependent security and auxiliary-input security based on the DCR and QR assumptions. Previous schemes that achieved these properties relied either on the DDH or LWE assumptions. The proposed scheme is also the first to achieve leakage resiliency for leakage rate $(1-o(1))$ of the secret key length, under the QR assumption. We note that leakage resilient schemes under the DCR and the QR assumptions, for the restricted case of composite modulus product of safe primes, were implied by the work of [NS, Crypto09], using hash proof systems. However, under the QR assumption, known constructions of hash proof systems only yield a leakage rate of $o(1)$ of the secret key length.

Protocols for group key exchange are cryptographic algorithms that allow a group of parties communicating over a public network to come up with a common secret key. One of the interesting results of research on group key exchange is the protocol compiler presented by Abdalla et al.~in TCC '07. Abdalla et al.'s compiler shows how one can transform any authenticated 2-party key exchange protocol into an authenticated group key exchange protocol with 2 more rounds of communication. This compiler certainly is elegant in its genericness, symmetricity, simplicity and efficiency. However, the situation completely changes when it comes to security. In this work, we reveal a major security weakness in Abdalla et al.'s compiler and show how to address it. The security weakness uncovered here implies that Abdalla et al.'s proof of security for their compiler is invalid.

We present an efficient implementation of the Orlandi protocol which is the first implementation of a protocol for multiparty computation on arithmetic circuits, which is secure against up to $n-1$ static, active adversaries. An efficient implementation of an actively secure self-trust protocol enables a number of multiparty computation where one or more of the parties only trust himself. Examples includes auctions, negotiations, and online gaming. The efficiency of the implementation is largely obtained through an efficient implementation of the Paillier cryptosystem, also described in this paper.

We present improved cryptanalysis of two second-round SHA-3 candidates: the AES-based hash functions ECHO and GROSTL. We explain methods for building better differential trails for ECHO by increasing the granularity of the truncated differential paths previously considered. In the case of GROSTL, we describe a new technique, the internal differential attack, which shows that when using parallel computations designers should also consider the differential security between the parallel branches. Then, we exploit the recently introduced start-from-the-middle or Super-Sbox attacks, that proved to be very efficient when attacking AES-like permutations, to achieve a very efficient utilization of the available freedom degrees. Finally, we obtain the best known attacks so far for both ECHO and GROSTL. In particular, we are able to mount a distinguishing attack for the full GROSTL-256 compression function.

At Crypto 2005, Coron et al. introduced a formalism to study the presence or absence of structural flaws in iterated hash functions: If one cannot differentiate a hash function using ideal primitives from a random oracle, it is considered structurally sound, while the ability to differentiate it from a random oracle indicates a structural weakness. This model was devised as a tool to see subtle real world weaknesses while in the random oracle world. In this paper we take in a practical point of view. We show, using well known examples like NMAC and the Mix-Compress-Mix (MCM) construction, how we can prove a hash construction secure and insecure at the same time in the indifferentiability setting. These constructions do not differ in their implementation but only on an abstract level. Naturally, this gives rise to the question what to conclude for the implemented hash function. Our results cast doubts about the notion of “indifferentiability from a random oracle” to be a mandatory, practically relevant criterion (as e.g., proposed by Knudsen [16] for the SHA-3 competition) to separate good hash structures from bad ones.

We introduce a ``generalized small inverse problem (GSIP)'' and present an algorithm for solving this problem. GSIP is formulated as finding small solutions of $f(x_0, x_1, \ldots , x_n)=x_0 h(x_1, \ldots , x_n)+C=0 (\bmod \; M)$ for an $n$-variate polynomial $h$, non-zero integers $C$ and $M$. Our algorithm is based on lattice-based Coppersmith technique. We provide a strategy for construction of a lattice basis for solving $f=0$, which are systematically transformed from a lattice basis for solving $h=0$. Then, we derive an upper bound such that the target problem can be solved in polynomial time in $\log M$ in an explicit form. Since GSIPs include some RSA related problems, our algorithm is applicable to them. For example, the small key attacks by Boneh and Durfee are re-found automatically.