Universal composability (or UC security) provides very strong security guarantees for protocols that run in complex real-world environments. In particular, security is guaranteed to hold when the protocol is run concurrently many times with other secure and possibly insecure protocols. Commitment schemes are a basic building block in many cryptographic constructions, and as such universally composable commitments are of great importance in constructing UC-secure protocols. In this paper, we construct highly efficient UC-secure commitments from the standard DDH assumption, in the common reference string model. Our commitment stage is non-interactive, has a common reference string with $O(1)$ group elements, and has complexity of $O(1)$ exponentiations for committing to a group element (to be more exact, the effective cost is that of $23\frac{1}{3}$ exponentiations overall, for both the commit and decommit stages). Our scheme is secure in the presence of static adversaries.

The McEliece cryptosystem is one of the few systems to be considered secure against Quantum attacks. The original scheme is built upon Goppa codes and produces very large keys, hence latest research has focused mainly on trying to reduce the public key size. Previous proposals tried to replace the class of Goppa codes with other families of codes, but this revealed to be an insecure choice. In this paper we introduce a construction based on Generalized Srivastava codes, a large class which include Goppa codes as a special case, that allows relatively short public keys without being vulnerable to known structural attacks.

Differential Fault Analysis (DFA) finds the key of a block cipher using differential information between correct and faulty ciphertexts obtained by inducing faults during the computation of ciphertexts. Among many ciphers AES has been the main target of DFA due to its popularity. DFA of AES has also been diversied into several directions: reducing the required number of faults, applying it to multi-byte fault models, extending to AES-192 and AES-256, or exploiting faults induced at an earlier round. This paper deals with the first three directions together, especially giving weight to reducing the required number of faults. Many previous works show that the required numbers of faults are different although the same fault model is used. This comes from lack of a general method of constructing and solving differential fault equations. Therefore we first present how to generate differential fault equations systematically and reduce the number of candidates of the key with them, which leads us to find the minimum number of faults. Then we extend to multi-byte fault models and AES-192/256.

Ciphers get their strength from the mathematical functions of confusion and diffusion, also known as substitution and permutation. These were the basics of classical cryptography and they are still the basic part of modern ciphers. In block ciphers diffusion is achieved by the use of Maximum Distance Separable (MDS) matrices. In this paper we present some methods for constructing dynamic (and random) MDS matrices.

Recently, a lot of progresses have been made in software implementations of pairings at the 128-bit security level in large characteristic. In this work, we obtain analogous progresses for hardware implementations. For this, we use the RNS representation of numbers which is especially well suited for pairing computation in a hardware context. A FPGA implementation is proposed, based on an adaptation of Guillermin's architecture which computes a pairing in 1.07 ms. It is 2 times faster than all previous hardware implementations (including ASIC and small characteristic implementations) and almost as fast as best software implementations.

In this article, we provide the first independent analysis of the (2nd-round tweaked) 256-bit version of the SHA-3 candidate SHAvite-3. By leveraging recently introduced cryptanalysis tools such as rebound attack or Super-Sbox cryptanalysis, we are able to derive chosen-related-salt distinguishing attacks on the compression function on up to 8 rounds (12 rounds in total) and free-start collisions on up to 7 rounds. In particular, our best results are obtained by carefully controlling the differences in the key schedule of the internal cipher. Most of our results have been implemented and verified experimentally.

In a perfect secret sharing scheme the dealer distributes shares to participants so that qualified subsets can recover the secret, while unqualified subsets have no information on the secret. In an on-line secret sharing scheme the dealer assigns shares in the order the participants show up, knowing only those qualified subsets whose all members she have seen. We often assume that the overall access structure (the set of minimal qualified subsets) is known and only the order of the participants is unknown. On-line secret sharing is a useful primitive when the set of participants grows in time, and redistributing the secret when a new participant shows up is too expensive. In this paper we start the investigation of unconditionally secure on-line secret sharing schemes. The complexity of a secret sharing scheme is the size of the largest share a single participant can receive over the size of the secret. The infimum of this amount in the on-line or off-line setting is the on-line or off-line complexity of the access structure, respectively. For paths on at most five vertices and cycles on at most six vertices the on-line and offline complexities are equal, while for other paths and cycles these values differ. We show that the gap between these values can be arbitrarily large even for graph based access structures. We present a general on-line secret sharing scheme that we call first-fit. Its complexity is the maximal degree of the access structure. We show, however, that this on-line scheme is never optimal: the on-line complexity is always strictly less than the maximal degree. On the other hand, we give examples where the first-fit scheme is almost optimal, namely, the on-line complexity can be arbitrarily close to the maximal degree. The performance ratio is the ratio of the on-line and off-line complexities of the same access structure. We show that for graphs the performance ratio is smaller than the number of vertices, and for an infinite family of graphs the performance ratio is at least constant times the square root of the number of vertices.

Vulnerabilities related to weak passwords are a pressing global economic and security issue. We report a novel, simple, and effective approach to address the weak password problem. Building upon chaotic dynamics, criticality at phase transitions, CAPTCHA recognition, and computational round-off errors we design an algorithm that strengthens security of passwords. The core idea of our method is to split a long and secure password into two components. The first component is memorized by the user. The second component is transformed into a CAPTCHA image and then protected using evolution of a two-dimensional dynamical system close to a phase transition, in such a way that standard brute-force attacks become ineffective. We expect our approach to have wide applications for authentication and encryption technologies.

In this paper we find a lower bound of the second-order nonlinearities of Boolean bent functions of the form $f(x) = Tr_{1}^{n}(\alpha_{1}x^{d_{1}} + \alpha_{2}x^{d_{2}})$,where $d_1$ and $d_2$ are Niho exponents. A lower bound of the second-order nonlinearities of these Boolean functions can also be obtained by using a result proved by Li, Hu and Gao (eprint.iacr.org/2010 /009.pdf). It is demonstrated that for large values of $n$ the lower bound obtained in this paper are better than the lower bound obtained by Li, Hu and Gao.

The availability of a new carry-less multiplication instruction in the latest Intel desktop processors significantly accelerates multiplication in binary fields and hence presents the opportunity for reevaluating algorithms for binary field arithmetic and scalar multiplication over elliptic curves. We describe how to best employ this instruction in field multiplication and the effect on performance of doubling and halving operations. Alternate strategies for implementing inversion and half-trace are examined to restore most of their competitiveness relative to the new multiplier. These improvements in field arithmetic are complemented by a study on serial and parallel approaches for Koblitz and random curves, where parallelization strategies are implemented and compared. The contributions are illustrated with experimental results improving the state-of-the-art performance of halving and doubling-based scalar multiplication on NIST curves at the 112- and 192-bit security levels, and a new speed record for side-channel resistant scalar multiplication in a random curve at the 128-bit security level.

Cloud computing is a style of computing in which dynamically scalable and commonly virtualized resources are provided as a service over the Internet. This paper, first presents a novel Hierarchical Architecture for Cloud Computing (HACC). Then, Identity-Based Encryption (IBE) and Identity-Based Signature (IBS) for HACC are proposed. Finally, an Authentication Protocol for Cloud Computing (APCC) is presented. Performance analysis indicates that APCC is more efficient and lightweight than SSL Authentication Protocol (SAP), especially for the user side. This aligns well with the idea of cloud computing to allow the users with a platform of limited performance to outsource their computational tasks to more powerful servers.

We introduce a pre-computation technique that drastically reduces the online computational complexity of mix-nets based on homomorphic cryptosystems. More precisely, we show that there is a permutation commitment scheme that allows a mix-server to: (1) commit to a permutation and efficiently prove knowledge of doing so correctly in the offline phase, and (2) shuffle its input and give an extremely efficient commitment-consistent proof of a shuffle in the online phase. We prove our result for a general class of shuffle maps that generalize all known types of shuffles, and even allows shuffling ciphertexts of different cryptosystems in parallel.

In this paper, we propose a new approach to identify a tag of a RFID system in constant time while keeping untraceability to the tag. Our scheme does not use any cryptographic primitives. Instead, we use a line in a plane to represent a tag. The points on the line, which are infinite and different each other, can be used as tag identification. We also explore the scalability of the proposed scheme. The result of experiments showed that a tag of the RFID system over 1,000,000 tags, embedded 3000 gates, can store 559 dynamic identity proofs.

We present Selections, a new cryptographic voting protocol that is end-to-end verifiable and suitable for Internet voting. After a one-time in-person registration, voters can cast ballots in an arbitrary number of elections. We say a system provides over-the-shoulder coercion-resistance if a voter can undetectably avoid complying with an adversary that is present during the vote casting process. Our system is the first in the literature to offer this property without the voter having to anticipate coercion and precompute values. Instead, a voter can employ a panic password. We prove that Selections is coercion-resistant against a non-adaptive adversary.

The paper presents several improved side channel cube attacks on PRESENT based on single bit leakage model. Compared with the previous study of Yang et al in CANS 2009 [30], based on the same model of single bit leakage in the 3rd round, we show that: if the PRESENT cipher structure is unknown, for the leakage bit 0, 32-bit key can be recovered within $2^{7.17}$ chosen plaintexts; if the cipher structure is known, for the leakage bit 4,8,12, 48-bit key can be extracted by $2^{11.92}$ chosen plaintexts, which is less than $2^{15}$ in [30]; then, we extend the single bit leakage model to the 4th round, based on the two level “divide and conquer” analysis strategy, we propose a sliding window side channel cube attack on PRESENT, for the leakage bit 0, about $2^{15.14}$ chosen plaintexts can obtain 60-bit key; in order to obtain more key bits, we propose an iterated side channel cube attack on PRESENT, about $2^{8.15}$ chosen plaintexts can obtain extra 12 equivalent key bits, so overall $2^{15.154}$ chosen plaintexts can reduce the PRESENT-80 key searching space to $2^{8}$; finally, we extend the attack to PRESENT-128, about $2^{15.156}$ chosen plaintexts can extract 85 bits key, and reduce the PRESENT-128 key searching space to $2^{43}$. Compared with the previous study of Abdul-Latip et al in ASIACCS 2011 [31] based on the Hamming weight leakage model, which can extract 64-bit key of PRESENT-80/128 by $2^{13}$ chosen plaintexts, our attacks can extract more key bits, and have certain advantages over [31].

