International Association
for Cryptologic Research

Vector commitments enable a user to commit to a sequence of values and provably reveal one or many values at specific positions at a later time. In this work, we construct Pointproofs--a new vector commitment scheme that supports non-interactive aggregation of proofs across multiple commitments. Our construction enables any third party to aggregate a collection of proofs with respect to different, independently computed commitments into a single proof represented by an elliptic curve point of 48-bytes. In addition, our scheme is hiding: a commitment and proofs for some values reveal no information about the remaining values.

We build Pointproofs and demonstrate how to apply them to blockchain smart contracts. In our example application, Pointproofs reduce bandwidth overheads for propagating a block of transactions by at least 60% compared to prior state-of-art vector commitments.

Pointproofs are also efficient: on a single-thread, it takes 0.08 seconds to generate a proof for 8 values with respect to one commitment, 0.25 seconds to aggregate 4000 such proofs across multiple commitments into one proof, and 23 seconds (0.7 ms per value proven) to verify the aggregated proof.

The Institute of Cybersecurity and Cryptology (iC2) at the University of Wollongong, Australia offers a full-time PhD position (3.5 years) in the area of applied cryptography. The PhD candidate will work on the ARC DP200100144 project titled “Securing Public Cloud Storage with Protection against Malicious Senders” under the supervision of Prof. Willy Susilo, A/Prof. Guomin Yang and Dr. Fuchun Guo.

We are looking for an enthusiastic and outstanding student with an Honours or Master degree in Computer Science or related area. Applicants with prior research experience in cryptography are more favourable. As women are underrepresented in this area, women are strongly encouraged to apply.

The PhD candidate will receive a full scholarship (stipend approx. AUD$27,094/annum + the tuition fee waiver valued at approx. AUD$ 30,000/annum).

Any interested applicant will need to send their full CV + record in prior study (Bachelor and Master transcripts) to A/Prof. Guomin Yang (gyang@uow.edu.au) by 1 June 2020, and highlighting their previous experience in cryptography research in the email. Please use the subject “PhD scholarship application to iC2” in the email sent. The successful candidate will be expected to start his/her study from August 2020 (depending on the approval of the required student visa).

Closing date for applications:

Contact: Guomin Yang

EUROCRYPT 2020 is the 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques and one of the three general conferences of the International Association for Cryptologic Research (IACR).

Due to the current novel coronavirus outbreak, EUROCRYPT 2020 has been converted into an all-digital event, which will be taking place online during 11-15 May 2020. The event will be viewable through Zoom Video Webinars or a live broadcast on YouTube, and will contain a mix of pre-recorded talks and live events with chat and Q&A.

Registrations for the original EUROCRYPT 2020 event have already been refunded and registrants should be seeing refunds in their credit card account in the coming days as their banks clear the transactions.

Registration for the virtual EUROCRYPT 2020 event will be open shortly. We will ask you to register for it although there will be no cost for EUROCRYPT 2020 virtual attendance itself. If you have not already paid your IACR membership fee (USD 50 for regular members or USD 25 for student members) by attending a previous IACR event in 2020, you will need to pay that fee as part of registering for EUROCRYPT 2020.

Further details about the all-digital event, including its scientific program and registration process, will be communicated soon via the IACR news system, the conference website, and other appropriate communication channels.

Decentralized Privacy-Preserving Proximity Tracing (DP-3T) is an open protocol which aims to help fight the current pandemic. Their proposal is an app for mobile phones which broadcasts frequently changing pseudorandom identifiers via (low energy) Bluetooth, and at the same time, the app stores IDs broadcast by phones in its proximity. Only if a user is tested positive, their IDs of the last 14 days are published so other users can check if they have stored them locally and thus were close to an infected person.

Vaudenay [eprint 2020/399] observes that this basic scheme succumbs to relay and even replay attacks, and proposes more complex \emph{interactive} schemes which prevent those attacks without giving up too many privacy aspects. Unfortunately interaction is problematic for this application for efficiency and security reasons.

