International Association
for Cryptologic Research

The learning with rounding problem (LWR) has become a popular cryptographic assumption to study recently due to its determinism and resistance to known quantum attacks. Unfortunately, LWR is only known to be provably hard for instances of the problem where the LWR modulus $q$ is at least as large as some polynomial function of the number of samples given to an adversary, meaning LWR is provably hard only when (1) an adversary can only see a fixed, predetermined amount of samples or (2) the modulus $q$ is superpolynomial in the security parameter, meaning that the hardness reduction is from superpolynomial approximation factors on worst-case lattices.

In this work, we show that there exists a (still fully deterministic) variant of the LWR problem that allows for both unbounded queries and a polynomial modulus $q$, breaking an important theoretical barrier. To our knowledge, our new assumption, which we call the "nearby learning with lattice rounding problem" (NLWLR), is the first fully deterministic version of the learning with errors (LWE) problem that allows for both unbounded queries and a polynomial modulus. We note that our assumption is not practical for any kind of use and is mainly intended as a theoretical proof of concept to show that provably hard deterministic forms of LWE can exist with a modulus that does not grow polynomially with the number of samples.

In this paper we consider linear secret sharing schemes over a finite field $\mathbb{F}_q$, where the secret is a vector in $\mathbb{F}_q^\ell$ and each of the $n$ shares is a single element of $\mathbb{F}_q$. We obtain lower bounds on the so-called threshold gap $g$ of such schemes, defined as the quantity $r-t$ where $r$ is the smallest number such that any subset of $r$ shares uniquely determines the secret and $t$ is the largest number such that any subset of $t$ shares provides no information about the secret. Our main result establishes a family of bounds which are tighter than previously known bounds for $\ell\geq 2$. Furthermore, we also provide bounds, in terms of $n$ and $q$, on the partial reconstruction and privacy thresholds, a more fine-grained notion that considers the amount of information about the secret that can be contained in a set of shares of a given size. Finally, we compare our lower bounds with known upper bounds in the asymptotic setting.

White-box cryptography protects key extraction from software implementations of cryptographic primitives. It is widely deployed in DRM and mobile payment applications in which a malicious attacker might control the entire execution environment. So far, no provably secure white-box implementation of AES has been put forward, and all the published practical constructions are vulnerable to differential computation analysis (DCA) and differential fault analysis (DFA). As a consequence, the industry relies on home-made obscure white-box implementations based on secret designs. It is therefore of interest to investigate the achievable resistance of an AES implementation to thwart a white-box adversary in this paradigm. To this purpose, the ECRYPT CSA project has organized the WhibOx contest as the catch the flag challenge of CHES 2017. Researchers and engineers were invited to participate either as designers by submitting the source code of an AES-128 white-box implementation with a freely chosen key, or as breakers by trying to extract the hard-coded keys in the submitted challenges. The participants were not expected to disclose their identities or the underlying designing/attacking techniques. In the end, 94 submitted challenges were all broken and only 13 of them held more than 1 day. The strongest (in terms of surviving time) implementation, submitted by Biryukov and Udovenko, survived for 28 days (which is more than twice as much as the second strongest implementation), and it was broken by a single team, i.e., the authors of the present paper, with reverse engineering and algebraic analysis. In this paper, we give a detailed description of the different steps of our cryptanalysis. We then generalize it to an attack methodology to break further obscure white-box implementations. In particular, we formalize and generalize the linear decoding analysis that we use to extract the key from the encoded intermediate variables of the target challenge.

