International Association
for Cryptologic Research

More than ten years ago, a devastating data substitution attack was shown to successfully compromise all previously proposed remote attestation techniques. In fact, the authors went further than simply attacking previously proposed methods: they called into question whether it is theoretically possible for remote attestation methods to exist in face of their attack. Subsequently, it has been shown that it is possible, by relying on self-modifying code. We show that it is possible to create remote attestation that is secure against all data substitution attacks, without relying on self-modifying code. Our proposed method relies on a construction of the checksum process that forces frequent L2 cache overflows if any data substitution attack takes place.

Selective opening security (SO security) is desirable for public key encryption (PKE) in a multi-user setting. {In a selective opening attack, an adversary receives a number of ciphertexts for possibly correlated messages, then it opens a subset of them and gets the corresponding messages together with the randomnesses used in the encryptions. SO security aims at providing security for the unopened ciphertexts.} Among the existing simulation-based, selective opening, chosen ciphertext secure (SIM-SO-CCA secure) PKEs, only one (Libert et al. Crypto'17) enjoys tight security, which is reduced to the Non-Uniform LWE assumption. However, their public key and ciphertext are not compact.

In this work, we focus on constructing PKE with tight SIM-SO-CCA security based on standard assumptions. We characterize securities needed for key encapsulation mechanism (KEM) and show how to transform these securities into SIM-SO-CCA security of PKE through a tight security reduction, while the construction of PKE from KEM follows the general framework proposed by Liu and Paterson (PKC'15). We present two KEM constructions with tight securities based on the Matrix Decision Diffie-Hellman assumption. These KEMs in turn lead to two tightly SIM-SO-CCA secure PKE schemes. One of them enjoys not only tight security but also compact public key.

We consider reputation systems in the Universal Composability Framework where users can anonymously rate each others products that they purchased previously. To obtain trustworthy, reliable, and honest ratings, users are allowed to rate products only once. Everybody is able to detect users that rate products multiple times. In this paper we present an ideal functionality for such reputation systems and give an efficient realization that is usable in practical applications.

Authentication and integrity are fundamental security services that are critical for any viable system. However, some of the emerging systems (e.g., smart grids, aerial drones) are delay-sensitive, and therefore their safe and reliable operation requires delay-aware authentication mechanisms. Unfortunately, the current state-of-the-art authentication mechanisms either incur heavy computations or lack scalability for such large and distributed systems. Hence, there is a crucial need for digital signature schemes that can satisfy the requirements of delay-aware applications.

In this paper, we propose a new digital signature scheme that we refer to as Compact Energy and Delay-aware Authentication (CEDA). In CEDA, signature generation and verification only require a small-constant number of multiplications and Pseudo Random Function (PRF) calls. Therefore, it achieves the lowest end-to-end delay among its counterparts. Our implementation results on an ARM processor and commodity hardware show that CEDA has the most efficient signature generation on both platforms, while offering a fast signature verification. Among its delay-aware counterparts, CEDA has smaller private key with a constant-size signature. All these advantages are achieved with the cost of a larger public key. This is a highly favorable trade-off for applications wherein the verifier is not memory-limited. We open-sourced our implementation of CEDA to enable its broad testing and adaptation.

In the setting of secure multiparty computation, a set of $n$ parties with private inputs wish to jointly compute some functionality of their inputs. One of the most fundamental results of secure computation was presented by Ben-Or, Goldwasser and Wigderson (BGW) in 1988. They demonstrated that any $n$-party functionality can be computed with \emph{perfect security}, in the private channels model. When the adversary is semi-honest this holds as long as $t<n/2$ parties are corrupted, and when the adversary is malicious this holds as long as $t<n/3$ parties are corrupted. Unfortunately, a full proof of these results was never published. In this paper, we remedy this situation and provide a full proof of security of the BGW protocol. This includes a full description of the protocol for the malicious setting, including the construction of a new subprotocol for the perfect multiplication protocol that seems necessary for the case of $n/4\leq t<n/3$.

We provide the first verifiable shuffle specifically for fully homomorphic schemes. A verifiable shuffle is a way to ensure that if a node receives and sends encrypted lists, the content will be the same, even though no adversary can trace individual list items through the node. Shuffles are useful in e-voting, traffic routing and other applications.

We build our shuffle on the ideas and techniques of Groth's 2010 shuffle, but make necessary modifications for a less ideal setting where the randomness and ciphertexts admit no group structure.

The protocol relies heavily on the properties of the so-called gadget matrices, so we have included a detailed introduction to these.

Zero-knowledge proofs of knowledge and fully-homomorphic encryption are two areas that have seen considerable advances in recent years, and these two techniques are used in conjunction in the context of verifiable decryption. Existing solutions for verifiable decryption are aimed at the batch setting, however there are many applications in which there will only be one ciphertext that requires a proof of decryption. The purpose of this paper is to provide a zero-knowledge proof of correct decryption on an FHE ciphertext, which for instance could hold the result of a cryptographic election.

We give two main contributions. Firstly, we present a bootstrapping-like protocol to switch from one FHE scheme to another. The first scheme has efficient homomorphic capabilities; the second admits a simple zero-knowledge protocol. To illustrate this, we use the Brakerski et al. (ITCS, 2012) scheme for the former, and Gentry's original scheme (STOC, 2009) for the latter. Secondly, we present a simple one-shot zero-knowledge protocol for verifiable decryption using Gentry's original FHE scheme.

Nowadays it is well known that randomness may fail due to bugs or deliberate randomness subversion. As a result, the security of traditional public-key encryption (PKE) cannot be guaranteed any more. Currently there are mainly three approaches dealing with the problem of randomness failures: deterministic PKE, hedged PKE, and nonce-based PKE. However, these three approaches only apply to different application scenarios respectively. Since the situations in practice are dynamic and very complex, it's almost impossible to predict the situation in which a scheme is deployed, and determine which approach should be used beforehand. In this paper, we initiate the study of hedged security for nonce-based PKE, which adaptively applies to the situations whenever randomness fails, and achieves the best-possible security. Specifically, we lift the hedged security to the setting of nonce-based PKE, and formalize the notion of chosen-ciphertext security against chosen-distribution attacks (IND-CDA2) for nonce-based PKE. By presenting two counterexamples, we show a separation between our IND-CDA2 security for nonce-based PKE and the original NBP1/NBP2 security defined by Bellare and Tackmann (EUROCRYPT 2016). We show two nonce-based PKE constructions meeting IND-CDA2, NBP1 and NBP2 security simultaneously. The first one is a concrete construction in the random oracle model, and the second one is a generic construction based on a nonce-based PKE scheme and a deterministic PKE scheme.

Dear IACR members,

Happy New Year and best wishes to everyone for 2018! Here is an update on recent developments in the IACR.

To start out with some statistics, currently the IACR has 1500 members for 2018. All 2017 IACR conferences together counted almost 1900 attendees in total and published 359 papers. As you can read next, these numbers will grow in the future.

RWC 2018:

One important development for the IACR in 2017 was the establishment of the IACR Symposium on Real World Crypto (RWC), by joining forces with the former Real-World Crypto conference. According to the traditional schedule of RWC this event will now open IACR's calendar year. I am looking forward to seeing many of you at the first IACR-RWC, which takes place in Zurich on January 10-12. RWC 2018 has been completely booked out for weeks already, we expect 600 attendees. This is the largest number of registrations for an IACR event ever.

Elections:

The Board's composition changes for 2018, following the recent election: Josh Benaloh leaves and Tancrède Lepoint joins.

Let me take this occasion to thank Josh for his outstanding and long-lasting service to the IACR, with roles as secretary, Crypto general chair, the Board's program-chair contact and more. I could trace it back to him serving as secretary starting 1999. He pushed hard to make IACR actually use the cryptographic protocols he was interested in, and he succeeded when IACR adopted Helios online voting for elections. As president I was always glad to count on his deep understanding of votes and elections.

In the regular schedule General Chairs Steve Myers and S.M. Yiu will leave, Marc Fischlin, Muthu V., and Mitsuru Matsui join in 2018. I would like to thank all General Chairs of the 2017 conferences and their teams for their tremendous work.

Minutes from meetings of the Board of Directors:

As always you can find information from IACR Board of Directors in the minutes of the meetings available online (https://iacr.org/docs/minutes/minutes.html). Please take a look to understand the current projects and challenges of IACR.

Policy on Conflicts of Interest:

The IACR Board of Directors has recently finalized a formal Policy on Conflicts of Interest. This was discussed already at Eurocrypt, Crypto and Asiacrypt. You can find the text online under https://iacr.org/docs/.

To cite from the document: In particular, the authors of each submission are asked during the submission process to identify all members of the Program Committee who have an automatic conflict of interest (COI) with the submission. A reviewer and an author have an automatic COI if one was the thesis advisor/supervisor to the other, or if they've shared an institutional affiliation within the last two years, or if they've published two or more joint authored works within the last three years, or if they are in the same family. Any further COIs of importance should be separately disclosed. It is the responsibility of all authors to ensure correct reporting of COI information. Submissions with incorrect or incomplete COI information may be rejected without consideration of their merits.

Best regards,
Christian Cachin
IACR President

Key-encapsulation mechanisms (KEMs) are a common stepping stone for constructing public-key encryption. Secure KEMs can be built from diverse assumptions, including ones related to integer factorization, discrete logarithms, error correcting codes, or lattices. In light of the recent NIST call for post-quantum secure PKE, the zoo of KEMs that are believed to be secure continues to grow. Yet, on the question of which is the most secure KEM opinions are divided. While using the best candidate might actually not seem necessary to survive everyday life situations, placing a wrong bet can actually be devastating, should the employed KEM eventually turn out to be vulnerable.

We introduce KEM combiners as a way to garner trust from different KEM constructions, rather than relying on a single one: We present efficient black-box constructions that, given any set of `ingredient' KEMs, yield a new KEM that is (CCA) secure as long as at least one of the ingredient KEMs is.

As building blocks our constructions use cryptographic hash functions and blockciphers. Some corresponding security proofs require idealized models for these primitives, others get along on standard assumptions.

We initiate the study of public-key encryption (PKE) schemes and key-encapsulation mechanisms (KEMs) that retain security even when public parameters (primes, curves) they use may be untrusted and subverted. We define a strong security goal that we call ciphertext pseudo-randomness under parameter subversion attack (CPR-PSA). We also define indistinguishability (of ciphertexts for PKE, and of encapsulated keys from random ones for KEMs) and public-key hiding (also called anonymity) under parameter subversion attack, and show they are implied by CPR-PSA, for both PKE and KEMs. We show that hybrid encryption continues to work in the parameter subversion setting to reduce the design of CPR-PSA PKE to CPR-PSA KEMs and an appropriate form of symmetric encryption. To obtain efficient, elliptic-curve-based KEMs achieving CPR-PSA, we introduce efficiently-embeddable group families and give several constructions from elliptic-curves.

Attribute-based signature (ABS), originally introduced by Maji et al. (CT-RSA'11), represents an essential mechanism to allow for fine-grained authentication. A user associated with an attribute $x$ can sign w.r.t. a given public policy $C$ only if his attribute satisfies $C$, i.e., $C(x)=1$. So far, much effort on constructing bilinear map-based ABS schemes have been made, where the state-of-the-art scheme of Sakai et al. (PKC'16) supports the very wide class of unbounded circuits as policies. However, construction of ABS schemes without bilinear maps are less investigated, where it was not until recently that Tsabary (TCC'17) showed a lattice-based ABS scheme supporting bounded circuits as policies, at the cost of weakening the security requirement. In this work, we affirmatively close the gap between ABS schemes based on bilinear maps and lattices by constructing the first lattice-based ABS scheme for unbounded circuits in the random oracle model. We start our work by providing a generic construction of ABS schemes for unbounded-circuits in the random oracle model, which in turn implies that one-way functions are sufficient to construct ABS schemes. To prove security, we formalize and prove a generalization of the Forking Lemma, which we call "general multi-forking lemma with oracle access"', capturing the situation where the simulator is interacting with some algorithms he cannot rewind, and also covering many features of the recent lattice-based ZKPs. This, in fact, was a formalization lacking in many existing anonymous signatures from lattices so far (e.g., group signatures). Therefore, this formalization is believed to be of independent interest. Finally, we provide a concrete instantiation of our generic ABS construction from lattices by introducing a new $\Sigma$-protocol, that highly departs from the previously known techniques, for proving possession of a valid signature of the lattice-based signature scheme of Boyen (PKC'10).

In STOC 2008, Peikert and Waters introduced a powerful primitive called lossy trapdoor functions (LTFs). In a nutshell, LTFs are functions that behave in one of two modes. In the normal mode, functions are injective and invertible with a trapdoor. In the lossy mode, functions statistically lose information about their inputs. Moreover, the two modes are computationally indistinguishable. In this work, we put forward a relaxation of LTFs, namely, regularly lossy functions (RLFs). Compared to LTFs, the functions in the normal mode are not required to be efficiently invertible or even unnecessary to be injective. Instead, they could also be lossy, but in a regular manner. We also put forward richer abstractions of RLFs, namely all-but-one regularly lossy functions (ABO-RLFs) and one-time regularly lossy filters (OT-RLFs).

We show that (ABO)-RLFs admit efficient constructions from both a variety of number-theoretic assumptions and hash proof system (HPS) for subset membership problems satisfying natural algebraic properties. Thanks to the relaxations on functionality, the constructions enjoy much compact key size and better computational efficiency than that of (ABO)-LTFs.

We demonstrate the utility of RLFs and their extensions in the leakage-resilient cryptography. As a special case of RLFs, lossy functions imply leakage-resilient injective one-way functions with optimal leakage rate $1-o(1)$. ABO-RLFs (or OT-RLFs) immediately imply leakage-resilient one-time message authentication code (MAC) with optimal leakage rate $1-o(1)$. ABO-RLFs together with HPS give rise to leakage-resilient chosen-ciphertext (CCA) secure key encapsulation mechanisms (KEM) (this approach extends naturally to the identity-based setting). Combining the construction of ABO-RLFs from HPS, this gives the first leakage-resilient CCA-secure public-key encryption (PKE) with optimal leakage rate based solely on HPS, and thus goes beyond the barrier posed by Dodis et al. (Asiacrypt 2010).

The University of Colorado Colorado Springs (UCCS) invites applications from nationally and internationally renowned individuals for the Gallogly Endowed Engineering Chair of Cybersecurity. The qualified candidate will have an outstanding record of research/development accomplishments, as well as a record of practical application/work. The occupant of the Gallogly Endowed Chair will assume a leadership role in research activities in the EAS Computer Science Department and in the National Cybersecurity Center. He/she is expected to maintain a vigorous, creative, externally funded research program that compliments that of current faculty and builds on departmental strengths. External funding should be sufficient to support graduate students, postdoctoral researchers, etc. as needed to support the research effort. Teaching will be in support of the School Ph.D in Security degree, the Master of Information Assurance, and the rapidly growing Bachelor of Innovation in Computer Security degree programs. It would most likely include teaching one undergraduate course and one graduate level course per year. Teaching would also include mentoring of graduate and undergraduate students in the research environment.

The overall workload is 50% academic in the Computer Science Department, conducting teaching, research & development and professional service in cybersecurity as faculty member. The remaining 50% of workload will be to develop research, teaching, and training opportunities in collaboration with National Cybersecurity Center (NCC). In particular, the candidate will help plan and design the infrastructure of the UCCS building housing NCC and to develop the programs for the center. This will include creating partnerships with institutions across the nation and advancing the cybersecurity industry. It will include fostering opportunities to partner closely with industry to drive student engagement and learning opportunities in cybersecurity. The position requires the ability to obtain a US security clearance to conduct classified research.

Closing date for applications: 1 March 2018

Contact: Posting Contact Name: Terry Boult

Posting Contact Email: tboult at uccs.edu

More information: https://cu.taleo.net/careersection/2/jobdetail.ftl?job=11128

We are looking for outstanding PhD candidates and Post doctoral researchers working on topics related to cryptography and IT Security.

Topics of particular interest include (but are not limited to):

- Secure cryptographic implementations

- Leakage/tamper resilient cryptography

- Distributed cryptography

- Blockchains and cryptocurrencies

The application must include a curriculum vitae, a short research statement, and names of 1 person (2 in case of PostDocs) that can provide reference about the applicant and her/his work. In case of PostDoc applications, the candidate shall be able to show solid expertise in cryptography/IT Security illustrated in form of publications at major crypto/security venues such as CRYPTO, EUROCRYPT, ASIACRYPT, TCC, PKC, CHES, FC, ACM CCS, IEEE S&P, USENIX Security, NDSS etc.

The positions are available immediately and salary is internationally competitive based on the TU Darmstadt’s wage agreement (TV-TUD) and includes social benefits. TU Darmstadt offers excellent working environment in the heart of the Rhein-Main area, and has a strong institute for research on IT security with more than 300 researchers working on all aspects of cybersecurity.

Review of applications starts immediately until the positions are filled.

Closing date for applications: 28 February 2018

Contact: Prof. Sebastian Faust, Contact: sebastian.faust(at)cs(dot)tu-darmstadt(dot)de

Very recently, Liu, Li, Kim and Nepal submitted Compact-LWE, a new public key encryption scheme, to NIST as a candidate of the standard of post-quantum cryptography. About the security of Compact-LWE, the authors claimed that "even if the hard problems in lattice, such as CVP and SIS, can be efficiently solved, the secret values or private key in Compact-LWE still cannot be efficiently recovered. This allows Compact-LWE to choose very small dimension parameters, such as n = 8 in our experiment". However, in this paper, we show it is not true by proposing a ciphertext-only attack against Compact-LWE. More precisely, if we can solve CVP, we can decrypt any ciphertext without knowing the private keys. Since the dimension of the underlying lattice is very small (128) for the authors' parameter choice, (approximation-)CVP can be efficiently solved with lattice basis reduction algorithm. Hence, we can always break Compact-LWE with the authors' parameter choice in our experiments, which means that Compact-LWE with the recommended parameters is not secure.

The Department of Computer Science at the University of Surrey is seeking to recruit a full-time researcher to the “FutureTPM” project funded by the European Union as part of the H2020 programme. The successful candidate will join the Secure Systems group (http://www.surrey.ac.uk/cs/research/) for up to three years, working on the development and integration of quantum-resistant cryptography into the Trusted Platform Module (TPM), the development of a formal security model for all TPM functionalities and the vulnerability analysis of the TCG Software Stack (TSS) for accessing all the functions of the TPM.

The post is available to start in February 2018, and runs to December 2020 (salary £30,688 to £36,613 per annum).

The goal of FutureTPM is to provide a new generation of TPM-based solutions, incorporating robust and physically secure Quantum-Resistant (QR) cryptographic primitives (formally verified), to ensure long-term security, privacy and operational assurance in the complex domain of future ICT systems and services.

The successful applicant will: (i) demonstrate experience and knowledge of applied cryptography and trusted computing technologies, (ii) exposure to theoretical cryptography (in particular to simulation-based and code-based security proofs), and interest in the application of formal methods to security and cryptography, (iii) and a solid foundation in risk assessment and vulnerability analysis for cyber-physical systems.

Closing date for applications: 5 February 2018

Contact: For informal enquiries please contact Professor Liqun Chen at liqun.chen (at) surrey.ac.uk or +44 (0)1483 6844615 or Dr Thanassis Giannetsos at a.giannetsos (at) surrey.ac.uk or +44 (0) 1483 683037

More information: https://jobs.surrey.ac.uk/vacancy.aspx?ref=001018

Motivated by the need to assess the concrete security of a device after a side channel attack, there has been a flurry of recent work designing both key rank and key enumeration algorithms. Two main competitors for key ranking can be found in the literature: a convolution based algorithm put forward by Glowacz et al. (FSE 2015), and a path counting based algorithm proposed by Martin et al. (Asiacrypt 2015). Both key ranking algorithms can be extended to key enumeration algorithms (Poussier et al. (CHES 2016) and Martin et al. (Asiacrypt 2015)). The two approaches were proposed independently, and have so far been treated as uniquely different techniques, with different levels of accuracy. However, we show that both approaches (for ranking) are mathematically equivalent for a suitable choice of their respective discretisation parameter. This settles questions about which one returns more accurate rankings. We then turn our attention to their related enumeration algorithms and determine why and how these algorithms differ in their practical performance.

We consider a setting where users store their encrypted documents on a remote server and can selectively share documents with each other. A user should be able to perform keyword searches over all the documents she has access to, including the ones that others shared with her. The contents of the documents, and the search queries, should remain private from the server.

This setting was considered by Popa et al. (NSDI '14) who developed a new cryptographic primitive called Multi-Key Searchable Encryption (MKSE), together with an instantiation and an implementation within a system called Mylar, to address this goal. Unfortunately, Grubbs et al. (CCS '16) showed that the proposed MKSE definition fails to provide basic security guarantees, and that the Mylar system is susceptible to simple attacks. Most notably, if a malicious Alice colludes with the server and shares a document with an honest Bob then the privacy of all of Bob's search queries is lost.

In this work we revisit the notion of MKSE and propose a new strengthened definition that rules out the above attacks. We then construct MKSE schemes meeting our definition. We first give a simple and efficient construction using only pseudorandom functions. This construction achieves our strong security definition at the cost of increasing the server storage overhead relative to Mylar, essentially replicating the document each time it is shared. We also show that high server storage overhead is not inherent, by giving an alternate (albeit impractical) construction that manages to avoid it using obfuscation.

We study game-based definitions of individual and universal verifiability by Smyth, Frink & Clarkson. We prove that building voting systems from El Gamal coupled with proofs of correct key generation suffices for individual verifiability. We also prove that it suffices for an aspect of universal verifiability. Thereby eliminating the expense of individual-verifiability proofs and simplifying universal-verifiability proofs for a class of encryption-based voting systems. We use the definitions of individual and universal verifiability to analyse the mixnet variant of Helios. Our analysis reveals that universal verifiability is not satisfied by implementations using the weak Fiat-Shamir transformation. Moreover, we prove that individual and universal verifiability are satisfied when statements are included in hashes (i.e., when using the Fiat-Shamir transformation, rather than the weak Fiat-Shamir transformation).