International Association
for Cryptologic Research

We present a new approach to extending oblivious transfer with communication complexity that is logarithmic in the security parameter. Our method only makes black-box use of the underlying cryptographic primitives, and can achieve security against an active adversary with almost no overhead on top of passive security. This results in the first oblivious transfer protocol with sublinear communication and active security, which does not require any non-black-box use of cryptographic primitives.

Our main technique is a novel twist on the classic OT extension of Ishai et al. (Crypto 2003), using an additively key-homomorphic PRF to reduce interaction. We first use this to construct a protocol for a large batch of 1-out-of-$n$ OTs on random inputs, with amortized $o(1)$ communication. Converting these to 1-out-of-2 OTs on chosen strings requires logarithmic communication. The key-homomorphic PRF used in the protocol can be instantiated under the learning with errors assumption with exponential modulus-to-noise ratio.

In delegated computing, prominent in the context of cloud computing, guaranteeing both the correctness and authenticity of computations is of critical importance. Homomorphic signatures can be used as cryptographic solutions to this problem. In this paper we solve the open problem of constructing a linearly homomorphic signature scheme that is secure against an active adversary under standard assumptions. We provide a construction based on the DL and CDH assumption. Furthermore we show how our scheme can be combined with homomorphic encryption under the framework of Linearly Homomorphic Authenticated Encryption with Public Verifiability. This way we can provide the first such scheme that is context hiding. Furthermore our solution even allows verification in constant time (in an amortized sense).

Lattice-based group signature is an active research topic in recent years. Since the pioneering work by Gordon, Katz and Vaikuntanathan (Asiacrypt 2010), ten other schemes have been proposed, providing various improvements in terms of security, efficiency and functionality. However, in all known constructions, one has to fix the number $N$ of group users in the setup stage, and as a consequence, the signature sizes are dependent on $N$.

In this work, we introduce the first constant-size group signature from lattices, which means that the size of signatures produced by the scheme is independent of $N$ and only depends on the security parameter $\lambda$. More precisely, in our scheme, the sizes of signatures, public key and users' secret keys are all of order $\widetilde{\mathcal{O}}(\lambda)$. The scheme supports dynamic enrollment of users and is proven secure in the random oracle model under the Ring Short Integer Solution (RSIS) and Ring Learning With Errors (RLWE) assumptions. At the heart of our design is a zero-knowledge argument of knowledge of a valid message-signature pair for the Ducas-Micciancio signature scheme (Crypto 2014), that may be of independent interest.

We present a secure two-factor authentication (TFA) scheme based on the possession by the user of a password and a crypto-capable device. Security is ``end-to-end" in the sense that the attacker can attack all parts of the system, including all communication links and any subset of parties (servers, devices, client terminals), can learn users' passwords, and perform active and passive attacks, online and offline. In all cases the scheme provides the highest attainable security bounds given the set of compromised components.

Our solution builds a TFA scheme using any Device-Enhanced PAKE, defined by Jarecki et al., and any Short Authenticated String (SAS) Message Authentication, defined by Vaudenay. We show an efficient instantiation of this modular construction which utilizes any password-based client-server authentication method, with or without reliance on public-key infrastructure. The security of the proposed scheme is proven in a formal model that we formulate as an extension of the traditional PAKE model.

We also report on a prototype implementation of our schemes, including TLS-based and PKI-free variants, as well as several instantiations of the SAS mechanism, all demonstrating the practicality of our approach.

Abstract—We introduce a simple and practical Proof of Space (PoS) with applicability to ledger-based payment schemes. It has a dramatically simpler structure than previous proposals, and with that, becomes very easy to analyze. A proof can be as short as a few hundred bits, and can be publicly verified using only two hash function computations.

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