We present several improvements to the framework of differential-linear attacks with a special focus on ARX ciphers. As a demonstration of their impact, we apply them to Chaskey and ChaCha and we are able to significantly improve upon the best attacks published so far.

A Hashed Time Lock Contract (HTLC) is a central concept in cryptocurrencies where some value can be spent either with the preimage of a public hash by one party (Bob) or after a timelock expires by another party (Alice). We present a bribery attack on HTLC's where Bob's hash-protected transaction is censored by Alice's timelocked transaction. Alice incentivizes miners to censor Bob's transaction by leaving almost all her value to miners in general. Miners follow (or refuse) this bribe if their expected payoff is better (or worse). We explore conditions under which this attack is possible, and how HTLC participants can protect themselves against the attack. Applications like Lightning Network payment channels and Cross-Chain Atomic Swaps use HTLC's as building blocks and are vulnerable to this attack. Our proposed solution uses the hashpower share of the weakest known miner to derive parameters that make these applications robust against this bribing attack.

In both hardware and software, masking can represent an effective means of hardening an implementation against side channel attack vectors such as Differential Power Analysis (DPA). Focusing on software, however, the use of masking can present various challenges: specifically, it often 1) requires significant effort to translate any theoretical security properties into practice, and, even then, 2) imposes a significant overhead in terms of efficiency. To address both challenges, this paper explores use of an Instruction Set Extension (ISE) to support masking in software-based implementations of a range of (symmetric) cryptographic kernels including AES: we design, implement, and evaluate such an ISE, using RISC-V as the base ISA. Our ISE-supported first-order masked implementation of AES, for example, is an order of magnitude more efficient than a software-only alternative wrt. both execution latency and memory footprint; this renders it comparable to an unmasked implementation using the same metrics, but also first-order secure.

The Fiat-Shamir transform is a methodology for compiling a (public-coin) interactive proof system for a language $L$ into a non-interactive argument system for $L$. Proving security of the Fiat-Shamir transform in the standard model, especially in the context of succinct arguments, is largely an unsolved problem. The work of Canetti et al. (STOC 2019) proved the security of the Fiat-Shamir transform applied to the Goldwasser-Kalai-Rothblum (STOC 2008) succinct interactive proof system under a very strong ``optimal learning with errors'' assumption. Achieving a similar result under standard assumptions remains an important open question. In this work, we consider the problem of compiling a different succinct interactive proof system: Pietrzak's proof system (ITCS 2019) for the iterated squaring problem. We construct a hash function family (with evaluation time roughly $2^{\lambda^{\epsilon}}$) that guarantees the soundness of Fiat-Shamir for this protocol assuming the sub-exponential ($2^{-n^{1-\epsilon}}$)-hardness of the $n$-dimensional learning with errors problem. (The latter follows from the worst-case $2^{n^{1-\epsilon}}$ hardness of lattice problems.) More generally, we extend the ``bad-challenge function'' methodology of Canetti et al. for proving the soundness of Fiat-Shamir to a class of protocols whose bad-challenge functions are not efficiently computable. As a corollary (following Choudhuri et al., ePrint 2019 and Ephraim et al., EUROCRYPT 2020), we construct hard-on-average problems in the complexity class $\mathbf{CLS}\subset \mathbf{PPAD}$ under the $2^{\lambda^\epsilon}$-hardness of the repeated squaring problem and the $2^{-n^{1-\epsilon}}$-hardness of the learning with errors problem. Under the additional assumption that the repeated squaring problem is ``inherently sequential'', we also obtain a Verifiable Delay Function (Boneh et al., EUROCRYPT 2018) in the standard model. Finally, we give additional PPAD-hardness and VDF instantiations demonstrating a broader tradeoff between the strength of the repeated squaring assumption and the strength of the lattice assumption.

Can Alice and Bob agree on a uniformly random secret key without having any truly secret randomness to begin with? Here we consider a setting where Eve can get partial leakage on the internal state of both Alice and Bob individually before the protocol starts. They then run a protocol using their states without any additional randomness and need to agree on a shared key that looks uniform to Eve, even after observing the leakage and the protocol transcript. We focus on non-interactive (one round) key exchange (NIKE), where Alice and Bob send one message each without waiting for one another. We first consider this problem in the symmetric-key setting, where the states of Alice and Bob include a shared secret as well as individual uniform randomness. However, since Eve gets leakage on these states, Alice and Bob need to perform privacy amplification to derive a fresh secret key from them. Prior solutions require Alice and Bob to sample fresh uniform randomness during the protocol, while in our setting all of their randomness was already part of their individual states a priori and was therefore subject to leakage. We show an information-theoretic solution to this problem using a novel primitive that we call a two-seed extractor, which we in turn construct by drawing a connection to communication-complexity lower-bounds in the number-on-forehead (NOF) model. We then turn to studying this problem in the public-key setting, where the states of Alice and Bob consist of independent uniform randomness. Unfortunately, we give a black-box separation showing that leakage-resilient NIKE in this setting cannot be proven secure via a black-box reduction under any game-based assumption when the leakage is super-logarithmic. This includes virtually all assumptions used in cryptography, and even very strong assumptions such as indistinguishability obfuscation (iO). Nevertheless, we also provide positive results that get around the above separation: - We show that every key exchange protocol (e.g., Diffie-Hellman) is secure when the leakage amount is logarithmic, or potentially even greater if we assume sub-exponential security without leakage. - We notice that the black-box separation does not extend to schemes in the common reference string (CRS) model, or to schemes with preprocessing, where Alice and Bob can individually pre-process their random coins to derive their secret state prior to leakage. We give a solution in the CRS model with preprocessing using bilinear maps. We also give solutions in just the CRS model alone (without preprocessing) or just with preprocessing (without a CRS), using iO and lossy functions.

We study collision-finding against Merkle-Damgård hashing in the random-oracle model by adversaries with an arbitrary $S$-bit auxiliary advice input about the random oracle and $T$ queries. Recent work showed that such adversaries can find collisions (with respect to a random IV) with advantage $\Omega(ST^2/2^n)$, where $n$ is the output length, beating the birthday bound by a factor of $S$. These attacks were shown to be optimal. We observe that the collisions produced are very long, on the order $T$ blocks, which would limit their practical relevance. We prove several results related to improving these attacks to find short collisions. We first exhibit a simple attack for finding $B$-block-long collisions achieving advantage $\tilde{\Omega}(STB/2^n)$. We then study if this attack is optimal. We show that the prior technique based on the bit-fixing model (used for the $ST^2/2^n$ bound) provably cannot reach this bound, and towards a general result we prove there are qualitative jumps in the optimal attacks for finding length $1$, length $2$, and unbounded-length collisions. Namely, the optimal attacks achieve (up to logarithmic factors) order of $(S+T)/2^n$, $ST/2^n$ and $ST^2/2^n$ advantage. We also give an upper bound on the advantage of a restricted class of short-collision finding attacks via a new analysis on the growth of trees in random functional graphs that may be of independent interest.

We observe that all previously known lattice-based blind signature schemes contain subtle flaws in their security proofs (e.g., Rückert, ASIACRYPT '08) or can be attacked (e.g., BLAZE by Alkadri et al., FC '20). Motivated by this, we revisit the problem of constructing blind signatures from standard lattice assumptions. We propose a new three-round lattice-based blind signature scheme whose security can be proved, in the random oracle model, from the standard SIS assumption. Our starting point is a modified version of the (insecure) BLAZE scheme, which itself is based Lyubashevsky's three-round identification scheme combined with a new aborting technique to reduce the correctness error. Our proof builds upon and extends the recent modular framework for blind signatures of Hauck, Kiltz, and Loss (EUROCRYPT '19). It also introduces several new techniques to overcome the additional challenges posed by the correctness error which is inherent to all lattice-based constructions. While our construction is mostly of theoretical interest, we believe it to be an important stepping stone for future works in this area.

We investigate the complexity of problems that admit perfect zero-knowledge interactive protocols and establish new unconditional upper bounds and oracle separation results. We establish our results by investigating certain distribution testing problems: computational problems over high-dimensional distributions represented by succinct Boolean circuits. A relatively less-investigated complexity class SBP emerged as significant in this study. The main results we establish are: 1. A unconditional inclusion that NIPZK is in CoSBP. 2. Construction of a relativized world in which there is a distribution testing problem that lies in NIPZK but not in SBP, thus giving a relativized separation of NIPZK (and hence PZK) from SBP. 3. Construction of a relativized world in which there is a distribution testing problem that lies in PZK but not in CoSBP, thus giving a relativized separation of PZK from CoSBP. These results refine the landscape of perfect zero-knowledge classes in relation to traditional complexity classes.

Recent years have seen a tremendous growth in the interest in secure multiparty computation (MPC) and its applications. While much progress has been made concerning its efficiency, many current, state-of-the-art protocols are vulnerable to Denial of Service attacks, where a cheating party may prevent the honest parties from learning the output of the computation, whilst remaining anonymous. The security model of identifiable abort aims to prevent these attacks, by allowing honest parties to agree upon the identity of a cheating party, who can then be excluded in the future. Several existing MPC protocols offer security with identifiable abort against a dishonest majority of corrupted parties. However, all of these protocols have a round complexity that scales linearly with the depth of the circuit (and are therefore unsuitable for use in high latency networks) or use cryptographic primitives or techniques that have a high computational overhead. In this work, we present the first efficient MPC protocols with identifiable abort in the dishonest majority setting, which run in a constant number of rounds and make only black-box use of cryptographic primitives. Our main construction is built from highly efficient primitives in a careful way to achieve identifiability at a low cost. In particular, we avoid the use of public-key operations outside of a setup phase, incurring a relatively low overhead on top of the fastest currently known constant-round MPC protocols based on garbled circuits. Our construction also avoids the use of adaptively secure primitives and heavy zero-knowledge machinery, which was inherent in previous works. In addition, we show how to upgrade our protocol to achieve public verifiability using a public bulletin board, allowing any external party to verify correctness of the computation or identify a cheating party.

Performing a comprehensive side-channel analysis evaluation of small embedded devices is a process known for its variability and complexity. In real-world experimental setups, the results are largely influenced by a huge amount of parameters that are not easily adjusted without trial and error and are heavily relying on the experience of professional security analysts. In this paper, we advocate the use of an existing statistical methodology called Six Sigma (6σ) for side-channel analysis optimization for this purpose. This well-known methodology is commonly used in other industrial fields, such as production and quality engineering, to reduce the variability of industrial processes. We propose a customized Six Sigma methodology, which enables even a less-experienced security analysis to select optimal values for the different variables that are critical for the side-channel analysis procedure. Moreover, we show how our methodology helps in improving different phases in the side-channel analysis process.

We provide a new definitional framework capturing the multi-user security of encryption schemes and pseudorandom functions in the face of adversaries that can adaptively compromise users' keys. We provide a sequence of results establishing the security of practical symmetric encryption schemes under adaptive compromise in the random oracle or ideal cipher model. The bulk of analysis complexity for adaptive compromise security is relegated to the analysis of lower-level primitives such as pseudorandom functions. We apply our framework to give proofs of security for the BurnBox system for privacy in the face of border searches and the in-use searchable symmetric encryption scheme due to Cash et al. In both cases, prior analyses had bugs that our framework helps avoid.

In this work, we study the question of what set of simple-to-state assumptions suffice for constructing functional encryption and indistinguishability obfuscation (iO), supporting all functions describable by polynomial-size circuits. Our work improves over the state-of-the-art work of Jain, Lin, Matt, and Sahai (Eurocrypt 2019) in multiple dimensions. New Assumption: Previous to our work, all constructions of iO from simple assumptions required novel pseudorandomness generators involving LWE samples and constant-degree polynomials over the integers, evaluated on the error of the LWE samples. In contrast, Boolean pseudorandom generators (PRGs) computable by constant-degree polynomials have been extensively studied since the work of Goldreich (2000). We show how to replace the novel pseudorandom objects over the integers used in previous works, with appropriate Boolean pseudorandom generators with sufficient stretch, when combined with LWE with binary error over suitable parameters. Both binary error LWE and constant degree Goldreich PRGs have been a subject of extensive cryptanalysis since much before our work and thus we back the plausibility of our assumption with security against algorithms studied in context of cryptanalysis of these objects. New Techniques: We introduce a number of new techniques: \begin{itemize} \item We show how to build partially-hiding \emph{public-key} functional encryption, supporting degree-2 functions in the secret part of the message, and arithmetic $\mathsf{NC}^1$ functions over the public part of the message, assuming only standard assumptions over asymmetric pairing groups. \item We construct single-ciphertext and single-secret-key functional encryption for all circuits with long outputs, which has the features of {\em linear} key generation and compact ciphertext, assuming only the LWE assumption. \end{itemize} Simplification: Unlike prior works, our new techniques furthermore let us construct {\em public-key} functional encryption for polynomial-sized circuits directly (without invoking any bootstrapping theorem, nor transformation from secret-key to public key FE), and based only on the {\em polynomial hardness} of underlying assumptions. The functional encryption scheme satisfies a strong notion of efficiency where the size of the ciphertext is independent of the size of the circuit to be computed, and grows only sublinearly in the output size of the circuit and polynomially in the input size and the depth of the circuit. Finally, assuming that the underlying assumptions are subexponentially hard, we can bootstrap this construction to achieve $iO$.