In this note we suggest a very simple and efficient \emph{non-interactive} solution to prevent relay and replay attacks while preserving most of the privacy guarantees. In a nutshell, we let the users broadcast their IDs together with their current time (and if we want to prevent relay attacks, also location). The time and location are authenticated using a concept we term ``delayed authentication": We propose a message authentication code, where one can first check that the message matches the tag without knowing the key. The message and parts of the tag can then be deleted, and this delayed tag is independent of the message, but it's still possible to finish verification of the tag later when the key become known.

This means a receiving party can first check if the time and location match its own, but then delete those values, so this sensitive data is never locally stored. Should the sender be tested positive and his keys get released, the receiving party still can authenticate the delayed tag to detect a potential replay or relay attack.

Since its proposal in Asiacrypt 2018, the commutative isogeny-based key exchange protocol (CSIDH) has spurred considerable attention to improving its performance and re-evaluating its classical and quantum security guarantees. In this paper we discuss how the optimal strategies employed by the Supersingular Isogeny Diffie-Hellman (SIDH) key agreement protocol can be naturally extended to CSIDH. Furthermore, we report a software library that achieves moderate but noticeable performance speedups when compared against state-of-the-art implementations of CSIDH-512, which is the most popular CSIDH instantiation.

We introduce the Multi-Base Discrete Logarithm (MBDL) problem. We show that, unlike the basic Discrete Logarithm (DL) problem, MBDL allows a TIGHT (rewinding-avoiding) proof for the IMP-PA security of the Schnorr identification scheme, leading to a proof from MBDL for the Schnorr signature scheme that loses only a factor of the number of adversary hash queries, which is essentially optimal. We show that not only is the MBDL problem hard in the generic group model, but with a bound that matches that for DL, so that our new reductions for Schnorr allow implementations, for the same level of proven security, to use smaller groups, which increases efficiency. We then give an MBDL-based, non-rewinding proof for the BN multi-signature scheme (seeing renewed interest in crypto-currencies) that is tight up to the number of hash queries, improving on the prior DL-based proof, and leading again to improved efficiency by allowing the use of smaller groups.

Candidates of Indistinguishability Obfuscation (iO) can be categorized as ``direct'' or ``bootstrapping based''. Direct constructions rely on high degree multilinear maps [GGH13,GGHRSW13] and provide heuristic guarantees, while bootstrapping based constructions [LV16,Lin17,LT17,AJLMS19,Agr19,JLMS19] rely, in the best case, on bilinear maps as well as new variants of the Learning With Errors (LWE) assumption and pseudorandom generators. Recent times have seen exciting progress in the construction of indistinguishability obfuscation (iO) from bilinear maps (along with other assumptions) [LT17,AJLMS19,JLMS19,Agr19].

As a notable exception, a recent work by Agrawal [Agr19] provided a construction for iO without using any maps. This work identified a new primitive, called Noisy Linear Functional Encryption (NLinFE) that provably suffices for iO and gave a direct construction of NLinFE from new assumptions on lattices. While a preliminary cryptanalysis for the new assumptions was provided in the original work, the author admitted the necessity of performing significantly more cryptanalysis before faith could be placed in the security of the scheme. Moreover, the author did not suggest concrete parameters for the construction.

In this work, we fill this gap by undertaking the task of thorough cryptanalytic study of NLinFE. We design two attacks that let the adversary completely break the security of the scheme. To achieve this, we develop new cryptanalytic techniques which (we hope) will inform future designs of the primitive of NLinFE.

From the knowledge gained by our cryptanalytic study, we suggest modifications to the scheme. We provide a new scheme which overcomes the vulnerabilities identified before. We also provide a thorough analysis of all the security aspects of this scheme and argue why plausible attacks do not work. We additionally provide concrete parameters with which the scheme may be instantiated. We believe the security of NLinFE stands on significantly firmer footing as a result of this work.

