International Association
for Cryptologic Research

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.

In ideal-lattice cryptography, lattices are generated by defining a bijective map between an ideal of a ring of integers and a subset of $\mathbb{C}^n$. This map can be taken to be the coefficient embedding and, along with the Ring-LWE problem, the canonical embedding. However, some lattices cannot be generated using the canonical embedding in a straightforward manner. In this paper, we introduce a new class of problems called $\alpha$-Ring-LWE, which combines Ring-LWE with the twisted canonical embedding. In this context, $\alpha$ stands to be a number field element that distorts the canonical embedding coordinates. We prove the hardness of $\alpha$-Ring-LWE by providing a reduction between the Ring-LWE problem to $\alpha$-Ring-LWE for both search and decision variants. As a result, we obtain a hardness result based on a hard problem over ideal lattices. The addition of a torsion factor enables the construction of a broader class of lattices as rotated lattices. An example is the construction of the integer lattice $\mathbb{Z}^n$ by embedding the ring of integers of the totally real subfield of a cyclotomic number field $\mathbb{Q}(\zeta_p)$ with $p$ being a prime number [BFOV04].

In this paper, we extend the applicability of differential fault attacks to lattice-based cryptography. We show how two deterministic lattice-based signature schemes, Dilithium and qTESLA, are vulnerable to such attacks. In particular, we demonstrate that single random faults can result in a nonce-reuse scenario which allows key recovery. We also expand this to fault-induced partial nonce-reuse attacks, which do not corrupt the validity of the computed signatures and thus are harder to detect.

Using linear algebra and lattice-basis reduction techniques, an attacker can extract one of the secret key elements after a successful fault injection. Some other parts of the key cannot be recovered, but we show that a tweaked signature algorithm can still successfully sign any message. We provide experimental verification of our attacks by performing clock glitching on an ARM Cortex-M4 microcontroller. In particular, we show that up to 65.2% of the execution time of Dilithium is vulnerable to an unprofiled attack, where a random fault is injected anywhere during the signing procedure and still leads to a successful key-recovery.

Software ever-increasingly relies on building blocks implemented by security libraries, which provide access to evolving standards, protocols, and cryptographic primitives. These libraries are often subject to complex development models and long decision-making processes, which limit the ability of contributors to participate in the development process, hinder the deployment of scientific results and pose challenges for OS maintainers.

In this paper, focusing on OpenSSL as a de-facto standard, we analyze these limits, their impact on the security of modern systems, and their significance for researchers.

We propose the OpenSSL ENGINE API as a tool in a framework to overcome these limits, describing how it fits in the OpenSSL architecture, its features, and a technical review of its internals.

We evaluate our methodology by instantiating libsuola, a new ENGINE providing support for emerging cryptographic standards such as X25519 and Ed25519 for currently deployed versions of OpenSSL, performing benchmarks to demonstrate the viability and benefits.

The results confirm that the ENGINE API offers (1) an ideal architecture to address wide-ranging security concerns; (2) a valuable tool to enhance future research by easing testing and facilitating the dissemination of novel results in real-world systems; and (3) a means to bridge the gaps between research results and currently deployed systems.

The recent line of study on randomness extractors has been a great success, resulting in exciting new techniques, new connections, and breakthroughs to long standing open problems in several seemingly different topics. These include seeded non-malleable extractors, privacy amplification protocols with an active adversary, independent source extractors (and explicit Ramsey graphs), and non-malleable codes in the split state model. Previously, the best constructions are given in [Li17]: seeded non-malleable extractors with seed length and entropy requirement $O(\log n+\log(1/\epsilon)\log \log (1/\epsilon))$ for error $\epsilon$; two-round privacy amplification protocols with optimal entropy loss for security parameter up to $\Omega(k/\log k)$, where $k$ is the entropy of the shared weak source; two-source extractors for entropy $O(\log n \log \log n)$; and non-malleable codes in the $2$-split state model with rate $\Omega(1/\log n)$. However, in all cases there is still a gap to optimum and the motivation to close this gap remains strong.

In this paper, we introduce a set of new techniques to further push the frontier in the above questions. Our techniques lead to improvements in all of the above questions, and in several cases partially optimal constructions. This is in contrast to all previous work, which only obtain close to optimal constructions. Specifically, we obtain:

1. A seeded non-malleable extractor with seed length $O(\log n)+\log^{1+o(1)}(1/\epsilon)$ and entropy requirement $O(\log \log n+\log(1/\epsilon))$, where the entropy requirement is asymptotically optimal by a recent result of Gur and Shinkar [GurS17];

