Advances in cryptography have enabled the features of confidentiality, security, and integrity on small embedded devices such as IoT devices. While mathematically strong, the platform on which an algorithm is implemented plays a significant role in the security of the final product. Side-channel attacks exploit the variations in the system’s physical characteristics to obtain information about the sensitive data. In our scenario, a software implementation of a cryptographic algorithm is flashed on devices from different manufactures with the same instruction set configured for identical execution. To analyze the influence of the microarchitecture on side-channel leakage, we acquire thirty-two sets of power traces from four physical devices. While we notice minor differences in the leakage behaviour for different physical boards from the same manufacturer, our results confirm that the difference in microarchitecture implementations will leak different side-channel information. We also show that TVLA leakage prediction should be treated with caution as it is sensitive to both false positives and negatives.

Practical side-channel attacks on recent devices may be challenging due to the poor quality of acquired signals. It can originate from different factors, such as the growing architecture complexity, especially in System-on-Chips, creating unpredictable and concurrent operation of multiple signal sources on the device. This work makes use of mixture distributions to formalize this complexity, allowing us to explain the benefit of using a technique like Scatter, where different samples of the traces are aggregated into the same distribution. Some observations of the conditional mixture distributions are made in order to model the leakage in such context. From this, we infer local coherency of information held in the distribution as a general property of side-channel leakage in mixture distributions. This leads us to introduce how spatial analysis tools, such as Moran's Index, can be used to significantly improve non-profiled attacks compared to other techniques from the state-of-the-art. Exploitation of this technique is experimentally shown very promising, as demonstrated on two AES implementations including masking and shuffling countermeasures.

Symmetric Searchable Encryption (SSE) allows users to outsource encrypted data to a possibly untrusted remote location while simultaneously being able to perform keyword search directly through the stored ciphertexts. An ideal SSE scheme should reveal no information about the content of the encrypted information nor about the searched keywords and their mapping to the stored files. However, most of the existing SSE schemes fail to fulfill this property since in every search query, some information potentially valuable to a malicious adversary is leaked. The leakage becomes even bigger if the underlying SSE scheme is dynamic. In this paper, we minimize the leaked information by proposing a forward and backward private SSE scheme in a multi-client setting. Our construction achieves optimal search and update costs. In contrast to many recent works, each search query only requires one round of interaction between a user and the cloud service provider. In order to guarantee the security and privacy of the scheme and support the multi-client model (i.e. synchronization between users), we exploit the functionality offered by AMD's Secure Encrypted Virtualization (SEV).

In this paper, we show that a software implementation of CCA secure Saber KEM protected by first-order masking and shuffling can be broken by deep learning-based power analysis. Using an ensemble of deep neural networks created at the profiling stage, we can recover the session key and the long-term secret key from $257 \times N$ and $24 \times 257 \times N$ traces, respectively, where $N$ is the number of repetitions of the same measurement. The value of $N$ depends on the implementation, environmental factors, acquisition noise, etc.; in our experiments $N = 10$ is enough to succeed. The neural networks are trained on a combination of 80% of traces from the profiling device with a known shuffling order and 20% of traces from the device under attack captured for all-0 and all-1 messages. ``Spicing'' the training set with traces from the device under attack helps minimize the negative effect of device variability.

Several constructions of Mutually Unbiased Bases (MUBs) borrow tools from combinatorial objects. In this paper we focus how one can construct Approximate Real MUBs (ARMUBs) with improved parameters using results from the domain of Resolvable Block Designs (RBDs). We first explain the generic idea of our strategy in relating the RBDs with MUBs/ARMUBs, which are sparse (the basis vectors have small number of non-zero co-ordinates). Then specific parameters are presented, for which we can obtain new classes and improve the existing results. To be specific, we present an infinite family of $\lceil\sqrt{d}\rceil$ many ARMUBs for dimension $d = q(q+1)$, where $q \equiv 3 \bmod 4$ and it is a prime power, such that for any two vectors $v_1, v_2$ belonging to different bases, $|\braket{v_1|v_2}| < \frac{2}{\sqrt{d}}$. We also demonstrate certain cases, such as $d = sq^2$, where $q$ is a prime power and $sq \equiv 0 \bmod 4$. These findings subsume and improve our earlier results in [Cryptogr. Commun. 13, 321-329, January 2021]. This present construction idea provides several infinite families of such objects, not known in the literature, which can find efficient applications in quantum information processing for the sparsity, apart from suggesting that parallel classes of RBDs are intimately linked with MUBs/ARMUBs.

The bulk of Internet interactions is highly redundant and also security sensitive. To reduce communication bandwidth and provide a desired level of security, a data stream is first compressed to squeeze out redundant bits and then encrypted using authenticated encryption. This generic solution is very flexible and works well for any pair of (compression, encryption) algorithms. Its downside, however, is the fact that the two algorithms are designed independently. One would expect that designing a single algorithm that compresses and encrypts (called compcrypt) should produce benefits in terms of efficiency and security. The work investigates how to design a compcrypt algorithm using the ANS compression. First, we examine basic properties of ANS and show that a plain ANS with a hidden encoding table can be broken by statistical attacks. Next, we study ANS behaviour when its states are chosen at random. Our compcrypt algorithm is built using ANS with randomised state jumps and a sponge MonkeyDuplex encryption. Its security and efficiency are discussed. The design provides 128-bit security for both confidentiality and integrity/authentication. Our implementation experiments show that our compcrypt algorithm processes symbols with a rate up to 269 MB/s (with a slight loss of compression rate).

Many privacy preserving blockchain and e-voting systems are based on the modified ElGamal scheme that supports homomorphic addition of encrypted values. For practicality reasons though, decryption requires the use of precomputed discrete-log (dlog) lookup tables along with algorithms like Shanks's baby-step giant-step and Pollard's kangaroo. We extend the Shanks approach as it is the most commonly used method in practice due to its determinism and simplicity, by proposing a truncated lookup table strategy to speed up decryption and reduce memory requirements. While there is significant overhead at the precomputation phase, these costs can be parallelized and only paid once and for all. As a starting point, we evaluated our solution against the widely-used secp family of elliptic curves and show that we can achieve storage reduction by 7x-14x, depending on the group size. Our algorithm can be immediately imported to existing works, especially when the range of encrypted values is known, such as in Zether, PGC and Solidus protocols.

Expanding graphs are known due to their remarkable applications to Computer Science. We are looking for their applications to Post Quantum Cryptography. One of them is postquantum analog of Diffie-Hellman protocol in the area of intersection of Noncommutative and Multivariate Cryptographies .This graph based protocol allows correspondents to elaborate collision cubic transformations of affine space Kn defined over finite commutative ring K. Security of this protocol rests on the complexity of decomposition problem of nonlinear polynomial map into given generators. We show that expanding graphs allow to use such output as a ‘’seed’’ for secure construction of infinite sequence of cubic transformation of affine spaces of increasing dimension. Correspondents can use the sequence of maps for extracting passwords for one time pads in alphabet K and other symmetric or asymmetric algorithms. We show that cubic polynomial maps of affine spaces of prescribed dimension can be used for transition of quadratic public keys of Multivariate Cryptography into the shadow of private areas.

