International Association for Cryptologic Research

IACR News Central

Here you can see all recent updates to the IACR webpage. These updates are also available:

Now viewing news items related to:

22 June 2018
The MD transform that underlies the MD and SHA families iterates a compression function $\mathsf{h}$ to get a hash function $\mathsf{H}$. The question we ask is, what property X of $\mathsf{h}$ guarantees collision resistance (CR) of $\mathsf{H}$? The classical answer is that X itself be CR. We show that weaker conditions X, in particular forms of what we call constrained-CR, suffice. This reduces demands on compression functions, to the benefit of security, and also, forensically, explains why collision-finding attacks on compression functions have not, historically, lead to immediate breaks of the corresponding hash functions. We obtain our results via a definitional framework called RS security, and a parameterized treatment of MD, that also serve to unify prior work and variants of the transform.
We analyze the FOO electronic voting protocol in the provable secu- rity model using the technique of Computationally Complete Symbolic Attacker (CCSA). The protocol uses commitments, blind signatures and anonymous chan- nels to achieve vote privacy. Unlike the Dolev-Yao analyses of the protocol, we assume neither perfect cryptography nor existence of perfectly anonymous chan- nels. Our analysis reveals new attacks on vote privacy, including an attack that arises due to the inadequacy of the blindness property of blind signatures and not due to a specific implementation of anonymous channels. With additional assumptions and modifications, we were able to show that the protocol satisfies vote privacy. Our techniques demonstrate effectiveness of the CCSA technique for both attack detection and verification.
We construct an efficiently verifiable slow-timed hash function. A slow-timed hash function is a hash function with the guarantee that its evaluation requires to run a given number of sequential steps, but the result can be efficiently verified. They have applications in decentralised systems, such as the generation of trustworthy public randomness in a trustless environment. To construct a slow-timed hash function, we actually build a trapdoor slow-timed hash function. A trapdoor slow-timed hash function is essentially a slow-timed hash function which can be evaluated efficiently by parties who know a secret (the trapdoor). By setting up this scheme in a way that the trapdoor is unknown (not even by the party running the setup), we obtain a simple slow-timed hash function.
In this paper, we propose a new technique to perform several homomorphic operations in one bootstrapping call over a multi-value plaintext space. Our construction relies on the FHEW-based gate bootstrapping: we analyze its structure and propose a strategy we call multi-value bootstrapping which allows to bootstrap an arbitrary function in an efficient way. The security of our scheme relies on the LWE assumption over the torus. We give three applications: the first one is the efficient evaluation of an arbitrary boolean function (LUT), the second one is the optimization of the circuit bootstrapping from (Asiacrypt'2017) which allows to compose circuits in a leveled mode, the third one is the homomorphic evaluation of a neural network where the linear part is evaluated using a generalization of the key-switching procedure and the non-linear part is evaluated with our multi-value bootstrapping.

We have implemented the proposed method and were able to evaluate arbitrary 6-to-6 LUTs under 1.2 seconds. Our implementation is based on the TFHE library but can be easily integrated into other homomorphic libraries based on the same structure, such as FHEW (Eurocrypt'2015). The number of LUT outputs does not influence the execution time by a lot, e.g. evaluation of additional 128 outputs on the same 6 input bits takes only 0.05 more seconds.
The ARM TrustZone is a security extension which is used in recent Samsung flagship smartphones to create a Trusted Execution Environment (TEE) called a Secure World, which runs secure processes (Trustlets). The Samsung TEE includes cryptographic key storage and functions inside the Keymaster trustlet. The secret key used by the Keymaster trustlet is derived by a hardware device and is inaccessible to the Android OS. However, the ARM32 AES implementation used by the Keymaster is vulnerable to side channel cache-attacks. The Keymaster trustlet uses AES-256 in GCM mode, which makes mounting a cache attack against this target much harder. In this paper we show that it is possible to perform a successful cache attack against this AES implementation, in AES-256/GCM mode, using widely available hardware. Using a laptop's GPU to parallelize the analysis, we are able to extract a raw AES-256 key with 7 minutes of measurements and under a minute of analysis time and an AES-256/GCM key with 40 minutes of measurements and 30 minutes of analysis.
The threat of side-channels is becoming increasingly prominent for resource-constrained internet-connected devices. While numerous power side-channel countermeasures have been proposed, a promising approach to protect the non-invasive electromagnetic side-channel attacks has been relatively scarce. Today's availability of high-resolution electromagnetic (EM) probes mandates the need for a low-overhead solution to protect EM side-channel analysis (SCA) attacks. This work, for the first time, performs a white-box analysis to root-cause the origin of the EM leakage from an integrated circuit. System-level EM simulations with Intel 32 nm CMOS technology interconnect stack reveals that the EM leakage from metals above layer 8 can be detected by an external non-invasive attacker with the commercially available EM probes. This work proposes a two-stage solution to eliminate the critical signal radiation from the higher-level metal layers. Firstly, we propose routing the entire cryptographic core using the local lower-level metal layers, whose leakage cannot be picked up by an external attacker. Then, the entire crypto IP is embedded within a signature attenuation hardware (SAH) which in turn suppresses the critical encryption signature and finally connects to the highly radiating top-level metal layers. We utilize the Attenuated Signature Noise Injection (ASNI) circuit, which was recently proposed as a low-overhead generic power SCA countermeasure, in order to encapsulate the cryptographic core with local low-level metal routing, and thereby significantly suppress the critical signatures even before it reaches to the higher metals. System-level implementation of the ASNI circuit with local lower-level metal layers in TSMC 65 nm CMOS technology, with an AES-128 core (as an example cryptographic engine) operating at 40 MHz, shows that the system remains secure against EM SCA attack even after $1 M$ encryptions, with $67\%$ power efficiency compared to the unprotected AES.
Oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (JACM 1996), can be used to read and write to memory in a way that hides which locations are being accessed. The best known ORAM schemes have an $O(\log n)$ overhead per access, where $n$ is the data size. The work of Goldreich and Ostrovsky gave a lower bound showing that this is optimal for ORAM schemes that operate in a ``balls and bins'' model, where memory blocks can only be shuffled between different locations but not manipulated otherwise. The lower bound even extends to weaker settings such as offline ORAM, where all of the accesses to be performed need to be specified ahead of time, and read-only ORAM, which only allows reads but not writes. But can we get lower bounds for general ORAM, beyond ``balls and bins''?

The work of Boyle and Naor (ITCS '16) shows that this is unlikely in the offline setting. In particular, they construct an offline ORAM with $o(\log n)$ overhead assuming the existence of small sorting circuits. Although we do not have instantiations of the latter, ruling them out would require proving new circuit lower bounds. On the other hand, the recent work of Larsen and Nielsen (CRYPTO '18) shows that there indeed is an $\Omega(\log n)$ lower bound for general online ORAM.

This still leaves the question open for online read-only ORAM or for read/write ORAM where we want very small overhead for the read operations. In this work, we show that a lower bound in these settings is also unlikely. In particular, our main result is a construction of online ORAM where reads (but not writes) have an $o(\log n)$ overhead, assuming the existence of small sorting circuits as well as very good locally decodable codes (LDCs). Although we do not have instantiations of either of these with the required parameters, ruling them out is beyond current lower bounds.
Substitution Boxes (S-Boxes) are crucial components in the design of many symmetric ciphers. The security of these ciphers against linear, differential, algebraic cryptanalyses and side-channel attacks is then strongly dependent on the choice of the S-Boxes. To construct S-Boxes having good resistive properties both towards classical cryptanalysis as well side-channel attacks is not a trivial task. In this article we propose new methods for generating S-Boxes with strong cryptographic properties and therefore study the resilience of such S-Boxes against side-channel attacks in terms of its theoretical metrics and masking possibility.
ePrint Report Two Notions of Differential Equivalence on Sboxes Christina Boura, Anne Canteaut, Jérémy Jean, Valentin Suder
In this work, we discuss two notions of differential equivalence on Sboxes. First, we introduce the notion of DDT-equivalence which applies to vectorial Boolean functions that share the same difference distribution table (DDT). Next, we compare this notion to what we call the $\gamma$-equivalence, applying to vectorial Boolean functions whose DDTs have the same support. We discuss the relation between these two equivalence notions, demonstrate that the number of DDT- or $\gamma$-equivalent functions is invariant under EA- and CCZ-equivalence and provide an algorithm for computing the DDT-equivalence and the $\gamma$-equivalence classes of a given function. We study the sizes of these classes for some families of Sboxes. Finally, we prove a result that shows that the rows of the DDT of an APN permutation are pairwise distinct.
Multi-Key Homomorphic Signatures (MKHS) enable clients in a system to sign and upload messages to an untrusted server. At any later point in time, the server can perform a computation $C$ on data provided by $t$ different clients, and return the output $y$ and a short signature $\sigma{C, y}$ vouching for the correctness of $y$ as the output of the function $f$ on the signed data. Interestingly, MKHS enable verifiers to check the validity of the signature using solely the public keys of the signers whose messages were used in the computation. Moreover, the signatures $\sigma{C, y}$ are succinct, namely their size depends at most linearly in the number of clients, and only logarithmically in the total number of inputs of $C$. Existing MKHS are constructed based either on standard assumptions over lattices (Fiore et al., ASIACRYPT'16), or on non-falsifiable assumptions (SNARKs) (Lai et al., ePrint'16). In this paper, we investigate connections between single-key and multi-key homomorphic signatures. We propose a generic compiler, called \matrioska, which turns any (sufficiently expressive) single-key homomorphic signature scheme into a multi-key scheme. Matrioska establishes a formal connection between these two primitives and is the first alternative to the only known construction under standard falsifiable assumptions. Our result relies on a novel technique that exploits the homomorphic property of a single-key HS scheme to compress an arbitrary number of signatures from $t$ different users into only $t$ signatures.
The existence of secure indistinguishability obfuscators (iO) has far-reaching implications, significantly expanding the scope of problems amenable to cryptographic study. All known approaches to constructing iO rely on d-linear maps which allow the encoding of elements from a large domain, evaluating degree d polynomials on them, and testing if the output is zero. While secure bilinear maps are well established in cryptographic literature, the security of candidates for $d>2$ is poorly understood.

We propose a new approach to constructing iO for general circuits. Unlike all previously known realizations of iO, we avoid the use of d-linear maps of degree $d\ge 3$.

At the heart of our approach is the assumption that a new weak pseudorandom object exists, that we call a perturbation resilient generator ($\Delta\mathsf{RG}$). Informally, a $\Delta\mathsf{RG}$ maps n integers to m integers, and has the property that for any sufficiently short vector $a\in \mathbb{Z}^m$, all efficient adversaries must fail to distinguish the distributions $\Delta\mathsf{RG}(s)$ and $(\Delta\mathsf{RG}(s)+a)$, with at least some probability that is inverse polynomial in the security parameter. We require that the $\Delta\mathsf{RG}$ be computable by degree-2 polynomials over Z. We use techniques building upon the Dense Model Theorem to deal with adversaries that have nontrivial but non-overwhelming distinguishing advantage.

As a result, we obtain iO for general circuits assuming:

- Subexponentially secure LWE

- Bilinear Maps

- $(1-1/poly(\lambda))$-secure 3-block-local PRGs

- $1/poly(\lambda)$-secure $\Delta\mathsf{RG}$s
ePrint Report A Note on Key Rank Daniel P. Martin, Marco Martinoli
In recent years key rank has become an important aspect of side-channel analysis, enabling an evaluation lab to analyse the security of a device after a side-channel attack. In particular, it enables the lab to do so when the enumeration effort would be beyond their computing power. Due to its importance there has been a host of work investigating key rank over the last few years. In this work we build upon the existing literature to make progress on understanding various properties of key rank. We begin by showing when two different "scoring methods" will provide the same rank. This has been implicitly used by various algorithms in the past but here it is shown for a large class of functions. We conclude by giving the computational complexity of key rank. This implies that it is unlikely for, considerably, better algorithms to exist.
We introduce a new notion of one-message zero-knowledge (1ZK) arguments that satisfy a weak soundness guarantee — the number of false statements that a polynomial-time non-uniform adversary can convince the verifier to accept is not much larger than the size of its non-uniform advice. The zero-knowledge guarantee is given by a simulator that runs in (mildly) super-polynomial time.

We construct such 1ZK arguments based on the notion of multi-collision-resistant keyless hash functions, recently introduced by Bitansky, Kalai, and Paneth (STOC 2018). Relying on the constructed 1ZK arguments, subexponentially-secure time-lock puzzles, and other standard assumptions, we construct one-message fully-concurrent non-malleable commitments. This is the first construction that is based on assumptions that do not already incorporate non-malleability, as well as the first based on (subexponentially) falsifiable assumptions.
Zerocoin (Miers et. al, IEEE S&P’13), designed as an extension to Bitcoin and similar cryptocurrencies, was the first anonymous cryptocurrency proposal which supports large anonymity sets. We identify a cryptographic denial-of-spending attack on the original Zerocoin protocol and a second Zerocoin protocol (Groth and Kohlweiss, EUROCRYPT’15), which enables a network attacker to destroy money of honest users. The attack leads to real-world vulnerabilities in multiple cryptocurrencies, which rely on implementations of the original Zerocoin protocol.

The existence of the attack does not contradict the formal security analyses of the two Zerocoin protocols but exposes the lack of an important missing property in the security model of Zerocoin. While the security definitions model that the attacker should not be able to create money out of thin air or steal money from honest users, it does not model that the attacker cannot destroy money of honest users. Fortunately, there are simple fixes for the security model and for both protocols.
ePrint Report Is Java Card ready for hash-based signatures? Ebo van der Laan, Erik Poll, Joost Rijneveld, Joeri de Ruiter, Peter Schwabe, Jan Verschuren
The current Java Card platform does not seem to allow for fast implementations of hash-based signature schemes. While the underlying implementation of the cryptographic primitives provided by the API can be fast, thanks to implementations in native code or in hardware, the cumulative overhead of the many separate API calls results in prohibitive performance for many common applications. In this work, we present an implementation of XMSS$^{MT}$ on the current Java Card platform, and make suggestions how to improve this platform in future versions.
ePrint Report Hierarchical Attribute-based Signatures Constantin-Catalin Dragan, Daniel Gardham, Mark Manulis
Attribute-based Signatures (ABS) are a powerful tool allowing users with attributes issued by authorities to sign messages while also proving that their attributes satisfy some policy. ABS schemes provide flexible and privacy-preserving approach to authentication since the signer's identity and attributes remain hidden within the anonymity set of users sharing policy-conform attributes. Current ABS schemes exhibit some limitations when it comes to the management and issue of attributes. In this paper we address the lack of support for hierarchical attribute management, a property that is prevalent in traditional PKIs where certification authorities are organised into hierarchies and signatures are verified along roots of trust.

Hierarchical Attribute-based Signatures (HABS) introduced in this work support delegation of attributes along paths from the top-level authority down to the users while also ensuring that signatures produced by these users do not leak their delegation paths, thus extending the original privacy guarantees of ABS schemes. Our generic HABS construction also ensures unforgeability of signatures in the presence of collusion attacks and contains an extended tracebility property allowing a dedicated tracing authority to identify the signer and reveal its attribute delegation paths. We include public verification procedure for the accountability of the tracing authority.

We anticipate that HABS will be useful for privacy-preserving authentication in applications requiring hierarchical delegation of attribute-issuing rights and where knowledge of delegation paths might leak information about signers and their attributes, e.g., in intelligent transport systems where vehicles may require certain attributes to authenticate themselves to the infrastructure but remain untrackable by the latter.
We revisit the factoring with known bits problem on general RSA moduli in the forms of $N=p^r q^s$ for $r,s\ge 1$, where two primes $p$ and $q$ are of the same bit-size. The relevant moduli are inclusive of $pq$, $p^r q$ for $r>1$, and $p^r q^s$ for $r,s>1$, which are used in the standard RSA scheme and other RSA-type variants. Previous works acquired the results mainly by solving univariate modular equations. In contrast, we investigate how to efficiently factor $N=p^r q^s$ with given leakage of the primes by the integer method using the lattice-based technique in this paper. More precisely, factoring general RSA moduli with known most significant bits (MSBs) of the primes can be reduced to solving bivariate integer equations, which was first proposed by Coppersmith to factor $N=pq$ with known high bits. Our results provide a unifying solution to the factoring with known bits problem on general RSA moduli. Furthermore, we reveal that there exists an improved factoring attack via the integer method for particular RSA moduli like $p^3 q^2$ and $p^5 q^3$.
ePrint Report Domain-specific Accelerators for Ideal Lattice-based Public Key Protocols Hamid Nejatollahi, Nikil Dutt, Indranil Banerjee, Rosario Cammarota
Post Quantum Lattice-Based Cryptography (LBC) schemes are increasingly gaining attention in traditional and emerging security problems, such as encryption, digital signature, key exchange, homomorphic encryption etc, to address security needs of both short and long-lived devices — due to their foundational properties and ease of implementation. However, LBC schemes induce higher computational demand compared to classic schemes (e.g., DSA, ECDSA) for equivalent security guarantees, making domain-specific acceleration a viable option for improving security and favor early adoption of LBC schemes by the semiconductor industry. In this paper, we present a workflow to explore the design space of domain-specific accelerators for LBC schemes, to target a diverse set of host devices, from resource-constrained IoT devices to high-performance computing platforms. We present design exploration results on workloads executing NewHope and BLISSB-I schemes accelerated by our domain-specific accelerators, with respect to a baseline without acceleration. We show that achieved performance with acceleration makes the execution of NewHope and BLISSB-I comparable to classic key exchange and digital signature schemes while retaining some form of general purpose programmability. In addition to 44% and 67% improvement in energy-delay product (EDP), we enhance performance (cycles) of the sign and verify steps in BLISSB-I schemes by 24% and 47%, respectively. Performance (EDP) improvement of server and client side of the NewHope key exchange is improved by 37% and 33% (52% and 48%), demonstrating the utility of the design space exploration framework.
21 June 2018
Job Posting Ph.D. student in Quantum Cryptanalysis University of Amsterdam / Leiden University / Centrum Wiskunde & Informatica (CWI)<br>
The aim of the PhD project is to carry out quantum cryptanalysis of the most promising schemes in the NIST competition for post-quantum cryptography. The objective ranges from identifying potential vulnerabilities in the design to possibly discovering complete breaks, but also considers the question of finding the right choice of parameters for schemes that (seem to) withstand quantum attacks.

Supervision will be shared between QuSoft and Mathematisch Instituut (MI) Leiden, with Christian Schaffner (University of Amsterdam / QuSoft) and Peter Stevenhagen (MI Leiden) as main supervisors and Serge Fehr (CWI / MI Leiden / QuSoft) and Peter Bruin (MI Leiden) as co-supervisors.

You should hold a Master\'s degree (or expect to obtain this by the end of the academic year 2017/18) in computer science, mathematics or physics, with excellent grades and outstanding results, or a comparable degree.

Furthermore you should also possess:

  • a strong background in cryptography, quantum algorithms and/or mathematics (relevant to post-quantum cryptography);

  • demonstrated research abilities, e.g. by completion of an (undergraduate) research project;

  • good academic writing and presentation skills;

  • good social and organisational skills;

  • full professional proficiency in spoken and written English.

See the link below for further information and for the application procedure.

Closing date for applications: 15 July 2018

Contact: Dr Christian Schaffner (c.schaffner (at) uva.nl)

More information: http://www.uva.nl/en/content/vacancies/2018/06/18-371-phd-candidate-in-quantum-cryptanalysis.html

Job Posting Senior Research Software Design Engineer Microsoft Research, Redmond WA, USA
Description available at https://careers.microsoft.com/us/en/job/391591/SENIOR-RSDE

Closing date for applications: 1 August 2018

Contact: Kristin Lauter

Email: klauter (at) microsoft.com

The Institute for IT Security at the University of Lübeck invites applications for an open position as

Professor for Secure Software Systems (W2)

As future holder of the position, you should bring a proven scientific track record in IT Security, especially in at least one of the following areas:

  • Security of Complex and Networked Software Systems
  • Anonymity and Privacy
  • Operating Systems Security
  • Computer Forensics

You bring along a high potential for strengthening the profile of the new Institute for IT Security through research work, project management, and the acquisition of third party funds in the field of IT Security.

Your teaching tasks include participation in the courses of the degree programs of the Department of Computer Science/Engineering, especially in the new Bachelor’s and Master’s program in IT Security.

University of Lübeck offers excellent opportunities for interdisciplinary cooperation in the key areas of Computer Science, Medical Engineering, Robotics, e-Government, Data Science, as well as the Life Sciences and Medicine. In addition, the university supports activities in technology transfer.

For a detailed description of the position as well as necessary templates and further information on the application process, please visit the link below.

Closing date for applications: 18 July 2018

Contact: Susanne Markmann,

Büro der MINT-Sektionen

Email: mint.buero (at) uni-luebeck.de

More information: https://www.uni-luebeck.de/structure/sektionen/sektionen-mint/berufungsverfahren-stellen.html

Applications are invited for two full-time Pre-doc positions in the Security in Information Technology (SIT) Research Group at Technische Universität Darmstadt, Germany, under the direction of Prof. Dr. Michael Waidner.

We are looking for candidates interested in working at the intersection of privacy engineering, and applied cryptography. This project addresses two central challenges in the provision of cloud services: (1) client privacy, and (2) verifiable metering and billing. For challenge (1), we design and develop anonymous communication mechanisms for the cloud. For challenge (2), we build techniques for service verification and design an infrastructure for verifiable metering and billing, enabling clients to verify in real-time their service consumption and corresponding charges. By solving and combining both challenges we obtain privacy-preserving verifiable metering and billing. Further details on the project can be found here.

The vacancy is within the Collaborative Research Center CROSSING, funded by DFG, the German Research Foundation. Collaborative Research Centers are institutions funded by the German Research Foundation (DFG) and are established at universities to pursue a scientifically ambitious, complex, longterm research program. The goal of the center CROSSING is to provide cryptography-based security solutions enabling trust in new and next generation computing environments. For more information about CROSSING please visit www.crossing.tu-darmstadt.de.

As part of its research program CROSSING will develop an opensource software called OpenCCE which will allow users to deploy the developed solutions in a secure and easy way.

Applications will be considered until the positions are filled.

Closing date for applications: 30 September 2018

Contact: Applicants are kindly requested to send their applications to staff-sit (at) crisp-da.de with the subject “Funded PhD position in CRC CROSSING” and a single pdf (< 10MB).

More information: https://www.sit.informatik.tu-darmstadt.de

20 June 2018
Event date: 15 October 2018
Submission deadline: 25 July 2018
Notification: 15 August 2018
18 June 2018
Job Posting Post-doc Universite Libre de Bruxelles, Belgium
Applications are invited for a one-year Post-Doc position in the Quality and Computer Security Research Lab and the Algorithmic Group of the Université Libre de Bruxelles.

The successful applicant will work on the analysis and design of searchable encryption schemes and on data structures enabling efficient search operations on encrypted data.

Candidates shall hold a PhD degree in Computer Science or related field, should have experience in the research field of the position and should be fluent in English.

Applications must include:

- A Curriculum Vitae

- A motivation letter

- The list of publications and a copy of three selected publications

- The copies of diplomas and certificates

- Two (or more) reference letters

- The date from which the applicant will be available

Applications must be sent to olivier.markowitch (at) ulb.ac.be and stefan.langerman (at) ulb.ac.be

Closing date for applications: 1 October 2018

Contact: Olivier Markowitch, Universite Libre de Bruxelles, Computer Science Department, olivier.markowitch (at) ulb.ac.be

More information: https://qualsec.ulb.ac.be/about-2/post-doc-position/

Job Posting Post-doc (RA) University of Luxembourg
The successful candidate will join the APSIA group led by Prof. Peter Y. A. Ryan. The candidate will be part of the Eureopean H2020 project “FutureTPM”, and will conduct research on the design and analysis of quantum-safe Trusted Platform Modules (TPM). The candidate will be supervised by Prof. Peter Y. A. Ryan and Dr. Alfredo Rial. The candidate’s tasks include the following:

Shaping research directions and producing results in one or more of the following topics:

Develop and analyse quantum-safe algorithms and protocols.

Explore the incorporation of quantum-safe algorithms in a TPM architecture.

Define security properties and models for a TPM against quantum adversaries.

Coordinating research projects and delivering outputs

Collaborating with partners in the FutureTPM project

Providing guidance to PhD and MSc students

Disseminating results through scientific publications

Closing date for applications: 6 July 2018

Contact: Peer Y A Ryan, peter.ryan (at) uni.lu or Alfredo Rial, alfredo.rial (at) uni.lu

More information: http://emea3.mrted.ly/1vbm4

Job Posting PhD University of Luxembourg
The successful candidate will join the APSIA group led by Prof. Peter Y. A. Ryan. The candidate will be part of the Luxembourg National Research Fund (FNR) funded project “Quantum Communication with Deniability”, which starts 1st July 2018 and will conduct research on enabling “deniability” using both classical and quantum mechanisms. The candidate will be supervised by Prof. Peter Y. A. Ryan and Dr. Peter Roenne. The candidate’s tasks include the following:

Research on the following topics in quantum cryptography and information theory:

Exploring formal definitions of the notion of deniability against various threat models.

Exploring the limits of what is achievable in terms of deniability using both classical and quantum mechanisms.

Designing and analysing novel protocols and mechanisms to achieve stronger forms of deniability.

Providing guidance to M.Sc. students

Closing date for applications: 6 July 2018

Contact: P Y A Ryan, peter.ryan (at) uni.lu

More information: http://emea3.mrted.ly/1vblq

ePrint Report Privacy Preserving Verifiable Key Directories Melissa Chase, Apoorvaa Deshpande, Esha Ghosh
In recent years, some of the most popular online chat services such as iMessage and WhatsApp have deployed end-to-end encryption to mitigate some of the privacy risks to the transmitted messages. But facilitating end-to-end encryption requires a Public Key Infrastructure (PKI), so these services still require the service provider to maintain a centralized directory of public keys. A downside of this design is placing a lot of trust in the service provider; a malicious or compromised service provider can still intercept and read users' communication just by replacing the user's public key with one for which they know the corresponding secret. A recent work by Melara et al. builds a system called CONIKS where the service provider is required to prove that it is returning a consistent for each user. This allows each user to monitor his own key and reduces some of the risks of placing a lot of trust in the service provider. New systems [EthIKS,Catena] are already being built on CONIKS. While these systems are extremely relevant in practice, the security and privacy guarantees of these systems are still based on some ad-hoc analysis rather than on a rigorous foundation. In addition, without modular treatment, improving on the efficiency of these systems is challenging. In this work, we formalize the security and privacy requirements of a verifiable key service for end-to-end communication in terms of the primitive called {\em Verifiable Key Directories} (VKD). Our abstraction captures the functionality of all three existing systems: CONIKS, EthIKS and Catena. We quantify the leakage from these systems giving us a better understanding of their privacy in concrete terms. Finally, we give a VKD construction (with concrete efficiency analysis) which improves significantly on the existing ones in terms of privacy and efficiency. Our design modularly builds from another primitive that we define as append-only zero knowledge sets (aZKS) and from append-only Strong Accumulators. By providing modular constructions, we allow for the independent study of each of these building blocks: an improvement in any of them would directly result in an improved VKD construction. Our definition of aZKS generalizes the definition of the zero knowledge set for updates, which is a secondary contribution of this work, and can be of independent interest.
ePrint Report Continuously Non-Malleable Codes with Split-State Refresh Antonio Faonio, Jesper Buus Nielsen, Mark Simkin, Daniele Venturi
Non-malleable codes for the split-state model allow to encode a message into two parts, such that arbitrary independent tampering on each part, and subsequent decoding of the corresponding modified codeword, yields either the same as the original message, or a completely unrelated value. Continuously non-malleable codes further allow to tolerate an unbounded (polynomial) number of tampering attempts, until a decoding error happens. The drawback is that, after an error happens, the system must self-destruct and stop working, otherwise generic attacks become possible.

In this paper we propose a solution to this limitation, by leveraging a split-state refreshing procedure. Namely, whenever a decoding error happens, the two parts of an encoding can be locally refreshed (i.e.,\ without any interaction), which allows to avoid the self-destruct mechanism in some applications. Additionally, the refreshing procedure can be exploited in order to obtain security against continual leakage attacks. We give an abstract framework for building refreshable continuously non-malleable codes in the common reference string model, and provide a concrete instantiation based on the external Diffie-Hellman assumption.

Finally, we explore applications in which our notion turns out to be essential. The first application is a signature scheme tolerating an arbitrary polynomial number of split-state tampering attempts, without requiring a self-destruct capability, and in a model where refreshing of the memory happens only after an invalid output is produced. This circumvents an impossibility result from a recent work by Fuijisaki and Xagawa (Asiacrypt 2016). The second application is a compiler for tamper-resilient read-only RAM programs. In comparison to other tamper-resilient RAM compilers, ours has several advantages, among which the fact that, in some cases, it does not rely on the self-destruct feature.
In this paper, we propose a new type of non-recursive Mastrovito multiplier for $GF(2^m)$ using a $n$-term Karatsuba algorithm (KA), where $GF(2^m)$ is defined by an irreducible trinomial, $x^m+x^k+1, m=nk$. We show that such a type of trinomial combined with the $n$-term KA can fully exploit the spatial correlation of entries in related Mastrovito product matrices and lead to a low complexity architecture. The optimal parameter $n$ is further studied. As the main contribution of this study, the lower bound of the space complexity of our proposal is about $O(\frac{m^2}{2}+m^{3/2})$. Meanwhile, the time complexity matches the best Karatsuba multiplier known to date. To the best of our knowledge, it is the first time that Karatsuba-based multiplier has reached such a space complexity bound while maintaining relatively low time delay.
ePrint Report Attack on Kayawood Protocol: Uncloaking Private Keys Matvei Kotov, Anton Menshov, Alexander Ushakov
We analyze security properties of a two-party key-agreement protocol recently proposed by I. Anshel, D. Atkins, D. Goldfeld, and P. Gunnels, called Kayawood protocol. At the core of the protocol is an action (called E-multiplication) of a braid group on some finite set. The protocol assigns a secret element of a braid group to each party (private key). To disguise those elements, the protocol uses a so-called cloaking method that multiplies private keys on the left and on the right by specially designed elements (stabilizers for E-multiplication).

We present a heuristic algorithm that allows a passive eavesdropper to recover Alice's private key by removing cloaking elements. Our attack has 100% success rate on randomly generated instances of the protocol for the originally proposed parameter values and for recent proposals that suggest to insert many cloaking elements at random positions of the private key. Our implementation of the attack is available on GitHub.

  older items