International Association
for Cryptologic Research

BLS signatures have fast aggregated signature verification but slow individual signature verification. We propose a three part optimisation that dramatically reduces CPU time in large distributed system using BLS signatures: First, public keys should be given on both source groups $\mathbb{G}_1$ and $\mathbb{G}_2$, with a proof-of-possession check for correctness. Second, aggregated BLS signatures should carry their particular aggregate public key in $\mathbb{G}_2$, so that verifiers can do both hash-to-curve and aggregate public key checks in $\mathbb{G}_1$. Third, individual non-aggregated BLS signatures should carry short Chaum-Pedersen DLEQ proofs of correctness, so that verifying individual signatures no longer requires pairings, which makes their verification much faster. We prove security for these optimisations. The proposed scheme is implemented and benchmarked to compare with classic BLS scheme.

QC-MDPC (quasi cyclic moderate density parity check) code-based McEliece cryptosystems are considered to be one of the candidates for post-quantum cryptography. Decreasing DER (decoding error rate) is one of important factor for their security, since recent attacks to these cryptosystems effectively use DER information. In this paper, we pursue the possibility of optimization-base decoding, concretely we examine ADMM (alternating direction method of multipliers), a recent developing method in optimization theory. Further, RSPA (reproducing sum-product algorithm), which efficiently reuse outputs of SPA (sum-product algorithm) is proposed for the reduction of execution time in decoding. By numerical simulations, we show that the proposing scheme shows considerable decrement in DER compared to the conventional decoding methods such as BF (bit-flipping algorithm) variants or SPA.

The desirable encryption scheme possesses high PRF security, high efficiency, and the ability to produce variable-length outputs. Since designing dedicated secure PRFs is difficult, a series of works was devoted to building optimally secure PRFs from the sum of independent permutations (SoP), Encrypted Davies-Meyer (EDM), its Dual (EDMD), and the Summation-Truncation Hybrid (STH) for variable output lengths, which can be easily instantiated from existing permutations. For increased efficiency, reducing the number of operations in established primitives has been gaining traction: Mennink and Neves pruned EDMD to FastPRF, and Andreeva et al. introduced ForkCiphers, which take an n-bit input, process it through a reduced-round permutation, fork it into two states, and feed each of them into another reduced-round permutation to produce a 2n-bit output. The constructions above can be used in secure variable-length modes or generalizations such as MultiForkCiphers. In this paper, we suggest a framework of those constructions in terms of the three desiderata: we span the spectrum of (1) output length vs. PRF security, (2) full vs. round-reduced primitives, and (3) fixed- vs. variable-length outputs. From this point of view, we identify remaining gaps in the spectrum and fill them with the proposal of several highly secure and efficient fixed- and variable-output-length PRFs. We fork SoP and STH to ForkPRF and ForkSTH, extend STH to the variable-output-length construction STHCENC, which bridges the gap between CTR mode and CENC,and propose ForkCENC, ForkSTHCENC, ForkEDMD, as well as ForkEDM-CTR as the variable-output-length and round-reduced versions of CENC, STH, FastPRF, and FastPRF's dual, respectively. Using recent results on Patarin's general Mirror Theory, we have proven that almost all our proposed PRFs are optimally secure under the assumption that the permutations are pairwise independent and random and STH achieves the optimal security depending on the output length. Our constructions can be highly efficient in practice. We propose efficient instantiations from round-reduced AES and back it with the cryptanalysis lessons learned from existing earlier analysis of AES-based primitives.

We design and implement a simple zero-knowledge argument protocol for $\mathsf{NP}$ whose communication complexity is proportional to the square-root of the verification circuit size. The protocol can be based on any collision-resistant hash function. Alternatively, it can be made non-interactive in the random oracle model, yielding concretely efficient zk-SNARKs that do not require a trusted setup or public-key cryptography. Our protocol is obtained by applying an optimized version of the general transformation of Ishai et al. (STOC 2007) to a variant of the protocol for secure multiparty computation of Damg$\mathring{a}$rd and Ishai (CRYPTO 2006). It can be viewed as a simple zero-knowledge interactive PCP based on ``interleaved'' Reed-Solomon codes.

