International Association
for Cryptologic Research

At Eurocrypt 2017 a tweak to counter Simon’s quantum attack was proposed: replace the common bitwise addition, with other operations, as a modular addition. The starting point of our paper is afollow up of these previous results:

First, we have developped new algorithms that improve and generalize Kuperberg’s algorithm for the hidden shift problem, which is the algorithm that applies instead of Simon when considering modular additions.

Thanks to our improved algorithm, we have been able to build a quantum attack in the superposition model on Poly1305, proposed at FSE 2005,largely used and claimed to be quantumly secure. We also answer an open problem by analyzing the effect of the tweak to the FX construction.

We have also generalized the algorithm. We propose for the first time a quantum algorithm for solving the problem with parallel modular additions, with a complexity that matches both Simon and Kuperberg in its extremes. We also propose a generic algorithm to solve the hidden shift problem in non-abelian groups.

In order to verify the theoretical analysis we performed, and to get concrete estimates of the cost of the algorithms, we have simulated them, and were able to validate our estimated complexities.

Finally, we analyze the security of some classical symmetric constructions with concrete parameters, to evaluate the impact and practicality of the proposed tweak, concluding that it does not seem to be efficient.

Event date: 19 November to 21 November 2018

Event date: 13 August to 14 August 2018

The Department of Computer, Control and Management Engineering Antonio Ruberti (DIAG) of Sapienza University of Rome invites outstanding candidates to express their interests for 1 full-time RTD-B Assistant Professor position (Tenure-track) in Cyber Security (in the context of Computer Science Engineering). The RTD-B Assistant Professor position can be converted after three years into an Associate Professor position if the national qualification (ASN) at the Associate Professor level is obtained in the Academic Discipline \"Information Processing Systems\" (ING-INF/05) of the Italian University System.

Profile

Candidates will hold a PhD from a leading research university, three years of research experience after PhD, and an appropriate record of publications in highly ranked international conferences and journals. Teaching experience is also positively considered.

Position

Successful candidates will be engaged in first-class research in the area of Cyber Security, will supervise Master Thesis and PhD students in their fields, will teach in the Master degree in Cyber Security at Sapienza University of Rome and in the degree of Computer Science Engineering, will be involved in collaborations with industry and public bodies, and will take an important role at the Inter-Departmental Research Center of Cyber Intelligence and Information Security (CIS) at Sapienza University of Rome. Appointments are full-time. The salary is competitive. We especially welcome expression of interests from female scholars.

Expression of Interest

People who are interested in this position should send the following to recruitment (at) diag.uniroma1.it:

1. Curriculum vitae

2. 3-page (max) research statement including the research program that the candidate intends to pursue while at Sapienza.

Expressions of interest should preferably be sent before the end of May 2018. For further information, please consult recruitment (at) diag.uniroma1.it

Closing date for applications: 31 May 2018

The Department of Computer Science and the profile area CYSEC-Cybersecurity at TU Darmstadt seek a Lead for an independent junior research group in the field of cybersecurity and privacy research, to be the recipient of a

Claude Shannon Fellowship

The Claude Shannon Fellowship is part of the Department of Computer Science at TU Darmstadt and simultaneously anchored in the cybersecurity profile area (CYSEC) of TU Darmstadt. The position is initially limited to three years with a possible maximum of six years.

Fellows are given the opportunity to teach and to conduct independent research, and receive additional resources to establish a research group with 1-2 PhD students. The Claude-Shannon Fellowship program is based upon the DFG\'s Emmy Noether program and provides competitive personal compensation and access to resources comparable to those at the W1/W2 assistant professorship level. TU Darmstadt offers excellent working conditions in a vibrant scientific community, embedded in the outstanding living and research environment of the Rhine-Main metropolitan region.

For more information about the application procedure please consult the link below.

The Technische Universität Darmstadt intends to increase the number of female employees and encourages female candidates to apply. In case of equal qualifications applicants with a degree of disability of at least 50 or equal will be given preference. Wages and salaries are according to the collective agreements on salary scales, which apply to the Technische Universität Darmstadt (TV-TU Darmstadt). Part-time employment is generally possible.

Contact

Please send your application in a single pdf file to: Melanie Schöyen, Management Assistant CYSEC, E-mail: personal (at) cysec.de

