International Association
for Cryptologic Research

A recent result by Dulek et al. (EUROCRYPT 2020) showed a secure protocol for computing any quantum circuit even without the presence of an honest majority. Their protocol, however, is susceptible to a ``denial of service'' attack and allows even a single corrupted party to force an abort. We propose the first quantum protocol that admits security-with-identifiable-abort, which allows the honest parties to agree on the identity of a corrupted party in case of an abort. Additionally, our protocol is the first to have the property that the number of rounds where quantum communication is required is independent of the circuit complexity. Furthermore, if there exists a post-quantum secure classical protocol whose round complexity is independent of the circuit complexity, then our protocol has this property as well. Our protocol is secure under the assumption that classical fully homomorphic encryptions schemes exist.

In this article, we analyze and investigate two authenticated encryption algorithms: GIFT-COFB and HyENA. The two modes differ in some low levels details in both the design and security proofs. However, they share a lot of similarities. We take a look at the best-known attacks and security proofs of these designs. We show that the best-known attack is not a matching attack to the security bounds provided by the designers in the security proof. Second, we give a new attack that we characterize as an {\it "almost matching"} attack. It is significantly closer to the provable security bounds. The new attack requires $O(2^{n/4})$ encryptions and $O(2^{n/2})$ decryptions, as opposed to $O(2^{n/2})$ encryptions and $O(2^{n/2})$ decryptions shown previously. However, there is still a substantial logarithmic gap between this attack and the corresponding security bound. Next, we analyze why this gap still exists and why it is unlikely to find matching attacks. We give two arguments. The first argument is by analyzing the security proof and showing how it masks a term with non-negligible encryption complexity. The second argument looks at the attacker's point of view. A successful attack requires satisfying a non-trivial linear equation over secret random variables. Satisfying such an equation requires more decryption queries than what is bounded by the security proof. It is worth emphasizing that the analysis and attacks presented in this paper {\it do not} threaten the security claims made by the designers or the security of these designs within the parameters required by the NIST lightweight cryptography project. The results increase confidence in the security claims of GIFT-COFB and HyENA while showing their limitations by relying mostly on bounding the number of unsuccessful forgeries.

The Covid-19 pandemic created various new challenges for our societies. Quickly discovering new infections using automated contact tracing without endangering privacy of the general public is one of these. Most discussions concerning architectures for contact tracing applications revolved around centralized against decentralized approaches. In contrast, the system proposed in this work builds on the idea of message-based contact tracing to inform users of their risk. Our main contribution is the combination of a blind-signature approach to verify infections with an anonymous postbox service. In our evaluation we analyze all components in our system for performance and privacy, as well as security. We derive parameters for operating our system in a pandemic scenario.

The Cyber Science Lab at the School of Computer Science, University of Guelph, Canada, has two fully funded PhD positions in Cybersecurity. The Cyber Science Lab is a research lab focused on advancing knowledge and practice in AI for Security and Security of AI systems. There are also many opportunities to work on industry projects in the lab. Normally PhD students work on two industry projects during their study and can make an additional 30,000 CAD/year through industry projects. For more details see https://cybersciencelab.org/open-phd-positions

Closing date for applications:

Contact: Ali Dehghantanha (ali@cybersciencelab.org) or Khodakhast Bibak (bibakk@miamioh.edu).

The Cyber Science Lab at the School of Computer Science, University of Guelph, Canada, is looking for a Postdoctoral Research Fellow in Security of AI/ML systems. Strong applicants in other areas of Cybersecurity may also be considered. The initial appointment would be for one year and can be extended for another year. Salary will be in the range of $60,000 to $75,000 a year commensurate with experience, and extended health coverage is also provided. Candidates with strong track of publication or previous postdoc experience are normally receiving higher salaries. For more details see https://cybersciencelab.org/open-positions.

Closing date for applications:

Contact: Ali Dehghantanha (ali@cybersciencelab.org) or Khodakhast Bibak (bibakk@miamioh.edu).

There are two Ph.D. positions opening at Dr. Jiafeng Harvest Xie's research group at the Department of Electrical and Computer Engineering of Villanova University, Villanova, PA (west of Philadelphia), USA. The research topics of this position primarily focused on fault attack/detection related to the AI system and post-quantum cryptosystems. Interested ones are warmly welcomed to send their resume/CV to Dr. Xie through email: jiafeng.xie@villanova.edu

Requirements: preferred to be at the majors of Computer Science, Computer Engineering, Electrical Engineering and related others. Familiar with fault attack and analysis will be desirable. Proficiency in programming languages such as C/C++ and HDLs. Good at English communication and writing. Great enthusiasm of doing research oriented tasks. Excellent team work member.

Degree: both B.S. and M.S. graduates or similar are warmly welcomed to apply.