PBKDF2 [27] is a well-known password-based key derivation function. In order to slow attackers down, PBKDF2 introduces CPU-intensive operations based on an iterated pseudorandom function (in our case HMAC-SHA-1). If we are able to speed up a SHA-1 or an HMAC implementation, we are able to speed up PBKDF2-HMAC-SHA-1. This means that a performance improvement might be exploited by regular users and attackers. Interestingly, FIPS 198-1 [31] suggests that it is possible to precompute first message block of a keyed hash function only once, store such a value and use it each time is needed [43]. Therefore the computation of first message block does not contribute to slowing attackers down, thus making the computation of second message block crucial. In this paper we focus on the latter, investigating the possibility to avoid part of the HMAC-SHA-1 operations. We show that some CPU-intensive operations may be replaced with a set of equivalent, but less onerous, instructions. We identify useless XOR operations exploiting and extending Intel optimizations [26], and applying the Boyar-Peralta heuristic [12]. In addition, we provide an alternative method to compute the SHA-1 message scheduling function and explain why attackers might exploit these findings to speed up a brute force attack.

Suppose that $N$ players share cryptocurrency using an M-of-N multisig scheme. If N-M+1 players disappear, the remaining ones have a problem: They’ve permanently lost their funds. We introduce Paralysis Proofs. A Paralysis Proof is a proof that players cannot act in concert, e.g., some players have become unavailable. Paralysis Proofs can support the construction of a Paralysis Proof System, which helps maintain resource availability by updating (e.g., downgrading) the resource’s access structure when critical players, i.e., key-share holders, become unavailable. We present a very general Paralysis Proof System implementation that combines trusted hardware, specifically Intel SGX, with a censorship-resistant channel in the form of a blockchain. Active players may issue a challenge to inactive or missing ones. A failure to respond in a timely way, as recorded on the blockchain, generates a Paralysis Proof that authorizes the trusted hardware to change the access structure, for instance, to allow cryptocurrency to be spent without the missing players. Paralysis Proofs help address a pervasive key-management problem in cryptocurrencies and many other settings. We present specific instantiations for Ethereum (without trusted hardware) and for Bitcoin (with and without trusted hardware). We show that for any cryptocurrency system, versions with trusted hardware can be far more efficient than those without. We also show how extensions of our techniques can encompass a rich array of access-structure policies addressing problems well beyond paralysis.

Differential computation analysis (DCA) is a technique recently introduced by Bos et al. and Sanfelix et al. for key recovery from whitebox implementations of symmetric ciphers. It consists in applying the differential power analysis approach to software execution traces that are obtained by tracing the memory accesses of a whitebox application. While being very effective, DCA relies on analyst intuition to be efficient. In particular, memory range selection is needed to prevent software execution traces from becoming prohibitively long. Moreover, analyst failure to specify the relevant range lets the vulnerable whitebox implementation be evaluated as secure.

We present a novel approach for dimensionality reduction of software execution traces, that takes a significant part of analyst intuition out of the loop. The approach exploits the lack of measurement noise in the traces and selects only the samples that are relevant for the key recovery. Our experiments with the published whitebox implementations show that the length of software execution traces can be automatically reduced to a few dozens of bits. This results in an attack speedup of several orders of magnitude, which in turn facilitates the use of more computationally intensive DCA flavours such as multiple leakage targets proposed by Klemsa.

Our approach simplifies the methodology for whitebox analysis down to the tracing of a large default memory range, letting our dimensionality reduction techniques extract the relevant points for DCA, and run the attack on multiple leakage targets, excluding analyst errors and saving analysis time. It also provides quick insights in case of whitebox implementations with additional protection layers such as encodings, and can be used to identify the range for fault injection in differential fault analysis.

We make our techniques available to the community as a part of a free/libre open-source side channel analysis toolkit. We believe they are a step forward for fully automated whitebox analysis tools.

This paper presents the basic concepts of the Edwards curves, twisted Edwards curves and the point addition laws on these curves. The main result is the parameterization of the Edward curve with the given torsion subgroup in the rational field Q.