Game-theoretic analyses of cryptocurrencies and---more generally---blockchain-based decentralized ledgers offer insight on their economic robustness and behavior when even their underpinning cryptographic assumptions fail. In this work we utilize the recently proposed blockchain adaptation of the rational protocol design (RPD) framework [EUROCRYPT '18] to analyze 51% double-spending attacks against Nakamoto-style proof-of-work based cryptocurrencies. We first observe a property of the originally proposed utility class that yields an unnatural conclusion against such attacks, and show how to devise a utility that avoids this pitfall and makes predictions that match the observable behavior---i.e., that renders attacking a dominant strategy in settings where an attack was indeed observed in reality. We then propose a generic remedy to the underlying protocol parameters that provably deter adversaries controlling a majority of the system's resources from attacks on blockchain consistency, including the 51% double-spending attack. This can be used as guidance to patch systems that have suffered such attacks, e.g., Ethereum Classic and Bitcoin Cash, and serves as a demonstration of the power of game-theoretic analyses.

In the recent ePrint report 2021/583 titled "Entropoid-based cryptography is group exponentiation in disguise" Lorenz Panny gave a cryptanalysis of the entropoid based instances proposed in our eprint report 2021/469. We acknowledge the correctness of his claims for the concrete instances described in our original report 2021/469. However, we find that claims for the general applicability of his attack on the general Entropoid framework are misleading. Namely, based on the Theorem 1 in his report, which claims that for every entropic quasigroup $(G, *)$, there exists an Abelian group $(G, \cdot)$, commuting automorphisms $\sigma$, $\tau$ of $(G, \cdot)$, and an element $c \in G$, such that $x * y = \sigma(x) \cdot \tau(y) \cdot c$ the author infers that \emph{"all instantiations of the entropoid framework should be breakable in polynomial time on a quantum computer."} There are two misleading parts in these claim: \textbf{1.} It is implicitly assumed that all instantiations of the entropoid framework would define entropic quasigroups - thus fall within the range of algebraic objects addressed by Theorem 1. \emph{We will show a construction of entropic groupoids that are not quasigroups}; \textbf{2.} It is implicitly assumed that finding the group $(G, \cdot)$, the commuting automorphisms $\sigma$ and $\tau$ and the constant $c$ \emph{would be easy for every given entropic operation} $*$ and its underlying groupoid $(G, *)$. However, the provable existence of a mathematical object \emph{does not guarantee an easy finding} of that object. Treating the original entropic operation $* := *_1$ as a one-dimensional entropic operation, we construct multidimensional entropic operations $* := *_m$, for $m\geq 2$ and we show that newly constructed operations do not have the properties of $* = *_1$ that led to the recovery of the automorphism $\sigma$, the commutative operation $\cdot$ and the linear isomorphism $\iota$ and its inverse $\iota^{-1}$. We give proof-of-concept implementations in SageMath 9.2 for the new multidimensional entropic operations $* := *_m$ defined over several basic operations $* := *_1$ and we show how the non-associative and non-commutative exponentiation works for the key exchange and digital signature schemes originally proposed in report 2021/469.

Lossy trapdoor functions, introduced by Peikert and Waters (STOC '08), can be initialized in one of two indistinguishable modes: in injective mode, the function preserves all information about its input, and can be efficiently inverted given a trapdoor, while in lossy mode, the function loses some information about its input. Such functions have found countless applications in cryptography, and can be constructed from a variety of number-theoretic or algebraic ``Cryptomania'' assumptions. In this work, we introduce targeted lossy functions (TLFs), which relax lossy trapdoor functions along two orthogonal dimensions. First, they do not require an inversion trapdoor in injective mode. Second, the lossy mode of the function is initialized with some target input, and the function is only required to lose information about this particular target. The injective and lossy modes should be indistinguishable even given the target. We construct TLFs from ``Minicrypt'' assumptions, namely, injective pseudorandom generators, or even one-way functions under a natural relaxation of injectivity. We then generalize TLFs to incorporate branches, and construct all-injective-but-one and all-lossy-but-one variants. We show a wide variety of applications of targeted lossy functions. In several cases, we get the first Minicrypt constructions of primitives that were previously only known under Cryptomania assumptions. Our applications include: -Pseudo-entropy functions from one-way functions. -Deterministic leakage-resilient message-authentication codes and improved leakage-resilient symmetric-key encryption from one-way functions. -Extractors for extractor-dependent sources from one-way functions. -Selective-opening secure symmetric-key encryption from one-way functions. -A new construction of CCA PKE from (exponentially secure) trapdoor functions and injective pseudorandom generators. We also discuss a fascinating connection to distributed point functions.

We present a history of how cryptographic key sizes have been determined for various schemes.

Apple's file-sharing service AirDrop leaks phone numbers and email addresses by exchanging vulnerable hash values of the user's own contact identifiers during the authentication handshake with nearby devices. In a paper presented at USENIX Security'21, we theoretically describe two attacks to exploit these vulnerabilities and propose "PrivateDrop" as a privacy-preserving drop-in replacement for Apple's AirDrop protocol based on private set intersection. In this demo, we show how these vulnerabilities are efficiently exploitable via Wi-Fi and physical proximity to a target. Privacy and security implications include the possibility of conducting advanced spear phishing attacks or deploying multiple "collector" devices in order to build databases that map contact identifiers to specific locations. For our proof-of-concept, we leverage a custom rainbow table construction to reverse SHA-256 hashes of phone numbers in a matter of milliseconds. We discuss the trade-off between success rate and storage requirements of the rainbow table and, after following responsible disclosure with Apple, we publish our proof-of-concept implementation as "AirCollect" on GitHub.

Correct application of masking on hardware implementation of cryptographic primitives necessitates the instantiation of registers in order to achieve the non-completeness (commonly said to stop the propagation of glitches). This sometimes leads to a high latency overhead, making the implementation not necessarily suitable for the underlying application. As a concrete example, this holds for Keccak. Application of d + 1 Domain Oriented Masking (DOM) on a round-based implementation of Keccak leads to the introduction of two register stages per round, i.e., two times higher latency. On the other hand, Rhythmic-Keccak, introduced in CHES 2018, unrolls two rounds to half the latency compared to an unprotected ordinary round-based implementation. To that end, td + 1 masking is used which requires a notable area, and – apart from the difficulty to construct – its extension to higher orders seems beyond the bounds of feasibility. In this paper, we focus on d + 1 masking and introduce a methodology which enables us to stay with the latency of an unprotected round-based implementation, i.e., one register stage per round. While being secure under glitch-extended probing model, we provide a general design where the desired security order can be easily adjusted without any effect on the above-given latency. Compared to the Rhythmic-Keccak, the synthesis results show that our first-order design is able to accomplish the entire operations of Keccak-f[200] in the same period of time while decreasing the area by 74.5%. Notably, our implementations achieve around 30% less delay compared to the corresponding original DOM-Keccak designs.

Traitor tracing aims to identify the source of leaked decryption keys. Since the "traitor" can try to hide their key within obfuscated code in order to evade tracing, the tracing algorithm should work for general, potentially obfuscated, decoder programs. In the setting of such general decoder programs, prior work uses black box tracing: the tracing algorithm ignores the implementation of the decoder, and instead traces just by making queries to the decoder and observing the outputs. We observe that, in some settings, such black box tracing leads to consistency and user privacy issues. On the other hand, these issues do not appear inherent to white box tracing, where the tracing algorithm actually inspects the decoder implementation. We therefore develop new white box traitor tracing schemes providing consistency and/or privacy. Our schemes can be instantiated under various assumptions ranging from public key encryption and NIZKs to indistinguishability obfuscation, with different trade-offs. To the best of our knowledge, ours is the first work to consider white box tracing in the general decoder setting.

We show equivalence between the existence of one-way functions and the existence of a \emph{sparse} language that is hard-on-average w.r.t. some efficiently samplable ``high-entropy'' distribution. In more detail, the following are equivalent: - The existence of a $S(\cdot)$-sparse language $L$ that is hard-on-average with respect to some samplable distribution with Shannon entropy $h(\cdot)$ such that $h(n)-\log(S(n)) \geq 4\log n$; - The existence of a $S(\cdot)$-sparse language $L \in \NP$, that is hard-on-average with respect to some samplable distribution with Shannon entropy $h(\cdot)$ such that $h(n)-\log(S(n)) \geq n/3$; - The existence of one-way functions. Our results are inspired by, and generalize, the recent elegant paper by Ilango, Ren and Santhanam (ECCC'21), which presents similar characterizations for concrete sparse languages.

We study several strengthening of classical circular security assumptions which were recently introduced in four new lattice-based constructions of indistinguishability obfuscation: Brakerski-Döttling-Garg-Malavolta (Eurocrypt 2020), Gay-Pass (STOC 2021), Brakerski-Döttling-Garg-Malavolta (Eprint 2020) and Wee-Wichs (Eprint 2020). We provide explicit counterexamples to the {\em $2$-circular shielded randomness leakage} assumption w.r.t.\ the Gentry-Sahai-Waters fully homomorphic encryption scheme proposed by Gay-Pass, and the {\em homomorphic pseudorandom LWE samples} conjecture proposed by Wee-Wichs. Our work suggests a separation between classical circular security of the kind underlying un-levelled fully-homomorphic encryption from the strengthened versions underlying recent iO constructions, showing that they are not (yet) on the same footing. Our counterexamples exploit the flexibility to choose specific implementations of circuits, which is explicitly allowed in the Gay-Pass assumption and unspecified in the Wee-Wichs assumption. Their indistinguishabilty obfuscation schemes are still unbroken. Our work shows that the assumptions, at least, need refinement. In particular, generic leakage-resilient circular security assumptions are delicate, and their security is sensitive to the specific structure of the leakages involved.

In this paper, we show that standard model black-box reductions naturally lift to various setup assumptions, such as the random oracle (ROM) or ideal cipher model. Concretely, we prove that a black-box reduction from a security notion P to security notion Q in the standard model can be turned into a non-programmable black-box reduction from P_O to Q_O in a model with a setup assumption O, where P_O and Q_O are the natural extensions of P and Q to a model with a setup assumption O. Our results rely on a generalization of the recent framework by Hofheinz and Nguyen (PKC 2019) to support primitives which make use of a trusted setup. Our framework encompasses standard idealized settings like the random oracle and the ideal cipher model. At the core of our main result lie novel properties of negligible functions that can be of independent interest.

A two-party authenticated key exchange (AKE) protocol allows each of the two parties to share a common secret key over insecure channels even in the presence of active adversaries who can actively control and modify the exchanged messages. To capture the various kind of malicious behaviors of the adversaries, there have been lots of efforts to define the security models. Amongst them, the extended Canetti-Krawczyk (eCK) security model is considered as one of the strongest ones and widely adopted. In this paper, we present a pairing-based eCK-secure AKE protocol in the standard model. The underlying assumptions of our construction are the hardness of the decisional bilinear Diffie-Hellman (DBDH) problem and the existence of pseudorandom functions. It is notable that the previous constructions either relied their security on random oracles or used somewhat strong assumptions such as the existence of strong-pseudorandom functions. We believe our construction is well-suited for real-world implementations such as the TLS protocol suite since our construction is simple and based on standard assumptions without random oracles.

SHA-256 is a secure cryptographic hash function. As such, its output should not have any detectable property. This paper describes three bit strings whose hashes by SHA-256 are nevertheless correlated in a non-trivial way: the first half of their hashes XORs to zero. They were found by “brute-force”, without exploiting any cryptographic weakness in the hash function itself. This does not threaten the security of the hash function and does not have any cryptographic implication. This is an example of a large “combinatorial” computation in which at least 8.7 × 10 22 integer operations have been performed. This was made possible by the combination of: 1) recent progress on algorithms for the underlying problem, 2) creative use of "dedicated" hardware accelerators, 3) adapted implementations of the relevant algorithms that could run on massively parallel machines. The actual computation was done on aging hardware. It required seven calendar months using two obsolete second-hand bitcoin mining devices converted into "useful" computational devices. A second step required 570 CPU-years on an 8-year old IBM BlueGene/Q computer, a few weeks before it was scrapped. To the best of our knowledge, this is the first practical 128-bit collision-like result obtained by brute-force, and it is the first bitcoin miner-accelerated computation.

We study new candidates for symmetric cryptographic primitives that leverage alternation between linear functions over $\mathbb{Z}_2$ and $\mathbb{Z}_3$ to support fast protocols for secure multiparty computation (MPC). This continues the study of weak pseudorandom functions of this kind initiated by Boneh et al. (TCC 2018) and Cheon et al. (PKC 2021). We make the following contributions. (Candidates). We propose new designs of symmetric primitives based on alternating moduli. These include candidate one-way functions, pseudorandom generators, and weak pseudorandom functions. We propose concrete parameters based on cryptanalysis. (Protocols). We provide a unified approach for securely evaluating modulus-alternating primitives in different MPC models. For the original candidate of Boneh et al., our protocols obtain at least 2x improvement in all performance measures. We report efficiency benchmarks of an optimized implementation. (Applications). We showcase the usefulness of our candidates for a variety of applications. This includes short "Picnic-style" signature schemes, as well as protocols for oblivious pseudorandom functions, hierarchical key derivation, and distributed key generation for function secret sharing.

In recent years, research has shown the networking layer’s significant influence on the scalability, security, and privacy of blockchain systems. Such large-scale networks however exhibit a degree of complexity that demands model-based simulations as real-world experiments are often not possible. In this work, we methodically characterize blockchain networks by reference to the paradigmatic Bitcoin peer-to-peer network, explore the state-of-the-art protocols, and emphasize this key design space. To this end, we conducted a longitudinal measurement study on the Bitcoin network, from which we extract a comprehensive network model and implement it as part of the bns network simulation framework. We validate the model in comparison to real-world measurements as well as to results from related work. Moreover, we experimentally show how network utilization and miners’ geographical location impact the block propagation characteristics.

Many recent private set intersection (PSI) protocols encode input sets as polynomials. We consider the more general notion of an oblivious key-value store (OKVS), which is a data structure that compactly represents a desired mapping $k_i \mapsto v_i$. When the $v_i$ values are random, the OKVS data structure hides the $k_i$ values that were used to generate it. The simplest (and size-optimal) OKVS is a polynomial $p$ that is chosen using interpolation such that $p(k_i)=v_i$. We initiate the formal study of oblivious key-value stores, and show new constructions resulting in the fastest OKVS to date. Similarly to cuckoo hashing, current analysis techniques are insufficient for finding {\em concrete} parameters to guarantee a small failure probability for our OKVS constructions. Moreover, it would cost too much to run experiments to validate a small upper bound on the failure probability. We therefore show novel techniques to amplify an OKVS construction which has a failure probability $p$, to an OKVS with a similar overhead and failure probability $p^c$. Setting $p$ to be moderately small enables to validate it by running a relatively small number of $O(1/p)$ experiments. This validates a $p^c$ failure probability for the amplified OKVS. Finally, we describe how OKVS can significantly improve the state of the art of essentially all variants of PSI. This leads to the fastest two-party PSI protocols to date, for both the semi-honest and the malicious settings. Specifically, in networks with moderate bandwidth (e.g., 30 - 300 Mbps) our malicious two-party PSI protocol has 40\% less communication and is 20-40\% faster than the previous state of the art protocol, even though the latter only has heuristic confidence.

Secure multi-party computation allows mutually distrusting parties to compute securely over their private data. However, guaranteeing output delivery to honest parties when the adversarial parties may abort the protocol has been a challenging objective. As a representative task, this work considers two-party coin-tossing protocols with guaranteed output delivery, a.k.a., fair coin-tossing. In the information-theoretic plain model, as in two-party zero-sum games, one of the parties can force an output with certainty. In the commitment-hybrid, any $r$-message coin-tossing protocol is ${1/\sqrt r}$-unfair, i.e., the adversary can change the honest party's output distribution by $1/\sqrt r$ in the statistical distance. Moran, Naor, and Segev (TCC--2009) constructed the first $1/r$-unfair protocol in the oblivious transfer-hybrid. No further security improvement is possible because Cleve (STOC--1986) proved that $1/r$-unfairness is unavoidable. Therefore, Moran, Naor, and Segev's coin-tossing protocol is optimal. However, is oblivious transfer necessary for optimal fair coin-tossing? Maji and Wang (CRYPTO--2020) proved that any coin-tossing protocol using one-way functions in a black-box manner is at least $1/\sqrt r$-unfair. That is, optimal fair coin-tossing is impossible in Minicrypt. Our work focuses on tightly characterizing the hardness of computation assumption necessary and sufficient for optimal fair coin-tossing within Cryptomania, outside Minicrypt. Haitner, Makriyannia, Nissim, Omri, Shaltiel, and Silbak (FOCS--2018 and TCC--2018) proved that better than $1/\sqrt r$-unfairness, for any constant $r$, implies the existence of a key-agreement protocol. We prove that any coin-tossing protocol using public-key encryption (or, multi-round key agreement protocols) in a black-box manner must be $1/\sqrt r$-unfair. Next, our work entirely characterizes the additional power of secure function evaluation functionalities for optimal fair coin-tossing. We augment the model with an idealized secure function evaluation of $f$, \aka, the $f$-hybrid. If $f$ is complete, that is, oblivious transfer is possible in the $f$-hybrid, then optimal fair coin-tossing is also possible in the $f$-hybrid. On the other hand, if $f$ is not complete, then a coin-tossing protocol using public-key encryption in a black-box manner in the $f$-hybrid is at least $1/\sqrt r$-unfair.

