Randomized hash-lock protocols for Radio Frequency IDentification (RFID) tags offer forward untraceability, but incur heavy search on the server. Key trees have been proposed as a way to reduce search times, but because partial keys in such trees are shared, key compromise affects several tags. Buttyän et al. have quantified the resulting loss of anonymity in the system, and proposed specific tree properties in an attempt to minimize this loss. We will further improve upon these results, and provide a proof of optimality. Finally, our proposals are compared to existing results by means of simulation.

We propose a new non-interactive (perfect) zero-knowledge (NIZK) shuffle argument that, when compared the only previously known efficient NIZK shuffle argument by Groth and Lu, has a small constant factor times smaller computation and communication, and is based on more standard computational assumptions. Differently from Groth and Lu who only prove the co-soundness of their argument under purely computational assumptions, we prove computational soundness under a necessary knowledge assumption. We also present a general transformation that results in a shuffle argument that has a quadratically smaller common reference string (CRS) and a small constant factor times times longer argument than the original shuffle. Our main technical result is a ``$1$-sparsity'' argument that has linear CRS length and prover's communication. This should be compared to the basic arguments of Groth (Asiacrypt 2010) and Lipmaa (TCC 2012), where the prover's computational complexity is quadratic. This gives a new insight to the NIZK arguments of Groth and Lipmaa, and we hope that the $1$-sparsity argument (and possible related future basic arguments) can be used to build NIZK arguments for other interesting languages.

The design of rational cryptographic protocols is a recently created research area at the intersection of cryptography and game theory. At TCC'10, Fuchsbauer \emph{et al.} introduced two equilibrium notions (computational version of strict Nash equilibrium and stability with respect to trembles) offering a computational relaxation of traditional game theory equilibria. Using trapdoor permutations, they constructed a rational $t$-out-of $n$ sharing technique satisfying these new security models. Their construction only requires standard communication networks but the share bitsize is $2 n |s| + O(k)$ for security against a single deviation and raises to $(n-t+1)\cdot (2n|s|+O(k))$ to achieve $(t-1)$-resilience where $k$ is a security parameter. In this paper, we propose a new protocol for rational $t$-out-of $n$ secret sharing scheme based on the Chinese reminder theorem. Under some computational assumptions related to the discrete logarithm problem and RSA, this construction leads to a $(t-1)$-resilient computational strict Nash equilibrium that is stable with respect to trembles with share bitsize $O(k)$. Our protocol does not rely on simultaneous channel. Instead, it only requires synchronous broadcast channel and synchronous pairwise private channels.

This paper is a short summary of our real-world side-channel analysis of the bitstream encryption mechanism provided by Xilinx FPGAs. This work covers our results analyzing the Virtex 4, Virtex 5, and Spartan 6 family showing that the encryption mechanism can be completely broken with moderate effort. The presented results provide an overview of a practical real-world analysis and should help practitioners to judge the necessity to implement side-channel countermeasures. We demonstrate sophisticated attacks on off-the-shelf FPGAs that go far beyond schoolbook attacks on 8-bit AES S-boxes. We were able to perform the key extraction by using only the measurements of a single power-up. Access to the key allows cloning and manipulating a design, which has been encrypted to protect the intellectual property and to prevent fraud. As a consequence, the target product faces serious threats like IP theft and more advanced attacks such as reverse engineering or the introduction of hardware Trojans. To the best of our knowledge, this is the first successful attack against the bitstream encryption of Xilinx Virtex 4, Virtex 5, and Spartan 6 reported in the open literature.

Over the last two decades FPGAs have become central components for many advanced digital systems, e.g., video signal processing, network routers, data acquisition and military systems. In order to protect the intellectual property and to prevent fraud, e.g., by cloning an FPGA or manipulating its content, many current FPGAs employ a bitstream encryption feature. We develop a successful attack on the bitstream encryption engine integrated in the widespread Virtex-II Pro FPGAs from Xilinx, using side-channel analysis. After measuring the power consumption of a single power-up of the device and a modest amount of off-line computation, we are able to recover all three different keys used by its triple DES module. Our method allows extracting secret keys from any real-world device where the bitstream encryption feature of Virtex-II Pro is enabled. As a consequence, the target product can be cloned and manipulated at will of the attacker. Also, more advanced attacks such as reverse engineering or the introduction of hardware Trojans become potential threats. As part of the side-channel attack, we were able to deduce certain internals of the hardware encryption engine. To our knowledge, this is the first attack against the bitstream encryption of a commercial FPGA reported in the open literature.

In this thesis, we build on Boneh and Hamburg's work on generalized identity-based encryption and spatial encryption. GIBE is a model that covers many of the generalizations of identity-based cryptography that have appeared in the past decade. It is simple and flexible, and can be tuned to different attack models such as selective security. Spatial encryption is an encryption system within the GIBE model. It is designed as a toolbox from which other encryption systems can be built, using linear algebra as an encoding method. It is based on the work of Boneh, Boyen and Goh, and generalizes hierarchical IBE as well as the hierarchical inner-product encryption of Okamoto and Takashima. Here we show several new results related to spatial encryption. We show how to build adaptively secure spatial systems (under a compact but nonstandard assumption) using Lewko and Waters' dual-system encryption. In doing this, we also show how to adapt Lewko and Waters' result to a prime-order setting without sacrificing constant-size ciphertexts. We also show new embeddings of other cryptosystems into spatial encryption. Beyond spatial encryption, we propose a variant called "doubly-spatial encryption", which generalizes both spatial encryption and Attrapadung and Libert's "negated spatial encryption". This generalization adds more flexibility, including more flexible revocation systems and potential improvements in policy language. Unfortunately, we were only able to prove selective security for doubly-spatial encryption, and its ciphertext is no longer constant-size.

RSA-CRT fault attacks have been an active research area since their discovery by Boneh, DeMillo and Lipton in 1997. We present alternative key-recovery attacks on RSA-CRT signatures: instead of targeting one of the sub-exponentiations in RSA-CRT, we inject faults into the public modulus before CRT interpolation, which makes a number of countermeasures against Boneh et al.'s attack ineffective. Our attacks are based on orthogonal lattice techniques and are very efficient in practice: depending on the fault model, between 5 to 45 faults suffice to recover the RSA factorization within a few seconds. Our simplest attack requires that the adversary knows the faulty moduli, but more sophisticated variants work even if the moduli are unknown, under reasonable fault models. All our attacks have been fully validated experimentally with fault-injection laser techniques.

Cryptanalytic time memory tradeoff algorithms are tools for quickly inverting one-way functions and many consider the rainbow table method to be the most efficient tradeoff algorithm. However, it was recently announced, mostly based on experiments, that the parallelization of the perfect distinguished point tradeoff algorithm brings about an algorithm that is 50\% more efficient than the perfect rainbow table method. Motivated by this claim, while noting that the massive pre-computation associated with any tradeoff algorithm makes the non-perfect forms of tradeoff algorithms more practical, we provide an accurate theoretic analysis of the parallel version of the non-perfect distinguished point tradeoff algorithm. Performance differences between different tradeoff algorithms are usually not very large, but even these small differences can be crucial in practice. So we take care not to ignore the side effects of false alarms in providing an online time complexity analysis of the parallel distinguished point tradeoff algorithm. Our complexity results are used to compare the parallel non-perfect distinguished point tradeoff against the non-perfect rainbow table method. The two algorithms are compared under identical success rate requirements and the pre-computation efforts are also taken into account. Contrary to our anticipation, we find that the rainbow table method is superior in typical situations, even though the parallelization did have a positive effect on the efficiency of the distinguished point tradeoff algorithm.

Each member of a team consisting of $n$ person has a secret. The $k$ out of $n$ simultaneous threshold secret sharing requires that any group of $k$ members should be able to recover the secret of the other $n-k$ members, while any group of $k-1$ or less members should have no information on the secret of other team members. We show that when all secrets are independent and have size $s$ then each team member must receive a share of size at least $(n-k)s$, and we present a scheme which achieves this bound. This result shows a significant saving over $n$ independent applications of the $k$ out of $n-1$ threshold schemes which assigns shares of size $(n-1)s$ to each team member independently of $k$.

Grand Cru, a candidate cipher algorithm of NESSIE project, is based on the strategy of multiple layered security and derived from AES-128. This algorithm was not selected for second phase evaluation of NESSIE project due to implementation and processing cost. In this paper we present relatively a fast implementation of the cipher using Texas Instrument’s DSP C64x+.

Secure two-party computation protocol allows two players, Alice with secret input $x$ and Bob with secret input $y$, to jointly execute an arbitrary program $\pi(x,y)$ such that only the output of the program is revealed to one or both players. In the two player setting, under computational assumptions most approaches require to first ``unroll'' $\pi$ into a circuit, and then execute this circuit in a private manner. Without unrolling the circuit, an alternative method was proposed by Ostrovsky and Shoup (in STOC 1997) with both players simulating the CPU of an oblivious RAM machine using ``off-the-shelf'' secure two-party computation to perform CPU simulation with atomic instructions implemented by circuits and relying on one of the players to implement encrypted memory. The simulation of the CPU must be done through circuit-based secure two-party computation, thus CPU ``memory'' in the Oblivious RAM simulation must be minimized, as otherwise it impacts simulation of each step of the computation. Luckily, there are multiple Oblivious RAM solutions that require $O(1)$ CPU memory in the security parameter. The Ostrovsky-Shoup compiler suffers from two drawbacks: -The best running time of Oblivious RAM simulation with $O(1)$ memory is still prohibitive and requires $O(\log^2t/\log\log t)$ overhead for running programs of length $t$ by Kushilevitz, Lu, and Ostrovsky (in SODA 2012). -The most problematic part of this approach is that all Oblivious RAM simulations, starting with Goldreich and Ostrovsky (in JACM 1996) require ``Oblivious Sorting'' that introduce a huge constant into Oblivious RAM simulation that essentially kills all practicality. In this paper, we observe that in the secure two-party computation, Alice and Bob can simulate two non-communicating databases. We show how to extend the Ostrovsky-Shoup compiler so that two non-communicating servers can eliminate all the drawbacks stated above. More specifically, we design a new Oblivious RAM protocol where a client interacts with two non-communicating servers, that supports $n$ reads and writes, and requires $O(n)$ memory for the servers, $O(1)$ memory for the client, and $O(\log n)$ amortized read/write overhead for data access. The constants in the big-O notation are tiny, and we show that the storage and data access overhead of our solution concretely compares favorably to the state-of-the-art single-server schemes. As alluded to above, our protocol enjoys an important feature from a practical perspective as well. At the heart of almost all previous single-server Oblivious RAM solutions, a crucial but inefficient process known as oblivious sorting was required. In our two-server model, we describe a novel technique to bypass oblivious sorting, and show how this can be carefully blended with existing techniques to attain a more practical Oblivious RAM protocol in comparison to all prior work. This new protocol leads to a novel application in the realm of secure two-party RAM program computation. We show that our multi-server Oblivious RAM construction can be composed with an extended version of the Ostrovsky-Shoup compiler to obtain a new method for secure two-party RAM computation with lower overhead than (implicitly) existing constructions by a factor of $O(\log n/\log\log n)$ of Gordon et al.