Start date: Spring 2021 and Fall 2021 are both ok. It is always better to apply as early as possible. Positions are open until they are filled.

The 2021 U.S. News & World Report ranks Villanova as tied for the 53th best National University in the U.S.

Brief introduction of Dr. Xie: Dr. Jiafeng Harvest Xie is currently an Assistant Professor at the Department of Electrical and Computer Engineering of Villanova University. His research interests include cryptographic engineering, hardware security, and VLSI digital design. He is the Best Paper Awardee of IEEE HOST 2019. He has served the Associate Editor for Microelectronics Journal, IEEE Access, and IEEE Trans. Circuits and Systems II. He has also been awarded the 2019 IEEE Access Outstanding Associate Editor.

Contact: Jiafeng Harvest Xie (jiafeng.xie@villanova.edu)

Closing date for applications:

Contact: Jiafeng Harvest Xie

The modular squaring operation has attracted significant attention due to its potential in constructing cryptographic time-lock puzzles and verifiable delay functions. In such applications, it is important to understand precisely how quickly a modular squaring operation can be computed, even in parallel on dedicated hardware.

We use tools from circuit complexity and number theory to prove concrete numerical lower bounds for squaring on a parallel machine, yielding nontrivial results for practical input bitlengths. For example, for $n=2048$, we prove that every logic circuit (over AND, OR, NAND, NOR gates of fan-in two) computing modular squaring on all $n$-bit inputs (and any modulus that is at least $2^{n-1}$) requires depth (critical path length) at least $12$. By a careful analysis of certain exponential Gauss sums related to the low-order bit of modular squaring, we also extend our results to the average case. For example, our results imply that every logic circuit (over any fan-in two basis) computing modular squaring on at least $76\%$ of all $2048$-bit inputs (for any RSA modulus that is at least $2^{n-1}$) requires depth at least $9$.

We present MAGIC, a mode for authenticated encryption that simultaneously supports encryption, message authentication and error correction, all with the same code. In MAGIC, the same code employed for cryptographic integrity is also the parity used for error correction. To correct errors, MAGIC employs the Galois Hash transformation, which due to its bit linearity can perform corrections in a similar way as other codes do (e.g., Reed Solomon). To provide a cryptographically strong MAC, MAGIC encrypts the output of the Galois Hash using a secret key. To analyze the security of this construction we adapt the definition of the MAC adversary so that it is applicable to systems that combine message authentication with error correction. We demonstrate that MAGIC offers security in the order of O(2^(N/2)) with N being the tag size.

In this report, we analyze the hardware implementations of 10 candidates for Round 2 of the NIST lightweight cryptography standardization process. These candidates are Ascon, DryGASCON, Elephant, Gimli, PHOTON-Beetle, Pyjamask, Romulus, Subterranean, TinyJAMBU and Xoodyak. Specifically, we study the implementations of these algorithms when synthesized using the TSMC 65nm and FDSOI 28nm technologies and Synopsys Design Compiler, targeting various performance trade-offs and different use-cases. We show how different candidates stack-up against such trade-offs. We base our benchmarking parameters and metrics on real-world use-cases, such as high-speed applications, lightweight communication protocols and internet payloads.

Ascon, DryGASCON, and Shamash are submissions to NIST's lightweight cryptography standardization process and have similar designs. We analyze these algorithms against subspace trails, truncated differentials, and differential-linear distinguishers. We provide probability one 4-round subspace trails for DryGASCON-256, 3-round subspace trails for \DryGASCON-128, and 2-round subspace trails for \Shamash permutations. Moreover, we provide the first 3.5-round truncated differential and 5-round differential-linear distinguisher for DryGASCON-128. Finally, we improve the data and time complexity of the 4 and 5-round differential-linear attacks on Ascon.

This work presents a detailed study of the classical security of the post-quantum supersingular isogeny key encapsulation (SIKE) protocol using a realistic budget-based cost model that considers the actual computing and memory costs that are needed for cryptanalysis. In this effort, we design especially-tailored hardware accelerators for the time-critical isogeny computations that we use to model an ASIC-powered instance of the van Oorschot-Wiener (vOW) parallel collision search algorithm. We then extend the analysis to AES and SHA-3 in the context of the NIST post-quantum cryptography standardization process to carry out a parameter analysis based on our cost model. This analysis, together with the state-of-the-art quantum security analysis of SIKE, indicates that the current SIKE parameters offer a wide security margin, which in turn opens up the possibility of using significantly smaller primes that would enable more efficient and compact implementations with reduced bandwidth. Our improved cost model and analysis can be applied widely to other cryptographic settings and primitives, and can have implications for other post-quantum candidates in the NIST process.

