International Association
for Cryptologic Research

In the ordinary security model for signature schemes, we consider an adversary that may forge a signature on a new message using only his knowledge of other valid message and signature pairs. To take into account side channel attacks such as tampering or fault-injection attacks, Bellare and Kohno (Eurocrypt 2003) formalized related-key attacks (RKA), where stronger adversaries are considered. In RKA for signature schemes, the adversary can also manipulate the signing key and obtain signatures for the modified key. This paper considers RKA security of two established signature schemes: the Schnorr signature scheme and (a well-known variant of) DSA. First, we show that these signature schemes are secure against a weak notion of RKA. Second, we demonstrate that, on the other hand, neither the Schnorr signature scheme nor DSA achieves the standard notion of RKA security, by showing concrete attacks on these. Lastly, we show that a slight modification of both the Schnorr signature scheme and (the considered variant of) DSA yields fully RKA secure schemes.

The notion of multi-input functional encryption (MI-FE) was recently introduced by Goldwasser et al. [EUROCRYPT\'14] as a means to non-interactively compute aggregate information on the joint private data of multiple users. A fundamental limitation of their work, however, is that the total number of users (which corresponds to the arity of the functions supported by the MI-FE scheme) must be a priori bounded and fixed at the system setup time.

In this work, we overcome this limitation by introducing the notion of unbounded input MI-FE that supports the computation of functions with unbounded arity. We construct such an MI-FE scheme with indistinguishability security in the selective model based on the existence of public-coin differing-inputs obfuscation for turing machines and collision-resistant hash functions.

Our result enables several new exciting applications, including a new paradigm of on-the-fly secure multiparty computation where new users can join the system dynamically.

In this paper, we study the security of multi-prime RSA whose modulus is N=p_1p_2...p_r for r>=3 with small prime difference of size N^\\gamma. In ACISP 2013, Zhang and Takagi showed a Fermat-like factoring attack, which can directly factor N for \\gamma

Job Responsibilities:

•To develop cryptographic protocols and schemes.

•To develop secure cloud computing systems.

•To design, analyze and implement security systems and e-commerce systems.

Requirements

•Master’s degree in Computer Science, Electronic Engineering or other relevant disciplines with 3+ years experience; less experience for PhD holders.

•Experience in cryptographic system design and cryptanalysis.

•Deep knowledge on number theory and security proofs.

•Hands-on experience with C/C++ and Java.

•Preferably having experiences on using cryptographic libraries such as OpenSSL, MIRACL, PBC, etc.

•Experience in developing cloud computing systems an advantage, but not a must.

•Strong interpersonal and communications skills.

•Good command of both written and spoken English.

Within the Cryptography Group at the University of Bristol (http://www.cs.bris.ac.uk/Research/CryptographySecurity/) , we are looking to expand our side channel activities in the areas of programming language and compiler extensions (to support side channel aware implementation techniques), analysis of newly proposed elliptic curves and related signature standards, attacks on complex devices, and implementations of (hardware) countermeasures. To be eligible for funding students must normally either be UK or EU citizens, and have lived in the UK for at least 3 years prior to the start of the studentship.

We have an active and well funded side channel community within the Cryptography Group, working on both theoretical aspects and practical attacks. Our lab features state of the art equipment and we benefit from friendly relationships to both local as well as international companies and institutions with an interest in all aspects of side channel research. Any new student will have rich opportunities for their development alongside making contacts within the wider cryptographic community.

If you are interested then please get in touch as soon as possible by an email to the contact below containing a transcript, and/or (predicted) degree classification, alongside some information about any final year project that you have finished (or are currently working on), and internships you may have concluded.

Low-cost resource-constrained devices can allocate very limited resources for implementing security. At the same time, they still require some level of protection. In this paper, we present a lightweight message authentication scheme based on Cyclic Redundancy Check (CRC). The presented CRC inherits the implementation simplicity of the conventional CRC checksum except that the LFSR implementing its encoding and decoding is made re-programmable. Similarly to previously proposed cryptographic CRCs, it detects both random and malicious errors without increasing bandwidth. The main difference from previous approaches is that we use arbitrary instead of irreducible generator polynomials. This eliminates the need for irreducibility tests. We provide a detailed quantitative analysis of the achieved security as a function of message and CRC sizes. The results show that the presented scheme is particularly suitable for the authentication of short messages.

Secret sharing schemes with general monotone access structures have been widely discussed in the literature. But in some scenarios, non-monotone access structures may have more practical significance. In this paper, we shed a new light on secret sharing schemes realizing general (not necessarily monotone) access structures. Based on an attack model for secret sharing schemes with general access structures, we redefine perfect secret sharing schemes, which is a generalization of the known concept of perfect secret sharing schemes with monotone access structures. Then, we provide for the first time two constructions of perfect secret sharing schemes with general access structures. The first construction can be seen as a democratic scheme in the sense that the shares are generated by the players themselves.

Our second construction significantly enhance the efficiency of the system, where the shares are distributed by the trusted center (TC).

The Modular Inversion Hidden Number Problem (MIHNP) was introduced by

Boneh, Halevi and Howgrave-Graham in Asiacrypt 2001 (BHH\'01). They provided

two heuristics - in Method I, two-third of the output bits are required to solve the

problem, whereas the more efficient heuristic (Method II) requires only one-third of

the bits of the output. After more than a decade, here Sarkar in [28] identified that

the claim in Method II is actually not correct and a detailed calculation justified that

this method too requires two-third of the bits of the output, contrary to the claim in

BHH\'01. He reconstructed the lattice and give a bound which heuristically solve with

half of the output bits. Although J.Xu et al in [29] solved it with only one-third of the

output bits asymptotically but that technique is difficult to understand and implement.

Here we essentially use similar idea of [28] but in a clever way such that it is a better

bound although we solve the problem heuristically with only half of the output bits in

asymptotic sense. This is lot easier to understand and implement.

Also experimental results support the claim corresponding to our heuristics. In the last

section we actually talk about a variant of this which seems to be hard to solve under

lattice attack.

Interference between processes executing on shared hardware can be used to mount performance-degradation attacks. However, in most cases, such attacks offer little benefit for the adversary. In this paper, we show that performance-degradation attacks can be used to amplify side-channel leaks, enabling the adversary to increase both the amount and the quality of information captured.

We describe a new microarchitectural performance-degradation attack that can slow victims down by a factor of over 150. We identify a new information leak in the OpenSSL implementation of the ECDSA digital signature algorithm. We show how to use the performance-degradation attack to amplify a side-channel enough to enable exploiting the new information leak. Using the combined attack, an adversary can break a private key of the secp256k1 curve, used in the Bitcoin protocol, after observing only 6 signatures. This result is over four times better than any previously described attack.

From March 17 to March 19
Location: Bochum, Germany
More Information: http://fse.rub.de/summerschool/

Submission: 31 March 2016
Notification: 27 May 2016
From September 12 to September 14
Location: Tokyo, Japan
More Information: http://http://www.iwsec.org/2016/

After some discussion with my colleagues, we suspect that the proposed scheme is not transcript secure as it is vulnerable against the averaging attack from Gentry-Szydlo: see section 4.3 from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.135.3088&rep=rep1&type=pdf A message m is hashed into a ring element c. Then the signature is \\sigma = s*c+p*e over the ring, where s is the signing key, p is a small modular and e is the error follows Gaussian distribution. If you have enough pairs of (c_i, \\sigma_i = s*c_i+p*e_i) you can compute \\sum sigma_i and expect (\\sum e_i) to be close to 0. This is because e_i follows Gaussian distribution, so when you add a lot of samples from Gaussian distribution, you expect the sum to be very focused on 0. So the attacker knows both \\sum c_i and \\sum sigma_i = s*(\\sum c_i) with a non-negligible probability. Let Sigma = \\sum sigma_i and C = \\sum c_i. The pair of (Sigma, C) allows an attacker to forge a signature for a given message m\'. The attacker do the following: 1. c\' = hash(m\') 2. t = c\'/C 3. sigma\' = Sigma * t + p*e Then (c\', sigma\') is a valid signature satisfying verification formula: a*sigma\' = b * c\' mod p Zhenfei Zhang Security Innovation From: 2015-24-11 19:21:31 (UTC)

To solve the approximate nearest neighbor search problem (NNS) on the sphere, we propose a method using locality-sensitive filters (LSF), with the property that nearby vectors have a higher probability of surviving the same filter than vectors which are far apart. We instantiate the filters using spherical caps of height 1 - A, where a vector survives a filter if it is contained in the corresponding spherical cap, and where ideally each filter has an independent, uniformly random direction.

For small A, these filters are very similar to the spherical locality-sensitive hash (LSH) family previously studied by Andoni et al. For larger A bounded away from 0, these filters potentially achieve a superior performance, provided we have access to an efficient oracle for finding relevant filters. Whereas existing LSH schemes are limited by a performance parameter of P \\geq 1/(2c^2 - 1) to solve approximate NNS with approximation factor c, with spherical LSF we potentially achieve smaller asymptotic values of P, depending on the density of the data set. For sparse data sets where the dimension is super-logarithmic in the size of the data set, we asymptotically obtain P = 1/(2c^2 - 1), while for a logarithmic dimensionality with density constant K we obtain asymptotics of P \\sim 1/(4 K c^2).

To instantiate the filters and prove the existence of an efficient decoding oracle, we replace the independent filters by filters taken from certain structured random product codes. We show that the additional structure in these concatenation codes allows us to decode efficiently using techniques similar to lattice enumeration, and we can find the relevant filters with low overhead, while at the same time not significantly changing the collision probabilities of the filters.

We finally apply spherical LSF to sieving algorithms for solving the shortest vector problem (SVP) on lattices, and show that this leads to a heuristic time complexity for solving SVP in dimension n of (3/2)^{n/2 + o(n)} ~ 2^{0.292 n + o(n)}. This asymptotically improves upon the previous best algorithms for solving SVP which use spherical LSH and cross-polytope LSH and run in time 2^{0.298 n + o(n)}. Experiments with the GaussSieve validate the claimed speedup and show that this method may be practical as well, as the polynomial overhead is small. Our implementation is available under an open-source license.

s2n is an implementation of the TLS protocol that was released in late June 2015 by Amazon. It is implemented in around 6,000 lines of C99 code. By comparison, OpenSSL needs around 70,000 lines of code to implement the protocol. At the time of its release, Amazon announced that s2n had undergone three external security evaluations and penetration tests. We show that, despite this, s2n - as initially released - was vulnerable to a timing attack in the case of CBC-mode ciphersuites, which could be extended to complete plaintext recovery in some settings. Our attack has two components. The first part is a novel variant of the Lucky 13 attack that works even though protections against Lucky 13 were implemented in s2n.

The second part deals with the randomised delays that were put in place in s2n as an additional countermeasure to Lucky 13. Our work highlights the challenges of protecting implementations against sophisticated timing attacks. It also illustrates that standard code audits are insufficient to uncover all cryptographic attack vectors.

Loosely speaking, a family of computational groups is a family (G_d)_{d\\in D} of groups (where D is a set of bit strings) whose elements are represented by bit strings in such a way that equality testing, multiplication, inversion, computing the identity element, and sampling random elements in G_d can be performed efficiently when d is given. A family (G_d)_{d\\in D} of computational groups is called pseudo-free if, given a random index d (for an arbitrary value of the security parameter) and random elements g_1,...,g_m\\in G_d, it is computationally hard to find a system of group equations v_i(a_1,...,a_m;x_1,...,x_n)=w_i(a_1,...,a_m;x_1,...,x_n), i=1,...,s, and elements h_1,...,h_n\\in G_d such that this system of equations is unsatisfiable in the free group freely generated by a_1,...,a_m (over variables x_1,...,x_n), but v_i(g_1,...,g_m;h_1,...,h_n)=w_i(g_1,...,g_m;h_1,...,h_n) in G_d for all i\\in\\{1,...,s\\}. If a family of computational groups satisfies this definition with the additional requirement that n=0, then this family is said to be weakly pseudo-free. The definition of a (weakly) pseudo-free family of computational groups can be easily generalized to the case when all groups in the family belong to a fixed variety of groups.

In this paper, we initiate the study of (weakly) pseudo-free families of computational elementary abelian p-groups, where p is an arbitrary fixed prime. We restrict ourselves to families (G_d)_{d\\in D} of computational elementary abelian p-groups such that for every index d, each element of G_d is represented by a single bit string of length polynomial in the length of d.

First, we prove that pseudo-freeness and weak pseudo-freeness for families of computational elementary abelian p-groups are equivalent. Second, we give some necessary and sufficient conditions for a family of computational elementary abelian p-groups to be pseudo-free (provided that at least one of two additional conditions holds). These necessary and sufficient conditions are formulated in terms of collision-intractability or one-wayness of certain homomorphic families of knapsack functions. Third, we establish some necessary and sufficient conditions for the existence of pseudo-free families of computational elementary abelian p-groups. With one exception, these conditions are the existence of certain homomorphic collision-intractable families of p-ary hash functions or certain homomorphic one-way families of functions.

As an example, we construct a Diffie-Hellman-like key agreement protocol from an arbitrary family of computational elementary abelian p-groups. Unfortunately, we do not know whether this protocol is secure under reasonable assumptions.

From January 25 to January 29
Location: Tenerife, Spain
More Information: http://www.cosic.esat.kuleuven.be/school-iot/venue.shtml

Submission: 15 February 2016
Notification: 1 April 2016
From July 17 to July 22
Location: Longyearbyen, Norway
More Information: http://arcticcrypt.b.uib.no/

In an order-preserving encryption scheme, the encryption algorithm produces

ciphertexts that preserve the order of their plaintexts. Order-preserving

encryption schemes have been studied intensely in the last decade, and yet not

much is known about the security of these schemes. Very recently, Boneh et

al. (Eurocrypt 2015) introduced a generalization of order-preserving

encryption, called order-revealing encryption, and presented a construction

which achieves this notion with best-possible security. Because their

construction relies on multilinear maps, it is too impractical for most

applications and therefore remains a theoretical result.

In this work, we build efficiently implementable order-revealing encryption

from pseudorandom functions. We present the first efficient order-revealing

encryption scheme which achieves a simulation-based security notion with

respect to a leakage function that precisely quantifies what is leaked by the

scheme. Moreover, we show how composing our construction with existing order-

preserving encryption schemes results in order-revealing encryption that is

strictly more secure than all preceding order-preserving encryption schemes.

We present a new oblivious RAM that supports variable-sized storage blocks (vORAM), which is the first ORAM to allow varying block sizes without trivial padding. We also present a new history-independent data structure (a HIRB tree) that can be stored within a vORAM. Together, this construction provides an efficient and practical oblivious data structure (ODS) for a key/value map, and goes further to provide an additional privacy guarantee as compared to prior ODS maps: even upon client compromise, deleted data and the history of old operations remain hidden to the attacker.

We implement and measure the performance of our system using Amazon Web Services, and the single-operation time for a realistic database (up to $2^{18}$ entries) is less than 1 second. This represents a 100x speed-up compared to the current best oblivious map data structure (which provides neither secure deletion nor history independence) by Wang et al. (CCS 14).

We introduce a linear code based on resilient maps on vector spaces over finite fields, we give a basis of this code and upper and lower

bounds for its minimal distance. Then the use of the introduced code

for building vector space secret sharing schemes is explained and an

estimation of the robustness of the schemes against cheaters is provided.