Shor's quantum algorithm, running in quantum computers, can efficiently solve integer factorization problem and discrete logarithm problem in polynomial time. This poses an urgent and serious threat to long-term security with recent accelerated evolution of quantum computing. However, National Institute of Standards and Technology (NIST) plans to release its standard of post-quantum cryptography between 2022 and 2024. It is crucially important to propose an early solution, which is likely secure against quantum attacks and classical attacks, and likely to comply with the future NIST standard. A robust combiner combines a set of 2 or more cryptography primitives into a new primitive of the same type, and guarantees that if anyone of the ingredient primitive is secure, then the resulting primitive is secure. This work proposes the first construction of robust combiner for Key Encapsulation Mechanism (KEM), with optimal amortized performance. From our robust combiner of KEMs, we construct efficient stateful hybrid Key Exchange Protocol (KEP), which is more suitable for two parties who will communicate with each other frequently.

We present functional encryption schemes for attribute-weighted sums, where encryption takes as input $N$ attribute-value pairs $(x_i,z_i)$ where $x_i$ is public and $z_i$ is private; secret keys are associated with arithmetic branching programs $f$, and decryption returns the weighted sum $\sum_{i=1}^N f(x_i) z_i$ while leaking no additional information about the $z_i$'s. Our main construction achieves (1) compact public parameters and key sizes that are independent of $N$ and the secret key can decrypt a ciphertext for any a-prior unbounded $N$; (2) short ciphertexts that grow with $N$ and the size of $z_i$ but not $x_i$; (3) simulation-based security against unbounded collusions; (4) relies on the standard $k$-linear assumption in prime-order bilinear groups.

Reputation systems constitute one of the few workable mechanisms for distributed applications in which users can be made accountable for their actions. By collecting user experiences in reputation profiles, participants are encouraged to interact more with well-behaving peers hence better online behavior is motivated. In this work, we develop a privacy-preserving reputation scheme for collaborative systems such as P2P networks in which peers can represent themselves with different pseudonyms when interacting with others. All these pseudonyms, however, are bound to the same reputation token, allowing honest peers to maintain their good record, even when switching to a new pseudonym, while at the same time preventing malicious peers from making a fresh start. Our system is truly decentralized. Using an append-only distributed ledger such as Bitcoin’s blockchain, we show how participants can make anonymous yet verifiable assertions about their own reputation. In particular, reputation can be demonstrated and updated effectively using efficient zkSNARK proofs. The system maintains soundness, peer-pseudonym unlinkability as well as unlinkability among pseudonyms of the same peer. We formally prove these properties and we evaluate the efficiency of the various operations envisioned in our scheme.

Pairings are a powerful tool to build advanced cryptographic schemes. The most efficient way to instantiate a pairing scheme is through Pairing-Friendly Elliptic Curves. Because a randomly picked elliptic curve will not support an efficient pairing (the embedding degree will usually be too large to make any computation practical), a pairing-friendly curve has to be carefully constructed. This has led to famous curves, e.g. Barreto-Naehrig curves. However, the computation of the discrete logarithm problem on the finite-field side has received much interest and its complexity has recently decreased. Hence the need to propose new curves has emerged. In this work, we give one new curve that is specifically tailored to be fast over the first pairing-group, which is well suited for several cryptographic schemes, such as group signatures and their variants (EPID, anonymous attestation, etc) or accumulators.

We provide a construction of chosen ciphertext secure public-key encryption from (injective) trapdoor functions. Our construction is black box and assumes no special properties (e.g. ``lossy'', ``correlated product secure'') of the trapdoor function.

This article describes recent progress in realizing verifiable state machines, a primitive that enables untrusted services to provide cryptographic proofs that they operate correctly. Applications of this primitive range from proving the correct operation of distributed and concurrent cloud services to reducing blockchain transaction costs by leveraging inexpensive off-chain computation without trust.

The use of deep learning in side-channel analysis has been more and more prominent recently. In particular, Convolution Neural Networks (CNN) are very efficient tools to extract the secret information from side-channel traces. Previous work regarding the use of CNN in side-channel has been mostly proposed through practical results. Zaid et al. have proposed a theoretical methodology in order to better understand the convolutional part of CNN and to understand how to construct an efficient CNN in the side-channel context [ZBHV19]. The proposal of Zaid et al. has been recently questioned by [WAGP20]. However this revisit is based on wrong assumptions and misinterpretations. Hence, many of the claims of [WAGP20] are unfounded regarding [ZBHV19]. In this paper, we clear out the potential misunderstandings brought by [WAGP20] and explain more thoroughly the contributions of [ZBHV19].

We carry out the first provable security analysis of the new FIDO2 protocols, the promising FIDO Alliance's proposal for a standard for passwordless user authentication. Our analysis covers the core components of FIDO2: the W3C’s Web Authentication (WebAuthn) specification and the new Client-to-Authenticator Protocol (CTAP2). Our analysis is modular. For WebAuthn and CTAP2, in turn, we propose appropriate security models that aim to capture their intended security goals and use the models to analyze their security. First, our proof confirms the authentication security of WebAuthn. Then, we show CTAP2 can only be proved secure in a weak sense; meanwhile we identify a series of its design flaws and provide suggestions for improvement. To withstand stronger yet realistic adversaries, we propose a generic protocol called sPACA and prove its strong security; with proper instantiations sPACA is also more efficient than CTAP2. Finally, we analyze the overall security guarantees provided by FIDO2 and WebAuthn+sPACA based on the security of its components. We expect that our models and provable security results will help clarify the security guarantees of the FIDO2 protocols. In addition, we advocate the adoption of our sPACA protocol as a substitute of CTAP2 for both stronger security and better performance.

Time-release cryptography requires problems that take a long time to solve and take just as long even with significant computational resources. While time-release cryptography originated with the seminal paper of Rivest, Shamir and Wagner ('96), it has gained special visibility recently due to new time-release primitives, like verifiable delay functions (VDFs) and sequential proofs of work, and their novel blockchain applications. In spite of this recent progress, security definitions remain inconsistent and fragile, and foundational treatment of these primitives is scarce. Relationships between the various time-release primitives are elusive, with few connections to standard cryptographic assumptions. We systematically address these drawbacks. We define formal notions of sequential functions, the building blocks of time-release cryptography. The new definitions are robust against change of machine models, making them more amenable to complexity theoretic treatment. We demonstrate the equivalence of various types of sequential functions under standard cryptographic assumptions. The time-release primitives in the literature (such as those defined by Bitansky et al. (ITCS '16)) imply that these primitives exist, as well as the converse. However, showing that a given construction is a sequential function is a hard circuit lower bound problem. To our knowledge, no results show that standard cryptographic assumptions imply any sequentiality. For example, repeated squaring over RSA groups is assumed to be sequential, but nothing connects this conjecture to standard hardness assumptions. To circumvent this, we construct a function that we prove is sequential if there exists any sequential function, without needing any specific knowledge of this hypothetical function. Our techniques use universal circuits and fully homomorphic encryption and generalize some of the elegant techniques of the recent work on lattice NIZKs (Canetti et al., STOC '19). Using our reductions and sequential function constructions, we build VDFs and sequential proofs of work from fully homomorphic encryption, incremental verifiable computation, and the existence of a sequential function. Though our constructions are theoretical in nature and not competitive with existing techniques, they are built from much weaker assumptions than known constructions.

Existing approaches to secure multiparty computation (MPC) require all the participants to commit to the entire duration of the protocol. As interest in MPC continues to grow, it is inevitable that there will be a desire to use it to evaluate increasingly complex functionalities on massive datasets, resulting in computations spanning several hours or days. Such scenarios call for a dynamic participation model for MPC where participants have the flexibility to go offline as needed and (re)join when they have available computational resources. Such a model would also democratize access to privacy-preserving computation by facilitating an ``MPC-as-a-service'' paradigm --- the deployment of MPC in volunteer-operated networks that perform computation on behalf of clients. In this work, we initiate the study of ``fluid MPC'', where parties can dynamically join and leave the computation. The minimum commitment required from each participant is referred to as ``fluidity'', measured in the number of rounds of communication that it must stay online. Our contributions are threefold: 1) We provide a formal treatment of fluid MPC, exploring various possible modeling choices. 2) We construct information-theoretic fluid MPC protocols in the honest-majority setting. Our protocols achieve ``maximal fluidity'', meaning that a party can exit the computation after receiving and sending messages in one round. 3) We implement our protocol and test it in multiple network settings.

In an (honest-verifier) zero-knowledge proof of partial knowledge, introduced by Cramer, Damgård and Schoenmakers (CRYPTO 1994), a prover knowing witnesses for some $k$-subset of $n$ given public statements can convince the verifier of this claim without revealing which $k$-subset. The accompanying solution combines $\Sigma$-protocol theory and linear secret sharing, and achieves linear communication complexity for general $k,n$. Especially the ``one-out-of-$n$'' case $k=1$ has seen myriad applications during the last decades, e.g., in electronic voting, ring signatures, and confidential transaction systems in general. In this paper we focus on the discrete logarithm (DL) setting, where the prover claims knowledge of DLs of $k$-out-of-$n$ given elements. Groth and Kohlweiss (EUROCRYPT 2015) have shown how to solve the special case $k=1$ with logarithmic (in $n$) communication, instead of linear as prior work. However, their method takes explicit advantage of $k=1$ and does not generalize to $k>1$ without losing all advantage over prior work. Alternatively, an indirect approach for solving the considered problem is by translating the $k$-out-of-$n$ relation into a circuit and then applying recent advances in communication-efficient circuit ZK. Indeed, for the $k=1$ case this approach has been highly optimized, e.g., in ZCash. Our main contribution is a new, simple honest-verifier zero-knowledge proof protocol for proving knowledge of $k$ out of $n$ DLs with logarithmic communication and for general $k$ and $n$, without requiring any generic circuit ZK machinery. Our solution puts forward a novel extension of the compressed $\Sigma$-protocol theory (CRYPTO 2020), which we then utilize to compress a new $\Sigma$-protocol for proving knowledge of $k$-out-of-$n$ DL's down to logarithmic size. The latter $\Sigma$-protocol is inspired by the CRYPTO 1994 approach, but a careful re-design of the original protocol is necessary for the compression technique to apply. Interestingly, even for $k=1$ and general $n$ our approach improves prior direct approaches as it reduces prover complexity without increasing the communication complexity. Besides the conceptual simplicity, we also identify regimes of practical relevance where our approach achieves asymptotic and concrete improvements, e.g., in proof size and prover complexity, over the generic approach based on circuit-ZK. Finally, we show various extensions and generalizations of our core result. For instance, we extend our protocol to proofs of partial knowledge of Pedersen (vector) commitment openings, and/or to include a proof that the witness satisfies some additional constraint, and we show how to extend our results to non-threshold access structures.

A continuous group key agreement (CGKA) protocol allows a long-lived group of parties to agree on a continuous stream of fresh secret key material. The protocol must support constantly changing group membership, make no assumptions about when, if, or for how long members come online, nor rely on any trusted group managers. Due to sessions' long life-time, CGKA protocols must simultaneously ensure both post-compromise security and forward secrecy (PCFS). That is, current key material should be secure despite both past and future compromises. The work of Alwen et al. (CRYPTO'20), introduced the CGKA primitive and identified it as a crucial component for constructing end-to-end secure group messaging protocols (SGM) (though we believe there are certainly more applications given the fundamental nature of key agreement). The authors analyzed the TreeKEM CGKA, which lies at the heart of the SGM protocol under development by the IETF working group on Messaging Layer Security (MLS). In this work, we continue the study of CGKA as a stand-alone cryptographic primitive. We present $3$ new security notions with increasingly powerful adversaries. Even the weakest of the 3 (passive security) already permits attacks to which all prior constructions (including all variants of TreeKEM) are vulnerable. Going further, the 2 stronger (active security) notions additionally allow the adversary to use parties' exposed states (and full network control) to mount attacks. These are closely related to so-called insider attacks, which involve malicious group members actively deviating from the protocol. Insider attacks present a significant challenge in the study of CGKA (and SGM). Indeed, we believe ours to be the first security notions (and constructions) to formulate meaningful guarantees (e.g. PCFS) against such powerful adversaries. They are also the first composable security notions for CGKA of any type at all. In terms of constructions, for each of the 3 security notions we provide a new CGKA scheme enjoying sub-linear (potentially even logarithmic) communication complexity in the number of group members. We prove each scheme optimally secure, in the sense that the only security violations possible are those necessarily implied by correctness.

Reverse engineering of integrated circuits, i.e., understanding the internals of IC, is required for many benign and malicious applications. Examples of the former are detection of patent infringements, hardware Trojans or IP-theft, as well as interface recovery and defect analysis, while malicious applications include IP-theft and finding insertion points for hardware Trojans. However, regardless of the application, the reverse engineer initially starts with a large unstructured netlist, forming an incomprehensible sea of gates. This work presents DANA, a generic, technology-agnostic, and fully automated dataflow analysis methodology for flattened gate-level netlists. By analyzing the flow of data between individual FF, DANA recovers high-level registers. The key idea behind DANA is to combine independent metrics based on structural and control information with a powerful automated architecture. Notably, DANA works without any thresholds, scenario-dependent parameters, or other "magic" values that the user must choose. We evaluate DANA on nine modern hardware designs, ranging from cryptographic co-processors, over CPUs, to the OpenTitan, a state-of-the-art SOC, which is maintained by the lowRISC initiative with supporting industry partners like Google and Western Digital. Our results demonstrate almost perfect recovery of registers for all case studies, regardless whether they were synthesized as FPGA or ASIC netlists. Furthermore, we explore two applications for dataflow analysis: we show that the raw output of DANA often already allows to identify crucial components and high-level architecture features and also demonstrate its applicability for detecting simple hardware Trojans. Hence, DANA can be applied universally as the first step when investigating unknown netlists and provides major guidance for human analysts by structuring and condensing the otherwise incomprehensible sea of gates. Our implementation of DANA and all synthesized netlists are available as open source on GitHub.

