International Association
for Cryptologic Research

We show the first deterministic construction of an unconditionally secure multiparty computation (MPC) protocol in the passive adversarial model over black-box non-Abelian groups which is both optimal and has subexponential complexity of construction. More specifically, following the result of Desmedt et al. (2012) that the problem of MPC over non-Abelian groups can be reduced to finding a $t$-reliable $n$-coloring of planar graphs, we show the construction of such a graph which allows a path from the input nodes to the output nodes when any $t$-party subset is in the possession of the adversary. Unlike the (deterministic) constructions from Desmedt et al. (2012) our construction is subexponential and optimal at the same time, i.e., it is secure for any $t < \\frac{n}{2}$.

The notion of domain-specific pseudonymous signatures (DSPS) has recently been introduced for private authentication of ID documents, like passports, that embed a chip with computational abilities. Thanks to this privacy-friendly primitive, the document authenticates to a service provider through a reader and the resulting signatures are anonymous, linkable inside the service and unlinkable across services. A subsequent work proposes to enhance security and privacy of DSPS through group signatures techniques. In this paper, we improve on these proposals in three ways. First, we spot several imprecisions in previous formalizations. We consequently provide a clean security model for \\emph{dynamic domain-specific pseudonymous signatures}, where we correctly address the dynamic and adaptive case. Second, we note that using group signatures is somehow an overkill for constructing DSPS, and we provide an optimized construction that achieves the same strong level of security while being more efficient. Finally, we study the implementation of our protocol in a chip and show that our solution is well-suited for these limited environments. In particular, we propose a secure protocol for delegating the most demanding operations from the chip to the reader.

This work builds on the variant of the function field sieve (FFS) algorithm for the medium prime case introduced by Joux and

Lercier in 2006. We make two contributions. The first contribution introduces a divisility and smoothness technique which

is similar to that of the special-q technique used in integer factorisation algorithms. Such a technique, though, has not

been earlier used in the context of discrete log computations and provides concrete speed-ups in the practical run-time of

the relation collection and the descent phases of the FFS algorithm. The second contribution is to improve the

descent phase of the algorithm. The improvements are based on increasing the degree of freedom and the use of a walk

technique. As a consequence, we show that it is feasible to carry out discrete log computations for certain fields which are

excluded by the analysis of Joux and Lercier. In concrete terms, we present record computations of discrete logs for fields

with 16 and 18-bit prime characteristic. Further, we provide concrete analysis of the effectiveness of the FFS algorithm for

certain fields with medium sized prime characteristic.

A lot of cryptographic protocols have been proposed for semi-honest model. In general, they are much more efficient than those proposed for the malicious model. In this paper, we propose a method that allows to detect the parties that have violated the protocol rules after the computation has ended, thus making the protocol secure against covert attacks. This approach can be useful in the settings where for any party it is fatal to be accused in violating protocol rules. In this way, up to the verification, all the computation can be performed in semi-honest model, which makes it very efficient in practice. The verification is statistical zero-knowledge, and it is based on linear probabilistically checkable proofs ($\\PCP$) for verifiable computation. Each malicious party is detected with probability $1 - \\varepsilon$ for a negligible $\\varepsilon$ that is defined by the failure of the corresponding linear $\\PCP$. The initial protocol has to be executed only once, and the verification requires in total $3$ additional rounds (if some parties act dishonestly, in the worst case they may force the protocol to substitute each round with $4$ rounds, due to the transmission functionality that prevents the protocol from stopping). The verification also ensures that all the parties have sampled all the randomness from an appropriate distribution. Its efficiency does not depend on whether the inputs of the parties have been shared, or each party uses its own private input.

The major drawback of the proposed scheme is that the number of values sent before and after the protocol is exponential in the number of parties. Nevertheless, the settings make the verification very efficient for a small number of parties.

Identity-based encryption (IBE) is a special case of public-key encryption where user identities replace public keys. Every user is given a corresponding secret key for decryp- tion, and encryptions for his or her identity must remain confidential even to attackers who learn the secret keys associated with other identities. Several IBE constructions are known to date, but their security relies on specific assumptions, such as quadratic residuosity, as well as different pairing-based and lattice-based assumptions.

