International Association
for Cryptologic Research

Side-channel attacks are a fundamental threat to the security of cryptographic implementations. One of the most prominent countermeasures against side-channel attacks is masking, where each intermediate value of the computation is secret shared, thereby concealing the computation's sensitive information. An important security model to study the security of masking schemes is the random probing model, in which the adversary obtains each intermediate value of the computation with some probability $p$. To construct secure masking schemes, an important building block is the refreshing gadget, which updates the randomness of the secret shared intermediate values. Recently, Dziembowski, Faust, and Zebrowski (ASIACRYPT'19) analyzed the security of a simple refreshing gadget by using a new technique called the leakage diagram.

In this work, we follow the approach of Dziembowski et al. and significantly improve its methodology. Concretely, we refine the notion of a leakage diagram via so-called dependency graphs, and show how to use this technique for arbitrary complex circuits via composition results and approximation techniques. To illustrate the power of our new techniques, as a case study, we designed provably secure parallel gadgets for the random probing model, and adapted the ISW multiplication such that all gadgets can be parallelized. Finally, we evaluate concrete security levels, and show how our new methodology can further improve the concrete security level of masking schemes. This results in a compiler provable secure up to a noise level of $ O({1})$ for affine circuits and $ O({1}/{\sqrt{n}})$ in general.

An attribute-based credential system enables users to prove possession of a credential and statements over certified attributes to verifiers in zero-knowledge while maintaining anonymity and unlinkability. In a relational anonymous credential system, users can further prove their relationship to other entities in their social graph, such as position in an organizational hierarchy or friends-of-friends status in an online social network graph, while protecting their own privacy and that of other users involved in the social graph. While traditional anonymous credential schemes make no provisions for privacy-preserving relationship predicates, a relational credential system is more usable, because it can facilitate relationship-based access control with a wide range of predicates and offers strong privacy guarantees for relationship proofs. We propose the first relational credential scheme, based on a new $q$-SDH graph signature scheme and an efficient zero-knowledge proof system for graph predicates. We rigorously prove the security for the proposed scheme and provide a benchmark using Facebook social graphs.

Blockchain has attracted significant attention in recent years due to its potential to revolutionize various industries by providing trustlessness. To comprehensively examine blockchain systems, this article presents both a macro-level overview on the most popular blockchain systems, and a micro-level analysis on a general blockchain framework and its crucial components. The macro-level exploration provides a big picture on the endeavors made by blockchain professionals over the years to enhance the blockchain performance while the micro-level investigation details the blockchain building blocks for deep technology comprehension. More specifically, this article introduces a general modular blockchain analytic framework that decomposes a blockchain system into interacting modules and then examines the major modules to cover the essential blockchain components of network, consensus, and distributed ledger at the micro-level. The framework as well as the modular analysis jointly build a foundation for designing scalable, flexible, and application-adaptive blockchains that can meet diverse requirements. Additionally, this article explores popular technologies that can be integrated with blockchain to expand functionality and highlights major challenges. Such a study provides critical insights to overcome the obstacles in designing novel blockchain systems and facilitates the further development of blockchain as a digital infrastructure to service new applications.

Side-channel attacks against cryptographic implementations are mitigated by the application of masking and hiding countermeasures. Hiding countermeasures attempt to reduce the Signal-to-Noise Ratio of measurements by adding noise or desynchronization effects during the execution of the cryptographic operations. To bypass these protections, attackers adopt signal processing techniques such as pattern alignment, filtering, averaging, or resampling. Convolutional neural networks have shown the ability to reduce the effect of countermeasures without the need for trace preprocessing, especially alignment, due to their shift invariant property. Data augmentation techniques are also considered to improve the regularization capacity of the network, which improves generalization and, consequently, reduces the attack complexity.

In this work, we deploy systematic experiments to investigate the benefits of data augmentation techniques against masked AES implementations when they are also protected with hiding countermeasures. Our results show that, for each countermeasure and dataset, a specific neural network architecture requires a particular data augmentation configuration to achieve significantly improved attack performance. Our results clearly show that data augmentation should be a standard process when targeting datasets with hiding countermeasures in deep learning-based side-channel attacks.

