International Association
for Cryptologic Research

The optimization of the main key compression bottlenecks of the supersingular isogeny key encapsulation mechanism (SIKE) has been a target of research in the last few years. Significant improvements were introduced in the recent works of Costello et al. and Zanon et al. The combination of the techniques in Zanon et al. reduced the running time of binary torsion basis generation in decompression by a factor of 29 compared to previous work. On the other hand, generating such a basis still takes almost a million cycles on an Intel Core i5-6267U. In this paper, we continue the work of Zanon et al. and introduce a technique that drops the complexity of binary torsion basis generation by a factor log p in the number of underlying field multiplications. In particular, our experimental results show that a basis can be generated in about 1.3k cycles, attaining an improvement by a factor more than 600. Although this result eliminates one of the key compression bottlenecks, many other bottlenecks remain. In addition, we give further improvements for the ternary torsion generation with significant impact on the related decompression procedure. Moreover, a new trade-off between ciphertext sizes vs decapsulation speed and storage is introduced and achieves a 2 times faster decapsulation.

The one-out-of-many proof is a cryptographic zero-knowledge construction enabling the prover to demonstrate knowledge of a secret element among the given public list of cryptographic commitments opening to zero. This method is relying on standard Decisional Diffie-Hellman security assumptions and can result in efficient accountable ring signature schemes [4] and proofs of set memberships [5] with a signature size smaller than all existing alternative schemes relying on standard assumptions. This construction also serves as a fundamental building block for numerous recent blockchain privacy protocols including Anonymous Zether, Zerocoin, Lelantus, Lelantus-MW, Triptych and Triptych-2. One-out-of-many proofs require O(logN)-sized communication and can be implemented in O(N) time for the verifier and O(NlogN) time for the prover. In this work, we introduce a new method of instantiating one-out-of-many proofs which reduces the proof generation time by an order of magnitude. In certain practical applications our method also helps to fasten the verification process of multiple simultaneously generated proofs. Our approach still results in shorter proofs comprised of only a logarithmic number of commitments and does not compromise the highly efficient batch verification properties endemic to the original construction. We believe this work can also foster further research towards building more efficient one-out-of-many proofs which are extremely useful constructions in the blockchain privacy space and beyond.

Mathematics and cryptography have a long history together, with the ups and downs inherent in any long relationship. Whether it is a marriage of convenience or a love match, their progeny have lives of their own and have had an impact on the world. This invited lecture will briefly recall some high points from the past, give speculation and encouragement for the future of this marriage, and give counseling on how to improve communication, resolve conflicts, and play well together, based on personal experience and lessons learned.

In a joint effort to fight the COVID-19 pandemic, Apple Inc. and Google Inc. recently partnered to develop a contact tracing technology to help governments and health agencies reduce the spread of the virus, with user privacy and security central to the design. The partnership announcement included technical specifications of the planned technology, which has great potential for widespread adoption due to the global reach of the two companies. In this report, we provide a security analysis of these specifications. We show that the current specifications may introduce significant risks to society and propose mitigation strategies for these risks that do not require major changes to the technology and are easy to adopt. Our analysis focuses mostly on system security considerations yet also includes information security considerations. We leave out of scope a discussion on how important or effective the technology is in fighting the pandemic.

Picnic is a digital signature algorithm designed to provide security against attacks by quantum computers. The design uses only symmetric-key primitives, and is an efficient instantiation of the MPC-in-the-head paradigm. In this work, we explore the Picnic design in great detail. We investigate and benchmark different parameter choices and show that there exist better parameter choices than those in the current specification. We also present improvements to the MPC protocol that shorten signatures and reduce signing time. The proposed MPC changes tailor the protocol to the circuit of interest in Picnic, but may also be of independent interest. Taken together, these changes give a new instantiation of Picnic that signs messages 7.9 to 13.9 times faster, and verifies signatures 4.5 to 5.5 times faster than the existing ``Picnic2'' design, while having nearly the same signature sizes.

The COVID-19 pandemic has posed a unique challenge for the world to find solutions, ranging from vaccines to ICT solutions to slow down the virus spreading. Due to the highly contagious nature of the virus, social distancing is one fundamental measure which has already adopted by many countries. At the technical level, this prioritises contact tracing solutions, which can alert the users who have been in close contact with the infected persons and meanwhile allow heath authorities to take proper actions. In this paper, we examine several existing privacy-aware contact tracing solutions and analyse their (dis)advantages. At the end, we describe several major observations and outline an interdisciplinary research agenda towards more comprehensive and effective privacy-aware contact tracing solutions.