The computation of Gröbner bases remains one of the most powerful methods for tackling the Polynomial System Solving (PoSSo) problem. The most efficient known algorithms reduce the Gröbner basis computation to Gaussian eliminations on several matrices. However, several degrees of freedom are available to generate these matrices. It is well known that the particular strategies used can drastically affect the efficiency of the computations. In this work we investigate a recently-proposed strategy, the so-called "Mutant strategy", on which a new family of algorithms is based (MXL, MXL2 and MXL3). By studying and describing the algorithms based on Gröbner basis concepts, we demonstrate that the Mutant strategy can be understood to be equivalent to the classical Normal Selection strategy currently used in Gröbner basis algorithms. Furthermore, we show that the "partial enlargement" technique can be understood as a strategy for restricting the number of S-polynomials considered in an iteration of the F4 Gröbner basis algorithm, while the new termination criterion used in MXL3 does not lead to termination at a lower degree than the classical Gebauer-Möller installation of Buchberger's criteria. We claim that our results map all novel concepts from the MXL family of algorithms to their well-known Gröbner basis equivalents. Using previous results that had shown the relation between the original XL algorithm and F4, we conclude that the MXL family of algorithms can be fundamentally reduced to redundant variants of F4.

A collision timing attack which exploits the data-dependent timing characteristics of combinational circuits is demonstrated. The attack is based on the correlation collision attack presented at CHES 2010, and the timing attributes of combinational circuits when implementing complex functions, e.g., S-boxes, in hardware are exploited by the help of the scheme used in another CHES 2010 paper namely fault sensitivity analysis. Similarly to other side-channel collision attacks, our approach avoids the need for a hypothetical model to recover the secret materials. The results when attacking all 14 AES ASIC cores of the SASEBO LSI chips in three different process technologies, 130nm, 90nm, and 65nm, are presented. Successfully breaking the DPA-protected and the fault attack protected cores indicates the strength of the attack.

A new class of polynomials was introduced by Bernstein (Bernstein 2007) which were later named by Sarkar as Bernstein-Rabin-Winograd (BRW) polynomials (Sarkar 2009). For the purpose of authentication, BRW polynomials offer considerable computational advantage over usual polynomials: $(m-1)$ multiplications for usual polynomial hashing versus $\lfloor\frac{m}{2}\rfloor$ multiplications and $\lceil\log_2 m\rceil$ squarings for BRW hashing, where $m$ is the number of message blocks to be authenticated. In this paper, we develop an efficient pipelined hardware architecture for computing BRW polynomials. The BRW polynomials have a nice recursive structure which is amenable to parallelization. While exploring efficient ways to exploit the inherent parallelism in BRW polynomials we discover some interesting combinatorial structural properties of such polynomials. These are used to design an algorithm to decide the order of the multiplications which minimizes pipeline delays. Using the nice structural properties of the BRW polynomials we present a hardware architecture for efficient computation of BRW polynomials. Finally we provide implementations of tweakable enciphering schemes proposed in Sarkar 2009 which uses BRW polynomials. This leads to the fastest known implementation of disk encryption systems.

ARMADILLO2 is the recommended variant of a multi-purpose cryptographic primitive dedicated to hardware which has been proposed by Badel et al. in [1]. In this paper we propose a meet-in-the-middle technique that allows us to invert the ARMADILLO2 function. Using this technique we are able to perform a key recovery attack on ARMADILLO2 in FIL-MAC application mode. A variant of this attack can also be applied when ARMADILLO2 is used as a stream cipher in the PRNG application mode. Finally we propose a (second) preimage attack on its hashing application mode. All the cryptanalysis presented in this paper can be applied for any arbitrary bitwise permutations $\sigma_0$ and $\sigma_1$ used in the internal permutation.

Due to its low cost, robustness, flexibility and ubiquitous nature, cloud computing is changing the way entities manage their data. However, various privacy concerns arise whenever potentially sensitive data is outsourced to the cloud. This paper presents a novel approach for coping with such privacy concerns. The proposed scheme prevents the cloud server from learning any possibly sensitive plaintext in the outsourced databases. It also allows the database owner to delegate users to conducting content-level fine-grained private search and decryption. Moreover, our scheme supports private querying whereby neither the database owner nor the cloud server learns query details. Additional requirement that user's input be authorized by CA can also be supported.

Secure computation enables mutually suspicious parties to compute a joint function of their private inputs while providing strong security guarantees. Amongst other things, even if some of the participants are corrupted the output is still correctly computed, and parties do not learn anything about each other's inputs except for that output. Despite the power and generality of secure computation, its use in practice seems limited. We argue that one of the reasons for this is that the model of computation on the web is not suited to the type of communication patterns needed for secure computation. Specifically, in most web scenarios clients independently connect to servers, interact with them and then leave. This rules out the use of secure computation protocols that require that \emph{all} participants interact simultaneously. In this paper, we initiate the study of secure computation in a client-server model where each client connects to the server \emph{once} and interacts with it, without any other client necessarily being connected at the same time. We point out some inherent limitations in this model and present definitions that capture what can be done. We also present a general feasibility result and several truly practical protocols for a number of functions of interest. All our protocols are based on standard assumptions, and we achieve security both in the semi-honest and malicious adversary models.

Due to the possibility of key exposure, forward security in encryption and signing has been well studied, especially in the identity-based setting where an entity's public key is that entity's name. From an efficiency point of view, one would like to use the signcryption primitive and have the best of both worlds. However, strong forward security, where the adversary cannot signcrypt in sender's name nor designcrypt in receiver's name for past time periods even if it has the secrets of both, requires periodic updating of the secret keys of the users. This is an improvement over signcryption schemes that only protect against designcrypting in the past. In this paper, we propose the first ever strong forward secure identity-based signcryption scheme which has public ciphertext verifiability and a third-party verification protocol.

Finding the shortest vector of a lattice is one of the most important problems in computational lattice theory. For a random lattice, one can estimate the length of the shortest vector using the Gaussian heuristic. However, no rigorous proof can be provided for some classes of lattices, as the Gaussian heuristic may not hold for them. In the paper we study two types of random lattices in cryptography: the knapsack lattices and the NTRU lattices. For random knapsack lattices, we prove lower bounds of shortest vector lengths, which are very close to lengths predicted by the Gaussian heuristic. For a random NTRU lattice, we prove that with a overwhelming probability, the ratio between the length of the shortest vector and the length of the target vector, which corresponds to the secret key, is at least a constant, independent of the dimension of the lattice. The main technique we use is the incompressibility method from the theory of Kolmogorov complexity.

Online advertising plays an important role in supporting many Internet services. Personalized online advertising offers marketers a way to direct ads at very specific audiences. The vast body of Internet users combined with the ease of creating and monitoring personalized advertising campaigns make online advertising an extremely strong tool for marketers. However, many concerns arise regarding the implications of online advertising for the privacy of web users. Specifically, recent works show how the privacy of Internet users may be breached by attacks utilizing personalized advertising campaigns such as those provided by Facebook. Such attacks succeed even without the user ever noticing the attack or being able to avoid it (unless refraining from going on the Internet). In this work, we suggest practical and concrete measures for preventing the feasibility of such attacks on online advertising systems, taking Facebook as our case study. We present a mechanism for releasing statistics on advertising campaigns in a way that preserves the privacy of web users. The notion of privacy that we adopt is a mathematically rigorous definition of privacy called {\em differential privacy}. In addition, we show that the seemingly overly restrictive notion of differential privacy is in fact the one necessary here, and that weaker notions would not suffice.

An MDS matrix is an important building block adopted by different algorithms that provides diffusion and therefore, has been an area of active research. In this paper, we present an idea of direct exponent and direct square of a matrix. We prove that direct square of an MDS matrix results in an MDS matrix whereas direct exponent may not be an MDS matrix. We also delineate direct exponent class and scalar multiplication class of an MDS matrix and determine the number of elements in these classes. In the end, we discuss the standing of design properties of a cryptographic primitive by replacing MDS matrix by dynamic one.

As traditional oblivious transfer protocols are treated as cryptographic primitives in most cases, they are usually executed without the consideration of possible attacks, e.g., impersonation, replaying, and man-in-the-middle attacks. Therefore, when these protocols are applied in certain applications, such as mental poker game playing and fairly contracts signing, some extra mechanisms must be combined to ensure its security. However, after the combination, we found that almost all of the resulting schemes are not efficient enough in communicational cost, which is a significant concern for all commercial transactions. Inspired by this observation, we propose a novel secure oblivious transfer protocol based on bilinear pairing which not only can provide mutual authentication to resist malicious attacks but also is efficient in communicational cost.