Hardware obfuscation is widely used in practice to counteract reverse engineering. In recent years, low-level obfuscation via camouflaged gates has been increasingly discussed in the scientific community and industry. In contrast to classical high-level obfuscation, such gates result in recovery of an erroneous netlist. This technology has so far been regarded as a purely defensive tool. We show that low-level obfuscation is in fact a double-edged sword that can also enable stealthy malicious functionalities. In this work, we present Doppelganger, the first generic design-level obfuscation technique that is based on low-level camouflaging. Doppelganger obstructs central control modules of digital designs, e.g., FSMs or bus controllers, resulting in two different design functionalities: an apparent one that is recovered during reverse engineering and the actual one that is executed during operation. Notably, both functionalities are under the designer's control. In two case studies, we apply Doppelganger to a universal cryptographic coprocessor. First, we show the defensive capabilities by presenting the reverse engineer with a different mode of operation than the one that is actually executed. Then, for the first time, we demonstrate the considerable threat potential of low-level obfuscation. We show how an invisible, remotely exploitable key-leakage Trojan can be injected into the same cryptographic coprocessor just through obfuscation. In both applications of Doppelganger, the resulting design size is indistinguishable from that of an unobfuscated design, depending on the choice of encodings.

Recently, Huang et al. proposed a concept of public key encryption with filtered equality test (PKE-FET) that allows a tester who has a warrant for the selected message set to check equality of messages in ciphertexts that belong to that set (Journal of Computer and System Sciences, 2017). They also presented an instantiation of the PKE-FET that was asserted to achieve the indistinguishability against adaptive chosen ciphertext attacks (IND-CCA2) in the standard model. In this note, we show that Huang et al.’s instantiation does not achieve the IND-CCA2 security by presenting a simple adaptive chosen ciphertext attack.

Privacy protection and scalability are significant issues with blockchain. We propose an anonymous probabilistic payment under the general functionality for solving them. We consider the situation that several payers pay several payees through a tumbler. We have mediated the tumbler of the payment channel hub between payers and payees. Unlinkability means that the link, which payer pays which payee via the tumbler, is broken. A cryptographic puzzle plays a role in controlling the intermediation and execution of transactions. Masking the puzzle enables the payer and the payee to unlink their payments. The overview of the proposed protocol is similar to TumbleBit (NDSS 2017). We confirm the protocol realizes the ideal functionalities discussed in TumbleBit. The functionality required for our proposal is the hashed time lock contract that various cryptocurrencies use. This request is general, not restricted to any particular cryptocurrency. Our proposal includes a probabilistic payment. In probabilistic payment, one pays an ordinary mount with a certain probability. One pays a small amount as an expected value. One can run fewer transactions than a deterministic payment. It contributes scalability. We introduce a novel fractional oblivious transfer for probabilistic payment. We call it the ring fractional oblivious transfer (RFOT). RFOT is based on the ring learning with errors (RLWE) encryption. Our trick is based on the fact that an element of the ring is indistinguishable from the circular shifted element. We confirm that RFOT holds the properties of fractional hiding and binding presented in the DAM scheme (Eurocrypt 2017).

In modern distributed systems, an adversary’s limitations when corrupting subsets of servers may not necessarily be based on threshold constraints, but rather based on other technical or organizational characteristics in the systems. This means that the corruption patterns (and thus protection guarantees) are not based on the adversary being limited by a threshold, but on the adversary being limited by other constraints, in particular by what is known as a General Adversary Structure (GAS). We consider efficient secure multiparty computation (MPC) under such dynamically-changing GAS settings. During these changes, one desires to protect against and during corruption profile change, which renders some (secret sharing-based) encoding schemes underlying the MPC protocol more efficient than others when operating with the (currently) considered GAS. One of our contributions is a set of novel protocols to efficiently and securely convert back and forth between different MPC schemes for GAS; this process is often called share conversion. Specifically, we consider two MPC schemes, one based on additive secret sharing and the other based on Monotone Span Programs (MSP). The ability to efficiently convert between the secret sharing representations of these MPC schemes enables us to construct the first communication-efficient structure-adaptive proactive MPC protocol for dynamic GAS settings. By structure-adaptive, we mean that the choice of the MPC protocol to execute in future rounds after the GAS is changed (as specified by an administrative entity) is chosen to ensure communication-efficiency (the typical bottleneck in MPC). Furthermore, since such secure collaborative computing may be long-lived, we consider the mobile adversary setting, often called the proactive security setting. As our second contribution, we construct communication-efficient MPC protocols that can adapt to the proactive security setting. Proactive security assumes that at each (well defined) period of time the adversary corrupts different parties and over time may visit the entire system and corrupt all parties, provided that in each period it controls groups obeying the GAS constraints. In our protocol, the shares can be refreshed, meaning that parties receive new shares reconstructing the same secret, and some parties who lost their shares because of the reboot/resetting can recover their shares. As our third contribution, we consider another aspect of global long-term computations, namely, that of the dynamic groups. It is worth pointing out that such a setting with dynamic groups and GAS was not dealt with in existing literature on (proactive) MPC. In dynamic group settings, parties can be added and eliminated from the computation, under different GAS restrictions. We extend our protocols to this additional dynamic group settings defined by different GAS.

Cryptography is one of the basic phenomena of security systems. However, some of the widely used public key cryptography algorithms can be broken by using quantum computers. Therefore, many post-quantum cryptography algorithms are proposed in recent years to handle this issue. NTRU is one of the most important of these quantum-safe algorithms. Besides the importance of cryptography algorithms, the architecture where they are implemented is also essential. In this study, we developed an NTRU public key cryptosystem application and designed several processors to compare them in many aspects. We address two dierent architectures in this work. The RISC-V is chosen as it is the most lately version of classical RISC architecture. As competitor to this, we preferred transport triggered architecture (TTA) which oers high level customization and scalability. Details of all dierent implementations and the test results obtained with them are shared and discussed.

In digital world cryptographic algorithms protect sensitive information from intruder during communication. True random number generation is used for Cryptography algorithms as key value encryption and decryption process. To develop unbreakable algorithms key as one important parameter for Cryptography .We proposed DNA based True random number generation.DNA is deoxyribonucleic acid chemical molecule present in all living cells. DNA molecule consists of 4 nucleotides A-adenine,T-Thymine,G-Guanine and CCytosine. DNA molecules have uniqueness properties like Each person in the world distinguish based on DNA sequences and genes. The proposed algorithm pass NIST SP 800-22 test suite for DNA based true random number generation with highest Entropy,FFT,Block Frequency and Linear Complexity.

Gimli is a family of cryptographic primitives (both a hash function and an AEAD scheme) that has been selected for the second round of the NIST competition for standardizing new lightweight designs. The candidate Gimli is based on the permutation Gimli, which was presented at CHES 2017. In this paper, we study the security of both the permutation and the constructions that are based on it. We exploit the slow diffusion in Gimli and its internal symmetries to build, for the first time, a distinguisher on the full permutation of complexity $2^{64}$. We also provide a practical distinguisher on 23 out of the full 24 rounds of Gimli that has been implemented. Next, we give (full state) collision and semi-free-start collision attacks on Gimli-Hash, reaching respectively up to 12 and 18 rounds. On the practical side, we compute a collision on 8-round Gimli-Hash. In the quantum setting, these attacks reach 2 more rounds. Finally, we perform the first study of linear trails in Gimli, and we find a linear distinguisher on the full permutation.

In the implementation of post-quantum primitives, it is well known that all computations that handle secret information need to be implemented to run in constant time. Using the Fujisaki-Okamoto transformation or any of its different variants, a CPA-secure primitive can be converted into an IND-CCA secure KEM. In this paper we show that although the transformation does not handle secret information apart from calls to the CPA-secure primitive, it has to be implemented in constant time. Namely, if the ciphertext comparison step in the transformation is leaking side-channel information, we can launch a key-recovery attack. Several proposed schemes in round 2 of the NIST post-quantum standardization project are susceptible to the proposed attack and we develop and show the details of the attack on one of them, being FrodoKEM. It is implemented on the reference implementation of FrodoKEM, which is claimed to be secure against all timing attacks. Experiments show that the attack code is able to extract the secret key for all security levels using about \(2^{30}\) decapsulation calls.

Side-channel analysis and fault-injection attacks are known as serious threats to cryptographic hardware implementations and the combined protection against both is currently an open line of research. A promising countermeasure with considerable implementation overhead appears to be a mix of first-order secure Threshold Implementations and linear Error-Correcting Codes. In this paper we employ for the first time the inherent structure of non-systematic codes as fault countermeasure which dynamically mutates the applied generator matrices to achieve a higher-order side-channel and fault-protected design. As a case study, we apply our scheme to the PRESENT block cipher that do not show any higher-order side-channel leakage after measuring 150 million power traces.

Loyalty programs in the form of punch cards that can be redeemed for benefits have long been a ubiquitous element of the consumer landscape. However, their increasingly popular digital equivalents, while providing more convenience and better bookkeeping, pose a considerable privacy risk. This paper introduces a privacy-preserving punch card protocol that allows firms to digitize their loyalty programs without forcing customers to submit to corporate surveillance. We also present a number of extensions that allow our scheme to provide other privacy-preserving customer loyalty features. Compared to the best prior work, we achieve a $14\times$ reduction in the computation and a $11\times$ reduction in the communication required to perform a ``hole punch,'' a $55\times$ reduction in the communication required to redeem a punch card, and a $128\times$ reduction in the computation time required to redeem a card. Much of our performance improvement can be attributed to removing the reliance on pairings or range proofs present in prior work, which has only addressed this problem in the context of more general loyalty systems. By tailoring our scheme to punch cards and related loyalty systems, we demonstrate that we can reduce communication and computation costs by orders of magnitude.

Protocols for secure Multi-Party Computation (MPC) can be classified according to the underlying communication model. Two prominent communication models considered in the literature are the synchronous and asynchronous models, which considerably differ in terms of the achievable security guarantees. Synchronous MPC protocols can achieve the optimal corruption threshold $n/2$ and allow every party to give input, but become completely insecure when synchrony assumptions are violated. On the other hand, asynchronous MPC protocols remain secure under arbitrary network conditions, but can tolerate only $n/3$ corruptions and parties with slow connections unavoidably cannot give input. A natural question is whether there exists a protocol for MPC that can tolerate up to $t_s < n/2$ corruptions under a synchronous network and $t_a < n/3$ corruptions even when the network is asynchronous. We answer this question by showing tight feasibility and impossibility results. More specifically, we show that such a protocol exists if and only if $t_a + 2t_s < n$ and the number of inputs taken into account under an asynchronous network is at most $n-t_s$.

