International Association
for Cryptologic Research

Electronic Health Record (EHR) system facilitates us a lot for health record management. Privacy risk of patients’ records is the dominating obstacle in the widely deployed EHRs. Role-based access control (RBAC) schemes offer an access control on EHRs according to one’s role. Only the medical staff with roles satisfying the specified access policies can read EHRs. In existing schemes, attackers can link patients’ identities to their doctors. Therefore, the classification of patients’ diseases are leaked without actually knowing patients’ EHRs. To address this problem, we present an anonymous RBAC scheme. Not only it achieves flexible access control, but also realizes privacy-preserving for individuals. Moreover, our scheme maintains the property of constant size for the encapsulated EHRs. The proposed security model with both semantic security and anonymity can be proven under decisional bilinear group assumptions. Besides, we provide an approach for EHR owners to search out their targeted EHR in the anonymous system. For better user experience, we apply “online/offline” approach to speed up data processing in our scheme. Experimental results show that the time consumption for key generation and EHR encapsulation can be done in milliseconds.

Proofs of partial knowledge allow a prover to prove knowledge of witnesses for k out of n instances of NP languages. Cramer, Schoenmakers and Damg\aa rd [CDS94] provided an efficient construction of a 3-round public-coin witness-indistinguishable (k, n)-proof of partial knowledge for any NP language, by cleverly combining n executions of Sigma-protocols for that language. This transform assumes that all n instances are fully specified before the proof starts, and thus directly rules out the possibility of choosing some of the instances after the first round. Very recently, Ciampi et al. [CPS+16] provided an improved transform where one of the instances can be specified in the last round. They focus on (1,2)-proofs of partial knowledge with the additional feature that one instance is defined in the last round, and could be adaptively chosen by the verifier. They left as an open question the existence of an efficient (1, 2)-proof of partial knowledge where no instance is known in the first round. More in general, they left open the question of constructing an efficient (k, n)-proof of partial knowledge where knowledge of all n instances can be postponed. Indeed, this property is achieved only by inefficient constructions requiring NP reductions [LS90]. In this paper we focus on the question of achieving adaptive-input proofs of partial knowledge. We provide through a transform the first efficient construction of a 3-round public-coin witness- indistinguishable (k, n)-proof of partial knowledge where all instances can be decided in the third round. Our construction enjoys adaptive-input witness indistinguishability. Additionally, the proof of knowledge property remains also if the adversarial prover selects instances adaptively at last round as long as our transform is applied to a proof of knowledge belonging to the widely used class of proofs of knowledge described in [Mau15, CD98]. Since knowledge of instances and witnesses is not needed before the last round, we have that the first round can be precomputed and in the online/offline setting our performance is similar to the one of [CDS94]. Our new transform relies on the DDH assumption (in contrast to the transforms of [CDS94, CPS+16] that are unconditional). We also show how to strengthen the transform of [CPS+16] so that it also achieves adaptive soundness, when the underlying combined protocols belong to the class of protocols described in [Mau15, CD98].

Juels and Ristenpart introduced honey encryption (HE) and showed how to achieve message recovery security even in the face of attacks that can exhaustively try all likely keys. This is important in contexts like password-based encryption where keys are very low entropy, and HE schemes based on the JR construction were subsequently proposed for use in password management systems and even long-term protection of genetic data. But message recovery security is in this setting, like previous ones, a relatively weak property, and in particular does not prohibit an attacker from learning partial information about plaintexts or from usefully mauling ciphertexts.

We show that one can build HE schemes that can hide partial information about plaintexts and that prevent mauling even in the face of exhaustive brute force attacks. To do so, we introduce target-distribution semantic-security and target-distribution non-malleability security notions and proofs that a slight variant of the JR HE construction can meet them. The proofs require new balls-and-bins type analyses significantly different from those used in prior work. Finally, we provide a formal proof of the folklore result that an unbounded adversary which obtains a limited number of encryptions of known plaintexts can always succeed at message recovery.

The goal of leakage-resilient cryptography is to construct cryptographic algorithms that are secure even if the devices on which they are implemented leak information to the adversary. One of the main parameters for designing leakage resilient constructions is the leakage \emph{rate}, i.e., a proportion between the amount of leaked information and the complexity of the computation carried out by the construction. We focus on the so-called circuit compilers, which is an important tool for transforming any cryptographic algorithm (represented as a circuit) into one that is secure against the leakage attack. Our model is the ``probing attack'' where the adversary learns the values on some (chosen by him) wires of the circuit.

Our results can be summarized as follows. First, we construct circuit compilers with perfect security and leakage rate $O(1/\log(n))$, where $n$ denotes the security parameter (previously known constructions achieved rate $O(1/n)$). Moreover, for the circuits that have only affine gates we obtain a construction with a constant leakage rate. In particular, our techniques can be used to obtain constant-rate leakage-resilient schemes for refreshing an encoded secret (previously known schemes could tolerate leakage rates $O(1/n)$).