This article concerns itself with the triangular permutation group, induced by triangular polynomial maps over $\F_p$, which is a $p$-sylow subgroup of $\perm(\F_p^n)$. The aim of this article is twofold: on the one hand, we give an alternative to $\F_p$-actions on $\F_p^n$, namely $\Z$-actions on $\F_p^n$ and how to describe them as what we call ``$\Z$-flows''. On the other hand, we describe how the triangular permutation group can be used in applications, in particular we give a cryptographic application for session-key generation. The described system has a certain degree of information theoretic security. We compute its efficiency and storage size. To make this work, we give explicit criteria for a triangular permutation map to have only one orbit, which we call ``maximal orbit maps''. We describe the conjugacy classes of maximal orbit maps, and show how one can conjugate them even further to the map $z\lp z+1$ on $\Z/p^n\Z$.

We aim at constructing adaptive oblivious transfer protocols, enjoying fully simulatable security, from various well-known assumptions such as DDH, $d$-Linear, QR, DCR, and LWE. To this end, we present two generic constructions of adaptive OT, one of which utilizes verifiable shuffles together with threshold decryption schemes, while the other uses permutation networks together with what we call {\em loosely-homomorphic} key encapsulation schemes. We then show that specific choices of the building blocks lead to concrete adaptive OT protocols with fully simulatable security in the standard model under the targeted assumptions. Our generic methods can be extended to build universally composable (UC) secure, and leakage-resilient OT protocols.

Recently, many researchers have proposed RFID authentication protocols. These protocols are mainly consists of two types: symmetric key based and asymmetric key based. The symmetric key based systems usually have some weaknesses such as suffering brute force, de-synchronization, impersonation, and tracing attacks. In addition, the asymmetric key based systems usually suffer from impersonation, man-in-the-middle, physical, and tracing attacks. To get rid of those weaknesses and reduce the system workload, we adopt elliptic curve cryptosystem (ECC) to construct an asymmetric key based RFID authentication system. Our scheme needs only two passes and can resist various kinds of attacks. It not only outperforms the other RFID schemes having the same security level but also is the most efficient.

A theme of recent side-channel research has been the quest for distinguishers which remain effective even when few assumptions can be made about the underlying distribution of the measured leakage traces. The Kolmogorov-Smirnov (KS) test is a well known non-parametric method for distinguishing between distributions, and, as such, a perfect candidate and an interesting competitor to the (already much discussed) mutual information (MI) based attacks. However, the side-channel distinguisher based on the KS test statistic has received only cursory evaluation so far, which is the gap we narrow here. This contribution explores the effectiveness and effciency of Kolmogorov-Smirnov analysis (KSA), and compares it with mutual information analysis (MIA) in a number of relevant scenarios ranging from optimistic first-order DPA to multivariate settings. We show that KSA shares certain ‘generic’ capabilities in common with MIA whilst being more robust to noise than MIA in univariate settings. This has the practical implication that designers should consider results of KSA to determine the resilience of their designs against univariate power analysis attacks.

In this paper, we give a generalization of Lucas addition chains, where subtraction is allowed. We call them ''Lucas addition-subtraction chain''. We also show that this new method gives minimal addition-subtraction chains for infinitely many integers. This new method will also be used to prove that Lucas addition chains are optimal for many integers. Moreover, we show that Lucas addition chains give minimal addition chains for all integers of Hamming weight $3$, like the \emph{binary method}. Finally, we give a theorem to get short (and many times minimal) Lucas addition-subtraction chains.

Let r, B and w be positive integers. Let C be a linear code of length Bw and subspace of Fr . The k-regular-decoding problem is to find 2 a nonzero codeword consisting of w length-B blocks with Hamming weight k. This problem was mainly studied after 2002. Not being able to solve this problem is critical for cryptography as it gives a fast attack against FSB, SWIFFT and learning parity with noise. In this paper, the classical methods are used in the same algorithm and improved.

Verifier-Local Revocation (VLR) group signatures, introduced by Boneh and Shacham in 2004, are a particular case of dynamic group signature schemes where the revocation process does not influence the activity of the signers. The verifiers use a Revocation List to check if the signers are revoked. In all known schemes, checking a signature requires a computational time linear in the number of revoked members. Usually, it requires one pairing per revoked user. Recently, Chen and Li proposed a scheme where Revocation Check uses exponentiations instead of pairings. In this paper, we first propose a correction of their scheme to enable a full proof of the traceability property. Then our main contribution is to extend this tweaked scheme to ensure Backward Unlinkability. This important property prevents the loss of anonymity of past signatures when a user is revoked. We succeed in achieving this consequent improvement with a constant additional cost only. We thus obtain the scheme with the most efficient Revocation Check among VLR schemes enabling Backward Unlinkability.

An important parameter in a secret sharing scheme is the number of minimal qualified sets. Given this number, the universal access structure is the richest possible structure, namely the one in which there are one or more participants in every possible Boolean combination of the minimal qualified sets. Every access structure is a substructure of the universal structure for the same number of minimal qualified subsets, thus universal access structures have the highest complexity given the number of minimal qualified sets. We show that the complexity of the universal structure with $n$ minimal qualified sets is between $n/\log_2n$ and $n/2.7182\dots$ asymptotically.

These notes present new results to reestablish the differential resistance of MD6. In this paper we introduce a classification system of differential weight patterns that allows us to extend previous analysis to prove that MD6 is resistant to differential cryptanalysis. Our analysis allows us to more than double the security margin of MD6 against differential attacks.

Lisoněk recently reformulated the characterization of Charpin and Gong of a large class of hyperbent functions in terms of cardinalities of curves. In this note, we show that such a reformulation can be naturally extended to a distinct family of functions proposed by Mesnager. Doing so, a polynomial time and space test is obtained to test the hyperbentness of functions in this family. Finally we show how this reformulation can be transformed to obtain a more efficient test.

Signcryption is a cryptographic primitive which performs encryption and signature in a single logical step with the cost lower than signature-then-encryption approach.. In this paper we gave attacks on confidentiality and unforgeability of two identity based signcryption schemes without random oracles. Further we proposed an improved identity based signcryption scheme without random oracles. We also proposed an identity based public verifiable signcryption scheme with third party verification without random oracles.

At SAC 2009, Misoczki and Barreto proposed a new class of codes, which have parity-check matrices that are quasi-dyadic. A special subclass of these codes were shown to coincide with Goppa codes and those were recommended for cryptosystems based on error-correcting codes. Quasi-dyadic codes have both very compact representations and allow for efficient processing, resulting in fast cryptosystems with small key sizes. In this paper, we generalize these results and introduce quasi-monoidic codes, which retain all desirable properties of quasi-dyadic codes. We show that, as before, a subclass of our codes contains only Goppa codes or, for a slightly bigger subclass, only Generalized Srivastava codes. Unlike before, we also capture codes over fields of odd characteristic. These include wild Goppa codes that were proposed at SAC 2010 by Bernstein, Lange, and Peters for their exceptional error-correction capabilities. We show how to instantiate standard code-based encryption and signature schemes with our codes and give some preliminary parameters.

Rational secret sharing was proposed by Halpern and Teague in STOC'04. The authors show that, in a setting with rational players, secret sharing and multiparty computation are only possible if the actual secret reconstruction round remains unknown to the players. All the subsequent works use a similar approach with different assumptions. We change the direction by bridging cryptography, game theory, and reputation systems, and propose a social model for repeated rational secret sharing. We provide a novel scheme, named "socio-rational secret sharing", in which players are invited to each game based on their reputations in the community. The players run secret sharing protocols while founding and sustaining a public trust network. As a result, new concepts such as a rational foresighted player, social game, and social Nash equilibrium are introduced. To motivate our approach, consider a repeated secret sharing game such as secure auctions, where the auctioneers receive sealed-bids from the bidders to compute the auction outcome without revealing the losing bids. If we assume each party has a reputation value, we can then penalize (or reward) the players who are selfish (or unselfish) from game to game. We show that this social reinforcement rationally stimulates the players to be cooperative.

We consider the question of how to store a value secretly on devices that continually leak information about their internal state to an external attacker. If the secret value is stored on a single device from which it is efficiently retrievable, and the attacker can leak even a single predicate of the internal state of that device, then she may learn some information about the secret value itself. Therefore, we consider a setting where the secret value is shared between multiple devices (or multiple components of a single device), each of which continually leaks arbitrary adaptively chosen predicates its individual state. Since leakage is continual, each device must also continually update its state so that an attacker cannot just leak it entirely one bit at a time. In our model, the devices update their state individually and asynchronously, without any communication between them. The update process is necessarily randomized, and its randomness can leak as well. As our main result, we construct a sharing scheme for two devices, where a constant fraction of the internal state of each device can leak in between and during updates. Our scheme has the structure of a public-key encryption, where one share is a secret key and the other is a ciphertext. As a contribution of independent interest, we also get public-key encryption in the continual leakage model, introduced by Brakerski et al. and Dodis et al. (FOCS '10). This scheme tolerates continual leakage on the secret key and the updates, and simplifies the recent construction of Lewko, Lewko and Waters (STOC '11). For our main result, we show how to update the ciphertexts of the encryption scheme so that the message remains hidden even if an attacker interleaves leakage on secret key and ciphertext shares. The security of our scheme is based on the linear assumption in prime-order bilinear groups. We also provide an extension to general access structures realizable by linear secret sharing schemes across many devices. The main advantage of this extension is that the state of some devices can be compromised entirely, while that of the all remaining devices is susceptible to continual leakage. Lastly, we show impossibility of information theoretic sharing schemes in our model, where continually leaky devices update their state individually.

This paper shows that a $390 mass-market quad-core 2.4GHz Intel Westmere (Xeon E5620) CPU can create 109000 signatures per second and verify 71000 signatures per second on an elliptic curve at a 2^128 security level. Public keys are 32 bytes, and signatures are 64 bytes. These performance figures include strong defenses against software side-channel attacks: there is no data flow from secret keys to array indices, and there is no data flow from secret keys to branch conditions.