Timed-release encryption (TRE) makes it possible to send information ``into the future'' such that a pre-determined amount of time needs to pass before the information can be decrypted, which has found numerous applications. The most prominent construction is based on sequential squaring in RSA groups, proposed by Rivest et al. in 1996. Malavolta and Thyagarajan (CRYPTO'19) recently proposed an interesting variant of TRE called homomorphic time-lock puzzles (HTLPs). Here one considers multiple puzzles which can be independently generated by different entities. One can homomorphically evaluate a circuit over these puzzles to obtain a new puzzle. Solving this new puzzle yields the output of a circuit evaluated on all solutions of the original puzzles. While this is an interesting concept and enables various new applications, for constructions under standard assumptions one has to rely on sequential squaring. We observe that viewing HTLPs as homomorphic TRE gives rise to a simple generic construction that avoids the homomorphic evaluation on the puzzles and thus the restriction of relying on sequential squaring. It can be instantiated based on any TLP, such as those based on one-way functions and the LWE assumption (via randomized encodings), while providing essentially the same functionality for applications. Moreover, it overcomes the limitation of the approach of Malavolta and Thyagarajan that, despite the homomorphism, one puzzle needs to be solved per decrypted ciphertext. Hence, we obtain a ``solve one, get many for free'' property for an arbitrary amount of encrypted data, as we only need to solve a single puzzle independent of the number of ciphertexts. In addition, we introduce the notion of incremental TLPs as a particularly useful generalization of TLPs, which yields particularly practical (homomorphic) TRE schemes. Finally, we demonstrate various applications by firstly showcasing their cryptographic application to construct dual variants of timed-release functional encryption and also show that we can instantiate previous applications of HTLPs in a simpler and more efficient way.

In this article, we propose GIFT-COFB, an Authenticated Encryption with Associated Data (AEAD) scheme, based on the GIFT lightweight block cipher and the COFB lightweight AEAD operating mode. We explain how these two primitives can fit together and the various design adjustments possible for performance and security improvements. We show that our design provides excellent performances in all constrained scenarios, hardware or software, while being based on a provably-secure mode and a well analysed block cipher.

Today's most compact zero-knowledge arguments are based on the hardness of the discrete logarithm problem and related classical assumptions. If one is interested in quantum-safe solutions, then all of the known techniques stem from the PCP-based framework of Kilian (STOC 92) which can be instantiated based on the hardness of any collision-resistant hash function. Both approaches produce asymptotically logarithmic sized arguments but, by exploiting extra algebraic structure, the discrete logarithm arguments are a few orders of magnitude more compact in practice than the generic constructions. In this work, we present the first (poly)-logarithmic, potentially post-quantum zero-knowledge arguments that deviate from the PCP approach. At the core of succinct zero-knowledge proofs are succinct commitment schemes (in which the commitment and the opening proof are sub-linear in the message size), and we propose two such constructions based on the hardness of the (Ring)-Short Integer Solution (Ring-SIS) problem, each having certain trade-offs. For commitments to $N$ secret values, the communication complexity of our first scheme is $\tilde{O}(N^{1/c})$ for any positive integer $c$, and $O(\log^2 N)$ for the second. Both of these are a significant theoretical improvement over the previously best lattice construction by Bootle et al. (CRYPTO 2018) which gave $O(\sqrt{N})$-sized proofs.

As both notions employ the same key-evolution paradigm, Bellare \emph{et al.} (CANS 2017) study combining forward security with leakage resilience. The idea is for forward security to serve as a hedge in case at some point the full key gets exposed from the leakage. In particular, Bellare \emph{et al.} combine forward security with \emph{continual} leakage resilience, dubbed FS+CL. Our first result improves on Bellare \emph{et al.}'s FS+CL secure PKE scheme by building one from any continuous leakage-resilient binary-tree encryption (BTE) scheme; in contrast, Bellare \emph{et al.} require extractable witness encryption. Our construction also preserves leakage rate of the underlying BTE scheme and hence, in combination with existing CL-secure BTE, yields the first FS+CL secure encryption scheme with optimal leakage rate from standard assumptions. \ind We next explore combining forward security with other notions of leakage resilience. Indeed, as argued by Dziembowski \emph{et al.} (CRYPTO 2011), it is desirable to have a \emph{deterministic} key-update procedure, which FS+CL does not allow for arguably pathological reasons. To address this, we combine forward security with \emph{entropy-bounded} leakage (FS+EBL). We construct FS+EBL non-interactive key exchange (NIKE) with deterministic key update based on indistinguishability obfuscation ($\iO$), and DDH or LWE. To make the public keys constant size, we rely on the Superfluous Padding Assumption (SuPA) of Brzuska and Mittelbach (ePrint 2015) \emph{without} auxiliary information, making it more plausible. SuPA notwithstanding, the scheme is also the first FS-secure NIKE from $\iO$ rather than multilinear maps. We advocate a future research agenda that uses FS+EBL as a hedge for FS+CL, whereby a scheme achieves the latter if key-update randomness is good and the former if not.

We present a new short zero-knowledge argument for the range proof and the arithmetic circuits without a trusted setup. In particular, the proof size of our protocol is the shortest of the category of proof systems with a trustless setup. More concretely, when proving a committed value is a positive integer less than 64 bits, except for negligible error in the $128$-bit security parameter, the proof size is $576$ byte long, which is of $85.7\%$ size of the previous shortest one due to Bünz et al.~(Bulletproofs, IEEE Security and Privacy 2018), while computational overheads in both proof generation and verification are comparable with those of Bulletproofs, respectively. Bulletproofs is established as one of important privacy enhancing technologies for distributed ledger, due to its trustless feature and short proof size. In particular, it has been implemented and optimized in various programming languages for practical usages by independent entities since it proposed. The essence of Bulletproofs is based on the logarithmic inner product argument with no zero-knowledge. In this paper, we revisit Bulletproofs from the viewpoint of the first sublinear zero-knowledge argument for linear algebra due to Groth~(CRYPTO 2009) and then propose Bulletproofs+, an improved variety of Bulletproofs. The main ingredient of our proposal is the zero-knowledge weighted inner product argument (zk-WIP) to which we reduce both the range proof and the arithmetic circuit proof. The benefit of reducing to the zk-WIP is a minimal transmission cost during the reduction process. Note the zk-WIP has all nice features of the inner product argument such as an aggregating range proof and batch verification.

We provide a simple and complete proof of the famous Pi&#8853;Pj Theorem in the particular case where &#958;max=2. This Theorem gives a lower bound for the number of solutions of simple linear systems of equations in the case where all the variables have to be pairwise distinct. Such systems often occur in cryptographic proofs of security, and this particular Theorem can be used to prove that the function x&#8614;P(0||x)&#8853;P(1||x) is an optimally secure pseudorandom function when P is a uniformly random permutation.

The candidates for the NIST Post-Quantum Cryptography standardization have undergone extensive studies on efficiency and theoretical security, but research on their side-channel security is largely lacking. This remains a considerable obstacle for their real-world deployment, where side-channel security can be a critical requirement. This work describes a side-channel resistant instance of Saber, one of the lattice-based candidates, using masking as a countermeasure. Saber proves to be very efficient to mask due to two specific design choices: power-of-two moduli, and limited noise sampling of learning with rounding. A major challenge in masking lattice-based cryptosystems is the integration of bit-wise operations with arithmetic masking, requiring algorithms to securely convert between masked representations. The described design includes a novel primitive for masked logical shifting on arithmetic shares, as well as adapts an existing masked binomial sampler for Saber. An implementation is provided for an ARM Cortex-M4 microcontroller, and its side-channel resistance is experimentally demonstrated. The masked implementation features a 2.5x overhead factor, significantly lower than the 5.7x previously reported for a masked variant of NewHope. Masked key decapsulation requires less than 3,000,000 cycles on the Cortex-M4 and consumes less than 12kB of dynamic memory, making it suitable for deployment in embedded platforms. We have made our implementation available at https://github.com/KULeuven-COSIC/SABER-masking.

Database management systems (DBMS) are one of cloud services with great interests in industry and business. In such services, since there is no trust in the cloud servers, the databases are encrypted prior to outsourcing. One of the most challenging issues in designing these services is supporting SQL join queries on the encrypted database. The multi-adjustable join scheme (M-Adjoin) [Khazaei-Rafiee 2019], an extension of Adjoin [Popa-Zeldovich 2012 and Mironov-Segev-Shahaf 2017], is a symmetric-key primitive that supports the join queries for a list of column labels on an encrypted database. In previous works, the following security notions were introduced for Adjoin and M-Adjoin schemes: 3Partition, M3Partition and M3P k , for every integer k . Additionally, simulation-based and indistinguishability-based security notions have been defined by Mironov et al. for Adjoin scheme. In this paper, we extend their results to M-Adjoin and study the relations between all security notions for M-Adjoin. Some non-trivial relations are proved which resolve some open problems raised by [Mironov-Segev-Shahaf 2017].

PMAC is a rate-1, parallelizable, block-cipher-based message authentication code (MAC), proposed by Black and Rogaway (EUROCRYPT 2002). Improving the security bound is a main research topic for PMAC. In particular, showing a tight bound is the primary goal of the research, since Luykx et al.'s paper (EUROCRYPT 2016). Regarding the pseudo-random-function (PRF) security of PMAC, a collision of the hash function, or the difference between a random permutation and a random function offers the lower bound $\Omega(q^2/2^n)$ for $q$ queries and the block cipher size $n$. Regarding the MAC security (unforgeability), a hash collision for MAC queries, or guessing a tag offers the lower bound $\Omega(q_m^2/2^n + q_v/2^n)$ for $q_m$ MAC queries and $q_v$ verification queries (forgery attempts). The tight upper bound of the PRF-security $O(q^2/2^n)$ of PMAC was given by Gaž et el. (ToSC 2017, Issue 1), but their proof requires a 4-wise independent masking scheme that uses 4 $n$-bit random values. Open problems from their work are: (1) find a masking scheme with three or less random values with which PMAC has the tight upper bound for PRF-security; (2) find a masking scheme with which PMAC has the tight upper bound for MAC-security. In this paper, we consider PMAC with three powering-up masks that uses three random values for the masking scheme. We show that the PMAC has the tight upper bound $O(q^2/2^n)$ for PRF-security, which answers the open problem (1), and the tight upper bound $O(q_m^2/2^n + q_v/2^n)$ for MAC-security, which answers the open problem (2). Note that these results deal with two-key PMAC, thus showing tight upper bounds of PMACs with single-key and/or with two (or one) powering-up masks are open problems.

Time-lock puzzles---problems whose solution requires some amount of sequential effort---have recently received increased interest (e.g., in the context of verifiable delay functions). Most constructions rely on the sequential-squaring conjecture that computing $g^{2^T} \bmod N$ for a uniform $g$ requires at least $T$ (sequential) steps. We study the security of time-lock primitives from two perspectives: - We give the first hardness result about the sequential-squaring conjecture in a non-generic model. Namely, in a quantitative version of the algebraic group model (AGM) that we call the strong AGM, we show that speeding up sequential squaring is as hard as factoring $N$. - We then focus on timed commitments, one of the most important primitives that can be obtained from time-lock puzzles. We extend existing security definitions to settings that may arise when using timed commitments in higher-level protocols, and give the first construction of non-malleable timed commitments. As a building block of independent interest, we also define (and give constructions for) a related primitive called timed public-key encryption.

We present a new protocol for two-party private set intersection (PSI) with semi-honest security in the plain model and one-sided malicious security in the random oracle model. Our protocol achieves a better balance between computation and communication than existing PSI protocols. Specifically, our protocol is the fastest in networks with moderate bandwidth (e.g., 30 - 100 Mbps). Considering the monetary cost (proposed by Pinkas et al. in CRYPTO 2019) to run the protocol on a cloud computing service, our protocol also compares favorably. Underlying our PSI protocol is a new lightweight multi-point oblivious pesudorandom function (OPRF) protocol based on oblivious transfer (OT) extension. We believe this new protocol may be of independent interest.

We present our discovery of a group of side-channel vulnerabilities in implementations of the ECDSA signature algorithm in a widely used Atmel AT90SC FIPS 140-2 certified smartcard chip and five cryptographic libraries (libgcrypt, wolfSSL, MatrixSSL, SunEC/OpenJDK/Oracle JDK, Crypto++). Vulnerable implementations leak the bit-length of the scalar used in scalar multiplication via timing. Using leaked bit-length, we mount a lattice attack on a 256-bit curve, after observing enough signing operations. We propose two new methods to recover the full private key requiring just 500 signatures for simulated leakage data, 1200 for real cryptographic library data, and 2100 for smartcard data. The number of signatures needed for a successful attack depends on the chosen method and its parameters as well as on the noise profile, influenced by the type of leakage and used computation platform. We use the set of vulnerabilities reported in this paper, together with the recently published TPM-FAIL vulnerability as a basis for real-world benchmark datasets to systematically compare our newly proposed methods and all previously published applicable lattice-based key recovery methods. The resulting exhaustive comparison highlights the methods' sensitivity to its proper parametrization and demonstrates that our methods are more efficient in most cases. For the TPM-FAIL dataset, we decreased the number of required signatures from approximately 40 000 to mere 900.

An increasing number of lightweight cryptographic primitives have been published recently. Some of these proposals are ARX primitives, which have shown a great performance in software. Rotational-XOR cryptanalysis is a statistical technique to attack ARX primitives. In this paper, a computer tool to speed up and make easier the security evaluation of ARX block ciphers against rotational-XOR cryptanalysis is shown. Our tool takes a Python implementation of an ARX block cipher and automatically finds an optimal rotational-XOR characteristic. Compared to most of the automated tools, which only support a small set of primitives, our tool supports any ARX block cipher and it is executed with a simple shell command.

We consider the theoretically-sound selection of cryptographic parameters, such as the size of algebraic groups or RSA keys, for TLS 1.3 in practice. While prior works gave security proofs for TLS 1.3, their security loss is quadratic in the total number of sessions across all users, which due to the pervasive use of TLS is huge. Therefore, in order to deploy TLS 1.3 in a theoretically-sound way, it would be necessary to compensate this loss with unreasonably large parameters that would be infeasible for practical use at large scale. Hence, while these previous works show that in principle the design of TLS 1.3 is secure in an asymptotic sense, they do not yet provide any useful concrete security guarantees for real-world parameters used in practice. In this work, we provide a new security proof for the cryptographic core of TLS 1.3 in the random oracle model, which reduces the security of TLS 1.3 tightly (that is, with constant security loss) to the (multi-user) security of its building blocks. For some building blocks, such as the symmetric record layer encryption scheme, we can then rely on prior work to establish tight security. For others, such as the RSA-PSS digital signature scheme currently used in TLS 1.3, we obtain at least a linear loss in the number of users, independent of the number of sessions, which is much easier to compensate with reasonable parameters. Our work also shows that by replacing the RSA-PSS scheme with a tightly-secure scheme (e. g., in a future TLS version), one can obtain the first fully tightly-secure TLS protocol. Our results enable a theoretically-sound selection of parameters for TLS 1.3, even in large-scale settings with many users and sessions per user.

Secret sharing enables a dealer to split a secret into a set of shares, in such a way that certain authorized subsets of share holders can reconstruct the secret, whereas all unauthorized subsets cannot. Non-malleable secret sharing (Goyal and Kumar, STOC 2018) additionally requires that, even if the shares have been tampered with, the reconstructed secret is either the original or a completely unrelated one. In this work, we construct non-malleable secret sharing tolerating $p$-time {\em joint-tampering} attacks in the plain model (in the computational setting), where the latter means that, for any $p>0$ fixed {\em a priori}, the attacker can tamper with the same target secret sharing up to $p$ times. In particular, assuming one-to-one one-way functions, we obtain: - A secret sharing scheme for threshold access structures which tolerates joint $p$-time tampering with subsets of the shares of maximal size ({\em i.e.}, matching the privacy threshold of the scheme). This holds in a model where the attacker commits to a partition of the shares into non-overlapping subsets, and keeps tampering jointly with the shares within such a partition (so-called {\em selective partitioning}). - A secret sharing scheme for general access structures which tolerates joint $p$-time tampering with subsets of the shares of size $O(\sqrt{\log n})$, where $n$ is the number of parties. This holds in a stronger model where the attacker is allowed to adaptively change the partition within each tampering query, under the restriction that once a subset of the shares has been tampered with jointly, that subset is always either tampered jointly or not modified by other tampering queries (so-called {\em semi-adaptive partitioning}). At the heart of our result for selective partitioning lies a new technique showing that every one-time {\em statistically} non-malleable secret sharing against joint tampering is in fact {\em leakage-resilient} non-malleable ({\em i.e.},\ the attacker can leak jointly from the shares prior to tampering). We believe this may be of independent interest, and in fact we show it implies lower bounds on the share size and randomness complexity of statistically non-malleable secret sharing against {\em independent} tampering.

Accumulators provide compact representations of large sets and compact membership witnesses. Besides constant-size witnesses, public-key accumulators provide efficient updates of both the accumulator itself and the witness. However, bilinear group based accumulators come with drawbacks: they require a trusted setup and their performance is not practical for real-world applications with large sets. In this paper, we introduce multi-party public-key accumulators dubbed dynamic (threshold) secret-shared accumulators. We present an instantiation using bilinear groups having access to more efficient witness generation and update algorithms that utilize the shares of the secret trapdoors sampled by the parties generating the public parameters. Specifically, for the q-SDH-based accumulators, we provide a maliciously-secure variant sped up by a secure multi-party computation (MPC) protocol (IMACC'19) built on top of SPDZ and a maliciously secure threshold variant built with Shamir secret sharing. For these schemes, a performant proof-of-concept implementation is provided, which substantiates the practicability of public-key accumulators in this setting. We explore applications of dynamic (threshold) secret-shared accumulators to revocation schemes of group signatures and credentials system. In particular, we consider it as part of Sovrin's system for anonymous credentials where credentials are issued by the foundation of trusted nodes.

Pedersen commitments have been adopted by several cryptocurrencies for hiding transaction amounts. While Pedersen commitments are perfectly hiding in isolation, the cryptocurrency transaction rules can reveal relationships between the amounts hidden in the commitments involved in the transaction. Such relationships can be combined with the public coin creation schedule to provide upper bounds on the number of coins in a commitment. In this paper, we consider the Grin cryptocurrency and derive upper bounds on the number of coins which can be present in regular transaction outputs. In a March 2020 snapshot of the Grin blockchain, we find that out of the 110,149 unspent regular transaction outputs 983 of them have less than 1800 grin (number of coins typically minted in half an hour) stored in them. On the other hand, 95% of the unspent regular transaction outputs in the snapshot have an upper bound which is at least 90% of the total Grin supply at their respective block heights. We conclude that while our method does not violate the confidentiality of the amounts in most of the outputs on the Grin blockchain, the amounts in some outputs can be estimated to be in a narrow range.

This paper exposes a new vulnerability and introducesa corresponding attack, the NoneXistent Name ServerAttack (NXNSAttack), that disrupts and may paralyzethe DNS system making it difficult or impossible for In-ternet users to access websites, web e-mail, online videochats, or any other online resource. The NXNSAttackgenerates a storm of packets between DNS resolvers andDNS authoritative name servers. The storm is producedby the response of resolvers to unrestricted referral re-sponse messages of authoritative name servers. Theattack is significantly more destructive than NXDomainattacks (e.g., the Mirai attack): i) It reaches an am-plification factor of more than 1620x on the numberof packets exchanged by the recursive resolver. ii) Inaddition to the negative cache, the attack also satu-rates the ‘NS’ resolver caches. To mitigate the attackimpact, we propose an enhancement to the recursiveresolver algorithm, MaxFetch(k), that prevents unnec-essary proactive fetches. We implemented MaxFetch(1)mitigation enhancement on a BIND resolver and testedit on real-world DNS query datasets. Our results showthat MaxFetch(1) degrades neither the recursive resolverthroughput nor its latency. Following the discovery of theattack, a responsible disclosure procedure was carriedout, and several DNS vendors and public providers haveissued a CVE and patched their systems.