Code-based public key cryptosystems are one of the main techniques available in the area of Post-Quantum Cryptography. This work aims to propose a key encapsulation mechanism (KEM) with short ciphertext and secret key. Our goal is achieved in two steps. We first present a public key encryption (PKE) scheme, basicPKE, using a parity check matrix of Maximum Distance Separable (MDS) code as the public key matrix. In our construction, we exploit the structure of a companion matrix to obtain an MDS code which significantly reduces the storage of the secret key. The scheme basicPKE provides security against Indistinguishability under Chosen Plaintext Attacks (IND-CPA). Secondly, following the design framework of basicPKE, we construct another PKE scheme, fullPKE, that leads us to design our KEM scheme, fullKEM. We have shown that the scheme fullPKE is secure against One-Wayness under Plaintext and Validity Checking Attacks (OW-PCVA) and the scheme fullKEM achieves security against Indistinguishability under Chosen Ciphertext Attacks (IND-CCA) in the random oracle model. Moreover, our KEM can be shown to accomplish post-quantum security in the quantum random oracle model.

Proving the security of masked implementations in theoretical models that are relevant to practice and match the best known attacks of the side-channel literature is a notoriously hard problem. The random probing model is a good candidate to contribute to this challenge, due to its ability to capture the continuous nature of physical leakage (contrary to the threshold probing model), while also being convenient to manipulate in proofs and to automate with verification tools. Yet, despite recent progresses in the design of masked circuits with good asymptotic security guarantees in this model, existing results still fall short when it comes to analyze the security of concretely useful circuits under realistic noise levels and with low number of shares. In this paper, we contribute to this issue by introducing a new composability notion, the Probe Distribution Table (PDT), and a new tool (called STRAPS, for the Sampled Testing of the RAndom Probing Security). Their combination allows us to significantly improve the tightness of existing analyses in the most practical (low noise, low number of shares) region of the design space. We illustrate these improvements by quantifying the random probing security of an AES S-box circuit, masked with the popular multiplication gadget of Ishai, Sahai and Wagner from Crypto 2003, with up to six shares.

Symmetric Searchable Encryption (SSE) schemes enable keyword searches over encrypted documents. To obtain efficiency, SSE schemes incur a certain amount of leakage. The vast majority of the literature on SSE considers only leakage from one component of the overall SSE system, the encrypted search index. This component is used to identify which documents to return in response to a keyword query. The actual fetching of the documents is left to another component, usually left unspecified in the literature, but generally envisioned as a simple storage system matching document identifiers to encrypted documents. This raises the question: do SSE schemes actually protect the security of data and queries when considered from a system-wide viewpoint? We answer this question in the negative. We do this by introducing a new inference attack that achieves practically efficient, highly scalable, accurate query reconstruction against end-to-end SSE systems. In particular, our attack works even when the SSE schemes are built in the natural way using the state-of-the-art techniques (namely, volume-hiding encrypted multi-maps) designed to suppress leakage and protect against previous generations of attack. A second question is whether the state-of-the-art leakage suppression techniques can instead be applied on a system-wide basis, to protect both the encrypted search index and the encrypted document store, to produce efficient SSE systems. We also answer this question in the negative. To do so, we implement SSE systems using those state-of-the-art leakage suppression methods, and evaluate their performance. We show that storage overheads range from $100\times$ to $800\times$ while bandwidth overheads range from $20\times$ to $100\times$, as compared to a naive baseline system. Our results motivate the design of new SSE systems that are designed with system-wide security in mind from the outset. In this regard, we show that one such SSE system due to Chen et al. (IEEE INFOCOM 2018), with provable security guarantees based on differential privacy, is also vulnerable to our new attack. In totality, our results force a re-evaluation of how to build end-to-end SSE systems that offer both security and efficiency.

Side-channel and fault injection attacks reveal secret information by monitoring or manipulating the physical effects of computations involving secret variables. Circuit-level countermeasures help to deter these attacks, and traditionally such countermeasures have been developed for each attack vector separately. We demonstrate a multipurpose ring oscillator design - Programmable Ring Oscillator (PRO) to address both fault attacks and side-channel attacks in a generic, application-independent manner. PRO, as an integrated primitive, can provide on-chip side-channel resistance, power monitoring, and fault detection capabilities to a secure design. We present a grid of PROs monitoring the on-chip power network to detect anomalies. Such power anomalies may be caused by external factors such as electromagnetic fault injection and power glitches, as well as by internal factors such as hardware Trojans. By monitoring the frequency of the ring oscillators, we are able to detect the on-chip power anomaly in time as well as in location. Moreover, we show that the PROs can also inject a random noise pattern into a design's power consumption. By randomly switching the frequency of a ring oscillator, the resulting power-noise pattern significantly reduces the power-based side-channel leakage of a cipher. We discuss the design of PRO and present measurement results on a Xilinx Spartan-6 FPGA prototype, and we show that side-channel and fault vulnerabilities can be addressed at a low cost by introducing PRO to the design. We conclude that PRO can serve as an application-independent, multipurpose countermeasure.

The idea of smart contracts has been around for a long time. The introduction of Ethereum has taken the concept of smart contracts to new heights because of its integration with Blockchain technology. As a result, the applications of smart contracts have also surged in areas such as e-Voting, Insurance, Crowdfunding, etc. In this paper, we aim to present the construction of a “Fully Anonymous e-Voting” protocol using the concepts of zkHawk and Zcash. zkHawk is a novel smart contract protocol designed during this Ph.D. that improves upon the Hawk protocol by solving the underlying anonymity problem of a trusted manager. We will leverage the concept of zk-SNARKs in Zcash to carry out the voting phase of the election and the zkHawk smart contract protocol to tally the results of the election. The voting phase employing Zcash will be initially designed with Non-Universal zk-SNARKs and improved upon with Universal zk-SNARKs.

Consider the identification (ID) via channels problem, where a receiver decides whether the transmitted identifier is its identifier, rather than decoding it. This model allows to transmit identifiers whose size scales doubly-exponentially in the blocklength, unlike common transmission codes with exponential scaling. Binary constant-weight codes (CWCs) suffice to achieve the ID capacity. Relating parameters of a binary CWC to the minimum distance of a code and using higher-order correlation moments, two upper bounds on binary CWC sizes are proposed. These bounds are also upper bounds on identifier sizes for ID codes constructed by using binary CWCs. We propose two constructions based on optical orthogonal codes (OOCs), which are used in optical multiple access schemes, have constant-weight codewords, and satisfy cyclic cross-correlation and auto-correlation constraints. These constructions are modified and concatenated with outer Reed-Solomon codes to propose new binary CWCs being optimal for ID. Improvements to the finite-parameter performance of both our and existing code constructions are shown by using outer codes with larger minimum distance vs. blocklength ratios. We illustrate ID regimes for which our ID code constructions perform significantly better than existing constructions. An extensive list of other modified OOCs that can be used as binary CWCs is provided.

The Signal protocol is used in many messaging applications today. While it is an active research topic to design a post-quantum variant of the protocol, no such variant is currently realized in the real world. In the following document we describe a hybrid version of the Signal protocol, that will be implemented to achieve post-quantum security for Tutanota’s end-to-end encrypted e-mails.

This study proposes a chosen-ciphertext side-channel attack against a lattice-based key encapsulation mechanism (KEM), the third-round candidate of the national institute of standards and technology (NIST) standardization project. Unlike existing attacks that target operations such as inverse NTT and message encoding/decoding, we target Barrett Reduction in the decapsulation phase of CRYSTALS-KYBER to obtain a secret key. We show that a sensitive variable-dependent leakage of Barrett Reduction exposes an entire secret key. The results of experiments conducted on the ARM Cortex-M4 microcontroller accomplish a success rate of 100%. We only need six chosen ciphertexts for KYBER512 and KYBER768 and eight chosen ciphertexts for KYBER1024. We also show that the m4 scheme of the pqm4 library, an implementation with the ARM Cortex-M4 specific optimization (typically in assembly), is vulnerable to the proposed attack. In this scheme, six, nine, and twelve chosen ciphertexts are required for KYBER512, KYBER768, and KYBER1024, respectively.

OPAQUE [Jarecki et al., Eurocrypt 2018] is an asymmetric password authenticated key exchange (aPAKE) protocol that is being developed as an Internet standard and for use within TLS 1.3. OPAQUE combines an Oblivious PRF (OPRF) with an authenticated key exchange to provide strong security properties, including security against pre-computation attacks (called saPAKE security). However, the security of OPAQUE relies crucially on the security of the OPRF. If the latter breaks (by cryptanalysis, quantum attacks or security compromise), the user's password is exposed to an offline dictionary attack. To address this weakness, we present KHAPE, a variant of OPAQUE that does not require the use of an OPRF to achieve aPAKE security, resulting in improved resilience and near-optimal computational performance. An OPRF can be optionally added to KHAPE, for enhanced saPAKE security, but without opening the password to an offline dictionary attack upon OPRF compromise. In addition to resilience to OPRF compromise, a DH-based implementation of KHAPE (using HMQV) offers the best performance among aPAKE protocols in terms of exponentiations with less than the cost of an exponentiation on top of an UNauthenticated Diffie-Hellman exchange. KHAPE uses three messages if the server initiates the exchange or four when the client does (one more than OPAQUE in the latter case). All results in the paper are proven within the UC framework in the ideal cipher model. Of independent interest is our treatment of key-hiding AKE which KHAPE uses as a main component as well as our UC proofs of AKE security for protocols 3DH (a basis of Signal), HMQV and SKEME, that we use as efficient instantiations of KHAPE.

We introduce a new key generation mechanism where users can generate a "back up key'', securely nested inside the secret key of a signature scheme. Our main motivation is that in case of leakage of the secret key, established techniques based on zero-knowledge proofs of knowledge are void since the key becomes public. On the other hand, the "back up key'', which is secret, can be used to generate a "proof of ownership'', i.e., only the real owner of this secret key can generate such a proof. To the best of our knowledge, this extra level of security is novel, and could have already been used in practice, if available, in digital wallets for cryptocurrencies that suffered massive leakage of account private keys. In this work, we formalize the notion of "Proof of Ownership'' and "Fallback'' as new properties. Then, we introduce our construction, which is compatible with major designs for wallets based on ECDSA, and adds a W-OTS(+) signing key as a "back up key''. Thus offering a quantum secure fallback. This design allows the hiding of any quantum secure signature key pair, and is not exclusive to W-OTS(+). Finally, we briefly discuss the construction of multiple generations of proofs of ownership.

Consider a scenario where Alice stores some secret data $s$ on $n$ servers using a $t$-out-of-$n$ secret sharing scheme. Trudy (the collector) is interested in the secret data of Alice and is willing to pay for it. Trudy publishes an advertisement on the internet which describes an elaborate cryptographic scheme to collect the shares from the $n$ servers. Each server who decides to submit its share is paid a hefty monetary reward and is guaranteed ``immunity" from being caught or prosecuted in a court for violating its service agreement with Alice. Bob is one of the servers and sees this advertisement. On examining the collection scheme closely, Bob concludes that there is no way for Alice to prove anything in a court that he submitted his share. Indeed, if Bob is rational, he might use the cryptographic scheme in the advertisement and submit his share since there are no penalties and no fear of being caught and prosecuted. Can we design a secret sharing scheme which Alice can use to avoid such a scenario? We introduce a new primitive called as Traceable Secret Sharing to tackle this problem. In particular, a traceable secret sharing scheme guarantees that a cheating server always runs the risk of getting traced and prosecuted by providing a valid evidence (which can be examined in a court of law) implicating its dishonest behavior. We explore various definitional aspects and show how they are highly non-trivial to construct (even ignoring efficiency aspects). We then give an efficient construction of traceable secret sharing assuming the existence of a secure two-party computation protocol. We also show an application of this primitive in constructing traceable protocols for multi-server delegation of computation.

Many new ciphers target a concise algebraic description for efficient evaluation in a proof system or a multi-party computation. This new target for optimization introduces algebraic vulnerabilities, particularly involving Gröbner basis analysis. Unfortunately, the literature on Gröbner bases tends to be either purely mathematical, or focused on small fields. In this paper, we survey the most important algorithms and present them in an intuitive way. The discussion of their complexities enables researchers to assess the security of concrete arithmetization-oriented ciphers. Aside from streamlining the security analysis, this paper helps newcomers enter the field.

While privacy preserving distributed payment schemes manage to drastically improve user privacy, they come at the cost of generating new regulatory concerns: in a private ledger the transactions cannot be subject to any level of auditing, and thus are not compatible with tracing illegal behaviors. In this work we present MiniLedger, a distributed payment system which not only guarantees the privacy of transactions, but also offers built-in functionalities for various types of audits by any external authority. MiniLedger is the first private and auditable payment system with storage costs independent of the number of transactions. To achieve such a storage improvement, we introduce pruning functionalities for the transaction history while maintaining integrity and auditing. We provide formal security definitions and a number of extensions for various auditing levels. Our evaluation results show that MiniLedger is practical in terms of storage requiring as low as 70KB per participant for 128 bits of security, and depending on the implementation choices, can prune 1 million transactions in less than a second.