The open-source hardware IP model has recently started gaining popularity in the developer community. This model offers the integrated circuit (IC) developers wider standardization, faster time-to-market and richer platform for research. In addition, open-source hardware conforms to the Kerckhoff’s principle of a publicly-known algorithm and thus helps to enhance security. However, when security comes into consideration, source transparency is only one part of the solution. A complex global IC supply chain stands between the source and the final product. Hence, even if the source is known, the finished product is not guaranteed to match it. In this article, we propose the Open Scan model, in which, in addition to the source code, the IC vendor contributes a library-independent information on scan insertion. With scan information available, the user or a certification lab can perform partial reverse engineering of the IC to verify conformance to the advertised source. Compliance lists of open-source programs, such as of the OpenTitan cryptographic IC, can be amended to include this requirement. The Open Scan model addresses accidental and dishonest deviations from the golden model and partially addresses malicious modifications, known as hardware Trojans. We verify the efficiency of the proposed method in simulation with the Trust-Hub Trojan benchmarks and with several open-source benchmarks, in which we randomly insert modifications.

A linkable ring signature allows a user to sign anonymously on behalf of a group while ensuring that multiple signatures from the same user are detected. Applications such as privacy-preserving e-voting and e-cash can leverage linkable ring signatures to significantly improve privacy and anonymity guarantees. To scale to systems involving large numbers of users, short signatures with fast verification are a must. Concretely efficient ring signatures currently rely on a trusted authority maintaining a master secret, or follow an accumulator-based approach that requires a trusted setup.

In this work, we construct the first linkable ring signature with both logarithmic signature size and verification that does not require any trusted mechanism. Our scheme, which relies on discrete-log type assumptions and bilinear maps, improves upon a recent concise ring signature called DualRing by integrating improved preprocessing arguments to reduce the verification time from linear to logarithmic in the size of the ring. Our ring signature allows signatures to be linked based on what message is signed, ranging from linking signatures on any message to only signatures on the same message.

We provide benchmarks for our scheme and prove its security under standard assumptions. The proposed linkable ring signature is particularly relevant to use cases that require privacy-preserving enforcement of threshold policies in a fully decentralized context, and e-voting.

Oblivious Pseudo-Random Functions (OPRFs) are a central tool for building modern protocols for authentication and distributed computation. For example, OPRFs enable simple login protocols that do not reveal the password to the provider, which helps to mitigate known shortcomings of password-based authentication such as password reuse or mix-up. Reliable treatment of passwords becomes more and more important as we login to a multitude of services with different passwords in our daily life. To ensure the security and privacy of such services in the long term, modern protocols should always consider the possibility of attackers with quantum computers. Therefore, recent research has focused on constructing post-quantum-secure OPRFs. Unfortunately, existing constructions either lack efficiency, or they are based on complex and relatively new cryptographic assumptions, some of which have lately been disproved. In this paper, we revisit the security and the efficiency of the well-known “OPRFs via Garbled Circuits” approach. Such an OPRF is presumably post-quantum-secure and built from well-understood primitives, namely symmetric cryptography and oblivious transfer. We investigate security in the strong Universal Composability model, which guarantees security even when multiple instances are executed in parallel and in conjunction with arbitrary other protocols, which is a realistic scenario in today’s internet. At the same time, it is faster than other current post-quantumsecure OPRFs. Our implementation and benchmarks demonstrate that our proposed OPRF is currently among the best choices if the privacy of the data has to be guaranteed for a long time.

We present new protocols for threshold Schnorr signatures that work in an asynchronous communication setting, providing robustness and optimal resilience. These protocols provide unprecedented performance in terms of communication and computational complexity. In terms of communication complexity, for each signature, a single party must transmit a few dozen group elements and scalars across the network (independent of the size of the signing committee). In terms of computational complexity, the amortized cost for one party to generate a signature is actually less than that of just running the standard Schnorr signing or verification algorithm (at least for moderately sized signing committees, say, up to 100).

For example, we estimate that with a signing committee of 49 parties, at most 16 of which are corrupt, we can generate 50,000 Schnorr signatures per second (assuming each party can dedicate one standard CPU core and 500Mbs of network bandwidth to signing). Importantly, this estimate includes both the cost of an offline precomputation phase (which just churns out message independent "presignatures") and an online signature generation phase. Also, the online signing phase can generate a signature with very little network latency (just one to three rounds, depending on how throughput and latency are balanced).