Privacy-preserving machine learning (PPML) has many applications, from medical image classification and anomaly detection to financial analysis. nGraph-HE enables data scientists to perform private inference of deep learning (DL) models trained using popular frameworks such as TensorFlow. nGraph-HE computes linear layers using the CKKS homomorphic encryption (HE) scheme. The non-polynomial activation functions, such as MaxPool and ReLU, are evaluated in the clear by the data owner who obtains the intermediate feature maps. This leaks the feature maps to the data owner from which it may be possible to deduce the DL model weights. As a result, such protocols may not be suitable for deployment, especially when the DL model is intellectual property. In this work, we present MP2ML, a machine learning framework which integrates nGraph-HE and the secure two-party computation framework ABY, to overcome the limitations of leaking the intermediate feature maps to the data owner. We introduce a novel scheme for the conversion between CKKS and secure multi-party computation to execute DL inference while maintaining the privacy of both the input data and model weights. MP2ML is compatible with popular DL frameworks such as TensorFlow that can infer pre-trained neural networks with native ReLU activations. We benchmark MP2ML on the CryptoNets network with ReLU activations, on which it achieves a throughput of 33.3 images/s and an accuracy of 98.6%. This throughput matches the previous state-of-the-art work, even though our protocol is more accurate and scalable.

Nowadays, the resistance against algebraic attacks and fast algebraic attacks are considered as an important cryptographic property for Boolean functions used in stream ciphers. Both attacks are very powerful analysis concepts and can be applied to symmetric cryptographic algorithms used in stream ciphers. The notion of algebraic immunity has received wide attention since it is a powerful tool to measure the resistance of a Boolean function to standard algebraic attacks. Nevertheless, an algebraic tool to handle the resistance to fast algebraic attacks is not clearly identified in the literature. In the current paper, we propose a new parameter to measure the resistance of a Boolean function to fast algebraic attack. We also introduce the notion of fast immunity profile and show that it informs both on the resistance to standard and fast algebraic attacks. Further, we evaluate our parameter for two secondary constructions of Boolean functions. Moreover, A coding-theory approach to the characterization of perfect algebraic immune functions is presented. Via this characterization, infinite families of binary linear complementary dual codes (or LCD codes for short) are obtained from perfect algebraic immune functions. The binary LCD codes presented in this paper have applications in armoring implementations against so-called side-channel attacks (SCA) and fault non-invasive attacks, in addition to their applications in communication and data storage systems.

Secret sharing is a very useful way to maintain secrecy of private data when stored in a distributed way among several nodes. Two significant questions in this area are 1. how to accommodate new nodes and assign shares to the new nodes, the problem becomes harder if the number of joining nodes or the access structure is not known in advance and can be (potentially) unbounded and 2. to reduce the computational complexity of secret sharing schemes. In this paper we propose two new constructions of such secret sharing schemes based on different combinatorial structures. The first construction is based on generalized paths joining the opposite vertices of a hypercube which has been divided into smaller hypercubes. The second construction is a forest- based construction utilizing a dynamic data structure technique known as fractional cascading. The generalized path we call a pavement is new to this paper. Both our constructions use a new secret redistribution scheme to assign and re-assign shares to nodes. Towards the second question we show that allowing certain trade-offs, the constructions are implementable by $AC^0$ circuits which is the lowest complexity class in which secret sharing and reconstruction is possible. To the best of the knowledge of the authors, none of the similar existing schemes (evolving or dynamic) are $AC^0$ computable and this paper for the first time combines the idea of hypercubes and dynamic data structures with secret sharing for preserving long-term confidentiality of secret data.

The common approach in secure communication channel protocols is to rely on ciphertexts arriving in-order and to close the connection upon any rogue ciphertext. Cryptographic security models for channels generally reflect such design. This is reasonable when running atop lower-level transport protocols like TCP ensuring in-order delivery, as for example is the case with TLS or SSH. However, protocols like QUIC or DTLS which run over a non-reliable transport such as UDP, do not---and in fact cannot---close the connection if packets are lost or arrive in a different order. Those protocols instead have to carefully catch effects arising naturally in unreliable networks, usually by using a sliding-window technique where ciphertexts can be decrypted correctly as long as they are not misplaced too far. In order to be able to capture QUIC and the newest DTLS version 1.3, we introduce a generalized notion of robustness of cryptographic channels. This property can capture unreliable network behavior and guarantees that adversarial tampering cannot hinder ciphertexts that can be decrypted correctly from being accepted. We show that robustness is orthogonal to the common notion of integrity for channels, but together with integrity and chosen-plaintext security it provides a robust analogue of chosen-ciphertext security of channels. In contrast to prior work, robustness allows us to study packet encryption in the record layer protocols of QUIC and of DTLS 1.3 and the novel sliding-window techniques both protocols employ. We show that both protocols achieve robust chosen-ciphertext security based on certain properties of their sliding-window techniques and the underlying AEAD schemes. Notably, the robustness needed in handling unreliable network messages requires both record layer protocols to tolerate repeated adversarial forgery attempts. This means we can only establish non-tight security bounds (in terms of AEAD integrity), a security degration that was missed in earlier protocol drafts. Our bounds led the responsible IETF working groups to introduce concrete forgery limits for both protocols and the IRTF CFRG to consider AEAD usage limits more broadly.

As the fault based analysis techniques are becoming more and more powerful, there is a need to streamline the existing tools for better accuracy and ease of use. In this regard, we propose a machine learning assisted tool that can be used in the context of a differential fault analysis. In particular, finding the exact fault location by analyzing the XORed output of a stream cipher/ stream cipher based design is somewhat non-trivial. Traditionally, Pearson's correlation coefficient is used for this purpose. We show that a machine learning method is more powerful than the existing correlation coefficient, aside from being simpler to implement. As a proof of concept, we take two variants of Grain-128a (namely a stream cipher, and a stream cipher with authentication), and demonstrate that machine learning can outperform correlation with the same training/testing data. Our analysis shows that the machine learning can be considered as a replacement for the correlation in the future research works.

Physically unclonable function (PUF) is a technology to generate a device-unique identifier using process variation. PUF enables a cryptographic key that appears only when the chip is active, providing an efficient countermeasure against reverse-engineering attacks. In this paper, we explore the data conversion that digitizes a physical quantity representing PUF’s uniqueness into a numerical value as a new attack surface. We focus on time-to-digital converter (TDC) that converts time duration into a numerical value. We show the first signal injection attack on a TDC by manipulating its clock, and verify it through experiments on an off-the-shelf TDC chip. Then, we show how to leverage the attack to reveal a secret key protected by a PUF that uses a TDC for digitization.

In this short trivial note we argue that, assuming Generalized Continuum Hypothesis to be true, it is impractical to use encryption with $Key \in \{ 0, 1 \}^K$ and $Message \in \{ 0, 1 \}^M$ such that $\aleph_0 \leqslant \mathrm{card}\,K < \mathrm{card}\,M$, because "complexity" of the known-plaintext bruteforce attack equals "complexity" of a single $En/Decrypt(Key, Message)$ "computation" then.

We define and study a new cryptographic primitive, named One-One Constrained Pseudorandom Functions. In this model there are two parties, Alice and Bob, that hold a common random string $K$, where Alice in addition holds a predicate $f:[N] \rightarrow \{ 0,1 \}$ and Bob in addition holds an input $x \in [N]$. We then let Alice generate a key $K_f$ based on $f$ and $K$, and let Bob evaluate a value $K_x$ based on $x$ and $K$. We consider a third party that sees the values $(x,f,K_f)$ and the goal is to allow her to reconstruct $K_x$ whenever $f(x)=1$, while keeping $K_x$ pseudorandom whenever $f(x)=0$. This primitive can be viewed as a relaxation of constrained PRFs, such that there is only a single key query and a single evaluation query. We focus on the information-theoretic setting, where the one-one cPRF has perfect correctness and perfect security. Our main results are as follows. 1. A Lower Bound. We show that in the information-theoretic setting, any one-one cPRF for punctured predicates is of exponential complexity (and thus the lower bound meets the upper bound that is given by a trivial construction). This stands in contrast with the well known GGM-based punctured PRF from OWF, which is in particular a one-one cPRF. This also implies a similar lower bound for all NC1. 2. New Constructions. On the positive side, we present efficient information-theoretic constructions of one-one cPRFs for a few other predicate families, such as equality predicates, inner-product predicates, and subset predicates. We also show a generic AND composition lemma that preserves complexity. 3. An Amplification to standard cPRF. We show that all of our one-one cPRF constructions can be amplified to a standard (single-key) cPRF via any key-homomorphic PRF that supports linear computations. More generally, we suggest a new framework that we call the double-key model which allows to construct constrained PRFs via key-homomorphic PRFs. 4. Relation to CDS. We show that one-one constrained PRFs imply conditional disclosure of secrets (CDS) protocols. We believe that this simple model can be used to better understand constrained PRFs and related cryptographic primitives, and that further applications of one-one constrained PRFs and our double-key model will be found in the future, in addition to those we show in this paper.

Proxy re-encryption (PRE), formalized by Blaze et al. in 1998, allows a proxy entity to delegate the decryption right of a ciphertext from one party to another without obtaining the information of the plaintext. In recent years, many studies have explored how to construct PRE schemes that support fine-grained access control for complex application scenarios, such as identity-based PRE and attribute-based PRE. Besides, in order to achieve more flexible access control, the predicate proxy re-encryption (PPRE) is further studied. However, existing PPRE is restricted with the inner product predicate function. Therefore, how to realize the PPRE of arbitrary predicate function is still a problem to be solved. In this manuscript, we propose a secure generic construction of predicate proxy key re-encapsulation mechanism built from a ``linear'' predicate key encapsulation mechanism. Since the secure key encapsulation mechanism can be used as a building block to construct public key encryption, we can obtain a PPRE from our construction. As a result, the results open up new avenues for building more flexible and fine-grained PPRE.