Levillain et al. (AsiaCCS 2015) proposed two cookie masking methods, TLS Scramble and MCookies, to counter a class of attacks on SSL/TLS in which the attacker is able to exploit its ability to obtain many encryptions of a target HTTP cookie. In particular, the masking methods potentially make it viable to continue to use the RC4 algorithm in SSL/TLS. In this paper, we provide a detailed analysis of TLS Scramble and MCookies when used in conjunction with RC4 in SSL/TLS. We show that, in fact, both are vulnerable to variants of the known attacks against RC4 in SSL/TLS exploiting the Mantin biases (Mantin, EUROCRYPT 2005):

* For the TLS Scramble mechanism, we provide a detailed statistical analysis coupled with extensive simulations that show that about $2^{37}$ encryptions of the cookie are sufficient to enable its recovery.

* For the MCookies mechanism, our analysis is made more complex by the presence of a Base64 encoding step in the mechanism, which (unintentionally) acts like a classical block cipher S-box in the masking process. Despite this, we are able to develop a maximum likelihood analysis which provides a rigorous statistical procedure for estimating the unknown cookie. Based on simulations, we estimate that $2^{45}$ encryptions of the cookie are sufficient to enable its recovery.

Taken together, our analyses show that the cookie masking mechanisms as proposed by Levillain et al. only moderately increase the security of RC4 in SSL/TLS.

In this paper we focus on S-box constructions. We consider the uniformity property of an S-box which plays an important role in Threshold Implementations (TI). Most papers so far have studied TI sharings for given S-boxes. We proceed in the opposite way: starting from $n$-bit S-boxes with known sharings we construct new $(n+1)$-bit S-boxes from them with the desired sharings. In addition, we investigate the self-equivalency of S-boxes and show some interesting properties.

When implementing a cryptographic algorithm, efficient operations have high relevance both in hardware and software. Since a number of operations can be performed via polynomial multiplication, the arithmetic of polynomials over finite fields plays a key role in real-life implementations. One of the most interesting paper that addressed the problem has been published in 2009. In [5], Bernstein suggests to split polynomials into parts and presents a new recursive multiplication technique which is faster than those commonly used. In order to further reduce the number of bit operations [6] required to multiply n-bit polynomials, researchers adopt different approaches. In [18] a greedy heuristic has been applied to linear straight-line sequences listed in [6]. In 2013, D'angella, Schiavo and Visconti [20] skip some redundant operations of the multiplication algorithms described in [5]. In 2015, Cenk, Negre and Hasan [12] suggest new multiplication algorithms. In this paper, (a) we present a "k-1"-level Recursion algorithm that can be used to reduce the effective number of bit operations required to multiply n-bit polynomials; and (b) we use algebraic extensions of F_2 combined with Lagrange interpolation to improve the asymptotic complexity.

By allowing a large number of users to behave as readers or writers, Multi-User Searchable Encryption (MUSE) raises new security and performance challenges beyond the typical requirements of Symmetric Searchable Encryption (SSE). In this paper we identify two core mandatory requirements of MUSE protocols being privacy in face of users colluding with the CSP and low complexity for the users, pointing that no existing MUSE protocol satisfies these two requirements at the same time. We then come up with the first MUSE protocol that satisfies both of them. The design of the protocol also includes new constructions for a secure variant of Bloom Filters (BFs) and multi-query Oblivious Transfer (OT).

Security and privacy are important requirements for the broad deployment of intelligent transportation systems (ITS). This motivated the development of many proposals aimed at creating a Vehicular Public Key Infrastructure (VPKI) for addressing such needs. Among them, schemes based on pseudonym certificates are considered particularly prominent: they provide data authentication in a privacy-preserving manner while allowing vehicles to be revoked in case of misbehavior. Indeed, this is the approach followed by the Security Credential Management System (SCMS), one of the leading candidate designs for protecting vehicular communications in the United States. Despite SCMS's appealing design, in this article we show that it still can be further improved. Namely, one of the main benefits of SCMS is its so-called butterfly key expansion process, which allows batches of pseudonym certificates to be issued for authorized vehicles by means of a single request. Whereas this procedure requires the vehicle to provide two separate public/private key pairs for registration authorities, we present a modified protocol that uses a single key for the same purpose. As a result, the processing and bandwidth costs of the certificate provisioning protocol drop as far as 50%. Such performance gains come with no negative impact in terms of security, flexibility or scalability when compared to the original SCMS.