To achieve this result, we provide two new innovations. One is a new secret sharing protocol (again, asynchronous, robust, optimally resilient) that allows the dealer to securely distribute shares of a large batch of ephemeral secret keys, and to publish the corresponding ephemeral public keys. To achieve better performance, our protocol minimizes public-key operations, and in particular, is based on a novel technique that does not use the traditional technique based on "polynomial commitments". The second innovation is a new algorithm to efficiently combine ephemeral public keys contributed by different parties (some possibly corrupt) into a smaller number of secure ephemeral public keys. This new algorithm is based on a novel construction of a so-called "super-invertible matrix" along with a corresponding highly-efficient algorithm for multiplying this matrix by a vector of group elements.

As protocols for verifiably sharing a secret key with an associated public key and the technology of super-invertible matrices both play a major role in threshold cryptography and multi-party computation, our two new innovations should have applicability well beyond that of threshold Schnorr signatures.

NUS-Singapore is seeking a highly-motivated Postdoc—candidate in the field of cyber security with an emphasis on embedded and hardware security (preferably Physical Unclonable Function (PUF)). Candidates with experience in one or more of the following are preferred: PUF, lightweight cryptography, post-quantum cryptography; designing novel cryptographic primitives and protocols; digital design on ASIC or FPGA platforms using hardware description languages; computer architectures and embedded software; side-channel analysis and fault attacks; and machine learning attacks on PUF especially for security applications. Research topics include but are not limited to Physical Unclonable Function (PUF) secure cryptographic implementations in hardware and software; mechanisms against side-channel analysis and fault attacks security; In the first instance, candidates can discuss applications with Dr Prosanta Gope via email.

Closing date for applications:

Contact: Dr Prosanta Gope

The recent advancements in deep learning have brought about significant changes in various aspects of people's lives. Meanwhile, these rapid developments have raised concerns about the legitimacy of the training process of deep networks. However, to protect the intellectual properties of untrusted AI developers, directly examining the training process by accessing the model parameters and training data by verifiers is often prohibited.

In response to this challenge, we present zkDL, an efficient zero-knowledge proof of deep learning training. At the core of zkDL is zkReLU, a specialized zero-knowledge proof protocol with optimized proving time and proof size for the ReLU activation function, a major obstacle in verifiable training due to its non-arithmetic nature. To integrate zkReLU into the proof system for the entire training process, we devise a novel construction of an arithmetic circuit from neural networks. By leveraging the abundant parallel computation resources, this construction reduces proving time and proof sizes by a factor of the network depth. As a result, zkDL enables the generation of complete and sound proofs, taking less than a minute with a size of less than 20 kB per training step, for a 16-layer neural network with 200M parameters, while ensuring the privacy of data and model parameters.

We give the first construction of a fully black-box round-optimal secure multiparty computation (MPC) protocol in the plain model. Our protocol makes black-box use of a sub-exponentially secure two-message statistical sender private oblivious transfer (SSP-OT), which in turn can be based on (sub-exponential variants of) almost all of the standard cryptographic assumptions known to imply public-key cryptography.

This work focuses on the parallel broadcast primitive, where each of the $n$ parties wish to broadcast their $\ell$-bit input in parallel. We consider the authenticated model with PKI and digital signatures that is secure against $t < n/2$ Byzantine faults under a synchronous network.

We show a generic reduction from parallel broadcast to a new primitive called graded parallel broadcast and a single instance of validated Byzantine agreement. Using our reduction, we obtain parallel broadcast protocols with $O(n^2 \ell + \kappa n^3)$ communication ($\kappa$ denotes a security parameter) and expected constant rounds. Thus, for inputs of size $\ell = \Omega(n)$ bits, our protocols are asymptotically free.

Our graded parallel broadcast uses a novel gradecast protocol with multiple grades with asymptotically optimal communication complexity of $O(n \ell + \kappa n^2)$ for inputs of size $\ell$ bits. We also present a multi-valued validated Byzantine agreement protocol with asymptotically optimal communication complexity of $O(n \ell + \kappa n^2)$ for inputs of size $\ell$ bits in expectation and expected constant rounds. Both of these primitives are of independent interest.