This paper is an extended version of the paper published in CCS 2017 and features a tighter analysis, better implementation along with formal proofs. For large verification circuits, the Ligero prover remains competitive against subsequent works with respect to the prover’s running time, where our efficiency advantages become even bigger in an amortized setting, where several instances need to be proven simultaneously.

Our protocol is attractive not only for very large verification circuits but also for moderately large circuits that arise in applications. For instance, for verifying a SHA-256 preimage with $2^{-40}$ soundness error, the communication complexity is roughly 35KB.

The communication complexity of our protocol is independent of the circuit structure and depends only on the number of gates. For $2^{-40}$ soundness error, the communication becomes smaller than the circuit size for circuits containing roughly 3 million gates or more. With our refined analysis the Ligero system's proof lengths and prover's running times are better than subsequent post-quantum ZK-SNARKs for small to moderately large circuits.

A Password-Authenticated Key Exchange (PAKE) protocol allows two parties to agree upon a cryptographic key, when the only information shared in advance is a low-entropy password. The standard security notion for PAKE (Canetti et al., Eurocrypt 2005) is in the Universally Composable (UC) framework. We show that unlike most UC security notions, UC PAKE does not imply correctness. While Canetti et al. seems to have implicitly noticed this issue, it has yet to be explicitly identified by the PAKE literature. We present a comprehensive study of correctness in UC PAKE: 1. We show that TrivialPAKE, a no-message protocol that does not satisfy correctness, is a UC PAKE; 2. We propose nine approaches to guaranteeing correctness in the UC security notion of PAKE, and show that seven of them are equivalent, whereas the other two are unachievable; 3. We prove that a direct solution, namely changing the UC PAKE functionality to incorporate correctness, is impossible; 4. Finally, we show how to naturally incorporate correctness by changing the model — we view PAKE as a three-party protocol, with the man-in-the-middle adversary as the third party. In this way, we hope to shed some light on the very nature of UC-security in the man-in-the-middle setting.

Accountability is a well-established and widely used security concept that allows for obtaining undeniable cryptographic proof of misbehavior, thereby incentivizing honest behavior. There already exist several general purpose accountability frameworks for formal game-based security analyses. Unfortunately, such game-based frameworks do not support modular security analyses, which is an important tool to handle the complexity of modern protocols.

Universal composability (UC) models provide native support for modular analyses, including re-use and composition of security results. So far, accountability has mainly been modeled and analyzed in UC models for the special case of MPC protocols, with a general purpose accountability framework for UC still missing. That is, a framework that among others supports arbitrary protocols, a wide range of accountability properties, handling and mixing of accountable and non-accountable security properties, and modular analysis of accountable protocols.

To close this gap, we propose AUC, the first general purpose accountability framework for UC models, which supports all of the above, based on several new concepts. We exemplify AUC in three case studies not covered by existing works. In particular, AUC unifies existing UC accountability approaches within a single framework.

Fair exchange (also referred to as atomic swap) is a fundamental operation in any cryptocurrency, that allows users to atomically exchange coins. While a large body of work has been devoted to this problem, most solutions lack on-chain privacy. Thus, coins retain a public transaction history which is known to degrade the fungibility of a currency. This has led to a flourishing line of related research on fair exchange with privacy guarantees. Existing protocols either rely on heavy scripting (which also degrades fungibility), do not support atomic swaps across a wide range currencies, or come with incomplete security proofs.

To overcome these limitations, we introduce Sweep-UC (Read as Sweep Ur Coins), the first fair exchange protocol that simultaneously is efficient, minimizes scripting, and is compatible with a wide range of currencies (more than the state of the art). We build Sweep-UC from modular subprotocols and give a rigorous security analysis in the UC-framework. Many of our tools and security definitions can be used in standalone fashion and may serve as useful components for future constructions of fair exchange.