Quantum money allows a bank to mint quantum money states that can later be verified and cannot be forged. Usually, this requires a quantum communication infrastructure to transfer quantum states between the user and the bank. This work combines the notion of classical verification -- introduced by Gavinsky (CCC 2012) -- with the notion of user-generated money -- introduced here -- to introduce Semi-Quantum Money, the first quantum money scheme to require only classical communication with the (entirely classical) bank. This work features constructions for both a public memory-dependent semi-quantum money scheme, based on the works of Zhandry and Coladangelo, and for a private memoryless semi-quantum money scheme, based on the notion of Noisy Trapdoor Claw Free Functions (NTCF) introduced by Brakerski et al. (FOCS 2018). In terms of technique, our main contribution is a strong parallel repetition theorem for NTCF.

The goal of white-box cryptography is to protect secret keys embedded in a cryptographic software deployed in an untrusted environment. In this article, we revisit state-of-the-art countermeasures employed in white-box cryptography, and we discuss possible ways to combine them. Then we analyze the different gray-box attack paths and study their performances in terms of required traces and computation time. Afterward, we propose a new paradigm for the gray-box attack against white-box cryptography, which exploits the data-dependency of the target implementation. We demonstrate that our approach provides substantial complexity improvements over the existing attacks. Finally, we showcase this new technique by breaking the three winning AES-128 white-box implementations from WhibOx 2019 white-box cryptography competition.

The GIFT family of lightweight block ciphers, published at CHES 2017, offers excellent hardware performance figures and has been used, in full or in part, in several candidates of the ongoing NIST lightweight cryptography competition. However, implementation of GIFT in software seems complex and not efficient due to the bit permutation composing its linear layer (a feature shared with PRESENT cipher). In this article, we exhibit a new non-trivial representation of the GIFT family of block ciphers over several rounds. This new representation, that we call fixslicing, allows extremely efficient software bitsliced implementations of GIFT, using only a few rotations, surprisingly placing GIFT as a very efficient candidate on micro-controllers. Our constant time implementations show that, on ARM Cortex-M3, 128-bit data can be ciphered with only about 800 cycles for GIFT-64 and about 1300 cycles for GIFT-128 (assuming pre-computed round keys). In particular, this is much faster than the impressive PRESENT implementation published at CHES 2017 that requires 2116 cycles in the same setting, or the current best AES constant time implementation reported that requires 1617 cycles. This work impacts GIFT, but also improves software implementations of all other cryptographic primitives directly based on it or strongly related to it. For example, we observe that with the fixslicing technique GIFT-COFB performs faster than Ascon on ARM Cortex-M processors.