Byzantine fault-tolerant state machine replication (BFT-SMR) replicates a state machine across a set of replicas, and processes requests as a single machine even in the presence of Byzantine faults. Recently, synchronous BFT-SMRs have received tremendous attention due to their simple design and high fault-tolerance threshold.

In this paper, we propose Arena, the first multi-leader synchronous BFT-SMR. Thanks to the synchrony assumption, Arena gains the performance benefit from multi-leader with a much simpler design (compared to other partially synchronous multi-leader designs). Furthermore, it is more robust: ``no progress'' of a leader will not trigger a view-change. Our experimental results show that Arena achieves a peak throughput of up to 7.7$\times$ higher than the state-of-the-art.

We present a new framework for building round-optimal (two-round) $adaptively$ secure MPC. We show that a relatively weak notion of OT that we call $indistinguishability \ OT \ with \ receiver \ oblivious \ sampleability$ (r-iOT) is enough to build two-round, adaptively secure MPC against $malicious$ adversaries in the CRS model. We then show how to construct r-iOT from CDH, LPN, or isogeny-based assumptions that can be viewed as group actions (such as CSIDH and CSI-FiSh). This yields the first constructions of two-round adaptively secure MPC against malicious adversaries from CDH, LPN, or isogeny-based assumptions. We further extend our non-isogeny results to the plain model, achieving (to our knowledge) the first construction of two-round adaptively secure MPC against semi-honest adversaries in the plain model from LPN.

Our results allow us to build a two-round adaptively secure MPC against malicious adversaries from essentially all of the well-studied assumptions in cryptography. In addition, our constructions from isogenies or LPN provide the first post-quantum alternatives to LWE-based constructions for round-optimal adaptively secure MPC. Along the way, we show that r-iOT also implies non-committing encryption(NCE), thereby yielding the first constructions of NCE from isogenies or LPN.

In oblivious finite automata evaluation, one party holds a private automaton, and the other party holds a private string of characters. The objective is to let the parties know whether the string is accepted by the automaton or not, while keeping their inputs secret. The applications include DNA searching, pattern matching, and more. Most of the previous works are based on asymmetric cryptographic primitives, such as homomorphic encryption and oblivious transfer. These primitives are significantly slower than symmetric ones. Moreover, some protocols also require several rounds of interaction. As our main contribution, we propose an oblivious finite automata evaluation protocol via conditional disclosure of secrets (CDS), using one (potentially malicious) outsourcing server. This results in a constant-round protocol, and no heavy asymmetric-key primitives are needed. Our protocol is based on a building block called "an oblivious CDS scheme for deterministic finite automata'' which we also propose in this paper. In addition, we propose a standard CDS scheme for deterministic finite automata as an independent interest.

Secret sharing is a cryptographic primitive that divides a secret into several shares, and allows only some combinations of shares to recover the secret. As it can also be used in secure multi-party computation protocol with outsourcing servers, several variations of secret sharing are devised for this purpose. Most of the existing protocols require the number of computing servers to be determined in advance. However, in some situations we may want the system to be "evolving". We may want to increase the number of servers and strengthen the security guarantee later in order to improve availability and security of the system. Although evolving secret sharing schemes are available, they do not support computing on shares. On the other hand, "homomorphic" secret sharing allows computing on shares with small communication, but they are not evolving. As the contribution of our work, we give the definition of "evolving homomorphic" secret sharing supporting both properties. We propose two schemes, one with hierarchical access structure supporting multiplication, and the other with partially hierarchical access structure supporting computation of low degree polynomials. Comparing to the work with similar functionality of Choudhuri et al. (IACR ePrint 2020), our schemes have smaller communication costs.

This paper proposes $t$-secure homomorphic secret sharing schemes for low degree polynomials. Homomorphic secret sharing is a cryptographic technique to outsource the computation to a set of servers while restricting some subsets of servers from learning the secret inputs. Prior to our work, at Asiacrypt 2018, Lai, Malavolta, and Schröder proposed a $1$-secure scheme for computing polynomial functions. They also alluded to $t$-secure schemes without giving explicit constructions; constructing such schemes would require solving set cover problems, which are generally NP-hard. Moreover, the resulting implicit schemes would require a large number of servers. In this paper, we provide a constructive solution for threshold-$t$ structures by combining homomorphic encryption with the classic secret sharing scheme for general access structure by Ito, Saito, and Nishizeki. Our scheme also quantitatively improves the number of required servers from $O(t^2)$ to $O(t)$, compared to the implicit scheme of Lai et al. We also suggest several ideas for future research directions.