In this work we present a duplex-based authenticated encryption scheme Friet based on a new permutation called Friet-P. We designed Friet-P with a novel approach for cryptographic permutations and block ciphers that takes fault-attack resistance into account and that we introduce in this paper. In this method, we build a permutation $f_C$ to be embedded in a larger one, $f$ . First, we define $f$ as a sequence of steps that all abide a chosen error-correcting code $C$, i.e., that map $C$-codewords to $C$-codewords. Then, we embed $f_C$ in $f$ by first encoding its input to an element of $C$, applying $f$ and then decoding back from $C$. This last step detects a fault when the output of $f$ is not in $C$. We motivate the design of the permutation we use in Friet and report on performance in soft- and hardware. We evaluate the fault-detection capabilities of the software and simulated hardware implementations with attacks. Finally, we perform a leakage evaluation. Our code is available at https://github.com/thisimon/Friet.git.

The golden collision problem asks us to find a single, special collision among the outputs of a pseudorandom function. This generalizes meet-in-the-middle problems, and is thus applicable in many contexts, such as cryptanalysis of the NIST post-quantum candidate SIKE.

The main quantum algorithms for this problem are memory-intensive, and the costs of quantum memory may be very high. The quantum circuit model implies a linear cost for random access, which annihilates the exponential advantage of the previous quantum collision-finding algorithms over Grover's algorithm or classical van Oorschot-Wiener.

Assuming that quantum memory is costly to access but free to maintain, we provide new quantum algorithms for the golden collision problem with high memory requirements but low gate costs. Under the assumption of a two-dimensional connectivity layout, we provide better quantum parallelization methods for generic and golden collision finding. This lowers the quantum security of the golden collision and meet-in-the-middle problems, including SIKE.

We prove that the following are equivalent:

- Existence of one-way functions: the existence of one-way functions (which in turn are equivalent to PRGs, pseudo-random functions, secure encryptions, digital signatures, commitment schemes, and more).

- Mild average-case hardness of $K^{poly}$-complexity: the existence of polynomials $t,p$ such that no PPT algorithm can determine the $t$-time bounded Kolmogorov Complexity, $K^t$, for more than a $1-\frac{1}{p(n)}$ fraction of $n$-bit strings.

In doing so, we present the first natural, and well-studied, computational problem characterizing "non-trivial" complexity-based Cryptography: "Non-trivial" complexity-based Cryptography is possible iff $K^{poly}$ is mildly hard-on average.

Pattern matching is one of the most fundamental and important paradigms in digital forensics and cyber threat intelligence approaches. While it is a straightforward operation when performed on plaintext data, it becomes a challenging task when the privacy of both the analyzed data and the analysis patterns must be preserved. In this paper, we propose P$^3$MED: a new provably correct, secure, and quite efficient construction that allows arbitrary pattern matching over encrypted data while fully protecting both the data to be analyzed and the patterns to be matched. That is, the entity that will perform pattern matching will learn nothing about the patterns to be searched as well as the data to be inspected, except the presence or the absence of a set of "unknown" patterns (the entity charged to perform pattern matching will not have access to the analysis patterns plaintexts). Compared to existing solutions, the construction we propose has some remarkable properties: (1) the size of the ciphertext is linear to the size of plaintext and independent of the sizes and the number of the analysis patterns; (2) the sizes of the issued trapdoors are constant on the size of the data to be analyzed; and (3) the search complexity is linear to the size of the data to be inspected and is constant on the sizes of the analysis patterns. The conducted evaluations show that P$^3$MED drastically improves the performance of the most efficient state of the art solution.

Blockchain Sharding (BS) is a blockchain improvement approach. It increases the overall transaction throughput, reduces the resource required, and increases the reward expectation for nodes by splitting the blockchain into several parallel-running committees (shards). Recently, several flexible sharding methods that can tolerate up to $n/2$ Byzantine nodes ($n/2$ security level) have been proposed. However, the nodes in these methods may be frequently reassigned from shard to shard to maintain security when others leave the system.

Theoretically, nodes in non-sharding blockchains have different weight (power or stake) for creating a consensus, so that the adversary needs to control half of the overall weight of the system to make a piece of faulty information accepted into the blockchain ($p/2$ security level). However, all the nodes in the BS approaches carry the same weight, and it is only under the assumption that the honest participants are creating as many nodes as they can, that the $n/2$ security level BS approach reaches the $p/2$ security level.

In this paper, we present Multichain MWPoW, a $p/2$ security level BS architecture that does not require honest participants to create multiple nodes and allows for fewer node reassignments. It combines the Multiple Winners Proof of Work consensus protocol (MWPoW) and a flexible $n/2$ blockchain sharding approach. Our experiments suggest that Multichain MWPoW largely outperforms existing BSs in terms of security, transaction throughput and flexibility.

We present a card-based protocol for computing a three-input majority using six cards. The protocol essentially consists of performing a simple XOR protocol two times. Compared to the existing protocols, our protocol does not require private operations other than choosing cards.

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.