2. A two-round privacy amplification protocol with optimal entropy loss for security parameter up to $\Omega(k)$, which solves the privacy amplification problem completely;

3. A two-source extractor for entropy $O(\frac{\log n \log \log n}{\log \log \log n})$, which also gives an explicit Ramsey graph on $N$ vertices with no clique or independent set of size $(\log N)^{O(\frac{\log \log \log N}{\log \log \log \log N})}$; and

4. The first explicit non-malleable code in the $2$-split state model with constant rate, which has been a major goal in the study of non-malleable codes for quite some time. One small caveat is that the error of this code is only (an arbitrarily small) constant, but we can also achieve negligible error with rate $\Omega(\log \log \log n/\log \log n)$, which already improves the rate in [Li17] exponentially.

We believe our new techniques can help to eventually obtain completely optimal constructions in the above questions, and may have applications in other settings.

Backdooring cryptographic algorithms is an indisputable taboo in the cryptographic literature for a good reason: however noble the intentions, backdoors might fall in the wrong hands, in which case security is completely compromised. Nonetheless, more and more legislative pressure is being produced to enforce the use of such backdoors.

In this work we introduce the concept of {\em dispensable cryptographic backdoors} which can be used only once and become useless after that. These exotic primitives are impossible in the classical digital world without stateful and secure trusted hardware support, but, as we show, are feasible assuming quantum computation and access to classical stateless hardware tokens.

Concretely, we construct a dispensable (single-use) version of message authentication codes, and use them to derive a black-box construction of stateful hardware tokens in the above setting with quantum computation and classical stateless hardware tokens. This can be viewed as a generic transformation from stateful to stateless tokens and enables, among other things, one-time programs and memories.

We then use the latter primitives to propose a resolution to the most prominent recent legislative push in favor of backdooring cryptography: the conflict between Apple and FBI last year. We show that it is possible for Apple to create a one-time backdoor which unlocks any single device, and no more than one, i.e., the backdoor becomes useless after it is used. We further describe how to use our ideas to derive a version of CCA-secure public key encryption, which is accompanied with a dispensable (i.e, single-use, as in the above scenario) backdoor.

Offset Public Permutation Mode (OPP) by Granger et al. is a one-pass authenticated encryption scheme supporting associated data (AEAD scheme). Leveraging an error in analysis of the scheme, a chosen plaintext attack that creates a forgery was discovered. This attack makes no assumptions about the underlying tweakable blockcipher while having negligible complexity requirements and high probability of success. An implementation of the attack is also provided.

Silicon Physically Unclonable Functions (PUFs) have been proposed as an emerging hardware security primitive in various applications such as device identification, authentication and cryptographic key generation. Despite their potential, PUF designs based on the Arbiter PUF (APUF) are vulnerable to classical machine learning attacks, which use challenge response pairs. Classical machine learning can be mitigated in the $x$-XOR APUF when enough APUF components have been employed (high $x$). However, reliability based machine learning attacks cannot be prevented by increasing $x$. In this paper, we study the most prominent reliability based machine learning attack, the CMA-ES reliability attack. This work is the first to provide analysis and experimentation to explain under which conditions the CMA-ES reliability attack succeeds and where it fails. Based on these insights, we develop two key contributions. First, we demonstrate how the accuracy of the CMA-ES reliability attack can be improved through enhanced modeling. Second, we propose a new PUF design, the $(x,y)$-Interpose PUF. Through theory and simulation, we show our new PUF model is not vulnerable to the CMA-ES reliability attack, classical machine learning attacks and special attacks that approximate the Interpose PUF as an XOR APUF. In addition, we determine that the security of the IPUF can be reduced to the security of an XOR APUF under classical machine learning attacks, whose complexity depends exponentially on the number of component APUFs in the XOR APUF as shown in the literature. We also show our proposed $(x,y)$-Interpose PUF design is twice as reliable as an $(x+y)$ XOR APUF while using the same hardware overhead as an $(x+y)$ XOR APUF.

We conduct a multi-faceted investigation of the security properties of the three deterministic random bit generator (DRBG) mechanisms recommended in the NIST SP 800-90A standard [4]. This standard received a considerable amount of negative attention, due to the host of controversy and problems with the now retracted DualEC-DRBG, which was included in earlier revisions. Perhaps because of the attention paid to the DualEC, the other algorithms in the standard have received surprisingly patchy analysis to date, despite widespread deployment. This paper provides an analysis of the remaining DRBG algorithms in NIST SP 800-90A. We uncover a mix of positive and less than positive results, emphasizing and addressing the gap between theoretical models, and the NIST DRBGs as specified and used. As an initial positive result, we verify claims in the standard by proving (with a few caveats) the forward security of all three DRBGs. However, digging deeper into flexibility in implementation and usage choices permitted by the standard, we uncover some undesirable properties of these standardized DRBGs. Specifically, we argue that these DRBGs have the property that leaking certain parts of the state may lead to catastrophic failure of the algorithm. Furthermore, we show that flexibility in the specification allows implementers and users of these algorithms to make choices that considerably weaken the algorithms in these scenarios.