Secure multi-party computation has been extensively studied in the past years and has reached a level that is considered practical for several applications. The techniques developed thus far have been steadily optimized for performance and were shown to be secure in the classical setting, but are not known to be secure against quantum adversaries. In this work, we start to pave the way for secure two-party computation in a quantum world where the adversary has access to a quantum computer. We show that post-quantum secure two-party computation has comparable efficiency to their classical counterparts. For this, we develop a lattice-based OT protocol which we use to implement a post-quantum secure variant of Yao's famous garbled circuits (GC) protocol (FOCS'82). Along with the OT protocol, we show that the oblivious transfer extension protocol of Ishai et al. (CRYPTO'03), which allows running many OTs using mainly symmetric cryptography, is post-quantum secure. To support these results, we prove that Yao's GC protocol achieves post-quantum security if the underlying building blocks do.

We present the first practical software implementation of Supersingular Isogeny Key Encapsulation (SIKE) round 2, targeting NIST's 1, 2, and 5 security levels on 32-bit ARM Cortex-M4 microcontrollers. The proposed library introduces a new speed record of SIKE protocol on the target platform. We achieved this record by adopting several state-of-the-art engineering techniques as well as highly-optimized hand-crafted assembly implementation of finite field arithmetic. In particular, we carefully redesign the previous optimized implementations of filed arithmetic on 32-bit ARM Cortex-M4 platform and propose a set of novel techniques which are explicitly suitable for SIKE/SIDH primes. Moreover, the proposed arithmetic implementations are fully scalable to larger bit-length integers and can be adopted over different security levels. The benchmark result on STM32F4 Discovery board equipped with 32-bit ARM Cortex-M4 microcontrollers shows that the entire key encapsulation over p434 takes about 326 million clock cycles (i.e. 1.94 seconds @168MHz). In contrast to the previous optimized implementation of the isogeny-based key exchange on low-power 32-bit ARM Cortex-M4, our performance evaluation shows feasibility of using SIKE mechanism on the target platform. In comparison to the most of the post-quantum candidates, SIKE requires an excessive number of arithmetic operations, resulting in significantly slower timings. However, its small key size makes this scheme as a promising candidate on low-end microcontrollers in the quantum era by ensuring the lower energy consumption for key transmission than other schemes.

The US National Institute of Standards and Technology (NIST) recently announced the public-key cryptosystems (PKC) that have passed to the second round of the post-quantum standardization process. Most of these PKC come in two flavours: a weak IND-CPA version and a strongly secure IND-CCA construction. For the weaker scheme, no level of security is claimed in the plaintext-checking attack (PCA) model. However, previous works showed that, for several NIST candidates, only a few PCA queries are sufficient to recover the secret key. In order to create a more complete picture, we design new key-recovery PCA against several round 2 candidates. Our attacks against CRYSTALS-Kyber, HQC, LAC and SABER are all practical and require only a few thousand queries to recover the full secret key. In addition, we present another KR-PCA attack against the rank-based scheme RQC, which needs roughly $O(2^{38})$ queries. Hence, this type of scheme seems to resist better than others to key recovery. Motivated by this observation, we prove an interesting result on the rank metric. Namely, that the learning problem with the rank distance is hard for some parameters, thus invalidating a common strategy for reaction attacks.

Rainbow is a signature scheme that is based on multivariate polynomials. It is one of the Round-2 candidates of the NIST’s Post-Quantum Cryptography Standardization project. Its computations rely heavily on GF(2^8) arithmetic and the Rainbow submission optimizes the code by using AVX2 shuffle and permute instructions. In this paper, we show a new optimization that leverages: a) AVX512 architecture; b) the latest processor capabilities Galois Field New Instructions(GF-NI), available on Intel "Ice Lake" processor. We achieved a speedup of 2.43x/3.13x/0.64x for key generation/signing/verifying, respectively. We also propose a variation of Rainbow, with equivalent security, using a different representation of GF(2^8). With this variant, we achieve a speedup of 2.44x/4.7x/2.1x for key generation/signing/verifying, respectively.

With the growth of cloud computing, the need arises for Private Set Intersection (PSI) protocols that can operate on outsourced data and delegate computation to cloud servers. One limitation of existing delegated PSI protocols is that they are all designed for static data and do not allow efficient update on outsourced data. Another limitation is that they cannot efficiently support PSI among multiple clients, which is often needed in practice. This paper presents “Feather”, the first delegated PSI protocol that supports efficient data updates and scalable multi-party PSI computation on outsourced datasets. The clients can independently prepare and upload their private data to the cloud once, then delegate the computation an unlimited number of times. The update operation has O(1) communication and computation complexity, and this is achieved without sacrificing PSI efficiency and security. Feather does not use public key cryptography, that makes it more scalable. We have implemented a prototype and compared the concrete performance against the state of the art. The evaluation indicates that Feather does achieve better performance in both update and PSI computation.

The breakthrough of blockchain in many decentralized cryptocurrencies has reactivated studies on consensus under network synchrony, which has better security than a consensus under network asynchrony but has been considered to be impractical and only theoretical so far. One of the biggest concerns is the speed of transaction processing. To solve this concern, transactions can be processed responsively, i.e., without reliance on synchrony. Another approach is to minimize reliance on synchrony to achieve optimal synchronous latency. In this paper, we consider answering the question ”Can we achieve both responsiveness and optimal synchronous latency?”. To do this, we first show some theoretical possibilities and impossibilities in achieving both responsiveness and optimal synchronous latency, and then we present a practical blockchain or state machine replication protocol we call Hybrid-BFT. Hybrid-BFT can process transactions responsively under normal situation, i.e., small number of faults, while it can achieve optimal synchronous latency even under worst situation. Furthermore, Hybrid-BFT achieves responsive leader change, making it completely free from synchronous delay under normal situation.

