Group key exchange (GKE) protocols let a group of users jointly establish fresh and secure key material. Many flavors of GKE have been proposed, differentiated by, among others, whether group membership is static or dynamic, whether a single key or a continuous stream of keys is established, and whether security is provided in the presence of state corruptions (forward and post-compromise security). In all cases, an indispensable ingredient to the rigorous analysis of a candidate solution is a corresponding formal security model. We observe, however, that most GKE-related publications are more focused on building new constructions that have more functionality or are more efficient than prior proposals, while leaving the job of identifying and working out the details of adequate security models a subordinate task. In this systematization of knowledge we bring the formal modeling of GKE security to the fore by revisiting the intuitive goals of GKE, critically evaluating how these goals are reflected (or not) in the established models, and how they would be best considered in new models. We classify and compare characteristics of a large selection of game-based GKE models that appear in the academic literature, including those proposed for GKE with post-compromise security. We observe a range of shortcomings in some of the studied models, such as dependencies on overly restrictive syntactical constrains, unrealistic adversarial capabilities, or simply incomplete definitions. Our systematization enables us to identify a coherent suite of desirable characteristics that we believe should be represented in all general purpose GKE models. To demonstrate the feasibility of covering all these desirable characteristics simultaneously in one concise definition, we conclude with proposing a new generic reference model for GKE.

The ultimate goal in modern secure e-voting is to enable everyone to verify whether the final election result correctly reflects the votes chosen by the (human) voters, without exposing how each individual voted. These fundamental security properties are called end-to-end verifiability and voter privacy. Unfortunately, it turns out to be very challenging to pursue these properties simultaneously, especially when the latter must be future-proofed against the rise of quantum computers. In this work, we show, for the first time, a practical approach to do this. We present Epoque, the first end-to-end verifiable, voter-private, post-quantum-secure homomorphic e-voting protocol. It achieves its properties through the combination of practical lattice-based cryptographic primitives only, in a novel way. We formally prove all our security claims under common trust and hardness assumptions. At the core of Epoque lies an efficient identity-based encryption (IBE) scheme with blazingly fast master-key decryption. It is the component that makes the efficient tallying of thousands or millions of ballots a practical possibility. In order to demonstrate its practicality, we fully implemented it and provide detailed benchmarks; we believe this latter contribution is of independent interest beyond the specific e-voting application.

Secure multi-party computation (MPC) allows multiple parties to perform secure joint computations on their private inputs. Today, applications for MPC are growing with thousands of parties wishing to build federated machine learning models or trusted setups for blockchains. To address such scenarios we propose a suite of novel MPC protocols that maximize throughput when run with large numbers of parties. In particular, our protocols have both communication and computation complexity that decrease with the number of parties. Our protocols build on prior protocols based on packed secret-sharing, introducing new techniques to build more efficient computation for general circuits. Specifically, we introduce a new approach for handling linear attacks that arise in protocols using packed secret-sharing and we propose a method for unpacking shared multiplication triples without increasing the asymptotic costs. Compared with prior work, we avoid the $\log |C|$ overhead required when generically compiling circuits of size $|C|$ for use in a SIMD computation, and we improve over folklore ``committee-based'' solutions by a factor of $O(s)$, the statistical security parameter. In practice, our protocol is up to $10X$ faster than any known construction, under a reasonable set of parameters.

Verifiable Random Functions (VRFs) play a key role in Proof-of-Stake blockchains such as Algorand to achieve highly scalable consensus, but currently deployed VRFs lack post-quantum security, which is crucial for future-readiness of blockchain systems. This work presents the first quantum-safe VRF scheme based on symmetric primitives. Our main proposal is a practical many-time quantum-safe VRF construction, X-VRF, based on the XMSS signature scheme. An innovation of our work is to use the state of the blockchain to counter the undesired stateful nature of XMSS by constructing a blockchain-empowered VRF. While increasing the usability of XMSS, our technique also enforces honest behavior when creating an X-VRF output so as to satisfy the fundamental uniqueness property of VRFs. We show how X-VRF can be used in the Algorand setting to extend it to a quantum-safe blockchain and provide four instances of X-VRF with different key life-time. Our extensive performance evaluation, analysis and implementation indicate the effectiveness of our proposed constructions in practice. Particularly, we demonstrate that X-VRF is the most efficient quantum-safe VRF with a maximum proof size of 3 KB and a possible TPS of 449 for a network of thousand nodes.

Let $\mathbb{F}_{\!q}$ be a finite field and $E_b\!: y^2 = x^3 + b$ be an ordinary (i.e., non-supersingular) elliptic curve (of $j$-invariant $0$) such that $\sqrt{b} \in \mathbb{F}_{\!q}$ and $q \not\equiv 1 \: (\mathrm{mod} \ 27)$. For example, these conditions are fulfilled for the curve BLS12-381 ($b=4$). It is a de facto standard in the real world pairing-based cryptography at the moment. This article provides a new constant-time hash function $H\!: \{0,1\}^* \to E_b(\mathbb{F}_{\!q})$ indifferentiable from a random oracle. Its main advantage is the fact that $H$ computes only one exponentiation in $\mathbb{F}_{\!q}$. In comparison, the previous fastest constant-time indifferentiable hash functions to $E_b(\mathbb{F}_{\!q})$ compute two exponentiations in $\mathbb{F}_{\!q}$. In particular, applying $H$ to the widely used BLS multi-signature with $m$ different messages, the verifier should perform only $m$ exponentiations rather than $2m$ ones during the hashing phase.

An (n,m)-function is a mapping from GF(2^n) to GF(2^m). Such functions have numerous applications across mathematics and computer science, and in particular are used as building blocks of block ciphers in symmetric cryptography. The classes of APN and AB functions have been identified as cryptographically optimal with respect to providing resistance against two of the most powerful known cryptanalytic attacks, namely differential and linear cryptanalysis. The classes of APN and AB functions are directly related to optimal objects in many other branches of mathematics, and have been a subject of intense study since at least the early 90's. Finding new constructions of these functions is hard; one of the most significant practical issues is that any tentatively new function must be proven inequivalent to all the known ones. Testing equivalence can be significantly simplified by computing invariants, i.e. properties that are preserved by the appropriate equivalence relation. In this paper, we survey the known invariants for CCZ- and EA-equivalence, with a particular focus on their utility in distinguishing between inequivalent instances of APN and AB functions. We evaluate each invariant with respect to how easy it is to implement in practice, how efficiently it can be calculated on a computer, and how well it can distinguish between distinct EA- and CCZ-equivalence classes.

The safety of the Bitcoin blockchain relies on strong network synchrony. Therefore, violating the blockchain safety requires strong adversaries who control a mining pool with 51% hash rate. In this paper, we show that the network synchrony does not hold in the real world Bitcoin network, which can be exploited to amortize the cost of various attacks. Towards that, first we construct the Bitcoin ideal world functionality to formally specify its ideal execution model in a synchronous network. We then develop a large-scale data collection system through which we connect with more than 36K IP addresses of the Bitcoin nodes and identify 359 mining nodes. We contrast the Bitcoin ideal functionality against real world measurements to expose network anomalies that can be exploited to optimize the existing attacks. Particularly, we observe high block propagation delay in the Bitcoin network causing weak network synchronization: on average, in 9.97 minutes, only 39% nodes have the up-to-date blockchain. Through a fine-grained analysis, we discover non-uniform block propagation delay among the mining nodes showing that the Bitcoin network is asynchronous. To realize the threat of asynchronous network, we present the HashSplit attack that allows an adversary to orchestrate concurrent mining on multiple branches of the blockchain to violate common prefix and chain quality properties. We also propose the attack countermeasures by releasing a Bitcoin Core version that closely models the Bitcoin ideal functionality. Our measurements, theoretical modeling, pro-posed attack, and countermeasures open new directions in the security evaluation of Bitcoin and similar blockchain systems

The one-time-pad (OTP) is a classical yet the strongest cipher. Although the OTP offers perfect secrecy and is quantum-safe, it has cryptographic as well as operational weaknesses. Cryptographically its encryption is malleable. Operationally a key used more than once by mistake can lead to successful breaking of the OTP. Hence, there is a need for extensions of OTP to address these two weaknesses simultaneously keeping all the strength of OTP intact. To address this need, we propose two extensions of OTP. In the process we also prove a relation between block ciphers and Latin rectangles.

This paper presents HashWires, a hash-based range proof protocol that is applicable in settings for which there is a trusted third party (typically a credential issuer) that can generate commitments. We refer to these as "credential-based" range proofs (CBRPs). HashWires improves upon hashchain solutions that are typically restricted to micro-payments for small interval ranges, achieving an exponential speedup in proof generation and verification time. In terms of proof size and computational cost, we show that HashWires compares favorably against Bulletproofs for both 32- and 64-bit numeric values. Although CBRPs are inherently less flexible than general zero-knowledge range proofs, we provide a number of applications in which a credential issuer can leverage HashWires to provide range proofs for private values, without having to rely on heavyweight cryptographic tools and assumptions.

Physical attacks are serious threats to hardware implementations of any strong cryptographic primitive. Particularly, fault injection attack is considered as a powerful technique to successfully attack embedded cryptographic implementations since various fault injection mechanisms from simple clock glitches to more advanced techniques like laser fault injection can lead to devastating attacks, even with just a single successfully injected fault. Given these critical attack vectors, researchers in academia and industry came up with a long list of dedicated countermeasures to thwart such attacks. However, the validation of proposed countermeasures is mostly performed on custom adversary models that are often not tightly coupled with the actual physical behavior of available fault injection mechanisms and techniques and, hence, fail to model the reality accurately. Furthermore, using custom models complicates comparison between different designs and evaluation results. As a consequence, we aim to close this gap by proposing a simple, generic, and consolidated fault injection adversary model in this work that can be perfectly tailored to existing fault injection mechanisms and their physical behavior in hardware. To demonstrate the advantages of our adversary model, we apply it to a cryptographic primitive (i.e., an ASCON S-box) and evaluate it based on different attack vectors. We further show that our proposed adversary model can be used and integrated into the state-of-the-art fault verification tool VerFI. Finally, we provide a discussion on the benefits and differences of our approach compared to already existing evaluation methods and briefly discuss limitations of current available verification tools.

A sizable body of work has identified the importance of architecture and application level security when using logic locking, a family of module level supply chain security techniques, to secure processor ICs. However, prior logic locking research proposes configuring logic locking using only module level considerations. To begin our work, we perform a systematic design space exploration of logic locking in modules throughout a processor IC. This exploration shows that locking with only module level considerations cannot guarantee architecture/application level security, regardless of the locking technique used. To remedy this, we propose a tool-driven security-aware approach to enhance the 2 most effective candidate locking locations, on-chip memory and data path. We show that through minor design modifications of the on-chip memory and data path architecture, one can exponentially improve the architecture/application level security of prior locking art with only a modest design overhead. Underlying our design space exploration and security-aware design approach is ObfusGEM, an open-source logic locking simulation framework released with this work to quantitatively evaluate the architectural effectiveness of logic locking in custom processor architecture configurations.

The Schnorr-Lyubashevsky approach has been shown able to produce secure and efficient signature schemes without trapdoors in the lattice-based setting, exploiting small vectors in the Euclidean metric and rejection sampling in the signature generation. Translating such an approach to the code-based setting has revealed to be challenging, especially for codes in the Hamming metric. In this paper, we propose a novel adaptation of the Schnorr-Lyubashevsky framework to the code-based setting, by relying on random non-binary linear codes and vectors with restricted entries to produce signatures. We provide some preliminary arguments to assess the security of the new scheme and to compute its parameters. We show that it achieves compact and competitive key and signature sizes, even without resorting to structured random codes.

Designing a block cipher or cryptographic permutation can be approached in many different ways. One such approach, popularized by AES, consists in grouping the bits along the S-box boundaries, e.g., in bytes, and in consistently processing them in these groups. This aligned approach leads to hierarchical structures like superboxes that make it possible to reason about the differential and linear propagation properties using combinatorial arguments. In contrast, an unaligned approach avoids any such grouping in the design of transformations. However, without hierarchical structure, sophisticated computer programs are required to investigate the differential and linear propagation properties of the primitive. In this paper, we formalize this notion of alignment and study four primitives that are exponents of different design strategies. We propose a way to analyze the interactions between the linear and the nonlinear layers w.r.t. the differential and linear propagation, and we use it to systematically compare the four primitives using non-trivial computer experiments. We show that alignment naturally leads to different forms of clustering, e.g., of active bits in boxes, of two-round trails in activity patterns, and of trails in differentials and linear approximations.

In this paper, we study dedicated quantum collision attacks on SHA-256 and SHA-512 for the first time. The attacks reach 38 and 39 steps, respectively, which significantly improve the classical attacks for 31 and 27 steps. Both attacks adopt the framework of the previous work that converts many semi-free-start collisions into a 2-block collision, and are faster than the generic attack in the cost metric of time-space tradeoff. We observe that the number of required semi-free-start collisions can be reduced in the quantum setting, which allows us to convert the previous classical 38 and 39 step semi-free-start collisions into a collision. The idea behind our attacks is simple and will also be applicable to other cryptographic hash functions.