Efficient implementation of Boolean masking in terms of low latency has evolved into a hot topic due to the necessity of embedding a physically secure and at-the-same-time fast implementation of cryptographic primitives in e.g., the memory encryption of pervasive devices. Instead of fully minimizing the circuit's area and randomness requirements at the cost of latency, the focus has changed into finding optimal tradeoffs between the circuit area and the execution time. The main latency bottleneck in hardware masking lies in the need for registers to stop the propagation of glitches and maintain non-completeness. Usually, an exponentially growing number of shares (hence an extremely large circuit), as well as a high demand for fresh randomness, are the result of avoiding registers in a securely masked hardware implementation of a block cipher. In this paper, we present several first-order secure and low-latency implementations of PRINCE. In particular, we show how to realize the masked variant of round-based PRINCE with only a single register stage per cipher round. We compare the resulting architectures, based on the popular TI and GLM masking scheme based on the area, latency, and randomness requirements and point out that both designs are suited for specific use cases.

This paper revisits Key-Policy Attribute-Based Encryption (KP-ABE), allowing dele- gation of keys, traceability of compromised keys, and key anonymity, as additional properties. Whereas delegation of rights has been addressed in the seminal paper by Goyal et al. in 2006, introducing KP-ABE, this feature has almost been neglected in all subsequent works in favor of better security levels. However, in multi-device scenarios, this is quite important to allow users to independently authorize their own devices, and thus to delegate their initial rights with possibly more restrictions to their everyday-use devices. But then, one may also require tracing capabilities in case of corrupted devices and anonymity for the users and their devices. To this aim, we define a new variant of KP-ABE including delegation, with switchable attributes, in both the ciphertexts and the keys, and new indistinguishability properties. We then provide a concrete and efficient instantiation with adaptive security under the sole SXDH assumption in the standard model. We eventually explain how this new primitive can address all our initial goals.

The one more-discrete logarithm assumption (OMDL) underlies the security analysis of identification protocols, blind signature and multi-signature schemes, such as blind Schnorr signatures and the recent MuSig2 multi-signatures. As these schemes produce standard Schnorr signatures, they are compatible with existing systems, e.g. in the context of blockchains. OMDL is moreover assumed for many results on the impossibility of certain security reductions. Despite its wide use, surprisingly, OMDL is lacking any rigorous analysis; there is not even a proof that it holds in the generic group model (GGM). (We show that a claimed proof is flawed.) In this work we give a formal proof of OMDL in the GGM. We also prove a related assumption, the one-more computational Diffie-Hellman assumption, in the GGM. Our proofs deviate from prior proofs in the GGM and replace the use of the Schwartz-Zippel Lemma by a new argument.

Ternary LWE, i.e., LWE with coefficients of the secret and the error vectors taken from $\{-1, 0, 1\}$, is a popular choice among NTRU-type cryptosystems and some signatures schemes like BLISS and GLP. In this work we consider quantum combinatorial attacks on ternary LWE. Our algorithms are based on the quantum walk framework of Magniez-Nayak-Roland-Santha. At the heart of our algorithms is a combinatorial tool called the representation technique that appears in algorithms for the subset sum problem. This technique can also be applied to ternary LWE resulting in faster attacks. The focus of this work is quantum speed-ups for such representation-based attacks on LWE. When expressed in terms of the search space $\mathcal{S}$ for LWE keys, the asymptotic complexity of the representation attack drops from $\mathcal{S}^{0.24}$ (classical) down to $\mathcal{S}^{0.19}$ (quantum). This translates into noticeable attack's speed-ups for concrete NTRU instantiations like NTRU-HRSS and NTRU Prime. Our algorithms do not undermine current security claims for NTRU or other ternary LWE based schemes, yet they can lay ground for improvements of the combinatorial subroutines inside hybrid attacks on LWE.

We build the first construction of a partially oblivious pseudorandom function (POPRF) that does not rely on bilinear pairings. Our construction can be viewed as combining elements of the 2HashDH OPRF of Jarecki, Kiayias, and Krawczyk with the Dodis-Yampolskiy PRF. We analyze our POPRF’s security in the random oracle model via reduction to a new one-more gap strong Diffie-Hellman inversion assumption. The most significant technical challenge is establishing confidence in the new assumption, which requires new proof techniques that enable us to show that its hardness is implied by the $q$-DL assumption in the algebraic group model. Our new construction is as fast as the current, standards-track OPRF 2HashDH protocol, yet provides a new degree of flexibility useful in a variety of applications. We show how POPRFs can be used to prevent token hoarding attacks against Privacy Pass, reduce key management complexity in the OPAQUE password authenticated key exchange protocol, and ensure stronger security for password breach alerting services.

We construct the first authenticated key exchange protocols that achieve tight security in the standard model. Previous works either relied on techniques that seem to inherently require a random oracle, or achieved only “Multi-Bit-Guess” security, which is not known to compose tightly, for instance, to build a secure channel. Our constructions are generic, based on digital signatures and key encapsulation mechanisms (KEMs). The main technical challenges we resolve is to determine suitable KEM security notions which on the one hand are strong enough to yield tight security, but at the same time weak enough to be efficiently instantiable in the standard model, based on standard techniques such as universal hash proof systems. Digital signature schemes with tight multi-user security in presence of adaptive corruptions are a central building block, which is used in all known constructions of tightly-secure AKE with full forward security. We identify a subtle gap in the security proof of the only previously known efficient standard model scheme by Bader et al. (TCC 2015). We develop a new variant, which yields the currently most efficient signature scheme that achieves this strong security notion without random oracles and based on standard hardness assumptions.

In this work we resolve the open problem raised by Prabhakaran and Rosulek at CRYPTO 2007, and present the first anonymous, rerandomizable, Replayable-CCA (RCCA) secure public-key encryption scheme. This solution opens the door to numerous privacy-oriented applications with a highly desired RCCA security level. At the core of our construction is a non-trivial extension of smooth projective hash functions (Cramer and Shoup, EUROCRYPT 2002), and a modular generic framework developed for constructing rerandomizable RCCA-secure encryption schemes with receiver-anonymity. The framework gives an enhanced abstraction of the original Prabhakaran and Rosulek's scheme (which was the first construction of rerandomizable RCCA-secure encryption in the standard model), where the most crucial enhancement is the first realization of the desirable property of receiver-anonymity, essential to privacy settings. It also serves as a conceptually more intuitive and generic understanding of RCCA security, which leads, for example, to new implementations of the notion. Finally, note that (since CCA security is not applicable to the privacy applications motivating our work) the concrete results and the conceptual advancement presented here, seem to substantially expand the power and relevance of the notion of rerandomizable RCCA-secure encryption.

With the development of side-channel attacks, a necessity arises to invent authenticated key exchange protocols in a leakage-resilient manner. Constructing authenticated key exchange protocols using existing cryptographic schemes is an effective method, as such construction can be instantiated with any appropriate scheme in a way that the formal security argument remains valid. In parallel, constructing authenticated key exchange protocols that are proven to be secure in the standard model is more preferred as they rely on real-world assumptions. In this paper, we present a Diffie-Hellman-style construction of a leakage-resilient authenticated key exchange protocol, that can be instantiated with any CCLA2-secure public-key encryption scheme and a function from the pseudo-random function family. Our protocol is proven to be secure in the standard model assuming the hardness of the decisional Diffie-Hellman problem. Furthermore, it is resilient to continuous partial leakage of long-term secret keys, that happens even after the session key is established, while satisfying the security features defined by the eCK security model.

We introduce a novel method for reducing an arbitrary $\delta$-noisy leakage function to a collection of $\epsilon$-random probing leakages. These reductions combined with linear algebra tools are utilized to study the security of linear Boolean masked circuits in a practical and concrete setting. The secret recovery probability (SRP) that measures an adversary's ability to obtain secrets of a masked circuit is used to quantify the security. Leakage data and the parity-check relations imposed by the algorithm's structure are employed to estimate the SRP Both the reduction method and the SRP metric were used in the previous works. Here, as our main contribution, the SRP evaluation task is decomposed from the given $\mathbb{F}_q$ field to $q-1$ different binary systems indexed with $i$. Where for the $i$th system, the equivalent $\delta_i$-noisy leakage is reduced optimally to a $\epsilon_i$-random probing leakage with $\epsilon_i=2\delta_i$. Each binary system is targeting a particular bit-composition of the secret. The $q-1$ derived $\delta_i\leq \delta$ values are shown to be a good measure for the informativeness of the given $\delta$-noisy leakage function. Our works here can be considered as an extension of the work of TCC 2016. There, only $ \delta$-noisy leakage from the shares of a secret was considered. Here, we also incorporate the leakages that are introduced by the computations over the shares.

We study masked implementation's security when an adversary randomly probes each of its internal variables, intending to recover non-trivial knowledge about its secrets. We introduce a novel metric called Secret Recovery Probability (SRP) for assessing the informativeness of the probing leakages about the masked secrets. To evaluate SRP, our starting point is to describe the relations of the intermediate variables with a parity equation system where the target secret is an unknown of this system ...

This paper describes the first practical single-trace side-channel power analysis of SIKE. While SIKE is a post-quantum key exchange, the scheme still relies on a secret elliptic curve scalar multiplication which involves a loop of a double-and-add procedure, of which each iteration depends on a single bit of the private key. The attack therefore exploits the nature of elliptic curve point addition formulas which require the same function to be executed multiple times. We show how a single trace of a loop iteration can be segmented into several power traces on which 32-bit words can be hypothesised based on the value of a single private key bit. This segmentation enables a classical correlation power analysis in an extend-and-prune approach. Further error-correction techniques based on depth-search are suggested. The attack is explicitly geared towards and experimentally verified on an STM32F3 featuring a Cortex-M4 microcontroller which runs the SIKEp434 implementation adapted to 32-bit ARM that is part of the official implementations of SIKE. We obtained a resounding 100% success rate recovering the full private key in each experiment. We argue that our attack defeats many countermeasures which were suggested in a previous power analysis of SIKE, and finally show that the well-known countermeasure of projective coordinate randomisation stops the attack with a negligible overhead.

Secure computation enables two or more parties to jointly evaluate a function without revealing to each other their private input. G-module is an abelian group M, where the group G acts compatibly with the abelian group structure on M. In this work, we present several secure computation protocols for G-module operations in the online/offline mode. We then show how to instantiate those protocols to implement many widely used secure computation primitives in privacy-preserving machine learning and data mining, such as oblivious cyclic shift, one-round shared OT, oblivious permutation, oblivious shuffle, secure comparison, oblivious selection, DReLU, and ReLU, etc. All the proposed protocols are constant-round, and they are 2X - 10X more efficient than the-state-of-the-art constant-round protocols in terms of communication complexity.

When generating quartets for the rectangle attacks on ciphers with linear key-schedule, we find the right quartets which may suggest key candidates have to satisfy some nonlinear relations. However, some quartets generated always violate these relations, so that they will never suggest any key candidates. Inspired by previous rectangle frameworks, we find that guessing certain key cells before generating quartets may reduce the number of invalid quartets. However, guessing a lot of key cells at once may lose the benefit from the early abort technique, which may lead to a higher overall complexity. To get better tradeoff, we build a new rectangle framework on ciphers with linear key-schedule with the purpose of reducing overall complexity or attacking more rounds. In the tradeoff model, there are many parameters affecting the overall complexity, especially for the choices of the number and positions of key guessing cells before generating quartets. To identify optimal parameters, we build a uniform automatic tool on SKINNY as an example, which includes the optimal rectangle distinguishers for key-recovery phase, the number and positions of guessing key cells before generating quartets, the size of key counters to build that affecting the exhaustive search step, etc. Based on the automatic tool, we identify a 32-round key-recovery attack on SKINNY-128-384 in the related-key setting, which extends the best previous attack by 2 rounds. For other versions with n-2n or n-3n, we also achieve one more round than before. In addition, using the previous rectangle distinguishers, we achieve better attacks on round-reduced ForkSkinny, Deoxys-BC-384 and GIFT-64. At last, we discuss the conversion of our rectangle framework from related-key setting into single-key setting and give new single-key rectangle attack on 10-round Serpent.

