International Association
for Cryptologic Research

Functional encryption lies at the frontiers of current research in cryptography; some variants have been shown sufficiently powerful to yield indistinguishability obfuscation (IO) while other variants have been constructed from standard assumptions such as LWE. Indeed, most variants have been classified as belonging to either the former or the latter category. However, one mystery that has remained is the case of secret-key functional encryption with an unbounded number of keys and ciphertexts. On the one hand, this primitive is not known to imply anything outside of minicrypt, the land of secret-key crypto, but on the other hand, we do no know how to construct it without the heavy hammers in obfustopia. In this work, we show that (subexponentially secure) secret-key functional encryption is powerful enough to construct indistinguishability obfuscation if we additionally assume the existence of (subexponentially secure) plain public-key encryption. In other words, secret-key functional encryption provides a bridge from cryptomania to obfustopia. On the technical side, our result relies on two main components. As our first contribution, we show how to use secret key functional encryption to get “exponentially-efficient indistinguishability obfuscation” (XIO), a notion recently introduced by Lin et al. (PKC ’16) as a relaxation of IO. Lin et al. show how to use XIO and the LWE assumption to build IO. As our second contribution, we improve on this result by replacing its reliance on the LWE assumption with any plain public-key encryption scheme. Lastly,we ask whether secret-key functional encryption can be used to construct public-key encryption itself and therefore take us all the way from minicrypt to obfustopia. A result of Asharov and Segev (FOCS ’15) shows that this is not the case under black-box constructions, even for exponentially secure functional encryption. We show, through a non-black box construction, that subexponentially secure-key functional encryption indeed leads to public-key encryption. The resulting public-key encryption scheme, however, is at most quasi-polynomially secure, which is insufficient to take us to obfustopia.

Higher-order masking is a widely used countermeasure to make software implementations of blockciphers achieve high security levels against side-channel attacks. Unfortunately, it often comes with a strong impact in terms of performances which may be prohibitive in some contexts. This situation has motivated the research for efficient schemes that apply higher-order masking with minimal performance overheads. The most widely used approach is based on a polynomial representation of the cipher s-box(es) allowing the application of standard higher-order masking building blocks such as the ISW scheme (Ishai-Sahai-Wagner, Crypto 2003). Recently, an alternative approach has been considered which is based on a bitslicing of the s-boxes. This approach has been shown to enjoy important efficiency benefits, but it has only been applied to specific blockciphers such as AES, PRESENT, or custom designs. In this paper, we present a generic method to find a Boolean representation of an s-box with efficient bitsliced higher-order masking. Specifically, we propose a method to construct a circuit with low \emph{multiplicative complexity}. Compared to previous work on this subject, our method can be applied to any s-box of common size and not necessarily to small s-boxes. We use it to derive higher-order masked s-box implementations that achieve important performance gain compared to optimized state-of-the-art implementations.

As distributed networks are heavily used in modern applications, new security challenges emerge. In a multi-party computation (in short, MPC) protocol over an incomplete network, such a challenge is to hide, to the extent possible, the topology of the underlying communication network. Such a topology-hiding (aka network hiding) property is in fact very relevant in applications where anonymity is needed.

To our knowledge, with the exception of two recent works by Chandran et al. [ITCS 2015] and by Moran et al. [TCC 2015], existing MPC protocols do not hide the topology of the underlying communication network. Moreover, the above two solutions are either not applicable to arbitrary networks (as is [ITCS 2015]) or, as in [TCC 2015], they make non-black-box and recursive use of cryptographic primitives resulting in an unrealistic communication and computation complexity even for simple, i.e., low degree and diameter, networks.

Our work suggests the first topology-hiding communication protocol for incomplete networks which makes black-box use of the underlying cryptographic assumption-in particular, a public-key encryption scheme-and tolerates any adversary who passively corrupts arbitrarily many network nodes. Our solutions are based on a new, enhanced variant of threshold homomorphic encryption, in short, TH-PKE, that requires no a-priori setup and allows to circulate an encrypted message over any (unknown) incomplete network and then decrypt it without revealing any network information to intermediate nodes. We show how to realize this enhanced TH-PKE from the DDH assumption. The black-box nature of our scheme, along with some optimization tricks that we employ, makes our communication protocol more efficient than existing solutions.

We then use our communication protocol to make any semi-honest secure MPC protocol topology-hiding with a reasonable-i.e., for simple networks, polynomial with small constants-communication and computation overhead. We further show how to construct anonymous broadcast without using expensive MPCs to setup the original pseudonyms.