We also show that our main construction is secure against constant-rate leakage in the random probing leakage model, where the leaking wires are chosen randomly.

The goal of searchable encryption (SE) is to enable a client to execute searches over encrypted files stored on an untrusted server while ensuring some measure of privacy for both the encrypted files and the search queries. Research has focused on developing efficient SE schemes at the expense of allowing some small, well-characterized "(information) leakage" to the server about the files and/or the queries. The practical impact of this leakage, however, remains unclear.

We thoroughly study file-injection attacks--in which the server sends files to the client that the client then encrypts and stores--on the query privacy of single-keyword and conjunctive SE schemes. We show such attacks can reveal the client's queries in their entirety using very few injected files, even for SE schemes having low leakage. We also demonstrate that natural countermeasures for preventing file-injection attacks can be easily circumvented. Our attacks outperform prior work significantly in terms of their effectiveness as well as in terms of their assumptions about the attacker's prior knowledge.

In this paper, we will study some possible generalizations of the famous Diffie-Hellman algorithm. As we will see, at the end, most of these generalizations will not be secure or will be equivalent to some classical schemes. However, these results are not always obvious and moreover our analysis will present some interesting connections between the concepts of commutativity, associativity, and public key cryptography.

Xoring two permutations is a very simple way to construct pseudorandom functions from pseudorandom permutations. The aim of this paper is to get precise security results for this construction. Since such construction has many applications in cryptography (see \cite{BI,BKrR,HWKS,SL} for example), this problem is interesting both from a theoretical and from a practical point of view. In \cite{SL}, it was proved that Xoring two random permutations gives a secure pseudorandom function if $m \ll 2^{\frac {2n}{3}}$. By ``secure'' we mean here that the scheme will resist all adaptive chosen plaintext attacks limited to $m$ queries (even with unlimited computing power). More generally in \cite{SL} it is also proved that with $k$ Xor, instead of 2, we have security when $m \ll 2^{\frac {kn}{k+1}}$. In this paper we will prove that for $k=2$, we have in fact already security when $m \ll O(2^n)$. Therefore we will obtain a proof of a similar result claimed in \cite{BI} (security when $m\ll O(2^n /n^{2/3})$). Moreover our proof is very different from the proof strategy suggested in \cite{BI} (we do not use Azuma inequality and Chernoff bounds for example, but we will use the ``$H_{\sigma}$ technique'' as we will explain), and we will get precise and explicit $O$ functions. Another interesting point of our proof is that we will show that this (cryptographic) problem of security is directly related to a very simple to describe and purely combinatorial problem.

Event date: 16 November to 18 November 2016
Submission deadline: 1 July 2016
Notification: 15 August 2016

We prove that any algorithm for learning parities requires either a memory of quadratic size or an exponential number of samples. This proves a recent conjecture of Steinhardt, Valiant and Wager and shows that for some learning problems a large storage space is crucial.

More formally, in the problem of parity learning, an unknown string $x \in \{0,1\}^n$ was chosen uniformly at random. A learner tries to learn $x$ from a stream of samples $(a_1, b_1), (a_2, b_2)... $, where each $a_t$ is uniformly distributed over $\{0,1\}^n$ and $b_t$ is the inner product of $a_t$ and $x$, modulo 2. We show that any algorithm for parity learning, that uses less than $n^2/25$ bits of memory, requires an exponential number of samples.

Previously, there was no non-trivial lower bound on the number of samples needed, for any learning problem, even if the allowed memory size is $O(n)$ (where $n$ is the space needed to store one sample).

We also give an application of our result in the field of bounded-storage cryptography. We show an encryption scheme that requires a private key of length $n$, as well as time complexity of $n$ per encryption/decryption of each bit, and is provenly and unconditionally secure as long as the attacker uses less than $n^2/25$ memory bits and the scheme is used at most an exponential number of times. Previous works on bounded-storage cryptography assumed that the memory size used by the attacker is at most linear in the time needed for encryption/decryption.

We study the problem of devising provably secure PRNGs with input based on the sponge paradigm. Such constructions are very appealing, as efficient software/hardware implementations of SHA-3 can easily be translated into a PRNG in a nearly black-box way. The only existing sponge-based construction, proposed by Bertoni et al. (CHES 2010), fails to achieve the security notion of robustness recently considered by Dodis et al. (CCS 2013), for two reasons: (1) The construction is deterministic, and thus there are high-entropy input distributions on which the construction fails to extract random bits, and (2) The construction is not forward secure, and presented solutions aiming at restoring forward security have not been rigorously analyzed.