To circumvent the lack of generic constructions, Dodis et al. (EUROCRYPT \'02) introduced the notion of bounded-collusion IBE (BC-IBE), where attackers only learn secret keys of an a-priori bounded number t of identities. They provided a generic BC-IBE construction from any semantically-secure encryption scheme which, however, suffers from a ω(t) blow-up in ciphertext size. Goldwasser et al. (TCC 2012) recently presented a generic construction with no ciphertext-length blow-up. Their construction requires an underlying public-key scheme with a key homomorphism, as well as a hash-proof-style security definition that is strictly stronger than semantic security. This latter requirement in particular reduces the applicability of their construction to existing schemes.

In this paper, we present the first generic constructions of BC-IBE from semantically-secure encryption schemes with no ciphertext-length blow-up. Our constructions require different degrees of key-homomorphism and malleability properties that are usually easy to verify. We provide concrete instantiations based on the DDH, QR, NTRU, and LWE assumptions. For all of these assumptions, our schemes present the smallest BC-IBE ciphertext size known to date. Our NTRU-based construction is particularly interesting, due to the lack of NTRU- based IBE constructions as well as the fact that it supports fully-homomorphic evaluation. Our results also yield new constructions of bounded CCA-secure cryptosystems.

We conduct a theoretical and practical comparison of two Ring-LWE-based, scale-invariant, leveled homomorphic encryption schemes -- Fan and Vercauteren\'s adaptation of BGV and the YASHE scheme proposed by Bos, Lauter, Loftus and Naehrig. In particular, we explain how to choose parameters to ensure correctness and security against lattice attacks. Our parameter selection improves the approach of van de Pol and Smart to choose parameters for schemes based on the Ring-LWE problem by using the BKZ-2.0 simulation algorithm.

We implemented both schemes in C++, using the arithmetic library FLINT, and compared them in practice to assess their respective strengths and weaknesses. In particular, we performed a homomorphic evaluation of the lightweight block cipher SIMON. Combining block ciphers with homomorphic encryption allows to solve the gargantuan ciphertext expansion in cloud applications.

Recently, Baseri et al. proposed a secure untraceable off-line electronic cash system. They claimed that their scheme could achieve security requirements of an e-cash system such as, untraceability, anonymity, unlinkability, double spending checking, un-forgeability, date-attachability, and prevent forging coins. They further prove the un-forgeability security feature by using the hardness of discrete logarithm problems. However, after cryptanalysis, we found that the scheme cannot attain the security feature, untraceability. We, therefore, modify it to comprise this desired requirement, which is very important in an e-cash system.

We give a polynomial time attack on the McEliece public key cryptosystem based on algebraic geometry codes. Roughly speaking, this attacks runs in $O(n^4)$ operations in $\\mathbb F_q$, where $n$ denotes the code length. Compared to previous attacks, allows to recover a decoding algorithm for the public key even for codes from high genus curves.

we propose an elegant memory-hard proof-of-work system based on cuckoo hashing

Name: Claude Carlet

Name: Abdelaziz Elaabid
Topic: Side channel attacks: advanced experimentations on template attacks
Category: secret-key cryptography

Description: In the 90\'s, the emergence of new cryptanalysis methods revolutionized the security of cryptographic devices. These attacks are based on power consumption analysis, when the microprocessor is running the cryptographic algorithm. Especially, we analyse in this thesis some properties of the template attack, with examples from attacks against an unprotected ASIC implementation. We point out that the efficiency of template attacks can be unleashed by using a relevent power model, and we provide some practical improvements by the use of different signal processing techniques. Furthermore, we investigate the relevance of the theoretical framework on profiled SCAs presented by F.-X. Standaert et al. at Eurocrypt 2009. The analyse consists in a case-study based on side-channel measurements acquired experimentally from a hardwired cryptographic accelerator. Therefore, with respect to previous formal analyses carried out on software measurements or on simulated data, the investigations we describe are more complex, due to the underlying chip\'s architecture and to the large amount of algorithmic noise.In this context, we explore the appropriateness of different choices for the sensitive variables, and we show that a skilled attacker aware of the register transfers occurring during the cryptographic operations can select the most adequate distinguisher, thus increasing its success rate. The principal component analysis (PCA) is used to represent the templates in some dimensions, and we give a physical interpretation of the templates eigenvalues and eigenvectors. We introduce a method based on the thresholding of leakage data to accelerate the profiling or the matching stages. This method empowers an attacker, in that it saves traces when converging towards correct values of the secret. Concretely, we demonstrate a 5 times speed-up in the on-line phase of the attack. Also, it has been underlined that the various samples garnered during the same acquisition can carry complement[...]

Department of Applied Mathematics and Computer Science, Technical University of Denmark, would like to invite applications for a Postdoc position of 18 months, starting 1 April 2014 or soon thereafter. The topic of the project is lightweight cryptology, which regards scenarios involving strongly resource-constrained devices.

Candidates for the position should have a solid background in hardware design and automation and be able to work on the physical constraints and optimization of the hardware implementations or, alternatively, we will consider candidates with a strong cryptanalytic and mathematical background who are able to analyse the security of ciphers to be designed.

The Chair for Information Security and Cryptography at the University of Trier, Germany, offers

a full-time position for a postdoctoral researcher

in a project funded by the German Research Foundation (DFG). The goal of the project is to develop methods for the modular analysis of real-world cryptographic protocols, such as TLS, SSH, WPA2, etc., based on the approach of universal composability, and to apply the developed methods to such protocols.

The position is available immediately, with an internationally competitive salary. The starting date is negotiable. Contracts can initially be offered for up to three years, with the perspective of an extension.

There are no teaching obligations.

The successful candidate must have a Master`s degree (or an equivalent degree) in Computer Science, Mathematics, or a related discipline, and have completed, or be near completion of a PhD degree relevant to the research area of the project. You should have a proven high level of analytical capability and mathematical skills. Good English skills are expected; knowledge of German is not required.

Applications will be considered until the position is filled.

FIDES is a lightweight authenticated cipher, presented at CHES 2013.

The cipher has two version, providing either 80-bit or 96-bit

security. In this paper, we describe internal state-recovery attacks

on both versions of FIDES, and show that once we recover the internal

state, we can use it to immediately forge any message. Our attacks are

based on a guess-and-determine algorithm, exploiting the slow

diffusion of the internal linear transformation of FIDES. Our most

basic attacks have time complexities of 2^{75} and 2^{90} for FIDES-80

and FIDES-96, respectively, use a very small amount of memory, and

their most distinctive feature is their very low data complexity: the

attacks require at most 24 bytes of an arbitrary plaintext and its

corresponding ciphertext, in order to break the cipher with

probability 1. In addition to the basic attacks, we describe optimized

attacks which exploit additional data in order to reduce the time

complexities to 2^{73} and 2^{88} for FIDES-80 and FIDES-96,

respectively.

We show that a Magma implementation of Joux\'s new L[1/4] algorithm

can be used to compute discrete logarithms in the 1303-bit finite field

F_{3^{6*137}} with very modest computational resources.

Our implementation illustrates the effectiveness of Joux\'s algorithm

for computing discrete logarithms in small-characteristic finite

fields which are not Kummer or twisted-Kummer extensions.

Securing cryptographic implementations against side-channel attacks is one of the most important challenges in modern cryptography. Many countermeasures have been introduced for this purpose, and analyzed in specialized security models. Formal solutions have also been proposed to extend the guarantees of provable security to physically observable devices. Masking and leakage-resilient cryptography are probably the most investigated and best understood representatives of these two approaches. Unfortunately, claims whether one, the other or their combination provides better security at lower cost remained vague so far. In this paper, we provide the first comprehensive treatment of this important problem. For this purpose, we analyze whether cryptographic implementations can be security-bounded, in the sense that the time complexity of the best side-channel attack is lower-bounded, independent of the number of measurements performed. Doing so, we first put forward a significant difference between stateful primitives such as leakage-resilient PRGs (that easily ensure bounded security), and stateless ones such as leakage-resilient PRFs (that hardly do). We then show that in practice, leakage-resilience alone provides the best security vs. performance tradeoff when bounded security is achievable, while masking alone is the solution of choice otherwise. That is, we highlight that~one (x)or the other approach should be privileged, which contradicts the usual intuition that physical security is best obtained by combining countermeasures.

Besides, our experimental results underline that despite defined in exactly the same way, the bounded leakage requirement in leakage-resilient PRGs and PRFs imply significantly different challenges for hardware designers. Namely, such a bounded leakage is much harder to guarantee for stateless primitives (like PRFs) than for statefull ones (like PRGs). As a result, constructions of leakage-resilient PRGs and PRFs proven under the same bounded leakage assumption, and instantiated with the same AES implementation, may lead to different practical security levels.

We consider the Fourier Entropy-Influence (FEI) conjecture in the context of cryptographic Boolean functions. We show that the FEI conjecture is true for the functions satisfying the strict avalanche criterion, which forms a subset of asymptotic log--density~$1$ in the set of all Boolean functions. Further, we prove that the FEI conjecture is satisfied for plateaued Boolean functions, monomial algebraic normal form (with the best involved constant), direct sums, as well as concatenations of Boolean functions. As a simple consequence of these general results we find that each affine equivalence class of quadratic Boolean functions contains at least one function satisfying the FEI conjecture. Further, we propose some ``leveled\'\' FEI conjectures.

Chuang and Chen propose an anonymous multi server authenticated key agreement scheme based on trust computing using smart card, password, and biometrics. Chuang and Chen say that this scheme not only supports multi-server but also achieves security requirements. but this scheme is vulnerable to masquerade attack, smart card attack, DoS attack and insufficient for perfect forward secrecy. To solve problems, this paper proposes security enhanced anonymous multi server authenticated key agreement scheme using smart card and biometrics.

So far, low probability differentials for the key schedule of block ciphers have been used as a straightforward proof of security against related-key differential attacks. To achieve the resistance, it is believed that for cipher with $k$-bit key it suffices the upper bound on the probability to be $2^{-k}$. Surprisingly, we show that this reasonable assumption is incorrect, and the probability should be (much) lower than $2^{-k}$. Our counter example is a related-key differential analysis of the block cipher CLEFIA-128. We show that although the key schedule of CLEFIA-128 prevents differentials with a probability higher than $2^{-128}$, the linear part of the key schedule that produces the round keys, and the Feistel structure of the cipher, allow to exploit particularly chosen differentials with a probability as low as $2^{-128}$. CLEFIA-128 has $2^{14}$ such differentials, which translate to $2^{14}$ pairs of weak keys. The probability of each differential is too low for attacks, but the weak keys have a special structure which allows with a divide-and-conquer approach to gain advantage of $2^7$ over generic attacks. We exploit the advantage and give a membership test for the weak-key class,

provide analysis in the hashing mode, and show the importance for the secret-key mode. The proposed analysis has been tested with computer experiments on small-scale variants of CLEFIA-128.

Our results do not threaten the practical use of CLEFIA.

Name: Constantin Catalin Dragan
Topic: Security of CRT-based Secret Sharing Schemes
Category: (no category)

Description:

The Chinese Remainder Theorem (CRT) is a very useful tool in many areas of theoretical and practical cryptography. One of these areas is the theory of threshold secret sharing schemes. A (t+1,n)-threshold secret sharing scheme is a method of partitioning a secret among n users by providing each user with a share of the secret such that any t+1 users can uniquely reconstruct the secret by pulling together their shares. Several threshold schemes based on CRT are known. These schemes use sequences of pairwise co-prime positive integers with special properties. The shares are obtained by dividing the secret or a secret-dependent quantity by the numbers in the sequence and collecting the remainders. The secret can be reconstructed by some sufficient number of shares by using CRT. It is well-known that the CRT-based threshold secret sharing schemes are not perfect (and, therefore, not ideal) but some of them are asymptotically perfect and asymptotically ideal and perfect zero-knowledge if sequences of consecutive primes are used for defining them.

\r\n\r\n

\r\nIn this thesis we introduce (k-)compact sequences of co-primes and their applications to the security of CRT-based threshold secret sharing schemes is thorough investigated. Compact sequences of co-primes may be significantly denser than sequences of consecutive primes of the same length, and their use in the construction of CRT-based threshold secret sharing schemes may lead to better security properties. Concerning the asymptotic idealness property for CRT-based threshold schemes, we have shown there exists a necessary and sufficient condition for the Goldreich-Ron-Sudan (GRS) scheme and Asmuth-Bloom scheme if and only if (1-)compact sequences of co-primes are used. Moreover, the GRS and Asmuth-Bloom schemes based on k-compact sequences of co-primes are asymptotically perfect and perfect zero-knowledge. The Mignotte scheme is far from being asymptotically perfect [...]