We develop two variants of Cocks' identity-based encryption. One variant has faster encryption, where the most time-consuming part only requires several modular multiplications. The other variant makes the first variant anonymous under suitable complexity assumptions, while its decryption efficiency is about twice lower than the first one. Both the variants have ciphertext expansion twice more extensive than the original Cocks' identity-based encryption. To alleviate the issue of the second variant's large ciphertext expansion, we consider using it to construct a public-key encryption with keyword search scheme with a fast encryption algorithm.

Auditing a secure multiparty computation (MPC) protocol entails the validation of the protocol transcript by a third party that is otherwise untrusted. In this work we introduce the concept of end-to-end verifiable MPC (VMPC), that requires the validation to provide a correctness guarantee even in the setting that all servers, trusted setup primitives and all the client systems utilized by the input-providing users of the MPC protocol are subverted by an adversary. To instantiate VMPC, we introduce a new concept in the setting of zero-knowlegde protocols that we term crowd verifiable zero-knowledge (CVZK). A CVZK protocol enables a prover to convince a set of verifiers about a certain statement, even though each one individually contributes a small amount of entropy for verification and some of them are adversarially controlled. Given CVZK, we present a VMPC protocol that is based on discrete-logarithm related assumptions. At the high level of adversity that VMPC is meant to withstand, it is infeasible to ensure perfect correctness, thus we investigate the classes of functions and verifiability relations that are feasible in our framework, and present a number of possible applications the underlying functions of which can be implemented via VMPC.

We study the rational behaviors of participants in committee-based blockchains. Committee-based blockchains rely on specific blockchain consensus that must be guaranteed in presence of rational participants. We consider a simplified blockchain consensus algorithm based on existing or proposed committee-based blockchains that encapsulates the main actions of the participants: voting for a block, and checking its validity. Knowing that those actions have costs, and achieving the consensus gives rewards to committee members, we study using game theory how strategic players behave while trying to maximizing their gains. We consider different reward schemes, and found that in each setting, there exist equilibria where blockchain consensus is guaranteed; in some settings however, there can be coordination failures hindering consensus. Moreover, we study equilibria with trembling participants, which is a novelty in the context of committee-based blockchains. Trembling participants are rational that can do unintended actions with a low probability. We found that in presence of trembling participants, there exist equilibria where blockchain consensus is guaranteed; however, when only voters are rewarded, there also exist equilibria where validity can be violated.

Token-curated registries (TCRs) are a mechanism by which a set of users are able to jointly curate a reputable list about real-world information. Entries in the registry may have any form, so this primitive has been proposed for use -- and deployed -- in a variety of decentralized applications, ranging from the simple joint creation of lists to helping to prevent the spread of misinformation online. Despite this interest, the security of this primitive is not well understood, and indeed existing constructions do not achieve strong or provable notions of security or privacy. In this paper, we provide a formal cryptographic treatment of TCRs as well as a construction that provably hides the votes cast by individual curators. Along the way, we provide a model and proof of security for an underlying voting scheme, which may be of independent interest.

Recent studies have suggested various side-channel attacks for eavesdropping sound by analyzing the side effects of sound waves on nearby objects (e.g., a bag of chips and window) and devices (e.g., motion sensors). These methods pose a great threat to privacy, however they are limited in one of the following ways: they (1) cannot be applied in real time (e.g., Visual Microphone), (2) are not external, requiring the attacker to compromise a device with malware (e.g., Gyrophone), or (3) are not passive, requiring the attacker to direct a laser beam at an object (e.g., laser microphone). In this paper, we introduce "Lamphone," a novel side-channel attack for eavesdropping sound; this attack is performed by using a remote electro-optical sensor to analyze a hanging light bulb’s frequency response to sound. We show how fluctuations in the air pressure on the surface of the hanging bulb (in response to sound), which cause the bulb to vibrate very slightly (a millidegree vibration), can be exploited by eavesdroppers to recover speech and singing, passively, externally, and in real time. We analyze a hanging bulb’s response to sound via an electro-optical sensor and learn how to isolate the audio signal from the optical signal. Based on our analysis, we develop an algorithm to recover sound from the optical measurements obtained from the vibrations of a light bulb and captured by the electro-optical sensor. We evaluate Lamphone’s performance in a realistic setup and show that Lamphone can be used by eavesdroppers to recover human speech (which can be accurately identified by the Google Cloud Speech API) and singing (which can be accurately identified by Shazam and SoundHound) from a bridge located 25 meters away from the target room containing the hanging light bulb.

We give a lattice reduction algorithm that achieves root Hermite factor $k^{1/(2k)}$ in time $k^{k/8 + o(k)}$ and polynomial memory. This improves on the previously best known enumeration-based algorithms which achieve the same quality, but in time $k^{k/(2e) + o(k)}$. A cost of $k^{k/8 + o(k)}$ was previously mentioned as potentially achievable (Hanrot-Stehlé'10) or as a heuristic lower bound (Nguyen'10) for enumeration algorithms. We prove the complexity and quality of our algorithm under a heuristic assumption and provide empirical evidence from simulation and implementation experiments attesting to its performance for practical and cryptographic parameter sizes. Our work also suggests potential avenues for achieving costs below $k^{k/8 + o(k)}$ for the same root Hermite factor, based on the geometry of SDBKZ-reduced bases.

Logic synthesis is a fundamental step in the realization of modern integrated circuits. It has traditionally been employed for the optimization of CMOS-based designs, as well as for emerging technologies and quantum computing. Recently, it found application in minimizing the number of AND gates in cryptography benchmarks represented as xor-and graphs (XAGs). The number of AND gates in an XAG, which is called the logic network’s multiplicative complexity, plays a critical role in various cryptography and security protocols such as fully homomorphic encryption (FHE) and secure multi-party computation (MPC). Further, the number of AND gates is also important to assess the degree of vulnerability of a Boolean function, and influences the cost of techniques to protect against side-channel attacks. However, so far a complete logic synthesis flow for reducing the multiplicative complexity in logic networks did not exist or relied heavily on manual manipulations. In this paper, we present a logic synthesis toolbox for cryptography and security applications. The proposed tool consists of powerful transformations, namely resubstitution, refactoring, and rewriting, specifically designed to minimize the multiplicative complexity of an XAG. Our flow is fully automatic and achieves significant results over both EPFL benchmarks and cryptography circuits. We improve the best-known results for cryptography up to 59%, resulting in a normalized geometric mean of 0.82.

We give a lower bound for the size of the value set of almost perfect nonlinear (APN) functions \(F\colon \mathbb{F}_2^n \to \mathbb{F}_2^n\) in explicit form and proof it with methods of linear programming. It coincides with the bound given in [CHP17]. For \(n\) even it is \(\frac{ 2^n + 2 }{3}\) and sharp as the simple example \(F(x) = x^3\) shows. The sharp lower bound for \(n\) odd has to lie between \(\frac{ 2^n + 1 }{3}\) and \(2^{n-1}\). Sharp bounds for the cases \(n = 3\) and \(n = 5\) are explicitly given.

Secure aggregation is a cryptographic primitive that enables a server to learn the sum of the vector inputs of many clients. Bonawitz et al. (CCS 2017) presented a construction that incurs computation and communication for each client linear in the number of parties. While this functionality enables a broad range of privacy preserving computational tasks, scaling concerns limit its scope of use. We present the first constructions for secure aggregation that achieve polylogarithmic communication and computation per client. Our constructions provide security in the semi-honest and the semi-malicious setting where the adversary controls the server and a $\gamma$-fraction of the clients, and correctness with up to $\delta$-fraction dropouts among the clients. Our constructions show how to replace the complete communication graph of Bonawitz et al., which entails the linear overheads, with a $k$-regular graph of logarithmic degree while maintaining the security guarantees. Beyond improving the known asymptotics for secure aggregation, our constructions also achieve very efficient concrete parameters. The semi-honest secure aggregation can handle a billion clients at the per client cost of the protocol of Bonawitz et al. for a thousand clients. In the semi-malicious setting with $10^4$ clients, each client needs to communicate only with $3\%$ of the clients to have a guarantee that its input has been added together with the inputs of at least $5000$ other clients, while withstanding up to $5\%$ corrupt clients and $5\%$ dropouts. We also show an application of secure aggregation to the task of secure shuffling which enables the first cryptographically secure instantiation of the shuffle model of differential privacy.

Multivariate public key cryptography is a candidate for post-quantum cryptography, and it allows generating particularly short signatures and fast verification. The Rainbow signature scheme proposed by J. Ding and D. Schmidt is such a multivariate cryptosystem and is considered secure against all known attacks. The Rainbow-Band-Separation attack recovers a secret key of Rainbow by solving certain systems of quadratic equations, and its complexity is estimated by the well-known indicator called the degree of regularity. However, the degree of regularity generally is larger than the solving degree in experiments, and an accurate estimation cannot be obtained. In this paper, we propose a new indicator for the complexity of the Rainbow-Band-Separation attack using the $F_4$ algorithm, which gives a more precise estimation compared to one using the degree of regularity. This indicator is deduced by the two-variable power series $$\frac{\prod _{i=1}^m(1-t_1^{d_{i1}}t_2^{d_{i2}})}{(1-t_1)^{n_1}(1-t_2)^{n_2}},$$ which coincides with the one-variable power series at $t_1=t_2$ deriving the degree of regularity. Moreover, we show a relation between the Rainbow-Band-Separation attack using the hybrid approach and the HighRank attack. By considering this relation and our indicator, we obtain a new complexity estimation for the Rainbow-Band-Separation attack. Consequently, we are able to understand the precise security of Rainbow against the Rainbow-Band-Separation attack using the $F_4$ algorithm.

Currently the National Institute of Standards and Technology (NIST) is engaged in a post-quantum standardization effort, analyzing numerous candidate schemes to provide security against the advancing threat of quantum computers. Among the candidates in the second round of the standardization process is Rainbow, a roughly 15 year old digital signature scheme based on multivariate systems of equations. While there are many attack avenues for Rainbow, the parameters have to date seemed balanced in such a way to make every attack sufficiently costly that it meets the security levels specified by NIST in their standardization effort. One type of attack against Rainbow has historically outperformed empirically its theoretical complexity: the Rainbow Band Separation (RBS) attack. We explain this discrepancy by providing a tighter theoretical analysis of the attack complexity. While previous analyses assumed that the system of equations derived in the attack are generic, our analysis uses the fact that they are structured to justify tighter bounds on the complexity. As a result, we can prove under the same set of assumptions used to justify the analysis in the Rainbow submission specification that none of the parameters of Rainbow achieve their claimed security level. Specifically, the level I, III and V parameter sets fall short of their claimed security levels by at least 3, 6 and 10 bits, respectively. We then apply our analysis to suggest the small parameter changes necessary to guarantee that Rainbow can meet the NIST security levels.

Classical definitions for secure multiparty computation assume the existence of a single adversarial entity controlling the set of corrupted parties. Intuitively, the definition requires that the view of the adversary, corrupting $t$ parties, in a real-world execution can be simulated by an adversary in an ideal model, where parties interact only via a trusted-party. No restrictions, however, are imposed on the view of honest parties in the protocol, thus, if honest parties obtain information about the private inputs of other honest parties -- it is not counted as a violation of privacy. This is arguably undesirable in many situations that fall into the MPC framework. Nevertheless, there are secure protocols (e.g., the 2-round multiparty protocol of Ishai et al.~[CRYPTO 2010] tolerating a single corrupted party) that instruct the honest parties to reveal their private inputs to all other honest parties (once the malicious party is somehow identified). In this paper, we put forth a new security notion, which we call \textit{FaF-security}, extending the classical notion. In essence, $(t,h^*)$-FaF-security requires the view of a subset of up to $h^*$ honest parties to also be simulatable in the ideal model (in addition to the view of the malicious adversary, corrupting up to $t$ parties). This property should still hold, even if the adversary leaks information to honest parties by sending them non-prescribed messages. We provide a thorough exploration of the new notion, investigating it in relation to a variety of existing security notions. We further investigate the feasibility of achieving FaF-security and show that every functionality can be computed with (computational) $(t,h^*)$-FaF full-security, if and only if $2t+ h^*<m$. Interestingly, the lower-bound result actually shows that even fair FaF-security is impossible in general when $2t+ h^*\ge m$ (surprisingly, the view of the malicious attacker is not used as the trigger for the attack). We also investigate the optimal round complexity for $(t,h^*)$-FaF-secure protocols and give evidence that the leakage of private inputs of honest parties in the protocol of Ishai et al.~[CRYPTO 2010] is inherent. Finally, we investigate the feasibility of statistical/perfect FaF-security, employing the viewpoint used by Fitzi et al.~[ASIACRYPT 1999] for \textit{mixed-adversaries}.