We propose a seeded variant of Bertoni et al.'s PRNG with input which we prove secure in the sense of robustness, delivering in particular concrete security bounds. On the way, we make what we believe to be an important conceptual contribution, developing a variant of the security framework of Dodis et al. tailored at the ideal permutation model that captures PRNG security in settings where the weakly random inputs are provided from a large class of possible adversarial samplers which are also allowed to query the random permutation.

As a further application of our techniques, we also present a simple and very efficient key-derivation function based on sponges (which can hence be instantiated from SHA-3 in a black-box fashion), which we also prove secure when fed with samples from permutation-dependent distributions.

Smart contracts are programs that execute autonomously on blockchains. Many of their envisioned uses require them to consume data from outside the blockchain. (For example, a financial instrument might rely on a stock price.) Trustworthy *data feeds* that can support data requests by smart contracts will thus be critical to any smart contract system.

We present an authenticated data feed system called Town Crier (TC). TC builds on the observation that many web sites, such as major news and finance sites, already serve as trusted data sources for non-blockchain uses. TC acts as a bridge between such servers and smart contract systems. It uses trusted hardware to authenticate and scrape data from HTTPS-enabled websites and to generate trustworthy data for relying smart contracts. It also includes a range of advanced features such as support for private data requests, which involve decryption and evaluation of request ciphertext within TC's hardware.

We describe the TC architecture, its underlying trust model, and its applications, and report on an implementation that uses the newly released Intel SGX software development kit and furnishes data for the smart-contract system Ethereum. To the best of our knowledge, ours is the first research paper reporting system implementation on a real SGX-enabled host. Finally, we present formal proofs of the security of TC, including correct handling of payment in Ethereum. We will soon be launching TC as an online public service.

Digital currencies like Bitcoin rely on cryptographic primitives to operate. However, past experience shows that cryptographic primitives do not last forever: increased computational power and advanced cryptanalysis cause primitives to break frequently, and motivate the development of new ones. It is therefore crucial for maintaining trust in a crypto currency to anticipate such breakage.

We present the first systematic analysis of the effect of broken primitives on Bitcoin. We identify the core cryptographic building blocks and analyze the various ways in which they can break, and the subsequent effect on the main Bitcoin security guarantees. Our analysis reveals a wide range of possible effects depending on the primitive and type of breakage, ranging from minor privacy violations to a complete breakdown of the currency.

Our results lead to several observations on, and suggestions for, the Bitcoin migration plans in case of broken cryptographic primitives.

Cryptographic security is usually defined as some form of guarantee that holds except when a bad event with negligible probability occurs, and nothing is guaranteed in that case. However, in settings where such failure can happen with substantial probability, one needs to provide guarantees even for the bad case. A typical example is where a (possibly weak) password is used instead of an unguessable cryptographic key to protect a session, the bad event being that the adversary correctly guesses the password. In a situation with multiple such sessions, a per-session guarantee is desired: any session for which the password has not been guessed remains secure, independently of whether other sessions have been compromised. In particular, a user with a very strong password enjoys the full security guarantees of an analysis in which passwords are replaced by uniform cryptographic keys.

Our contributions are two-fold. First, we provide a new, general technique for stating security guarantees that degrade gracefully and which could not be expressed with existing formalisms. Our method is simple, does not require new security definitions, and can be carried out in any simulation-based security framework (thus providing composability). Second, we apply our approach to revisit the analysis of password-based message authentication and of password-based encryption (PBE), investigating whether they provide strong per-session guarantees.

In the case of PBE, one would intuitively expect a weak form of confidentiality, where a transmitted message only leaks to the adversary once the underlying password is guessed. Indeed, we show that PBE does achieve this weak confidentiality if an upper-bound on the number of adversarial password-guessing queries is known in advance for each session. However, such local restrictions appear to be questionable since we show that standard domain separation techniques employed in password-based cryptography, such as salting, can only provide global restrictions on the number of adversarial password-guessing queries. Quite surprisingly, we show that in this more realistic scenario the desired per-session confidentiality is unachievable. This impossibility result resolves an open problem stated by Bellare, Ristenpart and Tessaro (CRYPTO 2012).

Smart phones and mobile devices have become more and more ubiquitous recently. This ubiquity gives chance for mobile advertising, especially location-based advertising, to develop into a very promising market. In many location-based advertising services, it is implied that service providers would obtain actual locations of users in order to serve relevant advertisements which are near users’ current locations. However, this practice has raised a significant privacy concern as various private information of an user can be inferred based on her locations and trajectories. In this work, we propose PrAd, a location-based advertising model that appreciates users’ location privacy; i.e. it never reveals their locations to any untrusted party. Our solution is conceptualized based on several state-of-the-art privacy preserving techniques such as data obfuscation, space encoding and private information retrieval (PIR). We especially introduce algorithmic modification to existing hardware-based PIR technique to make it more practical and thus suit real-time applications. Moreover, PrAd enables a correct billing mechanism among involved parties without revealing any individual sensitive information. Finally, we confirm the effectiveness of our proposed framework by evaluating its performance using a real world dataset.