Modern electronic voting systems (e-voting systems) are designed to provide not only vote privacy but also (end-to-end) verifiability. Several verifiable e-voting systems have been proposed in the literature, with Helios being one of the most prominent ones.

Almost all such systems, however, reveal not just the voting result but also the full tally, consisting of the exact number of votes per candidate or even all single votes. There are several situations where this is undesirable. For example, in elections with only a few voters (e.g., boardroom or jury votings), revealing the complete tally leads to a low privacy level, possibly deterring voters from voting for their actual preference. In other cases, revealing the complete tally might unnecessarily embarrass some candidates. Often, the voting result merely consists of a single winner or a ranking of candidates, so revealing only this information but not the complete tally is sufficient. This property is called tally-hiding and it offers completely new options for e-voting.

In this paper, we propose the first provably secure end-to-end verifiable tally-hiding e-voting system, called Ordinos. We instantiated our system with suitable cryptographic primitives, including an MPC protocol for greater-than tests, implemented the system, and evaluated its performance, demonstrating its practicality. Moreover, our work provides a deeper understanding of tally-hiding in general, in particular in how far tally-hiding affects the levels of privacy and verifiability of e-voting systems.

In this work we develop a rewarding framework that can be used as a building block in crowd-sensing applications. Although a core requirement of such systems is user engagement, people may be reluctant to participate as sensitive information about them may be leaked or inferred from submitted data. Thus monetary incentives could help attract a large number of participants, thereby increasing not only the amount but also the quality of sensed data. Our first contribution in this work is to ensure that users can submit data and obtain Bitcoin payments in a privacy-preserving manner, preventing curious providers from linking the data or the payments back to the user. At the same time, we thwart malicious user behavior such as double-redeeming attempts where a user tries to obtain rewards for multiple submissions of the same data. More importantly, we ensure the fairness of the exchange in a completely trustless manner; by relying on the Blockchain, we eliminate the trust placed on third parties in traditional fair exchange protocols. Finally, our system is highly efficient as most of the protocol steps do not utilize the Blockchain network. When they do, we only rely on simple Bitcoin transactions as opposed to prior works that are based on the use of highly complex smart contracts.

Chameleon-hash functions, introduced by Krawczyk and Rabin at NDSS 2000, are trapdoor collision-resistant hash-functions parametrized by a public key. If the corresponding secret key is known, arbitrary collisions for the hash function can be efficiently found. Chameleon-hash functions have prominent applications in the design of cryptographic primitives, such as lifting non-adaptively secure signatures to adaptively secure ones. Recently, this primitive also received a lot of attention as a building block in more complex cryptographic applications ranging from editable blockchains to advanced signature and encryption schemes.

We observe that in latter applications various different notions of collision-resistance are used, and it is not always clear if the respective notion does really cover what seems intuitively required by the application. Therefore, we revisit existing collision-resistance notions in the literature, study their relations, and - using the example of the recent redactable blockchain proposals - discuss which practical impact different notions of collision-resistance might have. Moreover, we provide a stronger, and arguably more desirable, notion of collision-resistance than what is known from the literature. Finally, we present a surprisingly simple and efficient black-box construction of chameleon-hash functions achieving this strong notion.

As part of our planned expansion in the area of Cybersecurity, the Department of Mathematics and Computer Science at the University of Southern Denmark, Odense, invites applications for an assistant professor position in Computer Science. We interpret the area cybersecurity broadly: the ideal applicant is a computer scientist with a strong theoretical background, conducting research on cybersecurity or research that has cybersecurity as a direct application. We would like to expand on our current security research efforts within Cryptology, Formal Methods, Information Security, Security in DevOps, and Data-driven approaches, so these topics are of particular interest. Application deadline: 30 May 2020.

Closing date for applications:

Contact: Jacopo Mauro mauro@imada.sdu.dk or Joan Boyar joan@imada.sdu.dk

More information: https://www.sdu.dk/da/service/ledige_stillinger/1098235