Due to their use in crypto-currencies, threshold ECDSA signatures have received much attention in recent years. Though efficient solutions now exist both for the two party, and the full threshold scenario, there is still much room for improvement, be it in terms of protocol functionality, strengthening security or further optimising efficiency. In the past few months, a range of protocols have been published, allowing for a non interactive -- and hence extremely efficient -- signing protocol; providing new features, such as identifiable aborts (parties can be held accountable if they cause the protocol to fail), fairness in the honest majority setting (all parties receive output or nobody does) and other properties. In some cases, security is proven in the strong simulation based model. We combine ideas from the aforementioned articles with the suggestion of Castagnos \textit{et al.} (PKC 2020) to use the class group based $\mathsf{CL}$ framework so as to drastically reduce bandwidth consumption. Building upon this latter protocol we present a new, maliciously secure, full threshold ECDSA protocol that achieving additional features without sacrificing efficiency. Our most basic protocol boasts a non interactive signature algorithm and identifiable aborts. We also propose a more advanced variant that also achieves adaptive security (for the $n$-out-of-$n$ case) and proactive security. Our resulting constructions improve upon state of the art Paillier's based realizations achieving similar goals by up to a 10 factor in bandwidth consumption.

At CHES 2016, Bos, Hubain, Michiels and Teuwen showed that most of existing white-box implementations are easily broken by standard side-channel attacks. A natural idea to apply the well-developed side-channel countermeasure - linear masking schemes - leaves implementations vulnerable to linear algebraic attacks which exploit absence of noise in the white-box setting and are applicable for any order of linear masking. At ASIACRYPT 2018, Biryukov and Udovenko proposed a security model (BU-model for short) for protection against linear algebraic attacks and a new quadratic masking scheme which is provably secure in this model. However, countermeasures against higher-degree attacks were left as an open problem. In this work, we study the effectiveness of another well-known side-channel countermeasure - shuffling - against linear and higher-degree algebraic attacks in the white-box setting. First, we extend the classic shuffling to include dummy computation slots and show that this is a crucial component for protecting against the algebraic attacks. We quantify and prove the security of dummy shuffling against the linear algebraic attack in the BU-model. We introduce a refreshing technique for dummy shuffling and show that it allows to achieve close to optimal protection in the model for arbitrary degrees of the attack, thus solving the open problem of protection against the algebraic attack in the BU-model. Furthermore, we describe an interesting proof-of-concept construction that makes the slot function public (while keeping the shuffling indexes private). A variant of this construction was used, among other countermeasures, in the challenge \#100, one of the three white-box AES challenges from the CHES 2019 CTF / WhibOx 2019 contest that proved to be challenging for the attackers.

We present a novel approach for blockchain asset owners to reclaim their funds in case of accidental private-key loss or transfer to a mistyped address. Our solution can be deployed upon failure or absence of proactively implemented backup mechanisms, such as secret sharing and cold storage. The main advantages against previous proposals is it does not require any prior action from users and works with both single-key and multi-sig accounts. We achieve this by a 3-phase Commit() -> Reveal() -> Claim() - or - Challenge() smart contract that enables accessing funds of addresses for which the spending key is not available. We provide an analysis of the threat and incentive models and formalize the concept of reactive KEy-Loss Protection (KELP).

Indifferentiability is used to analyze the security of constructions of idealized objects, such as random oracles or ideal ciphers. Reset indifferentiability is a strengthening of plain indifferentiability which is applicable in far more scenarios, but is often considered too strong due to significant impossibility results. Our main results are: - Under weak reset indifferentiability, ideal ciphers imply (fixed size) random oracles and random oracle domain shrinkage is possible. We thus show that reset indifferentiability is more useful than previously thought. - We lift our analysis to the quantum setting showing that ideal ciphers imply random oracles under quantum indifferentiability. - Despite Shor's algorithm, we observe that generic groups are still meaningful quantumly, showing that they are quantumly (reset) indifferentiable from ideal ciphers; combined with the above, cryptographic groups yield post-quantum symmetric key cryptography. In particular, we obtain a plausible post-quantum random oracle that is a subset-product followed by two modular reductions.

At CRYPTO'19, Gohr proposed a new cryptanalysis strategy based on the utilisation of machine learning algorithms. Using deep neural networks, he managed to build a neural based distinguisher that surprisingly surpassed state-of-the-art cryptanalysis efforts on one of the versions of the well studied NSA block cipher speck (this distinguisher could in turn be placed in a larger key recovery attack). While this work opens new possibilities for machine learning-aided cryptanalysis, it remains unclear how this distinguisher actually works and what information is the machine learning algorithm deducing. The attacker is left with a black-box that does not tell much about the nature of the possible weaknesses of the algorithm tested, while hope is thin as interpretability of deep neural networks is a well-known difficult task. In this article, we propose a detailed analysis and thorough explanations of the inherent workings of this new neural distinguisher. First, we studied the classified sets and tried to find some patterns that could guide us to better understand Gohr's results. We show with experiments that the neural distinguisher generally relies on the differential distribution on the ciphertext pairs, but also on the differential distribution in penultimate and antepenultimate rounds. In order to validate our findings, we construct a distinguisher for speck cipher based on pure cryptanalysis, without using any neural network, that achieves basically the same accuracy as Gohr's neural distinguisher and with the same efficiency (therefore improving over previous non-neural based distinguishers). Moreover, as another approach, we provide a machine learning-based distinguisher that strips down Gohr's deep neural network to a bare minimum. We are able to remain very close to Gohr's distinguishers' accuracy using simple standard machine learning tools. In particular, we show that Gohr's neural distinguisher is in fact inherently building a very good approximation of the Differential Distribution Table (DDT) of the cipher during the learning phase, and using that information to directly classify ciphertext pairs. This result allows a full interpretability of the distinguisher and represents on its own an interesting contribution towards interpretability of deep neural networks. Finally, we propose some method to improve over Gohr's work and possible new neural distinguishers settings. All our results are confirmed with experiments we have been conducted on speck block cipher (source code available online).