Proof of Work (PoW) powered blockchains currently account for more than 90% of the total market capitalization of existing digital currencies. Although the security provisions of Bitcoin have been thoroughly analysed, the security guarantees of variant (forked) PoW blockchains (which were instantiated with different parameters) have not received much attention in the literature.

In this paper, we introduce a novel quantitative framework to analyse the security and performance implications of various consensus and network parameters of PoW blockchains. Based on our framework, we devise optimal adversarial strategies for double-spending and selfish mining while taking into account real world constraints such as network propagation, different block sizes, block generation intervals, information propagation mechanism, and the impact of eclipse attacks. Our framework therefore allows us to capture existing PoW-based deployments as well as PoW blockchain variants that are instantiated with different parameters, and to objectively compare the tradeoffs between their performance and security provisions.

A new distinguishing property against block ciphers, called the division property, was introduced by Todo at Eurocrypt 2015. Our work gives a new approach to it by the introduction of the notion of parity sets. First of all, this new notion permits us to formulate and characterize in a simple way the division property of any order. At a second step, we are interested in the way of building distinguishers on a block cipher by considering some further properties of parity sets, generalising the division property. We detail in particular this approach for substitution-permutation networks. To illustrate our method, we provide low-data distinguishers against reduced-round Present. These distinguishers reach a much higher number of rounds than generic distinguishers based on the division property and demonstrate, amongst others, how the distinguishers can be improved when the properties of the linear and the Sbox layer are taken into account. At last, this work provides an analysis of the resistance of Sboxes against this type of attacks, demonstrates links with the algebraic normal form of an Sbox as well as its inverse Sbox and exhibit design criteria for Sboxes to resist such attacks.

Authentication technology plays a critical role in securing access to online services, such as banking, email and social networking. Session authentication schemes establish the identity of the user only at the beginning of the session so are vulnerable to attacks which tamper with communications after the authenticated session has been established. Transaction authentication schemes defend against such attacks by performing an additional authentication step at critical parts of the session, but are unpopular with users due to repeated authentication. Continuous authentication schemes, in contrast, verify user identity and intent throughout the session. So far, such schemes have had limited use in practice due to two primary weaknesses of existing approaches: privacy concerns and risk of false positives/false negatives.

This project aims to address these limitations by designing and evaluating new approaches for continuous authentication, based on a solid theoretical underpinning so as to give a high degree of confidence that the resulting decisions match expectations and requirements. Furthermore the project will focus on ways to preserve user privacy by processing behavioural measurements on the user’s computer such that sensitive information is not sent to the online service. The evaluation to be performed will consider the false-positive/false-negative rates, privacy impact, user acceptance and costs of deployment and operation.

The student will be supervised by Dr Steven Murdoch in the Information Security Group at University College London, in collaboration with VASCO Data Security.

The successful applicant will have their fees paid in full at the home/EU rate at UCL and receive a tax-free stipend at standard EPSRC rates. The project is to start on the 26th September 2016, in line with the start of the 2016/17 Academic Year at UCL.

Closing date for applications: 27 June 2016

Contact: Submit applications online using the PRiSM (the UCL application system). Contact Dr Steven Murdoch (s.murdoch (at) ucl.ac.uk) for queries about the position

More information: https://www.prism.ucl.ac.uk/#!/?project=185

The Cybersecurity Research Center at the New Jersey Institute of Technology (NJIT) invites applications for a Postdoctoral Research Associate position in the area of Security of Storage Systems and Applied Cryptography.

The Postdoctoral Research Associate is expected to pursue research towards establishing a framework that provides strong integrity, availability and reliability guarantees for data outsourced at cloud storage providers. Familiarity with cloud storage systems and applied cryptography is preferred.

The candidates are expected to:

- have completed their PhD degree in Computer Science or closely related areas,

- have adequate cybersecurity/applied cryptography research experience demonstrated through a good publication record, and

- have excellent verbal and written skills in English

We expect the position to be available immediately for one year and to be renewable, based on mutual interest and availability of funding.

Interested applicants should submit their CV and the names of at least two references by applying as soon as possible at https://njit.jobs/applicants/Central?quickFind=55066. Applications will be reviewed on a rolling basis until the position is filled.

Work environment and location:

Details about the center\'s research activities can be found at:

http://centers.njit.edu/cybersecurity/.