Generic decoding of linear codes is the best known attack against most code-based cryptosystems. Understanding and measuring the complexity of the best decoding technique is thus necessary to select secure parameters. We consider here the possibility that an attacker has access to many cryptograms and is satisfied by decrypting (i.e.\ decoding) only one of them. We show that, in many cases of interest in cryptology, a variant of Stern's collision decoding can be adapted to gain a factor almost $\sqrt{N}$ when $N$ instances are given. If the attacker has access to an unlimited number of instances, we show that the attack complexity is significantly lower, in fact raised by a power slightly larger than $2/3$. Finally we give indications on how to counter those attacks.

In this paper, we present a new combinatorial conjecture about binary strings. Based on the new conjecture, two classes of Boolean functions of $2k$ variables with optimal algebraic immunity are proposed, where $k\ge 2$. The first class contains unbalanced functions having high algebraic degree and nonlinearity. The functions in the second one are balanced and have maximal algebraic degree and high nonlinearity. It is checked that, at least for small numbers of variables, both classes of functions have a good behavior against fast algebraic attacks. Compared with the known Boolean functions resisting algebraic attacks and fast algebraic attacks, the two classes of functions possess the highest lower bounds on nonlinearity. These bounds are however not enough for ensuring a sufficient nonlinearity for allowing resistance to the fast correlation attack. Nevertheless, as for previously found functions with the same features, there is a gap between the bound that we can prove and the actual values computed for small numbers of variables. Moreover, these values are very good and much better than for the previously found functions having all the necessary features for being used in the filter model of pseudo-random generators.

Recently, Yoon et al. proposed an efficient biometrics-based multi-server authentication with key agreement scheme for smart cards on elliptic curve cryptosystem (ECC) for multi-server communication environments [E.-J. Yoon, K.-Y. Yoo(2011) Robust biometrics-based multi-server authentication with key agreement scheme for smart cards on elliptic curve cryptosystem, Journal of Supercomputing, DOI: 10.1007/s11227-010-0512-1]. They claimed their scheme could withstand various attacks. In the letter, we will show Yoon et al.’s scheme is vulnerable to the privileged insider attack, the masquerade attack and the smart cart lost attack.

Kloosterman sums have recently become the focus of much research, most notably due to their applications in cryptography and their relations to coding theory. Very recently Mesnager has showed that the value $4$ of binary Kloosterman sums gives rise to several infinite classes of bent functions, hyper-bent functions and semi-bent functions in even dimension. In this paper we analyze the different strategies used to find zeros of binary Kloosterman sums to develop and implement an algorithm to find the value $4$ of such sums. We then present experimental results showing that the value $4$ of binary Kloosterman sums gives rise to bent functions for small dimensions, a case with no mathematical solution so far.

Proofs of Retrievability ({\POR}) is a cryptographic method for remotely auditing the integrity of files stored in the cloud, without keeping a copy of the original files in local storage. In a {\POR} scheme, a user Alice backups her data file together with some authentication data to a potentially dishonest cloud storage server Bob. Later, Alice can periodically and remotely verify the integrity of her data stored with Bob using the authentication data, without retrieving back the data file during a verification. Besides security, performances in communication, storage overhead and computaton are major considerations. Shacham and Waters~\cite{CompactPOR} gave a fast scheme with $\mathcal{O}(s)$ communication bits and a factor of $1/s$ file size expansion. Although Ateniese~\emph{et al.}~\cite{PDP} achieves constant communication requirement with the same $1/s$ storage overhead, it requires intensive computation in the setup and verification. In this paper, we incorporate a recent construction of constant size polynomial commitment scheme into Shacham and Waters~\cite{CompactPOR} scheme. The resulting scheme requires constant communication bits (particularly, 720 bits if elliptic curve is used or 3312 bits if a modulo group is used) per verification and a factor of $1/s$ file size expansion, and its computation in the setup and verification is significantly reduced compared to Ateniese~\emph{et al.}~\cite{PDP}. Essentially, Ateniese~\emph{et al.}~\cite{PDP} requires one group multiplication per each bit of the data file in the setup, while the proposed scheme requires one group multiplication per each chunk of data bits (160 bits per chunk if elliptic curve is used or 1024 bits per chunk if modulo group is used). The experiment results show that our proposed scheme is indeed efficient and practical. Our security proof is based on Strong Diffie-Hellman Assumption.

Recently, Baek et al. proposed a stateful identity based encryption scheme with compact ciphertext and commented that the security of the scheme can be reduced to the Computational Bilinear Diffie Hellman (CBDH) problem. In this paper, we formally prove that the security of the stateful identity based encryption scheme by Baek et al. cannot be reduced to the CBDH problem. In fact, we show that the challenger will confront the Y-Computational problem while providing the decryption oracle access to the adversary. We provide the exact and formal security proof for the scheme, assuming the hardness of the Gap Bilinear Diffie Hellman (GBDH) problem. We also propose two new stateful public key encryption scheme with ciphertext verifiability. Our schemes offer more compact ciphertext when compared to all existing stateful public key encryption schemes with ciphertext verifiability. We have proved all the schemes in the random oracle model.

The concept of an aggregate signcryption scheme was first introduced in 2009 by Selvi S.S.D. et. al. in the identity-based setting. The aggregation process of these schemes reduces the amount of exchanged information and is particularly useful in low-bandwidth communication networks and computationally-restricted environments. In this paper, we define a suitable security model for certificateless aggregate signcryption schemes and propose an example which we prove is secure in the random oracle model under the gap Bilinear Diffie-Hellman and computational Diffie-Helman intractability assumptions.

We exhibit a system for improving the quality of user-derived keying material on touch-screen devices. We allow a device to recover previously generated, highly entropic data suitable for use as (part of) a strong secret key from a user’s act of identifying to the device. Our system uses visual cryptography [22], using no additional electronics and no memorization on the part of the user. Instead, we require the use of a transparency overlaid on the touch-screen. Our scheme is similar to the identification scheme of [23] but tailored for constrained, touch-screen displays.

FCSRs have been proposed as an alternative to LFSRs for the design of stream ciphers. In 2009, a new "ring" representation of FCSRs was presented. This new representation preserves the statistical properties and circumvents the weaknesses of the Fibonacci and the Galois FCSRs. Moreover an extension of the ring FCSRs called ternary FCSRs has been proposed. They are suitable for hardware and software implementations of FCSRs. In this paper, we show a method of constructing a ternary FCSR with a given connection integer for hardware implementation. The construction is simple and convenient. And the ternary FCSRs we get are able to meet the hardware criteria.

We propose a generalization of the learning parity with noise (LPN) and learning with errors (LWE) problems to an abstract class of group-theoretic learning problems that we term _learning homomorphisms from noise_ (LHN). This class of problems contains LPN and LWE as special cases, but is much more general. It allows, for example, instantiations based on non-abelian groups, resulting in a new avenue for the application of combinatorial group theory to the development of cryptographic primitives. We then study a particular instantiation using relatively free groups and construct a symmetric cryptosystem based upon it.

Kabastianskii, Krouk and Smeets proposed in 1997 a digital signature scheme based on a couple of random error-correcting codes. A variation of this scheme was proposed recently and was proved to be EUF-1CMA secure in the random oracle model. In this paper we investigate the security of these schemes and suggest a simple attack based on (essentially) Stern’s algorithm for finding low weight codewords. It efficiently recovers the private key of all schemes of this type existing in the literature. This is basically due to the fact that we can define a code from the available public data with unusual properties: it has many codewords whose support is concentrated in a rather small subset. In such a case, Stern’s algorithm performs much better and we provide a theoretical analysis substantiating this claim. Our analysis actually shows that the insecurity of the proposed parameters is related to the fact that the rates of the couple of random codes used in the scheme were chosen to be too close. This does not compromise the security of the whole KKS scheme. It just points out that the region of weak parameters is really much larger than previously thought.

Over the years, various security notions have been proposed in order to cope with a wide range of security scenarios. Recently, the study of security notions has been extended towards comparing cryptographic definitions of secure implementation with game-theoretic definitions of universal implementation of a trusted mediator. In this work we go a step further: We define the notion of game universal implementation and we show it is equivalent to weak stand-alone security. Thus, we are able to answer positively the open question from [Halpern&Pass2010] regarding the existence of game-theoretic definitions that are equivalent to cryptographic security notions for which the ideal world simulator does not depend on both the distinguisher and the input distribution. Moreover, we investigate the propagation of the weak stand-alone security notion through the existing security hierarchy, from stand-alone to universal composability. Our main achievement in this direction is a separation result between two variants of the UC security definition: 1-bit specialized simulator UC security and specialized simulator UC security. This solves an open question from [Lindell03] and comes in contrast with the well known equivalence result between 1-bit UC security and UC security. We also show that weak security under 1-bounded concurrent general composition is equivalent to 1-bit specialized simulator UC security. As a consequence, we obtain that the notion of weak stand-alone security and the notion of stand-alone security are not equivalent.

We present a coprocessor design for fast arithmetic over large numbers of cryptographic sizes. Our design provides a efficient way to prevent side channel analysis as well as fault analysis targeting modular arithmetic with large prime or composite numbers. These two countermeasure are then suitable both for Elliptic Curve Cryptography over prime fields or RSA using CRT or not. To do so, we use the residue number system (RNS) in an efficient manner to protect from leakage and fault, while keeping its ability to fast execute modular arithmetic with large numbers. We illustrate our countermeasure with a fully protected RSA-CRT implementation using our architecture, and show that it is possible to execute a secure 1024 bit RSA-CRT in less than 0:7 ms on a FPGA.

A new signature system of multivariate public key cryptosys- tem is proposed. The new system, Hidden Pair of Bijection (HPB), is the advanced version of the Complementary STS system. This system real- ized both high security and quick signing. Experiments showed that the cryptanalysis of HPB by Gröbner bases has no less complexity than the random polynomial systems. It is secure against other way of cryptanalysis effective for Complementary STS. On the other hand, since it is based on bijections, signatures exist for any message, unlike other cryptosystems based on non-bijections such as HFE or Unbalanced Oil and Vinegar.