Authenticated encryption (AE) is used in a wide variety of applications, potentially in settings for which it was not originally designed. Recent research tries to understand what happens when AE is not used as prescribed by its designers. A question given relatively little attention is whether an AE scheme guarantees "key commitment'': ciphertext should decrypt to a valid plaintext only under the key that was used to generate the ciphertext. As key commitment is not part of AE's design goal, AE schemes in general do not satisfy it. Nevertheless, one would not expect this seemingly obscure property to have much impact on the security of actual products. In reality, however, products do rely on key commitment. We discuss three recent applications where missing key commitment is exploitable in practice. We provide proof-of-concept attacks via a tool that constructs AES-GCM ciphertext which can be decrypted to two plaintexts valid under a wide variety of file formats, such as PDF, Windows executables, and DICOM. Finally we discuss two solutions to add key commitment to AE schemes which have not been analyzed in the literature: one is a generic approach that adds an explicit key commitment scheme to the AE scheme, and the other is a simple fix which works for AE schemes like AES-GCM and ChaCha20Poly1305, but requires separate analysis for each scheme.

In the last few years a new design paradigm, the so-called ARX (modular addition, rotation, exclusive-or) ciphers, have gained popularity in part because of their non-linear operation's seemingly `inherent resilience' against Differential Power Analysis (DPA) Attacks: the non-linear modular addition is not only known to be a poor target for DPA attacks, but also the computational complexity of DPA-style attacks grows exponentially with the operand size and thus DPA-style attacks quickly become practically infeasible. We however propose a novel DPA-style attack strategy that scales linearly with respect to the operand size in the chosen-message attack setting.

We study the problem of enforcing circuit privacy for the homomorphic evaluation of quantum circuits. We present a generic transformation from semi-honest to malicious circuit privacy for quantum fully homomorphic encryption (QFHE). Our compiler assumes minimal structural properties of the underlying QFHE scheme, which are satisfied by recent candidate constructions [Mahadev, FOCS 2018]. Thus we obtain a maliciously circuit private QFHE scheme, assuming the quantum hardness of (a circular variant of) the learning with errors (LWE) problem. This immediately implies the existence of a two-round secure function evaluation protocol for quantum circuits with input-indistinguishable security for the client (holding a quantum state $\ket{\psi}$) and unbounded simulation security for the server (evaluating a quantum circuit $C$).

Secret sharing was proposed primarily in 1979 to solve the problem of key distribution. In recent decades, researchers have proposed many improvement schemes. Among all these schemes, the verifiable multi-secret sharing (VMSS) schemes are studied sufficiently, which share multiple secrets simultaneously and perceive malicious dealer as well as participants. By pointing out that the schemes presented by Dehkordi and Mashhadi in 2008 cannot detect some vicious behaviors of the dealer, we propose two new VMSS schemes by adding validity check in the verification phase to overcome this drawback. Our new schemes are based on XTR public key system, and can realize $GF(p^{6})$ security by computations in $GF(p^{2})$ without explicit constructions of $GF(p^{6})$, where $p$ is a prime. Compared with the VMSS schemes using RSA and linear feedback shift register (LFSR) public key cryptosystems, our schemes can achieve the same security level with shorter parameters by using trace function. What's more, our schemes are much simpler to operate than those schemes based on Elliptic Curve Cryptography (ECC). In addition, our schemes are dynamic and threshold changeable, which means that it is efficient to implement our schemes according to the actual situation when participants, secrets or the threshold needs to be changed.

The security of digital communication relies on few cryptographic protocols that are used to protect internet traffic, from web sessions to instant messaging. These protocols and the cryptographic primitives they rely on have been extensively studied and are considered secure.Yet, sophisticated attackers are often able to bypass rather than break security mechanisms. Kleptography or algorithm substitution attacks (ASA) describe techniques to place backdoors right into cryptographic primitives. While highly relevant as a building block, we show that the real danger of ASAs is their use in cryptographic protocols. In fact, we show that a highly desirable security property of these protocols - forward secrecy - implies the applicability of ASAs. We then analyze the application of ASAs in three widely used protocols: TLS, WireGuard, and Signal. We show that these protocols can be easily subverted by carefully placing ASAs. Our analysis shows that careful design of ASAs makes detection unlikely while leaking long-term secrets within a few messages in the case of TLS and WireGuard, allowing impersonation attacks. In contrast, Signal's double-ratchet protocol shows high immunity to ASAs, as the leakage requires much more messages. But once Signal's long-term key is leaked, the security of the Signal messenger is completely subverted by our attack due to unfortunate choices in the implementation of Signal's multi-device support.

Secure computation protocols enable mutually distrusting parties to compute a function of their private inputs while revealing nothing but the output. Protocols with {\em full security} (also known as {\em guaranteed output delivery}) in particular protect against denial-of-service attacks, guaranteeing that honest parties receive a correct output. This feature can be realized in the presence of an honest majority, and significant research effort has gone toward attaining full security with good asymptotic and concrete efficiency.

