International Association
for Cryptologic Research

At ACISP 2017, Wu et al. presented an identity-based encryption with equality test (IBEET) that considers to prevent insider attacks. To analyze its security, they proposed a new security notion for IBEET, which is slightly weaker than the indistinguishability under adaptive identity and chosen ciphertext attacks (IND-ID-CCA2) for traditional identity-based encryption. Then, they claimed that their proposed scheme achieves this new security notion under the Bilinear Diffie-Hellman (BDH) assumption in the random oracle model.

In this paper, we demonstrate that their scheme does not achieve the claimed security requirement by presenting an attack. Our attack algorithm is very simple: It requires only a pair of message and ciphertext, and takes one exponentiation and two bilinear map evaluations. Subsequently, we present a modification of their IBEET construction and show that it satisfies their security notion under the BDH assumption and the existence of strong pseudorandom permutation and existentially unforgeable message authentication code in the random oracle model. We remark that our modification has better efficiency than the original construction.

In Public-Key Encryption, traditionally no security is expected if honest parties use keys provided by an adversary. In this work, we re-examine this premise. While using untrusted keys may seem nonsensical at first glance, we argue the use of providing certain security guarantees even in such situations. We propose Chosen Object Attack (COA) security as a broad generalization of various notions of security that have been considered in the literature, including CCA security, key anonymity and robustness, along with concerns arising from untrusted keys. The main premise of this definition is that any of the objects in a cryptographic scheme could be adversarialy generated, and that should not compromise the security of honest parties in a way an idealized scheme would not have.

Our contributions are threefold.

• Firstly, we develop a comprehensive security definition for PKE in the real/ideal paradigm. Our definition subsumes CCA2 security, Anonymity and Robustness as special cases, and also addresses security concerns in complex application scenarios where the keys may be malicious (without having to explicitly model the underlying attack scenarios). To avoid impossibility results associated with simulation-based security, we use the notion of indistinguishability-preserving security (IND-PRE) from the “Cryptographic Agents” framework (Agrawal et al., EUROCRYPT 2015). Towards this, we extend this framework to accommodate adversarially created objects. Our definition can alternately be interpreted as the union of all possible game-based security definitions. We remark that the agents framework as extended in this work is applicable to primitives other than Public-Key Encryption, and would be of broader significance.

• Secondly, and somewhat surprisingly, we show that in the case of PKE, the above comprehensive definition is implied by a simpler definition (which we call COA security) that combines a traditional game-based definition with a set of consistency requirements. The proof of this implication relies on an extensive analysis of all possible executions involving arbitrarily many keys and ciphertexts, generated, transferred between parties and used in an arbitrary and adaptive manner.

• Thirdly, we consider constructions. Interestingly, using the above security definition, we show that the Cramer-Shoup cryptosystem (with minor modifications) already meets our definition. Further, we present transformations from any Anonymous CCA2-secure PKE scheme to a COA-secure PKE. Under mild correctness conditions on the Anonymous CCA2-secure PKE scheme, our transformation can be instantiated quite efficiently and is arguably a viable enhancement for PKE schemes used in practice.

During the last decade, constant-time cryptographic software has quickly transitioned from an academic construct to a concrete security requirement for real-world libraries. Most of OpenSSL's constant-time code paths are driven by cryptosystem implementations enabling a dedicated flag at runtime. This process is perilous, with several examples emerging in the past few years of the flag either not being set or software defects directly mishandling the flag.

In this work, we propose a methodology to analyze security-critical software for side-channel insecure code path traversal.

Applying our methodology to OpenSSL, we identify three new code paths during RSA key generation that potentially leak critical algorithm state.

Exploiting one of these leaks, we design, implement, and mount a single trace cache-timing attack on the GCD computation step. We overcome several hurdles in the process, including but not limited to:

(1) granularity issues due to word-size operands to the GCD function;

(2) bulk processing of desynchronized trace data;

(3) non-trivial error rate during information extraction; and

(4) limited high-confidence information on the modulus factors.

Formulating lattice problem instances after obtaining and processing this limited information, our attack achieves roughly a 28 % success rate for key recovery using the empirical data from roughly 10K trials.

Event date: 6 September to 7 September 2018
Submission deadline: 18 June 2018

The Cryptolux/SnT team of the University of Luxembourg is offering one Ph.D. student position in Applied Cryptography for the FinCrypt project funded by the Luxembourg research fund (FNR). The project will study security, scalability and privacy of distributed ledgers and smart contracts. Candidates with expertise or interest in the following areas are welcome to apply:

- Applied Cryptography (SK or PK)

- Crypto-currencies, smart-contracts, financial cryptography

- Privacy enhancing technologies