ARIA is a block cipher proposed by Kwon et al. at ICISC 2003, and it is widely used as the national standard block cipher in the Republic of Korea. In this study, we identify some flaws in the quantum rebound attack on 7-round ARIA-DM proposed by Dou et al., and we reveal that the limit of this attack is up to 5-round. Our revised attack applies not only to ARIA-DM but also to ARIA-MMO and ARIA-MP among the PGV models, and it is valid for all key lengths of ARIA. Moreover, we present dedicated quantum rebound attacks on 7-round ARIA-Hirose and ARIA-MJH for the first time. These attacks are only valid for the 256-bit key length of ARIA because they are constructed using the degrees of freedom in the key schedule. All our attacks are faster than the generic quantum attack in the cost metric of time–space tradeoff.

Fruit is a small-state stream cipher designed for securing communications among resource-constrained devices. The design of Fruit was first known to the public in 2016. It was later improved as Fruit-80 in 2018 and becomes the latest and final version among all versions of the Fruit stream ciphers. In this paper, we analyze the Fruit-80 stream cipher. We found that Fruit-80 generates identical keystreams from certain two distinct pairs of key and IV. Such pair of key and IV pairs is known as a slid pair. Moreover, we discover that when two pairs of key and IV fulfill specific characteristics, they will generate identical keystreams. This shows that slid pairs do not always exist arbitrarily in Fruit-80. We define specific rules which are equivalent to the characteristics. Using the defined rules, we are able to automate the searching process using an MILP solver, which makes searching of the slid pairs trivial.

Data privacy concerns are increasing significantly in the context of Internet of Things, cloud services, edge computing, artificial intelligence applications, and other applications enabled by next generation networks. Homomorphic Encryption addresses privacy challenges by enabling multiple operations to be performed on encrypted messages without decryption. This paper comprehensively addresses homomorphic encryption from both theoretical and practical perspectives. The paper delves into the mathematical foundations required to understand fully homomorphic encryption (FHE). It consequently covers design fundamentals and security properties of FHE and describes the main FHE schemes based on various mathematical problems. On a more practical level, the paper presents a view on privacy-preserving Machine Learning using homomorphic encryption, then surveys FHE at length from an engineering angle, covering the potential application of FHE in fog computing, and cloud computing services. It also provides a comprehensive analysis of existing state-of-the-art FHE libraries and tools, implemented in software and hardware, and the performance thereof.

In this paper, we reconsider the security for CRYSTALS-Dilithium, a lattice-based post-quantum signature scheme standardized by NIST. In their documentation, the authors proved that the security of the signature scheme can be based on the hardness of the following three assumptions: MLWE, MSIS and SelfTargetMSIS. While the first two are standard lattice assumptions with hardness well studied, the authors claimed that the third assumption SelfTargetMSIS can be estimated by the hardness of MSIS (and further into SIS). However, we point out that this is in fact not the case. We give a new algorithm for solving SelfTargetMSIS, by both experimental results and asymptotic complexities, we prove that under specific parameters, solving SelfTargetMSIS might be faster than MSIS. Although our algorithm does not propose a real threat to parameters used in Dilithium, we successfully show that solving SelfTargetMSIS cannot be turned into solving MSIS or MISIS. Furthermore, we define a new variant of MISIS, called sel-MISIS, and show that solving SelfTargetMSIS can only be turned into solving sel-MISIS. We believe that in order to fully understand the concrete hardness of SelfTargetMSIS and prevent potential attacks to Dilithium, the hardness of this new problem needs to be further studied.

We present novel protocols to compute SQL-like join operations on secret shared database tables with non-unique join keys. Previous approaches to the problem had the restriction that the join keys of both the input tables must be unique or had quadratic overhead. Our work lifts this restriction, allowing one or both of the secret shared input tables to have an unknown and unbounded number of repeating join keys while achieving efficient $O(n\log n)$ asymptotic communication/computation and $O(\log n)$ rounds of interaction, independent of the multiplicity of the keys.

We present two join protocols, \ProtoUni and \ProtoDup. The first, \ProtoUni is optimized for the case where one table has a unique primary key while the second, \ProtoDup is for the more general setting where both tables contain duplicate keys. Both protocols require $O(n \log n)$ time and $O(\log n)$ rounds to join two tables of size $n$. Our framework for computing joins requires an efficient sorting protocol and generic secure computation for circuits. We concretely instantiate our protocols in the honest majority three-party setting.

