International Association
for Cryptologic Research

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.

A multisignature scheme allows a group of signers to collaboratively sign a message, creating a single signature that convinces a verifier that every individual signer approved the message. The increased interest in technologies to decentralize trust has triggered the proposal of two highly efficient Schnorr-based multisignature schemes designed to scale up to thousands of signers, namely CoSi by Syta et al. (S&P 2016) and MuSig by Maxwell et al. (ePrint 2018). The MuSig scheme was presented with a proof under the one-more discrete-logarithm assumption, while the provable security of CoSi has so far remained an open question. In this work, we prove that CoSi and MuSig cannot be proved secure without radically departing from currently known techniques (and point out a flaw in the proof of MuSig). We then present DG-CoSi, a double-generator variant of CoSi based on the Okamoto (multi)signature scheme, and prove it secure under the discrete-logarithm assumption in the random-oracle model. Our experiments show that the second generator in DG-CoSi barely affects scalability compared to CoSi, allowing 8192 signers to collaboratively sign a message in under 1.5 seconds, making it a highly practical and provably secure alternative for large-scale deployments.

Cryptocurrencies have popularized public ledgers, known colloquially as "blockchains". While the Bitcoin blockchain is relatively simple to reason about as, effectively, a hash chain, more complex public ledgers are largely designed without any formalization of desired cryptographic properties such as authentication or integrity. These designs are then implemented without assurances against real-world bugs leading to little assurance with regards to practical, real-world security.

Ledger Design Language (LDL) is a modeling language for describing public ledgers. The LDL compiler produces two outputs. The first output is a an applied-pi calculus symbolic model representing the public ledger as a protocol. Using ProVerif, the protocol can be played against an active attacker, whereupon we can query for block integrity, authenticity and other properties. The second output is a formally verified read/write API for interacting with the public ledger in the real world, written in the F* programming language. F* features such as dependent types allow us to validate a block on the public ledger, for example, by type-checking it so that its signing public key be a point on a curve. Using LDL's outputs, public ledger designers obtain automated assurances on the theoretical coherence and the real-world security of their designs with a single framework based on a single modeling language.

The term near or weak blocks describes Bitcoin blocks whose PoW does not meet the required target difficulty to be considered valid under the regular consensus rules of the protocol. Near blocks are generally associated with protocol improvement proposals striving towards shorter transaction confirmation times. Existing proposals assume miners will act rationally based solely on intrinsic incentives arising from the adoption of these changes, such as earlier detection of blockchain forks.

In this paper we present Flux, a protocol extension for proof-of-work blockchains that leverages on near blocks, a new block reward distribution mechanism, and an improved branch selection policy to incentivize honest participation of miners. Our protocol reduces mining variance, improves the responsiveness of the underlying blockchain in terms of transaction processing, and can be deployed without conflicting modifications to the underlying base protocol as a velvet fork. We perform an initial analysis of selfish mining which suggests Flux not only provides security guarantees similar to pure Nakamoto consensus, but potentially renders selfish mining strategies less profitable.

Aggregate signature allows non-interactively condensing multiple individual signatures into a compact one. Besides the faster verification, it is useful to reduce storage and bandwidth, and is especially attractive for blockchain and cryptocurrency. For example, aggregate signature can mitigate some bottlenecks emerged with the Bitcoin systems (and actually almost all blockchain-based systems): low throughput, capacity, scalability, high transaction fee, etc. Unfortunately, achieving aggregate signature from general elliptic curve group (without bilinear maps) is a long-standing open question. Recently, there is also renewed interest in deploying Schnorr's signature in Bitcoin, for its efficiency and flexibility. In this work, we investigate the applicability of the Gamma-signature scheme proposed by Yao and Zhao. Akin to Schnorr's, Gamma-signature is generated with linear combination of ephemeral secret-key and static secret-key, and enjoys almost all the advantages of Schnorr's signature. Besides, Gamma-signature has salient features in online/offline performance, stronger provable security, and deployment flexibility with interactive protocols like IKE. In this work, we identify one more key advantage of Gamma-signature in signature aggregation, which is particularly crucial for applications to blockchain and cryptocurrency. Specifically, we first observe the incapability of Schnorr's for aggregating signatures in the Bitcoin system. This is demonstrated by concrete attacks. Then, we show that aggregate signature can be derived from the Gamma-signature scheme. To the best of our knowledge, this is the first aggregate signature scheme from general groups without bilinear maps. The security of aggregate Gamma-signature is proved based on a new assumption proposed and justified in this work, referred to as non-malleable discrete-logarithm (NMDL), which might be of independent interest and could find more cryptographic applications in the future. When applying the resultant aggregate Gamma-signature to Bitcoin, the storage volume of signatures reduces about 50%, and the signature verification time can even reduce about 80%. Finally, we specify in detail the implementation of aggregate Gamma-signature in Bitcoin, with minimal modifications that are in turn more friendly to segregated witness (SegWit) and provide better protection against transaction malleability attacks.