The goal of generic side-channel distinguishers is to allow key recoveries against any type of implementation, under minimum assumptions on the underlying hardware. Such distinguishers are particularly interesting in view of recent technological advances. Indeed, the traditional leakage models used in side-channel attacks, based on the Hamming weight or distance of the data contained in an implementation, are progressively invalidated by the increased variability in nanoscale electronic devices. In this paper, we consequently provide two contributions related to the application of side-channel analysis against emerging cryptographic implementations. First, we describe a new statistical test that is aimed to be generic and efficient when exploiting high-dimensional leakages. The proposed distinguisher is fully non-parametric. It formulates the leakage distributions using a copula and discriminates keys based on the detection of an ``outlier behavior". Next, we provide experiments putting forward the limitations of generic side-channel analysis in advanced scenarios, where leaking devices are protected with countermeasures. Our results exhibit that all non-profiled attacks published so far can sometimes give a false sense of security, due to incorrect leakage models. That is, there exists settings in which an implementation is secure against such non-profiled attacks and can be defeated with profiling. This confirms that the evaluations of cryptographic implementations should always consider profiling, as a worst case scenario.

The Hash function Skein is one of the 5 finalists of NIST SHA-3 competition. It is designed based on the threefish block cipher and it only uses three primitive operations: modular addition, rotation and bitwise XOR (ARX). In this paper, we combine two short differential paths to a long differential path using the modular differential technique. And we present the semi-free start near-collision attack up to the 32-step Skein-256 with the Hamming difference 51. The complexity of our attack is about $2^{105}$.

Any linear code can be used to construct a linear secret sharing scheme. In this paper, it is shown how to decide optimal linear codes (i.e., with the biggest information rate) realizing a given access structure over finite fields. It amounts to solving a system of quadratic equations constructed from the given access structure and the corresponding adversary structure. The system becomes a linear system for binary codes. An algorithm is also given for finding the adversary structure for any given access structure.

Elliptic curve discrete logarithm problem (ECDLP) is one of the most important hard problems that modern cryptography, especially public key cryptography, relies on. And many efforts are dedicate to solve this problem. In recent days, GPU technology develops very fast and GPU has become a powerful tool for massive computation. In this paper, we give an implementation of parallel Pollard ρ method, for ECDLP on GPU, and eliminate nearly all the conditional branches in procedures for big integer, elliptic curve and iteration function. The experimental result shows that with the help of GPU, we can gain a speedup of more than one hundred times. The branchless procedures are also useful for preventing side channel attacks.

In this paper, we compute $\ell$-isogenies between abelian varieties over a field of characteristic different from $2$ in polynomial time in $\ell$, when $\ell$ is an odd prime which is coprime to the characteristic. We use level~$n$ symmetric theta structure where $n=2$ or $n=4$. In a second part of this paper we explain how to convert between Mumford coordinates of Jacobians of genus~$2$ hyperelliptic curves to theta coordinates of level~$2$ or $4$. Combined with the preceding algorithm, this gives a method to compute $(\ell,\ell)$-isogenies in polynomial time on Jacobians of genus~$2$ curves.

In many everyday scenarios, sensitive information must be shared between parties without complete mutual trust. Private set operations are particularly useful to enable sharing information with privacy, as they allow two or more parties to jointly compute operations on their sets (e.g., intersection, union, etc.), such that only the minimum required amount of information is disclosed. In the last few years, the research community has proposed a number of secure and efficient techniques for Private Set Intersection (PSI), however, somewhat less explored is the problem of computing the magnitude, rather than the contents, of the intersection - we denote this problem as Private Set Intersection Cardinality (PSI-CA). This paper explores a few PSI-CA variations and constructs several protocols that are more efficient than the state-of-the-art.

The hardware-attractive block cipher family KTANTAN was studied by Bogdanov and Rechberger who identified flaws in the key schedule and gave a meet-in-the-middle attack. We revisit their result before investigating how to exploit the weakest key bits. We then develop several related-key attacks, e.g., one on KTANTAN32 which finds 28 key bits in time equivalent to $2^{3.0}$ calls to the full KTANTAN32 encryption. The main result is a related-key attack requiring $2^{28.44}$ time (half a minute on a current CPU) to recover the full 80-bit key. For KTANTAN48, we find three key bits in the time of one encryption, and give several other attacks, including full key recovery. For KTANTAN64, the attacks are only slightly more expensive, requiring $2^{10.71}$ time to find 38 key bits, and $2^{32.28}$ for the entire key. For all attacks, the requirements on related-key material are modest as in the forward and backward directions, we only need to flip a single key bit. All attacks succeed with probability one. Our attacks directly contradict the designers' claims. We discuss why this is, and what can be learnt from this.

Given a lattice ${\mathcal L}$ with the $i$-th successive minimum $\lambda_i$, its $i$-th gap $\frac{\lambda_i}{\lambda_1}$ often provides useful information for analyzing the security of cryptographic scheme related to ${\mathcal L}$. This paper concerns short vectors for lattices with gaps. In the first part, a $\lambda_2$-gap estimation of LWE lattices with cryptographic significance is given. For some $\gamma'$, a better reduction from $BDD_{\gamma'}$ to $uSVP_{\gamma}$ is obtained in the presence of larger $\lambda_2$-gap. The second part of the paper shows that gaps among the successive minima lead to a more efficient SVP search algorithm. As far as we know, it is the first SVP algorithm exploiting lattices with gaps.

Privacy preserving multiset union (PPMU) protocol allows a set of parties, each with a multiset, to collaboratively compute a multiset union secretly, meaning that any information other than union is not revealed. We propose efficient PPMU protocols, using multiplicative homomorphic cryptosystem. The novelty of our protocol is to directly encrypt a polynomial by representing it by an element of an extension field. The resulting protocols consist of constant rounds and improve communication cost. We also prove the security of our protocol against malicious adversaries, in the random oracle model.

We demonstrate how Game Theoretic concepts and formalism can be used to capture cryptographic notions of security. In the restricted but indicative case of two-party protocols in the face of malicious fail-stop faults, we first show how the traditional notions of secrecy and correctness of protocols can be captured as properties of Nash equilibria in games for rational players. Next, we concentrate on fairness. Here we demonstrate a Game Theoretic notion and two different cryptographic notions that turn out to all be equivalent. In addition, we provide a simulation based notion that implies the previous three. All four notions are weaker than existing cryptographic notions of fairness. In particular, we show that they can be met in some natural setting where existing notions of fairness are provably impossible to achieve.

In the setting of secure multiparty computation, a set of $n$ parties with private inputs wish to jointly compute some functionality of their inputs. One of the most fundamental results of secure computation was presented by Ben-Or, Goldwasser and Wigderson (BGW) in 1988. They demonstrated that any $n$-party functionality can be computed with \emph{perfect security}, in the private channels model. When the adversary is semi-honest this holds as long as $t<n/2$ parties are corrupted, and when the adversary is malicious this holds as long as $t<n/3$ parties are corrupted. Unfortunately, a full proof of these results was never published. In this paper, we remedy this situation and provide a full proof of security of the BGW protocol. This includes a full description of the protocol for the malicious setting, including the construction of a new subprotocol for the perfect multiplication protocol that seems necessary for the case of $n/4\leq t<n/3$.

We count the number of isogeny classes of Edwards curves over finite fields, answering a question recently posed by Rezaeian and Shparlinski. We also show that each isogeny class contains a {\em complete} Edwards curve, and that an Edwards curve is isogenous to an {\em original} Edwards curve over $\F_q$ if and only if its group order is divisible by $8$ if $q \equiv -1 \pmod{4}$, and $16$ if $q \equiv 1 \pmod{4}$. Furthermore, we give formulae for the proportion of $d \in \F_q \setminus \{0,1\}$ for which the Edwards curve $E_d$ is complete or original, relative to the total number of $d$ in each isogeny class.

A number of established and novel business models are based on fine grained billing, including pay-per-view, mobile messaging, voice calls, pay-as-you-drive insurance, smart metering for utility provision, private computing clouds and hosted services. These models apply fine-grained tariffs dependent on time-of-use or place of-use to readings to compute a bill. We extend previously proposed billing protocols to strengthen their privacy in two key ways. First, we study the monetary amount a customer should add to their bill in order to provably hide their activities, within the differential privacy framework. Second, we propose a cryptographic protocol for oblivious billing that ensures any additional expenditure, aimed at protecting privacy, can be tracked and reclaimed in the future, thus minimising its cost. Our proposals can be used together or separately and are backed by provable guarantees of security.

At PKC 2010 Smart and Vercauteren presented a variant of Gentry's fully homomorphic public key encryption scheme and mentioned that the scheme could support SIMD style operations. The slow key generation process of the Smart--Vercauteren system was then addressed in a paper by Gentry and Halevi, but their key generation method appears to exclude the SIMD style operation alluded to by Smart and Vercauteren. In this paper, we show how to select parameters to enable such SIMD operations, whilst still maintaining practicality of the key generation technique of Gentry and Halevi. As such, we obtain a somewhat homomorphic scheme supporting both SIMD operations and operations on large finite fields of characteristic two. This somewhat homomorphic scheme can be made fully homomorphic in a naive way by recrypting all data elements seperately. However, we show that the SIMD operations can be used to perform the recrypt procedure in parallel, resulting in a substantial speed-up. Finally, we demonstrate how such SIMD operations can be used to perform various tasks by studying two use cases: implementing AES homomorphically and encrypted database lookup.

We study the problem of computing on large datasets that are stored on an untrusted server. We follow the approach of \emph{amortized verifiable computation} introduced by Gennaro, Gentry, and Parno in CRYPTO 2010. We present the first practical verifiable computation scheme for high degree polynomial functions. Such functions can be used, for example, to make predictions based on polynomials fitted to a large number of sample points in an experiment. In addition to the many non-cryptographic applications of delegating high degree polynomials, we use our verifiable computation scheme to obtain new solutions for verifiable keyword search, and proofs of retrievability. Our constructions are based on the DDH assumption and its variants, and achieve adaptive security, which was left as an open problem by Gennaro \etal (albeit for general functionalities). Our second result is a primitive which we call a \emph{verifiable database} (VDB). Here, a weak client outsources a large table to an untrusted server, and makes retrieval and update queries. For each query, the server provides a response and a proof that the response was computed correctly. The goal is to minimize the resources required by the client. This is made particularly challenging if the number of update queries is unbounded. We present a VDB scheme based on the hardness of the subgroup membership problem in composite order bilinear groups.