Personal data exchange and disclosure prevention are widespread problems in our digital world. There are a couple of information technologies embedded in the commercial and government processes. People need to exchange their personal information while using these technologies. And therefore, It is essential to make this exchange is secure. Despite many legal regulations, there are many cases of personal data breaches that lead to undesirable consequences. Reasons for personal data leakage may be adversary attack or data administration error. At the same time, creating complex service interaction and multilayer information security may lead to many inconveniences for the user. Personal data exchange protocol has the following tasks: participant’s data transfer, ensuring information security, providing participants with trust in each other and ensuring service availability. In this paper, we represent a personal data exchange protocol called X. The main idea is to provide personal data encryption on the user side and thus to prevent personal data disclosure and publication. This approach allows us to transfer personal data from user to service only in the form of an encrypted data packet - blob. Each blob can be validated and certified by a personal data inspector who had approved user’s information. It can be any government department or a commercial organization, for example, passport issuing authority, banks, etc. It implies that we can provide several key features for personal data exchange. A requesting service cannot publish the user personal data. It still can perform a validation protocol with an inspector to validate user data. We do not depend on service data administration infrastructure and do not complicate the inspector’s processes by adding additional information about the personal data request. The personal data package has a link between the personal data owner and a service request. Each blob is generated for a single request and has a time limit for a provided encrypted personal data. After this limit, the service can not use a received package. The user cannot provide invalid personal data or use the personal data of another person. We don’t restrict specified cryptographic algorithms usage The X protocol can be implemented with any encryption, digital signature, key generation algorithms which are secure in our adversary model. For protocol description, Russian standardized cryptographic protocols are used. The paper also contains several useful examples of how the X protocol can be implemented in real information systems.

Cryptographic primitives have been designed to be secure against mathematical attacks in a black-box model. Such primitives can be implemented in a way that they are also secure against physical attacks, in a grey-box model. One of the most popular techniques for this purpose is masking. The increased security always comes with a high price tag in terms of implementation cost. In this work, we look at how the traditional design principles of symmetric primitives can be at odds with the optimization of the implementations and how they can evolve to be more suitable for embedded systems. In particular, we take a comparative look at the round 2 candidates of the NIST lightweight competition and their implementation properties in the world of masking.

GIFT-COFB is one of the round 2 candidate algorithms of NIST lightweight cryptography. In this paper we present a forgery attack on GIFT-COFB. In our attack, the block cipher GIFT is viewed as a block box, and for an arbitrary ciphertext $(C, T)$ with at least twice the block length of GIFT-COFB, if an attacker knows arbitrary two successive blocks of message $M$ corresponding to $C$, he/she can forge infinite new valid ciphertexts $(C', T')$ such that for each $(C', T')$, there exists a plaintext $M'$ satisfying $(C', T')$=GIFT-COFB($M'$). The above result shows that GIFT-COFB can not resist against the forgery attack.

We report on two new records: the factorization of RSA-240, a 795-bit number, and a discrete logarithm computation over a 795-bit prime field. Previous records were the factorization of RSA-768 in 2009 and a 768-bit discrete logarithm computation in 2016. Our two computations at the 795-bit level were done using the same hardware and software, and show that computing a discrete logarithm is not much harder than a factorization of the same size. Moreover, thanks to algorithmic variants and well-chosen parameters, our computations were significantly less expensive than anticipated based on previous records. The last page of this paper also reports on the factorization of RSA-250.

The Chinese remainder theorem (CRT)-based multiplier is a new type of hybrid bit-parallel multiplier, which can achieve nearly the same time complexity compared with the fastest multiplier known to date with reduced space complexity. However, the current CRT-based multipliers are only applicable to trinomials. In this paper, we propose an efficient CRT-based bit-parallel multiplier for a special type of pentanomial $x^m+x^{m-k}+x^{m-2k}+x^{m-3k}+1, 5k<m\leq 7k$. Through transforming the non-constant part $x^m+x^{m-k}+x^{m-2k}+x^{m-3k}$ into a binomial, we can obtain relatively simpler quotient and remainder computations, which lead to faster implementation with reduced space complexity compared with classic quadratic multipliers. Moreover, for some $m$, our proposal can achieve the same time delay as the fastest multipliers for irreducible Type II and Type C.1 pentanomials of the same degree, but the space complexities are reduced.

A software watermarking scheme can embed a message into a program without significantly changing its functionality. Moreover, any attempt to remove the embedded message in a marked program will substantially change the functionality of the program. Prior constructions of watermarking schemes focus on watermarking cryptographic functions, such as pseudorandom function (PRF), public key encryption, etc. A natural security requirement for watermarking schemes is collusion resistance, where the adversary’s goal is to remove the embedded messages given multiple marked versions of the same program. Currently, this strong security guarantee has been achieved by watermarking schemes for public key cryptographic primitives from standard assumptions (Goyal et al., CRYPTO 2019) and by watermarking schemes for PRFs from indistinguishability obfuscation (Yang et al., ASIACRYPT 2019). However, no collusion resistant watermarking scheme for PRF from standard assumption is known. In this work, we solve this problem by presenting a generic construction that upgrades a watermarkable PRF without collusion resistance to a collusion resistant one. One appealing feature of our construction is that it can preserve the security properties of the original scheme. For example, if the original scheme has security with extraction queries, the new scheme is also secure with extraction queries. Besides, the new scheme can achieve unforgeability even if the original scheme does not provide this security property. Instantiating our construction with existing watermarking schemes for PRF, we obtain collusion resistant watermarkable PRFs from standard assumptions, offering various security properties.

In this work, we exhibit a hierarchy of polynomial time algorithms solving approximate variants of the Closest Vector Problem (CVP). Our first contribution is a heuristic algorithm achieving the same distance tradeoff as HSVP algorithms, namely $\approx \beta^{\frac{n}{2\beta}}\textrm{covol}(\Lambda)^{\frac{1}{n}}$ for a random lattice $\Lambda$ of rank $n$. Compared to the so-called Kannan's embedding technique, our algorithm allows using precomputations and can be used for efficient batch CVP~instances. This implies that some attacks on lattice-based signatures lead to very cheap forgeries, after a precomputation. Our second contribution is a \emph{proven} reduction from approximating the closest vector with a factor $\approx n^{\frac32}\beta^{\frac{3n}{2\beta}}$ to the Shortest Vector Problem (SVP) in dimension $\beta$.

In function inversion, we are given a function $f: [N] \mapsto [N]$, and want to prepare some advice of size $S$, such that we can efficiently invert any image in time $T$. This is a well studied problem with profound connections to cryptography, data structures, communication complexity, and circuit lower bounds. Investigation of this problem in the quantum setting was initiated by Nayebi, Aaronson, Belovs, and Trevisan (2015), who proved a lower bound of $ST^2 = \tilde\Omega(N)$ for random permutations against classical advice, leaving open an intriguing possibility that Grover's search can be sped up to time $\tilde O(\sqrt{N/S})$. Recent works by Hhan, Xagawa, and Yamakawa (2019), and Chung, Liao, and Qian (2019) extended the argument for random functions and quantum advice, but the lower bound remains $ST^2 = \tilde\Omega(N)$. In this work, we prove that even with quantum advice, $ST + T^2 = \tilde\Omega(N)$ is required for an algorithm to invert random functions. This demonstrates that Grover's search is optimal for $S = \tilde O(\sqrt{N})$, ruling out any substantial speed-up for Grover's search even with quantum advice. Further improvements to our bounds would imply new classical circuit lower bounds, as shown by Corrigan-Gibbs and Kogan (2019). To prove this result, we develop a general framework for establishing quantum time-space lower bounds. We further demonstrate the power of our framework by proving the following results. * Yao's box problem: We prove a tight quantum time-space lower bound for classical advice. For quantum advice, we prove a first time-space lower bound using shadow tomography. These results resolve two open problems posted by Nayebi et al (2015). * Salted cryptography: We show that “salting generically provably defeats preprocessing,” a result shown by Coretti, Dodis, Guo, and Steinberger (2018), also holds in the quantum setting. In particular, we prove quantum time-space lower bounds for a wide class of salted cryptographic primitives in the quantum random oracle model. This yields a first quantum time-space lower bound for salted collision-finding, which in turn implies that ${PWPP}^{O} \not\subseteq {FBQP}^{O}{/qpoly}$ relative to a random oracle $O$.

Masking is one of the most popular countermeasures to protect cryptographic implementations against side-channel analysis since it is provably secure and can be deployed at the algorithm level. To strengthen the original Boolean masking scheme, several works have suggested using schemes with high algebraic complexity. The Inner Product Masking (IPM) is one of those. In this paper, we propose a unified framework to quantitatively assess the side-channel security of the IPM in a coding-theoretic approach. Specifically, starting from the expression of IPM in a coded form, we use two defining parameters of the code to characterize its side-channel resistance. In order to validate the framework, we then connect it to two leakage metrics (namely signal-to-noise ratio and mutual information, from an information-theoretic aspect) and one typical attack metric (success rate, from a practical aspect) to build a firm foundation for our framework. As an application, our results provide ultimate explanations on the observations made by Balasch et al. at EUROCRYPT'15 and at ASIACRYPT'17, Wang et al. at CARDIS'16 and Poussier et al. at CARDIS'17 regarding the parameter effects in IPM, like higher security order in bounded moment model. Furthermore, we show how to systematically choose optimal codes (in the sense of a concrete security level) to optimize IPM by using this framework. Eventually, we present a simple but effective algorithm for choosing optimal codes for IPM, which is of special interest for designers when selecting optimal parameters for IPM.

In this paper we present a series of applications steming from a formal treatment of linear secret-sharing isomorphisms, which are linear transformations between different secret-sharing schemes defined over vector spaces over a field $\mathbb{F}$ and allow for efficient multiparty conversion from one secret-sharing scheme to the other. This concept generalizes the folklore idea that moving from a secret-sharing scheme over $\mathbb{F}_{p}$ to a secret sharing ``in the exponent'' can be done non-interactively by multiplying the share unto a generator of e.g., an elliptic curve group. We generalize this idea and show that it can also be used to compute arbitrary bilinear maps and in particular pairings over elliptic curves. We include the following practical applications originating from our framework: First we show how to securely realize the Pointcheval-Sanders signature scheme (CT-RSA 2016) in MPC. Second we present a construction for dynamic proactive secret-sharing which outperforms the current state of the art from CCS 2019. Third we present a construction for MPC input certification using digital signatures that we show experimentally to outperform the previous best solution in this area.

Secret sharing-based distributed storage systems are one approach to provide long-term protection of data even against quantum computing. Confidentiality is provided because the shares of data are renewed periodically while integrity is provided by commitment schemes. However, this solution is prohibitively costly and impractical: share renewal requires an information-theoretically secure channel between any two nodes and long-term confidential commitment schemes are computationally impractical for large files. In this paper, we present SAFE, a secret sharing-based long-term secure distributed storage system that leverages a Trusted Execution Environment (TEE) to overcome the above limitations. Share generation and renewal are performed inside the TEE and the shares are securely distributed to the storage servers. We prototype SAFE protocols using a TEE instantiation, and show their efficiency, even for large files, compared to existing schemes.

Skinny is a lightweight tweakable block cipher which received a great deal of cryptanalytic attention following its elegant structure and efficiency. Inspired by the Skinny competitions, multiple attacks on it were reported in different settings (e.g. single vs. related-tweakey) using different techniques (impossible differentials, meet-in-the-middle, etc.). In this paper we revisit some of these attacks, identify issues with several of them, and offer a series of improved attacks which were experimentally verified. Our best attack can attack up to 18 rounds using $2^{60}$ chosen ciphertexts data, $2^{116}$ time, and $2^{112}$ memory.

This paper introduces a logarithmic-size membership proof, Lin2Selector, obtained by iterating a new OR-reduction step, formalized as a standalone argument Lin2Xor. Our main technical contribution is the Lin2-Xor lemma, which establishes the required special soundness for this reduction and thereby enables a clean proof that Lin2Selector is a zero-knowledge argument of knowledge. As an application, we instantiate two setup-free linkable ring signatures via the Fiat–Shamir transform in the ROM: minimalistic L2S-LRS, of length 2(log n)+4 group/scalar elements, and multisignature-friendly L2S-LRS-MS, of length 2(log n)+5, supporting an LSAG-style key image. Both schemes rely only on the standard DLR/DDH assumptions in a black-box prime-order group and allow efficient verification dominated by a single multi-exponentiation, enabling standard batching optimizations. The OR-reduction step Lin2Xor suggests a natural generalization to higher arity. This may enable even more compact one-out-of-many proofs/signatures with lengths approaching (log n)+O(log log n), as well as compact k-out-of-many variants; we leave these as open directions.