- Distributed consensus protocols

- Cybersecurity

We offer:

You will work in an exciting international environment and will carry leading edge research in these hot research areas. Luxembourg’s financial center is one of the largest in Europe and our team is part of Security and Trust (SnT) research center (>200 people researching all aspects of IT security). The University offers highly competitive salaries (about 34,000 euro/year gross + benefits) and is an equal opportunity employer.

Applications, written in English, should be submitted by e-mail, and will be considered on receipt therefore applying before the deadline is highly encouraged.

Closing date for applications: 31 May 2018

Contact: Prof. Alex Biryukov

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

Event date: 29 October to 31 October 2018
Submission deadline: 8 June 2018
Notification: 20 July 2018

Postdoc research fellow positions available at CMU. Sample research topics include: secure multi-party computation, zero-knowledge proofs, blockchains and cryptocurrencies, and, non-malleable cryptography. However working in any topic within cryptography is possible. Must have a strong publication record in Crypto/Eurocrypt/TCC/STOC/FOCS. Dates are open.

Closing date for applications: 1 November 2018

Contact: Please contact Vipul Goyal at vipul (at) cmu.edu

More information: http://www.cs.cmu.edu/~goyal/

The cryptography group at the Institute of Science and Technology Austria (IST Austria) seeks two postdoctoral researchers, supported by an EU H2020 project (ERC-CoG TOCNeT) on provable security. IST Austria is a recently established basic research institute in the woods of Vienna.

The candidates should have a strong record in cryptography, witnessed by publications at top cryptography (Crypto,Eurocrypt,TCC,...) and/or security conferences (CCS,S&P,...). Current topics investigated in our group include

• Sustainable Blockchains
• Memory-Hard Functions
• Leakage-Resilient Cryptography
• Lattice-Based Cryptography
• Adaptive Security
• Pseudoentropy

The post-doctoral position is provided for up to four years with very competitive salary. The starting dates are flexible. There is no fixed deadline, applications will be considered until the position is filled.

Applications should include CV and a statement of research experience and interests. Please send applications to Krzysztof Pietrzak.

Closing date for applications: 1 September 2018

Contact: Krzysztof Pietrzak pietrzak (at) ist.ac.at

More information: http://pub.ist.ac.at/crypto/

In order to strengthen research and teaching in cryptography at NTNU we are opening a position at the associate professor level (either permanent or tenure track) at the Department of Mathematical Sciences.

The current cryptography group at NTNU works mostly in cryptographic protocol analysis and cryptographic primitives design, with significant applied work in electronic voting. The goal is either to strengthen existing research activities in cryptographic protocol analysis or contribute to complementary areas, such as secure multiparty computation or cryptographic applications of computational number theory/algebraic geometry.

This position is one out of nine strategic professorships announced simultaneously at NTNU. There is also a position in Secure Systems Engineering for which cryptographers may apply.

Closing date for applications: 1 June 2018

Contact: Kristian Gjøsteen, kristian.gjosteen (at) ntnu.no, +47 73 55 02 42

More information: https://www.ntnu.edu/positions-ie

Event date: 20 September to 21 September 2018
Submission deadline: 27 May 2018
Notification: 15 July 2018

Distance bounding (DB) protocols allow a prover to convince a verifier that they are within a distance bound. A public key distance bounding relies on the public key of the users to prove their identity and proximity claim. There has been a number of approaches in the literature to formalize security of public key distance bounding protocols. In this paper we extend an earlier work that formalizes security of public key DB protocols using an approach that is inspired by the security definition of identification protocols, and is referred to it as distance-bounding identification (DBID). We first show that if protocol participants have access to a directional antenna, many existing protocols that have been proven secure, will become insecure, and then show to revise the previous model to include this new capability of the users. DBID approach provides a natural way of modeling man-in-the-middle attack in line with identification protocols, as well as other attacks that are commonly considered in distance bounding protocols. We propose a new DBID scheme, called Poxy, with security proof. We compare the existing public key DB models, and prove the security of the scheme known as ProProx, in our model.

Anonymous Distance-Bounding (DB) protocols allow a prover to convince a verifier that they are within a distance bound from them, without revealing their identity. This is an attractive property that enables the prover to enjoy proximity based services, while their privacy is maintained. Combination of anonymity and distance-bounding however introduces new security challenges. We consider two new realistic attacks: a physical layer attack that uses directional antenna, and a collusion attack that involves multiple users. We show all existing anonymous DB protocols become insecure against at least one of these attacks, and then propose a new security model that captures these new attacks, and finally construct two protocols with provable security in this model. Our protocols are the only known anonymous DB protocols with provable security against known attacks.