Shortly after the introduction of zero-knowledge proofs, Goldreich, Micali and Wigderson (CRYPTO '86) demonstrated their wide applicability by constructing zero-knowledge proofs for the NP-complete problem of graph 3-coloring. A long-standing open question has been whether parallel repetition of their protocol preserves zero knowledge. In this work, we answer this question in the negative, assuming a standard cryptographic assumption (i.e., the hardness of learning with errors (LWE)). Leveraging a connection observed by Dwork, Naor, Reingold, and Stockmeyer (FOCS '99), our negative result is obtained by making positive progress on a related fundamental problem in cryptography: securely instantiating the Fiat-Shamir heuristic for eliminating interaction in public-coin interactive protocols. A recent line of works has shown how to instantiate the heuristic securely, albeit only for a limited class of protocols. Our main result shows how to instantiate Fiat-Shamir for parallel repetitions of much more general interactive proofs. In particular, we construct hash functions that, assuming LWE, securely realize the Fiat-Shamir transform for the following rich classes of protocols: - The parallel repetition of any ``commit-and-open'' protocol (such as the GMW protocol mentioned above), when a specific (natural) commitment scheme is used. Commit-and-open protocols are a ubiquitous paradigm for constructing general purpose public-coin zero knowledge proofs. - The parallel repetition of any base protocol that (1) satisfies a stronger notion of soundness called round-by-round soundness, and (2) has an efficient procedure, using a suitable trapdoor, for recognizing ``bad verifier randomness'' that would allow the prover to cheat. Our results are obtained by establishing a new connection between the Fiat-Shamir transform and list-recoverable codes. In contrast to the usual focus in coding theory, we focus on a parameter regime in which the input lists are extremely large, but the rate can be small. We give a (probabilistic) construction based on Parvaresh-Vardy codes (FOCS '05) that suffices for our applications.

There is a huge gap between the upper and lower bounds on the share size of secret-sharing schemes for arbitrary $n$-party access structures, and consistent with our current knowledge the optimal share size can be anywhere between polynomial in $n$ and exponential in $n$. For linear secret-sharing schemes, we know that the share size for almost all $n$-party access structures must be exponential in $n$. Furthermore, most constructions of efficient secret-sharing schemes are linear. We would like to study larger classes of secret-sharing schemes with two goals. On one hand, we want to prove lower bounds for larger classes of secret-sharing schemes, possibly shedding some light on the share size of general secret-sharing schemes. On the other hand, we want to construct efficient secret-sharing schemes for access structures that do not have efficient linear secret-sharing schemes. Given this motivation, Paskin-Cherniavsky and Radune (ITC'20) defined and studied a new class of secret-sharing schemes in which the shares are generated by applying degree-$d$ polynomials to the secret and some random field elements. The special case $d=1$ corresponds to linear and multi-linear secret-sharing schemes. We define and study two additional classes of polynomial secret-sharing schemes: (1) schemes in which for every authorized set the reconstruction of the secret is done using polynomials and (2) schemes in which both sharing and reconstruction are done by polynomials. For linear secret-sharing schemes, schemes with linear sharing and schemes with linear reconstruction are equivalent. We give evidence that for polynomial secret-sharing schemes, schemes with polynomial sharing are probably stronger than schemes with polynomial reconstruction. We also prove lower bounds on the share size for schemes with polynomial reconstruction. On the positive side, we provide constructions of secret-sharing schemes and conditional disclosure of secrets (CDS) protocols with quadratic sharing and reconstruction. We extend a construction of Liu et al. (CRYPTO'17) and construct optimal quadratic $k$-server CDS protocols for functions $f:[N]^k\rightarrow \{0,\1}$ with message size $O(N^{(k-1)/3})$. We show how to transform our quadratic $k$-server CDS protocol to a robust CDS protocol, and use the robust CDS protocol to construct quadratic secret-sharing schemes for arbitrary access structures with share size $O(2^{0.705n})$; this is better than the best known share size of $O(2^{0.7576n})$ for linear secret-sharing schemes and worse than the best known share size of $O(2^{0.585n})$ for general secret-sharing schemes.

In recent years, Ethereum gained tremendously in popularity, growing from a daily transaction average of 10K in January 2016 to an average of 500K in January 2020. Similarly, smart contracts began to carry more value, making them appealing targets for attackers. As a result, they started to become victims of attacks, costing millions of dollars. In response to these attacks, both academia and industry proposed a plethora of tools to scan smart contracts for vulnerabilities before deploying them on the blockchain. However, most of these tools solely focus on detecting vulnerabilities and not attacks, let alone quantifying or tracing the number of stolen assets. In this paper, we present Horus, a framework that empowers the automated detection and investigation of smart contract attacks based on logic-driven and graph-driven analysis of transactions. Horus provides quick means to quantify and trace the flow of stolen assets across the Ethereum blockchain. We perform a large-scale analysis of all the smart contracts deployed on Ethereum until May 2020. We identified 1,888 attacked smart contracts and 8,095 adversarial transactions in the wild. Our investigation shows that the number of attacks did not necessarily decrease over the past few years, but for some vulnerabilities remained constant. Finally, we also demonstrate the practicality of our framework via an in-depth analysis on the recent Uniswap and Lendf.me attacks.

Cryptocurrency exchange services are either trusted central entities that have been routinely hacked (losing over 8 billion USD), or decentralized services that make all orders public before they are settled. The latter allows market participants to ``front run'' each other, an illegal operation in most jurisdictions. We extend the ``Insured MPC'' approach of Baum et al. (FC 2020) to construct an efficient universally composable privacy preserving decentralized exchange where a set of servers run private cross-chain exchange order matching in an outsourced manner, while being financially incentivised to behave honestly. Our protocol allows for exchanging assets over multiple public ledgers, given that users have access to a ledger that supports standard public smart contracts. If parties behave honestly, the on-chain complexity of our construction is as low as that of performing the transactions necessary for a centralized exchange. In case malicious behavior is detected, users are automatically refunded by malicious servers at low cost. Thus, an actively corrupted majority can only mount a denial-of-service attack that makes exchanges fail, in which case the servers are publicly identified and punished, while honest clients do not to lose their funds. For the first time in this line of research, we report experimental results on the MPC building block, showing the approach is efficient enough to be used in practice.

Supersingular isogeny Diffie-Hellman key exchange (SIDH) is a post-quantum protocol based on the presumed hardness of computing an isogeny between two supersingular elliptic curves given some additional torsion point information. Unlike other isogeny-based protocols, SIDH has been widely believed to be immune to subexponential quantum attacks because of the non-commutative structure of the endomorphism rings of supersingular curves. We contradict this commonly believed misconception in this paper. More precisely, we highlight the existence of an abelian group action on the SIDH key space, and we show that for sufficiently unbalanced and overstretched SIDH parameters, this action can be efficiently computed (heuristically) using the torsion point information revealed in the protocol. This reduces the underlying hardness assumption to a hidden shift problem instance which can be solved in quantum subexponential time. We formulate our attack in a new framework allowing the inversion of one-way functions in quantum subexponential time provided a malleability oracle with respect to some commutative group action. This framework unifies our new attack with earlier subexponential quantum attacks on isogeny-based protocols, and it may be of further interest for cryptanalysis.

In a seminal work, Micali (FOCS 1994) gave the first succinct non-interactive argument (SNARG) in the random oracle model (ROM). The construction combines a PCP and a cryptographic commitment, and has several attractive features: it is plausibly post-quantum; it can be heuristically instantiated via lightweight cryptography; and it has a transparent (public-coin) parameter setup. However, it also has a significant drawback: a large argument size. In this work, we provide a new construction that achieves a smaller argument size. This is the first progress on the Micali construction since it was introduced over 25 years ago. A SNARG in the ROM is *$(t,\epsilon)$-secure* if every t-query malicious prover can convince the verifier of a false statement with probability at most ε. For $(t,\epsilon)$-security, the argument size of all known SNARGs in the ROM (including Micali's) is $\tilde{O}((\log (t/\epsilon))^2)$ bits, *even* if one were to rely on conjectured probabilistic proofs well beyond current techniques. In practice, these costs lead to SNARGs that are much larger than constructions based on other (pre-quantum and costly) tools. This has led many to believe that SNARGs in the ROM are inherently quadratic. We show that this is not the case. We present a SNARG in the ROM with a sub-quadratic argument size: $\tilde{O}(\log (t/\epsilon) \cdot \log t)$. Our construction relies on a strong soundness notion for PCPs and a weak binding notion for commitments. We hope that our work paves the way for understanding if a linear argument size, that is $O(\log (t/\epsilon))$, is achievable in the ROM.

We show the following generic result. Whenever a quantum query algorithm in the quantum random-oracle model outputs a classical value $t$ that is promised to be in some tight relation with $H(x)$ for some $x$, then $x$ can be efficiently extracted with almost certainty. The extraction is by means of a suitable simulation of the random oracle and works *online*, meaning that it is *straightline*, i.e., without rewinding, and *on-the-fly*, i.e., during the protocol execution and without disturbing it. The technical core of our result is a new commutator bound that bounds the operator norm of the commutator of the unitary operator that describes the evolution of the compressed oracle (which is used to simulate the random oracle above) and of the measurement that extracts $x$. We show two applications of our generic online extractability result. We show *tight* online extractability of commit-and-open $\Sigma$-protocols in the quantum setting, and we offer the first non-asymptotic post-quantum security proof of the *textbook* Fujisaki-Okamoto transformation, i.e, without adjustments to facilitate the proof.

This paper studies how to incorporate small information leakages (called “hints”) into information-set decoding (ISD) algorithms. In particular, the influence of these hints on solving the (n, k, t)-syndrome-decoding problem (SDP), i.e., generic syndrome decoding of a code of length n, dimension k, and an error of weight t, is analyzed. We motivate all hints by leakages obtainable through realistic side-channel attacks on code-based post-quantum cryptosystems. One class of studied hints consists of partial knowledge of the error or message, which allow to reduce the length, dimension, or error weight using a suitable transformation of the problem. As a second class of hints, we assume that the Hamming weights of subblocks of the error are known, which can be motivated by a template attack. We present adapted ISD algorithms for this type of leakage. For each third-round code-based NIST submission (Classic McEliece, BIKE, HQC), we show how many hints of each type are needed to reduce the work factor below the claimed security level. E.g., for Classic McEliece mceliece348864, the work factor is reduced below 2^128 for 175 known message entries, 9 known error locations, 650 known error-free positions, or known Hamming weights of 29 subblocks of roughly equal size.

We prove two classes of lower bounds on the communication complexity of information-theoretically secure multiparty computation. The first lower bound applies to perfect passive secure multiparty computation, in the standard model with $n=2t+1$ parties of which $t$ are corrupted. We show a lower bound that applies to secure evaluation of any function, assuming that each party can choose to learn to learn or not learn the output. Specifically, we show that there is a function $H^*$ such that for any protocol that evaluates $y_i=b_i \cdot f(x_1,...,x_n)$ with perfect passive security (where $b_i$ is a private boolean input), the total communication must be at least $\frac{1}{2} \sum_{i=1}^n H_f^*(x_i)$ bits of information. The second lower bound applies to the perfect maliciously secure setting with $n=3t+1$ parties. We show that for any $n$ and all large enough $S$, there exists a reactive functionality $F_S$ taking an $S$-bit string as input (and with short output) such that any protocol implementing $F_S$ with perfect malicious security must communicate $\Omega(nS)$ bits. Since the functionalities we study can be implemented with linear size circuits, the result can equivalently be stated as follows: for any $n$ and all large enough $g \in \mathbb{N}$ there exists a reactive functionality $F_C$ doing computation specified by a Boolean circuit $C$ with $g$ gates, where any perfectly secure protocol implementing $F_C$ must communicate $\Omega(n g)$ bits. The results easily extends to constructing similar functionalities defined over any fixed finite field. Using known techniques, we also show an upper bound that matches the lower bound up to a constant factor (existing upper bounds are a factor $\log n$ off for Boolean circuits). Both results also extend to the case where the threshold $t$ is suboptimal. Namely if $n=kt+s$ the bound is weakened by a factor $O(s)$, which corresponds to known optimizations via packed secret-sharing.

Several recent proposals of efficient public-key encryption are based on variants of the polynomial learning with errors problem ($\mathsf{PLWE}^f$) in which the underlying polynomial ring $\mathbb{Z}_q[x]/f$ \ is replaced with the (related) modular integer ring $\mathbb{Z}_{f(q)}$; the corresponding problem is known as Integer Polynomial Learning with Errors ($\mathsf{I-PLWE}^f$). Cryptosystems based on $\mathsf{I-PLWE}^f$ and its variants can exploit optimised big-integer arithmetic to achieve good practical performance, as exhibited by the $\mathsf{ThreeBears}$ cryptosystem. Unfortunately, the average-case hardness of $\mathsf{I-PLWE}^f$ and its relation to more established lattice problems have to date remained unclear. We describe the first polynomial-time average-case reductions for the search variant of $\mathsf{I-PLWE}^f$, proving its computational equivalence with the search variant of its counterpart problem $\mathsf{PLWE}^f$. Our reductions apply to a large class of defining polynomials $f$. To obtain our results, we employ a careful adaptation of Rényi divergence analysis techniques to bound the impact of the integer ring arithmetic carries on the error distributions. As an application, we present a deterministic public-key cryptosystem over integer rings. Our cryptosystem, which resembles $\mathsf{ThreeBears}$, enjoys one-way (OW-CPA) security provably based on the search variant of $\mathsf{I-PLWE}^f$.

A proxy re-encryption scheme can be executed by a semi-trusted proxy, so that we can transform a ciphertext encrypted with a key to another ciphertext encrypted with different key without allowing the proxy to access the plaintext. A method to implement a secure proxy re-encryption is by first converting the plaintext to an intermediate form by using an all or nothing transform (AONT). In this paper, we describe an improved proxy re-encryption scheme for symmetric cipher by advocating the usage of a variant of the AONT function in the proxy re-encryption scheme. We show that the scheme secure under Chosen Plaintext Attack (CPA) for all possible types of attackers.

Galois and Fibonacci are two different configurations of stream ciphers. Because the Fibonacci configuration is more convenient for cryptanalysis, most ciphers are designed as Fibonacci-configured. So far, although many transformations between Fibonacci and Galois configurations have been proposed, there is no sufficient analysis of their respective hardware performance. The 128-bit secret key stream cipher Espresso, its Fibonacciconfigured variant and linear Fibonacci variant have a similar security level. We take them as examples to design the optimization strategies in terms of both area and throughput, investigate which configuration is more efficient in a certain aspect. The Fibonacci-configured Espresso occupies 52 slices on Spartan-3 and 22 slices on Virtex-7, which are the minimum solutions among those three Espresso schemes or even smaller than 80-bit secret key ciphers. Based on our throughput improvement strategy, parallel Espresso design can perform 4.1 Gbps on Virtex-7 FPGA and 1.9 Gbps on Spartan-3 FPGA at most. In brief, the Fibonacci cipher is more suitable for extremely resource-constrained or extremely high-throughput applications, while the Galois cipher seems like a compromise between area and speed. Besides, the transformation from nonlinear feedback to linear feedback is not recommended for any hardware implementations.

We present the first homomorphic secret sharing (HSS) construction that simultaneously (1) has negligible correctness error, (2) supports integers from an exponentially large range, and (3) relies on an assumption not known to imply FHE --- specifically, the Decisional Composite Residuosity (DCR) assumption. This resolves an open question posed by Boyle, Gilboa, and Ishai (Crypto 2016). Homomorphic secret sharing is analogous to fully-homomorphic encryption, except the ciphertexts are shared across two non-colluding evaluators. Previous constructions of HSS either had non-negligible correctness error and polynomial-size plaintext space or were based on the stronger LWE assumption. We also present two applications of our technique: a multi-server ORAM with constant bandwidth overhead, and a rate-1 trapdoor hash function with negligible error rate.

Oblivious Pseudorandom Function (OPRF) is a protocol between a client holding input x and a server holding key k for a PRF F. At the end, the client learns F_k(x) and nothing else while the server learns nothing. OPRF's have found diverse applications as components of larger protocols, and the currently most efficient instantiation, with security proven in the UC model, is F_k(x)=H2(x,(H1(x))^k) computed using so-called exponential blinding, i.e., the client sends a=(H1(x))^r for random r, the server responds b=a^k, which the client ublinds as v=b^{1/r} to compute F_k(x)=H2(x,v). However, this protocol requires two variable-base exponentiations on the client, while a more efficient multiplicative blinding scheme replaces one or both client exponentiations with fixed-base exponentiation, leading to the decrease of the client's computational cost by a factor between two to six, depending on pre-computation. We analyze the security of the above OPRF with multiplicative blinding, showing surprising weaknesses that offer attack avenues which are not present using exponential blinding. We characterize the security of this OPRF implementation as a "Revised OPRF" functionality, a relaxation of UC OPRF functionality used in prior work. On the positive side, we show that the Revised OPRF suffices for the security of OPAQUE, the asymmetric PAKE protocol, hence allowing OPAQUE the computational advantages of multiplicative blinding. Unfortunately, we also show examples of other OPRF applications which become insecure when using such blinding. The conclusion is that usage of multiplicative blinding for F_k(x) defined as above, in settings where correct value g^k (needed for multiplicative blinding) is not authenticated, and OPRF inputs are of low entropy, must be carefully analyzed, or avoided all together. We complete the picture by showing a simple and safe alternative definition of function F_k(x) which offers (full) UC OPRF security using either form of blinding.

SIDH/SIKE-style protocols benefit from key compression to minimize their bandwidth requirements, but proposed key compression mechanisms rely on computing bilinear pairings. Pairing computation is a notoriously expensive operation, and, unsurprisingly, it is typically one of the main efficiency bottlenecks in SIDH key compression, incurring processing time penalties that are only mitigated at the cost of trade-offs with precomputed tables. We address this issue by describing how to compress isogeny-based keys without pairings. As a bonus, we also substantially reduce the storage requirements of other operations involved in key compression.

In this work, we study the compatibility of any key generation or setup algorithm. We focus on the specific case of encryption, and say that a key generation algorithm KeyGen is X-compatible (for X \in {CPA, CCA1, CCA2}) if there exist encryption and decryption algorithms that together with KeyGen, result in an X-secure public-key encryption scheme. We study the following question: Is every CPA-compatible key generation algorithm also CCA-compatible? We obtain the following answers: - Every sub-exponentially CPA-compatible KeyGen algorithm is CCA1-compatible, assuming the existence of hinting PRGs and sub-exponentially secure keyless collision resistant hash functions. - Every sub-exponentially CPA-compatible KeyGen algorithm is also CCA2-compatible, assuming the existence of non-interactive CCA2 secure commitments, in addition to sub-exponential security of the assumptions listed in the previous bullet. Here, sub-exponentially CPA-compatible KeyGen refers to any key generation algorithm for which there exist encryption and decryption algorithms that result in a CPA-secure public-key encryption scheme {\em against sub-exponential adversaries}. This gives a way to perform CCA secure encryption given any public key infrastructure that has been established with only (sub-exponential) CPA security in mind. The resulting CCA encryption makes black-box use of the CPA scheme and all other underlying primitives.

Post-quantum cryptography or PQC is a trend that has a deserved NIST status, and which aims to be resistant to quantum computer attacks like Shor and Grover algorithms. We choose to follow a non-standard way to achieve PQC: taking any standard asymmetric protocol and replacing numeric field arithmetic with GF-256 field operations. By doing so, it is easy to implement R-propped asymmetric systems as present and former papers show. Here R stands for Rijndael as we work over the AES field. This approach yields secure post-quantum protocols since the resulting multiplicative monoid resists known quantum algorithm and classical linearization attacks like Tsaban Algebraic Span or Romankov linearization attacks. Here we develop an original group-based digital signature protocol and R-propped it. The protocol security relies on the intractability of a generalized discrete log problem, combined with the power sets of algebraic ring extension tensors. The semantic security and classical and quantum security levels are discussed. Finally, we present a numerical example of the proposed protocol.

Trusted execution enviroments (TEEs) enable secure execution of program on untrusted hosts and cryptographically attest the correctness of outputs. As these are complex systems, it is hard to capture the exact security achieved by protocols employing TEEs. Crucially TEEs are typically employed in multiple protocols at the same time, thus composable security (with global subroutines) is a natural goal for such systems. We show that under an attested execution setup $G_\mathsf{att}$ we can realise cryptographic functionalities that are unrealizable in the standard model. We propose a new primitive of Functional Encryption for Stateful and Randomised functionalities (FESR) and an associated protocol, Steel, that realizes it. We show that Steel UC-realises FESR in the universal composition with global subroutines model (TCC 2020). Our work is also a validation of the compositionality of earlier work (Iron), CCS 2017) capturing (non-stateful) hardware-based functional encryption. As the existing functionality for attested execution of Pass et al. (Eurocrypt 2017) is too strong for real world use, we propose a weaker functionality that allows the adversary to conduct rollback and forking attacks. We show that the stateful variant of Steel, contrary to the stateless variant corresponding to Iron, is not secure in this setting and propose several mitigation techniques.

Updatable encryption (UE) allows a third party to periodically rotate encryption keys from one epoch to another without the need to download, decrypt, re-encrypt and upload already encrypted data by a client. Updating those outsourced ciphertexts is carried out via the use of so-called update tokens which in turn are generated during key rotation and can be sent (publicly) to the third party. The arguably most efficient variant of UE is ciphertext-independent UE as the key rotation does not depend on the outsourced ciphertexts which makes it particularly interesting in scenarios where access to (information of the) ciphertexts is not possible during key rotation. Available security notions for UE cannot guarantee any form of forward security (i.e., old ciphertexts are in danger after key leakage). Counter-intuitively, forward security would violate correctness, as ciphertexts should be updatable ad-infinitum given the update token. In this work, we investigate if we can have at least some form of "controlled" forward security to mitigate the following shortcoming: an adversary would record available information (i.e., some ciphertexts, all update tokens) and simply would wait for a single key leakage to decrypt all data ever encrypted. Our threefold contribution is as follows: a) First, we introduce an epoch-based UE CPA security notion to allow fine-grained updatability. It covers the concept of expiry epochs, i.e., ciphertexts can lose the ability of being updatable via a token after a certain epoch has passed. This captures the above mentioned shortcoming as the encrypting party can decide how long a ciphertext can be updatable (and, hence, decryptable). b) Second, we introduce a novel approach of constructing UE which significantly departs from previous ones and in particular views UE from the perspective of puncturable encryption (Green and Miers, S&P'15). We define tag-inverse puncturable encryption as a new variant that generalizes UE and may be of independent interest. c) Lastly, we present and prove secure the first UE scheme with the aforementioned properties. It is constructed via tag-inverse puncturable encryption and instantiated from standard assumptions. As it turned out, constructing such puncturing schemes is not straightforward and we require adapted proof techniques. Surprisingly, as a special case, this yields the first backwards-leak UE scheme with sub-linear ciphertexts from standard assumptions (an open problem posted in two recent works by Jiang Galteland and Pan & Miao et al., PKC'23).

