International Association
for Cryptologic Research

The Digital Security Department of EURECOM invites applications for a tenured position at the Assistant Professor level in the area of Security and Privacy for Cloud Computing.

EURECOM hosts one of the most established academic research activities in the field of security and privacy in Europe since more than 20 years. This activity takes place in three dedicated research groups as part of the digital security department. The new faculty is expected to join forces with the Applied Cryptography and Security Protocols Group with his/her expertise in the following fields:

- applied cryptography

- security protocols

- privacy enhancing technologies

geared towards the following application areas:

- security and privacy in cloud computing

- security and privacy in Big Data.

Candidates must have a Ph.D. in computer science or electrical engineering and a proven track record of postdoctoral research in one or several of these areas.

While actively leading research with his/her team, the new faculty is also expected to enhance the resources of the department by raising additional funding. Besides excellence in academic research, he/she must tackle with real life security and privacy problems raised by industrial applications.

The new faculty is also expected to carry out fundamental research and to develop new graduate courses in the aforementioned domains.

Qualified applicants should send a cover letter with a resume including a publication list emphasizing the three most important publications, a statement of proposed research and teaching activities and the names and addresses of three references by e-mail under reference MDCAC2016 to recruitment-mdcsec (at) eurecom.fr. The screening will start on November 1st, 2016 and applications will be accepted until the position is filled.

Closing date for applications: 31 December 2016

Contact: recruitment-mdcsec (at) eurecom.fr

subject: MDCAC2016

More information: http://www.eurecom.fr/en/home?quicktabs_homepage_tabs=2#quicktabs-homepage_tabs

We present the first chosen-ciphertext secure public-key encryption schemes resilient to continuous tampering of arbitrary (efficiently computable) functions. Since it is impossible to realize such schemes without a self-destruction or key-updating mechanism, our proposals allow for either of them. As in the previous works resilient to this type of tampering attacks, our schemes also tolerate bounded or continuous memory leakage attacks at the same time. Unlike the previous works, our schemes have efficient instantiations. We also prove that there is no secure digital signature scheme resilient to arbitrary tampering functions against a stronger variant of the continuous tampering attack, even if it has a self-destruction mechanism.

Motivated by the revelations of Edward Snowden, post-Snowden cryptography has become a prominent research direction in recent years. In Eurocrypt 2015, Mironov and Stephens-Davidowitz proposed a novel concept named cryptographic reverse firewall (CRF) which can resist exfiltration of secret information from an arbitrarily compromised machine. In this work, we continue this line of research and present generic CRF constructions for several widely used cryptographic protocols based on a new notion named malleable smooth projective hash function. Our contributions can be summarized as follows.

We introduce the notion of malleable smooth projective hash function, which is an extension of the smooth projective hash function (SPHF) introduced by Cramer and Shoup (Eurocrypt'02) with the new properties of key malleability and element rerandomizability. We demonstrate the feasibility of our new notion using graded rings proposed by Benhamouda et al. (Crypto'13), and present an instantiation from the k-linear assumption. Moreover, we show that the malleable SPHF can also be based on other standard assumptions.

