International Association
for Cryptologic Research

A distance bounding (DB) protocol is a two-party authentication protocol between a prover and a verifier which is based on the distance between the prover and the verifier. It aims to defeat threats by malicious provers who try to convince that they are closer to the verifier or adversaries which seek to impersonate a far-away prover. All these threats are covered in several security definitions and it is not possible to have a single definition covering all. In this paper, we describe a new DB model with three parties where the new party is named hardware. In this model, called secure hardware model (SHM), the hardware is held by the prover without being able to tamper with. We define an all-in-one security model which covers all the threats of DB and an appropriate privacy notion for SHM. In the end, we construct the most efficient (in terms of computation by the prover-hardware and number of rounds) and secure DB protocols achieving the optimal security bounds as well as privacy.

Masking is a common countermeasure to secure implementations against side-channel attacks. In 2003, Ishai, Sahai, and Wagner introduced a formal security model, named t-probing model, which is now widely used to theoretically reason on the security of masked implementations. While many works have provided security proofs for small masked components, called gadgets, within this model, no formal method allowed to securely compose gadgets with a tight number of shares (namely, t+1) until recently. In 2016, Barthe et al. filled this gap with maskComp, a tool checking the security of masking schemes composed of several gadgets. This tool can achieve provable security with tight number of shares by inserting mask-refreshing gadgets at carefully selected locations. However the method is not tight in the sense that there exists some compositions of gadgets for which it cannot exhibit a flaw nor prove the security. As a result, it is overconservative and might insert more refresh gadgets than actually needed to ensure t-probing security. In this paper, we exhibit the first method able to clearly state whether a shared circuit composed of standard gadgets (addition, multiplication and refresh) is t-probing secure or not. Given such a composition, our method either produces a probing-security proof (valid at any order) or exhibits a security flaw that directly imply a probing attack at a given order. Compared to maskComp, our method can drastically reduce the number of required refresh gadgets to get a probing security proof, and thus the randomness requirement for some secure shared circuits. We apply our method to a recent AES implementation secured with higher-order masking in bitslice and we show that we can save all the refresh gadgets involved in the s-box layer, which results in an significant performance gain.

We revisit the security analysis of bitslice masking which is currently the most efficient way to protect block ciphers against higher-order side-channel analysis. First, we put forward that the existing definition of Strong Non-Interference (SNI) used to reason about composability in masked implementations requires minor adaptations to capture the multiple-input multiple-output functions that bitslice implementations contain. We argue that the latter adaptations are instrumental in the analysis of a compositional strategy used in the masked AES implementations of Goudarzi and Rivain from EUROCRYPT 2017, where all multiplications are SNI with one input "refreshed" in a SNI manner. Second, we show that this strategy can be improved thanks to integer programming and report on an optimized masked AES S-box with significantly less SNI gadgets than previously required. Eventually we propose a new definition of Probe-Isolating Non-Interference (PINI) which captures a weaker yet sufficient requirement for composability in masked implementations. The latter definition allows major simplifications of the probing security analyzes of complex circuits. We show that it leads to improved performances for masked AES implementations (of order up to 20) by proposing and proving a first PINI multiplication.

We consider natural ways to extend the notion of Zero-Knowledge (ZK) Proofs beyond decision problems. Specifically, we consider search problems, and define zero-knowledge proofs in this context as interactive protocols in which the prover can establish the correctness of a solution to a given instance without the verifier learning anything beyond the intended solution, even if it deviates from the protocol.

The goal of this work is to initiate a study of Search Zero-Knowledge (search-ZK), the class of search problems for which such systems exist. This class trivially contains search problems where the validity of a solution can be efficiently verified (using a single message proof containing only the solution). A slightly less obvious, but still straightforward, way to obtain zero-knowledge proofs for search problems is to let the prover send a solution and prove in zero-knowledge that the instance-solution pair is valid. However, there may be other ways to obtain such zero-knowledge proofs, and they may be more advantageous.

In fact, we prove that there are search problems for which the aforementioned approach fails, but still search zero-knowledge protocols exist. On the other hand, we show sufficient conditions for search problems under which some form of zero-knowledge can be obtained using the straightforward way.

Fault-tolerant distributed consensus is a fundamental problem in secure distributed computing. In this work, we consider the problem of distributed consensus in directed graphs tolerating crash failures. Tseng and Vaidya (PODC'15) presented necessary and sufficient condition for the existence of consensus protocols in directed graphs. We improve the round and communication complexity of their protocol. Moreover, we prove that our protocol requires the optimal number of communication rounds, required by any protocol belonging to a restricted class of crash-tolerant consensus protocols in directed graphs.

A treasury system is a community controlled and decentralized collaborative decision-making mechanism for sustainable funding of the blockchain development and maintenance. During each treasury period, project proposals are submitted, discussed, and voted for; top-ranked projects are funded from the treasury. The Dash governance system is a real-world example of such kind of systems. In this work, we, for the first time, provide a rigorous study of the treasury system. We modeled, designed, and implemented a provably secure treasury system that is compatible with most existing blockchain infrastructures, such as Bitcoin, Ethereum, etc. More specifically, the proposed treasury system supports liquid democracy/delegative voting for better collaborative intelligence. Namely, the stake holders can either vote directly on the proposed projects or delegate their votes to experts. Its core component is a distributed universally composable secure end-to-end verifiable voting protocol. The integrity of the treasury voting decisions is guaranteed even when all the voting committee members are corrupted. To further improve efficiency, we proposed the world’s first honest verifier zero-knowledge proof for unit vector encryption with logarithmic size communication. This partial result may be of independent interest to other cryptographic protocols. A pilot system is implemented in Scala over the Scorex 2.0 framework, and its benchmark results indicate that the proposed system can support tens of thousands of treasury participants with high efficiency.

The Cascaded LRW2 tweakable block cipher was introduced by Landecker et al. at CRYPTO 2012, and proven secure up to $2^{2n/3}$ queries. There has not been any attack on the construction faster than the generic attack in $2^n$ queries. In this work we initiate the quest towards a tight bound. We first present a distinguishing attack in $2n^{1/2}2^{3n/4}$ queries against a generalized version of the scheme. The attack is supported with an experimental verification and a formal success probability analysis. We subsequently discuss non-trivial bottlenecks in proving tight security, most importantly the distinguisher's freedom in choosing the tweak values. Finally, we prove that if every tweak value occurs at most $2^{n/4}$ times, Cascaded LRW2 is secure up to $2^{3n/4}$ queries.

With the advancement of Cloud computing, people now store their data on remote Cloud servers for larger compu- tation and storage resources. However, users’ data may contain sensitive information of users and should not be disclosed to the Cloud servers. If users encrypt their data and store the encrypted data in the servers, the search capability supported by the servers will be significantly reduced because the server has no access to the data content. In this paper, we propose a Fine-grained Multi-keyword Ranked Search (FMRS) scheme over encrypted Cloud data. Specifically, we leverage novel techniques to real- ize multi-keyword ranked search, which supports both mixed “AND”, “OR” and “NO” operations of keywords and ranking according to the preference factor and relevance score. Security analysis indicates that the FMRS scheme can achieve the data confidentiality, the privacy protection of index and trapdoor, and the unlinkability of trapdoor. Extensive experiments using the real-world dataset demonstrate that the FMRS achieves better performance than the existing schemes in terms of functionality and efficiency.

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).