Structure-Aware private set intersection (sa-PSI) is a variant of PSI where Alice's input set $A$ has some publicly known structure, Bob's input $B$ is an unstructured set of points, and Alice learns the intersection $A \cap B$. sa-PSI was recently introduced by Garimella et al. (Crypto 2022), who described a semi-honest protocol with communication that scales with the description size of Alice's set, instead of its cardinality. In this paper, we present the first sa-PSI protocol secure against malicious adversaries.

sa-PSI protocols are built from function secret sharing (FSS) schemes, and the main challenge in our work is ensuring that multiple FSS sharings encode the same structured set. We do so using a cut-and-choose approach. In order to make FSS compatible with cut-and-choose, we introduce a new variant of function secret sharing, called derandomizable FSS (dFSS).

We show how to construct dFSS for union of geometric balls, leading to a malicious-secure sa-PSI protocol where Alice's input is a union of balls. We also improve prior FSS constructions, giving asymptotic improvements to semi-honest sa-PSI.

A universal re-encryption (URE) scheme is a public-key encryption scheme enhanced with an algorithm that on input a ciphertext, outputs another ciphertext which is still a valid encryption of the underlying plaintext. Crucially, such a re-encryption algorithm does not need any key as input, but the ciphertext is guaranteed to be valid under the original key-pair. Therefore, URE schemes lend themselves naturally as building blocks of mixnets: A sender transmits the encryption of a message under the receivers public-key to a mixer, which re-encrypts it, and the receiver later retrieves the re-encrypted ciphertext, which will decrypt successfully to the original message.

Young and Yung (SCN 2018) argued that the original definition of URE by Golle et al. (CT-RSA 2004) was flawed, because it did not consider anonymity of encryption. This motivated them to claim that they finally put URE on solid grounds by presenting four formal security notions which they argued a URE should satisfy.

As our first contribution, we introduce a framework that allows to compactly define and relate security notions as substitutions of systems. Using such framework, as our second contribution we show that Young and Yung's four notions are not minimal, and therefore do not properly capture the essence of a secure URE scheme. We provide three definitions that imply (and are implied by) theirs. Using the constructive cryptography framework, our third contribution is to capture the essence of URE from an application point of view by providing a composable security notion that expresses the ideal use of URE in a mixnet. Finally, we show that the composable notion is implied by our three minimal notions.

The majority of fault-tolerant distributed algorithms are designed assuming a nominal corruption model, in which at most a fraction $f_n$ of parties can be corrupted by the adversary. However, due to the infamous Sybil attack, nominal models are not sufficient to express the trust assumptions in open (i.e., permissionless) settings. Instead, permissionless systems typically operate in a weighted model, where each participant is associated with a weight and the adversary can corrupt a set of parties holding at most a fraction $f_w$ of total weight.

In this paper, we suggest a simple way to transform a large class of protocols designed for the nominal model into the weighted model. To this end, we formalize and solve three novel optimization problems, which we collectively call the weight reduction problems, that allow us to map large real weights into small integer weights while preserving the properties necessary for the correctness of the protocols. In all cases, we manage to keep the sum of the integer weights to be at most linear in the number of parties, resulting in extremely efficient protocols for the weighted model. Moreover, we demonstrate that, on weight distributions that emerge in practice, the sum of the integer weights tends to be far from the theoretical worst-case and, often even smaller than the number of participants.

While, for some protocols, our transformation requires an arbitrarily small reduction in resilience (i.e., $f_w = f_n - \epsilon$), surprisingly, for many important problems we manage to obtain weighted solutions with the same resilience ($f_w = f_n$) as nominal ones. Notable examples include asynchronous consensus, verifiable secret sharing, erasure-coded distributed storage and broadcast protocols. While there are ad-hoc weighted solutions to some of these problems, the protocols yielded by our transformations enjoy all the benefits of nominal solutions, including simplicity, efficiency, and a wider range of possible cryptographic assumptions.