Payment channel networks (PCNs) mitigate the scalability issues of current decentralized cryptocurrencies. They allow for arbitrarily many payments between users connected through a path of intermediate payment channels, while requiring interacting with the blockchain only to open and close the channels. Unfortunately, PCNs are (i) tailored to payments, excluding more complex smart contract functionalities, such as the oracle-enabling Discreet Log Contracts and (ii) their need for active participation from intermediaries may make payments unreliable, slower, expensive, and privacy-invasive. Virtual channels are among the most promising techniques to mitigate these issues, allowing two endpoints of a path to create a direct channel over the intermediaries without any interaction with the blockchain. After such a virtual channel is constructed, (i) the endpoints can use this direct channel for applications other than payments and (ii) the intermediaries are no longer involved in updates. In this work, we first introduce the Domino attack, a new DoS/griefing style attack that leverages virtual channels to destruct the PCN itself and is inherent to the design adopted by the existing Bitcoin-compatible virtual channels. We then demonstrate its severity by a quantitative analysis on a snapshot of the Lightning Network (LN), the most widely deployed PCN at present. We finally discuss other serious drawbacks of existing virtual channel designs, such as the support for only a single intermediary, a latency and blockchain overhead linear in the path length, or a non-constant storage overhead per user. We then present Donner, the first virtual channel construction that overcomes the shortcomings above, by relying on a novel design paradigm. We formally define and prove security and privacy properties in the Universal Composability framework. Our evaluation shows that Donner is efficient, reduces the on-chain number of transactions for disputes from linear in the path length to a single one, which is the key to prevent Domino attacks, and reduces the storage overhead from logarithmic in the path length to constant. Donner is Bitcoin-compatible and can be easily integrated in the LN.

Post-quantum cryptography (PQC) is nowadays a very active research field [1]. We follow a non-standard way to achieve it, taking any common protocol and replacing arithmetic with GF(2^8) field operations, a procedure defined as R-Propping [2-7]. The resulting protocol security relies on the intractability of a generalized discrete log problem, combined with the power sets of algebraic ring extension tensors and resilience to quantum and algebraic attacks. Oblivious Transfer (OT) is a keystone for Secure Multiparty Computing (SMPC) [8], one of the most pursued cryptographic areas. It is a critical issue to develop a fast OT solution because of its intensive use in many protocols. Here, we adopt the simple OT protocol developed by Chou and Orlandi [9] as the base model to be propped. Our solution is fully scalable to achieve quantum and classical security levels as needed. We present a step-by-step numerical example of the proposed protocol.

We introduce the problem of private signaling. In this problem, a sender posts a message to a certain location of a public bulletin board, and then computes a signal that allows only the intended recipient (and no one else) to learn that it is the recipient of the posted message. Besides privacy, this problem has the following crucial efficiency requirements. First, the sender and recipient do not participate in any out-of-band communication, and second, the overhead of the recipient should be asymptotically better than scanning the entire board. Existing techniques, such as the server-aided fuzzy message detection (Beck et al., CCS’21), could be employed to solve the private signaling problem. However, this solution requires that the computational effort of the recipient grows with the amount of privacy desired, providing no saving over scanning the entire board if the maximum privacy is required. In this work, we present a server-aided solution to the private signaling problem that guar- antees full privacy for all recipients, while requiring only constant amount of work for both the recipient and the sender. We provide the following contributions. First, we provide a formal definition of private signaling in the Universal Composability (UC) framework and show that it generalizes several real-world settings where recipient anonymity is desired. Second, we present two protocols that UC-realize our definition: one using a single server equipped with a trusted execution environment, and one based on two servers that employs garbled circuits. Third, we provide an open-source implementation of both of our protocols and evaluate their performance and show that they are practical.

We introduce a new technique for indexing joins in encrypted SQL databases called partially precomputed joins which achieves lower leakage and bandwidth than those used in prior constructions. These techniques are incorporated into state-of-the-art structured encryption schemes for SQL data, yielding a hybrid indexing scheme with both partially and fully precomputed join indexes. We then introduce the idea of leakage-aware query planning by giving a heuristic that helps the client decide, at query time, which index to use so as to minimize leakage and stay below a given bandwidth budget. We conclude by simulating our constructions on real datasets, showing that our heuristic is accurate and that partially-precomputed joins perform well in practice.

In an election where each voter may express $P$ preferences among $M$ possible choices, the Amun protocol allows to secure vote casting against over-the-shoulder adversaries, retaining privacy, fairness, end-to-end verifiability, and correctness. Before the election, each voter receives a ballot containing valid and decoy tokens: only valid tokens contribute in the final tally, but they remain indistinguishable from the decoys. Since the voter is the only one who knows which tokens are valid (without being able to prove it to a coercer), over-the-shoulder attacks are thwarted. We prove the security of the construction under the standard Decisional Diffie Hellman assumption in the random oracle model.

The threat of quantum computers has sparked the development of a new kind of cryptography to resist their attacks. Isogenies between elliptic curves are one of the tools used for such cryptosystems. They are championed by SIKE (Supersingular isogeny key encapsulation), an "alternate candidate" of the third round of the NIST Post-Quantum Cryptography Standardization Process. While all candidates are believed to be mathematically secure, their implementations may be vulnerable to hardware attacks. In this work we investigate for the first time whether Ti's 2017 theoretical fault injection attack is exploitable in practice. We also examine suitable countermeasures. We manage to recover the secret thanks to electromagnetic fault injection on an ARM Cortex A53 using a correct and an altered public key generation. Moreover we propose a suitable countermeasure to detect faults that has a low overhead as it takes advantage of a redundancy already present in SIKE implementations.

This paper presents a side-channel analysis (SCA) on key encapsulation mechanism (KEM) based on the Fujisaki–Okamoto (FO) transformation and its variants. The FO transformation has been widely used in actively securing KEMs from passively secure public key encryption (PKE), as it is employed in most of NIST post-quantum cryptography (PQC) candidates for KEM. The proposed attack exploits side-channel leakage during execution of a psuedorandom function (PRF) in the re-encryption of KEM decapsulation as a plaintext-checking oracle that tells whether the PKE decryption result is equivalent to the reference plaintext. The generality and practicality of the plaintext-checking oracle allows the proposed attack to attain a full-key recovery of various KEMs when an active attack on the underlying PKE is known. This paper demonstrates that the proposed attack can be applied to most NIST PQC third-round KEM candidates, namely, Kyber, Saber, FrodoKEM, NTRU, NTRU Prime, HQC, BIKE, and SIKE (for BIKE, the proposed attack achieves a partial key recovery). The applicability to Classic McEliece is unclear because there is no known active attack on this cryptosystem. This paper also presents a side-channel distinguisher design based on deep learning (DL) for mounting the proposed attack on practical implementation without the use of a profiling device. The feasibility of the proposed attack is demonstrated through experimental attacks on various PRF implementations (a SHAKE software, an AES software, an AES hardware, a bit-sliced masked AES software, and a masked AES hardware based on threshold implementation). The success of the proposed attack against all of these implementations, which include masked hardware based on threshold implementation, confirms its practicality.

The classic work of Gorbunov, Vaikuntanathan and Wee (CRYPTO 2012) and follow-ups provided constructions of bounded collusion Functional Encryption (FE) for circuits from mild assumptions. In this work, we improve the state of affairs for bounded collusion FE in several ways: 1. $New$ $Security$ $Notion$. We introduce the notion of $dynamic$ bounded collusion FE, where the declaration of collusion bound is delayed to the time of encryption. This enables the encryptor to dynamically choose the collusion bound for different ciphertexts depending on their individual level of sensitivity. Hence, the ciphertext size grows linearly with its own collusion bound and the public key size is independent of collusion bound. In contrast, all prior constructions have public key and ciphertext size that grow at least linearly with a fixed bound $Q$. 2. $CPFE$ $for$ $circuits$ $with$ $Dynamic$ $Bounded$ $Collusion$. We provide the first CPFE schemes for circuits enjoying dynamic bounded collusion security. By assuming identity based encryption (IBE), we construct CPFE for circuits of $unbounded$ size satisfying $non-adaptive$ simulation based security. By strengthening the underlying assumption to IBE with receiver selective opening security, we obtain CPFE for circuits of $bounded$ size, output length and depth enjoying $adaptive$ simulation based security. Moreover, we show that IBE is a necessary assumption for these primitives. Moreover, by relying on the Learning With Errors (LWE) assumption, we obtain the first $succinct$ CPFE for circuits, i.e. supporting circuits with unbounded size, but fixed output length and depth. This scheme achieves $adaptive$ simulation based security. 3. $KPFE$ $for$ $circuits$ $with$ $dynamic$ $bounded$ $collusion$. We provide the first KPFE for circuits of unbounded size, but bounded depth and output length satisfying dynamic bounded collusion security. Our construction relies on LWE and achieves $adaptive$ simulation based security. This improves the security of succinct KPFE by Goldwasser et al. [GKPVZ13b]. 4. $KP$ $and$ $CP$ $FE$ $for$ $TM/NL$ $with$ $dynamic$ $bounded$ $collusion$. We provide the first KPFE and CPFE constructions of bounded collusion functional encryption for Turing machines in the public key setting from LWE. Our constructions achieve non-adaptive simulation based security. Both the input and the machine in our construction can be of $unbounded$ polynomial length but the ciphertext size grows with the upper bound on the running time of the Turing machine on the given input. Given RAM access to the ciphertext, the scheme enjoys input specific decryption time. We provide a variant of the above scheme that satisfies $adaptive$ security, but at the cost of supporting a smaller class of computation, namely Nondeterministic Logarithmic-space (NL). Since NL contains Nondeterministic Finite Automata (NFA), this result subsumes $all$ prior work of bounded collusion FE for uniform models from standard assumptions [AMY19,AS17].

Functional Encryption is a powerful notion of encryption in which each decryption key is associated with a function $f$ such that decryption recovers the function evaluation $f(m)$. Informally, security states that a user with access to function keys $\mathsf{sk}_{f_1}, \mathsf{sk}_{f_2}, \ldots$ (and so on) can only learn $f_1(m), f_2(m), \ldots$ (and so on) but nothing more about the message. The system is said to be $q$-bounded collusion resistant if the security holds as long as an adversary gets access to at most $q = q(\lambda)$ function keys. A major drawback of such "statically" bounded collusion systems is that the collusion bound $q$ must be declared at setup time and is fixed for the entire lifetime of the system. We initiate the study of "dynamically" bounded collusion resistant functional encryption systems which provide more flexibility in terms of selecting the collusion bound, while reaping the benefits of statically bounded collusion FE systems (such as quantum resistance, simulation security, and general assumptions). Briefly, the virtues of a dynamically bounded scheme can be summarized as: (i) [Fine-grained individualized selection.] It lets each encryptor select the collusion bound by weighing the trade-off between performance overhead and the amount of collusion resilience. (ii) [Evolving encryption strategies.] Since the system is no longer tied to a single collusion bound, thus it allows to dynamically adjust the desired collusion resilience based on any number of evolving factors such as the age of the system, or a number of active users, etc. (iii) [Ease and simplicity of updatability.] None of the system parameters have to be updated when adjusting the collusion bound. That is, the same key $\mathsf{sk}_f$ can be used to decrypt ciphertexts for collusion bound $q = 2$ as well as $q = 2^\lambda$. We construct such a dynamically bounded functional encryption scheme for the class of all polynomial-size circuits under the general assumption of Identity-Based Encryption.

This is team SmartPools’ submission for the first Ergo Hackathon. It suggests that Ergo lacks the decentralization, and focus on regular people that it was designed for, and presents a potential solution for these problems in laying the framework for crowdfunded smart contract pools compatible with non-outsourceabilty. It should allow for pool formation with a greater level of decentralization than previously possible by including metrics for diminishing returns on over-contributing hash power to pools with data gathered from Ergo Oracles. This work is informal and preliminary. Further research is required to formalize this work and attempt to provide functional proof for its arguments; readers are highly encouraged to read the included references, and their references, for greater clarity.