This paper shows that if exponentiation $b=X^{k}$ in groups of finite field units or $B=[k]X$ in elliptic curves is considered as encryption of $X$ with exponent $k$ treated as symmetric key, then the decryption or the computation of $X$ from $b$ (respectively $B$) can be achieved in polynomial time with a high probability under random choice of $k$. Since given $X$ and $b$ or $B$ the problem of computing the discrete log $k$ is not known to have a polynomial time solution, the exponentiation has a trapdoor property associated with it. This paper makes this property precise. Further the decryption problem is a special case of a general problem of solving equations in groups. Such equations lead to more such trapdoor one way functions when solvable in polynomial time. The paper considers single and two variable equations on above groups and determines their solvability.

In cryptography and coding theory, it is important to study the pseudo-random sequences and the ergodic transformations. We already have the $1$-Lipshitz ergodic theory over ${\Z}_2$ established by V. Anashin and others. In this paper we present an ergodic theory over ${\F}_2[[T]]$ and some ideas which might be very useful in applications.

After several years of theoretical research on distance bounding protocols, the first implementations of such protocols have recently started to appear. These protocols are typically analyzed with respect to three types of attacks, which are historically known as Distance Fraud, Mafia Fraud, and Terrorist Fraud. We define and analyze a fourth main type of attack on distance bounding protocols, called Distance Hijacking. This type of attack poses a serious threat in many practical scenarios. We show that many proposed distance bounding protocols are vulnerable to Distance Hijacking, and we propose solutions to make these protocols resilient to this type of attack. We show that verifying distance bounding protocols using existing informal and formal frameworks does not guarantee the absence of Distance Hijacking attacks. We extend a formal framework for reasoning about distance bounding protocols to include overshadowing attacks. We use the resulting framework to prove the absence of all of the found attacks for protocols to which our countermeasures have been applied. Previous proposals for distance bounding protocols only analysed their protocols with respect to some specific attack types, whose relations and problem coverage are unknown. To improve this situation, we define an exhaustive classification for attacks on distance bounding protocols.

Revisiting long established conventions has proven very fertile in many a case. Let’s then revisit the premise that arithmetic must be constructed with the arithmetic addition as its foundation. Here we explore an arithmetic realm over integers without invoking the quintessential operation of addition. We propose an arithmetic constructed over a fundamental mapping of one set of integers into another. We start and focus here on mapping an arbitrary number of integers to a single integer, and further limit our investigation to a mapping procedure that views the input integers as a set of conflicting answers to a binary question, and attempt to figure out the single integer that best reflects the combined “wisdom” of the input answers. Thereby we construct the proposed arithmetic as ground tool for discriminant analysis. On the other end, the many-to-one mapping suggests this arithmetic as a fundamental hashing function, and the complexity of data loss suggests a new primitive for asymmetric cryptography. This arithmetic evolved from practical algorithms used by the author in his engineering practice, where the original name was BiPSA: Binary Polling Scenario Analysis. For continuity purposes we carry on the name. This article focuses on the skeleton arithmetic. Applications and substantiation will follow.

Hummingbird-2 is an encryption algorithm with a 128-bit secret key and a 64-bit initialization vector. Hummingbird-2 optionally produces an authentication tag for each message processed. Like it's predecessor Hummingbird-1, Hummingbird-2 has been targeted for low-end microcontrollers and for hardware implementation in lightweight devices such as RFID tags and wireless sensors. Compared to the previous version of the cipher, and in response to extensive analysis, the internal state has been increased to 128 bits and a flow of entropy from the state to the mixing function has been improved. In this paper we present the Hummingbird-2 algorithm, its design and security arguments, performance analysis on both software and hardware platforms, and timing analysis in relation to the ISO 18000-6C protocol.

In this paper, we present a new class of knapsack type PKC referred to as K(III)$\Sigma$PKC. In a sharp contrast with the conventional knapsack type PKC's, in our proposed scheme, K(III)$\Sigma$PKC, no conventional secret sequence but the natural binary number with noise is used. We show that the coding rate, a more conservative measure for the security on knapsack PKC, can be made approximately 1.0. In Appendix, we present K(II)$\Sigma$PKC.

In this paper, we present a new secret sharing scheme, referred to as KSS(I) on the basis of systematic Reed-Solomon code[2]. We show that KSS(I) can be successfully applied to biometrics.

Linear cryptanalysis, along with differential cryptanalysis, is an important tool to evaluate the security of block ciphers. This work introduces a novel extension of linear cryptanalysis: zero-correlation linear cryptanalysis, a technique applicable to many block cipher constructions. It is based on linear approximations with a correlation value of exactly zero. For a permutation on $n$ bits, an algorithm of complexity $2^{n-1}$ is proposed for the exact evaluation of correlation. Non-trivial zero-correlation linear approximations are demonstrated for various block cipher structures including AES, balanced Feistel networks, Skipjack, CLEFIA, and CAST256. As an example, using the zero-correlation linear cryptanalysis, a key-recovery attack is shown on 6 rounds of AES-192 and AES-256 as well as 13 rounds of CLEFIA-256.

Sorting is among the most fundamental and well-studied problems within computer science and a core step of many algorithms. In this article, we consider the problem of constructing a secure multi-party computing (MPC) protocol for sorting. Our protocol builds on previous work in the fields of MPC and sorting networks. Apart from the immediate uses for sorting, our protocol can be used as a building-block in more complex algorithms. We present a weighted set intersection algorithm, where each party inputs a set of weighted elements and the output consists of the input elements with their weights summed. As a practical example, we apply our protocols in a network security setting for aggregation of security incident reports from multiple reporters, specifically to detect stealthy port scans in a distributed but privacy preserving manner. Both sorting and weighted set intersection use $\Ordo{n \log^2 n}$ comparisons in $\Ordo{\log^2 n}$ rounds with practical constants. Our protocols can be built upon any secret sharing scheme supporting multiplication and addition. We have implemented and evaluated the performance of sorting on the Sharemind secure multi-party computation platform, demonstrating the real-world performance of our proposed protocols.

In this paper, we first modify the Smart-Vercauteren’s fully homomorphic encryption scheme [SV10] by applying self-loop bootstrappable technique. The security of the modified scheme only depends on the hardness of the polynomial coset problem, removing the assumption of the sparse subset sum problem in the original paper in [SV10]. Moreover, we construct a non-self-loop in FHE by using cycle keys. Then, we further improve our scheme to make it be practical. The securities of our improving FHE’s are respectively based on the hardness of factoring integer problem, solving Diophantine equation problem, and finding approximate greatest common divisor problem.

Fix positive integers B and w. Let C be a linear code over F_2 of length Bw. The 2-regular-decoding problem is to &#64257;nd a nonzero codeword consisting of w length-B blocks, each of which has Hamming weight 0 or 2. This problem appears in attacks on the FSB (fast syndrome-based) hash function and related proposals. This problem differs from the usual information-set-decoding problems in that (1) the target codeword is required to have a very regular structure and (2) the target weight can be rather high, so that there are many possible codewords of that weight. Augot, Finiasz, and Sendrier, in the paper that introduced FSB, pre- sented a variant of information-set decoding tuned for 2-regular decoding. This paper improves the Augot–Finiasz–Sendrier algorithm in a way that is analogous to Stern's improvement upon basic information-set decoding. The resulting algorithm achieves an exponential speedup over the previous algorithm.

We first present a fully homomorphic encryption scheme over the integers, which modifies the fully homomorphic encryption scheme in [vDGHV10]. The security of our scheme is merely based on the hardness of finding an approximate-GCD problem over the integers, which is given a list of integers perturbed by the small error noises, removing the assumption of the sparse subset sum problem in the origin scheme [vDGHV10]. Then, we construct a new fully homomorphic encryption scheme, which extends the above scheme from approximate GCD over the ring of integers to approximate principal ideal lattice over the polynomial integer ring. The security of our scheme depends on the hardness of the decisional approximate principle ideal lattice polynomial (APIP), given a list of approximate multiples of a principal ideal lattice. At the same time, we also provide APIP-based fully homomorphic encryption by introducing the sparse subset sum problem. Finally, we design a new fully homomorphic encryption scheme, whose security is based on the hardness assumption of approximate lattice problem and the decisional SSSP.

Although malleability is undesirable in traditional digital signatures, schemes with limited malleability properties enable interesting functionalities that may be impossible to obtain otherwise (e.g., homomorphic signatures). In this paper, we introduce a new malleable signature scheme called bounded vector signatures. The proposed scheme allows a user to sign a multi-dimensional vector of values, along with a description of the context within which the vector should be interpreted. The scheme includes a unique malleability property, which we refer to as the stretch property, that allows the components of the signed vector to be increased up to a pre-defined limit without access to the signing key. Decreasing these values, however, remains computationally infeasible. We prove the security of our construction under the strong RSA and decisional Diffie-Hellman assumptions in the random oracle model. Finally, we underscore the utility of bounded vector signatures by discussing their use in distributed systems security applications.

Message authentication codes usually require the underlining universal hash functions to have a long output so that the probability of successfully forging messages is low enough for cryptographic purposes. To take advantage of fast operation on word-size parameters in modern processors, long-output universal hashing schemes can be securely constructed by concatenating several instances of short-output primitives. In this paper, we describe a new method for short-output universal hash function termed digest() suitable for very fast software implementation and applicable to secure message authentication. The method possesses a higher level of security relative to other well-studied short-output universal hashing schemes. Suppose that the universal hash output is fixed at one word of b bits, then the collision probability of ours is 2^{1-b} compared to 6 * 2^{-b} of MMH, whereas 2^{-b/2} of NH within UMAC is far away from optimality. In addition to message authentication codes, we show how short-output universal hashing is applicable to manual authentication protocols where universal hash keys are used in a very different and interesting way.