We show how to generically construct CRFs via malleable SPHFs in a modular way for some widely used cryptographic protocols. Specifically, we propose generic constructions of CRFs for the unkeyed message-transmission protocol and the oblivious signature-based envelope (OSBE) protocol of Blazy, Pointcheval and Vergnaud (TCC'12). We also present a new malleable SPHFfrom the linear encryption of valid signatures for instantiating the OSBE protocol with CRFs.

We further study the two-pass oblivious transfer (OT) protocol and show that the malleable SPHF does not suffice for its CRF constructions. We then develop a new OT framework from graded rings and show how to construct OT-CRFs by modifying the malleable SPHF framework. This new framework encompasses the DDH-based OT-CRF constructions proposed by Mironov and Stephens-Davidowitz (Eurocrypt'15), and yields a new construction under the $k$-linear assumption.

Event date: 7 January to 12 January 2017

Event date: 29 January to 1 February 2017
Submission deadline: 30 September 2016
Notification: 21 November 2016

Event date: 5 June to 9 June 2017

The indistinguishability security of a public-key cryptosystem can be reduced to a computational hard assumption in the random oracle model, where the solution to a computational hard problem is hidden in one of the adversary's queries to the random oracle. Usually, there is a finding loss in finding the correct solution from the query set, especially when the decisional variant of the computational problem is also hard. The problem of finding loss must be addressed towards tight(er) reductions under this type. In EUROCRYPT 2008, Cash, Kiltz and Shoup proposed a novel approach using a trapdoor test that can solve the finding loss problem. The simulator can find the correct solution with overwhelming probability 1, if there exists a trapdoor test for the adopted hard problem. The proposed approach is efficient and can be used for many Diffie-Hellman computational assumptions. The only limitation is the requirement of a trapdoor test that must be found for the adopted computational assumptions.

In this paper, we introduce a universal approach for finding loss, namely Iterated Random Oracle, which can be applied to all computational assumptions. The finding loss in our proposed approach is very small. For $2^{60}$ queries to the random oracle, the success probability of finding the correct solution from the query set will be as large as $1/{64}$ compared to $1/{2^{60}}$ by a random pick. We show how to apply the iterated random oracle for security transformation from key encapsulation mechanism with one-way security to normal encryption with indistinguishability security. The security reduction is very tight due to a small finding loss. The transformation does not expand the ciphertext size. We also give the application of the iterated random oracle in the key exchange.

We present a radical solution to the two foremost challenges facing ``blockchain''-based cryptocurrencies: (1) ``mining pool'' oligopolies and (2) incompressibility of delays affecting validation. Both problems stem from the Blockchain mechanism itself, which drives participants into a winner-takes-all global contest that amounts to a low-odds high-variance rewards lottery.

Our proposal strips out the ``blocks''-&-``chain'' consolidation mechanism, instead repurposing the atomic transactions as the only system objects. A fully distributed proof of work, coupled with progressive and predictable rewards, is efficiently layered on top of the transaction structure. Without blocks, the cryptographic ``chain'' of transaction affirmations turns into a directed graph, whose sparseness, timely growth and global convergence are steered by game-theoretic incentives.

The transaction affirmation process is _cooperative_ (rather than competitive), to entice all participants to work _solitarily_ at their own pace, rather than in pools at the pace of a blockchain.

In the absence of blocks, we develop a framework that enjoys better decentralisation, improved responsiveness and natural scalability. Crucially, most of the key features of cryptocurrencies are _transaction-bound_ rather than blockchain-bound, and are thus compatible with our framework---e.g., scripting, multi denominations, _smart contracts_, etc.

In this paper, we revisit fully homomorphic encryption (FHE) based on GSW and its ring variants. We notice that the internal product of GSW can be replaced by a simpler external product between a GSW and an LWE ciphertext.

We show that the bootstrapping scheme FHEW of Ducas and Micciancio (Eurocrypt 2015) can be expressed only in terms of this external product. As a result, we obtain a speed up from less than 1 second to less than 0.1 seconds. We also reduce the 1GB bootstrapping key size to 24MB, preserving the same security levels, and we improve the noise propagation overhead by replacing exact decomposition algorithms with approximate ones.

Moreover, our external product allows to explain the unique asymmetry in the noise propagation of GSW samples and makes it possible to evaluate deterministic automata homomorphically as in (ePrint 2014/048) in an efficient way with a noise overhead only linear in the length of the tested word.

Finally, we provide an alternative practical analysis of LWE based scheme, which directly relates the security parameter to the error rate of LWE and the entropy of the LWE secret key.

We draw a new connection between Coppersmith's method for finding small solutions to polynomial congruences modulo integers and the capacity theory of adelic subsets of algebraic curves. Coppersmith's method uses lattice basis reduction to construct an auxiliary polynomial that vanishes at the desired solutions. Capacity theory provides a toolkit for proving when polynomials with certain boundedness properties do or do not exist. Using capacity theory, we prove that Coppersmith's bound for univariate polynomials is optimal in the sense that there are no auxiliary polynomials of the type he used that would allow finding roots of size $N^{1/d+\epsilon}$ for any monic degree-$d$ polynomial modulo $N$. Our results rule out the existence of polynomials of any degree and do not rely on lattice algorithms, thus eliminating the possibility of improvements for special cases or even superpolynomial-time improvements to Coppersmith's bound. We extend this result to constructions of auxiliary polynomials using binomial polynomials, and rule out the existence of any auxiliary polynomial of this form that would find solutions of size $N^{1/d+\epsilon}$ unless $N$ has a very small prime factor.

We initiate the study of public-key encryption (PKE) secure against selective-opening attacks (SOA) in the presence of randomness failures, i.e., when the sender may (inadvertently) use low-quality randomness. In the SOA setting, an adversary can adaptively corrupt senders; this notion is natural to consider in tandem with randomness failures since an adversary may target senders by multiple means.

Concretely, we first treat SOA security of nonce-based PKE. After formulating an appropriate definition of SOA- secure nonce-based PKE,we provide efficient constructions in the non-programmable random-oracle model, based on lossy trapdoor functions.

We then lift our notion of security to the setting of "hedged" PKE, which ensures security as long as the sender's seed, message, and nonce jointly have high entropy. This unifies the notions and strengthens the protection that nonce-based PKE provides against randomness failures even in the non-SOA setting.We lift our definitions and constructions of SOA-secure nonce-based PKE to the hedged setting as well.

Implantable Medical Devices (IMDs) are used to monitor and control patients with chronic diseases. A growing number of IMDs are equipped with a wireless interface that allows non-invasive monitoring and reprogramming through an external device, also known as device programmer. However, this wireless interface also brings important security and privacy risks that may lead to remote attacks. In this domain, the use of cryptography is challenging due to the inherent tensions between security vs accessibility and security vs energy cost. A well-studied problem yet unsolved is how to establish (and manage) cryptographic keys between the device programmer and the IMD. Recent work has investigated how Physiological Signals (PS) extracted from the patient can be used for key agreement or authentication between the devices.

This paper surveys some of the proposed countermeasures in the field of medical device security, with a special focus on those that use patient's physiological signals for key establishment or authentication between the devices. We point out that most of the existing solutions, including those relying on PS, take assumptions that do not necessarily hold in practical scenarios. Furthermore, we show that the H2H protocol and the Biosec protocol have serious security weaknesses and design flaws which make them vulnerable to attacks. Based on our analysis, we define some of the challenges that need be addressed before adopting these solutions. Furthermore, we investigate how to use physiological-signal-based protocols in cryptography, possibly in combination with other solutions, such as pre-installed factory keys, to achieve higher security protection.

We propose a new random oracle-less NIZK shuffle argument. It has a simple structure, where the first verification equation ascertains that the prover has committed to a permutation matrix, the second verification equation ascertains that the same permutation was used to permute the ciphertexts, and the third verification equation ascertains that input ciphertexts were ``correctly'' formed. The new argument has $3.5$ times more efficient verification than the up-to-now most efficient shuffle argument by Fauzi and Lipmaa (CT-RSA 2016). Compared to the Fauzi-Lipmaa shuffle argument, we (i) remove the use of knowledge assumptions and prove our scheme is sound in the generic bilinear group model, and (ii) prove standard soundness, instead of culpable soundness.

We study the problem of constructing a block-cipher on a "possibly-strange" set $\mathcal S$ using a block-cipher on a larger set $\mathcal T$. Such constructions are useful in format-preserving encryption, where for example the set $\mathcal S$ might contain "valid 9-digit social security numbers" while $\mathcal T$ might be the set of 30-bit strings. Previous work has solved this problem using a technique called cycle walking, first formally analyzed by Black and Rogaway. Assuming the size of $\mathcal S$ is a constant fraction of the size of $\mathcal T$, cycle walking allows one to encipher a point $x \in \mathcal S$ by applying the block-cipher on $\mathcal T$ a small /expected/ number of times and $O(N)$ times in the worst case, where $N = |\mathcal T|$, without any degradation in security. We introduce an alternative to cycle walking that we call /reverse cycle walking/, which lowers the worst-case number of times we must apply the block-cipher on $\mathcal T$ from $O(N)$ to $O(\log N)$. Additionally, when the underlying block-cipher on $\mathcal T$ is secure against $q = (1-\epsilon)N$ adversarial queries, we show that applying reverse cycle walking gives us a cipher on $\mathcal S$ secure even if the adversary is allowed to query all of the domain points. Such fully-secure ciphers have been the the target of numerous recent papers.

The concrete security bounds for some blockcipher-based constructions sometimes become worrisome or even vacuous; for example, when a light-weight blockcipher is used, when large amounts of data are processed, or when a large number of connections need to be kept secure. Rotating keys helps, but introduces a ``hybrid factor'' $m$ equal to the number of keys used. In such instances, analysis in the ideal-cipher model (ICM) can give a sharper picture of security, but this heuristic is called into question when cryptanalysis of the real-world blockcipher reveals weak keys, related-key attacks, etc.

To address both concerns, we introduce a new analysis model, the ideal-cipher model under key-oblivious access (ICM-KOA). Like the ICM, the ICM-KOA can give sharp security bounds when standard-model bounds do not. Unlike the ICM, results in the ICM-KOA are less brittle to current and future cryptanalytic results on the blockcipher used to instantiate the ideal cipher. Also, results in the ICM-KOA immediately imply results in the ICM _and_ the standard model, giving multiple viewpoints on a construction with a single effort. The ICM-KOA provides a conceptual bridge between ideal ciphers and tweakable blockciphers (TBC): blockcipher-based constructions secure in the ICM-KOA have TBC-based analogs that are secure under standard-model TBC security assumptions. Finally, the ICM-KOA provides a natural framework for analyzing blockcipher key-update strategies that use the blockcipher to derive the new key. This is done, for example, in the NIST CTR-DRBG and in the hardware RNG that ships on Intel chips.

Random number generators (RNGs) are essential for cryptographic systems, and statistical tests are usually employed to assess the randomness of their outputs. As the most commonly used statistical test suite, the NIST SP 800-22 suite includes 15 test items, each of which contains two-level tests. For the test items based on the binomial distribution, we find that their second-level tests are flawed due to the inconsistency between the assessed distribution and the assumed one. That is, the sequence that passes the test could still have statistical flaws in the assessed aspect. For this reason, we propose Q-value as the metric for these second-level tests to replace the original P-value without any extra modification, and the first-level tests are kept unchanged. We provide the correctness proof of the proposed Q-value based second-level tests. We perform the theoretical analysis to demonstrate that the modification improves not only the detectability, but also the reliability. That is, the tested sequence that dissatisfies the randomness hypothesis has a higher probability to be rejected by the improved test, and the sequence that satisfies the hypothesis has a higher probability to pass it. The experimental results on several deterministic RNGs indicate that, the Q-value based method is able to detect some statistical flaws that the original SP 800-22 suite cannot realize under the same test parameters.

In this paper, we revisit the security result of an authenticated key exchange (AKE) protocol recently proposed in CT-RSA 2016 by Chen, Mu, Yang, Susilo and Guo (we refer to this scheme as the CMYSG scheme). The security of the CMYSG scheme is shown in a new (stronger) challenge-dependent leakage-resilient eCK (CLR-eCK) model that captures (bounded) leakage from both the long term secret key of the parties as well the (per-session) randomness of the parties involved in an AKE protocol even after the challenge/test session. In this model, they proposed a generic framework for constructing one-round AKE protocols. The main tool employed in their construction is a (extended) 2-smooth projective hash proof system. The security of their protocol is reduced to the security of the underling hash-proof system, the existence of pseudo-random functions (PRF) and $\pi$-PRFs, collision-resistant hash functions and the Decisional Diffie-Hellman (DDH) hardness assumption. However, we disprove their security result and show that the security of the CMYSG protocol is incorrectly reduced to that of the DDH assumption. We then re-prove the security of the CMYSG scheme in the CLR-eCK model under the Gap Diffie-Hellman (GDH) hardness assumption in the random oracle model. Our security analysis continues the troubled past of the make-and-break efforts of constructing leakage-resilient AKE protocols and also leaves open the construction of CLR-eCK secure AKE protocol in the standard model.

When a group of individuals and organizations wish to compute a stable matching---for example, when medical students are matched to medical residency programs---they often outsource the computation to a trusted arbiter in order to preserve the privacy of participants' preferences. Secure multi-party computation offers the possibility of private matching processes that do not rely on any common trusted third party. However, stable matching algorithms have previously been considered infeasible for execution in a secure multi-party context on non-trivial inputs because they are computationally intensive and involve complex data-dependent memory access patterns.

We adapt the classic Gale-Shapley algorithm for use in such a context, and show experimentally that our modifications yield a lower asymptotic complexity and more than an order of magnitude in practical cost improvement over previous techniques. Our main improvements stem from designing new oblivious data structures that exploit the properties of the matching algorithms. We apply a similar strategy to scale the Roth-Peranson instability chaining algorithm, currently in use by the National Resident Matching Program. The resulting protocol is efficient enough to be useful at the scale required for matching medical residents nationwide, taking just over 18 hours to complete an execution simulating the 2016 national resident match with more than 35,000 participants and 30,000 residency slots.

In 2015, Hofheinz et al. [PKC, 2015] extended Chen and Wee's almost-tight reduction technique for identity based encryptions (IBE) [CRYPTO, 2013] to the multi-instance, multi-ciphertext (MIMC, or multi-challenge) setting, where the adversary is allowed to obtain multiple challenge ciphertexts from multiple IBE instances, and gave the first almost-tightly secure IBE in this setting using composite-order bilinear groups. Several prime-order realizations were proposed lately. However there seems to be a dilemma of high system performance (involving ciphertext/key size and encryption/decryption cost) or weak/standard security assumptions. A natural question is: can we achieve high performance without relying on stronger/non-standard assumptions?

In this paper, we answer the question in the affirmative by describing a prime-order IBE scheme with the same performance as the most efficient solutions so far but whose security still relies on the standard k-linear (k-Lin) assumption. Our technical start point is Blazy et al.'s almost-tightly secure IBE [CRYPTO, 2014]. We revisit their concrete IBE scheme and associate it with the framework of nested dual system group. This allows us to extend Blazy et al.'s almost-tightly secure IBE to the MIMC setting using Gong et al.'s method [PKC, 2016]. We emphasize that, when instantiating our construction by the Symmetric eXternal Diffie-Hellman assumption (SXDH = 1-Lin), we obtain the most efficient concrete IBE scheme with almost-tight reduction in the MIMC setting, whose performance is even comparable to the most efficient IBE in the classical model (i.e., the single-instance, single-ciphertext setting). Besides pursuing high performance, our IBE scheme also achieves a weaker form of anonymity pointed out by Attrapadung et al. [AsiaCrypt, 2015].

1 year postdoc to work in cryptography at Royal Holloway, alongside Kenny Paterson and the team there. All areas of research in cryptography will be considered.

Closing date for applications: 10 October 2016

Contact: Kenny Paterson

Information Security Group

Royal Holloway, University of London

kenny.paterson (at) rhul.ac.uk

More information: https://jobs.royalholloway.ac.uk/vacancy.aspx?ref=0916-295