Motivated by new applications such as secure Multi-Party Computation (MPC), Fully Homomorphic Encryption (FHE), and Zero-Knowledge proofs (ZK), the need for symmetric encryption schemes that minimize the number of field multiplications in their natural algorithmic description is apparent. This development has brought forward many dedicated symmetric encryption schemes that minimize the number of multiplications in GF(2^n) or GF(p), with p being prime. These novel schemes have lead to new cryptanalytic insights that have broken many of said schemes. Interestingly, to the best of our knowledge, all of the newly proposed schemes that minimize the number of multiplications use those multiplications exclusively in S-boxes based on a power mapping that is typically x^3 or x^{-1}. Furthermore, most of those schemes rely on complex and resource-intensive linear layers to achieve a low multiplication count. In this paper, we present Ciminion, an encryption scheme minimizing the number of field multiplications in large binary or prime fields, while using a very lightweight linear layer. In contrast to other schemes that aim to minimize field multiplications in GF(2^n) or GF(p), Ciminion relies on the Toffoli gate to improve the non-linear diffusion of the overall design. In addition, we have tailored the primitive for the use in a Farfalle-like construction in order to minimize the number of rounds of the used primitive, and hence, the number of field multiplications as far as possible.

In this work we present a new construction for a batched Oblivious Pseudorandom Function (OPRF) based on Vector-OLE and the PaXoS data structure. We then use it in the standard transformation for achieving Private Set Intersection (PSI) from an OPRF. Our overall construction is highly efficient with $O(n)$ communication and computation. We demonstrate that our protocol can achieve malicious security at only a very small overhead compared to the semi-honest variant. For input sizes $n = 2^{20}$, our malicious protocol needs 6.2 seconds and less than 59 MB communication. This corresponds to under 450 bits per element, which is the lowest number for any published PSI protocol (semi-honest or malicious) to date. Moreover, in theory our semi-honest (resp. malicious) protocol can achieve as low as 219 (resp. 260) bits per element for $n=2^{20}$ at the added cost of interpolating a polynomial over $n$ elements. As a second contribution, we present an extension where the output of the PSI is secret-shared between the two parties. This functionality is generally referred to as Circuit-PSI. It allows the parties to perform a subsequent MPC protocol on the secret-shared outputs, e.g., train a machine learning model. Our circuit PSI protocol builds on our OPRF construction along with another application of the PaXoS data structure. It achieves semi-honest security and allows for a highly efficient implementation, up to 3x faster than previous work.

We prove that the Module Learning With Errors (M-LWE) problem with binary secrets and rank $d$ is at least as hard as the standard version of M-LWE with uniform secret and rank $k$, where the rank increases from $k$ to $d \geq (k+1)\log_2 q + \omega(\log_2 n)$, and the Gaussian noise from $\alpha$ to $\beta = \alpha \cdot \Theta(n^2\sqrt{d})$, where $n$ is the ring degree and $q$ the modulus. Our work improves on the recent work by Boudgoust et al. in 2020 by a factor of $\sqrt{md}$ in the Gaussian noise, where $m$ is the number of given M-LWE samples, when $q$ fulfills some number-theoretic requirements. We use a different approach than Boudgoust et al. to achieve this hardness result by adapting the previous work from Brakerski et al. in 2013 for the Learning With Errors problem to the module setting. The proof applies to cyclotomic fields, but most results hold for a larger class of number fields, and may be of independent interest.

Sealed-bid auctions are a common way of allocating an asset among a set of parties but require trusting an auctioneer who analyses the bids and determines the winner. Many privacy-preserving computation protocols for auctions have been proposed to eliminate the need for a trusted third party. However, they lack fairness, meaning that the adversary learns the outcome of the auction before honest parties and may choose to make the protocol fail without suffering any consequences. In this work, we propose efficient protocols for both first and second-price sealed-bid auctions with fairness against rational adversaries, leveraging secret cryptocurrency transactions and public smart contracts. In our approach, the bidders jointly compute the winner of the auction while preserving the privacy of losing bids and ensuring that cheaters are financially punished by losing a secret collateral deposit. We guarantee that it is never profitable for rational adversaries to cheat by making the deposit equal to the bid plus the cost of running the protocol, i.e., once a party commits to a bid, it is guaranteed that it has the funds and it cannot walk away from the protocol without forfeiting the bid. Moreover, our protocols ensure that the winner is determined and the auction payments are completed even if the adversary misbehaves so that it cannot force the protocol to fail and then rejoin the auction with an adjusted bid. In comparison to the state-of-the-art, our constructions are both more efficient and furthermore achieve stronger security properties, i.e., fairness. Interestingly, we show how the second-price can be computed with a minimal increase of the complexity of the simpler first-price case. Moreover, in case there is no cheating, only collateral deposit and refund transactions must be sent to the smart contract, significantly saving on-chain storage.

The Fiat-Shamir with Aborts paradigm of Lyubashevsky has given rise to efficient lattice-based signature schemes. One popular implementation is Dilithium which is a finalist in an ongoing standardization process run by the NIST. Informally, it can be seen as a lattice analogue of the well-known discrete-logarithm-based Schnorr signature. An interesting research question is whether it is possible to combine several unrelated signatures, issued from different signing parties on different messages, into one single aggregated signature. Of course, its size should be significantly smaller than the trivial concatenation of all signatures. Ideally, the aggregation can be done offline by a third party, called public aggregation. Previous works have shown that it is possible to half-aggregate Schnorr signatures, but it was left unclear if the underlying techniques can be adapted to the lattice setting. In this work, we show that, indeed, we can use similar strategies to obtain a signature scheme allowing for public aggregation whose hardness is proven assuming the intractability of two well-studied problems on module lattices: The Module Learning With Errors problem (M-LWE) and the Module Short Integer Solution problem (M-SIS). Unfortunately, our scheme produces aggregated signatures that are larger than the trivial solution of concatenating. This is due to peculiarities that seem inherent to lattice-based cryptography. Its motivation is thus mainly pedagogical, as we explain the subtleties when designing lattice-based aggregate signatures that are supported by a proper security proof.

We describe a simple method for solving the distributed discrete logarithm problem in Paillier groups, allowing two parties to locally convert multiplicative shares of a secret (in the exponent) into additive shares. Our algorithm is perfectly correct, unlike previous methods with an inverse polynomial error probability. We obtain the following applications and further results. - Homomorphic secret sharing. We construct homomorphic secret sharing for branching programs with *negligible* correctness error and supporting *exponentially large* plaintexts, with security based on the decisional composite residuosity (DCR) assumption. - Correlated pseudorandomness. Pseudorandom correlation functions (PCFs), recently introduced by Boyle et al. (FOCS 2020), allow two parties to obtain a practically unbounded quantity of correlated randomness, given a pair of short, correlated keys. We construct PCFs for the oblivious transfer (OT) and vector oblivious linear evaluation (VOLE) correlations, based on the quadratic residuosity (QR) or DCR assumptions, respectively. We also construct a pseudorandom correlation generator (for producing a bounded number of samples, all at once) for general degree-2 correlations including OLE, based on a combination of (DCR or QR) and the learning parity with noise assumptions. - Public-key silent OT/VOLE. We upgrade our PCF constructions to have a *public-key setup*, where after independently posting a public key, each party can locally derive its PCF key. This allows completely *silent generation* of an arbitrary amount of OTs or VOLEs, without any interaction beyond a PKI, based on QR, DCR, a CRS and a random oracle. The public-key setup is based on a novel non-interactive vector OLE protocol, which can be seen as a variant of the Bellare-Micali oblivious transfer protocol.

In this paper, we describe an extensible experimental infrastructure and methodology for evaluating the micro-architectural leakage, based on power consumption, which stems from a physical device. Building on existing literature, we use it to systematically study 14 different devices, which span 4 different instruction set architectures and 4 different vendors. The study allows a characterisation of each device with respect to any leakage effects stemming from sources within the micro-architectural implementation; we use it, for example, to identify and document several novel leakage effects (e.g., due to speculative instruction execution), and scenarios where an assumption about leakage is non-portable between different yet compatible devices. Ours is the widest study of its kind we are aware of, and highlights a range of challenges with respect to 1) the design, implementation, and evaluation of masking schemes, 2) construction of accurate fine-grained leakage models, and 3) selection of suitable devices for experimental research. For example, in relation to 1), we cast further doubt on whether a given device can or does uphold the assumptions required by a given masking scheme; in relation to 2), we ultimately conclude that real-world leakage models (either statistical or formal) must include information about the micro-architecture of the device being modelled; in relation to 3), we claim the near mono-culture of devices that dominates existing literature is insufficient to support general claims regarding security. This is particularly important

An (n,m,t)-homomorphic secret sharing (HSS) scheme allows n clients to share their inputs across m servers, such that the inputs are hidden from any t colluding servers, and moreover the servers can evaluate functions over the inputs locally by mapping their input shares to compact output shares. Such compactness makes HSS a useful building block for communication-efficient secure multi-party computation (MPC). In this work, we propose a simple compiler for HSS evaluating multivariate polynomials based on two building blocks: (1) homomorphic encryption for linear functions or low-degree polynomials, and (2) information-theoretic HSS for low-degree polynomials. Our compiler leverages the power of the first building block towards improving the parameters of the second. We use our compiler to generalize and improve on the HSS scheme of Lai, Malavolta, and Schröder [ASIACRYPT'18], which is only efficient when the number of servers is at most logarithmic in the security parameter. In contrast, we obtain efficient schemes for polynomials of higher degrees and an arbitrary number of servers. This application of our general compiler extends techniques that were developed in the context of information-theoretic private information retrieval (Woodruff and Yekhanin [CCC'05]), which use partial derivatives and Hermite interpolation to support the computation of polynomials of higher degrees. In addition to the above, we propose a new application of HSS to MPC with preprocessing. By pushing the computation of some HSS servers to a preprocessing phase, we obtain communication-efficient MPC protocols for low-degree polynomials that use fewer parties than previous protocols based on the same assumptions. The online communication of these protocols is linear in the input size, independently of the description size of the polynomial.

At PQCrypto-2020, Castryck and Decru proposed CSURF (CSIDH on the surface) as an improvement to the CSIDH protocol. Soon after that, at Asiacrypt-2020, together with Vercauteren they introduced radical isogenies as a further improvement. The main improvement in these works is that both CSURF and radical isogenies require only one torsion point to initiate a chain of isogenies, in comparison to Vélu isogenies which require a torsion point per isogeny. Both works were implemented using non-constant-time techniques, however, in a realistic scenario, a constant-time implementation is necessary to mitigate risks of timing attacks. The analysis of constant-time CSURF and radical isogenies was left as an open problem by Castryck, Decru, and Vercauteren. In this work, we analyze this problem. A straightforward constant-time implementation of CSURF and radical isogenies encounters too many issues to be cost-effective, but we resolve some of these issues with new optimization techniques. We introduce projective radical isogenies to save costly inversions and present a hybrid strategy for the integration of radical isogenies in CSIDH implementations. These improvements make radical isogenies almost twice as efficient in constant-time, in terms of finite field multiplications. Using these improvements, we then measure the algorithmic performance in a benchmark of CSIDH, CSURF and CRADS (an implementation using radical isogenies) for different prime sizes. Our implementation provides a more accurate comparison between CSIDH, CSURF and CRADS than the original benchmarks, by using state-of-the-art techniques for all three implementations. Our experiments illustrate that the speed-up of constant-time CSURF-512 with radical isogenies is reduced to about 3% in comparison to the fastest state-of-the-art constant-time CSIDH-512 implementation. The performance is worse for larger primes, as radical isogenies scale worse than Vélu isogenies.

In this paper we describe the first improvement of the wire shuffling countermeasure against side-channel attacks described by Ishai, Sahai and Wagner at Crypto 2003. More precisely, we show how to get worst case statistical security against $t$ probes with running time ${\mathcal O}(t)$ instead of ${\mathcal O}(t \log t)$; our construction is also much simpler. Recall that the classical masking countermeasure achieves perfect security but with running time ${\mathcal O}(t^2)$.