In previous work I proposed a fully homomorphic encryption without bootstrapping which has the large size of ciphertext. This tme I propose the fully homomorphic public-key encryption scheme on non-associative octonion ring over finite field with the small size of ciphertext. In this scheme the size of ciphertext is one-third of the size in the scheme proposed before. Because proposed scheme adopts the medium text with zero norm, it is immune from the “p and -p attack”. As the proposed scheme is based on computational difficulty to solve the multivariate algebraic equations of high degree, it is immune from the Gröbner basis attack, the differential attack, rank attack and so on.

The list of papers accepted to Eurocrypt 2018 is now available at https://eurocrypt.iacr.org/2018/acceptedpapers.html

We are also glad to announce the following award winners:

Best Young Researcher Paper Award
The Discrete-Logarithm Problem with Preprocessing
Henry Corrigan-Gibbs (Stanford University)
Dmitry Kogan (Stanford University)

Best Paper Award
Simple Proofs of Sequential Work
Bram Cohen (Chia Network)
Krzysztof Pietrzak (IST Austria)

Best Paper Award
Two-Round Multiparty Secure Computation from Minimal Assumptions
Sanjam Garg (University of California, Berkeley)
Akshayaram Srinivasan (University of California, Berkeley)

Best Paper Award
k-Round MPC from k-Round OT via Garbled Interactive Circuits
Fabrice Benhamouda (IBM Research, Yorktown Heights)
Huijia Lin (University of California, Santa Barbara)

Event date: 18 June to 20 June 2018
Submission deadline: 1 March 2018
Notification: 2 April 2018

Event date: 4 June 2018
Submission deadline: 29 January 2018
Notification: 10 March 2018

Event date: 30 September to 3 October 2018

Event date: 8 July to 13 July 2018
Submission deadline: 1 February 2018
Notification: 15 March 2018

Event date: 3 December to 4 December 2018
Submission deadline: 22 June 2018
Notification: 22 August 2018

This is a “rolling advert” with a nominal closing date of 31 March 2018. Applications are welcome at any time and the timing of the selection process will be dependent on the applications received.

Disclaimer: This position is funded by HM Government and is available only to UK citizens.

Surrey Centre for Cyber Security (SCCS) at the University of Surrey invites applications for a fully-funded PhD position in Cryptography to work on a research project focusing on the design, analysis and development of multi-factor authentication protocols.

The successful candidate will be working under supervision of Dr Mark Manulis (Principal Supervisor, http://www.manulis.eu) and Dr Thanassis Giannetsos (Co-Supervisor).

Successful applicants are expected to hold Bachelor degree or Master degree in Information Security, Computer Science, Mathematics or related discipline accomplished with at least 2:1 honours and have strong background knowledge and technical skills (incl. programming skills) in cryptography and/or information/cyber security. A related research-oriented BSc final year project or MSc dissertation will strengthen the profile of the candidate. We particularly welcome applications from ongoing students who are projected to fulfil the above criteria and complete their degree in 2018.

The appointed candidate will receive a tax-free PhD stipend of GBP 22,000 per year for 3.5 years of PhD studies within which the candidate is expected to submit their PhD thesis. This stipend is significantly higher than an average PhD stipend in the UK. Additional funding is available to support presentation of research results at international conferences, participation in PhD summer schools and other scientific events, and engagement with industry.

Prior to submitting your application please contact us by email.

Closing date for applications: 31 March 2018

Contact: Mark Manulis
m.manulis (at) surrey.ac.uk

More information: https://jobs.surrey.ac.uk/vacancy.aspx?ref=007418