We study time/memory tradeoffs of function inversion: an algorithm, i.e., an inverter, equipped with an $s$-bit advice on a randomly chosen function $f\colon [n] \mapsto [n]$ and using $q$ oracle queries to $f$, tries to invert a randomly chosen output $y$ of $f$, i.e., to find $x\in f^{-1}(y)$. Much progress was done regarding adaptive function inversion - the inverter is allowed to make adaptive oracle queries. Hellman [IEEE transactions on Information Theory '80] presented an adaptive inverter that inverts with high probability a random $f$. Fiat and Naor [SICOMP '00] proved that for any $s,q$ with $s^3 q = n^3$ (ignoring low-order terms), an $s$-advice, $q$-query variant of Hellman's algorithm inverts a constant fraction of the image points of any function. Yao [STOC '90] proved a lower bound of $sq\ge n$ for this problem. Closing the gap between the above lower and upper bounds is a long-standing open question. Very little is known for the non-adaptive variant of the question - the inverter chooses its queries in advance. The only known upper bounds, i.e., inverters, are the trivial ones (with $s+q= n$), and the only lower bound is the above bound of Yao. In a recent work, Corrigan-Gibbs and Kogan [TCC '19] partially justified the difficulty of finding lower bounds on non-adaptive inverters, showing that a lower bound on the time/memory tradeoff of non-adaptive inverters implies a lower bound on low-depth Boolean circuits. Bounds that, for a strong enough choice of parameters, are notoriously hard to prove. We make progress on the above intriguing question, both for the adaptive and the non-adaptive case, proving the following lower bounds on restricted families of inverters: - Linear-advice (adaptive inverter): If the advice string is a linear function of $f$ (e.g., $A\times f$, for some matrix $A$, viewing $f$ as a vector in $[n]^n$), then $s+q \in \Omega(n)$. The bound generalizes to the case where the advice string of $f_1 + f_2$, i.e., the coordinate-wise addition of the truth tables of $f_1$ and $f_2$, can be computed from the description of $f_1$ and $f_2$ by a low communication protocol. - Affine non-adaptive decoders: If the non-adaptive inverter has an affine decoder - it outputs a linear function, determined by the advice string and the element to invert, of the query answers - then $s \in \Omega(n)$ (regardless of $q$). - Affine non-adaptive decision trees: If the non-adaptive inversion algorithm is a $d$-depth affine decision tree - it outputs the evaluation of a decision tree whose nodes compute a linear function of the answers to the queries - and $q < cn$ for some universal $c>0$, then $s\in \Omega(n/d \log n)$.

The Internet of Things (IoT) based services are getting a widespread expansion in all the directions and dimensions of the 21st century. The IoT based deployment involves an internet-connected sensor, mobiles, laptops, and other networking and computing de- vices. In most IoT based applications, the sensor collects the data and communicates it to the end-user via gateway device or fog device over a precarious internet channel. The attacker can use this open channel to capture the sensing device or the gateway device to collect the IoT data or control the IoT system. For a long time, numerous researchers are working towards designing the authentication mechanism for the sen- sor network to achieve reliable and computationally feasible security. For the resource constraint environment of the IoT, it is essential to design reliable, ecient, and secure authentication protocol. In this paper, we propose a novel approach of authentication in the IoT paradigm called a Level-Dependent Authentication(LDA). In the LDA protocol, we propose a security reliable and resource ecient key sharing mechanism in which users at level li can communicate with the sensor at level lj if and only if the level of user in the organizational hierarchy is lower or equal to the level of sensor deployment. We pro- vide a security analysis for the proposed LDA protocol using random oracle based games & widely accepted AVISPA tools. We prove mutual authentication for the proposed protocol using BAN logic. In this paper, we also discuss a comparative analysis of the proposed protocol with other existing IoT authentication systems based on communica- tion cost, computation cost, and security index. We provide an implementation for the proposed protocol using a globally adopted IoT protocol called MQTT protocol. Finally, we present the collected data related to the networking parameters like throughput and round trip delay.

Oblivious linear evaluation (OLE) is a fundamental building block in multi-party computation protocols. In OLE, a sender holds a description of an affine function $f_{\alpha,\beta}(z)=\alpha z+\beta$, the receiver holds an input $x$, and gets $\alpha x+\beta$ (where all computations are done over some field, or more generally, a ring). Vector OLE (VOLE) is a generalization where the sender has many affine functions and the receiver learns the evaluation of all of these functions on a single point $x$. The state-of-the-art semi-honest VOLE protocols generally fall into two groups. The first group relies on standard assumptions to achieve security but lacks in concrete efficiency. These constructions are mostly based on additively homomorphic encryption (AHE) and are classified as ``folklore". The second group relies on less standard assumptions, usually properties of sparse, random linear codes, but they manage to achieve concrete practical efficiency. In this work, we present a conceptually simple VOLE protocol that derives its security from a standard assumption, namely Ring Learning with Errors (RLWE), while still achieving concrete efficiency comparable to the fastest VOLE protocols from non-standard coding assumptions. Furthermore, our protocol admits a natural extension to batch OLE (BOLE), which is yet another variant of OLE that computes many OLEs in parallel.

Secure-channel establishment allows two endpoints to communicate confidentially and authentically. Since they hide all data sent across them, good or bad, secure channels are often subject to mass surveillance in the name of (inter)national security. Some protocols are constructed to allow easy data interception . Others are designed to preserve data privacy and are either subverted or prohibited to use without trapdoors. We introduce LIKE, a primitive that provides secure-channel establishment with an exceptional, session-specific opening mechanism. Designed for mobile communications, where an operator forwards messages between the endpoints, it can also be used in other settings. LIKE allows Alice and Bob to establish a secure channel with respect to n authorities. If the authorities all agree on the need for interception, they can ensure that the session key is retrieved. As long as at least one honest authority prohibits interception, the key remains secure; moreover LIKE is versatile with respect to who learns the key. Furthermore, we guarantee non-frameability: nobody can falsely incriminate a user of taking part in a conversation; and honest-operator: if the operator accepts a transcript as valid, then the key retrieved by the authorities is the key that Alice and Bob should compute. Experimental results show that our protocol can be efficiently implemented.

Ring signatures are a cryptographic primitive that allow a signer to anonymously sign messages on behalf of an ad-hoc group of $N$ potential signers (the so-called ring). This primitive has attracted significant research since its introduction by Rivest et al. (ASIACRYPT'01), but until recently, no construction was known that was both (i) compact, i.e., the signature size is sub-linear in $N$, and (ii) in the plain model, i.e., secure under standard hardness assumptions without requiring heuristic or setup assumptions. The first construction in this most desirable setting, where reducing trust in external parties is the primary goal, was only recently presented by Backes et al. (EUROCRYPT'19). An interesting generalization of ring signatures are $t$-out-of-$N$ ring signatures for $t\geq 1$, also known as threshold ring (thring) signatures (Bresson et al., CRYPTO'02). For threshold ring signatures, non-linkable sub-linear-size constructions are not even known under heuristic or setup assumptions. In this work, we propose the first sub-linear thring signatures and prove them secure in the plain model. While our constructions are inspired by the template underlying the Backes et al. construction, they require novel ideas and techniques. Our scheme is non-interactive, and has strong inter-signer anonymity, meaning that signers do not need to know the other signers that participate in a threshold signing. We then present a linkable counterpart to our non-linkable construction. Our thring signatures can easily be adapted to achieve the recently introduced notions of flexibility (Okamoto et al., EPRINT'18) as well as claimability and repudiability (Park and Sealfon, CRYPTO'19). (Th)Ring signatures and, in particular, their linkable versions have recently drawn significant attention in the field of privacy-friendly cryptocurrencies. We discuss applications that are enabled by our strong inter-signer anonymity, demonstrating that thring signatures are interesting from a practical perspective also.

A Diophantine equation is a multi-variate polynomial equation with integer coefficients, and it is satisfiable if it has a solution with all unknowns taking integer values. Davis, Putnam, Robinson and Matiyasevich showed that the general Diophantine satisfiability problem is undecidable (giving a negative answer to Hilbert’s tenth problem) but it is nevertheless possible to argue in zero-knowledge the knowledge of a solution, if a solution is known to a prover. We provide the first succinct honest-verifier zero-knowledge argument for the satisfiability of Diophantine equations with a communication complexity and a round complexity that grows logarithmically in the size of the polynomial equation. The security of our argument relies on standard assumptions on hidden-order groups. As the argument requires to commit to integers, we introduce a new integer-commitment scheme that has much smaller parameters than Damgard and Fujisaki’s scheme. We finally show how to succinctly argue knowledge of solutions to several NP-complete problems and cryptographic problems by encoding them as Diophantine equations.

This report deals with the problem of identifying the potential correlations between the observable power consumption of a digital circuit and its inputs, when the operating conditions of the circuit involve a logic hazard (also known as glitch). This problem is of utmost importance when the circuit is a cryptographic primitive that must ensure that secret input data (e.g., keys) does not leak. We present a universal algebra construction that allows to derive a set of artefacts from a digital circuit among which a conservative estimate of the Boolean expression that the circuit might leak as well as the extended input/output correlation matrix [1]. This allows the evaluation of the robustness against side channel attacks through a set of constructions that fall under the umbrella of robust probing security [2]. We believe that such a formalisation is well suited for CAD synthesis tools to help the design of more robust cryptographic primitives.

Bit permutation based block ciphers, like PRESENT and GIFT, are well-known for their extreme lightweightness in hardware implementation. However, designing such ciphers comes with one major challenge - to ensure strong cryptographic properties simply depending on the combination of three components, namely S-box, a bit permutation and a key addition function. Having a wrong combination of components could lead to weaknesses. In this article, we studied the interaction between these components, improved the theoretical security bound of GIFT and highlighted the potential pitfalls associated with a bit permutation based primitive design. We also conducted analysis on TRIFLE, a first-round candidate for the NIST lightweight cryptography competition, where our findings influenced the elimination of TRIFLE from second-round of the NIST competition. In particular, we showed that internal state bits of TRIFLE can be partially decrypted for a few rounds even without any knowledge of the key.

In the past decades, user authentication has been dominated by server-side password-based solutions that rely on "what users know". This approach is susceptible to breaches and phishing attacks, and poses usability challenges. As a result, the industry is gradually moving to biometric-based client-side solutions that do not store any secret information on servers. This shift necessitates the safe storage of biometric templates and private keys, which are used to generate tokens, on user devices. We propose a new generic framework called Biometric Enabled Threshold Authentication (BETA) to protect sensitive client-side information like biometric templates and cryptographic keys. Towards this, we formally introduce the notion of Fuzzy Threshold Tokenizer (FTS) where an initiator can use a "close" biometric measurement to generate an authentication token if at least $t$ (the threshold) devices participate. We require that the devices only talk to the initiator, and not to each other, to capture the way user devices are connected in the real world. We use the universal composability (UC) framework to model the security properties of FTS, including the unforgeability of tokens and the privacy of the biometric values (template and measurement), under a malicious adversary. We construct three protocols that meet our definition. Our first two protocols are general feasibility results that work for any distance function, any threshold $t$ and tolerate the maximal (i.e. $t-1$) amount of corruption. They are based on any two round UC-secure multi-party computation protocol in the standard model (with a CRS) and threshold fully homomorphic encryption, respectively. We show how to effectively use these primitives to build protocols in a constrained communication model with just four rounds of communication. For the third protocol, we consider inner-product based distance metrics (cosine similarity, Euclidean distance, etc.) specifically, motivated by the recent interest in its use for face recognition. We use Paillier encryption, efficient NIZKs for specific languages, and a simple garbled circuit to build an efficient protocol for the common case of $n=3$ devices with one compromised.

We consider threshold ring signatures (introduced by Bresson et al. [BSS02], where any t signers can sign a message while anonymizing themselves within a larger (size-n) group. The signature proves that t members of the group signed, without revealing anything else about their identities. Our contributions in this paper are two-fold. First, we strengthen existing definitions of threshold ring signatures in a natural way; we demand that a signer cannot be de-anonymized even by their fellow signers. This is crucial, since in applications where a signer's anonymity is important, we do not want anonymity to be compromised by a single insider. Our definitions demand non-interactive signing, which is important for anonymity, since truly anonymous interaction is difficult or impossible in many scenarios. Second, we give the first rigorous construction of a threshold ring signature with size independent of n, the number of users in the larger group. Instead, our signatures have size linear in t, the number of signers. This is also a very important contribution; signers should not have to choose between achieving their desired degree of anonymity (possibly very large n) and their need for communication efficiency.

Nakamoto's famous blockchain protocol enables achieving consensus in a so-called permissionless setting--anyone can join (or leave) the protocol execution, and the protocol instructions do not depend on the identities of the players. His ingenious protocol prevents ``sybil attacks'' (where an adversary spawns any number of new players) by relying on computational puzzles (a.k.a. ``moderately hard functions'') introduced by Dwork and Naor (Crypto'92). Recent work by Garay et al (EuroCrypt'15) and Pass et al. (EuroCrypt'17) demonstrate that this protocol provably achieves consistency and liveness assuming a) honest players control a majority of the computational power in the network, b) the puzzle-difficulty is appropriately set as a function of the maximum network message delay and the total computational power of the network, and c) the computational puzzle is modeled as a random oracle. These works, however, leave open the question of how to set the puzzle difficulty in a setting where the computational power in the network is changing. Nakamoto's protocol indeed also includes a description of a difficutly update procedure. A recent work by Garay et al. (Crypto'17) indeed shows a variant of this difficulty adjustment procedure can be used to get a sound protocol as long as the computational power does not change too fast --- however, under two restrictions: 1) their analysis assumes that the attacker cannot delays network messages, and 2) the changes in computational power in the network changes are statically set (i.e., cannot be adaptively selected by the adversary). In this work, we show the same result but without these two restrictions, demonstrating the soundness of a (slightly different) difficulty update procedure, assuming only that the computational power in the network does not change too fast (as a function of the maximum network message delays); as an additional contribution, our analysis yields a tight bound on the ``chain quality'' of the protocol.

A common approach to bootstrapping a new cryptocurrency is an airdrop, an arrangement in which existing users give away currency to entice new users to join. But current airdrops offer no recipient privacy: they leak which recipients have claimed the funds, and this information is easily linked to off-chain identities. In this work, we address this issue by defining a private airdrop and describing concrete schemes for widely-used user credentials, such as those based on ECDSA and RSA. Our private airdrop for RSA builds upon a new zero-knowledge argument of knowledge of the factorization of a committed secret integer, which may be of independent interest. We also design a private genesis airdrop that efficiently sends private airdrops to millions of users at once. Finally, we implement and evaluate. Our fastest implementation takes 40--180 ms to generate and 3.7--10 ms to verify an RSA private airdrop signature. Signatures are 1.8--3.3 kiB depending on the security parameter.