By definition, fully homomorphic encryption (FHE) schemes support homomorphic decryption, and all known FHE constructions are bootstrapped from a Somewhat Homomorphic Encryption (SHE) scheme via this technique. Additionally, when a public key is provided, ciphertexts are also re-randomizable, e.g., by adding to them fresh encryptions of 0. From those two operations we devise an algorithm to sanitize a ciphertext, by making its distribution canonical. In particular, the distribution of the ciphertext does not depend on the circuit that led to it via homomorphic evaluation, thus providing circuit privacy in the honest-but-curious model. Unlike the previous approach based on noise flooding, our approach does not degrade much the security/efficiency trade-off of the underlying FHE. The technique can be applied to all lattice-based FHE proposed so far, without substantially affecting their concrete parameters.

We are looking for a research scientist or post-doc in cryptography to work on novel cryptographic concepts for emerging ICT domains (e.g. cloud computing or cyber physical systems). Ideally you have experience in fields like modern public-key cryptography, distributed cryptography, privacy enhancing technologies, or multi-party computation. You will be involved in a EU research projects and advance/improve cryptography for secure and privacy preserving cloud based systems.

Further infos:

• Direct job posting: http://www.ait.ac.at/fileadmin/inserate/Jobs/Science/Scientist_for_Applied_Crypthography.pdf
• AIT Digital Safety & Security Department: http://www.ait.ac.at/departments/digital-safety-security

Closing date for applications: 30 April 2016

Contact:

• Thomas Loruenser, Department Digital Safety & Security, AIT Austrian Institute of Technology, or
• Maria Leonhard-Maurer, Head of Human Resources, E-Mail: maria.leonhard-maurer (at) ait.ac.at

More information: http://www.ait.ac.at/fileadmin/inserate/Jobs/Science/Scientist_for_Applied_Crypthography.pdf

This is a fantastic opportunity to work on a variety of exciting projects for a global leading company.

The successful candidate for this position will have significant experience performing security evaluation tasks on customers’ products – through code review, vulnerability analysis, test planning and interpretation of test results. The tasks are mainly carried out on embedded products, particularly payment devices, such as smart cards, POS terminals and mobile payment devices. A formal report will then be prepared for the customer.

Security Analysts are expected to maintain a high level of expertise regarding known threats and to follow technical developments in the embedded security arena to protect transaction applications. You will be particularly experienced in C, Java, assembly languages, GlobalPlatform and EMV standards, perhaps with a background in cryptography or data security. You will also be responsible for supporting the Project Management team on evaluation scoping, resource requirements, and certification body and customer expectations. Formal report writing in line with customer and certification scheme requirements will also be required.

Closing date for applications: 20 April 2016

Contact: Dom Gooch / 02032067564 / dominic.gooch (at) solagroup.com

We seek to hire a PhD student for the CryptoLux group led by Prof. Alex Biryukov. We are looking for candidates in one of the topics:

applied crypto, cryptanalysis, crypto finance, privacy.

Applications will be considered on receipt therefore applying before the deadline is encouraged.

Closing date for applications: 30 March 2016

Contact: Prof. Alex Biryukov

More information: https://www.cryptolux.org/index.php/Vacancies

In this paper we describe ZKBoo1, a proposal for practically efficient zero-knowledge arguments especially tailored for Boolean circuits and report on a proof-of-concept implementation. As an highlight, we can generate (resp. verify) a non-interactive proof for the SHA-1 circuit in approximately 13ms (resp. 5ms), with a proof size of 444KB. Our techniques are based on the “MPC-in-the-head” approach to zero-knowledge of Ishai et al. (IKOS), which has been successfully used to achieve significant asymptotic improvements. Our contributions include: 1) A thorough analysis of the different variants of IKOS, which highlights their pro and cons for prac- tically relevant soundness parameters; 2) A generalization and simplification of their approach, which leads to faster Σ-protocols (that can be made non-interactive using the Fiat-Shamir heuristic) for statements of the form “I know x such that y = f(x)” (where f is a circuit and y a public value); 3) A case study, where we provide explicit protocols, implementations and benchmarking of zero- knowledge protocols for the SHA-1 and SHA-256 circuits.

We show that differing-inputs obfuscation (diO) for Turing Machines is impossible to achieve. Our results are: (1) If sub-exponentially secure one-way functions exist then sub-exponentially secure diO for TMs does not exist (2) If in addition sub-exponentially secure iO exists then polynomially secure diO for TMs does not exist.