Digital signature schemes form the basis of trust in Internet communication. Shor (FOCS 1994) proposed quantum algorithms that can be used by a quantum computer to break the security of today’s widely used digital signature schemes, and this has fuelled intensive research on the design and implementation of post-quantum digital signatures. Hash-based digital signatures base their security on one-way functions that in practice are instantiated by hash functions. Hash-based signatures are widely studied and are part of NIST's post-quantum standardization effort. In this paper we present a multi-target attack that we call Intermediate Secret-Guessing attack on two hash-based signatures: XMSS^MT (Draft SP 800-208 that was considered by NIST for standardization), and K2SN-MSS (AsiaCCS 2019). The attack allows an adversary to forge a signature on an arbitrary message. We describe the intuition behind the attack and give details of its application on the attacked schemes together with corresponding theoretical analysis. The attack implies that the effective security levels of XMSS (a special case of XMSS^MT), XMSS^MT, and K2SN-MSS are 10, 39 and 12 bits lower than their designed security levels given access to $2^{20}$, $2^{60}$, and $2^{20}$ signatures, respectively. We implement the attack for each scheme, and give our results for reduced security parameters that validate our theoretical analysis. We also show that the attack can be avoided by modifying the application of a pseudorandom function for key generation. Our work shows the subtleties of replacing randomness with pseudo-randomness in the key generation of hash-based signatures, and the need for careful analysis of such designs.

Bounded IND-CCA security (IND-qCCA) is a notion similar to the traditional IND-CCA security, except the adversary is restricted to a constant number q of decryption/decapsulation queries. We show in this work that IND-qCCA is easily obtained from any passively secure PKE in the (Q)ROM. That is, simply adding a confirmation hash or computing the key as the hash of the plaintext and ciphertext holds an IND-qCCA KEM. In particular, there is no need for derandomization or re-encryption as in the Fujisaki-Okamoto (FO) transform. This makes the decapsulation process of such IND-qCCA KEM much more efficient than its FO-derived counterpart. In addition, IND-qCCA KEMs could be used in the recently proposed KEMTLS protocol [ACM CCS 2020] that requires IND-1CCA ephemeral key-exchange mechanisms or in TLS 1.3. Then, using similar proof techniques, we show that CPA-secure KEMs are sufficient for the TLS 1.3 handshake to be secure, solving an open problem in the ROM. In turn, this implies that the PRF-ODH assumption used to prove the security of TLS 1.3 is not necessary and can be replaced by the CDH assumption in the ROM. We also highlight and briefly discuss several use cases of IND-1CCA KEMs in protocols and ratcheting primitives.

Starting with the work of Rivest et al. in 1996, timed assumptions have found many applications in cryptography, building e.g. the foundation of the blockchain technology. They also have been used in the context of classical MPC, e.g. to enable fairness. We follow this line of research to obtain composable generic MPC in the plain model. This approach comes with a major advantage regarding environmental friendliness, a property coined by Canetti et al. (FOCS 2013). Informally, this means that our constructions do not “hurt” game-based security properties of protocols that hold against polynomial-time adversaries when executed alone. As an additional property, they can be plugged into any UC-secure protocol without loss of security. Towards proving the security of our constructions, we introduce a variant of the UC security notion that captures timed cryptographic assumptions. Combining standard timed commitments and standard polynomial-time hardness assumptions, we construct a composable commitment scheme in the plain model. As this construction is constant-round and black-box, we obtain the first fully environmentally friendly composable constant-round black-box generic MPC protocol in the plain model from standard (timed) assumptions.

Modern cryptography fundamentally relies on the assumption that the adversary trying to break the scheme is computationally bounded. This assumption lets us construct cryptographic protocols and primitives that are known to be impossible otherwise. In this work we explore the effect of bounding the adversary's power in other information theoretic proof-systems and show how to use this assumption to bypass impossibility results. We first consider the question of constructing succinct PCPs. These are PCPs whose length is polynomial only in the length of the original NP witness (in contrast to standard PCPs whose length is proportional to the non-deterministic verification time). Unfortunately, succinct PCPs are known to be impossible to construct under standard complexity assumptions. Assuming the sub-exponential hardness of the learning with errors (LWE) problem, we construct succinct probabilistically checkable arguments or PCAs (Zimand 2001, Kalai and Raz 2009), which are PCPs in which soundness is guaranteed against efficiently generated false proofs. Our PCA construction is for every NP relation that can be verified by a small-depth circuit (e.g., SAT, clique, TSP, etc.) and in contrast to prior work is publicly verifiable and has constant query complexity. Curiously, we also show, as a proof-of-concept, that such publicly-verifiable PCAs can be used to derive hardness of approximation results. Second, we consider the notion of Instance Compression (Harnik and Naor, 2006). An instance compression scheme lets one compress, for example, a CNF formula $\varphi$ on $m$ variables and $n \gg m$ clauses to a new formula $\varphi'$ with only $poly(m)$ clauses, so that $\varphi$ is satisfiable if and only if $\varphi'$ is satisfiable. Instance compression has been shown to be closely related to succinct PCPs and is similarly highly unlikely to exist. We introduce a computational analog of instance compression in which we require that if $\varphi$ is unsatisfiable then $\varphi'$ is effectively unsatisfiable, in the sense that it is computationally infeasible to find a satisfying assignment for $\varphi'$ (although such an assignment may exist). Assuming the same sub-exponential LWE assumption, we construct such computational instance compression schemes for every bounded-depth NP relation. As an application, this lets one compress $k$ formulas $\phi_1,\dots,\phi_k$ into a single short formula $\phi$ that is effectively satisfiable if and only if at least one of the original formulas was satisfiable.

We examine Multi-Party Computation protocols in the active-security-with-abort setting for $Q_2$ access structures over small and large finite fields $F_p$ and over rings $Z_{p^k}$. We give general protocols which work for any $Q_2$ access structure which is realised by a multiplicative Extended Span Program. We generalize a number of techniques and protocols from various papers and compare the different methodologies. In particular we examine the expected communication cost per multiplication gate when the protocols are instantiated with different access structures.

We investigate __all__ NIST PQC Round 3 KEM candidates from the viewpoint of fault-injection attacks: Classic McEliece, Kyber, NTRU, Saber, BIKE, FrodoKEM, HQC, NTRU Prime, and SIKE. All KEM schemes use variants of the Fujisaki-Okamoto transformation, so the equality test with re-encryption in decapsulation is critical. We survey effective key-recovery attacks when we can skip the equality test. We found the existing key-recovery attacks against Kyber, NTRU, Saber, FrodoKEM, HQC, one of two KEM schemes in NTRU Prime, and SIKE. We propose a new key-recovery attack against the other KEM scheme in NTRU Prime. We also report an attack against BIKE that leads to leakage of information of secret keys. The open-source pqm4 library contains all KEM schemes except Classic McEliece and HQC. We show that giving a single instruction-skipping fault in the decapsulation processes leads to skipping the equality test __virtually__ for Kyber, NTRU, Saber, BIKE, and SIKE. We also report the experimental attacks against them. We also report the implementation of NTRU Prime allows chosen-ciphertext attacks freely and the timing side-channel of FrodoKEM reported in Guo, Johansson, and Nilsson (CRYPTO 2020) remains, while there are no such bugs in their NIST PQC Round 3 submissions.

From June 2019 to March 2020, IETF conducted a selection process to choose password authenticated key exchange (PAKE) protocols for standardization. Similar standardization efforts were conducted before by IEEE (P1362.2) and ISO/IEC (11770-4). An important hallmark for this IETF selection process is its openness: anyone can nominate any candidate; all reviews are public; all email discussions on the IETF mailing lists are archived and publicly readable. However, despite the openness, it is unclear whether this IETF selection process has presented a successful model. Several important questions that were raised during the selection process had remained unaddressed even after the two winners (CPace and OPAQUE) were announced. We reflect on the IETF PAKE selection process as a case study, and summarize lessons in a set of principles with the hope to improve security standardization in the future.

Well-known authentication mechanisms such as Public-key Infrastructure (PKI) and Identity-based Public-key Certificates (ID-PKC) are not suitable to integrate with the peer-to-peer (P2P) network environment. The reason is the difficulty in maintaining a centralized authority to manage the certificates. The authentication becomes even harder in an anonymous environment. We present three authentication protocols such that the users can authenticate themselves in an anonymous P2P network, without revealing their identities. Firstly, we propose a way to use existing ring signature schemes to obtain anonymous authentication. Secondly, we propose an anonymous authentication scheme utilizing secret sharing schemes. Finally, we propose a zero-knowledge-based anonymous authentication protocol. We provide security justifications of the three protocols in terms of anonymity, completeness, soundness, resilience to impersonation attacks, and resilience to replay attacks.

One of the finalists in the NIST post-quantum cryptography competition is the Classic McEliece cryptosystem. Unfortunately, its public key size represents a practical limitation. One option to address this problem is to use different families of error-correcting codes. Most of such attempts failed as those cryptosystems were proved not secure. In this paper, we propose a McEliece type cryptosystem using high minimum distance self-dual codes and punctured codes derived from them. To the best of our knowledge, such codes have not been implemented in a code-based cryptosystem until now. For the 80-bit security case, we construct an optimal self-dual code of length 1\,064, which, as far as we are aware, was not presented before. Compared to the original McEliece cryptosystem, this allows us to reduce the key size by about 38.5\%.

General-purpose zero-knowledge proofs for all \textsf{NP} languages greatly simplify secure protocol design. However, they inherently require the code of the underlying relation. If the relation contains black-box calls to a cryptographic function, the code of that function must be known to use the ZK proof, even if both the relation and the proof require only black-box access to the function. Rosulek (Crypto'12) shows that non-trivial proofs for even simple statements, such as membership in the range of a one-way function, require non-black-box access. We propose an alternative approach to bypass Rosulek's impossibility result. Instead of asking for a ZK proof directly for the given one-way function $f$, we seek to construct a \textit{new} one-way function $F$ given only black-box access to $f$, \textit{and} an associated ZK protocol for proving non-trivial statements, such as range membership, over its output. We say that $F$, along with its proof system, is a \textit{proof-based} one-way function. We similarly define proof-based versions of other primitives, specifically pseudo-random generators and collision-resistant hash functions. We show how to construct proof-based versions of each of the primitives mentioned above from their ordinary counterparts under mild but necessary restrictions over the input. More specifically, - We first show that if the prover entirely chooses the input, then proof-based pseudo-random generators cannot be constructed from ordinary ones in a black-box manner, thus establishing that some restrictions over the input are necessary. - We next present black-box constructions handling inputs of the form $(x,r)$ where $r$ is chosen uniformly by the verifier. This is similar to the restrictions in the widely used Goldreich-Levin theorem. The associated ZK proofs support range membership over the output as well as arbitrary predicates over prefixes of the input. Our results open up the possibility that general-purpose ZK proofs for relations that require black-box access to the primitives above may be possible in the future without violating their black-box nature by instantiating them using proof-based primitives instead of ordinary ones.

Secure Multiparty Computation (MPC) is an invaluable tool for training machine learning models when the training data cannot be directly accessed by the model trainer. Unfortunately, complex algorithms, such as deep learning models, have their computational complexities increased by orders of magnitude when performed using MPC protocols. In this contribution, we study how to efficiently train an important class of machine learning problems by using MPC where features are known by one of the computing parties and only the labels are private. We propose new protocols combining differential privacy (DP) and MPC in order to privately and efficiently train a deep learning model in such scenario. More specifically, we release differentially private information during the MPC computation to dramatically reduce the training time. All released information does not compromise the privacy of the labels at the individual level. Our protocols can have running times that are orders of magnitude better than a straightforward use of MPC at a moderate cost in model accuracy.

The best known $n$ party unconditional multiparty computation protocols with an optimal corruption threshold communicates $O(n)$ field elements per gate. This has been the case even in the semi-honest setting despite over a decade of research on communication complexity in this setting. Going to the slightly sub-optimal corruption setting, the work of Damgard, Ishai, and Kroigaard (EUROCRYPT 2010) provided the first protocol for a single circuit achieving communication complexity of $O(\log|C|)$ elements per gate. While a number of works have improved upon this result, obtaining a protocol with $O(1)$ field elements per gate has been an open problem. In this work, we construct the first unconditional multi-party computation protocol evaluating a single arithmetic circuit with amortized communication complexity of $O(1)$ elements per gate.

In this work, we address communication, computation, and round efficiency of unconditionally secure multi-party computation for arithmetic circuits in the honest majority setting. We achieve both algorithmic and practical improvements: -- The best known result in the semi-honest setting has been due to Damgard and Nielsen (CRYPTO 2007). Over the last decade, their construction has played an important role in the progress of efficient secure computation. However despite a number of follow-up works, any significant improvements to the basic semi-honest protocol have been hard to come by. We show 33% improvement in communication complexity of this protocol. We show how to generalize this result to the malicious setting, leading to the best known unconditional honest majority MPC with malicious security. -- We focus on the round complexity of the Damgard and Nielsen protocol and improve it by a factor of 2. Our improvement relies on a novel observation relating to an interplay between Damgard and Nielsen multiplication and Beaver triple multiplication. An implementation of our constructions shows an execution run time improvement compared to the state of the art ranging from 30% to 50%.

Digital signatures are widely deployed to authenticate the source of incoming information, or to certify data integrity. Common signature verification procedures return a decision (accept/reject) only at the very end of the execution. If interrupted prematurely, however, the verification process cannot infer any meaningful information about the validity of the given signature. We notice that this limitation is due to the algorithm design solely, and it is not inherent to signature verification. In this work, we provide a formal framework to handle interruptions during signature verification. In addition, we propose a generic way to devise alternative verification procedures that progressively build confidence on the final decision. Our transformation builds on a simple but powerful intuition and applies to a wide range of existing schemes considered to be post-quantum secure including the NIST finalist Rainbow. While the primary motivation of progressive verification is to mitigate unexpected interruptions, we show that verifiers can leverage it in two innovative ways. First, progressive verification can be used to intentionally adjust the soundness of the verification process. Second, progressive verifications output by our transformation can be split into a computationally intensive offline set-up (run once) and an efficient online verification that is progressive.

We consider a distributed function computation problem in which parties observing noisy versions of a remote source facilitate the computation of a function of their observations at a fusion center through public communication. The distributed function computation is subject to constraints, including not only reliability and storage but also secrecy and privacy. Specifically, 1) the function computed should remain secret from an eavesdropper observing the public communication and correlated observations, measured in terms of the information leaked about the arguments of the function, to ensure secrecy regardless of the exact function used; 2) the remote source should remain private from the eavesdropper and the fusion center, measured in terms of the information leaked about the remote source itself. We derive the exact rate regions for lossless and lossy single-function computation and illustrate the lossy single-function computation rate region for an information bottleneck example, in which the optimal auxiliary random variables are characterized for binary-input symmetric-output channels. We extend the approach to lossless and lossy asynchronous multiple-function computations with joint secrecy and privacy constraints, in which case inner and outer bounds for the rate regions that differ only in the Markov chain conditions imposed are characterized.