Differential cryptanalysis is a well-known statistical attack on block ciphers. We present here a generalisation of this attack called multiple differential cryptanalysis. We study the data complexity, the time complexity and the success probability of such an attack and we experimentally validate our formulas on a reduced version of PRESENT. Finally, we propose a multiple differential cryptanalysis on 18-round PRESENT for both 80-bit and 128-bit master keys.

In this paper, we first introduce a new concept of approximate lattice problem (ALP), which is an extension of learning with errors (LWE). Next, we propose two ALP-based public key encryption schemes. Then, we construct two new fully homomorphic encryption scheme (FHE) based on respectively approximate principal ideal lattice problem with related modulus (APIP-RM) and approximate lattice problem with related modulus (ALP-RM). Moreover, we also extend our ALP-RM-based FHE to the ALP problem with unrelated modulus (ALP-UM). Our work is different from previous works in three aspects: (1)We extend the LWE problem to the ALP problem. This ALP problem is similar to the closest vector problem in lattice. We believe that this problem is independent of interest. (2)We construct a new FHE by using a re-randomizing method, which is different from the squashing decryption in previous works. (3)The expansion rate is merely O(k) with k a security parameter in Our FHE, which can be improved to O(logk) by using dimension reduction [BV11], whereas all previous schemes are at least O(k*logk) [BV11, Gen11, LNV11]. Our method can also decrease a factor k of the expansion rate in their schemes.

The need for controlled (privacy-preserving) sharing of sensitive information occurs in many different and realistic everyday scenarios, ranging from national security to social networking. We consider two interacting parties, at least one of which seeks information from the other: the latter is either willing, or compelled, to share information. This poses two challenges: (1) how to enable this type of sharing such that parties learn no information beyond what they are entitled to, and (2) how to do so efficiently, in real-world practical terms. This paper explores the notion of Privacy-Preserving Sharing of Sensitive Information (PPSSI), and provides two concrete and efficient instantiations, modeled in the context of simple database querying. Proposed techniques function as a privacy shield to protect parties from disclosing more than the required minimum of their respective sensitive information. PPSSI deployment prompts several challenges, that are addressed in this paper. Extensive experimental results attest to the practicality of attained privacy features and show that they incur quite low overhead (e.g., $10\%$ slower than standard MySQL).

Key agreement (KA) allows two or more users to negotiate a secret session key among them over an open network. Authenticated key agreement (AKA) is a KA protocol enhanced to prevent active attacks. AKA can be achieved using a public-key infrastructure (PKI) or identity-based cryptography. However, the former suffers from a heavy certificate management burden while the latter is subject to the so-called key escrow problem. Recently, certificateless cryptography was introduced to mitigate these limitations. We propose an efficient certificateless two-party AKA protocol. Security is proven under the standard computational Diffie-Hellman (CDH) and bilinear Diffie-Hellman (BDH) assumptions. Our protocol is efficient and practical, because it requires only one pairing operation and three scale multiplications by each party. Moreover, the pairing operation and one scale multiplication scale can be pre-computed, then only two scale multiplications are needed to finished the key agreement.

Bent functions (Boolean functions with extreme nonlinearity properties) are actively studied for their numerous applications in cryptography, coding theory, and other fields. New statements of problems lead to a large number of generalizations of the bent functions many of which remain little known to the experts in Boolean functions. In this article, we offer a systematic survey of them.

In this work we construct public key encryption schemes that admit a protocol for /blindly/ decrypting ciphertexts. In a blind decryption protocol, a user with a ciphertext interacts with a secret keyholder such that the user obtains the decryption of the ciphertext and the keyholder learns nothing about what it decrypted. While we are not the first to consider this problem, previous works provided only weak security guarantees against malicious users. We provide, to our knowledge, the first practical blind decryption schemes that are secure under a strong CCA security definition. We prove our construction secure in the standard model under simple, well-studied assumptions in bilinear groups. To motivate the usefulness of this primitive we discuss several applications including privacy-preserving distributed file systems and Oblivious Transfer schemes that admit /public/ contribution.

Cryptographic solutions to privacy-preserving multiparty linear programming are slow. This makes them unsuitable for many economically important applications, such as supply chain optimization, whose size exceeds their practically feasible input range. In this paper we present a privacy-preserving transformation that allows secure outsourcing of the linear program computation in an efficient manner. We evaluate security by quantifying the leakage about the input after the transformation and present implementation results. Using this transformation, we can mostly replace the costly cryptographic operations and securely solve problems several orders of magnitude larger.

We propose (T,N) multi-ciphertext scheme for symmetric encryption. The scheme encrypts a message into N distinct ciphertexts. The knowledge of the symmetric key allows decryption of the original message from any ciphertext. Moreover, knowing T+1 ciphertexts allows efficient recovery of the original message without the key (and without revealing the key as well). We define the security property of the scheme, and prove the security of the proposed scheme. We discuss several variants of the basic scheme that provides additional authenticity and efficiency.

Common Randomness Generation (CRG) and Secret Key Establishment (SKE) are fundamental primitives that are used in information-theoretic coding and cryptography. We study these two problems over the two-way channel model of communication, introduced by Shannon. In this model, the common randomness (CK) capacity is defined as the maximum number of random bits per channel use that the two parties can generate. The secret key (SK) capacity is defined similarly when the random bits are also required to be secure against a passive adversary. We provide lower bounds on the two capacities. These lower bounds are tighter than those one might derive based on the previously known results. We prove our lower bounds by proposing a two-round, two-level coding construction over the two-way channel. We show that the lower bound on the common randomness capacity can also be achieved using a simple interactive channel coding (ICC) method. We furthermore provide upper bounds on these capacities and show that the lower and the upper bounds coincide when the two-way channel consists of two independent (physically degraded) one-way channels. We apply the results to the case where the channels are binary symmetric.

We present a complete set of efficient explicit formulas for arithmetic in the degree 0 divisor class group of a genus two real hyperelliptic curve given in affine coordinates. In addition to formulas suitable for curves defined over an arbitrary finite field, we give simplified versions for both the odd and the even characteristic cases. Formulas for baby steps, inverse baby steps, divisor addition, doubling, and special cases such as adding a degenerate divisor are provided, with variations for divisors given in reduced and adapted basis. We describe the improvements and the correctness together with a comprehensive analysis of the number of field operations for each operation. Finally, we perform a direct comparison of cryptographic protocols using explicit formulas for real hyperelliptic curves with the corresponding protocols presented in the imaginary model.

Unconditionally secure signature (USS) schemes provide the ability to electronically sign documents without the reliance on computational assumptions needed in traditional digital signatures. Unlike digital signatures, USS schemes require both different signing and different verification algorithms for each user in the system. Thus, any viable security definition for a USS scheme must carefully treat the subject of what constitutes a valid signature. That is, it is important to distinguish between signatures that are created using a user's signing algorithm and signatures that may satisfy one or more user verification algorithms. Moreover, given that each verifier has his own distinct verification algorithm, a USS scheme must necessarily handle the event of a disagreement. In this paper, we present a new security model for USS schemes that incorporates these notions, as well as give a formal treatment of dispute resolution and the trust assumptions required. We provide formal definitions of non-repudiation and transferability in the context of dispute resolution, and give sufficient conditions for a USS scheme to satisfy these properties. Finally, we give an analysis of the construction of Hanaoka et al. in our security model.

We present the first cryptographically sound security proof of a routing protocol for mobile ad-hoc networks. More precisely, we show that the route discovery protocol does not output a non-existing path under arbitrary active attacks, where on a non-existing path there exists at least one pair of neighboring nodes without communication connection during the run of the route discovery protocol. The proof relies on the Dolev-Yao-style model of Backes, Pfitzmann and Waidner, which allows for mapping results obtained symbolically within this model to cryptographically sound proofs if certain assumptions are met.

Memory checking studies the problem of cryptographically verifying the correctness of untrusted indexed storage. After a series of results yielding checkers with $O(\log n)$ query complexity, Dwork, Naor, Ruthblum and Vaikuntanathan~\cite{naor-lower-mm08} derived an $\Omega(\log n/\log \log n)$ lower bound on the query complexity of any checker operating on memory words of polylogarithmic size, where $n$ is the number of memory indices. In view of this lower bound, we make the following two contributions: (1) We construct an \emph{optimal online memory checker} of $\Theta(\log n/\log \log n)$ query complexity, closing in this way the relevant complexity gap. Our construction employs pseudorandom functions and a simple data grouping technique inspired by I/O algorithms. (2) In our second and main result, we put forth the notion of \emph{parallel online memory checking} and provide parallel checker constructions with $O(1)$ query complexity and $O(\log n)$ processors. We initially show that checkers that use \emph{secret} small memory, including our optimal checker, are easily parallelizable; However, checkers that use only \emph{reliable} small memory cannot be naturally parallelized. We overcome this barrier by employing an algebraic hash function based on lattices assumptions and construct such parallel checkers with only reliable memory. To achieve our result, we establish and exploit a property that we call \emph{repeated linearity} of lattice-based hash functions, that might be of independent interest. Applications of our checkers include \emph{update-optimal} external memory authenticated data structures. We construct an authenticated B-tree data structure which can be updated with \emph{two} I/Os, outperforming the \emph{logarithmic} update complexity of hash-based external memory Merkle trees.