Code. No. 184

Application deadline: May 20, 2018

Closing date for applications: 20 May 2018

Contact: Melanie Schöyen, Management Assistant CYSEC, E-mail: personal (at) cysec.de

More information: https://www.tu-darmstadt.de/karriere_planen/allgemeineausschreibung/stellen_details_267904.en.jsp

Event date: 31 October to 31 July 2019
Submission deadline: 31 October 2018
Notification: 31 January 2019

In this paper, we study the problem of implementing the AEAD scheme, AEGIS-128, which is a finalist in the recently concluded competition, CAESAR. In order to achieve lightweight (least area) implementation, we first look into one round of AES encryption, which is a building block in this cipher. In this regard, we make use of the state-of-the-art implementation of AES in ASIC. We benchmark one round AES encryption (which is done for the first time) and later use it with AEGIS-128 to improve the optimized implementation reported (Inscrypt'14). Synthesis results show that our design requires 9.6\% less area and reduces the power consumption by 95.3\% (operating frequency is also reduced). Further, this concept can readily be applied to a variety of other ciphers.

In this paper, we revisit the ZigZag strategy of Granger, Kleinjung and Zumbrägel. In particular, we provide a new algorithm and proof for the so-called degree 2 elimination step. This allows us to provide a stronger theorem concerning discrete logarithm computations in small characteristic fields $\mathbb{F}_{q^{k_0k}}$ with $k$ close to $q$ and $k_0$ a small integer. As in the aforementioned paper, we rely on the existence of two polynomials $h_0$ and $h_1$ of degree $2$ providing a convenient representation of the finite field $\mathbb{F}_{q^{k_0k}}$.

A fundamental and widely-applied paradigm due to Franklin and Yung (STOC 1992) on Shamir-secret-sharing based general $n$-player MPC shows how one may trade the adversary threshold $t$ against amortized communication complexity, by using a so-called packed version of Shamir's scheme. For e.g. the BGW-protocol (with active security), this trade-off means that if $t + 2k -2 < n/3$, then $k$ parallel evaluations of the same arithmetic circuit on different inputs can be performed at the overall cost corresponding to a single BGW-execution.

In this paper we propose a novel paradigm for amortized MPC that offers a different trade-off, namely with the size of the field of the circuit which is securely computed, instead of the adversary threshold. Thus, unlike the Franklin-Yung paradigm, this leaves the adversary threshold unchanged. Therefore, for instance, this paradigm may yield constructions enjoying the maximal adversary threshold $\lfloor (n-1)/3 \rfloor$ in the BGW-model (secure channels, perfect security, active adversary, synchronous communication).

Our idea is to compile an MPC for a circuit over an extension field to a parallel MPC of the same circuit but with inputs defined over its base field and with the same adversary threshold. Key technical handles are our notion of reverse multiplication-friendly embeddings (RMFE) and our proof, by algebraic-geometric means, that these are constant-rate, as well as efficient auxiliary protocols for creating ``subspace-randomness'' with good amortized complexity. In the BGW-model, we show that the latter can be constructed by combining our tensored-up linear secret sharing with protocols based on hyperinvertible matrices a la Beerliova-Hirt (or variations thereof).

As a demonstration of the merits of the novel paradigm, we show that, in the BGW-model and with an optimal adversary threshold $\lfloor (n-1)/3 \rfloor$, it is possible to securely compute a binary circuit with amortized complexity $O(n)$ of bits per gate per instance. Known results would give $n \log n$ bits instead. By combining our result with the Franklin-Yung paradigm, and assuming a sub-optimal adversary (i.e., an arbitrarily small $\epsilon>0$ fraction below 1/3), this is improved to $O(1)$ bits instead of $O(n)$.

We present various differential fault attack schemes for the RECTANGLE-80 and demonstrate how initially we started from a 80-bit fault to a single word fault scheme. This was mainly due to a differential vulnerability in the S-box of RECTANGLE as a result of which the exhaustive search space for the key reduces from $2^{80}$ to $2^{32}$. We have also presented a key schedule attack that is a variant of the single fault scheme, exploiting the same vulnerability and reduces the search space to $2^{40}$. The paper concludes with the simulation results for the single word fault scheme followed by countermeasures.

During the secure boot process for a trusted execution environment, the processor must provide a chain of certificates to the remote client demonstrating that their secure container was established as specified. This certificate chain is rooted at the hardware manufacturer who is responsible for constructing chips according to the correct specification and provisioning them with key material. We consider a semi-honest manufacturer who is assumed to construct chips correctly, but may attempt to obtain knowledge of client private keys during the process.

Using the RISC-V Rocket chip architecture as a base, we design, document, and implement an attested execution processor that does not require secure non-volatile memory, nor a private key explicitly assigned by the manufacturer. Instead, the processor derives its cryptographic identity from manufacturing variation measured by a Physical Unclonable Function (PUF). Software executed by a bootloader built into the processor transforms the PUF output into an elliptic curve key pair. The (re)generated private key is used to sign trusted portions of the boot image, and is immediately destroyed. The platform can therefore provide attestations about its state to remote clients. Reliability and security of PUF keys are ensured through the use of a trapdoor computational fuzzy extractor.

We present detailed evaluation results for secure boot and attestation by a client of a Rocket chip implementation on a Xilinx Zynq 7000 FPGA.

Abstract. A proxy re-encryption (PRE) scheme is a public-key encryption scheme that allows the holder of a key pk to derive a re-encryption key for any other key pk&#8242;. This re-encryption key lets anyone transform ciphertexts under pk into ciphertexts under pk&#8242; without knowing the underlying message, while transformations from pk&#8242; to pk should not be possible (unidirectional). Security is defined in a multi-user setting against an adversary that gets the users’ public keys and can ask for re-encryption keys and can corrupt users by requesting their secret keys. Any ciphertext that the adversary cannot trivially decrypt given the obtained secret and re-encryption keys should be secure.

All existing security proofs for PRE only show selective security, where the adversary must first declare the users it wants to corrupt. This can be lifted to more meaningful adaptive security by guessing the set of corrupted users among the n users, which loses a factor exponential in n, rendering the result meaningless already for moderate n.

Jafargholi et al. (CRYPTO’17) proposed a framework that in some cases allows to give adaptive security proofs for schemes which were previously only known to be selectively secure, while avoiding the exponential loss that results from guessing the adaptive choices made by an adversary. We apply their framework to PREs that satisfy some natural additional properties. Concretely, we give a more fine-grained reduction for several unidirectional PREs, proving adaptive security at a much smaller loss. The loss depends on the graph of users whose edges represent the re- encryption keys queried by the adversary. For trees and chains the loss is quasi-polynomial in the size and for general graphs it is exponential in their depth and indegree (instead of their size as for previous reductions). Fortunately, trees and low-depth graphs cover many, if not most, interesting applications.

Our results apply e.g. to the bilinear-map based PRE schemes by Ate- niese et al. (NDSS’05 and CT-RSA’09), Gentry’s FHE-based scheme (STOC’09) and the LWE-based scheme by Chandran et al. (PKC’14).

We repurpose existing RSA/ECC co-processors for (ideal) lattice-based cryptography by exploiting the availability of fast long integer multiplication. Such co-processors are deployed in smart cards in passports and identity cards, secured microcontrollers and hardware security modules (HSM). In particular, we demonstrate an implementation of a variant of the Module-LWE-based Kyber Key Encapsulation Mechanism (KEM) that is tailored for optimal performance on a commercially available smart card chip (SLE 78). To benefit from the RSA/ECC co-processor we use Kronecker substitution in combination with schoolbook and Karatsuba polynomial multiplication. Moreover, we speed-up symmetric operations in our Kyber variant using the AES co-processor to implement a PRNG and a SHA-256 co-processor to realise hash functions. This allows us to execute CCA-secure Kyber768 key generation in 79.6 ms, encapsulation in 102.4 ms and decapsulation in 132.7 ms.

Deniable messaging protocols allow two parties to have `off-the-record' conversations without leaving any record that can convince external verifiers about what either of them said during the conversation. Recent events like WikiLeaks email dumps underscore the importance of deniable messaging to whistleblowers, politicians, dissidents and many others. Consequently, messaging protocols like Signal and OTR are expressly designed to provide deniability.

Many commodity devices today support hardware-assisted remote attestation which can be used to convince a remote verifier of some property locally observed on the device.

We show how an adversary can use remote attestation to undetectably break deniability in any deniable protocol (including messaging protocols) that provide an authenticated channel. We prove that our attack allows an adversary to convince skeptical verifiers and describe a concrete implementation of the attack against the Signal messaging protocol. We then show how attestation itself can be used to restore deniability by thwarting a realistic class of adversaries from mounting such attacks.

Hardware-based attestation changes the adversary model for deniable protocols, and its availability has now made it entirely practical for well-resourced attackers to break deniability, completely unbeknownst to the victim.

An Oblivious RAM (ORAM) introduced by Goldreich and Ostrovsky [JACM'96] is a (possibly randomized) RAM, for which the memory access pattern reveals no information about the operations performed. The main performance metric of an ORAM is the bandwidth overhead, i.e., the multiplicative factor extra memory blocks that must be accessed to hide the operation sequence. In their seminal paper introducing the ORAM, Goldreich and Ostrovsky proved an amortized $\Omega(\lg n)$ bandwidth overhead lower bound for ORAMs with memory size $n$. Their lower bound is very strong in the sense that it applies to the ``offline'' setting in which the ORAM knows the entire sequence of operations ahead of time.

However, as pointed out by Boyle and Naor [ITCS'16] in the paper ``Is there an oblivious RAM lower bound?'', there are two caveats with the lower bound of Goldreich and Ostrovsky: (1) it only applies to ``balls in bins'' algorithms, i.e., algorithms where the ORAM may only shuffle blocks around and not apply any sophisticated encoding of the data, and (2), it only applies to statistically secure constructions. Boyle and Naor showed that removing the ``balls in bins'' assumption would result in super linear lower bounds for sorting circuits, a long standing open problem in circuit complexity. As a way to circumventing this barrier, they also proposed a notion of an ``online'' ORAM, which is an ORAM that remains secure even if the operations arrive in an online manner. They argued that most known ORAM constructions work in the online setting as well.

Our contribution is an $\Omega(\lg n)$ lower bound on the bandwidth overhead of any online ORAM, even if we require only computational security and allow arbitrary representations of data, thus greatly strengthening the lower bound of Goldreich and Ostrovsky in the online setting. Our lower bound applies to ORAMs with memory size $n$ and any word size $r \geq 1$. The bound therefore asymptotically matches the known upper bounds when $r = \Omega(\lg^2 n)$.

Message-locked encryption (MLE) (formalized by Bellare, Keelveedhi and Ristenpart, 2013) is an important cryptographic primitive that supports deduplication in the cloud. Updatable block-level message-locked encryption (UMLE) (formalized by Zhao and Chow, 2017) adds the update functionality to the MLE. In this paper, we formalize and extensively study a new cryptographic primitive file-updatable message-locked encryption (FMLE). FMLE can be viewed as a generalization of the UMLE, in the sense that unlike the latter, the former does not require the existence of BL-MLE (block-level message-locked encryption). FMLE allows more flexibility and efficient methods for updating the ciphertext and tag. Our second contribution is the design of two efficient FMLE constructions, namely, RevD-1 and RevD-2, whose design principles are inspired from the very unique reverse decryption functionality of the FP hash function (designed by Paul, Homsirikamol and Gaj, 2012) and the APE authenticated encryption (designed by Andreeva et al., 2014). With respect to UMLE – which provides so far the most efficient update function – RevD-1 and RevD-2 reduce the total update time by at least 50%, on average. Additionally, our constructions are storage efficient. We also give extensive comparison between our and the existing constructions.

This work describes a fast fully homomorphic encryption scheme over the torus (TFHE), that revisits, generalizes and improves the fully homomorphic encryption (FHE) based on GSW and its ring variants. The simplest FHE schemes consist in bootstrapped binary gates. In this gate bootstrapping mode, we show that the scheme FHEW of [24] can be expressed only in terms of external product between a GSW and a LWE ciphertext. As a consequence of this result and of other optimizations, we decrease the running time of their bootstrapping from 690ms to 13ms single core, using 16MB bootstrapping key instead of 1GB, and preserving the security parameter. In leveled homomorphic mode, we propose two methods to manipulate packed data, in order to decrease the ciphertext expansion and to optimize the evaluation of look-up tables and arbitrary functions in RingGSW based homomorphic schemes. We also extend the automata logic, introduced in [26], to the efficient leveled evaluation of weighted automata, and present a new homomorphic counter called TBSR, that supports all the elementary operations that occur in a multiplication. These improvements speed-up the evaluation of most arithmetic functions in a packed leveled mode, with a noise overhead that remains additive. We finally present a new circuit bootstrapping that converts LWE ciphertexts into low-noise RingGSW ciphertexts in just 137ms, which makes the leveled mode of TFHE composable, and which is fast enough to speed-up arithmetic functions, compared to the gate bootstrapping approach. Finally, we provide an alternative practical analysis of LWE based schemes, which directly relates the security parameter to the error rate of LWE and the entropy of the LWE secret key, and we propose concrete parameter sets and timing comparison for all our constructions.

Revocable identity-based encryption (RIBE) is an extension of IBE that supports a key revocation mechanism; an indispensable feature for practical cryptographic schemes. Due to this extra feature, RIBE is often required to satisfy a strong security notion unique to the revocation setting called decryption key exposure resistance (DKER). Additionally, hierarchal IBE (HIBE) is another orthogonal extension of IBE that supports key delegation functionalities allowing for scalable deployments of cryptographic schemes. Thus far, R(H)IBE constructions with DKER are only known from bilinear maps, where all constructions rely heavily on the so-called key re-randomization property to achieve the DKER and/or hierarchal feature. Since lattice-based schemes seem to be inherently ill-fit with the key re-randomization property, we currently do not know of any lattice-based R(H)IBE schemes with DKER.

In this paper, we propose the first lattice-based RHIBE scheme with DKER without relying on the key re-randomization property, departing from all the previously known methods. We start our work by providing a generic construction of RIBE schemes with DKER, which uses as building blocks any two-level standard HIBE scheme and (weak) RIBE scheme without DKER. Based on previous lattice-based RIBE constructions, our result implies the first lattice-based RIBE scheme with DKER. Then, building on top of our generic construction, we construct the first lattice-based RHIBE scheme with DKER, by further exploiting the algebraic structure of lattices. To this end, we prepare a new tool called the level conversion keys, which allows us to achieve the hierarchal feature without relying on the key re-randomization property.

We continue the study of Homomorphic Secret Sharing (HSS), recently introduced by Boyle et al. (Crypto 2016, Eurocrypt 2017). A (2-party) HSS scheme splits an input x into shares (x0, x1) such that (1) each share computationally hides x, and (2) there exists an efficient homomorphic evaluation algorithm Eval such that for any function (or “program”) P from a given class it holds that Eval(x0,P)+Eval(x1,P) = P(x). Boyle et al. show how to construct an HSS scheme for branching programs, with an inverse polynomial error, using discrete-log type assumptions such as DDH.

We make two types of contributions.

Optimizations. We introduce new optimizations that speed up the previous optimized implementation of Boyle et al. by more than a factor of 30, significantly reduce the share size, and reduce the rate of leakage induced by selective failure.

Applications. Our optimizations are motivated by the observation that there are natural application scenarios in which HSS is useful even when applied to simple computations on short inputs. We demonstrate the practical feasibility of our HSS implementation in the context of such applications.

Software side channel attacks have become a serious concern with the recent rash of attacks on speculative processor architectures. Most attacks that have been demonstrated exploit the cache tag state as their exfiltration channel. While many existing defense mechanisms that can be implemented solely in software have been proposed, these mechanisms appear to patch specific attacks, and can be circumvented. In this paper, we propose minimal modifications to hardware to defend against a broad class of attacks, including those based on speculation, with the goal of eliminating the entire attack surface associated with the cache state covert channel.

We propose DAWG, Dynamically Allocated Way Guard, a generic mechanism for secure way partitioning of set associative structures including memory caches. DAWG endows a set associative structure with a notion of protection domains to provide strong isolation. When applied to a cache, unlike existing quality of service mechanisms such as Intel's Cache Allocation Technology (CAT), DAWG isolates hits and metadata updates across protection domains. We describe how DAWG can be implemented on a processor with minimal modifications to modern operating systems. We argue a non-interference property that is orthogonal to speculative execution and therefore argue that existing attacks such as Spectre Variant 1 and 2 will not work on a system equipped with DAWG. Finally, we evaluate the performance impact of DAWG on the cache subsystem.