To compensate for the poor reliability of Physical Unclonable Function (PUF) primitives, some low complexity solutions not requiring error-correcting codes (ECC) have been proposed. One simple method is to discard less reliable bits, which are indicated in the helper data stored inside the PUF. To avoid discarding bits, the Two-metric Helper Data (TMH) method, which particularly applies to oscillation-based PUFs, allows to keep all bits by using different metrics when deriving the PUF response. However, oscillation-based PUFs are sensitive to side-channel analysis (SCA) since the frequencies of the oscillations can be observed by current or electromagnetic measurements. This paper studies the security of PUFs using TMH in order to obtain both reliable and robust PUF responses. We show that PUFs using TMH are sensitive to SCA, but can be greatly improved by using temporal masking and adapted extraction metrics. In case of public helper data, an efficient protection requires the randomization of the measurement order. We study two different solutions, providing interesting insights into trade-offs between security and complexity.

Deliberately weakened ciphers are of great interest in political discussion on law enforcement, as in the constantly recurring crypto wars, and have been put in the spotlight of academics by recent progress. A paper at Eurocrypt 2021 showed a strong indication that the security of the widely-deployed stream cipher GEA-1 was deliberately and secretly weakened to 40 bits in order to fulfill European export restrictions that have been in place in the late 1990s. However, no explanation of how this could have been constructed was given. On the other hand, we have seen the MALICIOUS design framework, published at CRYPTO 2020, that allows to construct tweakable block ciphers with a backdoor, where the difficulty of recovering the backdoor relies on well-understood cryptographic assumptions. The constructed tweakable block cipher however is rather unusual and very different from, say, general-purpose ciphers like the AES. In this paper, we pick up both topics. For GEA-1 we thoroughly explain how the weakness was constructed, solving the main open question of the work mentioned above. By generalizing MALICIOUS we -- for the first time -- construct backdoored tweakable block ciphers that follow modern design principles for general-purpose block ciphers, i.e., more natural-looking deliberately weakened tweakable block ciphers.

Pilsung is an AES-based North Korean cipher, which uses key-dependent S-Boxes and permutation. The use of pseudo-random ShiftRows permutations gives rise to a potential for weak keys. In this work we show how to build distinguishers to such weak keys and how to effectively search for them. We conclude that no such class of weak keys exist.

Deep learning (DL) has revolutionized Side Channel Analysis (SCA) in recent years. One of the major advantages of DL in the context of SCA is that it can automatically handle masking and desynchronization countermeasures, even while they are applied simultaneously for a cryptographic implementation. However, the success of the attack strongly depends on the DL model used for the attack. Traditionally, Convolutional Neural Networks (CNNs) have been utilized in this regard. This work proposes to use Transformer Network (TN) for attacking implementations secured with masking and desynchronization. Our choice is motivated by the fact that TN is good at capturing the dependencies among distant points of interest in a power trace. Furthermore, we show that TN can be made shift-invariant which is an important property required to handle desynchronized traces. Experimental validation on several public datasets establishes that our proposed TN-based model, called TransNet, outperforms the present state-of-the-art on several occasions. Specifically, TransNet outperforms the other methods by a wide margin when the traces are highly desynchronized. Additionally, TransNet shows good attack performance against implementations with desynchronized traces even when it is trained on synchronized traces. The Tensorflow implementation of TransNet is available at https://github.com/suvadeep-iitb/TransNet.

Google's CECPQ1 experiment in 2016 integrated a post-quantum key-exchange algorithm, newhope1024, into TLS 1.2. The Google-Cloudflare CECPQ2 experiment in 2019 integrated a more efficient key-exchange algorithm, ntruhrss701, into TLS 1.3. This paper revisits the choices made in CECPQ2, and shows how to achieve higher performance for post-quantum key exchange in TLS 1.3 using a higher-security algorithm, sntrup761. Previous work had indicated that ntruhrss701 key generation was much faster than sntrup761 key generation, but this paper makes sntrup761 key generation much faster by generating a batch of keys at once. Batch key generation is invisible at the TLS protocol layer, but raises software-engineering questions regarding the difficulty of integrating batch key exchange into existing TLS libraries and applications. This paper shows that careful choices of software layers make it easy to integrate fast post-quantum software, including batch key exchange, into TLS with minor changes to TLS libraries and no changes to applications. As a demonstration of feasibility, this paper reports successful integration of its fast sntrup761 library, via a lightly patched OpenSSL, into an unmodified web browser and an unmodified TLS terminator. This paper also reports TLS 1.3 handshake benchmarks, achieving more TLS 1.3 handshakes per second than any software included in OpenSSL.

In many machine learning applications, training data consists of sensitive information from multiple sources. Privacy-preserving machine learning using secure computation enables multiple parties to compute on their joint data without disclosing their inputs to each other. In this work, we focus on clustering, an unsupervised machine learning technique that partitions data into groups. Previous works on privacy-preserving clustering often leak information and focus on the k-means algorithm, which provides only limited clustering quality and flexibility. Additionally, the number of clusters k must be known in advance. We analyze several prominent clustering algorithms' capabilities and their compatibility with secure computation techniques to create an efficient, fully privacy-preserving clustering implementation superior to k-means. We find affinity propagation to be the most promising candidate and securely implement it using various multi-party computation techniques. Privacy-preserving affinity propagation does not require any input parameters and consists of operations hat are relatively efficient with secure computation. As threat models, we consider passive security as well as active security with an honest and dishonest majority. We offer the first comparison of privacy-preserving clustering between these scenarios, enabling an understanding of the exact trade-offs between them. Based on the clustering quality and the computational and communication costs, privacy-preserving affinity propagation offers a good trade-off between quality and efficiency for practical privacy-preserving clustering.

The J-PAKE protocol is a Password Authenticated Key Establishment protocol whose security rests on Diffie-Hellman key establishment and Non-Interactive Zero Knowledge proofs. It has seen widespread deployment and has previously been proven secure, including forward secrecy, in a game-based model. In this paper we show that this earlier proof can be re-cast in the Universal Composability framework, thus yielding a stronger result. We also investigate the extension of such proofs to a significantly more efficient variant of the original J-PAKE, that drops the second round Non-Interactive Zero-Knowledge proofs, that we call sJ-PAKE. Adapting the proofs to this light-weight variant proves highly-non trivial, and requires novel proof strategies and the introduction of the algebraic group model. This means that J-PAKE implementations can be made more efficient by simply deleting parts of the code while retaining security under stronger assumptions. We also investigate the security of two further new variants that combine the efficiency gains of dropping the second round NIZK proofs with the gains achieved by two earlier, lightweight variants: RO-J-PAKE and CRS-J-PAKE. The earlier variants replaced the second Diffie-Hellman terms from each party by either a hash term or a CRS term, thus removing the need for half of the NIZK proofs in the first round. The efficiency and security assumptions of these variants are compared.