The knapsack cryptography is the public-key cryptography whose security depends mainly on the hardness of the subset sum problem. Many of knapsack schemes were broken by low-density attacks, which are attack methods to use the situation that a shortest vector or a closest vector in a lattice corresponds to a solution of the subset sum problem. For the case when the Hamming weight of a solution for a random instance of the subset sum problem is arbitrary, if the density is less than 0.9408, then the instance can be solvable almost surely by a single call of lattice oracle. This fact was theoretically shown by Coster et al. In Crypto 2000, Okamoto, Tanaka and Uchiyama introduced the concept of quantum public key cryptosystems and proposed a knapsack cryptosystem, so-called OTU scheme. However, no known algorithm breaks the OTU scheme. In this paper, we introduce some combinatorial statements to describe necessary condition for the failure of low density attacks. More precisely, we give better heuristics than Gaussian heuristics for minimum norms of orthogonal lattices. Consequently, we show that the OTU scheme can be broken under these heuristics.

Existing models for non-interactive MPC cannot provide full privacy for inputs, because they inherently leak the residual function (i.e., the output of the function on the honest parties’ input together with all possible values of the adversarial inputs). For example, in any non-interactive sealed-bid auction, the last bidder can figure out what was the highest previous bid. We present a new MPC model which avoids this privacy leak. To achieve this, we utilize a blockchain in a novel way, incorporating smart contracts and arbitrary parties that can be incentivized to perform computation (“bounty hunters,” akin to miners). Security is maintained under a monetary assumption about the parties: an honest party can temporarily supply a recoverable collateral of value higher than the computational cost an adversary can expend. We thus construct non-interactive MPC protocols with strong security guarantees (full security, no residual leakage) in the short term. Over time, as the adversary can invest more and more computational resources, the security guarantee decays. Thus, our model, which we call Gage MPC, is suitable for secure computation with limited-time secrecy, such as auctions. A key ingredient in our protocols is a primitive we call “Gage Time Capsules” (GaTC): a time capsule that allows a party to commit to a value that others are able to reveal but only at a designated computational cost. A GaTC allows a party to commit to a value together with a monetary collateral. If the original party properly opens the GaTC, it can recover the collateral. Otherwise, the collateral is used to incentivize bounty hunters to open the GaTC. This primitive is used to ensure completion of Gage MPC protocols on the desired inputs. As a requisite tool (of independent interest), we present a generalization of garbled circuit that are more robust: they can tolerate exposure of extra input labels. This is in contrast to Yao’s garbled circuits, whose secrecy breaks down if even a single extra label is exposed. Finally, we present a proof-of-concept implementation of a special case of our construction, yielding an auction functionality over an Ethereum-like blockchain.

With the proposal of Picnic3, it has become interesting to investigate the security of LowMC with a full S-box layer. To significantly improve the efficiency of the Picnic signature, the designers of Picnic3 recommended to use the 4-round LowMC as the underlying block cipher, which has been shown to be insecure with 2 chosen plaintexts by Liu-Isobe-Meier. However, the attack scenario is very different and constrained in Picnic as the attacker is only allowed to know one single plaintext-ciphertext pair under the same key for LowMC. Recently, Banik et al. proposed guess-and-determine attacks on reduced LowMC in the Picnic setting. A major finding in their attacks is that the 3-bit S-box of LowMC can be linearized by guessing a quadratic equation. Notably, the attack on 2-round LowMC with a full S-box layer can be achieved with time complexity $2^{2m}$ where $m$ is the number of S-boxes in each round. As $k=3m$, their attacks can not reach 3 rounds where $k$ is the length of the key in bits. Although Banik et al. have improved the attacks with the meet-in-the-middle strategies, its memory complexity is rather high, which is $m\times 2^m$ bits of memory. In this note, we aim at low-memory key-recovery attacks as it is more fair to compare it with a pure exhaustive search. Specifically, we will describe improved algebraic attacks on 2-round LowMC by expressing the 3-bit S-box as 14 linearly independent quadratic boolean equations, which is inspired by the unsuccessful algebraic attacks on AES. As a result, the algebraic attacks on 2-round LowMC with key sizes of 129/192/255 bits can be improved by a factor of $2^{4}/2^{6.3}/2^{7.6}$, respectively. It seems that our attacks imply the attacks on 3-round LowMC. However, by taking the cost of gaussian elimination into account, the derived attacks on 3-round LowMC with key sizes of 192 and 255 bits are only about $2^{2.3}$ and $2^{3.7}$ times faster than the brute force. Our techniques are further applied to the instances with a partial S-box layer and significantly improve previous attacks with negligible memory complexity.

A Sidon space is a subspace of an extension field over a base field in which the product of any two elements can be factored uniquely, up to constants. This paper proposes a new a public-key cryptosystem of the multivariate type which is based on Sidon spaces, and has the potential to remain secure even if quantum supremacy is attained. This system, whose security relies on the hardness of the well-known MinRank problem, is shown to be resilient to several straightforward algebraic attacks. In particular, it is proved that the two popular attacks on the MinRank problem, the kernel attack and the minor attack, succeed only with exponentially small probability. The system is implemented in software, and its hardness is demonstrated experimentally.

In 2016, Guruswami and Wootters showed Shamir's secret-sharing scheme defined over an extension field has a regenerating property. Namely, we can compress each share to an element of the base field by applying a linear form, such that the secret is determined by a linear combination of the compressed shares. Immediately it seemed like an application to improve the complexity of unconditionally secure multiparty computation must be imminent; however, thus far, no result has been published. We present the first application of regenerating codes to MPC, and show that its utility lies in reducing the number of rounds. Concretely, we present a protocol that obliviously evaluates a depth-$d$ arithmetic circuit in $d + O(1)$ rounds, in the amortized setting of parallel evaluations, with $o(n^2)$ ring elements communicated per multiplication. Our protocol is secure against the maximal adversary corrupting $t < n/2$ parties. All existing approaches in this setting have complexity $\Omega(n^2)$. Moreover, we extend some of the theory on regenerating codes to Galois rings. It was already known that the repair property of MDS codes over fields can be fully characterized in terms of its dual code. We show this characterization extends to linear codes over Galois rings, and use it to show the result of Guruswami and Wootters also holds true for Shamir's scheme over Galois rings.

Logic locking has been proposed to counter security threats during IC fabrication. Such an approach restricts unauthorized use by injecting sufficient module level error to derail application level IC functionality. However, recent research has identified a trade-off between the error rate of logic locking and its resilience to a Boolean satisfiablity (SAT) attack. As a result, logic locking often cannot inject sufficient error to impact an IC while maintaining SAT resilience. In this work, we propose using architectural context available during resource binding to co-design architectures and locking configurations capable of high corruption and SAT resilience simultaneously. To do so, we propose 2 security-focused binding/locking algorithms and apply them to bind/lock 11 MediaBench benchmarks. The resulting circuits showed a 26x and 99x increase in the application errors of a fixed locking configuration while maintaining SAT resilience and incurring minimal overhead compared to other binding schemes. Locking applied post-binding could not achieve a high application error rate and SAT resilience simultaneously.

Covert security has been introduced as a compromise between semi-honest and malicious security. In a nutshell, covert security guarantees that malicious behavior can be detected by the honest parties with some probability, but in case detection fails all bets are off. While the security guarantee offered by covert security is weaker than full-fledged malicious security, it comes with significantly improved efficiency. An important extension of covert security introduced by Asharov and Orlandi (ASIACRYPT'12) is public verifiability, which allows the honest parties to create a publicly verifiable certificate of malicious behavior. Public verifiability significantly strengthen covert security as the certificate allows punishment via an external party, e.g., a judge. Most previous work on publicly verifiable covert (PVC) security focuses on the two-party case, and the multi-party case has mostly been neglected. In this work, we introduce a novel compiler for multi-party PVC secure protocols. Our compiler leverages time-lock encryption to offer high probability of cheating detection (often also called deterrence factor) independent of the number of involved parties. Moreover, in contrast to the only earlier work that studies PVC in the multi-party setting (CRYPTO'20), we provide the first full formal security analysis.

This thesis addresses security and privacy problems for digital devices and biometrics, where a secret key is generated for authentication, identification, or secure computations. A physical unclonable function (PUF) is a promising solution for local security in digital devices. A low-complexity transform-coding algorithm is developed to make the information-theoretic analysis tractable and motivate a noisy (hidden) PUF source model. The optimal trade-offs between the secret-key, privacy-leakage, and storage rates for multiple measurements of hidden PUFs are characterized. The first optimal and low-complexity code constructions are proposed. Polar codes are designed to achieve the best known rate tuples. The gains from cost-constrained controllable PUF measurements are illustrated to motivate extensions.

The choice of activation functions can have a significant effect on the performance of a neural network. Although the researchers have been developing novel activation functions, Rectified Linear Unit ($ReLU$) remains the most common one in practice. This paper shows that evolutionary algorithms can discover new activation functions for side-channel analysis (SCA) that outperform $ReLU$. Using Genetic Programming (GP), candidate activation functions are defined and explored (neuroevolution). As far as we know, this is the first attempt to develop custom activation functions for SCA. The ASCAD database experiments show this approach is highly effective compared to the state-of-the-art neural network architectures. While the optimal performance is achieved when activation functions are evolved for the particular task, we also observe that these activation functions show the property of generalization and high performance for different SCA scenarios.