The Department of Computer Science at NJIT includes 27 tenured/tenure track professors and is rapidly expanding, supported by the university\'s \"2020 Vision\" strategic plan. Sources of research funding include DARPA, NSF, NIH, DHS, DOE, ARL, and ONR to name a few. Located in Northern New Jersey, within the greater New York Metropolitan area, NJIT is part of a vibrant ecosystem of research universities and corporate research centers.

Closing date for applications: 30 June 2016

Contact: Prof. Reza Curtmola

More information: https://njit.jobs/applicants/Central?quickFind=55066

This scholarship is to work on the High Performance Control System Security research project. High performance control systems are used in many security-critical applications such as car control systems, unmanned aerial vehicles (UAV), autonomous vehicles and critical-infrastructure systems. Most solutions suffer from security and safety flaws, which can be attributed to a lack of proper authentication, confidentiality and availability.

You\'ll investigate security in a particular control system (such as UAV) or perhaps a cluster of systems that exhibits similar design characteristics. This research is likely to relate to a generic key management protocols to implement authentication and confidentiality. Another possible research avenue is software defined networking and its impact on availability or how it can be used to mitigate denial of service (DoS) attacks.

Closing date for applications: 1 August 2016

Contact: Professor Josef Pieprzyk

More information: https://www.qut.edu.au/study/fees-and-scholarships/scholarships-and-prizes/control-system-security-scholarship

We address the problem of substring searchable encryption. A single user produces a big stream of data and later on wants to learn the positions in the string that some patterns occur. Although current techniques exploit auxiliary data structures to achieve efficient substring search on the server side, the cost at the user side may be prohibitive. We revisit the work of substring searchable encryption in order to reduce the storage cost of auxiliary data structures. Our solution entails suffix array which allows optimal storage cost $O(n)$ with small hidden factor at the size of the string $n$. On top of that we build an encrypted index that allows the server to answer substring queries without learning neither the query nor the result. We identify the leakages of the scheme following the work of Curtmola $\etal$ \cite{sse2} and we analyze the security of the protocol in the real ideal framework. Moreover, we demonstrate the practicality of the protocol by searching a one million characters data stream in less than one second within the GPU computing paradigm. The total speedup approximates a factor of $4$x, compared with naive CPU implementation.

Authenticated Key Exchange (AKE) is a cryptographic scheme with the aim to establish a high-entropy and secret session key over a insecure communications network. \emph{Password}-Authenticated Key Exchange (PAKE) assumes that the parties in play share a simple password, which is cheap and human-memorable and is used to achieve the authentication. PAKEs are practically relevant as these features are extremely appealing in an age where most people access sensitive personal data remotely from more-and-more pervasive hand-held devices. Theoretically, PAKEs allow the secure computation and authentication of a high-entropy piece of data using a low-entropy string as a starting point. In this paper, we apply the recently proposed technique introduced in~\cite{DXX2012} to construct two lattice-based PAKE protocols enjoying a very simple and elegant design that is an parallel extension of the class of Random Oracle Model (ROM)-based protocols \msf{PAK} and \msf{PPK}~\cite{BMP2000,M2002}, but in the lattice-based setting. The new protocol resembling \msf{PAK} is three-pass, and provides \emph{mutual explicit authentication}, while the protocol following the structure of \msf{PPK} is two-pass, and provides \emph{implicit authentication}. Our protocols rely on the Ring-Learning-with-Errors (RLWE) assumption, and exploit the additive structure of the underlying ring. They have a comparable level of efficiency to \msf{PAK} and \msf{PPK}, which makes them highly attractive. We present a preliminary implementation of our protocols to demonstrate that they are both efficient and practical. We believe they are suitable quantum safe replacements for \msf{PAK} and \msf{PPK}.

Bones et al. showed at Crypto 99 that moduli of the form $N=p^rq$ can be factored in polynomial time when $r \geq \log p$. Their algorithm is based on Coppersmith's technique for finding small roots of polynomial equations. Recently, Coron et al. showed that $N=p^rq^s$ can also be factored in polynomial time, but under the stronger condition $r \geq \log^3 p$. In this paper, we show that $N=p^rq^s$ can actually be factored in polynomial time when $r \geq \log p$, the same condition as for $N=p^rq$.

The ``kernel" model has been part of operating system architecture for decades, but upon closer inspection it clearly violates the principle of least required privilege. The kernel is a single entity which provides many services (memory management, interfacing to drivers, context switching, IPC) which have no real relation to each other, and has the ability to observe or tamper with all state of the system. This work presents Antikernel, a novel operating system architecture consisting of both hardware and software components and designed to be fundamentally more secure than the state of the art. To make formal verification easier, and improve parallelism, the Antikernel system is highly modular and consists of many independent hardware state machines (one or more of which may be a general-purpose CPU running application or systems software) connected by a packet-switched network-on-chip (NoC). We create and verify an FPGA-based prototype of the system.