Our join protocols are built around an efficient method to compute structured aggregations over a secret shared input vector $\V\in \mathbb{D}^n$. If the parties have another secret-shared vector of control bits $\B \in \{0, 1\}^n$ to partition $\V$ into sub-vectors (that semantically relates to the join operations). A structured aggregation computes a secret shared vector $\V'\in \mathbb{D}^n$ where every sub-vector $(\V_b,...,\V_e)$ (defined by the control bits) is aggregated as $\V_i'=\V_b\op...\op \V_i$ for $i\in \{b,...,e\}$ according to some user-defined operator $\op$. Critically, the $b,e$ indices that partition the vector are secret. It's trivial to compute aggregations by sequentially processing the input vector and control bits. This would require $O(n)$ rounds and would be very slow due to network latency.

We introduce Aggregation Trees as a general technique to compute aggregations in $O(\log n)$ rounds. For our purpose of computing joins, we instantiate $\op \in$ \textsf{\{copy previous value, add\}}, but we believe that this technique is quite powerful and can find applications in other useful settings.

We initiate the study of streaming functional encryption (sFE) which is designed for scenarios in which data arrives in a streaming manner and is computed on in an iterative manner as the stream arrives. Unlike in a standard functional encryption (FE) scheme, in an sFE scheme, we (1) do not require the entire data set to be known at encryption time and (2) allow for partial decryption given only a prefix of the input. More specifically, in an sFE scheme, we can sequentially encrypt each data point $x_i$ in a stream of data $x = x_1\ldots x_n$ as it arrives, without needing to wait for all $n$ values. We can then generate function keys for streaming functions which are stateful functions that take as input a message $x_i$ and a state $\mathsf{st}_i$ and output a value $y_i$ and the next state $\mathsf{st}_{i+1}$. For any $k \leq n$, a user with a function key for a streaming function $f$ can learn the first $k$ output values $y_1\ldots y_k$ where $(y_i, \mathsf{st}_{i+1}) = f(x_i, \mathsf{st}_i)$ and $\mathsf{st}_1 = \bot$ given only ciphertexts for the first $k$ elements $x_1\ldots x_k$.

In this work, we introduce the notion of sFE and show how to construct it from FE. In particular, we show how to achieve a secure sFE scheme for $\mathsf{P/Poly}$ from a compact, secure FE scheme for $\mathsf{P/Poly}$, where our security notion for sFE is similar to standard FE security except that we require all function queries to be made before the challenge ciphertext query. Furthermore, by combining our result with the FE construction of Jain, Lin, and Sahai (STOC, 2022), we show how to achieve a secure sFE scheme for $\mathsf{P/Poly}$ from the polynomial hardness of well-studied assumptions.

In this work, we put forward the notion of ``efficiently testable circuits'' and provide circuit compilers that transform any circuit into an efficiently testable one. Informally, a circuit is testable if one can detect tampering with the circuit by evaluating it on a small number of inputs from some test set.

Our technical contribution is a compiler that transforms any circuit $C$ into a testable circuit $(\widehat{C}, \widehat{T})$ for which we can detect arbitrary tampering with all wires in $\widehat{C}$. The notion of a testable circuit is weaker or incomparable to existing notions of tamper-resilience, which aim to detect or even correct for errors introduced by tampering during every query, but our new notion is interesting in several settings, and we achieve security against much more general tampering classes -- like tampering with all wires -- with very modest overhead.

Concretely, starting from a circuit $C$ of size $n$ and depth $d$, for any $L$ (think of $L$ as a small constant, say $L=4$), we get a testable $(\widehat{C}, \widehat{T})$ where $\widehat{C}$ is of size $\approx 12n$ and depth $d+\log(n)+L\cdot n^{1/L}$. The test set $\widehat{T}$ is of size $4\cdot 2^L$. The number of extra input and output wires (i.e., pins) we need to add for the testing is $3+L$ and $2^L$, respectively.