In CRYPTO 1997, Canetti \etal put forward the intruiging notion of \emph{deniable encryption}, which (informally) allows a sender and/or receiver, having already performed some encrypted communication, to produce `fake' (but legitimate-looking) random coins that open the ciphertext to another message. Deniability is a powerful notion for both practice and theory: apart from its inherent utility for resisting coercion, a deniable scheme is also noncommitting (a useful property in constructing adaptively secure protocols) and secure under selective-opening attacks on whichever parties can equivocate. To date, however, known constructions have achieved only limited forms of deniability, requiring at least one party to withhold its randomness, and in some cases using an interactive protocol or external parties. In this work we construct \emph{bi-deniable} public-key cryptosystems, in which both the sender and receiver can simultaneously equivocate; we stress that the schemes are noninteractive and involve no third parties. One of our systems is based generically on ``simulatable encryption'' as defined by Damgård and Nielsen (CRYPTO 2000), while the other is lattice-based and builds upon the results of Gentry, Peikert and Vaikuntanathan (STOC 2008) with techniques that may be of independent interest. Both schemes work in the so-called ``multi-distributional'' model, in which the parties run alternative key-generation and encryption algorithms for equivocable communication, but claim under coercion to have run the prescribed algorithms. Although multi-distributional deniability has not attracted much attention, we argue that it is meaningful and useful because it provides credible coercion resistance in certain settings, and suffices for all of the related properties mentioned above.

We construct a simple authentication protocol whose security is based solely on the problem of Learning Parity with Noise (LPN) which is secure against Man-in-the-Middle attacks. Our protocol is suitable for RFID devices, whose limited circuit size and power constraints rule out the use of more heavyweight operations such as modular exponentiation. The protocol is extremely simple: both parties compute a noisy bilinear function of their inputs. The proof, however, is quite technical, and we believe that some of our technical tools may be of independent interest.

Faults occurred during the operations in a hardware device cause many problems such as performance deterioration, unreliable output, etc. If a fault occurs in a cryptographic hardware device, the effect can be even serious because an adversary may exploit it to find the secret information stored in the device. More precisely, the adversary can find the key of a block cipher using differential information between correct and faulty ciphertexts obtained by inducing faults during the computation of ciphertexts. This kind of attack is called \emph{Differential Fault Analysis} (DFA). Among many ciphers \emph{Advanced Encryption Standard} (AES) has been the main target of DFA due to its popularity. AES is widely used in different platforms and systems including Intel and AMD microprocessors. Normally DFA on AES exploits faults induced at the last few rounds. Hence, a general countermeasure is to recompute the last few rounds of AES and compare it with the original output. As redundancy is a costly countermeasure, one should ascertain exactly which rounds need to be protected. In 2006, Phan and Yen introduced a new type of DFA, so called Square-DFA, that works even when faults are induced into some middle rounds. However, it is impractical as it requires several hundreds of faulty ciphertexts as well as a bit fault model. In this article, we propose new attacks that need only dozens of faulty ciphertexts in a byte fault model. Normally it is believed that randomly corrupting a byte is easier than corrupting a specific bit. In addition, we extend the attacks to the AES-192 and AES-256, which is the first result in the literature.

Randomness extractors are important tools in cryptography. Their goal is to compress a high-entropy source into a more uniform output. Beyond their theoretical interest, they have recently gained attention because of their use in the design and proof of leakage-resilient primitives, such as stream ciphers and pseudorandom functions. However, for these proofs of leakage resilience to be meaningful in practice, it is important to instantiate and implement the components they are based on. In this context, while numerous works have investigated the implementation properties of block ciphers such as the AES Rijndael, very little is known about the application of side-channel attacks against extractor implementations. In order to close this gap, this paper instantiates a low-cost hardware extractor and analyzes it both from a performance and from a side-channel security point of view. Our investigations lead to contrasted conclusions. On the one hand, extractors can be efficiently implemented and protected with masking. On the other hand, they provide adversaries with many more exploitable leakage samples than, e.g. block ciphers. As a result, they can ensure high security margins against standard (non-profiled) side-channel attacks and turn out to be much weaker against profiled attacks. From a methodological point of view, our analysis consequently raises the question of which attack strategies should be considered in security evaluations.

This paper investigates the two-pass authenticated key exchange protocol in the enhanced Canetti-Krawczyk (eCK) with perfect forward security. Currently, there exist no authenticated key exchange protocols which are provably secure in eCK model and meanwhile achieve perfect forward security against active adversary in one round. We propose a new two-pass authenticated key exchange protocol which enjoys following desirable properties. \textbf{First}, our protocol is shown secure in the eCK model under the gap Diffie-Hellman (GDH) assumption. Moreover, our protocol does not use the NAXOS transformation, the drawback of which will be discussed in the introduction. \textbf{Second}, under the same assumption, we prove that our protocol achieves perfect forward security against active adversary in one round. To the best of our knowledge, our proposal is first two-pass (one round) AKE protocol provably secure in the eCK model and achieving perfect forward security against active adversary.

In this paper, we propose a new lightweight block cipher called LBlock. Similar to many other lightweight block ciphers, the block size of LBlock is 64-bit and the key size is 80-bit. Our security evaluation shows that LBlock can achieve enough security margin against known attacks, such as differential cryptanalysis, linear cryptanalysis, impossible differential cryptanalysis and related-key attacks etc. Furthermore, LBlock can be implemented efficiently not only in hardware environments but also in software platforms such as 8-bit microcontroller. Our hardware implementation of LBlock requires about 1320 GE on 0.18 $\mu m$ technology with a throughput of 200 Kbps at 100 KHz. The software implementation of LBlock on 8-bit microcontroller requires about 3955 clock cycles to encrypt a plaintext block.

We present a fully homomorphic encryption scheme that is based solely on the (standard) learning with errors (LWE) assumption. Applying known results on LWE, the security of our scheme is based on the worst-case hardness of ``short vector problems'' on arbitrary lattices. Our construction improves on previous works in two aspects: 1. We show that ``somewhat homomorphic'' encryption can be based on LWE, using a new {\em re-linearization} technique. In contrast, all previous schemes relied on complexity assumptions related to ideals in various rings. 2. We deviate from the ``squashing paradigm'' used in all previous works. We introduce a new {\em dimension-modulus reduction} technique, which shortens the ciphertexts and reduces the decryption complexity of our scheme, {\em without introducing additional assumptions}. Our scheme has very short ciphertexts and we therefore use it to construct an asymptotically efficient LWE-based single-server private information retrieval (PIR) protocol. The communication complexity of our protocol (in the public-key model) is $k \cdot \polylog(k)+\log |DB|$ bits per single-bit query (here, $k$ is a security parameter).

We take a critical look at security models that are often used to give "provable security'' guarantees. We pay particular attention to digital signatures, symmetric-key encryption, and leakage resilience. We find that there has been a surprising amount of uncertainty about what the "right'' definitions might be. Even when definitions have an appealing logical elegance and nicely reflect certain notions of security, they fail to take into account many types of attacks and do not provide a comprehensive model of adversarial behavior.

We present a generic transformation that allows us to use a large class of pairing-based signatures to construct schemes for signing group elements in a structure preserving way. As a result of our transformation we obtain a new efficient signature scheme for signing a vector of group elements that is based only on the well established decisional linear assumption (DLIN). Moreover, the public keys and signatures of our scheme consist of group elements only, and a signature is verified by evaluating a set of pairing-product equations. In combination with the Groth-Sahai proof system, such a signature scheme is an ideal building block for many privacy-enhancing protocols. To do this, we start by proposing a new stateful signature scheme for signing vectors of exponents that is F-unforgeable under weak chosen message attacks. This signature scheme is of independent interest as it is compatible with Groth-Sahai proofs and secure under a computational assumption implied by DLIN. Then we give a general transformation for signing group elements based on signatures (for signing exponents) with efficient non-interactive zero-knowledge proofs. This transform also removes any dependence on state in the signature used to sign exponents. Finally, we obtain our result by instantiating this transformation with the above signature scheme and Groth-Sahai proofs.

The visual cryptography scheme (VCS) is a scheme which encodes a secret image into several shares, and only qualified sets of shares can recover the secret image visually, other sets of shares cannot get any information about the content of the secret image. From the point of view of encrypting (carrying) the secret information, the traditional VCS is not an efficient method. The amount of the information that a VCS encrypts depends on the amount of secret pixels. And because of the restrictions of the human eyes and the pixel expansion and the alignment problem of the VCS, a VCS perhaps can only be used to encrypt a small secret image. VCS requires a random number generator to guide the generation of the shares. As we will show in this paper, the random input of VCS can ba seen as a subchannel which helps carrying more secret information. We propose a general method to increase the amount of secret information that a threshold VCS can encrypt by treating the pseudo-random inputs of the VCS as a subchannel, i.e. the Encrypting More Information Visual Cryptography Scheme (EMIVCS). We also study the bandwidth of the proposed EMIVCS. The disadvantage of the proposed scheme is that, the decoding process is computer aided. However, compared with other computer aided VCS, the proposed scheme is more efficient.

We exhibit a hash-based storage auditing scheme which is provably secure in the random-oracle model (ROM), but easily broken when one instead uses typical indifferentiable hash constructions. This contradicts the widely accepted belief that the indifferentiability composition theorem applies to any cryptosystem. We characterize the uncovered limitation of the indifferentiability framework by show- ing that the formalizations used thus far implicitly exclude security notions captured by experiments that have multiple, disjoint adversarial stages. Examples include deterministic public-key encryption (PKE), password-based cryptography, hash function nonmalleability, key-dependent message security, and more. We formalize a stronger notion, reset indifferentiability, that enables an indifferentiability- style composition theorem covering such multi-stage security notions, but then show that practical hash constructions cannot be reset indifferentiable. We discuss how these limitations also affect the universal composability framework. We finish by showing the chosen-distribution attack security (which requires a multi-stage game) of some important public-key encryption schemes built using a hash construction paradigm introduced by Dodis, Ristenpart, and Shrimpton.

Elliptic curve cryptosystems are more and more widespread in everyday-life applications. This trend should still gain momentum in coming years thanks to the exponential security enjoyed by these systems compared to the subexponential security of other systems such as RSA. For this reason, efficient elliptic curve arithmetic is still a hot topic for cryptographers. The core operation of elliptic curve cryptosystems is the scalar multiplication which multiplies some point on an elliptic curve by some (usually secret) scalar. When such an operation is implemented on an embedded system such as a smart card, it is subject to {\em side channel attacks}. To withstand such attacks, one must constrain the scalar multiplication algorithm to be {\em regular}, namely to have an operation flow independent of the input scalar. A large amount of work has been published that focus on efficient and regular scalar multiplication and the choice leading to the best performances in practice is not clear. In this paper, we look into this question for general-form elliptic curves over large prime fields and we complete the current state-of-the-art. One of the fastest low-memory algorithms in the current literature is the Montgomery ladder using co-$Z$ Jacobian arithmetic {\em with $X$ and $Y$ coordinates only}. We detail the regular implementation of this algorithm with various trade-offs and we introduce a new binary algorithm achieving comparable performances. For implementations that are less constrained in memory, windowing techniques and signed exponent recoding enable reaching better timings. We survey regular algorithms based on such techniques and we discuss their security with respect to side-channel attacks. On the whole, our work give a clear view of the currently best time-memory trade-offs for regular implementation of scalar multiplication over prime-field elliptic curves.

We introduce a natural cryptographic functionality called \emph{functional re-encryption}. Informally, this functionality, for a public-key encryption scheme and a function $F$ with $n$ possible outputs, transforms (``re-encrypts") an encryption of a message $m$ under an ``input public key" $\pk$ into an encryption of the same message $m$ under one of the $n$ ``output public keys", namely the public key indexed by $F(m)$. In many settings, one might require that the program implementing the functional re-encryption functionality should reveal nothing about both the input secret key $\sk$ as well as the function $F$. As an example, consider a user Alice who wants her email server to share her incoming mail with one of a set of $n$ recipients according to an access policy specified by her function $F$, but who wants to keep this access policy private from the server. Furthermore, in this setting, we would ideally obtain an even stronger guarantee: that this information remains hidden even when some of the $n$ recipients may be corrupted. To formalize these issues, we introduce the notion of \emph{collusion-resistant obfuscation} and define this notion with respect to average-case secure obfuscation (Hohenberger \emph{et al.} - TCC 2007). We then provide a construction of a functional re-encryption scheme for any function $F$ with a polynomial-size domain and show that it satisfies this notion of collusion-resistant obfuscation. We note that collusion-resistant security can be viewed as a special case of dependent auxiliary input security (a setting where virtually no positive results are known), and this notion may be of independent interest. Finally, we show that collusion-resistant obfuscation of functional re-encryption for a function $F$ gives a way to obfuscate $F$ in the sense of Barak {\em et al.} (CRYPTO 2001), indicating that this task is impossible for arbitrary (polynomial-time computable) functions $F$.

Backes, Pfitzmann and Waidner showed in [7] that for protocols with hashes Dolev-Yao style models do not have cryptographically sound realization in the sense of BRSIM/UC in the standard model of cryptography. They proved that random oracle model provides a cryptographically sound realization. Canetti [9] introduced the notion of oracle hashing “towards realizing random oracles”. Based on these two approaches, we propose a random hash primitive, which already makes possible cryptographically sound realization in the sense of BRSIM/UC in the standard model of cryptography.

The advent of Pairing-based protocols has had a major impact on the applicability of cryptography to the solution of more complex real-world problems. However there has always been a question mark over the performance of such protocols. In response much work has been done to optimize pairing implementation, and now it is generally accepted that being pairing-based does not preclude a protocol from consideration as a practical proposition. However although a lot of effort has gone into the optimization of the stand-alone pairing, in many protocols the pairing calculation appears in a particular context within which further optimizations may be possible. It is the purpose of this paper to bridge the gap between theory and practise, and to show that even complex protocols may have a surprisingly efficient implementation. We also point out that in some cases the usually recommended pairing friendly curves may not in fact be optimal. We claim a new record with our implementation of a pairing at the AES-256 bit level.

With the rapid development of theory and application of chaos, more and more researchers are focusing on chaos based cryptosystems. Recently, Guo et al.’s [X. Guo, J. Zhang, Secure group key agreement protocol based on chaotic Hash, Information Sciences 180 (2010) 4069–4074] proposed a secure key agreement protocol based on chaotic Hash. They claimed that their scheme could withstand various attacks. Unfortunately, by giving concrete attacks, we indicate that Guo et al.’s scheme is vulnerable to the off-line password guessing attack. The analysis shows Guo et al.’s scheme is not secure for practical application.

New techniques for reducing the depth of circuits for cryptographic applications are described and applied to the AES S-box. These techniques also keep the number of gates quite small. The result, when applied to the AES S-box, is a circuit with depth 16 and only 128 gates. For the inverse, it is also depth 16 and has only 127 gates. There is a shared middle part, common to both the S-box and its inverse, consisting of 63 gates.

Radio frequency identification systems need protocols to provide confidentiality, user privacy, mutual authentication and etc. These protocols should resist active and passive attacks such as forgery, traceability, replay and desynchronization attacks. In this paper we cryptanalysis a hash based RFID mutual authentication protocol which has been recently proposed by Cho \textit{et al.} More precisely, we present the following attacks on this protocol: \begin{enumerate} \item \textbf{Desynchronization attack}: the success probability of attack is ``1'' while the attack complexity is one run of protocol. \item \textbf{Tag impersonation attack}: the success probability of attack is ``$\frac{1}{4}$'' for two runs of protocol. \item \textbf{Reader impersonation attack}: the success probability of attack is ``$\frac{1}{4}$'' for two runs of protocol. \end{enumerate}

In this paper, we consider the problem of k-out-of-n secret sharing scheme, capable of identifying t cheaters. We design a very simple k-out-of-n secret sharing scheme, which can identify up to t cheaters, with probability at least 1 - \epsilon, where 0 < \epsilon < 1/2, provided t < k / 2. This is the maximum number of cheaters, which can be identified by any k-out-of-n secret sharing scheme, capable of identifying t cheaters (we call these schemes as Secret Sharing with Cheater Identification (SSCI)). In our scheme, the set of all possible i^{th} share V_i satisfies the condition that |V_i| = |S| / \epsilon^{3n}, where S denotes the set of all possible secrets. Moreover, our scheme requires polynomial computation. In EUROCRYPT 2011, Satoshi Obana presented two SSCI schemes, which can identify up to t < k / 2 cheaters. However, the schemes require |V_i| \approx (n (t+1) 2^{3t-1} |S|) / \epsilon and |V_i| \approx ((n t 2^{3t})^2 |S|) / (\epsilon^2)$ respectively. Moreover, both the schemes are computationally inefficient, as they require to perform exponential computation in general. So comparing our scheme with the schemes of Obana, we find that not only our scheme is computationally efficient, but in our scheme the share size is significantly smaller than that of Obana. Thus our scheme solves one of the open problems left by Obana, urging to design efficient SSCI scheme with t < k/2. In CRYPT0 1995, Kurosawa, Obana and Ogata have shown that in any SSCI scheme, |V_i| \geq (|S| - 1) / (\epsilon) + 1. Though our proposed scheme does not exactly matches this bound, we show that our scheme {\it asymptotically} satisfies the above bound. To the best of our knowledge, our scheme is the best SSCI scheme, capable of identifying the maximum number of cheaters.

We prove that if one can predict any of the bits of the input to an elliptic curve based one-way function over a finite field, then we can invert the function. In particular, our result implies that if one can predict any of the bits of the input to a classical pairing-based one-way function with non-negligible advantage over a random guess then one can efficiently invert this function and thus, solve the Fixed Argument Pairing Inversion problem (FAPI-1/FAPI-2). The latter has implications on the security of various pairing-based schemes such as the identity-based encryption scheme of BonehFranklin, Hess’ identity-based signature scheme, as well as Joux’s three-party one-round key agreement protocol. Moreover, if one can solve FAPI-1 and FAPI-2 in polynomial time then one can solve the Computational Diffie–Hellman problem (CDH) in polynomial time. Our result implies that all the bits of the functions defined above are hard-to-compute assuming these functions are one-way. The argument is based on a list-decoding technique via discrete Fourier transforms due to Akavia–Goldwasser–Safra as well as an idea due to Boneh–Shparlinski.

For the fully homomorphic encryption schemes in [SV10, GH11], this paper presents attacks to solve equivalent secret key and directly recover plaintext from ciphertext for lattice dimensions n=2048 by using lattice reduction algorithm. According to the average-case behavior of LLL in [NS06], their schemes are also not secure for n=8192.

With the gaining popularity of remote storage (e.g. in the Cloud), we consider the setting where a small, protected local machine wishes to access data on a large, untrusted remote machine. This setting was introduced in the RAM model in the context of software protection by Goldreich and Ostrovsky. A secure Oblivious RAM simulation allows for a client, with small (e.g., constant size) protected memory, to hide not only the data but also the sequence of locations it accesses (both reads and writes) in the unprotected memory of size $n$. Our main results are as follows: -We analyze several schemes from the literature, observing a repeated design flaw that leaks information on the memory access pattern. For some of these schemes, the leakage is actually non-negligible, while for others it is negligible. -On the positive side, we present a new secure oblivious RAM scheme, extending a recent scheme by Goodrich and Mitzenmacher. Our scheme uses only $O(1)$ local memory, and its (amortized) overhead is $O(\log^2 n/\log\log n)$, outperforming the previously-best $O(\log^2n)$ overhead (among schemes where the client only uses $O(1)$ additional local memory). -We also present a transformation of our scheme above (whose amortized overhead is $O(\log^2 n/\log\log n)$) into a scheme with worst-case overhead of $O(\log^2 n/\log\log n)$.

Sophie Germain Counter Mode (SGCM) is an authenticated encryption mode of operation, to be used with 128-bit block ciphers such as AES. SGCM is a variant of the NIST standardized Galois / Counter Mode (GCM) which has been found to be susceptible to weak key / short cycle forgery attacks. The GCM attacks are made possible by its extremely smooth-order multiplicative group which splits into 512 subgroups. Instead of GCM's $GF(2^{128})$, we use $GF(p)$ with $p=2^{128}+12451$, where $\frac{p-1}{2}$ is also a prime. SGCM is intended for those who want a concrete, largely technically compatible alternative to GCM. In this memo we give a technical specification of SGCM, together with some elements of its implementation, security and performance analysis. Test vectors are also included.

The contribution of this paper is twofold. First we present a new simple electronic voting scheme having standard re-encryption mix net back-end, which allows to cast a ballot and verify its correctness in a new way. Then we extend the proposed scheme to represent a new very efficient mix network construction. We called our mix network to be self-proving mix, because it is shown how mix process correctness can be verified without demanding from mix party a special proof. Our proposed mix network allows to reveal all the cheating occurred during a mix process at verification of decryption parties work.

Two fundamental building blocks of secure two-party computation are oblivious transfer and bit commitment. While there exist unconditionally secure implementations of oblivious transfer from noisy correlations or channels that achieve constant rates, similar constructions are not known for bit commitment. In this paper we show that any protocol that implements $n$ instances of bit commitment with an error of at most $2^{-k}$ needs at least $\Omega(kn)$ instances of a given resource such as oblivious transfer or a noisy channel. This implies in particular that it is impossible to achieve a constant rate. We then show that it is possible to circumvent the above lower bound by restricting the way in which the bit commitments can be opened. In the special case where only a constant number of instances can be opened, our protocol achieves a constant rate, which is optimal. Our protocol implements these restricted bit commitments from string commitments and is universally composable. The protocol provides significant speed-up over individual commitments in situations where restricted commitments are sufficient.

On Nov 2007, NIST announced the SHA-3 competition to select a new hash standard as a replacement of SHA-2. On Dec 2010, five submissions have been selected as the final round candidates, including Skein, which have components based on ARX. In this paper, a new related-key boomerang distinguishing attack is proposed on 31-round Threefish-256 with a time complexity of about $2^{234}$. Our improved attack is based on the efficient algorithms for calculating differentials of modular addition.

The resistance of cryptographic implementations to side channel analysis is matter of considerable interest to those concerned with information security. It is particularly desirable to identify the attack methodology (e.g. differential power analysis using correlation or distance-of-means as the distinguisher) able to produce the best results. Attempts to answer this question are complicated by the many and varied factors contributing to attack success: the device power consumption characteristics, an attacker's power model, the distinguisher by which measurements and model predictions are compared, the quality of the estimations, and so on. Previous work has delivered partial answers for certain restricted scenarios. In this paper we assess the effectiveness of mutual information analysis within a generic and comprehensive evaluation framework. Complementary to existing work, we present several notions/characterisations of attack success, as well as a means of indicating the amount of data required by an attack. We are thus able to identify scenarios in which mutual information offers performance advantages over other distinguishers. Furthermore we observe an interesting feature -- unique to the mutual information based distinguisher -- resembling a type of stochastic resonance, which could potentially enhance the effectiveness of such attacks over other methods in certain noisy scenarios.

Distance-Bounding identification protocols aim at impeding man-in-the-middle attacks by measuring response times. There are three kinds of attacks such protocols could address: (1) Mafia attacks where the adversary relays communication between honest prover and honest verifier in different sessions; (2) Terrorist attacks where the adversary gets limited active support from the prover to impersonate. (3) Distance attacks where a malicious prover claims to be closer to the verifier than it actually is. Many protocols in the literature address one or two such threats, but no rigorous cryptographic security models ---nor clean security proofs--- exist so far. For resource-constrained RFID tags, distance-bounding is more difficult to achieve. Our contribution here is to formally define security against the above-mentioned attacks and to relate the properties. We thus refute previous beliefs about relations between the notions, showing instead that they are independent. Finally we use our new framework to assess the security of the RFID distance-bounding scheme due to Kim and Avoine, and enhance it to include impersonation security and allow for errors due to noisy channel transmissions.

In this paper we give the minimal connectivity required in a synchronous directed network, which is under the influence of a computationally unbounded \emph{Byzantine} adversary that can corrupt a subset of nodes, so that Secure Message Transmission is possible between sender $S$ and receiver $R$. We also show that secure communication between a pair of nodes in a given synchronous directed network is possible in both directions if and only if reliable communication is possible between them. We assume that in a network, every node is capable of computation and we model the network along the lines of \cite{SR06}.

In this paper we present the first public key encryption scheme that is structure preserving, i.e., our encryption scheme uses only algebraic operations. In particular it does not use hash-functions or interpret group elements as bit-strings. This makes our scheme a perfect building block for cryptographic protocols where parties for instance want to prove, to each other, properties about ciphertexts or jointly compute ciphertexts. Our scheme is also very efficient and is secure against \dkg adaptive\blk{} chosen ciphertext attacks. We also provide a few example protocols for our scheme. For instance, a joint computation of a ciphertext\dkg, generated from two secret plaintexts from each party respectively\blk, where in the end, only one of the parties learns the ciphertext. This latter protocol serves as a building block for our second contribution which is a set of protocols that implement the concept of oblivious trusted third parties. This concept has been proposed before, but no concrete realization was known.

The paper proposes a $\tau^2-$NAF method for scalar multiplication on Koblitz curves, which requires asymptotically $0.215m$ point additions in $GF(2^m)$. For $\tau^2-$NAF method, point quading operation $(a\rightarrow a^4)$ is performed instead of point squarings. The proposed method is faster than normal $\tau-$NAF method, which requires around $\frac{m}{3}$ point additions. However, like width $w$ based $\tau-$NAF methods, there is an overhead of pre-computations in the $\tau^2-$NAF method. For extended binary fields of small size, the $\tau^2-$NAF based scalar multiplication requires almost same number of point additions as in width $4$ $\tau-$NAF method. Though, complexity wise, $\tau^2-$NAF based scalar multiplication and width $4-\tau-$NAF based scalar multiplication are similar, but the techniques are different.

Norwegian nationwide Internet voting will make use of a setting that we will call the code-verification voting. The concrete protocol that will be used in Norway was proposed by Scytl and improved by Gjøsteen. As we show, Gjøsteen's protocol has several undesirable properties. In particular, one of the online servers shares the secret key with the offline tallier. Even without considering that, the coalition of two online voting servers can breach voter privacy. We propose two new code-verification voting protocols. The first protocol separates the secret keys, and is as efficient as Gjøsteen's protocol. The second protocol provides voter privacy against the coalition of online voting servers but is somewhat less efficient. While the new protocols are more secure than the protocol that is going to be used in the Norwegian nationwide Internet voting, they are based on the same setting, so as to minimize the required infrastructural changes.

We revisit the definition of unforgeability of blind signatures as proposed by Pointcheval and Stern (Journal of Cryptology 2000). Surprisingly, we show that this established definition falls short in two ways of what one would intuitively expect from a secure blind signature scheme: It is not excluded that an adversary submits the same message $m$ twice for signing, and then produces a signature for $m'\neq m$. The reason is that the forger only succeeds if \emph{all} messages are distinct. Moreover, it is not excluded that an adversary performs $k$ signing queries and produces signatures on $k+1$ messages as long as \emph{each} of these signatures does not pass verification with probability~$1$. Finally, we proposed a new definition, honest-user unforgeability, that covers these attacks. We give a simple and efficient transformation that transforms any unforgeable blind signature scheme (with deterministic verification) into an honest-user unforgeable one.

The Gallant-Lambert-Vanstone (GLV) method is a very efficient technique for accelerating point multiplication on elliptic curves with efficiently computable endomorphisms. Galbraith, Lin and Scott (J. Cryptol. 24(3), 446-469 (2011)) showed that point multiplication exploiting the 2-dimensional GLV method on a large class of curves over GF(p^2) was faster than the standard method on general elliptic curves over GF(p), and left as an open problem to study the case of 4-dimensional GLV on special curves (e.g., j(E) = 0) over GF(p^2). We study the above problem in this paper. We show how to get the 4-dimensional GLV decomposition with proper decomposed coefficients, and thus reduce the number of doublings for point multiplication on these curves to only a quarter. The resulting implementation shows that the 4-dimensional GLV method on a GLS curve runs in about 0.78 the time of the 2-dimensional GLV method on the same curve and in between 0.78-0.87 the time of the 2-dimensional GLV method using the standard method over GF(p). In particular, our implementation reduces by up to 27% the time of the previously fastest implementation of point multiplication on x86-64 processors due to Longa and Gebotys (CHES2010).

Tampering attacks are cryptanalytic attacks on the implementation of cryptographic algorithms (e.g., smart cards), where an adversary introduces faults with the hope that the tampered device will reveal secret information. Inspired by the work of Ishai et al. [Eurocrypt'06], we propose a compiler that transforms any circuit into a new circuit with the same functionality, but which is resilient against a well-defined and powerful tampering adversary. More concretely, our transformed circuits remain secure even if the adversary can adaptively tamper with every wire in the circuit as long as the tampering fails with some probability $\delta>0$. This additional requirement is motivated by practical tampering attacks, where it is often difficult to guarantee the success of a specific attack. Formally, we show that a $q$-query tampering attack against the transformed circuit can be ``simulated'' with only black-box access to the original circuit and $\log(q)$ bits of additional auxiliary information. Thus, if the implemented cryptographic scheme is secure against $\log(q)$ bits of leakage, then our implementation is tamper-proof in the above sense. Surprisingly, allowing for this small amount of information leakage -- and not insisting on perfect simulability like in the work of Ishai et al. -- allows for much more efficient compilers, which moreover do not require randomness during evaluation. Similar to earlier work our compiler requires small, stateless and computation-independent tamper-proof gadgets. Thus, our result can be interpreted as reducing the problem of shielding arbitrary complex computation to protecting simple components.

In this paper we present first ever error-free, asynchronous broadcast (called as A-cast) and Byzantine Agreement (called as ABA) protocols with optimal communication complexity and fault tolerance. Our protocols are multi-valued, meaning that they deal with $\ell$ bit input and achieve communication complexity of $O(n\ell)$ bits for large enough $\ell$ for a set of $n \geq 3t+1$ parties in which at most t can be Byzantine corrupted. In synchronous settings, Fitzi and Hirt (PODC'06) proposed probabilistically correct multi-valued broadcast (BC) and Byzantine Agreement (BA) protocols with optimal complexity of $O(n\ell)$ bits. Recently, Liang and Vaidya (PODC'11) achieved the same deterministically, i.e. without error probability. In asynchronous settings, Patra and Rangan (Latincrypt'10, ICITS'11) reported similar protocols with error probability. Here we achieve optimal complexity of $O(n\ell)$ bits for asynchronous error-free case. Following all the previous works on multi-valued protocols, we too follow reduction-based approach for our protocols, meaning that our multi-valued protocols are designed given existing A-cast and ABA protocols for small message (possibly for single bit). However compared to existing reductions, our reductions are simple and elegant. More importantly, our reductions run in constant expected time, in contrast to $O(n)$ of Patra and Rangan (ICITS'11). Furthermore our reductions invoke less or equal number of instances of protocols for single bit in comparison to the reductions of Patra and Rangan. In synchronous settings, while the reduction of Fitzi and Hirt is constant-round and invokes $O(n(n+\kappa))$ ($\kappa$ is the error parameter) instances of protocols for single bit, the reduction of Liang and Vaidya calls for round complexity and number instances that are in fact function of the message size, $O(\sqrt{\ell} + n^2)$ and $\calO(n^2\sqrt{\ell} + n^4)$, respectively where $\ell = \Omega(n^6)$. By adapting our techniques from asynchronous settings, we present new {\it error-free} reduction in synchronous world that is constant-round and calls for only $O(n^2)$ instances of protocols for single bit which is at least as good as Fitzi and Hirt.

GOST 28147-89 is a well-known block cipher and the official encryption standard of the Russian Federation. A 256-bit block cipher considered as an alternative for AES-256 and triple DES, having an amazingly low implementation cost and thus increasingly popular and used. Until 2010 researchers unanimously agreed that: "despite considerable cryptanalytic efforts spent in the past 20 years, GOST is still not broken" and in 2010 it was submitted to ISO 18033 to become a worldwide industrial encryption standard. In 2011 it was suddenly discovered that GOST is insecure on more than one account. There is an amazing variety of recent attacks on GOST. We have reflection attacks, attacks with double reflection, and various attacks which does not use reflections. All these methods follow a certain general framework called "Algebraic Complexity Reduction", a new general "umbrella" paradigm. The final key recovery step is in most cases a software algebraic attack and sometimes a Meet-In-The-Middle attack. In this paper we show that GOST is NOT SECURE even against (advanced forms of) differential cryptanalysis (DC). Previously Russian researchers postulated that GOST will be secure against DC for as few as 7 rounds out of 32 and Japanese researchers were already able to break about 13 rounds. In this paper we show a first advanced differential attack faster than brute force on full 32-round GOST. This paper is just a sketch and a proof of concept. More results of this kind will be published soon.

We put forward the notion of targeted malleability: given a homomorphic encryption scheme, in various scenarios we would like to restrict the homomorphic computations one can perform on encrypted data. We introduce a precise framework, generalizing the foundational notion of non-malleability introduced by Dolev, Dwork, and Naor (SICOMP '00), ensuring that the malleability of a scheme is targeted only at a specific set of "allowable" functions. In this setting we are mainly interested in the efficiency of such schemes as a function of the number of repeated homomorphic operations. Whereas constructing a scheme whose ciphertext grows linearly with the number of such operations is straightforward, obtaining more realistic (or merely non-trivial) length guarantees is significantly more challenging. We present two constructions that transform any homomorphic encryption scheme into one that offers targeted malleability. Our constructions rely on standard cryptographic tools and on succinct non-interactive arguments, which are currently known to exist in the standard model based on variants of the knowledge-of-exponent assumption. The two constructions offer somewhat different efficiency guarantees, each of which may be preferable depending on the underlying building blocks.

In synchronous networks, protocols can achieve security guarantees that are not possible in an asynchronous world: i.e., they can simultaneously achieve input completeness (all honest parties’ inputs are included in the computation) and guaranteed termination (honest parties do not “hang” indefinitely). In practice truly syn- chronous networks rarely exist, but synchrony can be emulated if channels have (known) latency and parties have loosely synchronized clocks. The framework of universal composability (UC) is inherently asynchronous, but several approaches for adding synchrony to the framework have been proposed. However, we show that the existing proposals do not provide the expected guarantees. Given this, we propose a “clean slate” approach to defining synchrony in the UC framework by introducing functionalities exactly meant to model, respectively, bounded-delay networks and loosely synchronized clocks. We show that the expected guarantees of synchronous computation can be realized given these functionalities, and that previous models can all be expressed within our new framework.

Homomorphic encryption schemes are powerful cryptographic primitives that allow for a variety of applications. Consequently, a variety of proposals have been made in the recent decades but none of them was based on coding theory. The existence of such schemes would be interesting for several reasons. First, it is well known that having multiple schemes based on different hardness assumptions is advantageous. In case that one hardness assumption turns out be wrong, one can switch over to one of the alternatives. Second, fo some codes decoding (which would represent decryption in this case) is a linear mapping only (if the error is known), i.e., a comparatively simple operation. This would make such schemes interesting candidates for constructing of fully-homomorphic schemes based on bootstrapping (see Gentry, STOC'09). We show that such schemes are indeed possible by presenting a natural construction principle. Moreover, these possess several non-standard positive features. First, they are not restricted to linear homomorphism but allow for evaluating multivariate polynomials up to a fixed (but arbitrary) degree $\mult$ on encrypted field elements. Second, they can be instantiated with various error correcting codes, even for codes with poor correcting capabilities. Third, depending on the deployed code, one can achieve very efficient schemes. As a concrete example, we present an instantiation based on Reed-Muller codes where for $\mult=2$ and $\mult=3$ and security levels between 80 and 128 bits, all operations take less than a second (after some pre-computation). However, our analysis reveals also limitations on this approach. For structural reasons, such schemes cannot be public-key, allow for a limited number of fresh encryptions only, and cannot be combined with the bootstrapping technique. We argue why such schemes are nonetheless useful in certain application scenarios and discuss possible directions on how to overcome these issues.

The onion routing network Tor is undoubtedly the most widely employed technology for anony- mous web access. Although the underlying onion routing (OR) protocol appears satisfactory, a comprehensive analysis of its security guarantees is still lacking. This has also resulted in a sig- nificant gap between research work on OR protocols and existing OR anonymity analyses. In this work, we address both issues with onion routing by defining a provably secure OR protocol, which is practical for deployment in the next generation Tor network. We start off by presenting a security definition (an ideal functionality) for the OR methodology in the universal composability (UC) framework. We then determine the exact security properties required for OR cryptographic primitives (onion construction and processing algorithms, and a key exchange protocol) to achieve a provably secure OR protocol. We show that the currently deployed onion algorithms with slightly strengthened integrity properties can be used in a provably secure OR construction. In the process, we identify the concept of predictably malleable symmetric encryptions, which might be of independent interest. On the other hand, we find the currently deployed key exchange protocol to be inefficient and difficult to analyze and instead show that a recent, significantly more efficient, key exchange protocol can be used in a provably secure OR construction. In addition, our definition greatly simplifies the process of analyzing OR anonymity metrics. We define and prove forward secrecy for the OR protocol, and realize our (white-box) OR definition from an OR black-box model assumed in a recent anonymity analysis. This realization not only makes the analysis formally applicable to the OR protocol but also identifies the exact adversary and network assumptions made by the black box model.

People had developed some attack methods to attack hash function. These methods need to choose some "differential pattern"[Dau05]. We present a way to restrict the collisions that hold the "differential pattern". At the same time, to build a hash function that meet the different needs, we propose a construction.

We derive an explicit method of computing the composition step in Cantor's algorithm for group operations on Jacobians of hyperelliptic curves. Our technique is inspired by the geometric description of the group law and applies to hyperelliptic curves of arbitrary genus. While Cantor's general composition involves arithmetic in the polynomial ring $F_q[x]$, the algorithm we propose solves a linear system over the base field which can be written down directly from the Mumford coordinates of the group elements. We apply this method to give more efficient formulas for group operations in both affine and projective coordinates for cryptographic systems based on Jacobians of genus 2 hyperelliptic curves in general form.

The Jakobsson hybrid Mix-net proposed by Jakobsson and Juels, is a very practical and efficient scheme for long input messages. But this hybrid Mix-net does not have public verifiable property. In this paper a new attack to the Jakobsson hybrid Mix-net is introduced. This attack breaks the robustness of the hybrid Mix-net scheme, given that the corrupted first mix server and one of the senders collude with each other.

In cloud storage service, users upload their data together with authentication information to cloud storage server. To ensure the availability and integrity of users' data stored in the cloud storage, users need to verify the cloud storage remotely and periodically, with the help of the pre-stored authentication information and without storing a local copy of the data or retrieving back the data during verification. Public verification enables a third party auditor (TPA), on the behalf of the data owner, to verify the integrity of cloud storage with the data owner's public key. In this paper, we propose a method that allows the data owner to delegate the auditing task to a potentially untrusted third party auditor in a secure manner: (1) The data owner can verify whether the TPA has indeed performed the specified audit task; (2) The data owner can verify whether the TPA did the audit task at the right time specified by the data owner; (3) The confidentiality of the data is protected against the TPA. Our method also enables a TPA to re-outsource the audit task.

We put forward a framework for the modular design and analysis of multi-party protocols. Our framework is called ``GNUC'' (with the recursive meaning ``GNUC's Not UC''), already alluding to the similarity to Canetti's Universal Composability (UC) framework. In particular, like UC, we offer a universal composition theorem, as well as a theorem for composing protocols with joint state. We deviate from UC in several important aspects. Specifically, we have a rather different view than UC on the structuring of protocols, on the notion of polynomial-time protocols and attacks, and on corruptions. We will motivate our definitional choices by explaining why the definitions in the UC framework are problematic, and how we overcome these problems. Our goal is to make offer a framework that is largely compatible with UC, such that previous results formulated in UC carry over to GNUC with minimal changes. We exemplify this by giving explicit formulations for several important protocol tasks, including authenticated and secure communication, as well as commitment and secure function evaluation.

Differential power analysis is a powerful cryptanalytic technique that exploits information leaking from physical implementations of cryptographic algorithms. During the two last decades numerous variations of the original principle have been published. In particular, the univariate case, where a single instantaneous leakage is exploited, has attracted much research effort. In this paper, we argue that several univariate attacks among the most frequently used by the community are not only asymptotically equivalent, but can also be rewritten one in function of the other, only by changing the leakage model used by the adversary. In particular, we prove that most univariate attacks proposed in the literature can be expressed as correlation power analyses with different leakage models. This result emphasizes the major role plays by the model choice on the attack efficiency. In a second point of this paper we hence also discuss and evaluate side channel attacks that involve no leakage model but rely on some general assumptions about the leakage. Our experiments show that such attacks, named robust, are a valuable alternative to the univariate differential power analyses. They only loose bit of efficiency in case a perfect model is available to the adversary, and gain a lot in case such information is not available.

We present a protocol that allows to prove in zero-knowledge that committed values $x_i, y_i, z_i$, $i=1,\dots,l$ satisfy $x_iy_i=z_i$, where the values are taken from a finite field $K$, or are integers. The amortized communication complexity per instance proven is $O(\kappa + l)$ for an error probability of $2^{-l}$, where $\kappa$ is the size of a commitment. When the committed values are from a field of small constant size, this improves complexity of previous solutions by a factor of $l$. When the values are integers, we improve on security: whereas previous solutions with similar efficiency require the strong RSA assumption, we only need the assumption required by the commitment scheme itself, namely factoring. We generalize this to a protocol that verifies $l$ instances of an algebraic circuit $D$ over $K$ with $v$ inputs, in the following sense: given committed values $x_{i,j}$ and $z_i$, with $i=1,\dots,l$ and $j=1,\dots,v$, the prover shows that $D(x_{i,1},\dots,x_{i,v})= z_i$ for $i=1,\dots,l$. For circuits with small multiplicative depth, this approach is better than using our first protocol: in fact, the amortized cost may be asymptotically smaller than the number of multiplications in $D$.

Traditionally, secure one-round key exchange protocols in the PKI setting have either achieved perfect forward secrecy, or forms of deniability, but not both. On the one hand, achieving perfect forward secrecy against active attackers seems to require some form of authentication of the messages, as in signed Diffie-Hellman style protocols, that subsequently sacrifice deniability. On the other hand, using implicit authentication along the lines of MQV and descendants sacrifices perfect forward secrecy in one round and achieves only weak perfect forward secrecy instead. We show that by reintroducing signatures, it is possible to satisfy both a very strong key-exchange security notion, which we call eCK-PFS, as well as a strong form of deniability, in one-round key exchange protocols. Our security notion for key exchange is stronger than, e.g., the extended-CK model, and captures perfect forward secrecy. Our notion of deniability, which we call peer-and-time deniability, is stronger than that offered by, e.g., the SIGMA protocol. We propose a concrete protocol and prove that it satisfies our definition of key-exchange security in the random oracle model as well as peer-and-time deniability. The protocol combines a signed-Diffie-Hellman message exchange with an MQV-style key computation, and offers a remarkable combination of advanced security properties.

We describe a systematic framework for using a stream cipher supporting an initialisation vector (IV) to perform various tasks of authentication and authenticated encryption. These include message authentication code (MAC), authenticated encryption (AE), authenticated encryption with associated data (AEAD) and deterministic authenticated encryption (DAE) with associated data. Several schemes are presented and rigourously analysed. A major component of the constructions is a keyed hash function having provably low collision and differential probabilities. Methods are described to efficiently extend such hash functions to take multiple inputs. In particular, double-input hash functions are required for the construction of AEAD schemes. An important practical aspect of our work is that a designer can combine off-the-shelf stream ciphers with off-the-shelf hash functions to obtain secure primitives for MAC, AE, AEAD and DAE(AD).

Let $n$ particles be independently allocated into $N$ boxes, where the $l$-th box appears with the probability $a_l$. Let $\mu_r$ be the number of boxes with exactly $r$ particles and $\mu=[ \mu_{r_1},\ldots, \mu_{r_m}]$. Asymptotical behavior of such random variables as $N$ tends to infinity was studied by many authors. It was previously known that if $Na_l$ are all upper bounded and $n/N$ is upper and lower bounded by positive constants, then $\mu$ tends in distribution to a multivariate normal low. A stronger statement, namely a large deviation local limit theorem for $\mu$ under the same condition, is here proved. Also all cumulants of $\mu$ are proved to be $O(N)$. Then we study the hypothesis testing that the box distribution is uniform, denoted $h$, with a recently introduced box-test. Its statistic is a quadratic form in variables $\mu-\mathbf{E}\mu(h)$. For a wide area of non-uniform $a_l$, an asymptotical relation for the power of the quadratic and linear box-tests, the statistics of the latter are linear functions of $\mu$, is proved. In particular, the quadratic test asymptotically is at least as powerful as any of the linear box-tests, including the well-known empty-box test if $\mu_0$ is in $\mu$.

In this paper, statistical testing of $N$ multinomial probabilities is studied and a new box-test, called \emph{Quadratic Box-Test}, is introduced. The statistics of the new test has $\chi^2_s$ limit distribution as $N$ and the number of trials $n$ tend to infinity, where $s$ is a parameter. The well-known empty-box test is a particular case for $s=1$. The proposal is quite different from Pearson's goodness-of-fit test, which requires fixed $N$ while the number of trials is growing, and linear box-tests. We prove that under some conditions on tested distribution the new test's power tends to $1$. That defines a wide region of non-uniform multinomial probabilities distinguishable from the uniform. For moderate $N$ an efficient algorithm to compute the exact values of the first kind error probability is devised.

We provide constructions of (m,1)-programmable hash functions (PHFs) for m >= 2. Mimicking certain programmability properties of random oracles, PHFs can, e.g., be plugged into the generic constructions by Hofheinz and Kiltz (J. Cryptol. 2011) to yield digital signature schemes from the strong RSA and strong q-Diffie-Hellman assumptions. As another application of PHFs, we propose new and efficient constructions of digital signature schemes from weaker assumptions, i.e., from the (standard, non-strong) RSA and the (standard, non-strong) q-Diffie-Hellman assumptions. The resulting signature schemes offer interesting trade-offs between efficiency/signature length and the size of the public-keys. For example, our q-Diffie-Hellman signatures can be as short as 200 bits; the signing algorithm of our Strong RSA signature scheme can be as efficient as the one in RSA full domain hash; compared to previous constructions, our RSA signatures are shorter (by a factor of roughly 2) and we obtain a considerable efficiency improvement (by an even larger factor). All our constructions are in the standard model, i.e., without random oracles.

We present an accelerated Schoof-type point-counting algorithm for curves of genus 2 equipped with an efficiently computable real multiplication endomorphism. Our new algorithm reduces the complexity of genus 2 point counting over a finite field $GF(q)$ of large characteristic from $\sO(\log^8 q)$ to $\sO(\log^5 q)$. Using our algorithm we compute a 256-bit prime-order Jacobian, suitable for cryptographic applications, and also the order of a 1024-bit Jacobian.

Security of public key schemes in a post-quantum world is a challenging task---as both RSA and ECC will be broken then. In this paper, we show how post-quantum signature systems based on Multivariate Quadratic (MQ) polynomials can be improved up by about 9/10, and 3/4, respectively, in terms of public key size and verification time. The exact figures are 88% and 73%. This is particularly important for small-scale devices with restricted energy, memory, or computational power. In addition, we show that this reduction does not affect security and that it is also optimal in terms of possible attacks. We do so by combining the priory unrelated concepts of reduced and equivalent keys. Our new scheme is based on the so-called Unbalanced Oil and Vinegar class of MQ-schemes. We have derived our results mathematically and verified the speed-ups through a C++ implementation.

The general number field sieve (GNFS) is asymptotically the fastest known factoring algorithm. One of the most important steps of GNFS is to select a good polynomial pair. A standard way of polynomial selection (being used in factoring RSA challenge numbers) is to select a nonlinear polynomial for algebraic sieving and a linear polynomial for rational sieving. There is another method called a nonlinear method which selects two polynomials of the same degree greater than one. In this paper, we generalize Montgomery's method using small geometric progression (GP) (mod $N$) to construct a pair of nonlinear polynomials. We introduce GP of length d+k with 1\leq k\leq d-1 and show that we can construct polynomials of degree $d$ having common root (mod N), where the number of such polynomials and the size of the coefficients can be precisely determined.

The ability to collectively toss a common coin among $n$ parties in the presence of faults is an important primitive in the arsenal of randomized distributed protocols. In the case of dishonest majority, it was shown to be impossible to achieve less than $\frac{1}{r}$ bias in $O(r)$ rounds (Cleve STOC '86). In the case of honest majority, in contrast, unconditionally secure $O(1)$-round protocols for generating common perfectly {\it unbiased} coins follow from general completeness theorems on multi-party secure protocols in the perfectly secure channels model (e.g., BGW, CCD STOC '88). However, in the multi-party protocols with faulty minority, parties need to generate and hold local secret values which are assumed to be {\it perfectly hidden} from malicious parties: an assumption which is crucial to proving the resulting common coin is unbiased. This assumption unfortunately does not seem to hold in practice, as attackers can launch side-channel attacks on the local state of honest parties and leak information on their secrets. In this work, we present an $O(1)$-round protocol for collectively generating an unbiased common coin, in the presence of leakage on the local state of the honest parties. We tolerate $t \le (\frac{1}{3} - \epsilon) n$ computationally-unbounded Byzantine faults and in addition a $\Omega(1)$-fraction leakage on each (honest) party's secret state. Our results hold in the memory leakage model (of Akavia, Goldwasser, Vaikuntanathan '08) adapted to the distributed setting. Another contribution of our work is a tool we use to achieve collective coin flipping -- {\it leakage-resilient verifiable secret sharing}. Informally, this is a variant of ordinary VSS in which secrecy guarantees are maintained even if information is leaked on individual shares of the secret.

In this paper we investigate the properties of generalized bent functions defined on $\BBZ_2^n$ with values in $\BBZ_q$ where $q \ge 2$ is any positive integer. We characterize the class of generalized bent functions symmetric with respect to two variables, provide an analogue of Maiorana--McFarland type bent functions in the generalized set up. A class of bent functions called generalized spreads type is introduced and it is demonstrated that recently introduced Dillon type generalized bent functions and Maiorana--McFarland type generalized bent functions can be described as generalized spreads type functions. Thus unification of two different types of generalized bent functions is achieved.

We initiate the formal treatment of cryptographic constructions based on the hardness of computing remainders modulo an ideal in multivariate polynomial rings. Of particular interest to us is a class of schemes known as "Polly Cracker." We start by formalising and studying the relation between the ideal remainder problem and the problem of computing a Gröbner basis. We show both positive and negative results. On the negative side, we define a symmetric Polly Cracker encryption scheme and prove that this scheme only achieves bounded CPA security under the hardness of the ideal membership problem. Furthermore, we show that a large class of algebraic transformations cannot convert this scheme to a fully secure Polly Cracker-style scheme. On the positive side, we formalise noisy variants of the ideal-theoretic problems. These problems can be seen as natural generalisations of the learning with errors (LWE) and the approximate GCD problems over polynomial rings. After formalising and justifying the hardness of the noisy assumptions, we show that noisy encoding of messages results in a fully IND-CPA-secure and somewhat homomorphic encryption scheme. Together with a standard symmetric-to-asymmetric transformation for additively homomorphic schemes, we provide a positive answer to the long-standing open problem of constructing a secure Polly Cracker-style cryptosystem reducible to the hardness of solving a random system of equations. Indeed, our results go beyond this and also provide a new family of somewhat homomorphic encryption schemes based on generalised hard problems. Our results also imply that Regev's LWE-based public-key encryption scheme is (somewhat) multiplicatively homomorphic for appropriate choices of parameters.

In this paper, we study the communication complexity of Reliable Message Transmission (RMT) and Secure Message Transmission (SMT) protocols in asynchronous settings. We consider two variants of the problem, namely perfect} (where no error is allowed in the protocol outcome) and statistical (where the protocol may output a wrong outcome with negligible probability). RMT and SMT protocols have been investigated rigorously in synchronous settings. But not too much attention has been paid to the asynchronous version of the problem. In a significant work, Choudhury et al. (ICDCN 2009 and JPDC 2011) have studied the network connectivity requirement for perfect and statistical SMT protocols in asynchronous settings. Their investigation reveals the following two important facts: 1. Perfect SMT protocols require more network connectivity in asynchronous network than synchronous network. 2. Connectivity requirement of statistical SMT protocols is same for both synchronous and asynchronous network. Unfortunately, nothing is known about the communication complexity of RMT and SMT protocols in asynchronous settings. In this paper, we derive tight bounds on the communication complexity of the above problems and compare our results with the existing bounds for synchronous protocols. The interesting conclusions derived from our results are: 1. Asynchrony increases the communication complexity of perfect RMT protocols. However, asynchrony has no impact on the communication complexity of statistical RMT protocols. 2. SMT: Communication complexity of SMT protocols is more in asynchronous network, for both perfect as well as statistical case.