Motivated by the problem of one-time password generation, we introduce the notion of {\em adjustable signature schemes} that allow the length of a signature to be adjusted---at the setup, signing or verification stages, depending on the application. We provide security definitions that precisely capture the trade-off between signature length and security for such schemes. We then provide both concrete and general feasibility results.

As a feasibility result, we provide the first instantiation of all variants of adjustable signatures based on indistinguishability obfuscation. Our starting point is the state-of-the-art construction by Ramchen and Waters [CCS 2014]. We observe that their scheme fails to meet our requirements for an adjustable signatures scheme, and enhance it to obtain {\em shorter} (and adjustable) signatures, {\em faster} signing and strong unforgeability.

For the simpler case of setup-adjustable signatures, we also provide a concrete construction based on the BLS signature scheme, by instantiating it using smaller group sizes that yield shorter signature lengths while providing reasonable security. We implement this scheme for various signature sizes an report on its efficiency.

A wide variety of objectively practical cryptographic schemes can be constructed using only symmetric-key operations and linear operations. To formally study this restricted class of cryptographic algorithms, we present a new model called {\em Linicrypt}. A Linicrypt program has access to a random oracle whose inputs and outputs are field elements, and otherwise manipulates data only via fixed linear combinations.

Our main technical result is that it is possible to decide {\em in polynomial time} whether two given Linicrypt programs induce computationally indistinguishable distributions (against arbitrary PPT adversaries, in the random oracle model).

We show also that indistinguishability of Linicrypt programs can be expressed as an existential formula, making the model amenable to {\em automated program synthesis.} In other words, it is possible to use a SAT/SMT solver to automatically generate Linicrypt programs satisfying a given security constraint. Interestingly, the properties of Linicrypt imply that this synthesis approach is both sound and complete.

We demonstrate this approach by synthesizing Linicrypt constructions of garbled circuits.

WPA2-Personal is widely used to protect Wi-Fi networks against illicit access. While attackers typically use GPUs to speed up the discovery of weak network passwords, attacking random passwords is considered to quickly become infeasible with increasing password length. Professional attackers may thus turn to commercial high-end FPGA-based cluster solutions to significantly increase the speed of those attacks. Well known manufacturers such as Elcomsoft have succeeded in creating world's fastest commercial FPGA-based WPA2 password recovery system, but since they rely on high-performance FPGAs the costs of these systems are well beyond the reach of amateurs. In this paper, we present a highly optimized low-cost FPGA cluster-based WPA-2 Personal password recovery system that can not only achieve similar performance at a cost affordable by amateurs, but in comparison our implementation would also be more than $5$ times as fast on the original hardware. Since the currently fastest system is not only significantly slower but proprietary as well, we believe that we are the first to present the internals of a highly optimized and fully pipelined FPGA WPA2 password recovery system. In addition we evaluated our approach with respect to performance and power usage and compare it to GPU-based systems.

In this work an unconditionally hiding auditing procedure for computations on documents stored in distributed fashion is introduced. There is only one multi-party computation (MPC) scheme providing auditability which computationally protects the inputs of the computations. Building on this, we propose a computationally hiding solution that uses bilinear maps and therefore produces no additional overhead in the online phase. In addition, we introduce a second variation that is the first auditable MPC scheme providing unconditional (or information-theoretic) hidingness. We achieve this by combining bilinear maps with unconditionally hiding commitments leading to only a small overhead in the online phase. We prove our solutions secure and give arguments for practicability and efficiency. The auditing procedures presented here are an important contribution since distributed storage solutions, e.g. cloud of clouds, allow for information-theoretic confidentiality. Using our technique, they can be extended to perform auditable computations on the data stored.

Ph.D. offer