The paper " An energy and area efficient, all digital entropy source compatible with modern standards based on jitter pipelining", by Peetermans and Verbauwhede, IACR Transactions on Cryptographic Hardware and Embedded Systems, Aug. 2022, 88-109, suggests a pipelined TRNG design and a stochastic model for it. The stochastic model is shown to be inadequate and other problems of the TRNG design are identified. Possible fixes for the problems are considered.

We propose and analyze LowMS, a new rank-based key encapsulation mechanism (KEM). The acronym stands for Loidreau with Multiple Syndromes, since our work combines the cryptosystem of Loidreau (presented at PQCrypto 2017) together with the multiple syndrome approach, that allows to reduce parameters by sending several syndromes with the same error support in one ciphertext.

Our scheme is designed without using ideal structures. Considering cryptosystems without such an ideal structure, like the FrodoKEM cryptosystem, is important since structure allows to compress objects, but gives reductions to specific problems whose security may potentially be weaker than for unstructured problems. For 128 bits of security, we propose parameters with a public key size of 4,6KB and a ciphertext size of 1,1KB. To the best of our knowledge, our scheme is the smallest among all existing unstructured post-quantum lattice or code-based algorithms, when taking into account the sum of the public key size and the ciphertext size. In that sense, our scheme is for instance about 4 times shorter than FrodoKEM.

Our system relies on the hardness of the Rank Support Learning problem, a well-known variant of the Rank Syndrome Decoding problem, and on the problem of indistinguishability of distorted Gabidulin codes, i.e. Gabidulin codes multiplied by an homogeneous matrix of given rank. The latter problem was introduced by Loidreau in his paper.

Event date: 10 July to 14 July 2023
Submission deadline: 26 January 2023
Notification: 10 April 2023

Blockchain Research Labs at Xi'an Jiaotong-Liverpool University is seeking two Ph.D. students to carry out research in funded projects on cryptography, blockchain applications, or privacy computing.

Interested candidates will kindly include their full CV and transcripts in their applications and send to Dr. Jie Zhang Jie.Zhang01@xjtlu.edu.cn. The deadline for applications is January 31st, 2023. We encourage early applications and the review of applications will begin immediately. Only shortlisted applications will be notified.

Closing date for applications:

Contact: Jie.Zhang01@xjtlu.edu.cn

An internship position is available at the MSR Security and Cryptography group in Microsoft (https://careers.microsoft.com/us/en/job/1492332/Research-Intern-Security-and-Cryptography).

We are looking for a student with expertise in hardware design and side-channel analysis, and focus on lattice-based cryptography.

Closing date for applications:

Contact: Interested candidates should submit their applications through the link available at: https://careers.microsoft.com/us/en/job/1492332/Research-Intern-Security-and-Cryptography

Scope: Responsible for driving ongoing developments, and designing our flagship authentication libraries to integrate with leading businesses.

• At least 3 years of experience in Rust
• Interest in security and cryptography
• Comfortable leading the team and taking ownership of the product
• A habit to write clean, well-documented code
• Ability to express yourself fluently in English, spoken and written.

Level: Senior

Location: Remote

Contract: Full time

Visa Sponsorship: N/A

Who are we? Silence Laboratories is a cybersecurity company. We focus on the fusion of cryptography, sensing and design to support a seamless authentication experience. Silence Laboratories (SL) is on a mission to provide business-friendly solutions for distributed digital signing and authentication. We do that through a unique fusion of multi-party computation (MPC) based cryptographic algorithms with threshold signature schemes (TSS) and intelligent multi-modal signal processing. We aim to solve fundamental authentication and account recovery challenges faced by our B2B customers. Our libraries provide businesses with an easy-to-use, proof-based authentication ecosystem. Silence Laboratories is a cybersecurity company. We focus on the fusion of cryptography, sensing and design to support a seamless authentication experience. Silence Laboratories (SL) is on a mission to provide business-friendly solutions for distributed digital signing and authentication. We do that through a unique fusion of multi-party computation (MPC) based cryptographic algorithms with threshold signature schemes (TSS) and intelligent multi-modal signal processing. We aim to solve fundamental authentication and account recovery challenges faced by our B2B customers.

Your Role: Please connect at jay.prakash@silencelaboratories.com or dm at Telegram: @jayece09

Closing date for applications:

Contact: Jay Prakash