Although anonymous authentication has been extensively studied, so far no scheme has been widely adopted in practice. A particular issue with fully anonymous authentication schemes is that users cannot easily be prevented from copying and sharing credentials. In this paper, we propose an anonymous authentication scheme for mobile devices that prevents copying and sharing of credentials based on hardware security features. Our system is an optimized adaptation of an existing direct anonymous attestation (DAA) scheme, specifically designed for resource-constrained mobile devices. Our solution provides (i) anonymity and untraceability of mobile embedded devices against service providers, (ii) secure device authentication even against collusions of malicious service providers, and (iii) allows for revocation of authentication credentials. We present a new cryptographic scheme with a proof of security, as well as an implementation on ARM TrustZone. Moreover, we evaluate the efficiency of our approach and demonstrate its suitability for mobile devices.

Group signature allows a group member to sign messages anonymously on the behalf of a group. In the case of a dispute, the designated group manager can open the signature to reveal the identity of its originator. As far as we know, most of the group signatures are based on traditional cryptography, such as RSA and discrete logarithm. Unfortunately these schemes would be broken if quantum computers emerge. The $\mathcal{MQ}$-problem based Multivariate Public-Key Cryptosystem (MPKC) is an important alternative to traditional PKCs for its potential to resist future attacks of quantum computers. The first group signature scheme based on MPKC is proposed in this paper. This scheme owns two special but important features. First, the group signature can be divided into different time periods. The signatures are linkable in the same time period, but un-linkable between different time periods. Second, the privileges of the group manager is limited. The group manager can not open a signature without the help of the verifier. These features are important in some applications such as e-voting systems. The theory of this scheme is simple and its security relies on the Isomorphism of Polynomials (IP) Problem and random hash function.

In addition to its usual complexity assumptions, cryptography silently assumes that information can be physically protected in a single location. As one can easily imagine, real-life devices are not ideal and information may leak through different physical side-channels. It is a known fact that information leakage is a function of both the executed code $F$ and its input $x$.\smallskip In this work we explore the use of polymorphic code as a way of resisting side channel attacks. We present experimental results with procedural and functional languages. In each case we rewrite the protected code code $F_i$ before its execution. The outcome is a genealogy of programs $F_0,F_1,\ldots$ such that for all inputs $x$ and for all indexes $i \neq j \Rightarrow F_i(x)=F_j(x)\mbox{~and~}F_i\neq F_j$. This is shown to increase resistance to side channel attacks.\smallskip

We describe improved versions of index-calculus algorithms for solving discrete logarithm problems in Jacobians of high-genus hyperelliptic curves defined over even characteristic fields. Our first improvement is to incorporate several ideas for the low-genus case by Gaudry and Theriault, including the large prime variant and using a smaller factor base, into the large-genus algorithm of Enge and Gaudry. We extend the analysis in [24] to our new algorithm, allowing us to predict accurately the number of random walk steps required to find all relations, and to select optimal degree bounds for the factor base. Our second improvement is the adaptation of sieving techniques from Flassenberg and Paulus, and Jacobson to our setting. The new algorithms are applied to concrete problem instances arising from the Weil descent attack methodology for solving the elliptic curve discrete logarithm problem, demonstrating significant improvements in practice.

We propose a four-tiered parallelization model for acceleration of the secure multiparty computation (SMC) on the CUDA based Graphic Processing Unit (GPU) cluster architecture. Specification layer is the top layer, which adopts the SFDL of Fairplay for specification of secure computations. The SHDL file generated by the SFDL compiler of Fairplay is used as inputs to the function layer, for which we developed both multi-core and GPU based control functions for garbling of various types of Boolean gates, and ECC-based 1-out-of-2 Oblivious Transfer (OT). These high level control functions invoke computation of 3-DGG (3-DES gate garbling), EGG (ECC based gate garbling), and ECC based OT that run at the secure protocol layer. An ECC Arithmetic GPU Library (EAGL), which co-run on the GPU cluster and its host, manages utilization of GPUs in parallel computing of ECC arithmetic. Experimental results show highly linear acceleration of ECC related computations when the system is not overloaded; When running on a GPU cluster consisted of 6 Tesla C870 devices, with GPU devices fully loaded with over 3000 execution threads, Fastplay achieved 35~40 times of acceleration over a serial implementation running on a 2.53GHz duo core CPU and 4GB memory. When the execution thread count exceeds this number, the speed up factor remains fairly constant, yet slightly increased.

In tandem with recent progress on computing on encrypted data via fully homomorphic encryption, we present a framework for computing on *authenticated* data via the notion of slightly homomorphic signatures, or P-homomorphic signatures. With such signatures, it is possible for a third party to derive a signature on the object m' from a signature of m as long as P(m,m')=1 for some predicate P which captures the ``authenticatable relationship" between m' and m. Moreover, a derived signature on m' reveals no extra information about the parent m. Our definition is carefully formulated to provide one unified framework for a variety of distinct concepts in this area, including arithmetic, homomorphic, quotable, redactable, transitive signatures and more. It includes being unable to distinguish a derived signature from a fresh one even when given the original signature. The inability to link derived signatures to their original sources prevents some practical privacy and linking attacks, which is a challenge not satisfied by most prior works. Under this strong definition, we then provide generic constructions for all univariate and closed predicates, and specific efficient constructions for a broad class of natural predicates such as quoting, subsets, weighted sums, averages, and Fourier transforms. To our knowledge, these are the first efficient constructions for these predicates (excluding subsets) that provably satisfy this strong security notion.