Looking for a Ph.D. thesis that combines computer security and mathematics? IRISA (https://www.irisa.fr/en), the computer science laboratory of Rennes in France, seeks to hire an outstanding doctoral student to perform research in the field of formal modeling and analysis of security. The position is within the project entitled Attack-Defense Trees for Computer Security: Formal Modeling of Preventive and Reactive Countermeasures. A detailed description of the thesis topic is available at http://people.irisa.fr/Barbara.Kordy/vacancies.php and at http://people.irisa.fr/Barbara.Kordy/vacancies/PhD_16.pdf

Candidate profile

The candidate is expected to have

• A Master degree in computer science or mathematics;

• A proven interest in formal methods and formal modeling;
• Excellent written and oral English skills.

Background in computer security will be a plus. Knowledge of French is not required.

Application

Applications should be written in English and include the following documents

• Motivation letter clearly explaining the candidate\'s interest in the proposed topic and his/her fit to the position;

• Curriculum Vitae (including contact information, education and work experience, short description of the master thesis, list of publications, etc.);
• Transcript of grades from all university-level courses taken;
• Contact information for 2 referees.

Applications will be considered on a rolling basis until the position is filled. Documents should be submitted by e-mail to dr. Barbara Kordy (barbara.kordy (at) irisa.fr).

Closing date for applications: 30 October 2016

Contact: Barbara Kordy

barbara.kordy (at) irisa.fr

More information: http://people.irisa.fr/Barbara.Kordy/vacancies.php

A fundamental open problem in the area of blockchain protocols is whether the Bitcoin blockchain protocol is the optimal solution (in terms of efficiency, security) for building a secure transaction ledger. A recently proposed and widely deployed alternative is the \GHOST protocol which, notably, is at the core of Ethereum as well as other recent proposals for improved Bitcoin-like systems. % The \GHOST variant is touted as offering superior performance compared to Bitcoin (block production in ethereum has been sped up by a factor of more than 40) without a security loss. Motivated by this, in this work, we study from both a provable security and attack susceptibility point of view the problem of transaction processing time for both \GHOST and Bitcoin.

We introduce a new formal framework for the analysis of blockchain protocols that relies on trees (rather than chains) and we showcase the power of the framework by providing a unified description of the \GHOST and Bitcoin protocols, the former of which we extract and formally describe in our framework. We then prove that \GHOST implements a ``robust transaction ledger'' (i.e., possesses liveness and persistence) and hence it is a provably secure alternative to Bitcoin.

We then focus on the liveness property of both Bitcoin and \GHOST, i.e., the worst-case transaction confirmation time that can be expected when playing against an adversary. We present a general attack methodology against liveness and we instantiate it with two attacks for Bitcoin and \GHOST. We prove that our attack for Bitcoin is essentially optimal. Furthermore, we perform simulation results and we demonstrate that for a wide range of confirmation parameter choices and hashing power bounds for the adversary, \GHOST, when under our attack, performs about the same or worse than Bitcoin in terms of transaction confirmation time. % Our results highlight the importance of provable security analysis in the context of blockchain protocols.

A secure comparison protocol allows players to evaluate the greater-than predicate on hidden values; it addresses a problem that belongs to the field of multiparty computation, in which players wish to jointly and privately evaluate a function on secret inputs. Introduced by Yao under the name millionaires' problem, secure comparisons have received a great deal of attention. They have proven to be one of the most fundamental building block in a large variety of multiparty computation protocols. However, due to their inherent non-arithmetic structure, they are in general less efficient than other fundamental primitives, and as such, are often a major bottleneck in multiparty computation protocols.

In this work, we design new two-party protocols for the greater-than functionality, secure against honest-but-curious adversaries (who follow the specifications of the protocol), improving over the state of the art. They can be readily used in a large variety of applications in which secure comparisons constitute the main efficiency bottleneck. Our protocols are defined in the preprocessing model, and are extremely efficient during the online phase. They are based solely on oblivious transfers, and can therefore use oblivious transfer extensions to get rid of all but a constant amount of expensive computations. Toward our goal of secure comparison, we also design protocols for testing equality between private inputs, which improve similarly over the state of the art. The latter contribution is of independent interest.

Oblivious RAM (ORAM) is a powerful cryptographic protocol which has recently risen in prominence, in part due to its ability to hide a client's access patterns from untrusted cloud storage services. We present an oblivious cloud storage system, ObliviSync, that specifically targets one of the most widely-used personal cloud storage paradigms: synchronization and backup services, popular examples of which are Dropbox, iCloud Drive, and Google Drive. We show that this setting provides a unique opportunity for Oblivious RAM research because full privacy can be achieved with a simpler form of ORAM called write-only ORAM. This allows for dramatically increased efficiency compared to related work - so much so that our solution has only a small constant overhead of approximately 4x compared with non-private file storage. We built and evaluated a full implementation of ObliviSync that supports multiple simultaneous read-only clients and a single concurrent read/write client whose edits automatically and seamlessly propagate to the readers. We show that our system functions under high work loads with realistic file size distributions.