We present an efficient protocol for {\em any constant} number of parties $n$, with {\em full security} against $t<n/2$ corrupted parties, that makes a black-box use of a pseudorandom generator. Our protocol evaluates an arithmetic circuit $C$ over a finite ring $R$ (either a finite field or $R=\Z_{2^k}$) with communication complexity of $\frac{3t}{2t+1}S + o(S)$ $R$-elements per party, where $S$ is the number of multiplication gates in $C$ (namely, $<1.5$ elements per party per gate). This matches the best known protocols for the semi-honest model up to the sublinear additive term. For a small number of parties $n$, this improves over a recent protocol of Goyal {\em et al.} (Crypto 2020) by a constant factor for circuits over large fields, and by at least an $\Omega(\log n)$ factor for Boolean circuits or circuits over rings.

Our protocol provides new methods for applying the sublinear-communication distributed zero-knowledge proofs of Boneh {\em et al.}~(Crypto 2019) for compiling semi-honest protocols into fully secure ones, in the more challenging case of $t>1$ corrupted parties. Our protocol relies on {\em replicated secret sharing} to minimize communication and simplify the mechanism for achieving full security. This results in computational cost that scales exponentially with $n$.

Our main fully secure protocol builds on a new intermediate honest-majority protocol for verifying the correctness of multiplication triples by making a {\em general} use of distributed zero-knowledge proofs. While this intermediate protocol only achieves the weaker notion of {\em security with abort}, it applies to any linear secret-sharing scheme and provides a conceptually simpler, more general, and more efficient alternative to previous protocols from the literature. In particular, it can be combined with the Fiat-Shamir heuristic to simultaneously achieve logarithmic communication complexity and constant round complexity.

Anonymous attestation for secure hardware platforms leverages tailored group signature schemes and assumes the hardware to be trusted. Yet, there is an ever increasing concern on the trustworthiness of hardware components and embedded systems. A subverted hardware may, for example, use its signatures to exfiltrate identifying information or even the signing key.

In this paper we focus on Enhanced Privacy ID (EPID)---a popular anonymous attestation scheme used in commodity secure hardware platforms like Intel SGX. We define and instantiate a \emph{subversion resilient} EPID scheme (or SR-EPID). In a nutshell, SR-EPID provides the same functionality and security guarantees of the original EPID, despite potentially subverted hardware. In our design, a ``sanitizer'' ensures no covert channel between the hardware and the outside world both during enrollment and during attestation (i.e., when signatures are produced). We design a practical SR-EPID scheme secure against adaptive corruptions and based on a novel combination of malleable NIZKs and hash functions modeled as random oracles.

Our approach has a number of advantages over alternative designs. Namely, the sanitizer bears no secret information---hence, a memory leak does not erode security. Further, the role of sanitizer may be distributed in a cascade fashion among several parties so that sanitization becomes effective as long as one of the parties has access to a good source of randomness. Also, we keep the signing protocol non-interactive, thereby minimizing latency during signature generation.

We propose a practical zero-knowledge proof system for proving knowledge of short solutions s, e to linear relations A s + e= u mod q which gives the most efficient solution for two naturally-occurring classes of problems. The first is when A is very ``tall'', which corresponds to a large number of LWE instances that use the same secret s. In this case, we show that the proof size is independent of the height of the matrix (and thus the length of the error vector e) and rather only linearly depends on the length of s. The second case is when A is of the form A' tensor I, which corresponds to proving many LWE instances (with different secrets) that use the same samples A'. The length of this second proof is square root in the length of s, which corresponds to square root of the length of all the secrets. Our constructions combine recent advances in ``purely'' lattice-based zero-knowledge proofs with the Reed-Solomon proximity testing ideas present in some generic zero-knowledge proof systems -- with the main difference is that the latter are applied directly to the lattice instances without going through intermediate problems.

There has been a lot of recent progress in constructing efficient zero-knowledge proofs for showing knowledge of an $\polvec s$ with small coefficients satisfying $\pol A\polvec s=\polvec t$. For typical parameters, the proof sizes have gone down from several megabytes to a bit under $50$KB (Esgin et al., Asiacrypt 2020). These are now within an order of magnitude of the sizes of lattice-based signatures, which themselves constitute proof systems which demonstrate knowledge of something weaker than the aforementioned equation. One can therefore see that this line of research is approaching optimality. In this paper, we modify a key component of these proofs, as well as apply several other tweaks, to achieve a further reduction of around $30\%$ in the proof output size. We also show that this savings propagates itself when these proofs are used in a general framework to construct more complex protocols.