Multi-Server Private Information Retrieval (PIR) is a cryptographic protocol that allows a client to securely query a database entry from $n \geq 2$ servers of which less than $t$ can collude, s.t. the servers learn no information about the query. Highly efficient PIR could be used for large-scale applications like Compromised Credential Checking (C3) (USENIX Security'19), which allows users to check whether their credentials have been leaked in a data breach. However, state-of-the art PIR schemes are not efficient enough for fast online responses at this scale. In this work, we introduce Client-Independent Preprocessing (CIP) PIR that moves $(t-1)/n$ of the online computation to a local, client independent, preprocessing phase suitable for efficient batch precomputations. The online performance of CIP-PIR improves linearly with the number of servers $n$. We show that large-scale applications like C3 with PIR are practical by implementing our CIP-PIR scheme using a parallelized CPU implementation. To the best of our knowledge, this is the first multi-server PIR scheme whose preprocessing phase is completely independent of the client, and where online performance simultaneously improves with the number of servers $n$. In addition, we accelerate for the first time the huge amount of XOR operations in multi-server PIR with GPUs. Our GPU-based CIP-PIR achieves an improvement up to factor $2.1\times$ over our CPU-based implementation for $n=2$ servers, and enables a client to query an entry in a 25 GB database within less than 1 second.

In $1$-out-of-$q$ Oblivious Transfer (OT) protocols, a sender Alice is able to send one of $q\ge 2$ messages to a receiver Bob, all while being oblivious to which message was transferred. Moreover, the receiver learns only one of these messages. Oblivious Transfer combiners take $n$ instances of OT protocols as input, and produce an OT protocol that is secure if sufficiently many of the $n$ original OT instances are secure. We present new $1$-out-of-$q$ OT combiners that are perfectly secure against active adversaries. Our combiners arise from secret sharing techniques. We show that given an $\mathbb{F}_q$-linear secret sharing scheme on a set of $n$ participants and adversary structure $\mathcal{A}$, we can construct $n$-server, $1$-out-of-$q$ OT combiners that are secure against an adversary corrupting either Alice and a set of servers in $\mathcal{A}$, or Bob and a set of servers $B$ with $\bar{B}\notin\mathcal{A}$. If the normalized total share size of the scheme is $\ell$, then the resulting OT combiner requires $\ell$ calls to OT protocols, and the total amount of bits exchanged during the protocol is $(q^2+q+1)\ell\log q$. We also present a construction based on $1$-out-of-$2$ OT combiners that uses the protocol of Crépeau, Brassard and Robert (FOCS 1986). This construction provides smaller communication costs for certain adversary structures, such as threshold ones: For any prime power $q\geq n$, there are $n$-server, $1$-out-of-$q$ OT combiners that are perfectly secure against active adversaries corrupting either Alice or Bob, and a minority of the OT candidates, exchanging $O(qn\log q)$ bits in total.

The 25 year-old NTRU problem is an important computational assumption in public-key cryptography. However, from a reduction perspective, its relative hardness compared to other problems on Euclidean lattices is not well-understood. Its decision version reduces to the search Ring-LWE problem, but this only provides a hardness upper bound. We provide two answers to the long-standing open problem of providing reduction-based evidence of the hardness of the NTRU problem. First, we reduce the worst-case approximate Shortest Vector Problem over ideal lattices to an average-case search variant of the NTRU problem. Second, we reduce another average-case search variant of the NTRU problem to the decision NTRU problem.

Differential-linear attacks are a cryptanalysis family that has recently benefited from various technical improvements, mainly in the context of ARX constructions. In this paper we push further this refinement, proposing several new improvements. In particular, we develop a better understanding of the related correlations, improve upon the statistics by using the LLR, and finally use ideas from conditional differentials for finding many right pairs. We illustrate the usefulness of these ideas by presenting the first 7.5-round attack on Chaskey. Finally, we present a new competitive attack on 12 rounds of Serpent, and as such the first cryptanalytic progress on Serpent in 10 years.

This paper presents the first publicly available cryptanalytic attacks on the GEA-1 and GEA-2 algorithms. Instead of providing full 64-bit security, we show that the initial state of GEA-1 can be recovered from as little as 65 bits of known keystream (with at least 24 bits coming from one frame) in time $2^{40}$ GEA-1 evaluations and using 44.5 GiB of memory. The attack on GEA-1 is based on an exceptional interaction of the deployed LFSRs and the key initialization, which is highly unlikely to occur by chance. This unusual pattern indicates that the weakness is intentionally hidden to limit the security level to 40 bit by design. In contrast, for GEA-2 we did not discover the same intentional weakness. However, using a combination of algebraic techniques and list merging algorithms we are still able to break GEA-2 in time $2^{45.1}$ GEA-2 evaluations. The main practical hurdle is the required knowledge of 1600 bytes of keystream.

In this work, we study Certificate Transparency (CT), an important standardized extension of classical Web-PKI, deployed and integrated into major browsers. We evaluate the properties of the published design of CT-v1 (RFC 6962), and identify five major concerns, which persist in drafts for CT-v2. Most significantly, CT-v1 fails to achieve the main goal of the original CT publications, namely security with No Trusted Third Party (NTTP) and it does not ensure transparency for revocation status. Several recent works address some of these issues but at the cost of significant, non-evolutionary deviation from the existing standards and ecosystem. In response, we present CTng, a redesign of CT. CTng achieves security, including transparency of certificate and of revocation status, with No Trusted Third Party, while preserving client’s privacy, allowing offline client validation of certificates, and facilitating resiliency to DoS. CTng is efficient and practical, and provides a possible next step in the evolution of PKI standards. We present a security analysis and an evaluation of our experimental open source prototype shows that CTng imposes acceptable communication and storage overhead.

In this note, we describe an attack against the ANSSI Side-Channel Analysis Database (ASCAD), which recovers the full key using the leakage of a single masked block cipher execution. The attack uses a new open-source Side-Channel Analysis Library (SCALib), which allows running the leakage profiling and attacking in less than 5 minutes. It exploits well-known techniques, yet improves significantly over the best known attacks against ASCAD. We conclude by questioning the impact of these experimental findings for side-channel security evaluations.

We study the problem of privacy-preserving approximate kNN search in an outsourced environment — the client sends the encrypted data to an untrusted server and later can perform secure approximate kNN search and updates. We design a security model and propose a generic construction based on locality-sensitive hashing, symmetric encryption, and an oblivious map. The construction provides very strong security guarantees, not only hiding the information about the data, but also the access, query, and volume patterns. We implement, evaluate efficiency, and compare the performance of two concrete schemes based on an oblivious AVL tree and an oblivious BSkiplist.

Improved attacks on generic small-domain Feistel ciphers with alternating round tweaks are obtained using linear cryptanalysis. This results in practical distinguishing and message-recovery attacks on the United States format-preserving encryption standard FF3-1 and the South-Korean standards FEA-1 and FEA-2. The data-complexity of the proposed attacks on FF3-1 and FEA-1 is $O(N^{r/2 - 1.5})$, where $N^2$ is the domain size and $r$ is the number of rounds. For example, FF3-1 with $N = 10^3$ can be distinguished from an ideal tweakable block cipher with advantage $\ge 1/10$ using $2^{23}$ encryption queries. Recovering the left half of a message with similar advantage requires $2^{24}$ data. The analysis of FF3-1 serves as an interesting real-world application of (generalized) linear cryptanalysis over the group $\mathbb{Z}/N\mathbb{Z}$.

Minimizing the round complexity of Byzantine Agreement (BA) protocols is a fundamental problem in distributed computing. The typical approach to achieve round efficient (randomized) BA is to have a weak form of BA, called graded consensus (GC), followed by a distributed coin, and to repeat this process until some termination condition is met---as introduced by Feldman and Micali (STOC'88). In this work, we revisit the question of building BA from GC, or, more precisely, from generalizations of GC. Concretely, for Monte Carlo style BA, where the protocol is run for a fixed number of rounds in function of the security parameter (in contrast to protocols with probabilistic termination), we demonstrate that this generalization helps to considerably reduce the round complexity of BA. In particular, assuming a setup for threshold signatures among the parties and corruption threshold $t<n/3$, we improve over the round complexity of the best known protocol by a factor of $1/2$, asymptotically; this is achieved by applying one single Feldman-Micali iteration consisting of one (generalized) GC instance and one round of coin tossing. Our technique also applies to the dishonest-minority case ($t<n/2$), yielding an improvement by a factor of $1/4$ (asymptotically) over the round complexity of the best known fixed-round protocol.

Intelligent Composed Algorithms (ICA) have been developed as a mechanism for introducing new cryptographic algorithms into applications and PKIs. Using ICAs, known cryptographic algorithms (Component-Algorithms) can be combined in order to obtain a stronger mix of cryptographic algorithms or primitives. Using ICAs it is also possible to use known Component-Algorithms as mutual alternatives. Furthermore, the combined and alternative use of Component-Algorithms as ICAs shall enable agile use of cryptographic algorithms without having to change standards as X.509 or CMS. An Intelligent Composed Algorithm is a flexible group of cryptographic algorithms together with the corresponding rules for their combination. The rules for the combination of Component-Algorithms are defined as algorithms (Controlling-Algorithms) themselves. In applications, ICAs are used as conventional algorithms, described by an algorithm identifier (an OID) and matching parameters. The chosen Component-Algorithms are defined by parameters of the Controlling-Algorithm. The use of ICAs impose no need to modify higher-order standards for applications and protocols, as X.509, RFC 5280, RFC 6960, RFC 2986, RFC 4210, and RFC 5652.

Ridesharing is revolutionizing the transportation industry in many countries. Yet, the state of the art is based on heavily centralized services and platforms, where the service providers have full possession of the users’ location data. Recently, researchers have started addressing the challenge of enabling privacy-preserving ridesharing. The initial proposals, however, have shortcomings, as some rely on a central party, some incur high performance penalties, and most do not consider time preferences for ridesharing. TOPPool encompasses ridesharing based on the proximity of end-points of a ride as well as partial itinerary overlaps. To achieve the latter, we propose a simple yet powerful reduction to a private set intersection on trips represented as sets of consecutive road segments. We show that TOPPool includes time preferences while preserving privacy and without relying on a third party. We evaluate our approach on real-world data from the New York’s Taxi & Limousine Commission. Our experiments demonstrate that TOPPool is superior in performance over the prior work: our intersection-based itinerary matching runs in less than 0.3 seconds for reasonable trip length, in contrast, on the same set of trips prior work takes up to 10 hours.

Fully homomorphic encryption (FHE) is an encryption scheme which enables computation on encrypted data without revealing the underlying data. While there have been many advances in the field of FHE, developing programs using FHE still requires expertise in cryptography. In this white paper, we present a fully homomorphic encryption transpiler that allows developers to convert high-level code (e.g., C++) that works on unencrypted data into high-level code that operates on encrypted data. Thus, our transpiler makes transformations possible on encrypted data. Our transpiler builds on Google's open-source XLS SDK (https://github.com/google/xls) and uses an off-the-shelf FHE library, TFHE (https://tfhe.github.io/tfhe/), to perform low-level FHE operations. The transpiler design is modular, which means the underlying FHE library as well as the high-level input and output languages can vary. This modularity will help accelerate FHE research by providing an easy way to compare arbitrary programs in different FHE schemes side-by-side. We hope this lays the groundwork for eventual easy adoption of FHE by software developers. As a proof-of-concept, we are releasing an experimental transpiler (https://github.com/google/fully-homomorphic-encryption/tree/main/transpiler) as open-source software.

Though recent breakthroughs greatly improved the efficiency of asynchronous Byzantine agreement (BA) protocols, they mainly focused on the setting with private setups, e.g., assuming established non-interactive threshold cryptosystems. Challenges remain to reduce the large communication complexities in the absence of such setups. For example, Abraham et al. (PODC'21) recently gave the first private-setup free construction for asynchronous validated BA (VBA) with expected $\mathcal{O}(n^3)$ messages and $\mathcal{O}(1)$ rounds, relying on only public key infrastructure (PKI), but the design still costs $\mathcal{O}(\lambda n^3 \log n)$ bits. Here $n$ is the number of parties, and $\lambda$ means the cryptographic security parameter capturing the length of hash, digital signature, etc. We reduce the communication of private-setup free asynchronous BA to expected $\mathcal{O}(\lambda n^3)$ bits. At the core of our design, we present a systematic treatment of reasonably fair common randomness protocols in the asynchronous network, and proceed as: (i) We give an efficient reasonably fair common coin protocol in the asynchronous setting with only PKI setup. It costs only $\mathcal{O}(\lambda n^3)$ bit and $\mathcal{O}(1)$ asynchronous rounds, and ensures that with at least $1/3$ probability, all honest parties can output a common bit that is as if randomly flipped. This directly renders more efficient private-setup free asynchronous binary agreement (ABA) with expected $\mathcal{O}(\lambda n^3)$ bits and expected constant rounds. (ii) Then, we lift our common coin to attain perfect agreement by using a single ABA. This gives us a reasonably fair random leader election protocol with expected $\mathcal{O}(\lambda n^3)$ communication and expected constant rounds. It is pluggable in all existing VBA protocols (e.g., Cachin et al., CRYPTO'01; Abraham et al., PODC'19; Lu et al., PODC'20) to remove the needed private setup or distributed key generation (DKG). As such, the communication of private-setup free VBA is reduced to expected $\mathcal{O}(\lambda n^3)$ bits while preserving fast termination in expected $\mathcal{O}(1)$ rounds. Moreover, our result paves a generic path to private-setup free asynchronous BA protocols, as it is not restricted to merely improve Abraham et al.'s specific VBA protocol in PODC'21. Our results and techniques could be found useful and interesting for a broad array of applications such as asynchronous DKG and DKG-free asynchronous random beacon.

Clustering is a popular unsupervised machine learning technique that groups similar input elements into clusters. It is used in many areas ranging from business analysis to health care. In many of these applications, sensitive information is clustered that should not be leaked. Moreover, nowadays it is often required to combine data from multiple sources to increase the quality of the analysis as well as to outsource complex computation to powerful cloud servers. This calls for efficient privacy-preserving clustering. In this work, we systematically analyze the state-of-the-art in privacy-preserving clustering. We implement and benchmark today's four most efficient fully private clustering protocols by Cheon et al. (SAC'19), Meng et al. (ArXiv'19), Mohassel et al. (PETS'20), and Bozdemir et al. (ASIACCS'21) with respect to communication, computation, and clustering quality. We compare them, assess their limitations for a practical use in real-world applications, and conclude with open challenges.

We provide the first construction of a succinct non-interactive argument (SNARG) for *all* polynomial time deterministic computations based on standard assumptions. For $T$ steps of computation, the size of the proof and the common random string (CRS) as well as the verification time are poly-logarithmic in $T$. The security of our scheme relies on the hardness of the Learning with Errors (LWE) problem against polynomial-time adversaries. Previously, SNARGs based on standard assumptions could support bounded-depth computations and required sub-exponential hardness assumptions [Jawale-Kalai-Khurana-Zhang, STOC'21]. Along the way, we also provide the first construction of non-interactive batch arguments for $\mathsf{NP}$ based solely on the LWE assumption.

We study the problem of designing *non-interactive batch arguments* for $\mathsf{NP}$. Such an argument system allows an efficient prover to prove multiple $\mathsf{NP}$ statements, with size smaller than the combined witness length. We provide the first construction of such an argument system for $\mathsf{NP}$ in the common reference string model based on standard cryptographic assumptions. Prior works either require non-standard assumptions (or the random oracle model) or can only support private verification. At the heart of our result is a new *dual mode* interactive batch argument system for $\mathsf{NP}$. We show how to apply the correlation-intractability framework for Fiat-Shamir -- that has primarily been applied to proof systems -- to such interactive arguments.

Existing blind signature schemes that are secure for polynomially many concurrent executions of the signing protocol are either inefficient or rely on non-standard assumptions (even in the random-oracle model). We show the first efficient blind signature schemes achieving this level of security based on the RSA, factoring, or discrete logarithm assumptions (in the random-oracle model). Our core technique involves an extension and generalization of a transform due to Pointcheval (Eurocrypt '98) that allows us to convert certain blind signature schemes that are secure for (concurrently) issuing logarithmically many signatures into ones secure for (concurrently) issuing polynomially many signatures.