We show that PRAMs can be obliviously simulated with perfect security, incurring only $O(\log N \log \log N)$ blowup in parallel runtime, $O(\log^3 N)$ blowup in total work, and $O(1)$ blowup in space relative to the original PRAM. Our results advance the theoretical understanding of Oblivious (Parallel) RAM in several respects. First, prior to our work, no perfectly secure Oblivious Parallel RAM (OPRAM) construction was known; and we are the first in this respect. Second, even for the sequential special case of our algorithm (i.e., perfectly secure ORAM), we not only achieve logarithmic improvement in terms of space consumption relative to the state-of-the-art but also significantly simplify perfectly secure ORAM constructions. Third, our perfectly secure OPRAM scheme matches the parallel runtime of earlier statistically secure schemes with negligible failure probability. Since we remove the dependence (in performance) on the security parameter, our perfectly secure OPRAM scheme in fact asymptotically outperforms known statistically secure ones if (sub-)exponentially small failure probability is desired. Our techniques for achieving small parallel runtime are novel and we employ expander graphs to de-randomize earlier statistically secure schemes --- this is the first time such techniques are used in the constructions of ORAMs/OPRAMs.

We consider a scenario where a server holds a huge database that it wants to make accessible to a large group of clients. After an initial setup phase, clients should be able to read arbitrary locations in the database while maintaining privacy (the server does not learn which locations are being read) and anonymity (the server does not learn which client is performing each read). This should hold even if the server colludes with a subset of the clients. Moreover, the run-time of both the server and the client during each read operation should be low, ideally only poly-logarithmic in the size of the database and the number of clients. We call this notion Private Anonymous Data Access (PANDA).

PANDA simultaneously combines aspects of Private Information Retrieval (PIR) and Oblivious RAM (ORAM). PIR has no initial setup, and allows anybody to privately and anonymously access a public database, but the server's run-time is linear in the data size. On the other hand, ORAM achieves poly-logarithmic server run-time, but requires an initial setup after which only a single client with a secret key can access the database. The goal of PANDA is to get the best of both worlds: allow many clients to privately and anonymously access the database as in PIR, while having an efficient server as in ORAM.

In this work, we construct bounded-collusion PANDA schemes, where the efficiency scales linearly with a bound on the number of corrupted clients that can collude with the server, but is otherwise poly-logarithmic in the data size and the total number of clients. Our solution relies on standard assumptions, namely the existence of fully homomorphic encryption, and combines techniques from both PIR and ORAM. We also extend PANDA to settings where clients can write to the database.

Security of cryptographic schemes is traditionally measured as the inability of resource-constrained adversaries to violate a desired security goal. The security argument usually relies on a sound design of the underlying components. Arguably, one of the most devastating failures of this approach can be observed when considering adversaries such as intelligence agencies that can influence the design, implementation, and standardization of cryptographic primitives. While the most prominent example of cryptographic backdoors is NIST’s Dual_EC_DRBG, believing that such attempts have ended there is naive.

Security of many cryptographic tasks, such as digital signatures, pseudorandom generation, and password protection, crucially relies on the security of hash functions. In this work, we consider the question of how backdoors can endanger security of hash functions and, especially, if and how we can thwart such backdoors. We particularly focus on immunizing arbitrarily backdoored versions of HMAC (RFC 2104) and the hash-based key derivation function HKDF (RFC 5869), which are widely deployed in critical protocols such as TLS. We give evidence that the weak pseudorandomness property of the compression function in the hash function is in fact robust against backdooring. This positive result allows us to build a backdoor-resistant pseudorandom function, i.e., a variant of HMAC, and we show that HKDF can be immunized against backdoors at little cost. Unfortunately, we also argue that safe-guarding unkeyed hash functions against backdoors is presumably hard.

In this paper, we first revisit the generic two-message key exchange (TMKE) scheme (which will be referred to as KF) introduced by Kurosawa and Furukawa (CT-RSA 2014). This protocol is mainly based on key encapsulation mechanism (KEM) which is assumed to be secure against chosen plaintext attacks (IND-CPA). However, we find out that the security of the KF protocol cannot be reduced to IND-CPA KEM. The concrete KF protocol instantiated from ElGamal KEM is even subject to key compromise impersonation (KCI) attacks. In order to overcome the flaws of the KF scheme, we introduce a new generic TMKE scheme from KEM. Instead, we require that the KEM should be secure against one-time adaptive chosen ciphertext attacks (OT-IND-CCA2). We call this class of KEM as OTKEM. In particular, we propose a new instantiation of OTKEM from Ring Learning with Errors (Ring-LWE) problem in the standard model. This yields a concrete post-quantum TMKE protocol with strong security. The security of our TMKE scheme is shown in the extended Canetti-Krawczyk model with perfect forward secrecy (eCK-PFS).