The ALRED family of Message Authentication Codes (MAC's) is based on three principles: Using a keyless block cipher in CBC mode to process the message, choosing AES-128 as this cipher, and reducing the effective number of rounds to 4 in order to speed up the processing. In this paper we show that each one of these principles creates significant weaknesses. More specifically, we show that any ALRED-type MAC which uses a keyless block cipher is vulnerable to new time/memory tradeoff attacks which are faster than generic tradeoff attacks on one-way functions. We then use the special properties of keyless AES to attack any number of rounds (4, 10, or a million) by forging the MAC of essentially any desired message in negligible time and space after a one-time preprocessing stage requiring 2^{96} time and negligible space. For the recommended 4-round version we show how to do the same using an improved preprocessing stage with a semi-practical time complexity of 2^{65}, which is the best one can hope for in such MAC constructions. Finally, we show that even if we replace the 4-round keyless AES by a 5-round or a 6-round version with additional secret round keys we can still compute such MAC's much faster than via exhaustive search.

The goal of \emph{Multi-Party Computation} (MPC) is to perform an arbitrary computation in a distributed, private, and fault-tolerant way. For this purpose, a fixed set of $n$ parties runs a protocol that tolerates an adversary corrupting a subset of the participating parties, and still preserves certain security guarantees. Most MPC protocols provide security guarantees in an \emph{all-or-nothing} fashion: Either the set of corrupted parties is tolerated and the protocol provides all specified security guarantees, or the set of corrupted parties is not tolerated and the protocol provides no security guarantees at all. Similarly, corruptions are in an all-or-nothing fashion: Either a party is fully honest, or it is fully corrupted. For example, an actively secure protocol is rendered completely insecure when just one party is corrupted additionally to what is tolerated, even if all corrupted parties are only passive. In this paper, we provide the first treatment of MPC with graceful degradation of both security and corruptions. First of all, our protocols provide graceful degradation of security, i.e., different security guarantees depending on the actual number of corrupted parties: the more corruptions, the weaker the security guarantee. We consider all security properties generally discussed in the literature (secrecy, correctness, robustness, fairness, and agreement on abort). Furthermore, the protocols provide graceful degradation with respect to the corruption type, by distinguishing fully honest parties, passively corrupted parties, and actively corrupted parties. Security can be maintained against more passive corruptions than is possible for active corruptions. We focus on perfect security, and prove exact bounds for which MPC with graceful degradation of security and corruptions is possible for both threshold and general adversaries. Furthermore, we provide protocols that meet these bounds. This strictly generalizes known results on hybrid security and mixed adversaries.

In this article, the theory of multidimensional linear attacks on block ciphers is developed and the basic attack algorithms and their complexity estimates are presented. As an application the multidimensional linear distinguisher derived by Cho for the block cipher PRESENT is discussed in detail.

Roughly speaking, an encryption scheme is said to be non-malleable, if no adversary can modify a ciphertext so that the resulting message is meaningfully related to the original message. We compare this notion of security to secrecy and authenticity, and provide a complete characterization of their relative strengths. In particular, we show that information-theoretic perfect non-malleability is equivalent to perfect secrecy of two different messages. This implies that for $n$-bit messages a shared secret key of length roughly $2n$ is necessary to achieve non-malleability, which meets the previously known upper bound. We define approximate non-malleability by relaxing the security conditions and only requiring non-malleability to hold with high probability (over the choice of secret key), and show that any authentication scheme implies approximate non-malleability. Since authentication is possible with a shared secret key of length roughly $\log n$, the same applies to approximate non-malleability.

We propose a new approach to practical two-party computation secure against an active adversary. All prior practical protocols were based on Yao's garbled circuits. We use an OT-based approach and get efficiency via OT extension in the random oracle model. To get a practical protocol we introduce a number of novel techniques for relating the outputs and inputs of OTs in a larger construction. We also report on an implementation of this approach, that shows that our protocol is more efficient than any previous one: For big enough circuits, we can evaluate more than 20000 Boolean gates per second. As an example, evaluating one oblivious AES encryption (~34000 gates) takes 64 seconds, but when repeating the task 27 times it only takes less than 3 seconds per instance.

We show that Katz-Wang’s duplicating key and ciphertext technique can be extended to a generic method that can be used in a certain category of Identity-Based Encryption (IBE) schemes for the purposes of improving their security reductions. We further develop two refined approaches by adapting the randomness reuse technique in the Katz-Wang technique: one is public key duplication, and the other is master key duplication. Compared to the Katz-Wang technique, our two refined approaches do not only improve the performances of the resulting IBE schemes but also enable a reduction algorithm to deal with decryption queries correctly and therefore can achieve chosen ciphertext security. As case studies, we apply these two approaches to modify the Boneh- Franklin IBE scheme and the Boneh-Boyen IBE scheme, respectively. Both of the modifications improve the tightness of security reductions, compared to the original schemes, with a reasonably low cost.

In this paper we characterize (octal) bent generalized Boolean functions defined on $\BBZ_2^n$ with values in $\BBZ_8$. Moreover, we propose several constructions of such generalized bent functions for both $n$ even and $n$ odd.

The famous Leftover Hash Lemma (LHL) states that (almost) universal hash functions are good randomness extractors. Despite its numerous applications, LHL-based extractors suffer from the following two drawbacks: (1) Large Entropy Loss: to extract v bits from distribution X of min-entropy m which are e-close to uniform, one must set v <= m - 2*log(1/e), meaning that the entropy loss L = m-v >= 2*log(1/e). (2) Large Seed Length: the seed length n of (almost) universal hash function required by the LHL must be at least n >= min(u-v, v + 2*log(1/e))-O(1), where u is the length of the source. Quite surprisingly, we show that both limitations of the LHL --- large entropy loss and large seed --- can often be overcome (or, at least, mitigated) in various quite general scenarios. First, we show that entropy loss could be reduced to L=log(1/e) for the setting of deriving secret keys for a wide range of cryptographic applications. Specifically, the security of these schemes gracefully degrades from e to at most e + sqrt(e * 2^{-L}). (Notice that, unlike standard LHL, this bound is meaningful even for negative entropy loss, when we extract more bits than the the min-entropy we have!) Based on these results we build a general *computational extractor* that enjoys low entropy loss and can be used to instantiate a generic key derivation function for *any* cryptographic application. Second, we study the soundness of the natural *expand-then-extract* approach, where one uses a pseudorandom generator (PRG) to expand a short "input seed" S into a longer "output seed" S', and then use the resulting S' as the seed required by the LHL (or, more generally, any randomness extractor). Unfortunately, we show that, in general, expand-then-extract approach is not sound if the Decisional Diffie-Hellman assumption is true. Despite that, we show that it is sound either: (1) when extracting a "small" (logarithmic in the security of the PRG) number of bits; or (2) in *minicrypt*. Implication (2) suggests that the sample-then-extract approach is likely secure when used with "practical" PRGs, despite lacking a reductionist proof of security! Finally, we combine our main results to give a very *simple and efficient* AES-based extractor, which easily supports variable-length messages, and is likely to offer our *improved entropy loss bounds* for any computationally-secure application, despite having a *fixed-length* seed.

The hash-and-sign RSA signature is one of the most elegant and well known signatures schemes, extensively used in a wide variety of cryptographic applications. Unfortunately, the only existing analysis of this popular signature scheme is in the random oracle model, where the resulting idealized signature is known as the RSA Full Domain Hash signature scheme (RSA-FDH). In fact, prior work has shown several “uninstantiability” results for various ab- stractions of RSA-FDH, where the RSA function was replaced by a family of trapdoor random permutations, or the hash function instantiating the random oracle could not be keyed. These abstractions, however, do not allow the reduction and the hash function instantiation to use the algebraic properties of RSA function, such as the multiplicative group structure of Z&#8727;n. In contrast, the multiplicative property of the RSA function is critically used in many standard model analyses of various RSA-based schemes. Motivated by closing this gap, we consider the setting where the RSA function representation is generic (i.e., black-box) but multiplicative, whereas the hash function itself is in the standard model, and can be keyed and exploit the multiplicative properties of the RSA function. This setting abstracts all known techniques for designing provably secure RSA-based signatures in the standard model, and aims to address the main limitations of prior uninstantiability results. Unfortunately, we show that it is still impossible to reduce the security of RSA-FDH to any natural assumption even in our model. Thus, our result suggests that in order to prove the security of a given instantiation of RSA-FDH, one should use a non-black box security proof, or use specific properties of the RSA group that are not captured by its multiplicative structure alone. We complement our negative result with a positive result, showing that the RSA-FDH signatures can be proven secure under the standard RSA assumption, provided that the number of signing queries is a-priori bounded.

This paper proposes a novel fault-propagation pattern based differential fault analysis method - FPP-DFA, and proves its feasibility on SPN structure block ciphers using bitwise permutation, such as PRESENT and PRINTcipher. Simulated experiments demonstrate that, with the fault model of injecting one nibble fault into the r-2th round substitution layer, on average 8 and 16 faulty samples can reduce the master key search space of PRESENT-80/128 to $2^{14.7}$ and $2^{21.1}$ respectively, and 12 and 24 effective faulty samples can reduce the master key search space of PRINTcipher-48/96 to $2^{13.7}$ and $2^{22.8}$ respectively; with the fault model of injecting one nibble fault into the r-3th round substitution layer, 8 samples can reduce the master key search space of PRINTCipher-96 to $2^{18.7}$.

Broadcast encryption provides a convenient method to distribute digital content to subscribers over an insecure broadcast channel. Traitor tracing is needed because some users may give out their decryption keys to construct pirate decoders. There are many traitor tracing schemes based on collusion secure codes and identifiable parent property codes. However, these schemes are subject to public collaboration of traitors, which is presented by Billet and Phan in EUROCRYPT 2009 as an attack against code-based traitor tracing schemes. In this paper, we describe a generic collusion secure codes based scheme secure against such collaboration. Our scheme is motivated by the idea of identity-based encryption with wildcards (WIBE). We regard the collusion secure codeword for each user as his/her identity, and issue private key accordingly. When in broadcasting, we use a special pattern of WIBE, namely all bit positions in the codewords of intended receivers are set as wildcards. When in tracing, we use another special pattern of WIBE, namely all positions are set as wildcards except the tracing position. By using WIBE, each user is issued one decryption key which should be used as a whole and any incomplete part of the key is useless, while in previous codes based schemes each user holds a number of keys that can be used separately for different bit positions in the codeword. Thus our scheme is resistant to public collaboration, since if the decryption key is disclosed as a whole, it will immediately lead to the accusation of the very traitor. Our idea fits well for code based traitor tracing schemes, no matter collusion secure codes or identifiable parent property codes. We provide an instance based on Boneh-Boyen-Goh WIBE scheme, achieving constant private key storage cost for each user. We also present another instance achieving shorter ciphertexts, on the expense of increasing public keys and private keys. Our scheme presents an answer to the problem left open by Billet and Phan.

In the paper we study lower bounds on the number of bent functions that can be obtained by iterative constructions, namely by the construction proposed by A.Canteaut and P.Charpin in 2003. The number of bent iterative functions is expressed in terms of sizes of finite sets and it is shown that evaluation of this number is closely connected to the problem of decomposing Boolean function into sum of two bent functions. A new lower bound for the number of bent iterative functions that is supposed to be asymptotically tight is given. Applying Monte-Carlo methods the number of bent iterative functions in 8 variables is counted. Based on the performed calculations several hypotheses on the asymptotic value of the number of all bent functions are formulated.

The problem of secure multiparty computation -- performing some computation based on distributed, private inputs -- has been studied intensively for more than twenty years. This work includes both ``one shot'' applications as well as reactive tasks, where the exact computation is not known in advance. We extend this line of work by asking whether it is possible to \emph{efficiently} both update and query secret data. A clearer formulation is, perhaps, to ask whether is it possible to construct efficient datastructures based on secure multiparty computation primitives. It is possible to construct arbitrary secure datastructures based on an oblivious RAM (ORAM). However, current state of the art information theoretically secure solutions incur a poly-logarithmic overhead on both secure computation and memory. The overhead is much smaller when considering computationally secure solutions, however, this requires secure evaluation of a one-way function as a primitive, which may reintroduce a considerable overhead. By constructing a secure priority queue we show that practical datastructures are possible. The ideas are radically different than those used in any ORAM implementation: The present solution accesses data in a \emph{deterministic} manner, whereas all ORAMs \emph{randomize} the access pattern in order to hide it. The priority queue operations -- insertion into the structure and deletion of the minimal element contained therein -- both require $\bigo(\log^2 n)$ invocations of the cryptographic primitives (secure arithmetic and comparison) amortized in $O(1)$ rounds amortized, where $n$ is the overall number of operations performed.

This paper shows that a turbo-coded communication system can be made secure with a little bit of complexity cost. The classical permutation ciphers are revisited and analyzed. Firstly, the ideal stream permutation ciphers are shown to be asymptotically information-theoretically secure in the sense that the channel from plaintext to ciphertext has a vanished capacity, while the practical stream permutation ciphers are shown to be more secure than the classical stream ciphers in terms of protecting keys. Secondly, a necessary condition to break down a block permutation cipher is derived, which is then utilized to guarantee the computational security of a modified block permutation cipher. Thirdly, turbo ciphers (turbo-like codes with private interleavers) are proposed and analyzed.

Many identity-based digital signature schemes using bilinear pairings have been proposed. But the relative computation cost of the pairing is approximately twenty times higher than that of the scalar multiplication over elliptic curve group. In order to save the running time and the size of the signature, we propose an identity based signature scheme without bilinear pairings. With both the running time and the size of the signature being saved greatly, our scheme is more practical than the previous related schemes for practical application.

We propose a compact coprocessor for the AES (encryption, decryption, and key expansion) and the cryptographic hash function ECHO on Virtex-$5$ and Virtex-$6$ FPGAs. Our architecture is built around a $8$-bit datapath. The Arithmetic and Logic Unit performs a single instruction that allows for implementing AES encryption, AES decryption, AES key expansion, and ECHO at all levels of security. Thanks to a careful organization of AES and ECHO internal states in the register file, we manage to generate all read and write addresses by means of a modulo-$16$ counter and a modulo-$256$ counter. A fully autonomous implementation of ECHO and AES on a Virtex-$5$ FPGA requires $193$ slices and a single $36$k memory block, and achieves competitive throughputs. Assuming that the security guarantees of ECHO are at least as good as the ones of the SHA-$3$ finalists BLAKE and Keccak, our results show that ECHO is a better candidate for low-area cryptographic coprocessors. Furthermore, the design strategy described in this work can be applied to combine the AES and the SHA-$3$ finalist {G}røstl.

There exist 3 different types of research about SCAs, such as SCA analysis, SCA evaluation and SCA countermeasures. All of these studies try to establish more security in cryptographic software, hardware and system. Evaluation of SCA tries to find factors of different SCAs, moreover, the purpose of SCA Evaluation could be regarded as the first step of building countermeasures against SCAs. We choose DPA, which is one of the most popular and realistic SCAs at present, as our research target to build practical evaluation scheme and countermeasure which can be regarded as plug-in of EDA toolkits and could help designers of circuits to judge the power leakage and improve the resistance against DPAs automatically. Our contribution concludes: more accurate evaluation scheme; more efficient balanced scheme; be portable to build countermeasures based on evaluation scheme, furthermore, our countermeasures could be plug in EDA toolkits which is automatic and transparent to designers of circuits.

There have been numerous recent proposals for key predistribution schemes for wireless sensor networks based on various types of combinatorial structures such as designs and codes. Many of these schemes have very similar properties and are analysed in a similar manner. We seek to provide a unified framework to study these kinds of schemes. We derive general formulas for the metrics of the resulting key predistribution schemes that can be evaluated for a particular scheme simply by substituting appropriate parameters of the underlying combinatorial structure. We also compare various classes of schemes based on different designs, and point out that some existing proposed schemes are in fact identical, even though their descriptions may seem different.

The FSB (fast syndrome-based) hash function was submitted to the SHA-3 competition by Augot, Finiasz, Gaborit, Manuel, and Sendrier in 2008, after preliminary designs proposed in 2003, 2005, and 2007. Many FSB parameter choices were broken by Coron and Joux in 2004, Saarinen in 2007, and Fouque and Leurent in 2008, but the basic FSB idea appears to be secure, and the FSB submission remains unbroken. On the other hand, the FSB submission is also quite slow, and was not selected for the second round of the competition. This paper introduces RFSB, an enhancement to FSB. In particular, this paper introduces the RFSB-509 compression function, RFSB with a particular set of parameters. RFSB-509, like the FSB-256 compression function, is designed to be used inside a 256-bit collision-resistant hash function: all known attack strategies cost more than 2^128 to find collisions in RFSB-509. However, RFSB-509 is an order of magnitude faster than FSB-256. On a single core of a Core 2 Quad CPU, RFSB-509 runs at 13.62 cycles/byte: faster than SHA-256, faster than 6 of the 14 second-round SHA-3 candidates, and faster than 2 of the 5 SHA-3 finalists.

We cryptanalyse a matrix-based key transport protocol due to Baumslag, Camps, Fine, Rosenberger and Xu from 2006. We also cryptanalyse two recently proposed matrix-based key agreement protocols, due to Habeeb, Kahrobaei and Shpilrain, and due to Romanczuk and Ustimenko.

In this paper, we summarize the recent related-key differential and boomerang attacks on AES by Biryukov et al. and present a framework for protection against these attacks. Then we study an alternative AES key schedule proposed by May et al. at ACISP 2002 as a possible candidate to protect against these related key attacks. We find that there exist equivalent keys for this key schedule and in response, we propose an improvement to overcome this weakness. We proceed to prove, using our framework, that our improved May et al.'s key schedule is secure against related-key differential and boomerang attacks. Since May et al.'s key schedule is not on-the-fly (which is a requirement for some hardware implementations), we propose an on-the-fly AES key schedule that is resistant against related-key differential and boomerang attacks.

There are two active and independent lines of research that aim at quantifying the amount of information that is disclosed by computing on confidential data. Each line of research has developed its own notion of confidentiality: on the one hand, differential privacy is the emerging consensus guarantee used for privacy-preserving data analysis. On the other hand, information-theoretic notions of leakage are used for characterizing the confidentiality properties of programs in language-based settings. The purpose of this article is to establish formal connections between both notions of confidentiality, and to compare them in terms of the security guarantees they deliver. We obtain the following results. First, we establish upper bounds for the leakage of every $\eps$-differentially private mechanism in terms of~$\eps$ and the size of the mechanism's input domain. We achieve this by identifying and leveraging a connection to coding theory. Second, we construct a class of $\eps$-differentially private channels whose leakage grows with the size of their input domains. Using these channels, we show that there cannot be domain-size-independent bounds for the leakage of all $\eps$-differentially private mechanisms. Moreover, we perform an empirical evaluation that shows that the leakage of these channels almost matches our theoretical upper bounds, demonstrating the accuracy of these bounds. Finally, we show that the question of providing optimal upper bounds for the leakage of $\eps$-differentially private mechanisms in terms of rational functions of $\eps$ is in fact decidable.

We use ideas from game theory to transform two families of authentication protocols so that even an intruder attacks a protocol, its payoff will still be lower than when it does not. This is particularly useful in resisting or discouraging a powerful and rational intruder (as present in military applications) who makes many attempts to break a protocol because (1) even the intruder fails, a denial of service attack is still mounted successfully, and (2) in a password-based protocol, the chance of a successful attack increases quite significantly as more and more attempts are launched to guess the password.

Bit-decomposition is an important primitive in 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, we will be able to construct constant-rounds protocols for various MPC problems, such as \emph{equality test}, \emph{comparison}, \emph{public modulo reduction} and \emph{private exponentiation}, which are four main applications of bit-decomposition. However, when considering perfect security, bit-decomposition does \emph{not} have a linear communication complexity. Thus any protocols involving bit-decomposition inherit this inefficiency, i.e. the communication complexity is non-linear. Constructing protocols for MPC problems without relying on bit-decomposition is a meaningful work because this may provide us with perfect secure protocols with linear communication complexity. It is already proved that \emph{equality test}, \emph{comparison} and \emph{public modulo reduction} can be solved without involving bit-decomposition and the communication complexity can be reduced to linear. However, it remains an open problem whether \emph{private exponentiation} could be done without relying on bit-decomposition. In this paper, maybe somewhat surprisingly, we show that it can. That is to say, we construct a \emph{constant-rounds, linear, perfect secure} protocol for private exponentiation \emph{without} relying on bit-decomposition though it seems essential to this problem. Compared with the previous solution for this problem (with perfect security), our protocol has a lower round complexity and a much lower communication complexity. In a recent work, Ning and Xu proposed a generalization of bit-decomposition which can, given a sharing of secret $x$ and an integer $m \ge 2$, compute the sharings (or bitwise sharings) of the base-$m$ digits of $x$. They also proposed a linear protocol for public modulo reduction as a simplification of their generalization. In this paper, we show that their generalization can be further generalized. More importantly, as a simplification of our further generalization, we propose a public modulo reduction protocol which is more efficient than theirs. Specifically, the round complexity of our (modulo reduction) protocol is the same with theirs, but the communication complexity can be considerably lower.

We consider the problem of rational secret sharing introduced by Halpern and Teague \cite{HT04}, where the players involved in secret sharing play only if it is to their advantage. This can be characterized in the form of preferences. Players would prefer to get the secret than to not get it and secondly with lesser preference, they would like as few other players to get the secret as possible. Several positive results have already been published to efficiently solve the problem of rational secret sharing. However, only a handful of papers have touched upon the use of an asynchronous broadcast channel, and in those papers, either the protocol involved cryptographic primitives \cite{FKN10} or else the protocol required the dealer to be interactively involved \cite{MSR08a}. However, \cite{OPRV09} did handle such a case through the use of an honest minority of players, but in their paper, they had placed a restriction on the number of honest players that could take part in relation to the total number number of players active in the protocol. In our paper, we propose an $m$-out-of-$n$ rational secret sharing scheme which can function over an asynchronous broadcast channel without the use of cryptographic primitives and with a non-interactive dealer. This is possible because our scheme uses a small number, $k+1$, of honest players. The protocol is resilient to coalitions of size up to $k$ and furthermore it is $\varepsilon$-resilient to coalitions of size up to $m-1$. The protocol will have a strict Nash equilibrium with probability $Pr(\frac{k+1}{n})$ and an $\varepsilon$-Nash equilibrium with probability $Pr(\frac{n-k-1}{n})$. Furthermore, our protocol is immune to backward induction. Later on in the paper, we extend our results to include malicious players as well. We also show that our protocol handles the possibility of a player deviating in order to force another player to get a wrong value. This type of deviation was discussed and handled by Asharov and Lindell \cite{AL09} by increasing the number of rounds. However, our protocol handles this in what we believe to be a more time efficient manner.

Given a prime $p$, an elliptic curve $\mathcal{E}/\mathbb{F}_p$ over the finite field $\mathbb{F}_p$ of $p$ elements and a binary linear recurrence sequence $\(u(n)\)_{n =1}^\infty$ of order~$r$, we study the distribution of the sequence of points $$ \sum_{j=0}^{r-1} u(n+j)P_j, \qquad n =1,\ldots, N, $$ on average over all possible choices of $\mathbb{F}_p$-rational points $P_1,\ldots, P_r$ on $\mathcal{E}$. For a sufficiently large $N$ we improve and generalise a previous result in this direction due to E.~El~Mahassni.