Everlasting security models the setting where hardness assumptions hold during the execution of a protocol but may get broken in the future. Due to the strength of this adversarial model, achieving any meaningful security guarantees for composable protocols is impossible without relying on hardware assumptions (Müller-Quade and Unruh, JoC'10). For this reason, a rich line of research has tried to leverage physical assumptions to construct well-known everlasting cryptographic primitives, such as commitment schemes. The only known everlastingly UC secure commitment scheme, due to Müller-Quade and Unruh (JoC'10), assumes honestly generated hardware tokens. The authors leave the possibility of constructing everlastingly UC secure commitments from malicious hardware tokens as an open problem. Goyal et al. (Crypto'10) constructs unconditionally UC-secure commitments and secure computation from malicious hardware tokens, with the caveat that the honest tokens must encapsulate other tokens. This extra restriction rules out interesting classes of hardware tokens, such as physically uncloneable functions (PUFs). In this work we present the first construction of an everlastingly UC-secure commitment scheme in the fully malicious token model without requiring honest token encapsulation. Our scheme assumes the existence of PUFs and is secure in the common reference string model. We also show that our results are tight by giving an impossibility proof for everlasting UC-secure computation from non-erasable tokens (such as PUFs), even with trusted setup.

With an increasing number of mobile devices and their high accessibility, protecting the implementation of cryptographic functions in the presence of physical adversaries has become more relevant than ever. Over the last decade, a lion’s share of research in this area has been dedicated to developing countermeasures at an algorithmic level. Here, masking has proven to be a promising approach due to the possibility of formally proving the implementation’s security solely based on its algorithmic description by elegantly modeling the circuit behavior. Theoretically verifying the security of masked circuits becomes more and more challenging with increasing circuit complexity. This motivated the introduction of security notions that enable masking of single gates while still guaranteeing the security when the masked gates are composed. Systematic approaches to generate these masked gates – commonly referred to as gadgets – were restricted to very simple gates like 2-input AND gates. Simply substituting such small gates by a secure gadget usually leads to a large overhead in terms of fresh randomness and additional latency (register stages) being introduced to the design. In this work, we address these problems by presenting a generic framework to construct trivially composable and secure hardware gadgets for arbitrary vectorial Boolean functions, enabling the transformation of much larger sub-circuits into gadgets. In particular, we present a design methodology to generate first-order secure masked gadgets which is well-suited for integration into existing Electronic Design Automation (EDA) tools for automated hardware masking as only the Boolean function expression is required. Furthermore, we practically verify our findings by conducting several case studies and show that our methodology outperforms various other masking schemes in terms of introduced latency or fresh randomness – especially for large circuits.

In this paper, we propose the first generic framework for attribute-based encryptions (ABE) with master-secret-key-dependent-message security (mKDM security) for affine functions via predicate encodings by Chen, Gay and Wee [Eurocrypt 2015]. The construction is adaptively secure under standard $k$-Lin assumption in prime-order bilinear groups. By this, we obtain a set of new mKDM-secure ABE schemes with high expressiveness that have never been reached before: we get the first hierarchical IBE (HIBE) scheme and the first ABE scheme for arithmetic branching program (ABP) with mKDM security for affine functions. Thanks to the expressiveness (more concretely, delegability like HIBE), we can obtain mKDM-secure ABE against chosen-ciphertext attack (i.e., CCA security) via a classical CPA-to-CCA transformation that works well in the context of mKDM.

Any non-zero ideal in a number field can be factored into a product of prime ideals. In this paper we report a surprising connection between the complexity of the shortest vector problem (SVP) of prime ideals in number fields and their decomposition groups. When applying the result to number fields popular in lattice based cryptosystems, such as power-of-two cyclotomic fields, we show that a majority of rational primes lie under prime ideals admitting a polynomial time algorithm for SVP. Although the shortest vector problem of ideal lattices underpins the security of the Ring-LWE cryptosystem, this work does not break Ring-LWE, since the security reduction is from the worst case ideal SVP to the average case Ring-LWE, and it is one-way.

In this paper, we study forward secret encrypted RAMs (FS eRAMs) which enable clients to outsource the storage of an n-entry array to a server. In the case of a catastrophic attack where both client and server storage are compromised, FS eRAMs guarantee that the adversary may not recover any array entries that were deleted or overwritten prior to the attack. A simple folklore FS eRAM construction with $O(\log n)$ overhead has been known for at least two decades. Unfortunately, no progress has been made since then. We show the lack of progress is fundamental by presenting an $\Omega(\log n)$ lower bound for FS eRAMs proving that the folklore solution is optimal. To do this, we introduce the symbolic model for proving cryptographic data structures lower bounds that may be of independent interest. Given this limitation, we investigate applications where forward secrecy may be obtained without the additional $O(\log n)$ overhead. We show this is possible for oblivious RAMs, memory checkers, and multicast encryption by incorporating the ideas of the folklore FS eRAM solution into carefully chosen constructions of the corresponding primitives.

Private set intersection reveals the intersection of two private sets, but many real-world applications require the parties to learn $\textit{only}$ partial information about the intersection. In this paper we introduce a new approach for computing arbitrary functions of the intersection, provided that it is safe to also reveal the cardinality of the intersection. In the most general case, our new protocol provides the participants with secret shares of the intersection, which can be fed into any generic 2PC protocol. Certain computations on the intersection can also be done even more directly and efficiently, avoiding this secret-sharing step. These cases include computing only the cardinality of intersection, or the ``cardinality-sum'' application proposed in Ion et al. (ePrint 2017). Compared to the state-of-the-art protocol for computing on intersection (Pinkas et al., Eurocrypt 2019), our protocol has about $2.5-3\times$ less communication, and has faster running time on slower (50Mbps) networks. Our new techniques can also be used to privately compute the {\em union} of two sets as easily as computing the intersection. Our protocol concretely improves the leading private set union protocol (Kolesnikov et al., Asiacrypt 2020) by a factor of $2-2.5\times$, depending on the network speed. We then show how private set union can be used in a simple way to realize the ``Private-ID'' functionality suggested by Buddhavarapu et al.~(ePrint 2020). Our protocol is significantly faster than the prior Private-ID protocol, especially on fast networks. All of our protocols are in the two-party setting and are secure against semi-honest adversaries.

Recently, Machine Learning (ML) is widely investigated in the side-channel analysis (SCA) community. As an artificial neural network can extract the feature without preprocessing, ML-based SCA methods relatively less rely on the attacker's ability. Consequently, they outperform traditional methods. Hiding is a countermeasure against SCA that randomizes the moments of manipulating sensitive data. Since hiding could disturb the neural network's learning, an attacker should design a proper architecture against hiding. In this paper, we propose inherently robust architecture against every kind of desynchronization. We demonstrated the proposed method with plenty of datasets, including open datasets. As a result, our method outperforms state-of-the-art on every dataset.

We study the problem of secure multiparty computation for functionalities where only one party receives the output, to which we refer as solitary MPC. Recently, Halevi et al. (TCC 2019) studied fully secure (i.e., with guaranteed output delivery) solitary MPC and showed impossibility of such protocols for certain functionalities when there is no honest majority among the parties. In this work, we study fully secure solitary MPC in the honest majority setting and focus on its round complexity. We note that a broadcast channel or public key infrastructure (PKI) setup is necessary for an $n$-party protocol against malicious adversaries corrupting up to $t$ parties where $n/3 \leq t < n/2$. Therefore, we study the following settings and ask the question: Can fully secure solitary MPC be achieved in fewer rounds than fully secure standard MPC in which all parties receive the output? - When there is a broadcast channel and no PKI: * We start with a negative answer to the above question. In particular, we show that the exact round complexity of fully secure solitary MPC is 3, which is the same as fully secure standard MPC. * We then study the minimal number of broadcast rounds needed in the design of round-optimal fully secure solitary MPC. We show that both the first and second rounds of broadcast are necessary when $2 \lceil n/5 \rceil \leq t < n/2$, whereas pairwise-private channels suffice in the last round. Notably, this result also applies to fully secure standard MPC in which all parties receive the output. - When there is a PKI and no broadcast channel, nevertheless, we show more positive results: * We show an upper bound of 5 rounds for any honest majority. This is superior to the super-constant lower bound for fully secure standard MPC in the exact same setting. * We complement this by showing a lower bound of 4 rounds when $3\lceil n/7 \rceil \leq t < n/2$. * For the special case of $t=1,n=3$, when the output receiving party does not have an input to the function, we show an upper bound of $2$ rounds, which is optimal. When the output receiving party has an input to the function, we show a lower bound of 3, which matches an upper bound from prior work. * For the special case of $t=2,n=5$, we show a lower bound of 3 rounds (an upper bound of 4 follows from prior work). All our results also assume the existence of a common reference string (CRS) and pairwise-private channels. Our upper bounds use a decentralized threshold fully homomorphic encryption (dTFHE) scheme (which can be built from the learning with errors (LWE) assumption) as the main building block.

The random oracle, generic group, and generic bilinear map models (ROM, GGM, GBM, respectively) are fundamental heuristics used to justify new computational assumptions and prove the security of efficient cryptosystems. While known to be invalid in some contrived settings, the heuristics generally seem reasonable for real-world applications. In this work, we ask: \emph{which heuristics are closer to reality?} Or conversely, which heuristics are a larger leap? We answer this question through the framework of computational indifferentiability, showing that the ROM is a strictly ``milder'' heuristic than the GGM, which in turn is strictly milder than the GBM. While this may seem like the expected outcome, we explain why it does not follow from prior works and is not the a priori obvious conclusion. In order to prove our results, we develop new ideas for proving computational indifferentiable separations.

Enforcement of policy regulations and availability of auditing mechanisms are crucial building blocks for the adoption of distributed payment systems. This paper reviews a number of existing proposals for distributed payment systems that offer some form of auditability for regulators. We identify two major distinct lines of work: payment systems that are not privacy-preserving such as Bitcoin, where regulation functionalities are typically tailored for organizations controlling many accounts, and privacy-preserving payment systems where regulation functionalities are typically targeted to user level. We provide a systematization methodology over several axes of characteristics and performance, while highlighting insights and research gaps that we have identified, such as lack of dispute-resolution solutions between the regulator and the entity under audit, and the incompatibility of ledger pruning or off-chain protocols with regulatory requirements. Based on our findings, we propose a number of exciting future research directions.

CRAFT is a lightweight tweakable Substitution-Permutation-Network (SPN) block cipher optimized for efficient protection of its implementations against Differential Fault Analysis (DFA) attacks. In this paper, we present an equivalent description of CRAFT up to a simple mapping on the plaintext, ciphertext and round tweakeys. We show that the new representation, for a sub-class of keys, leads to a new structure which is a Feistel network, with non-linear operation and key addition only on half the state. Consequently, it reveals a class of weak keys for which CRAFT is less resistant against differential and linear cryptanalyses. As a result, we present one weak-key single-tweak differential attack on 23 rounds (with time complexity of $2^{94}$ encryptions and data complexity of $2^{74}$ chosen plaintext/tweak/ciphertext tuples and works for $2^{112}$ weak keys) and one weak-key related-tweak attack on 26 rounds of the cipher (with time complexity of $2^{105}$ encryptions and data complexity $2^{73}$ chosen plaintext/tweak/ciphertext tuples and works for $2^{108}$ weak keys). Note that these attacks do not break the security claim of the CRAFT block cipher.

In this paper, we show that OAEP transform is indistinguishable under chosen ciphertext attack in the quantum random oracle model if the underlying trapdoor permutation is quantum partial-domain one-way. The existing post-quantum security of OAEP (TCC 2016-B ) requires a modification to the OAEP transform using an extra hash function. We prove the security of the OAEP transform without any modification and this answers an open question in one of the finalists of NIST competition, NTRU submission, affirmatively.

SNOW 3G is a stream cipher used as one of the standard algorithms for data confidentiality and integrity protection over the air interface in the 3G and 4G mobile communication systems. SNOW-V is a recent new version that was proposed as a candidate for inclusion in the 5G standard. In this paper, we propose a faster variant of SNOW-V, called SNOW-Vi, that can reach the targeted speeds for 5G in a software implementation on a larger variety of CPU architectures. SNOW-Vi differs in the way how the LFSR is updated and also introduces a new location of the tap $T2$ for stronger security, while everything else is kept the same as in SNOW-V. The throughput in a software environment is increased by around 50\% in average, up to 92 Gbps. This makes the applicability of the cipher much wider and more use cases are covered. The security analyses previously done for SNOW-V are not affected in most aspects, and SNOW-Vi provides the same 256-bit security level as SNOW-V.

We construct the currently most efficient signature schemes with tight multi-user security against adaptive corruptions. It is the first generic construction of such schemes, based on lossy identification schemes (Abdalla etal; JoC 2016), and the first to achieve strong existential unforgeability. It also has significantly more compact signatures than the previously most efficient construction by Gjosteen and Jager (CRYPTO 2018). When instantiated based on the decisional Diffie-Hellman assumption, a signature consists of only three exponents. We propose a new variant of the generic construction of signatures from sequential OR-proofs by Abe, Ohkubo, and Suzuki (ASIACRYPT 2002) and Fischlin, Harasser, and Janson (EUROCRYPT 2020). In comparison to Fischlin etal, who focus on constructing signatures in the non-programmable random oracle model (NPROM), we aim to achieve tight security against adaptive corruptions, maximize efficiency, and to directly achieve strong existential unforgeability (also in the NPROM). This yields a slightly different construction and we use slightly different and additional properties of the lossy identification scheme. Signatures with tight multi-user security against adaptive corruptions are a commonly-used standard building block for tightly-secure authenticated key exchange protocols. We also show how our construction improves the efficiency of all existing tightly-secure AKE protocols.

In this note, an LWE problem with a hidden trapdoor is introduced. It is used to construct an efficient public-key crypto-system EHT. The new system is significantly different from LWE based NIST candidates like FrodoKEM. The performance of EHT compares favorably with FrodoKEM.

Suppose that a problem $\Pi$ has a statistical zero-knowledge (SZK) proof with communication complexity $m$. The question of batch verification for SZK asks whether one can prove that $k$ instances $x_1,\ldots,x_k$ all belong to $\Pi$ with a statistical zero-knowledge proof whose communication complexity is better than $k \cdot m$ (which is the complexity of the trivial solution of executing the original protocol independently on each input). In a recent work, Kaslasi et al. (TCC, 2020) constructed such a batch verification protocol for any problem having a non-interactive SZK (NISZK) proof-system. Two drawbacks of their result are that their protocol is private-coin and is only zero-knowledge with respect to the honest verifier. In this work, we eliminate these two drawbacks by constructing a public-coin malicious-verifier SZK protocol for batch verification of NISZK. Similarly to the aforementioned prior work, the communication complexity of our protocol is $\big(k+poly(m) \big) \cdot polylog(k,m)$.

To factor an integer $N$ we construct $n$ triples of $p_n$-smooth integers $u,v,|u-vN|$ for the $n$-th prime $p_n$. Denote such triple a fac-relation. We get fac-relations from a nearly shortest vector of the lattice $\mathcal{L}(\mathbf{R}_{n,f})$ with basis matrix $\mathbf{R}_{n,f} \in \mathbb{R}^{(n+1)\times (n+1)}$ where $f : [1,n] \rightarrow [1,n]$ is a permutation of $[1,2,...,n]$ and $(f(1),...,f(n), N'\ln N)$ is the diagonal and (N'\ln p_1, \ldots, N'\ln p_n, N'\ln N) for $N'=N^{\frac{1}{n+1}}$ is the last line of $\mathbf{R}_{n,f}$. An independent permutation $f'$ yields an independent fac-relation. We find sufficiently short lattice vectors by strong primal-dual reduction of $\mathbf{R}_{n,f}$. We factor $N \approx 2^{400}$ by $n = 47$ and $N \approx 2^{800}$ by $n = 95$. Our accelerated strong primal-dual reduction of [Gama, Nguyen 2008] factors integers $N \approx 2^{400}$ and $N \approx 2^{800}$ by $4.2 \cdot 10^9$ and $8.4 \cdot 10^{10}$ arithmetic operations, much faster then the quadratic sieve and the number field sieve and using much smaller primes $p_n$. This destroys the RSA cryptosystem.

Oblivious RAM (ORAM) enables a user to read/write her outsourced cloud data without access-pattern leakage. Not all users want a fully functional ORAM all the time since it always creates inefficiency. We show that forward-private/backward-private (FP/BP) ORAMs are also good alternatives for reducing the search-pattern leakage of dynamic searchable encryption (DSE). We introduce the FP/BP-ORAM definitions and present LL-ORAM, the first FP/BP-ORAM that achieves near-zero client storage, single-round-trip read/write, worst-case sublinear search time, and an extremely simple implementation. LL-ORAM consists of a set of switchable protocols whose security can be switched among forward privacy, backward privacy, and perfect security at any time. The construction involves a novel tree data structure named LL-tree, whose advantage is that it supports fast computation in the cloud with an access-pattern-reduced leakage profile. LL-ORAM security is formally proven under forward and backward privacy. The experimental results demonstrate that LL-ORAM is efficient and can be practically employed by DSE applications.

Restoring the security of maliciously implemented cryptosystems has been widely considered challenging due to the fact that the subverted implementation could arbitrarily deviate from the official specification. Achieving security against adversaries that can arbitrarily subvert implementations seems to inherently require trusted component assumptions and/or architectural properties. At ASIACRYPT 2016, Russell et al. proposed an attractive model where a watchdog is used to test and approve individual components of an implementation before or during deployment. Such a detection-based strategy has been useful for designing various cryptographic schemes that are provably resilient to subversion. We consider Russell et al.'s watchdog model from a practical perspective regarding watchdog efficiency. We find that the asymptotic definitional framework while permitting strong positive theoretical results, does not yet guarantee practical watchdogs due to the fact that the running time of a watchdog is only bounded by an abstract polynomial. Hence, in the worst case, the running time of the watchdog might exceed the running time of the adversary, which seems impractical for most applications. We adopt Russell et al.'s watchdog model to the concrete security setting and design the first subversion-resilient public-key encryption scheme which allows for extremely efficient watchdogs with only linear running time. At the core of our construction is a new variant of a combiner for key encapsulation mechanisms (KEMs) by Giacon et al. (PKC'18). We combine this construction with a new subversion-resilient randomness generator that can also be checked by an efficient watchdog, even in constant time, which could be of independent interest for the design of other subversion-resilient cryptographic schemes. Our work thus shows how to apply Russell et al.'s watchdog model to design subversion-resilient cryptography with efficient watchdogs. We insist that this work does not intend to show that the watchdog model outperforms other defense approaches but to demonstrate that practical watchdogs are practically achievable. This is the full version of a work published at PKC21. We identify a subtle flaw in the proof of the previous version and show it is impossible to achieve CPA security under subversion with the proposed approach. However, the same construction can achieve one-way security under subversion.

This research revisits the fundamental problem of processing privacy-preserving Boolean queries over outsourced databases on untrusted public clouds. Many current Searchable Encryption (SE) schemes try to seek an appropriate trade-off between security and efficiency, yet most of them suffer from an unacceptable query leakage due to their conjunctive/disjunctive terms that are processed individually. We show, however, this trade-off still can be deeply optimized for more security. We consider a Boolean formula as a set of deterministic finite automatons (DFAs) and propose a novel approach to running an encrypted DFA, which can be effectively and efficiently processed by the cloud. We give three constructions for conjunctive, disjunctive, and Boolean queries, respectively. Their notable advantages are single-round, highly-efficient, adaptively-secure, and leakage-minimized. A lot of experiments are made to evaluate overall efficiency. Testing results show that the schemes achieve enhanced security almost without sacrificing anything of search efficiency.

Constructing interactive zero-knowledge arguments from simple assumptions with small communication complexity and good computational efficiency is an important, but difficult problem. In this work, we study interactive arguments with noticeable soundness error in their full generality and for the specific purpose of constructing concretely efficient shuffle arguments. To counterbalance the effects of a larger soundness error, we show how to transform such three-move arguments into publicly-accountable ones which allow the verifier to convince third parties of detected misbehavior by a cheating prover. This may be particularly interesting for applications where a malicious prover has to balance the profits it can make from cheating successfully and the losses it suffers from being caught. %In contrast to standard sequential repetition, our transformation increases the round and communication complexity by only a small additive factor. We construct interactive, public-coin, zero-knowledge arguments with noticeable soundness error for proving that a target vector of commitments is a pseudorandom permutation of a source vector. Our arguments do not rely on any trusted setup and only require the existence of collision-resistant hash functions. The communication complexity of our arguments is \emph{independent} of the length of the shuffled vector. For a soundness error of $2^{-5}=1/32$, the communication cost is $153$ bytes without and $992$ bytes with public accountability, meaning that our arguments are shorter than shuffle arguments realized using Bulletproofs (IEEE S\&P 2018) and even competitive in size with SNARKs, despite only relying on simple assumptions.

In this work, we first present general methods to construct information rate-1 PKE that is $\KDM^{(n)}$-secure with respect to \emph{block-affine} functions for any unbounded polynomial $n$. To achieve this, we propose a new notion of extractor that satisfies \emph{reusability}, \emph{homomorphic}, and \emph{security against correlated-source attacks}, and show how to use this extractor to improve the information rate of the \KDM-secure PKE of Brakerski et al.~(Eurocrypt 18). Then, we show how to amplify \KDM~security from block-affine function class into general bounded size circuits via a variant of the technique of Applebaum (Eurocrypt 11), achieving better efficiency. Furthermore, we show how to generalize these approaches to the IBE setting. Additionally, our PKE and IBE schemes are also leakage resilient, with leakage rates $1-o(1)$ against a slightly smaller yet still general class -- block leakage functions. We can instantiate the required building blocks from $\LWE$ or $\DDH$.

Group encryption (GE), introduced by Kiayias, Tsiounis and Yung (Asiacrypt'07), is the encryption analogue of group signatures. It allows to send verifiably encrypted messages satisfying certain requirements to certified members of a group, while keeping the anonymity of the receivers. Similar to the tracing mechanism in group signatures, the receiver of any ciphertext can be identified by an opening authority - should the needs arise. The primitive of GE is motivated by a number of interesting privacy-preserving applications, including the filtering of encrypted emails sent to certified members of an organization. This paper aims to improve the state-of-affairs of GE systems. Our first contribution is the formalization of fully dynamic group encryption (FDGE) - a GE system simultaneously supporting dynamic user enrolments and user revocations. The latter functionality for GE has not been considered so far. As a second contribution, we realize the message filtering feature for GE based on a list of $t$-bit keywords and $2$ commonly used policies: ``permissive'' - accept the message if it contains at least one of the keywords as a substring; ``prohibitive'' - accept the message if all of its $t$-bit substrings are at Hamming distance at least $d$ from all keywords, for $d \geq 1$. This feature so far has not been substantially addressed in existing instantiations of GE based on DCR, DDH, pairing-based and lattice-based assumptions. Our third contribution is the first instantiation of GE under code-based assumptions. The scheme is more efficient than the lattice-based construction of Libert et al. (Asiacrypt'16) - which, prior to our work, is the only known instantiation of GE under post-quantum assumptions. Our scheme supports the $2$ suggested policies for message filtering, and in the random oracle model, it satisfies the stringent security notions for FDGE that we put forward.

Extended Affine (EA) equivalence is the equivalence relation between two vectorial Boolean functions $F$ and $G$ such that there exist two affine permutations $A$, $B$, and an affine function $C$ satisfying $G = A \circ F \circ B + C$. While a priori simple, it is very difficult in practice to test whether two functions are EA-equivalent. This problem has two variants: EA-testing deals with figuring out whether the two functions can be EA-equivalent, and EA-recovery is about recovering the tuple $(A,B,C)$ if it exists. In this paper, we present a new efficient algorithm that efficiently solves the EA-recovery problem for quadratic functions. Though its worst-case complexity is obtained when dealing with APN functions, it supersedes all previously known algorithms in terms of performance, even in this case. This approach is based on the Jacobian matrix of the functions, a tool whose study in this context can be of independent interest. In order to tackle EA-testing efficiently, the best approach in practice relies on class invariants. We provide an overview of the literature on said invariants along with a new one based on the ortho-derivative which is applicable to quadratic APN functions, a specific type of functions that is of great interest, and of which tens of thousands need to be sorted into distinct EA-classes. Our ortho-derivative-based invariant is both very fast to compute, and highly discriminating.

In this paper, we present a new technique which can be used to find better linear approximations in ARX ciphers. Using this technique, we present the first explicitly derived linear approximations for 3 and 4 rounds of ChaCha and, as a consequence, it enables us to improve the recent attacks against ChaCha. Additionally, we present new differentials for 3 and 3.5 rounds of ChaCha that, when combined with the proposed technique, lead to further improvement in the complexity of the Differential-Linear attacks against ChaCha.

Blockchain technologies have received a great amount of attention, and its immutability is paramount to facilitate certain applications requiring persistent records. However, in many other use-cases, tremendous real-world incidents have exposed the harm of strict immutability. For example, illicit data stored in immutable blockchain poses numerous challenges for law enforcement agencies such as Interpol, and millions of dollars are lost due to the vulnerabilities of immutable smart contract. Moreover, ``Right to be Forgotten" (a.k.a. data erasure) has been imposed in new European Union's General Data Protection Regulation, thus causing immutable blockchains no longer compatible with personal data. Therefore, it is imperative (even legally required) to design efficient redactable blockchain protocols in a controlled way. In this paper, we propose a new redaction strategy to decouple the voting stage for redaction from the underlying consensus layer, where a committee with sufficient honest fraction is selected firstly and then the committee members would vote for the redaction. Based on this new strategy, we present a generic approach of designing redactable blockchain protocol in the permissionless setting with instant redaction, applied to both proof-of-stake (PoS) blockchain and proof-of-work (PoW) blockchain with just different instantiations to randomly select ``committee members'' according to stake or computational power. Our protocol can maintain the same adversary bound requirements and security assumption as the underlying blockchain (e.g., 1/2 adversary bound and various network environments), which is compatible with most current blockchains requiring only minimal changes. It also offers public verifiability for redactable chains, where any edited block in the chain is publicly verifiable. Compared to previous solutions in permissionless setting, our redaction operation can be completed instantly, even only within one slot for the best-case scenario of PoS instantiation, which is desirable for redacting harmful or sensitive data. Correspondingly, our redaction verification in the blockchain is also instant. Furthermore, we define the first ideal protocol of redactable blockchain following the language of universal composition, and prove that our protocol can achieve the security property of redactable common prefix, chain quality, and chain growth. Finally, we develop a proof-of-concept implementation, and conduct extensive experiments to evaluate the overhead incurred by redactions. The experimental results show that the overhead remains minimal for both online nodes and re-spawning nodes, which demonstrates the high efficiency of our design.

The United Kingdom (UK) government is considering advanced primitives such as identity-based encryption (IBE) for adoption as they transition their public-safety communications network from TETRA to an LTE-based service. However, the current LTE standard relies on elliptic-curve-based IBE, which will be vulnerable to quantum computing attacks, expected within the next 20-30 years. Lattices can provide quantum-safe alternatives for IBE. These schemes have shown promising results in terms of practicality. To date, several IBE schemes over lattices have been proposed, but there has been little in the way of practical evaluation. This paper provides the first complete optimised practical implementation and benchmarking of Latte, a promising Hierarchical IBE (HIBE) scheme proposed by the UK National Cyber Security Centre (NCSC) in 2017 and endorsed by European Telecommunications Standards Institute (ETSI). We propose optimisations for the KeyGen, Delegate, Extract and Gaussian sampling components of Latte, to increase attack costs, reduce decryption key lengths by 2x-3x, ciphertext sizes by up to 33%, and improve speed. In addition, we conduct a precision analysis, bounding the Rényi divergence of the distribution of the real Gaussian sampling procedures from the ideal distribution in corroboration of our claimed security levels. Our resulting implementation of the Delegate function takes 0.4 seconds at 80-bit security level on a desktop machine at 4.2GHz, significantly faster than the order of minutes estimated in the ETSI technical report. Furthermore, our optimised Latte Encrypt/Decrypt implementation reaches speeds up to 9.7x faster than the ETSI implementation.

We introduce a new definition for key updates, called backward-leak uni-directional key updates, in updatable encryption (UE). This notion is a variant of uni-directional key updates for UE. We show that existing secure UE schemes in the bi-directional key updates setting are not secure in the backward-leak uni-directional key updates setting. Thus, security in the backward-leak uni-directional key updates setting is strictly stronger than security in the bi-directional key updates setting. This result is in sharp contrast to the equivalence theorem by Jiang (Asiacrypt 2020), which says security in the bi-directional key updates setting is equivalent to security in the existing uni-directional key updates setting. We call the existing uni-directional key updates ``forward-leak uni-directional'' key updates to distinguish two types of uni-directional key updates in this paper. We also present a UE scheme that is secure in the backward-leak uni-directional key updates setting under the learning with errors assumption.

We focus on exploring more potential of Longa and Sica's algorithm (ASIACRYPT 2012), which is an elaborate iterated Cornacchia algorithm that can compute short bases for 4-GLV decompositions. The algorithm consists of two sub-algorithms, the first one in the ring of integers $\mathbb{Z}$ and the second one in the Gaussian integer ring $\mathbb{Z}[i]$. We observe that $\mathbb{Z}[i]$ in the second sub-algorithm can be replaced by another Euclidean domain $\mathbb{Z}[\omega]$ $(\omega=\frac{-1+\sqrt{-3}}{2})$. As a consequence, we design a new twofold Cornacchia-type algorithm with a theoretic upper bound of output $C\cdot n^{1/4}$, where $C=\frac{3+\sqrt{3}}{2}\sqrt{1+|r|+|s|}$ with small values $r, s$ given by the curve. Besides, we give some applications of our new algotithm in some cuvres not considered in Longa and Sica's algorithm.

Succinct non-interactive arguments of knowledge (SNARKs) have found numerous applications in the blockchain setting and elsewhere. The most efficient SNARKs require a distributed ceremony protocol to generate public parameters, also known as a structured reference string (SRS). Our contributions are two-fold: 1. We give a security framework for non-interactive zero-knowledge arguments with a ceremony protocol. 2. We revisit the ceremony protocol of Groth's SNARK [Bowe et al., 2017]. We show that the original construction can be simplified and optimized, and then prove its security in our new framework. Importantly, our construction avoids the random beacon model used in the original work.

At Asiacrypt 2020, Moriya et al. introduced two new IND-CPA secure supersingular isogeny based Public Key Encryption (PKE) protocols: SiGamal and C-SiGamal. Unlike the PKEs canonically derived from SIDH and CSIDH, the new protocols provide IND-CPA security without the use of hash functions. SiGamal and C-SiGamal are however not IND-CCA secure. Moriya et al. suggested a variant of SiGamal that could be IND-CCA secure, but left its study as an open problem. In this paper, we revisit the protocols introduced by Moriya et al. First, we show that the SiGamal variant suggested by Moriya et al. for IND-CCA security is, in fact, not IND-CCA secure. Secondly, we propose a new isogeny-based PKE protocol named SimS, obtained by simplifying SiGamal. SimS has smaller public keys and ciphertexts than (C-)SiGamal and it is more efficient. We prove that SimS is IND-CCA secure under CSIDH security assumptions and one Knowledge of Exponent-type assumption we introduce. Interestingly, SimS is also much closer to the CSIDH protocol, facilitating a comparison between SiGamal and CSIDH.

Verifiable random functions (VRFs), introduced by Micali, Rabin and Vadhan (FOCS’99), are the public-key equivalent of pseudorandom functions. A public verification key and proofs accompanying the output enable all parties to verify the correctness of the output. However, all known standard model VRFs have a reduction loss that is much worse than what one would expect from known optimal constructions of closely related primitives like unique signatures. We show that: 1. Every security proof for a VRF that relies on a non-interactive assumption has to lose a factor of Q, where Q is the number of adversarial queries. To that end, we extend the meta-reduction technique of Bader et al. (EUROCRYPT’16) to also cover VRFs. 2. This raises the question: Is this bound optimal? We answer this question in the affirmative by presenting the first VRF with a reduction from the non-interactive qDBDHI assumption to the security of VRF that achieves this optimal loss. We thus paint a complete picture of the achievability of tight verifiable random functions: We show that a security loss of Q is unavoidable and present the first construction that achieves this bound.

The LWE problem with its ring variants is today the most prominent candidate for building efficient public key cryptosystems resistant to quantum computers. NTRU-type cryptosystems use an LWE-type variant with small max-norm secrets, usually with ternary coefficients from the set $\{-1,0,1\}$. The presumably best attack on these schemes is a hybrid attack that combines lattice reduction techniques with Odlyzko's Meet-in-the-Middle approach. Odlyzko's algorithm is a classical combinatorial attack that for key space size S runs in time $S^{0.5}$. We substantially improve on this Meet-in-the-Middle approach, using the representation technique developed for subset sum algorithms. Asymptotically, our heuristic Meet-in-the-Middle attack runs in time roughly $S^{0.25}$, which also beats the $S^{\frac 1 3}$ complexity of the best known quantum algorithm. For the round-3 NIST post-quantum encryptions NTRU and NTRU Prime we obtain non-asymptotic instantiations of our attack with complexity roughly $S^{0.3}$. As opposed to other combinatorial attacks, our attack benefits from larger LWE field sizes $q$, as they are often used in modern lattice-based signatures. For example, for BLISS and GLP signatures we obtain non-asymptotic combinatorial attacks around $S^{0.28}$. Our attacks do not invalidate the security claims of the aforementioned schemes. However, they establish improved combinatorial upper bounds for their security. We leave it is an open question whether our new Meet-in-the-Middle attack in combination with lattice reduction can be used to speed up the hybrid attack.

This work introduces a new interactive oracle proof system based on the MPC-in-the-Head paradigm. To improve concrete efficiency and offer flexibility between computation time and communication size, a generic proof construction based on multi-round MPC protocols is proposed, instantiated with a specific protocol and implemented and compared to similar proof systems. Performance gains over previous work derive from a multi-party multiplication check optimized for the multi-round and MPC-in-the-Head settings. Of most interest among implementation optimizations is the use of identical randomness across repeated MPC protocol executions in order to accelerate computation without excessive cost to the soundness error. The new system creates proofs of SHA-256 pre-images of 43KB in 53ms with 16 MPC parties, or 23KB in 188ms for 128 parties. As a signature scheme, the non-interactive variant produces signatures, based on the AES-128 circuit, of 19KB in 4.2ms; this is 35% faster and 33 % larger than the Picnic3 scheme (13kB in 5.3ms for 16 parties) which is based on the 90% smaller LowMC circuit.

Mesh messaging applications allow users in relative proximity to communicate without the Internet. The most viable offering in this space, Bridgefy, has recently seen increased uptake in areas experiencing large-scale protests (Hong Kong, India, Iran, US, Zimbabwe, Belarus), suggesting its use in these protests. It is also being promoted as a communication tool for use in such situations by its developers and others. In this work, we report on a security analysis of Bridgefy. Our results show that Bridgefy, as analysed, permitted its users to be tracked, offered no authenticity, no effective confidentiality protections and lacked resilience against adversarially crafted messages. We verified these vulnerabilities by demonstrating a series of practical attacks on Bridgefy. Thus, if protesters relied on Bridgefy, an adversary could produce social graphs about them, read their messages, impersonate anyone to anyone and shut down the entire network with a single maliciously crafted message.

The introduction of the automatic search boosts the cryptanalysis of symmetric-key primitives to some degree. However, the performance of the automatic search is not always satisfactory for the search of long trails or ciphers with large state sizes. Compared with the extensive attention on the enhancement for the search with the mixed integer linear programming (MILP) method, few works care for the acceleration of the automatic search with the Boolean satisfiability problem (SAT) or satisfiability modulo theories (SMT) method. This paper intends to fill this vacancy. Firstly, with the additional encoding variables of the sequential counter circuit for the original objective function in the standard SAT method, we put forward a new encoding method to convert the Matsui's bounding conditions into Boolean formulas. This approach does not rely on new auxiliary variables and significantly reduces the consumption of clauses for integrating multiple bounding conditions into one SAT problem. Then, we evaluate the accelerating effect of the novel encoding method under different sets of bounding conditions. With the observations and experience in the tests, a strategy on how to create the sets of bounding conditions that probably achieve extraordinary advances is proposed. The new idea is applied to search for optimal differential and linear characteristics for multiple ciphers. For PRESENT, GIFT-64, RECTANGLE, LBlock, TWINE, and some versions in SIMON and SPECK families of block ciphers, we obtain the complete bounds (full rounds) on the number of active S-boxes, the differential probability, as well as the linear bias. The acceleration method is also employed to speed up the search of related-key differential trails for GIFT-64. Based on the newly identified 18-round distinguisher with probability $2^{-58}$, we launch a 26-round key-recovery attack with $2^{60.96}$ chosen plaintexts. To our knowledge, this is the longest attack on GIFT-64. Lastly, we note that the attack result is far from threatening the security of GIFT-64 since the designers recommended users to double the number of rounds under the related-key attack setting.

This paper presents three attack vectors of bit-wise cryptanalysis including rotational, bit-wise differential, and zero-sum distinguishing attacks on the AND-RX permutation Friet-PC, which is implemented in a lightweight authenticated encryption scheme Friet. First, we propose a generic procedure for a rotational attack on AND-RX cipher with round constants. By applying the proposed attack to Friet-PC, we can construct an 8-round rotational distinguisher with a time complexity of 2^{102}. Next, we explore single- and dual-bit differential biases, which are inspired by the existing study on Salsa and ChaCha, and observe the best bit-wise differential bias with 2^{&#8722;9.552}. This bias allows us to practically construct a 9-round bit-wise differential distinguisher with a time complexity of 2^{20.044}. Finally, we construct 13-, 15-, 17-, and 30-round zero-sum distinguishers with time complexities of 2^{31}, 2^{63}, 2^{127}, and 2^{383}, respectively. To summarize our study, we apply three attack vectors of bit-wise cryptanalysis to Friet-PC and show their superiority as effective attacks on AND-RX ciphers.

Sharding is an emerging technique to overcome scalability issues on blockchain based public ledgers. Without sharding, every node in the network has to listen to and process all ledger protocol messages. The basic idea of sharding is to parallelize the ledger protocol: the nodes are divided into smaller subsets that each take care of a fraction of the original load by executing lighter instances of the ledger protocol, also called shards. The smaller the shards, the higher the efficiency, as by increasing parallelism there is less overhead in the shard consensus. In this vein, we propose a novel approach that leverages the sharding safety-liveness dichotomy. We separate the liveness and safety in shard consensus, allowing us to dynamically tune shard parameters to achieve essentially optimal efficiency for the current corruption ratio of the system. We start by sampling a relatively small shard (possibly with a small honesty ratio), and we carefully trade-off safety for liveness in the consensus mechanism to tolerate small honesty without losing safety. However, for a shard to be live, a higher honesty ratio is required in the worst case. To detect liveness failures, we use a so-called control chain that is always live and safe. Shards that are detected to be not live are resampled with increased shard size and liveness tolerance until they are live, ensuring that all shards are always safe and run with optimal efficiency. As a concrete example, considering a population of 10K parties with at most 30% corruption and 60-bit security, previous designs required over 5800 parties in each shard to guarantee security. Our design requires only 1713 parties in the worst case with maximal corruption, and in the optimistic case works with only 35 parties without compromising security. Moreover, in this highly concurrent execution setting, it is paramount to guarantee that both the sharded ledger protocol and its sub protocols (i.e., the shards) are secure under composition. To prove the security of our approach, we present ideal functionalities capturing a sharded ledger as well as ideal functionalities capturing the control chain and individual shard consensus, which needs adjustable liveness. We further formalize our protocols and prove that they securely realize the sharded ledger functionality in the UC framework.

The inherent difficulty of maintaining stateful environments over long periods of time gave rise to the paradigm of serverless computing, where mostly-stateless components are deployed on demand to handle computation tasks, and are teared down once their task is complete. Serverless architecture could offer the added benefit of improved resistance to targeted denial-of-service attacks, by hiding from the attacker the physical machines involved in the protocol until after they complete their work. Realizing such protection, however, requires that the protocol only uses stateless parties, where each party sends only one message and never needs to speaks again. Perhaps the most famous example of this style of protocols is the Nakamoto consensus protocol used in Bitcoin: A peer can win the right to produce the next block by running a local lottery (mining), all while staying covert. Once the right has been won, it is executed by sending a single message. After that, the physical entity never needs to send more messages. We refer to this as the You-Only-Speak-Once (YOSO) property, and initiate the formal study of it within a new model that we call the YOSO model. Our model is centered around the notion of roles, which are stateless parties that can only send a single message. Crucially, our modelling separates the protocol design, that only uses roles, from the role-assignment mechanism, that assigns roles to actual physical entities. This separation enables studying these two aspects separately, and our YOSO model in this work only deals with the protocol-design aspect. We describe several techniques for achieving YOSO MPC; both computational and information theoretic. Our protocols are synchronous and provide guaranteed output delivery (which is important for application domains such as blockchains), assuming honest majority of roles in every time step. We describe a practically efficient computationally-secure protocol, as well as a proof-of-concept information theoretically secure protocol.

Abstract Modern cryptographic algorithms have an enormous key diversity, so if we want to test their strength for all the keys, it will take practically an infinite time. To avoid this, we use the sampling method, in which we examine a much smaller number of keys n and then we make estimation for the total key population N with a predetermined sampling error. For the generation of the n cipher outputs (samples) with the n corresponding keys, the critical questions are how many samples we will test and how large must be the size of each sample. The general rule is that, the sampling error is reduced as we increase the number of the samples. But since the tests must be executed in an acceptable time, we must compromise the above rule with some additional factors, such as the type of the cryptographic cipher, the kind and the size of the plain information and of course the available computer power. In this study we examine the interrelations of all the above factors, and we propose applicable solutions. Keywords: Cryptography, Data encryption, Communication security, Computer security, Data security, Information security.

We introduce the first construction for secure two-party computation of Poisson regression, which enables two parties who hold shares of the input samples to learn only the resulting Poisson model while protecting the privacy of the inputs. Our construction relies on new protocols for secure fixed-point exponentiation and correlated matrix multiplications. Our secure exponentiation construction avoids expensive bit decomposition and achieves orders of magnitude improvement in both online and offline costs over state of the art works. As a result, the dominant cost for our secure Poisson regression are matrix multiplications with one fixed matrix. We introduce a new technique, called correlated Beaver triples, which enables many such multiplications at the cost of roughly one matrix multiplication. This further brings down the cost of secure Poisson regression. We implement our constructions and show their extreme efficiency. In a LAN setting, our secure exponentiation for 20-bit fractional precision takes less than 0.07ms with a batch-size of 100,000. One iteration of secure Poisson regression on a dataset with 10,000 samples with 1000 binary features needs about 65.82s in the offline phase, 55.14s in the online phase and 17MB total communication. For several real datasets this translates into training that takes seconds and only a couple of MB communication.

Iterative methods are a standard technique in many areas of scientific computing. The key idea is that a function is applied repeatedly until the resulting sequence converges to the correct answer. When applying such methods in a secure computation methodology (for example using MPC, FHE, or SGX) one either needs to perform enough steps to ensure convergence irrespective of the input data, or one needs to perform a convergence test within the algorithm, and this itself leads to a leakage of data. Using the Banach Fixed Point theorem, and its extensions, we show that this data-leakage can be quantified. We then apply this to a secure (via MPC) implementation of the PageRank methodology. For PageRank we show that allowing this small amount of data-leakage produces a much more efficient secure implementation, and that for many underlying graphs this `leakage' is already known to any attacker.

Bitcoin transfers value on a public ledger of transactions anyone can verify. Coin ownership is defined in terms of public keys. Despite potential use for private transfers, research has shown that users’ activity can often be traced in practice. Businesses have been built on dragnet surveillance of Bitcoin users because of this lack of strong privacy, which harms its fungibility, a basic property of functional money. Although the public nature of this design lacks strong guarantees for privacy, it does not rule it out. A number of methods have been proposed to strengthen privacy. Among these is CoinJoin, an approach based on multiparty transactions that can introduce ambiguity and break common assumptions that underlie heuristics used for deanonymization. Existing implementations of CoinJoin have several limitations which may partly explain the lack of their widespread adoption. This work introduces WabiSabi, a new protocol for centrally coordinated CoinJoin implementations utilizing keyed verification anonymous credentials and homomorphic value commitments. This improves earlier approaches which utilize blind signatures in both privacy and flexibility, enabling novel use cases and reduced overhead.