We carry out a systematic study of the GGH15 graded encoding scheme used with general branching programs. This is motivated by the fact that general branching programs are more efficient than permutation branching programs and also substantially more expressive in the read-once setting.

Our main results are as follows:

- Proofs. We present new constructions of private constrained PRFs and lockable obfuscation, for constraints (resp. functions to be obfuscated) that are computable by general branching programs. Our constructions are secure under LWE with subexponential approximation factors. Previous constructions of this kind crucially rely on the permutation structure of the underlying branching programs. Using general branching programs allows us to obtain more efficient constructions for certain classes of constraints (resp. functions), while posing new challenges in the proof, which we overcome using new proof techniques.

- Attacks. We extend the previous attacks on indistinguishability obfuscation (iO) candidates that use GGH15 encodings. The new attack simply uses the rank of a matrix as the distinguisher, so we call it a "rank attack". The rank attack breaks, among others, the iO candidate for general read-once branching programs by Halevi, Halevi, Shoup and Stephens-Davidowitz (CCS 2017).

- Candidates. Drawing upon insights from our proofs and attacks, we present simple candidates for witness encryption and iO that resist the existing attacks, using GGH15 encodings. Our candidate for witness encryption crucially exploits the fact that formulas in conjunctive normal form (CNFs) can be represented by general, read-once branching programs.

This paper introduces a secure and privacy-preserving mechanism for biometric-based user authentication in a distributed manner. The design combines three modalities (face, iris and fingerprint) according to user’s performance strength parameters (False Acceptance and False Rejection Rates). We use a user-specific weighted score level fusion strategy to determine the final multimodal result. The stored unimodal templates are held by distinct database providers that can be malicious. Privacy regulations recognize biometric data as sensitive, hence their handling and storage in an untrusted environment with third parties are challenging. Therefore, we utilize Multi- Party Computation to enhance security among authentication stages. In contrast to the existing research, the novelty of this approach lies in performing multimodal authentication without storing private information in a single database, nor transferring the calculation results to any third party. The proposed protocol is analyzed to assess its usability, security and efficiency (execution time is less than a second under the studied scenario).

At Oakland 2013, R{\"u}hrmair and van Dijk showed that many advanced PUF (Physical Unclonable Function)-based security protocols (e.g. key agreement, oblivious transfer, and bit commitment) can be vulnerable if adversaries get access to the PUF and reuse the responses used in the protocol after the protocol execution. This observation implies the necessity of erasable PUFs for realizing secure PUF-based protocols in practice. Erasable PUFs are PUFs where the responses of any single challenge-response pair (CRP) can be selectively and dedicatedly erased, without affecting any other responses.

In this paper, we introduce two practical implementations of erasable PUFs: Firstly, we propose a full-fledged logical version of an erasable PUF, called programmable logically erasable PUF or PLayPUF, where an additional constant-size trusted computing base keeps track of the usage of every single CRP. Knowing the query history of each CRP, a PLayPUF interface can \textit{automatically} erase an individual CRP, if it has been used for a certain number of times. This threshold can be programmed a-priori to limit the usage of a given challenge in the future before erasure.

Secondly, we introduce two nanotechnological, memristor-based solutions: mrSHIC-PUFs and erasable mrSPUFs. The mrSHIC-PUF is a weak PUF in terms of the size of CRP space, and therefore its readout speed has to be limited intentionally to prolong the time for exhaustive reading. However, each individual response can be {\it physically} altered and erased for good. The erasable mrSPUF, as the second proposed physical erasable PUF, is a strong PUF in terms of the size of CRP space, such that no limit on readout speed is needed, but it can only erase/alter CRPs in groups. Both of these two physical erasable PUFs improve over the state-of-the-art erasable SHIC PUF, which does not offer reconfigurability of erased CRPs making the erasable SHIC PUF less practical.

In passing, we contextualize and locate our new PUF type in the existing landscape, illustrating their essential advantages over variants like reconfigurable PUFs.

Implementation attacks like side-channel and fault attacks are a threat for deployed devices especially if an attacker has physical access to a device. As a consequence, devices like smart cards usually provide countermeasures against implementation attacks, such as masking against side-channel attacks and detection-based countermeasures like temporal redundancy against fault attacks. In this paper, we show how to attack implementations protected with both masking and detection-based fault countermeasures by using statistical ineffective fault attacks using a single fault induction per execution. Our attacks are largely unaffected by the deployed protection order of masking and the level of redundancy of the detection-based countermeasure. Our observations refute the intuition that masking is a viable countermeasure against biased faults, statistical fault attacks, or statistical ineffective fault attacks.