Monero is one of the privacy-preserving cryptocurrencies employing CryptoNote protocol. The privacy features in Monero are provided by cryptographic techniques called linkable ring signature and one-time public key. Recent studies show that the majority of Monero inputs are traceable prior to mandatory RingCT transaction. After the RingCT was implemented, the problem was mitigated. We propose a novel attack to reduce the anonymity of Monero transactions or even to fully deanonymise the inputs. The proposed protocol can be launched in RingCT scenario and enable multiple attackers to collaborate without trusting each other. The attack scheme can be planted in the existing Monero services without extra fees and without putting the users’ money at risk.

Postdoc and PhD in cryptographic currencies and anti-surveillance at University of Edinburgh

Worried about surveillance? Imagining a world in which all data is encrypted? Concerned about mistakes in security proofs and bugs in software? Curious about what blockchain technology will look like after the crypto-currency bubble?

At the University of Edinburgh we design distributed cryptographic techniques to protect user\'s online privacy, based on scientific principles using mathematical proofs. A core enabling component is IOHK‘s Cardano blockchain.

Join as a Postdoc or PhD to work on privacy and anonymity, zero-knowledge and multi-party computation. Multiple positions are available. To apply, send your CV with a cover letter and two letters of recommendation. The positions are available until filled.

Contact: Markulf Kohlweiss, mkohlwei (at) ed.ac.uk, https://homepages.inf.ed.ac.uk/mkohlwei/

More Information:

* University of Edinburgh: http://web.inf.ed.ac.uk/security-privacy

* IOHK: https://iohk.io/

Closing date for applications: 31 May 2018

Multi-Party Computation of Oblivious RAM (MPC ORAM) implements secret-shared random access memory in a way that protects access pattern privacy against a threshold of corruptions. MPC ORAM enables secure computation of any RAM program on large data held by different entities, e.g. MPC processing of database queries on a secret-shared database. MPC ORAM can be constructed by any (client-server) ORAM, but there is an efficiency gap between known MPC ORAM's and ORAM's. Current asymptotically best MPC ORAM is implied by an "MPC friendly" variant of Path-ORAM called Circuit-ORAM, due to Wang et al. However, using garbled circuit for Circuit-ORAM's client implies MPC ORAM which matches Path-ORAM in rounds but increases bandwidth by \Omega(kappa) factor, while using GMW or BGW protocols implies MPC ORAM which matches Path-ORAM in bandwidth, but increases round complexity by \Omega(log n loglog n) factor, for kappa the security parameter and n the memory size.

In this paper we bridge the gap between MPC ORAM and client-server ORAM by showing a specialized 3PC ORAM protocol, i.e. MPC ORAM for 3 parties tolerating 1 fault, which uses only symmetric ciphers and asymptotically matches client-server Path-ORAM in round complexity and for large records also in bandwidth.

Our 3PC ORAM also allows for fast pipelined processing: With post- poned clean-up it processes b=O(log n) accesses in O(b+log n) rounds with O(D+poly(log n)) bandwidth per item, where D is record size.

In this work we provide a traitor tracing construction with ciphertexts that grow polynomially in $\log(n)$ where $n$ is the number of users and prove it secure under the Learning with Errors (LWE) assumption. This is the first traitor tracing scheme with such parameters provably secure from a standard assumption. In addition to achieving new traitor tracing results, we believe our techniques push forward the broader area of computing on encrypted data under standard assumptions. Notably, traitor tracing is substantially different problem from other cryptography primitives that have seen recent progress in LWE solutions. We achieve our results by first conceiving a novel approach to building traitor tracing that starts with a new form of Functional Encryption that we call Mixed FE. In a Mixed FE system the encryption algorithm is bimodal and works with either a public key or master secret key. Ciphertexts encrypted using the public key can only encrypt one type of functionality. On the other hand the secret key encryption can be used to encode many different types of programs, but is only secure as long as the attacker sees a bounded number of such ciphertexts. We first show how to combine Mixed FE with Attribute-Based Encryption to achieve traitor tracing. Second we build Mixed FE systems for polynomial sized branching programs (which corresponds to the complexity class LOGSPACE) by relying on the polynomial hardness of the LWE assumption with super-polynomial modulus-to-noise ratio.