Post-Quantum (PQ) signature schemes are known for large key and signature sizes, which may inhibit their deployment in real world applications. In this work, we construct a PQ signature scheme MMSAT that is the first such scheme capable of aggregating unrelated messages signed individually by different parties. Our proposal extends the notion of multisignatures, which are signatures that support aggregation of signatures on a single message signed by multiple parties. Multisignatures are especially useful in blockchain applications, where a transaction may be signed by multiple users. The proposed construction achieves significant gains in bandwidth and storage requirements by allowing aggregation of unrelated transactions. Our construction is derived by extending the PASS scheme, and thus the security of our scheme relies on the hardness of the Vandermonde-SIS problem. When aggregated, a signature consists of two parts. The first part is a post-quantum size signature that grows very slowly, scaling by on the order of~$\log{K}$ bits for~$K$ signatures. The second part scales linearly with~$K$, with a very short fixed cost, roughly twice the bit security. Thus even when aggregating a modest number of signatures, the per signature cost of MMSAT is in line with that of traditional pre-quantum signature schemes such as ECDSA. As an extension to MMSAT, we describe a variant called MMSATK in which it the public keys required to verify an aggregated signature are compressed by a factor of~$20$ to~$30$.

In their seminal work, Ben-Or and Linial (1985) introduced the full information model for collective coin-tossing protocols involving $n$ processors with unbounded computational power using a common broadcast channel for all their communications. The design and analysis of coin-tossing protocols in the full information model have close connections to diverse fields like extremal graph theory, randomness extraction, cryptographic protocol design, game theory, distributed protocols, and learning theory. Several works have focused on studying the asymptotically best attacks and optimal coin-tossing protocols in various adversarial settings. While one knows the characterization of the exact or asymptotically optimal protocols in some adversarial settings, for most adversarial settings, the optimal protocol characterization remains open. For the cases where the asymptotically optimal constructions are known, the exact constants or poly-logarithmic multiplicative factors involved are not entirely well-understood. In this work, we study $n$-processor coin-tossing protocols where every processor broadcasts an arbitrary-length message once. Note that, in this setting, which processor speaks and its message distribution may depend on the messages broadcast so far. An adaptive Byzantine adversary, based on the messages broadcast so far, can corrupt $k=1$ processor. A bias-$X$ coin-tossing protocol outputs 1 with probability $X$; 0 with probability $(1-X)$. For a coin-tossing protocol, its insecurity is the maximum change in the output distribution (in the statistical distance) that an adversarial strategy can cause. Our objective is to identify optimal bias-$X$ coin-tossing protocols with minimum insecurity, for every $X\in[0,1]$. Lichtenstein, Linial, and Saks (1989) studied bias-$X$ coin-tossing protocols in this adversarial model under the highly restrictive constraint that each party broadcasts an independent and uniformly random bit. The underlying message space is a well-behaved product space, and $X\in[0,1]$ can only be integer multiples of $1/2^n$, which is a discrete problem. The case where every processor broadcasts only an independent random bit admits simplifications, for example, the collective coin-tossing protocol must be monotone. Surprisingly, for this class of coin-tossing protocols, the objective of reducing an adversary’s ability to increase the expected output is equivalent to reducing an adversary’s ability to decrease the expected output. Building on these observations, Lichtenstein, Linial, and Saks proved that the threshold coin-tossing protocols are optimal for all $n$ and $k$. In a sequence of works, Goldwasser, Kalai, and Park (2015), Kalai, Komargodski, and Raz (2018), and (independent of our work) Haitner and Karidi-Heller (2020) prove that $k=\mathcal{O}\left(\sqrt n\cdot \polylog{n}\right)$ corruptions suffice to fix the output of any bias-X coin-tossing protocol. These results consider parties who send arbitrary-length messages, and each processor has multiple turns to reveal its entire message. However, optimal protocols robust to a large number of corruptions do not have any apriori relation to the optimal protocol robust to $k=1$ corruption. Furthermore, to make an informed choice of employing a coin-tossing protocol in practice, for a fixed target tolerance of insecurity, one needs a precise characterization of the minimum insecurity achieved by these coin-tossing protocols. We rely on an inductive approach to constructing coin-tossing protocols to study a proxy potential function measuring the susceptibility of any bias-$X$ coin-tossing protocol to attacks in our adversarial model. Our technique is inherently constructive and yields protocols that minimize the potential function. It happens to be the case that threshold protocols minimize the potential function. We demonstrate that the insecurity of these threshold protocols is 2-approximate of the optimal protocol in our adversarial model. For any other $X\in[0,1]$ that threshold protocols cannot realize, we prove that an appropriate (convex) combination of the threshold protocols is a 4-approximation of the optimal protocol.

We propose a very fast lattice-based zero-knowledge proof system for exactly proving knowledge of a ternary solution $\vec{s} \in \{-1,0,1\}^n$ to a linear equation $A\vec{s}=\vec{u}$ over $\mathbb{Z}_q$, which improves upon the protocol by Bootle, Lyubashevsky and Seiler (CRYPTO 2019) by producing proofs that are shorter by a factor of $8$. At the core lies a technique that utilizes the module-homomorphic BDLOP commitment scheme (SCN 2018) over the fully splitting cyclotomic ring $\mathbb{Z}_q[X]/(X^d + 1)$ to prove scalar products with the NTT vector of a secret polynomial.

We construct a practical lattice-based zero-knowledge argument for proving multiplicative relations between committed values. The underlying commitment scheme that we use is the currently most efficient one of Baum et al. (SCN 2018), and the size of our multiplicative proof ($9$KB) is only slightly larger than the $7$KB required for just proving knowledge of the committed values. We additionally expand on the work of Lyubashevsky and Seiler (Eurocrypt 2018) by showing that the above-mentioned result can also apply when working over rings $\mathbb{Z}_q[X]/(X^d+1)$ where $X^d+1$ splits into low-degree factors, which is a desirable property for many applications (e.g. range proofs, multiplications over $\mathbb{Z}_q$) that take advantage of packing multiple integers into the NTT coefficients of the committed polynomial.

It is known that attackers can exfiltrate data from air-gapped computers through their speakers via sonic and ultrasonic waves. To eliminate the threat of such acoustic covert channels in sensitive systems, audio hardware can be disabled and the use of loudspeakers can be strictly forbidden. Such audio-less systems are considered to be \textit{audio-gapped}, and hence immune to acoustic covert channels. In this paper, we introduce a technique that enable attackers leak data acoustically from air-gapped and audio-gapped systems. Our developed malware can exploit the computer power supply unit (PSU) to play sounds and use it as an out-of-band, secondary speaker with limited capabilities. The malicious code manipulates the internal \textit{switching frequency} of the power supply and hence controls the sound waveforms generated from its capacitors and transformers. Our technique enables producing audio tones in a frequency band of 0-24khz and playing audio streams (e.g., WAV) from a computer power supply without the need for audio hardware or speakers. Binary data (files, keylogging, encryption keys, etc.) can be modulated over the acoustic signals and sent to a nearby receiver (e.g., smartphone). We show that our technique works with various types of systems: PC workstations and servers, as well as embedded systems and IoT devices that have no audio hardware at all. We provide technical background and discuss implementation details such as signal generation and data modulation. We show that the POWER-SUPPLaY code can operate from an ordinary user-mode process and doesn't need any hardware access or special privileges. Our evaluation shows that using POWER-SUPPLaY, sensitive data can be exfiltrated from air-gapped and audio-gapped systems from a distance of five meters away at a maximal bit rates of 50 bit/sec.

In this paper, we investigate the security of the Learning With Error (LWE) problem with small secrets by refining and improving the so-called dual lattice attack. More precisely, we use the dual attack on a projected sublattice, which allows generating instances of the LWE problem with a slightly bigger noise that correspond to a fraction of the secret key. Then, we search for the fraction of the secret key by computing the corresponding noise for each candidate using the newly constructed LWE samples. As secrets are small, we can perform the search step very efficiently by exploiting the recursive structure of the search space. This approach offers a trade-off between the cost of lattice reduction and the complexity of the search part which allows to speed up the attack. Besides, we aim at providing a sound and \emph{non-asymptotic} analysis of the techniques to enable its use for practical selection of security parameters. As an application, we revisit the security estimates of some fully homomorphic encryption schemes, including the Fast Fully Homomorphic Encryption scheme over the Torus (TFHE) which is one of the fastest homomorphic encryption schemes based on the (Ring-)LWE problem. We provide an estimate of the complexity of our method for various parameters under three different cost models for lattice reduction and show that the security level of the TFHE scheme should be re-evaluated according to the proposed improvement (for at least 7 bits for the most recent update of the parameters that are used in the implementation).

The typical battery supported IoT computing node has progressed in recent years from an 8-bit processor with limited memory resources, to a 32-bit processor with ample amounts of ROM and RAM. This is a game-changer for developers who no longer need to struggle with assembly language programming, but rather can bring to bear all of the tools of modern software engineering, including high level language compilers. At the same time curve based cryptography has matured to the extent that efficient curves and algorithms are now well known. However the dynamics of academic research are such that execution speed, mandating continued use of assembly language, trumps all other considerations. In this paper we report on the performance that can be expected from simple portable high-level language implementations across a wide range of contemporary architectures.

The technological advancements of the digital era paved the way for the facilitation of electronic voting (e-voting) in the promise of efficiency and enhanced security. In standard e-voting designs, the tally process is assigned to a committee of designated entities called talliers. Naturally, the security analysis of any e-voting system with tallier designation hinges on the assumption that a subset of the talliers follows the execution guidelines and does not attempt to breach privacy. As an alternative approach, Kiayias and Yung [PKC ’02] pioneered the self-tallying elections (STE) paradigm, where the post-ballot-casting (tally) phase can be performed by any interested party, removing the need for tallier designation. In this work, we explore the prospect of decentralized e-voting where security is preserved under concurrent protocol executions. In particular, we provide the first comprehensive formalization of STE in the universal composability (UC) framework introduced by Canetti [FOCS ’01] via an ideal functionality that captures required security properties such as voter privacy, eligibility, fairness, one-voter one-vote, and verifiability. We provide a concrete instantiation, called E-cclesia , that UC realizes our functionality. The design of E-cclesia integrates several cryptographic primitives such as signatures of knowledge for anonymous eligibility check, dynamic accumulators for scalability, time-lock encryption for fairness and anonymous broadcast channels for voter privacy. For the latter primitive, we provide the first UC formalization along with a construction based on mix-nets that utilises layered encryption, threshold secret sharing and equivocation techniques. Finally, we discuss deployment and scalability considerations for E-cclesia . We present preliminary benchmarks of the key operations (in terms of computational cost) of the voting client and demonstrate the feasibility of our proposal with readily available cryptographic tools for mid-sized elections (∼100,000 voters).

In this paper we exploit elementary combinatorial techniques to settle different cryptanalytic observations on RC4 that remained unproved for more than two decades. At the same time, we present new observations with theoretical proofs. We first prove the biases (non-randomness) presented by Fluhrer and McGrew (FSE 2000) two decades ago. It is surprising that though the biases have been published long back, and there are many applications of them in cryptanalysis till recent days as well, the proofs have never been presented. In this paper, we complete that task and also show that any such bias immediately provides a glimpse of hidden variables in RC4. Further, we take up the biases of two non-consecutive key-stream bytes skipping one byte in between. We show the incompleteness of such a result presented by SenGupta et al (JoC, 2013) and provide new observations and proofs in this direction relating the key-stream bytes and glimpses. Similarly, we streamline certain missed observation in the famous Glimpse theorem presented by Jenkins in 1996. Our results point out how biases of RC4 key-stream and the Glimpses of the RC4 hidden variables are related. It is evident from our results that the biases and glimpses are everywhere in RC4 and it needs further investigation as we provide very high magnitude of glimpses that were not known earlier. The new glimpses and biases that we identify in this paper may be exploited in improving practical attacks against the protocols that use RC4.

Today’s world is organized based on merit and value. A single global currency that’s decentralized is needed for a global economy. Bitcoin is a partial solution to this need, however it suffers from scalability problems which prevent it from being mass-adopted. Also, the deflationary nature of bitcoin motivates people to hoard and speculate on them instead of using them for day to day transactions. We propose a scalable, decentralized cryptocurrency that is based on Proof of Work. The solution involves having parallel chains in a closed network using a mechanism which rewards miners proportional to their effort in maintaining the network. The proposed design introduces a novel approach for solving scalability problem in blockchain network based on merged mining.

The QC-MDPC code-based KEM BIKE is one of the Round-2 candidates of the NIST PQC standardization project. Its specification document describes a version that is claimed to have IND-CCA security. The security proof uses the Fujisaki-Okamoto transformation and a de-coder that targeted a Decoding Failure Rate (DFR) of 2^{-128} (for Level-1 security). However, there are several aspects that need to be amended in order for the IND-CCA proof to hold. The main issue is that using a decoder with DFR of 2^{-128} does not necessarily imply that the underlying PKE is \delta correct with \delta=2^{-128}, as required. In this paper, we handle the necessary aspects in the definitions of the KEM to ensure the security claim is correct. In particular, we close the gap in the proof by defining the notion of a message-agnostic PKE for which decryption failures are independent of the encrypted message. We show that all the PKE underlying the BIKE versions are message-agnostic. This implies that BIKE with a decoder that has a sufficiently low DFR is also an IND-CCA KEM.

In the recent trend of CAESAR competition and NIST light-weight competition, cryptographic community have witnessed the submissions of several cryptographic schemes that are build on public random permutations. Recently, in CRYPTO 2019, Chen et al. have initiated an interesting research direction in designing beyond birthday bound PRFs from public random permutations and they proposed two instances of such PRFs. In this work, we extend this research direction by proposing a nonce-based MAC build from public random permutations. We show that our proposed MAC achieves $2n/3$ bit security (with respect to the state size of the permutation) and the bound is essentially tight. Moreover, the security of the MAC degrades gracefully with the repetition of the nonce.

Side-channel leakage detection methods based on statistical tests, such as t-test or chi^2-test, provide high confidence in the presence of leakage with a large number of traces. However, practical limitations on testing time and equipment may set an upper-bound on the number of traces available, turning the number of traces into a limiting factor in side-channel leakage detection. We describe a statistical technique, based on statistical bootstrapping, that significantly improves the effectiveness of leakage detection using a limited set of traces. Bootstrapping generates additional sample sets from an initial set by assuming that it is representative of the entire population. The additional sample sets are then used to conduct additional leakage detection tests, and we show how to combine the results of these tests. The proposed technique, applied to side-channel leakage detection, can significantly reduce the number of traces required to detect leakage by one, or more orders of magnitude. Furthermore, for an existing measured sample set, the method can significantly increase the confidence of existing leakage hypotheses over a traditional (non-bootstrap) leakage detection test. This paper introduces the bootstrapping technique for leakage detection, applies it to three practical cases, and describes techniques for its efficient computation.

The existence of some structure in a code can lead to the decrease of security of the whole system built on it. Often subcodes are used to ``disguise'' the code as a ``general-looking'' one. However, the security of subcodes, whose Hadamard square is equal to the square of the base code, is reduced to the security of this code, i.e. this condition is undesirable. The paper finds the limiting conditions on the number of vectors of degree $ r $ removing of which retains this weakness for Reed--Muller subcodes and, accordingly, conditions for it to vanish. For $ r = 2 $ the exact structure of all resistant subcodes was found. For an arbitrary code $ RM(r, m) $, the desired number was estimated from both sides. Finally, the ratio of subcodes, whose Hadamard square is not equal to the square of the original code, was proven to tend to zero if additional conditions on the codimension of the subcode and the parameter $ r $ are imposed and $ m \rightarrow \infty $. Thus, the implementation of checks proposed in the paper helps to immediately filter out some insecure subcodes.

Cryptographic implementations deployed in real world devices often aim at (provable) security against the powerful class of side-channel attacks while keeping reasonable performances. Last year at Asiacrypt, a new formal verification tool named tightPROVE was put forward to exactly determine whether a masked implementation is secure in the well-deployed probing security model for any given security order t. Also recently, a compiler named Usuba was proposed to automatically generate bitsliced implementations of cryptographic primitives. This paper goes one step further in the security and performances achievements with a new automatic tool named Tornado. In a nutshell, from the high-level description of a cryptographic primitive, Tornado produces a functionally equivalent bitsliced masked implementation at any desired order proven secure in the probing model, but additionally in the so-called register probing model which much better fits the reality of software implementations. This framework is obtained by the integration of Usuba with tightPROVE+, which extends tightPROVE with the ability to verify the security of implementations in the register probing model and to fix them with inserting refresh gadgets at carefully chosen locations accordingly. We demonstrate Tornado on the lightweight cryptographic primitives selected to the second round of the NIST competition and which somehow claimed to be masking friendly. It advantageously displays performances of the resulting masked implementations for several masking orders and proves their security in the register probing model.

Contact tracing is among the most important interventions to mitigate the spread of any pandemic, usually in the form of manual contact tracing. Smartphone-facilitated digital contact tracing may help to increase tracing capabilities and extend the coverage to those contacts one does not know in person. Most implemented protocols use local Bluetooth Low Energy (BLE) communication to detect contagion-relevant proximity, together with cryptographic protections, as necessary to improve the privacy of the users of such a system. However, current decentralized protocols, including DP3T, do not sufficiently protect infected users from having their status revealed to their contacts, which raises fear of stigmatization. We alleviate this by proposing a new and practical solution with stronger privacy guarantees against active adversaries. It is based on the upload-what-you-observed paradigm, includes a separation of duties on the server side, and a mechanism to ensure that users cannot deduce which encounter caused a warning with high time resolution. Finally, we present a simulation-based security notion of digital contact tracing in the real–ideal setting, and prove the security of our protocol in this framework.

Multiple protocols implementing exciting cryptographic functionalities using blockchains such as time-lock encryption, one-time programs and fair multi-party computation assume the existence of a cryptographic primitive called extractable witness encryption. Unfortunately, there are no known efficient constructions (or even constructions based on any well studied assumptions) of extractable witness encryption. In this work, we propose a protocol that uses a blockchain itself to provide a functionality that is effectively the same as extractable witness encryption. By making small adjustments to the blockchain code, it is possible to easily implement applications that rely on extractable witness encryption and existed only as theoretical designs until now. There is also potential for new applications. As a key building block, our protocol uses a new and highly efficient batched dynamic proactive secret sharing scheme which may be of independent interest. We provide a proof-of-concept implementation of the extractable witness encryption construction and the underlying dynamic proactive secret sharing protocol.

We propose a new encoding algorithm for the simultaneous differential multidimensional scalar point multiplication algorithm $d$-MUL. Previous encoding algorithms are known to have major drawbacks in their efficient and secure implementation. Some of these drawbacks have been avoided in a recent paper in 2018 at a cost of losing the general functionality of the point multiplication algorithm. In this paper, we address these issues. Our new encoding algorithm takes the binary representations of scalars as input, and constructs a compact binary sequence and a permutation, which explicitly determines a regular sequence of group operations to be performed in $d$-MUL. Our algorithm simply slides windows of size two over the scalars and it is very efficient. As a result, while preserving the full generality of $d$-MUL, we successfully eliminate the recursive integer matrix computations in the originally proposed encoding algorithms. We also expect that our new encoding algorithm will make it easier to implement $d$-MUL in constant time. Our results can be seen as the efficient and full generalization of the one dimensional Montgomery ladder to arbitrary dimension.

The emergence of e-commerce has changed the way people trade. However, merchants are charged high fees for their use of the platform and for payment services. These costs are passed on to customers in the form of higher prices. Blockchain technology can provide lower transaction fees with high security and privacy level but is incapable of delivering the number of transactions per second demanded by real e-commerce. Establishing a layer above the blockchain to manage transactions which we called Blockchain Layer2 technology, has the potential to solve these issues. In this article, we focus on the effect that layer2 technology can provide in reducing fee costs and improving transaction volumes. We introduce the problems that the e-commerce industry is facing currently and how blockchain layer2 technology can help to address these issues. We list and describe the main layer2 mechanisms based on the Bitcoin and Ethereum blockchains. We discuss issues that arise when applying layer 2 technology to e-commerce. We analyse the costs associated with difference e-commerce payment network topologies and investigate the funds-capacity needed to support high levels of value transfer.

ECDSA is a widely adopted digital signature standard. A number of threshold protocols for ECDSA have been developed that let a set of parties jointly generate the secret signing key and compute signatures, without ever revealing the signing key. Threshold protocols for ECDSA have seen recent interest, in particular due to the need for additional security in cryptocurrency wallets where leakage of the signing key is equivalent to an immediate loss of money. We propose a threshold ECDSA protocol secure against an active adversary in the honest majority model with abort. Our protocol is efficient in terms of both computation and bandwidth usage, and it allows the parties to pre-process parts of the signature, such that once the message to sign becomes known, they can compute a secret sharing of the signature very efficiently, using only local operations. We also show how to obtain fairness in the online phase at the cost of some additional work in the pre-processing, i.e., such that the protocol either aborts during the pre-processing phase, in which case nothing is revealed, or the signature is guaranteed to be delivered to all honest parties.

Designing cryptographic permutations and block ciphers using a substitution-permutation network (SPN) approach where the nonlinear part does not cover the entire state has recently gained attention due to favorable implementation characteristics in various scenarios. For word-oriented partial SPN (P-SPN) schemes with a fixed linear layer, our goal is to better understand how the details of the linear layer affect the security of the construction. In this paper, we derive conditions that allow us to either set up or prevent attacks based on infinitely long truncated differentials with probability 1. Our analysis is rather broad compared to earlier independent work on this problem since we consider (1) both invariant and non-invariant/iterative trails, and (2) trails with and without active S-boxes. For these cases, we provide rigorous sufficient and necessary conditions for the matrix that defines the linear layer to prevent the analyzed attacks. On the practical side, we present a tool that can determine whether a given linear layer is vulnerable based on these results. Furthermore, we propose a sufficient condition for the linear layer that, if satisfied, ensures that no infinitely long truncated differential exists. This condition is related to the degree and the irreducibility of the minimal polynomial of the matrix that defines the linear layer. Besides P-SPN schemes, our observations may also have a crucial impact on the Hades design strategy, which mixes rounds with full S-box layers and rounds with partial S-box layers.

Recursive proof composition has been shown to lead to powerful primitives such as incrementally-verifiable computation (IVC) and proof-carrying data (PCD). All existing approaches to recursive composition take a succinct non-interactive argument of knowledge (SNARK) and use it to prove a statement about its own verifier. This technique requires that the verifier run in time sublinear in the size of the statement it is checking, a strong requirement that restricts the class of SNARKs from which PCD can be built. This in turn restricts the efficiency and security properties of the resulting scheme. Bowe, Grigg, and Hopwood (ePrint 2019/1021) outlined a novel approach to recursive composition, and applied it to a particular SNARK construction which does *not* have a sublinear-time verifier. However, they omit details about this approach and do not prove that it satisfies any security property. Nonetheless, schemes based on their ideas have already been implemented in software. In this work we present a collection of results that establish the theoretical foundations for a generalization of the above approach. We define an *accumulation scheme* for a non-interactive argument, and show that this suffices to construct PCD, even if the argument itself does not have a sublinear-time verifier. Moreover we give constructions of accumulation schemes for SNARKs, which yield PCD schemes with novel efficiency and security features.

The surge of interest in decentralization-enabling technologies sparked by the recent success of Bitcoin and other blockchains has led to several new challenges in cryptography and protocol design. One such challenge concerns the widely used digital signature scheme -- ECDSA -- that has in particular been chosen to secure transactions in Bitcoin and several other blockchain systems. To empower decentralized interoperability between such blockchains one would like to implement distributed custody over Bitcoin accounts, which technically can be realized via a threshold ECDSA protocol. Even though several threshold ECDSA protocols already exist, as we argue, due to lack of robustness in signature generation, they are not well suited for deployment scenarios with large committees of parties, out of which a significant fraction might be malicious or prone to DDoS attacks. We propose a new threshold ECDSA protocol that improves upon the state-of-the-art solutions by enabling robustness and fault attributability during signature generation. In addition to that, we improve the signing time and bandwidth of previous solutions by moving expensive operations that are oblivious to the signed message to a separate setup phase. Finally, we back our theoretical results via an empirical evaluation of our protocol in large-scale experiments in LAN and WAN settings.

Collusion-free (CF) and collusion-preserving (CP) protocols enrich the standard security offered by multi-party computation (MPC), to tackle settings where subliminal communication is undesirable. However, all existing solutions make arguably unrealistic assumptions on setups, such as physical presence of the parties, access to physical envelopes, or extreme isolation, where the only means of communication is a star-topology network. The above state of affairs remained a limitation of such protocols, which was even reinforced by impossibility results. Thus, for years, it has been unclear if and how the above setup assumptions could be relaxed towards more realistic scenarios. Motivated also by the increasing interest in using hardware tokens for cryptographic applications, in this work we provide the first solution to collusion preserving computation which uses weaker and more common assumptions than the state of the art, i.e., an authenticated broadcast functionality and access to honestly generated trusted hardware tokens. We prove that our protocol is collusion-preserving (in short, {\em CP}) secure as long as no parties abort. In the case of an aborting adversary, our protocol still achieves standard (G)UC security with identifiable (and unanimous) abort. Leveraging the above identifiability property, we augment our protocol with a penalization scheme which ensures that it is not profitable to abort, thereby obtaining CP security against incentive-driven attackers. To define (and prove) this latter result, we combine the Rational Protocol Design (RPD) methodology by Garay {\em et al.} [FOCS 2013] with the CP framework of Alwen {\em et al.} [CRYPTO 2012] to derive a definition of security in the presence of incentive-driven local adversaries which can be of independent interest. Similar to existing CP/CF solutions, our protocol preserves, as a fallback, security against monolithic adversaries, even when the setup (i.e., the hardware tokens) is compromised or corrupted. In addition, our fallback solution achieves identifiable and unanimous abort, which we prove are impossible in previous CP solutions.

ElGamal public key encryption scheme has been designed in the 80’s. It is one of the first partial homomorphic encryption and one of the first IND-CPA probabilistic public key encryption scheme. A linear version has been recently proposed by Boneh et al. In this paper, we present a linear encryption based on a generalized version of ElGamal encryption scheme. We prove that our scheme is IND-CPA secure under the linear assumption. We design a also generalized ElGamal scheme from the generalized linear. We also run an evaluation of performances of our scheme. We show that the decryption algorithm is faster than the existing versions.

Abstract: Rotation operator is frequently used in several stream ciphers, including HC-128, Rabbit, and Salsa20, the final candidates for eSTREAM. This is because ‘Rotation operator (ROT)’ is simple but has very good dispersibility. In this paper, we propose a ‘disperse rotation operator (DRT)’, which has the same structure as ROT but has better dispersibility. In addition, the use of DRT instead of ROT has shown that the quality of the output stream of all three stream ciphers is significantly improved. On the other hand, the use of DRT instead of ROT in HC-128 stream cipher prevents the expansion of differentiated attacks based on LSB.

We close the gap between black-box and non-black-box constructions of $\mathit{composable}$ secure multiparty computation in the plain model under the $\mathit{minimal}$ assumption of semi-honest oblivious transfer. The notion of protocol composition we target is $\mathit{angel\text{-}based}$ security, or more precisely, security with super-polynomial helpers. In this notion, both the simulator and the adversary are given access to an oracle called an $\mathit{angel}$ that can perform some predefined super-polynomial time task. Angel-based security maintains the attractive properties of the universal composition framework while providing meaningful security guarantees in complex environments without having to trust anyone. Angel-based security can be achieved using non-black-box constructions in $\max(R_{\mathsf{OT}},\widetilde{O}(\log n))$ rounds where $R_{\mathsf{OT}}$ is the round-complexity of the semi-honest oblivious transfer. However, currently, the best known $\mathit{black\text{-}box}$ constructions under the same assumption require $\max(R_{\mathsf{OT}},\widetilde{O}(\log^2 n))$ rounds. If $R_{\mathsf{OT}}$ is a constant, the gap between non-black-box and black-box constructions can be a multiplicative factor $\log n$. We close this gap by presenting a $\max(R_{\mathsf{OT}},\widetilde{O}(\log n))$-round black-box construction. We achieve this result by constructing constant-round 1-1 CCA-secure commitments assuming only black-box access to one-way functions.

Mass surveillance can be more easily achieved leveraging fear and desire of the population to feel protected while affected by devastating events. Indeed, in such scenarios, governments can adopt exceptional measures that limit civil rights, usually receiving large support from citizens. The COVID-19 pandemic is currently affecting daily life of many citizens in the world. People are forced to stay home for several weeks, unemployment rates quickly increase, uncertainty and sadness generate an impelling desire to join any government effort in order to stop as soon as possible the spread of the virus. Following recommendations of epidemiologists, governments are proposing the use of smartphone applications to allow automatic contact tracing of citizens.Such systems can be an effective way to defeat the spread of the SARS-CoV-2 virus since they allow to gain time in identifying potentially new infected persons that should therefore be in quarantine. This raises the natural question of whether this form of automatic contact tracing can be a subtle weapon for governments to violate privacy inside new and more sophisticated mass surveillance programs. In order to preserve privacy and at the same time to contribute to the containment of the pandemic, several research partnerships are proposing privacy-preserving contact tracing systems where pseudonyms are updated periodically to avoid linkability attacks. A core component of such systems is Bluetooth low energy (BLE, for short) a technology that allows two smartphones to detect that they are in close proximity. Among such systems there are some proposals like DP-3T, MIT-PACT, UW-PACT and the Apple&Google exposure notification system that through a decentralized approach claim to guarantee better privacy properties compared to other centralized approaches (e.g., PEPP-PT-NTK, PEPP-PT-ROBERT). On the other hand, advocates of centralized approaches claim that centralization gives to epidemiologists more useful data, therefore allowing to take more effective actions to defeat the virus. Motivated by Snowden's revelations about previous attempts of governments to realize mass surveillance programs, in this paper we first analyze mass surveillance attacks that leverage weaknesses of automatic contact tracing systems. We focus in particular on the DP-3T system (still our analysis is significant also for MIT-PACT and Apple&Google systems). Based on recent literature and new findings, we discuss how a government can exploit the use of the DP-3T system to successfully mount privacy attacks as part of a mass surveillance program. Interestingly, we show that privacy issues in the DP-3T system are not inherent in BLE-based contact tracing systems. Indeed, we propose two systems named and $\textsf{Pronto-C2}$ that, in our view, enjoy a much better resilience with respect to mass surveillance attacks still relying on BLE. Both systems are based on a paradigm shift: instead of asking smartphones to send keys to the Big Brother (this corresponds to the approach of the DP-3T system), we construct a decentralized BLE-based ACT system where smartphones anonymously and confidentially talk to each other in the presence of the Big Brother. Unlike $\textsf{Pronto-B2}$, $\textsf{Pronto-C2}$ relies on Diffie-Hellman key exchange providing better privacy but also requiring a bulletin board to translate a BLE beacon identifier into a group element. Both systems can optionally be implemented using Blockchain technology, offering complete transparency and resilience through full decentralization, therefore being more appealing for citizens. Only through a large participation of citizens contact tracing systems can be really useful to defeat COVID-19, and our proposal goes straight in this direction.

Building on the Gennaro & Goldfeder and Lindell & Nof protocols (CCS ’18), we present a threshold ECDSA protocol, for any number of signatories and any threshold, that improves as follows over the state of the art: * Signature generation takes only 4 rounds (down from the current 8 rounds), with a comparable computational cost. Furthermore, 3 of these rounds can take place in a preprocessing stage before the signed message is known, lending to a non-interactive threshold ECDSA protocol. * The protocol withstands adaptive corruption of signatories. Furthermore, it includes a periodic refresh mechanism and offers full proactive security. * The protocol realizes an ideal threshold signature functionality within the UC framework, in the global random oracle model, assuming Strong RSA, semantic security of the Paillier encryption, and a somewhat enhanced variant of existential unforgeability of ECDSA. These properties (low latency, compatibility with cold-wallet architectures, proactive security, and composable security) make the protocol ideal for threshold wallets for ECDSA-based cryptocurrencies.

We propose a leveled homomorphic encryption scheme based on the Approximate Greatest Common Divisor (AGCD) problem that operates natively on vectors and matrices. To overcome the limitation of large ciphertext expansion that is typical in AGCD-based schemes, we randomize the ciphertexts with a hidden matrix, which allows us to choose smaller parameters. To be able to efficiently evaluate circuits with large multiplicative depth, we use a decomposition technique à la GSW. The running times and ciphertext sizes are practical: for instance, for 100 bits of security, we can perform a sequence of 128 homomorphic products between 128-dimensional vectors and $128\times 128$ matrices in less than one second. We show how to use our scheme to homomorphically evaluate nondeterministic finite automata and also a Naïve Bayes Classifier. We also present a generalization of the GCD attacks against the some variants of the AGCD problem.

Since David Chaum introduced the idea of mix nets 40 years ago, they have become widely used building blocks for privacy-preserving protocols. Several important applications, such as secure e-voting, require that the employed mix net be verifiable. In the literature, numerous techniques have been proposed to make mix nets verifiable. Some of them have also been employed in politically binding elections. Verifiable mix nets differ in many aspects, including their precise verifiability levels, possible trust assumptions, and required cryptographic primitives; unfortunately, these differences are often opaque, making comparison painful. To shed light on this intransparent state of affairs, we provide the following contributions. For each verifiability technique proposed to date, we first precisely describe how the underlying basic mix net is to be extended and which (additional) cryptographic primitives are required, and then study its verifiability level, including possible trust assumptions, within one generic and expressive verifiability framework. Based on our uniform treatment, we are able to transparently compare all known verifiability techniques for mix nets, including their advantages and limitations. Altogether, our work offers a detailed and expressive reference point for the design, employment, and comparison of verifiable mix nets.

In this paper, we review different approaches on proximity tracing apps which are supposed to automate the current labor-intensive contact tracing approach conducted by national health officials. The purpose of these apps is to automatically notify people who are at risk of being infected with SARS-CoV-2 to interrupt infection chains as early as possible. However, a privacy-preserving and yet functional and scalable design of such apps is not trivial and in some parts leads to counter-intuitive properties. This paper reviews the most prominent European approaches, DP-3T, the German variant "NTK"' of PEPP-PT, and its closely related concept ROBERT. We discuss their design decisions from a privacy perspective and point out the fundamentally different adversary models assumed by the approaches. In addition, we touch on practical aspects such as scalability and ease of implementation.

Since Cheon et al. introduced an approximate homomorphic encryption scheme for complex numbers called Cheon-Kim-Kim-Song (CKKS) scheme, it has been widely used and applied in real-life situations, such as privacy-preserving machine learning. The polynomial approximation of a modulus reduction is the most difficult part of the bootstrapping for the CKKS scheme. In this paper, we cast the problem of finding an approximate polynomial for a modulus reduction into an L2-norm minimization problem. As a result, we find an approximate polynomial for the modulus reduction without using the sine function, which is the upper bound for the approximation of the modulus reduction. With the proposed method, we can reduce the degree of the polynomial required for an approximate modulus reduction, while also reducing the error compared with the most recent result reported by Han et al. (CT-RSA' 20). Consequently, we can achieve a low-error approximation, such that the maximum error is less than $2^{-40}$ for the size of the message $m/q\approx 2^{-10}$. By using the proposed method, the constraint of $q = O(m^{3/2})$ is relaxed as $O(m)$, and thus the level loss in bootstrapping can be reduced. The solution of the cast problem is determined in an efficient manner without iteration.

Motivated by recent results on solving large batches of closest vector problem (CVP) instances, we study how these techniques can be combined with lattice enumeration to obtain faster methods for solving the shortest vector problem (SVP) on high-dimensional lattices. Theoretically, under common heuristic assumptions we show how to solve SVP in dimension $d$ with a cost proportional to running a sieve in dimension $d - \Theta(d / \log d)$, resulting in a $2^{\Theta(d / \log d)}$ speedup and memory reduction compared to running a full sieve. Combined with techniques from [Ducas, Eurocrypt 2018] we can asymptotically get a total of $[\log(13/9) + o(1)] \cdot d / \log d$ dimensions \textit{for free} for solving SVP. Practically, the main obstacles for observing a speedup in moderate dimensions appear to be that the leading constant in the $\Theta(d / \log d)$ term is rather small; that the overhead of the (batched) slicer may be large; and that competitive enumeration algorithms heavily rely on aggressive pruning techniques, which appear to be incompatible with our algorithms. These obstacles prevented this asymptotic speedup (compared to full sieving) from being observed in our experiments. However, it could be expected to become visible once optimized CVPP techniques are used in higher dimensional experiments.

Rotational-XOR cryptanalysis is a cryptanalytic method aimed at finding distinguishable statistical properties in ARX-C ciphers, i.e., ciphers that can be described only using modular addition, cyclic rotation, XOR, and the injection of constants. In this paper we extend RX-cryptanalysis to AND-RX ciphers, a similar design paradigm where the modular addition is replaced by vectorial bitwise AND; such ciphers include the block cipher families Simon and Simeck. We analyse the propagation of RX-differences through AND-RX rounds and develop closed form formula for their expected probability. Finally, we formulate an SMT model for searching RX-characteristics in simon and simeck. Evaluating our model we find RX-distinguishers of up to 20, 27, and 35 rounds with respective probabilities of $2^{-26}, 2^{-42}$, and $2^{-54}$ for versions of simeck with block sizes of 32, 48, and 64 bits, respectively, for large classes of weak keys in the related-key model. In most cases, these are the longest published distinguishers for the respective variants of simeck. Interestingly, when we apply the model to the block cipher simon, the best distinguisher we are able to find covers 11 rounds of SIMON32 with probability $2^{-24}$. To explain the gap between simon and simeck in terms of the number of distinguished rounds we study the impact of the key schedule and the specific rotation amounts of the round function on the propagation of RX-characteristics in Simon-like ciphers.

We consider algebraic affine and projective curves of Edwards [3, 9] over the finite field ${{\text{F}}_{{{p}^{n}}}}$. It is known that many modern cryptosystems [11] can be naturally transformed into elliptic curves [5]. We research Edwards algebraic curves over a finite field, which are one of the most promising supports of sets of points which are used for fast group operations \cite{Bir}. We construct a new method for counting the order of an Edwards curve over a finite field. It should be noted that this method can be applied to the order of elliptic curves due to the birational equivalence between elliptic curves and Edwards curves. We not only find a specific set of coefficients with corresponding field characteristics for which these curves are supersingular, but we additionally find a general formula by which one can determine whether a curve ${{E}_{d}}[{{\mathbb{F}}_{p}}]$ is supersingular over this field or not. The method we have proposed has much less complexity $O\left( p\log _{2}^{2}p \right)$ at not large values $p$ in comparison with the best Schoof basic algorithm with complexity$O(log_{2}^{8}{{p}^{n}})$, as well as a variant of the Schoof algorithm that uses fast arithmetic, which has complexity $O(log_{2}^{4}{{p}^{n}})$, but works only for Elkis or Atkin primes. The embedding degree of the supersingular curve of Edwards over ${{\mathbb{F}}_{{{p}^{n}}}}$ in a finite field is investigated and the field characteristic, where this degree is minimal, is found. A birational isomorphism between the Montgomery curve and the Edwards curve is also constructed. A one-to-one correspondence between the Edwards supersingular curves and Montgomery supersingular curves is established. The criterion of supersingularity for Edwards curves is found over ${{\mathbb{F}}_{{{p}^{n}}}}$. \\

Contact Tracing is considered as the first and the most effective step towards containing an outbreak, as resources for mass testing and large quantity of vaccines are highly unlikely available for immediate utilization. Effective contact tracing can allow societies to reopen from lock-down even before availability of vaccines. The objective of mobile contact tracing is to speed up the manual interview based contact tracing process for containing an outbreak efficiently and quickly. In this article, we throw light on some of the issues and challenges pertaining to the adoption of mobile contact tracing solutions for fighting COVID-19. In essence, we proposed an Evaluation framework for mobile contact tracing solutions to determine their usability, feasibility, scalability and effectiveness. We evaluate some of the already proposed contact tracing solutions in light of our proposed framework. Furthermore, we present possible attacks that can be launched against contact tracing solutions along with their necessary countermeasures to thwart any possibility of such attacks.

For more than two decades, proving or refuting the following statement has remained a challenging open problem in the theory of secret sharing schemes (SSSs): every ideal access structure admits an ideal perfect multi-linear SSS. We consider a weaker statement in this paper asking if: every ideal access structure admits an ideal perfect group-characterizable (GC) SSS. Since the class of GC SSSs is known to include the multi-linear ones (as well as several classes of non-linear schemes), it might turn out that the second statement is not only true but also easier to tackle. Unfortunately, our understanding of GC SSSs is still too basic to tackle the weaker statement. As a first attempt, it is natural to ask if every ideal perfect SSS is equivalent to some GC scheme. The main contribution of this paper is to construct counterexamples using tools from theory of Latin squares and some recent results developed by the present authors for studying GC SSSs.

By associating Fermat's Little Theorem based $GF(2^n)$ inversion algorithms with the multiplicative Norm function, we present an additive Trace based $GF(2^n)$ inversion algorithm. For elements with Trace value 0, it needs 1 less multiplication operation than Fermat's Little Theorem based algorithms in some $GF(2^n)$s.

Due to growing commercial applications like Blockchain, the performance of large-integer arithmetic is the focus of both academic and industrial research. IBM introduced a new integer fused multiply-add instruction in z14, called VMSL, to accelerate such workloads. Unlike their floating-point counterparts, there are a variety of integer fused multiply-add instruction designs. VMSL multiplies two pairs of radix $2^{56}$ inputs, sums the two results together with an additional 128-bit input, and stores the resulting 128-bit value in a vector register. In this paper, we will describe the unique features of VMSL, the ways in which it is inherently more efficient than alternative specifications, in particular by enabling multiple carry strategies. We will then look at the issues we encountered implementing Montgomery Modular Multiplication for Elliptic Curve Cryptography on z14, including radix choice, mixed radices, instruction selection to trade instruction count for latency, and VMSL-specific optimizations for Montgomery-friendly moduli. The best choices resulted in a 20% increase in throughput.

This study is an attempt in quest of the fastest hardware algorithms for the computation of the evaluation component of verifiable delay functions (VDFs), $a^{2^T} \bmod N$, proposed for use in various distributed protocols, in which no party is assumed to compute it significantly faster than other participants. To this end, we propose a class of modular squaring algorithms suitable for low-latency ASIC implementations. The proposed algorithms aim to achieve highest levels of parallelization that have not been explored in previous works in the literature, which usually pursue more balanced optimization of speed and area. For this, we utilize redundant representations of integers and introduce three modular squaring algorithms that work with integers in redundant forms: i) Montgomery algorithm, ii) memory-based algorithm and iii) direct reduction algorithm for fixed moduli. All algorithms enable $O(\log k)$ depth circuit implementations, where $k$ is the bit-size of the modulus $N$ in the VDF function. We analyze and compare gate level-circuits of the proposed algorithms and provide estimates for their critical path delay and gate count.

In this work, we introduce the notion of puncturable witness pseudorandom function (pWPRF) which is a stronger variant of WPRF proposed by Zhandry, TCC 2016. The punctured technique is similar to what we have seen for puncturable PRFs and is capable of extending the applications of WPRF. Specifically, we construct a semi-adaptively secure offline witness encryption (OWE) scheme using a pWPRF, an indistinguishability obfuscation (iO) and a symmetric-key encryption (SKE), which enables us to encrypt messages along with NP statements. We show that replacing iO with extractability obfuscation, the OWE turns out to be an extractable offline witness encryption scheme. To gain finer control over data, we further demonstrate how to convert our OWEs into offline functional witness encryption (OFWE) and extractable OFWE. All of our OWEs and OFWEs produce an optimal size ciphertext, in particular, encryption of a message is as small as the size of the message plus the security parameter multiplied with a constant, which is optimal for any public-key encryption scheme. On the other hand, in any previous OWE, the size of a ciphertext increases polynomially with the size of messages. Finally, we show that the WPRF of Pal et al. (ACISP 2019) can be extended to a pWPRF and an extractable pWPRF.

In a recent work, Kumar, Meka, and Sahai (FOCS 2019) introduced the notion of bounded collusion protocols (BCPs), in which $N$ parties wish to compute some joint function $f:(\{0,1\}^n)^N\to\{0,1\}$ using a public blackboard, but such that only $p$ parties may collude at a time. This generalizes well studied models in multiparty communication complexity, such as the number-in-hand (NIH) and number-on-forehead (NOF) models, which are just endpoints on this rich spectrum. We construct explicit hard functions against this spectrum, and achieve a tradeoff between collusion and complexity. Using this, we obtain improved leakage-resilient secret sharing schemes against bounded collusion protocols. Our main tool in obtaining hard functions against BCPs are explicit constructions of leakage resilient extractors against BCPs for a wide range of parameters. Kumar et al. (FOCS 2019) studied such extractors and called them cylinder intersection extractors. In fact, such extractors directly yield correlation bounds against BCPs. We focus on the following setting: the input to the extractor consists of $N$ independent sources of length $n$, and the leakage function Leak $:(\{0,1\}^n)^N\to\{0,1\}^\mu\in\mathcal{F}$ is a BCP with some collusion bound $p$ and leakage (output length) $\mu$. While our extractor constructions are very general, we highlight some interesting parameter settings: 1. In the case when the input sources are uniform, and $p=0.99N$ parties collude, our extractor can handle $n^{\Omega(1)}$ bits of leakage, regardless of the dependence between $N,n$. The best NOF lower bound (i.e., $p=N-1$) on the other hand requires $N<\log n$ even to handle $1$ bit of leakage. 2. Next, we show that for the same setting as above, we can drop the entropy requirement to $k=$ polylog $n$, while still handling polynomial leakage for $p=0.99N$. This resolves an open question about cylinder intersection extractors raised by Kumar et al. (FOCS 2019), and we find an application of such low entropy extractors in a new type of secret sharing. We also provide an explicit compiler that transforms any function with high NOF (distributional) communication complexity into a leakage-resilient extractor that can handle polylogarithmic entropy and substantially more leakage against BCPs. Thus any improvement of NOF lower bounds will immediately yield better leakage-resilient extractors. Using our extractors against BCPs, we obtain improved $N$-out-of-$N$ leakage-resilient secret sharing schemes. The previous best scheme from Kumar et al. (FOCS 2019) required share size to grow exponentially in the collusion bound, and thus cannot efficiently handle $p=\omega(\log N)$. Our schemes have no dependence of this form, and can thus handle collusion size $p=0.99N$.

In this work we first provide a framework for defining a large subset of pairing-based digital signature schemes which we call Partially Structure-Preserving Signature (PSPS) schemes. PSPS schemes are similar in nature to structure-preserving signatures with the exception that in these schemes messages are scalars from $\Z^n_p$ instead of being source group elements. This class encompasses various existing schemes which have a number of desirable features which makes them an ideal building block for many privacy-preserving cryptographic protocols. They include the widely-used schemes of Camenisch-Lysyanskaya (CRYPTO 2004) and Pointcheval-Sanders (CT-RSA 2016). We then provide various impossibility and lower bound results for variants of this class. Our results include bounds for the signature and verification key sizes as well as lower bounds for achieving strong unforgeability. We also give a generic framework for transforming variants of PSPS schemes into structure-preserving ones. As part of our contribution, we also give a number of optimal PSPS schemes which may be of independent interest. Our results aid in understanding the efficiency of pairing-based signature schemes and show a connection between this class of signature schemes and structure-preserving ones.

Decentralized and permissionless ledgers offer an inherently low transaction rate, as a result of their consensus protocol demanding the storage of each transaction on-chain. A prominent proposal to tackle this scalability issue is to utilize off-chain protocols, where parties only need to post a limited number of transactions on-chain. Existing solutions can roughly be categorized into: (i) application-specific channels (e.g., payment channels), offering strictly weaker functionality than the underlying blockchain; and (ii) state channels, supporting arbitrary smart contracts at the cost of being compatible only with the few blockchains having Turing-complete scripting languages (e.g., Ethereum). In this work, we introduce and formalize the notion of generalized channels allowing users to perform any operation supported by the underlying blockchain in an off-chain manner. Generalized channels thus extend the functionality of payment channels and relax the definition of state channels. We present a concrete construction compatible with any blockchain supporting transaction authorization, time-locks and constant number of Boolean $\land$ and $\lor$ operations -- requirements fulfilled by many (non-Turing-complete) blockchains including the popular Bitcoin. To this end, we leverage adaptor signatures -- a cryptographic primitive already used in the cryptocurrency literature but formalized as a standalone primitive in this work for the first time. We formally prove the security of our generalized channel construction in the Universal Composability framework. As an important practical contribution, our generalized channel construction outperforms the state-of-the-art payment channel construction, the Lightning Network, in efficiency. Concretely, it halves the off-chain communication complexity and reduces the on-chain footprint in case of disputes from linear to constant in the number of off-chain applications funded by the channel. Finally, we evaluate the practicality of our construction via a prototype implementation and discuss various applications including financially secured fair two-party computation.

This paper provides a theoretical background for a new consensus model called Proof of Review (PoR), which extends Algorand’s blockchain consensus model and reproduces the human mechanism for analyzing reviews through analysis and reputation. Our protocol derives the trustworthiness of a participant’s reputation through a consensus of these reviews. In this new protocol, we combined concepts from proof of stake and proof of reputation to ensure a blockchain system comes to consensus on an honest (non-malicious) congruent review. Additionally, we formally prove this protocol provides further security by using a reputation-based stake instead of token-based, using theorems and proofs. We introduce new concepts in using reputation as a stake, where reputation must be earned and can never be purchased, spent, or traded. The stake is calculated based on the reputation -- not tokens -- of a user in the system proportional to the total reputation in the system at the beginning of each round. A round is a set of steps that conclude in a block being added to the blockchain. We also introduce blacklisting as a decisive action where, after a vote, an honest user will blacklist a leader (the participant elected with their proposed block) or reviewer for some egregious maliciousness, preventing further participation. Five steps are defined that overlay Algorand’s steps: (1) Evaluation of reviews; (2) Selection of the round’s leader and their associated block containing reviews; (3) Re-evaluation of reviews; (4) Block of reviews agreement (block decision); (5) Block addition to the ledger and reputation adjustment. At every step, verifiers are selected randomly for evaluating the reviews and are anonymous to each other. We provided properties related to reputation and formally proved (Honest Leader, Blacklisting Liveliness and Correctness, Evaluation of the Evaluator’s Confidence, Gradual Gain, and Swift Loss of Reputation). Finally, we discuss several types of attacks that are common for Proof of Stake and Reputation systems, and how our Proof of Review model (in extending Algorand) addresses those attacks. Furthermore, PoR mitigates several kinds of fake reviews (e.g. spam, trolling, etc.) through analysis. Preliminary experimental results show that payment transactions have similar completion times, regardless of the stake being tokens or reputation, the mechanism for adjusting reputation reflects expected behavior, and the accuracy of the review evaluation (using sentimental analysis) is substantiated for the dataset given. With this new model, we let the technology evaluate a review and secure it on a blockchain using a reputation-based stake. Proof of Review also provides third party access to reviewer’s reputation along with their respective evaluated reviews, a functionality that could benefit numerous industries including retail, academia, hospitality, corporate, and more. Applications could expedite and validate many different types of processes that rely on a form of review and the analysis of that review.

Zk-SNARKs, as the most efficient NIZK arguments in terms of proof size and verification, are ubiquitously deployed in practice. In applications like Hawk [S&P'16], Gyges [CCS'16], Ouroboros Crypsinous [S&P'19], the underlying zk-SNARK is lifted to achieve Black-Box Simulation Extractability (BB-SE) under a trusted setup phase. To mitigate the trust in such systems, we propose $\texttt{Tiramisu}$, as a construction to build NIZK arguments that can achieve $\textit{updatable BB-SE}$, which we define as a new variant of BB-SE. This new variant allows $\textit{updating}$ the public parameters, therefore eliminating the need for a trusted third party, while unavoidably relies on a $\textit{non-black-box}$ extraction algorithm in the setup phase. In the cost of one-time individual CRS update by the parties, this gets around a known impossibility result by Bellare et al. from ASIACRYPT'16, which shows that BB extractability cannot be achieved with subversion ZK (ZK without trusting a third party). $\texttt{Tiramisu}$ uses an efficient public-key encryption with updatable keys which may be of independent interest. We instantiate $\texttt{Tiramisu}$, implement the overhead, and present efficient BB-SE zk-SNARKs with updatable parameters that can be used in various applications while allowing the end-users to update the parameters and eliminate the needed trust.

In this work we study bounded collusion protocols (BCPs) recently introduced in the context of secret sharing by Kumar, Meka, and Sahai (FOCS 2019). These are multi-party communication protocols on $n$ parties where in each round a subset of $p$-parties (the collusion bound) collude together and write a function of their inputs on a public blackboard. BCPs interpolate elegantly between the well-studied number-in-hand (NIH) model ($p=1$) and the number-on-forehead (NOF) model ($p=n-1$). Motivated by questions in communication complexity, secret sharing, and pseudorandomness we investigate BCPs more thoroughly, answering several questions about them. * We prove a polynomial (in the input-length) lower bound for an explicit function against BCPs where any constant fraction of players can collude. Previously, nontrivial lower bounds were known only when the collusion bound was at most logarithmic in the input-length (owing to bottlenecks in NOF lower bounds). * For all $t \leq n$, we construct efficient $t$-out-of-$n$ secret sharing schemes where the secret remains hidden even given the transcript of a BCP with collusion bound $O(t/\log t)$. Prior work could only handle collusions of size $O(\log n)$. Along the way, we construct leakage-resilient schemes against disjoint and adaptive leakage, resolving a question asked by Goyal and Kumar (STOC 2018). * An explicit $n$-source cylinder intersection extractor whose output is close to uniform even when given the transcript of a BCP with a constant fraction of parties colluding. The min-entropy rate we require is $0.3$ (independent of collusion bound $p \ll n$). Our results rely on a new class of exponential sums that interpolate between the ones considered in additive combinatorics by Bourgain (Geometric and Functional Analysis 2009) and Petridis and Shparlinski (Journal d'Analyse Mathématique 2019).

Directed Acyclic Graph (DAG) is becoming an intriguing direction for distributed ledger structure due to its great potential in improving the scalability of distributed ledger systems. Among existing DAG-based ledgers, one promising category is transaction DAG, namely, treating each transaction as a graph vertex. In this paper, we propose Haootia, a novel two-layer framework of consensus, with a ledger in the form of a transaction DAG built on top of a delicately designed PoW-based backbone chain. By elaborately devising the principle of transaction linearizations, we achieve a secure and scalable DAG-based consensus. By implementing Haootia, we conclude that, with a rotating committee of size 46 and a confirmation latency around 20 seconds, Haootia achieves a throughput around 7500 TPS which is overwhelming compared with all formally analyzed DAG-based consensus schemes to date and all existing non-DAG-based ones to our knowledge.

In this work, we prove that Interpose PUF is learnable in the PAC model. First, we show that Interpose PUF can be approximated by a Linear Threshold Function~(LTF), assuming the interpose bit to be random. We translate the randomness in the interpose bit to classification noise of the hypothesis. Using classification noise model, we prove that the resultant LTF can be learned with number of labelled examples~(challenge response pairs) polynomial in the number of stages and PAC model parameters.

Stateful hash-based signature schemes are among the most efficient approaches for post-quantum signature schemes. Although not suitable for general use, they may be suitable for some use cases on constrained devices. LMS and XMSS are hash-based signature schemes that are conjectured to be quantum secure. In this work, we compared multiple instantiations of both schemes on an ARM Cortex-M4. More precisely, we compared performance, stack consumption, and other figures for key generation, signing and verifying. To achieve this, we evaluated LMS and XMSS using optimised implementations of SHA-256, SHAKE256, Gimli-Hash, and different variants of Keccak. Furthermore, we present slightly optimised implementations of XMSS achieving speedups of up to 3.11x for key generation, 3.11x for signing, and 4.32x for verifying.

Secure enclave architectures have become prevalent in modern CPUs and enclaves provide a flexible way to implement various hardware-assisted security services. But special-purpose security chips can still have advantages. Interestingly, dedicated security chips can also assist enclaves and improve their security.

Distributed Auditing Proofs of Liabilities (DAPOL) provides a novel zero knowledge proof solution to a particular class of auditing cases, in which we assume that the audited entity does not have any incentive to increase its liabilities or obligations. There are numerous domains requiring such an auditing feature, including proving financial solvency, transparent fundraising campaigns and accurate lottery jackpot amounts. Additionally, the algorithm provides a solution to official reports, such as in COVID-19 published daily cases, unemployment rate announcements and decentralized product/service rating reviews. Interestingly, it can also be used as a cryptographic primitive for novel e-voting systems (i.e., disapproval voting and counting dislikes), and for innovative private syndicated loan/insurance solutions, new methods for decentralized credit scoring and user ranking, among the others. Compared to conventional auditor-based approaches, DAPOL provides a privacy preserving mechanism for users to validate their vote or amount inclusion in the reported total of liabilities/obligations and complements the traditional validation performed by the auditors by adding extra privacy and fairness guarantees. The recommended approach combines previously known cryptographic techniques to provide a layered solution with predefined levels of privacy in the form of gadgets. The backbone of this proposal is based on the enhanced Maxwell Merkle-tree construction and is extended using zero knowledge proofs, sparse trees, balance splitting tricks, efficient padding, verifiable random functions, deterministic key derivation functions and the range proof techniques from Provisions and ZeroLedge solvency protocols, respectively.

The Meet-in-the-Middle (MITM) preimage attack is highly effective in breaking the preimage resistance of many hash functions, including but not limited to the full MD5, HAVAL, and Tiger, and reduced SHA-0/1/2. It was also shown to be a threat to hash functions built on block ciphers like AES by Sasaki in 2011. Recently, such attacks on AES hashing modes evolved from merely using the freedom of choosing the internal state to also exploiting the freedom of choosing the message state. However, detecting such attacks especially those evolved variants is difficult. In previous works, the search space of the configurations of such attacks is limited, such that manual analysis is practical, which results in sub-optimal solutions. In this paper, we remove artificial limitations in previous works, formulate the essential ideas of the construction of the attack in well-defined ways, and translate the problem of searching for the best attacks into optimization problems under constraints in Mixed-Integer-Linear-Programming (MILP) models. The MILP models capture a large solution space of valid attacks; and the objectives of the MILP models are attack configurations with the minimized computational complexity. With such MILP models and using the off-the-shelf solver, it is efficient to search for the best attacks exhaustively. As a result, we obtain the first attacks against the full (5-round) and an extended (5.5-round) version of Haraka-512 v2, and 8-round AES-128 hashing modes, as well as improved attacks covering more rounds of Haraka-256 v2 and other members of AES and Rijndael hashing modes.

The design of software countermeasures against active and passive adversaries is a challenging problem that has been addressed by many authors in recent years. The proposed solutions adopt a theoretical foundation (such as a leakage model) but often do not offer concrete reference implementations to validate the foundation. Contributing to the experimental dimension of this body of work, we propose a customized processor called SKIVA that supports experiments with the design of countermeasures against a broad range of implementation attacks. Based on bitslice programming and recent advances in the literature, SKIVA offers a flexible and modular combination of countermeasures against power-based and timing-based side-channel leakage and fault injection. Multiple configurations of side-channel protection and fault protection enable the programmer to select the desired number of shares and the desired redundancy level for each slice. Recurring and security-sensitive operations are supported in hardware through custom instruction-set extensions. The new instructions support bitslicing, secret-share generation, redundant logic computation, and fault detection. We demonstrate and analyze multiple versions of AES from a side-channel analysis and a fault-injection perspective, in addition to providing a detailed performance evaluation of the protected designs. To our knowledge, this is the first validated end-to-end implementation of a modular bitslice-oriented countermeasure.

An important selling point for the RISC-V instruction set is the separation between ISA and the implementation of the ISA, leading to flexibility in the design. We argue that for secure implementations, this flexibility is often a vulnerability. With a hardware attacker, the side-effects of instruction execution cannot be ignored. As a result, a strict separation between the ISA interface and implementation is undesirable. We suggest that secure ISA may require additional implementation constraints. As an example, we describe an instruction-set for the development of power side-channel resistant software.

Blockchains are gaining traction and acceptance, not just for cryptocurrencies, but increasingly as an architecture for distributed computing. In this work we seek solutions that allow a \emph{public} blockchain to act as a trusted long-term repository of secret information: Our goal is to deposit a secret with the blockchain, specify how it is to be used (e.g., the conditions under which it is released), and have the blockchain keep the secret and use it only in the specified manner (e.g., release only it once the conditions are met). This simple functionality enables many powerful applications, including signing statements on behalf of the blockchain, using it as the control plane for a storage system, performing decentralized program-obfuscation-as-a-service, and many more. Using proactive secret sharing techniques, we present a scalable solution for implementing this functionality on a public blockchain, in the presence of a mobile adversary controlling a small minority of the participants. The main challenge is that, on the one hand, scalability requires that we use small committees to represent the entire system, but, on the other hand, a mobile adversary may be able to corrupt the entire committee if it is small. For this reason, existing proactive secret sharing solutions are either non-scalable or insecure in our setting. We approach this challenge via "player replaceability", which ensures the committee is anonymous until after it performs its actions. Our main technical contribution is a system that allows sharing and re-sharing of secrets among the members of small dynamic committees, without knowing who they are until after they perform their actions and erase their secrets. Our solution handles a fully mobile adversary corrupting roughly 1/4 of the participants at any time, and is scalable in terms of both the number of parties and the number of time intervals.

The advances in machine learning have revealed its great potential for emerging mobile applications such as face recognition and voice assistant. Models trained via a Neural Network (NN) can offer accurate and efficient inference services for mobile users. Unfortunately, the current deployment of such service encounters privacy concerns. Directly offloading the model to the mobile device violates model privacy of the model owner, while feeding user input to the service compromises user privacy. To address this issue, we propose, tailor, and evaluate Leia, a lightweight cryptographic NN inference system at the edge. Unlike prior cryptographic NN inference systems, Leia is designed with two mobile-friendly perspectives. First, Leia leverages the paradigm of edge computing wherein the inference procedure keeps the model closer to the mobile user to foster low latency service. Specifically, Leia's architecture consists of two non-colluding edge services to obliviously perform NN inference on the encoded user data and model. Second, Leia's realization makes the judicious use of potentially constrained computational and communication resources in edge devices. In particular, Leia adapts the Binarized Neural Network (BNN), a trending flavor of NN model with low memory footprint and computational cost, and purely chooses the lightweight secret sharing techniques to develop secure blocks of BNN. Empirical validation executed on Raspberry Pi confirms the practicality of Leia, showing that Leia can produce a prediction result with 97% accuracy by 4 seconds in the edge environment.

Motivated by a fundamental paradigm in cryptography, we consider a recent variant of the classic problem of bounding the distinguishing advantage between a random function and a random permutation. Specifically, we consider the problem of deciding whether a sequence of $q$ values was sampled uniformly with or without replacement from $[N]$, where the decision is made by a streaming algorithm restricted to using at most s bits of internal memory. In this work, the distinguishing advantage of such an algorithm is measured by the KL divergence between the distributions of its output as induced under the two cases. We show that for any $ s=\Omega( \log N) $ the distinguishing advantage is upper bounded by $ O(q\cdot s/N) $, and even by $ O(q\cdot s/N \log N) $ when $ q\le N^{1-\epsilon} $ for any constant $ \epsilon>0 $ where it is nearly tight with respect to the KL divergence.

At Crypto ’99, Nguyen and Stern described a lattice based algorithm for solving the hidden subset sum problem, a variant of the classical subset sum problem where the n weights are also hidden. While the Nguyen-Stern algorithm works quite well in practice for moderate values of n, we argue that its complexity is actually exponential in n; namely in the final step one must recover a very short basis of a n-dimensional lattice, which takes exponential-time in n, as one must apply BKZ reduction with increasingly large block-sizes. In this paper, we describe a variant of the Nguyen-Stern algorithm that works in polynomial-time. The first step is the same orthogonal lattice attack with LLL as in the original algorithm. In the second step, instead of applying BKZ, we use a multivariate technique that recovers the short lattice vectors and finally the hidden secrets in polynomial time. Our algorithm works quite well in practice, as we can reach n=250 in a few hours on a single PC.

Verifying security of advanced cryptographic primitives such as attribute-based encryption (ABE) is often difficult. In this work, we show how to break eleven schemes: two single-authority and nine multi-authority (MA) ABE schemes. Notably, we break DAC-MACS, a highly-cited multi-authority scheme, published at TIFS. This suggests that, indeed, verifying security of complex schemes is complicated, and may require simpler tools. The multi-authority attacks also illustrate that mistakes are made in transforming single-authority schemes into multi-authority ones. To simplify verifying security, we systematize our methods to a linear approach to analyzing generic security of ABE. Our approach is not only useful in analyzing existing schemes, but can also be applied during the design and reviewing of new schemes. As such, it can prevent the employment of insecure (MA-)ABE schemes in the future.

Fault Template Analysis (FTA) has been shown as a powerful tool for attacking cryptosystems and exposing vulnerabilities which were previously not reported in existing literature. Fault templates can be utilized for attacking block ciphers in middle rounds which were known prior to be resistant against fault attacks. In this paper we revisit the potent of fault templates and show a more systematic methodology to develop fault templates of Boolean circuits using a well known concept in design verification, namely positive Davio's decomposition. We show that the improved FTAs, called FTA2.0, can be used to fault analyze block ciphers in the middle rounds using as few as two bit-flip faults. Further, it can be used to attack TI-implemented block ciphers by considering a Double Bit Upset (DBU) fault in a target share bit. The attack shows that varying the latency of the fault the adversary can obtain unmasked bits and can recover the secret key.

Synchronous consensus protocols, by definition, have a worst-case commit latency that depends on the bounded network delay. The notion of optimistic responsiveness was recently introduced to allow synchronous protocols to commit instantaneously when some optimistic conditions are met. In this work, we revisit this notion of optimistic responsiveness and present optimal latency results. We present a lower bound for Byzantine Broadcast that relates the latencies of optimistic and synchronous commits when the designated sender is honest and while the optimistic commit can tolerate some faults. We then present two matching upper bounds for tolerating f faults out of n = 2f +1 parties. Our first upper bound result achieves optimal optimistic and synchronous commit latencies when the designated sender is honest and the optimistic commit can tolerate some faults. Our second upper bound result achieves optimal optimistic and synchronous commit latencies when the designated sender is honest but the optimistic commit does not tolerate any faults. The presence of matching lower and upper bound results make both of the results tight for n = 2f + 1. Our upper bound results are presented in a state machine replication setting with a steady state leader who is replaced with a view-change protocol when they do not make progress. For this setting, we also present an optimistically responsive protocol where the view-change protocol is optimistically responsive too.

Sharing a documents with a business partner is not always easy. since the sender often need to send sensitive information. and he want to ensure the integrity and the secrecy of the document. And in the same time. he wants to insure that only the specific individual or the recipients are the only one who can view it. So people tend to use some encryption software. or protecting the document with some sort of password. and then share the password with the recipient to make sure he is the only one who can view the document. But Unfortunately in many situations this method will not work. for a particular reason. and that is once the sender send an email. the email will start his journey into the company's network. and it will pass through many appliances. such Firewalls, Exchange servers and most likely Sandboxes. And there is one feature in sandboxes that we are interested in. once the sandbox sees an encrypted file or a protected file. it will immediately stop the email and quarantine it. because the sandbox couldn’t scan it. or couldn’t ensure if it’s malicious or not. so it will stop it for further analysis or a manual analysis depending on the procedures there. And such an action could stop a valid business transaction. and it could cause some business interruption. In this paper we will introduce a scheme for allowing the share of protected files. and analyzing them through Sandboxes. and in the same time no one can view it except for the authorized people.

Payment Channel Networks (PCNs) have been a promising approach to scale blockchains. However, PCNs have limited liquidity: large-amount or multi-hop payments may fail. The major threat of PCNs liquidity is payment griefing, where the adversary who acts as the payee keeps withholding the payment, so that coins involved in the payment cannot be used for routing other payments before the payment expires. Payment griefing gives adversaries a chance to launch the congestion attack, where the adversary griefs a large number of payments and paralyses the entire PCN. Understanding congestion attacks, including their strategies and impact, is crucial for designing PCNs with better liquidity guarantees. However, existing research has only focused on the specific attacking strategies and specific aspects of their impact on PCNs. We fill this gap by studying the general congestion attack. Compared to existing attack strategies, in our framework each step serves an orthogonal purpose and is customisable, allowing the adversary to focus on different aspects of the liquidity. To evaluate the attack's impact, we propose a generic method of quantifying PCNs' liquidity and effectiveness of the congestion attacks. We evaluate our general congestion attacks on Bitcoin's Lightning Network, and show that with direct channels to 1.5% richest nodes, and $\sim$ 0.0096 BTC of cost, the adversary can launch a congestion attack that locks 47% ($\sim$280 BTC) coins in the network; reduces success rate of payments by 16.0%$\sim$60.0%; increases fee of payments by 4.5%$\sim$16.0%; increases average attempts of payments by 42.0%$\sim$115.3%; and increase the number of bankruptcy nodes (i.e., nodes with insufficient balance for making normal-size payments) by 26.6%$\sim$109.4%, where the amounts of payments range from 0.001 to 0.019 BTC.

We report on the concrete cryptanalysis of LEDAcrypt, a 2nd Round candidate in NIST's Post-Quantum Cryptography standardization process and one of 17 encryption schemes that remain as candidates for near-term standardization. LEDAcrypt consists of a public-key encryption scheme built from the McEliece paradigm and a key-encapsulation mechanism (KEM) built from the Niederreiter paradigm, both using a quasi-cyclic low-density parity-check (QC-LDPC) code. In this work, we identify a large class of extremely weak keys and provide an algorithm to recover them. For example, we demonstrate how to recover 1 in $2^{47.72}$ of LEDAcrypt's keys using only $2^{18.72}$ guesses at the 256-bit security level. This is a major, practical break of LEDAcrypt. Further, we demonstrate a continuum of progressively less weak keys (from extremely weak keys up to all keys) that can be recovered in substantially less work than previously known. This demonstrates that the imperfection of LEDAcrypt is fundamental to the system's design.

We present an optimization of Lagrange's algorithm for lattice basis reduction in dimension 2. The optimized algorithm is proven to be correct and to always terminate with quadratic complexity; it uses more iterations on average than Lagrange's algorithm, but each iteration is much simpler to implement, and faster. The achieved speed is such that it makes application of the speed-up on ECDSA and EC Schnorr signatures described by Antipa et al worthwhile, even for very fast curves such as Ed25519. We applied this technique to signature verification in Curve9767, and reduced verification time by 30 to 33% on both small (ARM Cortex M0+ and M4) and large (Intel Coffee Lake with AVX2) architectures.

We design a consecution of protocols which allows organizations to have secure strong access control of their users to their desktop machines based on biometry. It provides both strong secure authentication and privacy. Moreover, our mechanism allows the system admins to grant a various level of access to their end-users by fine tuning access control policy. Our system implements privacy-by-design. It separates biometric data from identity information. It is practical: we fully implemented our protocols as a proof of concept for a hospital. We use a 3D fingervein scanner to capture the biometric data of the user on a Raspberry Pi. For the biometry part, we developed an optimal way to aggregate scores using sequential distinguishers. It trades desired FAR and FRR against an average number of biometric captures.

In a quantum money scheme, a bank can issue money that users cannot counterfeit. Similar to bills of paper money, most quantum money schemes assign a unique serial number to each money state, thus potentially compromising the privacy of the users of quantum money. However in a quantum coins scheme, just like the traditional currency coin scheme, all the money states are exact copies of each other, providing a better level of privacy for the users. A quantum money scheme can be private, i.e., only the bank can verify the money states, or public, meaning anyone can verify. In this work, we propose a way to lift any private quantum coin scheme -- which is known to exist based on the existence of one-way functions, due to Ji, Liu, and Song (CRYPTO'18) -- to a scheme that closely resembles a public quantum coin scheme. Verification of a new coin is done by comparing it to the coins the user already possesses, by using a projector on to the symmetric subspace. No public coin scheme was known prior to this work. It is also the first construction that is very close to a public quantum money scheme and is provably secure based on standard assumptions. The lifting technique when instantiated with the private quantum coins scheme, due to Mosca and Stebila 2010, gives rise to the first construction that is very close to an inefficient unconditionally secure public quantum money scheme.

Computing on data in a manner that preserve the privacy is of growing importance. Multi-Party Computation (MPC) and Homomorphic Encryption (HE) are two cryptographic techniques for privacy-preserving computations. In this work, we have developed efficient UC-secure multiparty protocols for matrix multiplications and two-dimensional convolutions. We built upon the SPDZ framework and integrated the state-of-the-art HE algorithms for matrix multiplication. Our protocol achieved communication cost linear only in the input and output dimensions and not on the number of multiplication operations. We eliminate the ``triple sacrifice'' step of SPDZ to improve efficiency and simplify the zero-knowledge proofs. We implemented our protocols and benchmarked them against the SPDZ LowGear variant (Keller et al. Eurocrypt'18). For multiplying two square matrices of size 128, we reduced the communication cost from 1.54 GB to 12.46 MB, an improvement of over two orders of magnitude that only improves with larger matrix sizes. For evaluating all convolution layers of the ResNet-50 neural network, the communication reduces cost from 5 TB to 41 GB.

Pointcheval-Sanders (PS) signatures are well-studied in the literature and have found use within e.g. threshold credential schemes and redactable anonymous credential schemes. The present work leverages a mapping between PS signatures and a related class of polynomial-based signatures to construct multiple new signature/credential schemes. Specifically, new protocols for multi-message signatures, sequential aggregate signatures, signatures for message commitments, redactable signatures, and unlinkable redactable signatures are presented. A redactable anonymous credential scheme is also constructed. All original protocols employ constant-sized secret keys rather than linear-sized (in the number of messages/attributes). Security properties of the new protocols are analysed and a general discussion of security properties for both PS signatures and the new schemes is provided.

Variant secret sharing schemes deriving from Shamir's threshold secret sharing protocol are presented. Results include multi-secret sharing protocols using shares with $O(1)$ elements, independent of the number of secrets. The new schemes achieve a weaker notion of security (they're secure rather than strongly secure) but maintain a property called $K$-privacy (inspired by $k$-anonymity). $K$-privacy ensures that all secrets remain private with respect to a subset of the secret space, though the particular subset providing privacy may vary among adversaries that acquire distinct sub-threshold sets of shares. Depending on the number of secrets and the protocol details, secure $K$-private multi-secret sharing schemes may be ``almost'' strongly secure or may remain merely secure and $K$-private - a difference captured by the notion of $K$-security. Novel applications of the multi-secret sharing schemes are presented, realising a primitive called a switched threshold signature. Switched threshold signatures have the quirky property that aggregating a threshold number of signatures of one type (e.g. Pointcheval-Sanders signatures) ``switches'' the signatures into a master signature of a different type. Collectively these results may permit efficiencies within, e.g., threshold credential issuance protocols.

The information ratio of an access structure is an important parameter for quantifying the efficiency of the best secret sharing scheme (SSS) realizing it. The most common security notion is perfect security. The following relaxations, in increasing level of security, have been presented in the literature: quasi-perfect, almost-perfect and statistical. Understanding the power of relaxing the correctness and privacy requirements in the efficiency of SSSs is a long-standing open problem. In this article, we introduce and study an extremely relaxed security notion, called partial security, for which it is only required that any qualified set gains strictly more information about the secret than any unqualified one. We refer to this gap as the nominal capacity. We quantify the efficiency of such schemes using a parameter called partial information ratio. It is defined to be the same as the (standard) information ratio, except that we divide the largest share entropy by nominal capacity instead of the secret entropy. Despite this modification, partial security turns out weaker than the weakest mentioned non-perfect security notion, i.e., quasi-perfect security. We present three main results in this paper. First, we prove that partial and perfect information ratios coincide for the class of linear SSSs. Consequently, for this class, information ratio is invariant with respect to all security notions. Second, by viewing a partial SSS as a wiretap channel, we prove that for the general (i.e., non-linear) class of SSSs, partial and statistical information ratios are equal. Consequently, for this class, information ratio is invariant with respect to all non-perfect security notions. Third, we show that partial and almost-perfect information ratios do not coincide for the class of mixed-linear schemes (i.e., schemes constructed by combining linear schemes with different underlying finite fields). Our first result strengthens the previous decomposition theorems for constructing perfect linear schemes. Our second result leads to a very strong decomposition theorem for constructing general (i.e., non-linear) statistical schemes. Our third result provides a rare example of the effect of imperfection on the efficiency of SSSs for a certain class of schemes.

New cryptographic techniques such as homomorphic encryption (HE) allow computations to be outsourced to and evaluated blindfolded in a resourceful cloud. These computations often require private data owned by multiple participants, engaging in joint evaluation of some functions. For example, Genome-Wide Association Study (GWAS) is becoming feasible because of recent proliferation of genome sequencing technology. Due to the sensitivity of genomic data, these data should be encrypted using different keys. However, supporting computation on ciphertexts encrypted under multiple keys is a non-trivial task. In this paper, we present a comprehensive survey on different state-of-the-art cryptographic techniques and schemes that are commonly used. We review techniques and schemes including Attribute-Based Encryption (ABE), Proxy Re-Encryption (PRE), Threshold Homomorphic Encryption (ThHE), and Multi-Key Homomorphic Encryption (MKHE). We analyze them based on different system and security models and examine their complexities. We share lessons learned and draw observations for designing better schemes with reduced overheads.

Empowering electronic devices to support Post-Quantum Cryptography (PQC) is a challenging task. PQC introduces new mathematical elements and operations which are usually not easy to implement on standard processors. Especially for low cost and resource constraint devices, hardware acceleration is usually required. In addition, as the standardization process of PQC is still ongoing, a focus on maintaining flexibility is mandatory. To cope with such requirements, hardware/software co-design techniques have been recently used for developing complex and highly customized PQC solutions. However, while most of the previous works have developed loosely coupled PQC accelerators, the design of tightly coupled accelerators and Instruction Set Architecture (ISA) extensions for PQC have been barely explored. To this end, we present RISQ-V, an enhanced RISC-V architecture that integrates a set of powerful tightly coupled accelerators to speed up lattice-based PQC. RISQ-V efficiently reuses processor resources and reduces the amount of memory accesses. This significantly increases the performance while keeping the silicon area overhead low. We present three contributions. First, we propose a set of powerful hardware accelerators deeply integrated into the RISC-V pipeline. Second, we extended the RISC-V ISA with 29 new instructions to efficiently perform operations for lattice-based cryptography. Third, we implemented our RISQ-V in ASIC technology and on FPGA. We evaluated the performance of NewHope, Kyber, and Saber on RISQ-V. Compared to the pure software implementation on RISC-V, our co-design implementations show a speedup factor of up to 11.4 for NewHope, 9.6 for Kyber, and 2.7 for Saber. For the ASIC implementation, the energy consumption was reduced by factors of up to 9.5 for NewHope, 7.7 for Kyber, and 2.1 for Saber. The cell count of the CPU was increased by a factor of 1.6 compared to the original RISC-V design, which can be considered as a moderate increase for the achieved performance gain.

We initiate a study of pseudorandom encodings: efficiently computable and decodable encoding functions that map messages from a given distribution to a random-looking distribution. For instance, every distribution that can be perfectly and efficiently compressed admits such a pseudorandom encoding. Pseudorandom encodings are motivated by a variety of cryptographic applications, including password-authenticated key exchange, ''honey encryption'' and steganography. The main question we ask is whether every efficiently samplable distribution admits a pseudorandom encoding. Under different cryptographic assumptions, we obtain positive and negative answers for different flavors of pseudorandom encodings, and relate this question to problems in other areas of cryptography. In particular, by establishing a two-way relation between pseudorandom encoding schemes and efficient invertible sampling algorithms, we reveal a connection between adaptively secure multiparty computation for randomized functionalities and questions in the domain of steganography.

This paper revisits the Abe--Okamoto signature scheme to present a version of their signature scheme augmented with modern best practices, with major influences taken from EdDSA. Implementation guidance is given on how to reuse existing Ed25519 code.

White-box cryptography attempts to protect cryptographic secrets in pure software implementations. Due to their high utility, white-box cryptosystems (WBC) are deployed by the industry even though the security of these constructions is not well defined. A major breakthrough in generic cryptanalysis of WBC was Differential Computation Analysis (DCA), which requires minimal knowledge of the underlying white-box protection and also thwarts many obfuscation methods. To avert DCA, classic masking countermeasures originally intended to protect against highly related side-channel attacks have been proposed for use in WBC. However, due to the controlled environment of WBCs, new algebraic attacks against classic masking schemes have quickly been found. These algebraic DCA attacks break all classic masking countermeasures efficiently, as they are independent of the masking order. In this work, we propose a novel generic masking scheme that can resist both DCA and algebraic DCA attacks. The proposed scheme extends the seminal work by Ishai et al. which is probing secure and thus resists DCA, to also resist algebraic attacks. To prove the security of our scheme, we demonstrate the connection between two main security notions in white-box cryptography: probing security and prediction security. Resistance of our masking scheme to DCA is proven for an arbitrary order of protection, using the well-known strong non-interference notion by Barthe et al. Our masking scheme also resists algebraic attacks, which we show concretely for first and second-order algebraic protection. Moreover, we present an extensive performance analysis and quantify the overhead of our scheme, for a proof-of-concept protection of an AES implementation.

Fine-grained cryptography is concerned with adversaries that are only moderately more powerful than the honest parties. We will survey recent results in this relatively underdeveloped area of study and examine whether the time is ripe for further advances in it.

A division property is a generic tool to search for integral distinguishers, and automatic tools such as MILP or SAT/SMT allow us to evaluate the propagation efficiently. In the application to stream ciphers, it enables us to estimate the security of cube attacks theoretically, and it leads to the best key-recovery attacks against well-known stream ciphers. However, it was reported that some of the key-recovery attacks based on the division property degenerate to distinguishing attacks due to the inaccuracy of the division property. Three-subset division property (without unknown subset) is a promising method to solve this inaccuracy problem, and a new algorithm using automatic tools for the three-subset division property was recently proposed at Asiacrypt2019. In this paper, we first show that this state-of-the-art algorithm is not always efficient and we cannot improve the existing key-recovery attacks. Then, we focus on the feature of the three-subset division property without unknown subset and propose another new efficient algorithm using automatic tools. Our algorithm is more efficient than existing algorithms, and it can improve existing key-recovery attacks. In the application to Trivium, we show an 842-round key-recovery attack. We also show that an 855-round key-recovery attack, which was proposed at CRYPTO2018, has a critical flaw and does not work. As a result, our 842-round attack becomes the best key-recovery attack. In the application to Grain-128AEAD, we show that the known 184-round key-recovery attack degenerates to distinguishing attacks. Then, the distinguishing attacks are improved up to 189 rounds, and we also show the best key-recovery attack against 190 rounds. In the application to ACORN, we prove that the 772-round key-recovery attack at ISC2019 is in fact a constant-sum distinguisher. We then give new key-recovery attacks mounting to 773- and 774-round ACORN. We also verify the current best key-recovery attack on 892-round Kreyvium and recover the exact superpoly.

The fundamental problem in lattice-based cryptography is the hardness of the Ring-LWE, which has been based on the conjectured hardness of approximating ideal-SIVP or ideal-SVP. Though it is now widely conjectured both are hard in classical and quantum computation model” there is no sufficient attacks proposed and considered. In this paper we propose the subset quadruple attack on general structured LWE problems over any ring endowed with a positive definite inner product and an error distribution. Hence from the view of subset quadruple attacks, the error distributions of feasible non-negligible subset quadruples should be calculated to test the hardness. Sublattice pair with an ideal attack is a special case of subset quadruple attack. A lower bound for the Gaussian error distribution is proved to construct suitable feasible non-negligible sublattices. From the sublattice pair with an ideal attack we prove that the decision Poly-LWE over ${\bf Z}[x]/(x^n-p_n)$ with certain special inner products and arbitrary polynomially bounded widths of Gaussian error distributions can be solved with the polynomial time for the sufficiently large polynomially bounded modulus parameters $p_n$.\\ Keywords: Poly-LWE, Ring-LWE, Wide Error distribution, Subset quadruple attack, Sublattice pair with an ideal.

In this paper, we consider the structure of isogeny graphs in SIDH, that is an isogeny-based key-exchange protocol. SIDH is the underlying protocol of SIKE, which is one of the candidates for NIST post quantum cryptography standardization. Since the security of SIDH is based on the hardness of the path-finding problem in isogeny graphs, it is important to study those structure. The existence of cycles in isogeny graph is related to the path-finding problem, so we investigate cycles in the graphs used in SIKE. In particular, we focus on SIKEp434 and SIKEp503, which are the parameter sets of SIKE claimed to satisfy the NIST security level 1 and 2, respectively. We show that there are two cycles in the 3-isogeny graph in SIKEp434, and there is no cycles in the other graphs in SIKEp434 and SIKEp503.

We continue the study of Mastrovito form of Karatsuba multipliers under the shifted polynomial basis (SPB), recently introduced by Li et al. (IEEE TC (2017)). A Mastrovito-Karatsuba (MK) multiplier utilizes the Karatsuba algorithm (KA) to optimize polynomial multiplication and the Mastrovito approach to combine it with the modular reduction. The authors developed a MK multiplier for all trinomials, which obtain a better space and time trade-off compared with previous non-recursive Karatsuba counterparts. Based on this work, we make two types of contributions in our paper. FORMULATION. We derive a new modular reduction formulation for constructing Mastrovito matrix associated with Type II pentanomial. This formula can also be applied to other special type of pentanomials, e.g. Type I pentanomial and Type C.1 pentanomial. Through related formulations, we demonstrate that Type I pentanomial is less efficient than Type II one because of a more complicated modular reduction under the same SPB; conversely, Type C.1 pentanomial is as good as Type II pentanomial under an alternative generalized polynomial basis (GPB). EXTENSION. We introduce a new MK multiplier for Type II pentanomial. It is shown that our proposal is only one $T_X$ slower than the fastest bit-parallel multipliers for Type II pentanomial, but its space complexity is roughly 3/4 of those schemes, where $T_X$ is the delay of one 2-input XOR gate. To the best of our knowledge, it is the first time for hybrid multiplier to achieve such a time delay bound.

The Montgomery ladder and Joye ladder are well-known algorithms for elliptic curve scalar multiplication with a regular structure. The Montgomery ladder is best known for its implementation on Montgomery curves, which requires $5\mathbf{M} + 4\mathbf{S} + 1\mathbf{m} + 8\mathbf{A}$ per scalar bit, and 6 field registers. Here $(\mathbf{M},\mathbf{S},\mathbf{m},\mathbf{A})$ represent respectively field $\mathbf{M}$ultiplications, $\mathbf{S}$quarings, $\mathbf{m}$ultiplications by a curve constant, and $\mathbf{A}$dditions or subtractions. This ladder is also complete, meaning that it works on all input points and all scalars. Many protocols do not use Montgomery curves, but instead use prime-order curves in short Weierstrass form. These have historically been much slower, with ladders costing at least 14 multiplications or squarings per bit: $8\mathbf{M}+6\mathbf{S}+27\mathbf{A}$ for the Montgomery ladder and $8\mathbf{M}+6\mathbf{S}+30\mathbf{A}$ for the Joye ladder. In 2017, Kim et al. improved the Montgomery ladder to $8\mathbf{M}+4\mathbf{S}+12\mathbf{A}+1\mathbf{H}$ per bit using 9 registers, where the $\mathbf{H}$ represents a halving. Hamburg simplified Kim et al.'s formulas to $8\mathbf{M}+4\mathbf{S}+8\mathbf{A}+1\mathbf{H}$ per bit using 6 registers. Here we present improved formulas which compute the Montgomery ladder on short Weierstrass curves using $8\mathbf{M}+3\mathbf{S}+7\mathbf{A}$ per bit, and requiring 6 registers. We also give formulas for the Joye ladder that use $9\mathbf{M}+3\mathbf{S}+7\mathbf{A}$ per bit, requiring 5 registers. One of our new formulas supports very efficient 4-way vectorization. We also discuss curve invariants, exceptional points, side-channel protection and how to set up and finish these ladder operations. Finally, we show a novel technique to make these ladders complete when the curve order is not divisible by 2 or 3, at a modest increase in cost. A sample implementation of these techniques is given in the supplementary material, also posted at https://github.com/bitwiseshiftleft/ladder_formulas.

Deep Learning based Side-Channel Attacks (DL-SCA) are an emerging security assessment method increasingly being adopted by the majority of certification schemes and certification bodies to assess the resistance of cryptographic implementations. The related published investigations have demonstrated that DL-SCA are very efficient when targeting cryptographic designs protected with the common side-channel countermeasures. Furthermore, these attacks allow to streamline the evaluation process as the pre-processing of the traces (\emph{e.g.} alignment, dimensionality reduction, \dots) is no longer mandatory. In practice, the DL-SCA are applied following the divide-and-conquer strategy such that the target, for the training and the attack phases, only depends on $8$ key bits at most (to avoid high time complexity especially during the training). Then, the same process is repeated to recover the remaining bits of the key. To mitigate this practical issue, we propose in this work a new profiling methodology for DL-SCA based on the so-called multi-label classification. We argue that our new profiling methodology allows applying DL-SCA to target a bigger chunk of the key (typically $16$ bits) without introducing a learning time overhead and while guaranteeing a similar attack efficiency compared to the commonly used training strategy. As a side benefit, we demonstrate that our leaning strategy can be applied as well to train several intermediate operations at once. Interestingly, we show that, in this context, our methodology is even faster than the classical training and leads to a more efficient key recovery phase. We validated the soundness of our proposal on simulated traces and experimental data-sets; amongst them, some are publicly available side-channel databases. The obtained results have proven that our profiling methodology is of great practical interest especially in the context of performing penetration tests with high attack potential (\emph{e.g.} Common Criteria, EMVCO) where the time required to perform the attack has an impact on its final rating.

This paper presents WAGE, a new lightweight sponge-based authenticated cipher whose underlying permutation is based on a 37-stage Galois NLFSR over $\mathbb{F}_{2^7}$. At its core, the round function of the permutation consists of the well-analyzed Welch-Gong permutation (WGP), primitive feedback polynomial, a newly designed 7-bit SB sbox and partial word-wise XORs. The construction of the permutation is carried out such that the design of individual components is highly coupled with cryptanalysis and hardware efficiency. As such, we analyze the security of WAGE against differential, linear, algebraic and meet/miss-in-the-middle attacks. For 128-bit authenticated encryption security, WAGE achieves a throughput of 535 Mbps with hardware area of 2540 GE in ASIC ST Micro 90 nm standard cell library. Additionally, WAGE is designed with a twist where its underlying permutation can be efficiently turned into a pseudorandom bit generator based on the WG transformation (WG-PRBG) whose output bits have theoretically proved randomness properties.

In this paper, we present an instruction set coprocessor architecture for lattice-based cryptography and implement the module lattice-based post-quantum key encapsulation mechanism (KEM) Saber as a case study. To achieve fast computation time, the architecture is fully implemented in hardware, including CCA transformations. Since polynomial multiplication plays a performance-critical role in the module and ideal lattice-based public-key cryptography, a parallel polynomial multiplier architecture is proposed that overcomes memory access bottlenecks and results in a highly parallel yet simple and easy-to-scale design. Such multipliers can compute a full multiplication in $256$ cycles, but are designed to target any area/performance trade-offs. Besides optimizing polynomial multiplication, we make important design decisions and perform architectural optimizations to reduce the overall cycle counts as well as improve resource utilization. For the module dimension 3 (security comparable to AES-192), the coprocessor computes CCA key generation, encapsulation, and decapsulation in only 5,453, 6,618 and 8,034 cycles respectively, making it the fastest hardware implementation of Saber to our knowledge. On a Xilinx UltraScale+ XCZU9EG-2FFVB1156 FPGA, the entire instruction set coprocessor architecture runs at 250 MHz clock frequency and consumes 23,686 LUTs, 9,805 FFs, and 2 BRAM tiles (including 5,113 LUTs and 3,068 FFs for the Keccak core).

We facilitate trusted cross-blockchain state proofs by implementing a chain-relay that validates block headers from proof-of-work blockchains. While current approaches require proof sizes linear to the amount of blocks the state was built on, trusted intermediaries, or economic assumptions, we propose the utilization of off-chain computations through zkSNARKs to provide a cryptographically secure and highly scalable sidechain mechanism. Multiple block headers are included in batches and verified off-chain, while preserving light client support. Only the validity of the off-chain computation is verified on-chain, creating a sidechain mechanism that requires constant verification costs and releases the target ledger from processing and storing every single block header of the source blockchain. We provide a prototypical implementation that facilitates the verification of 504 Bitcoin headers in a single proof on Ethereum using the ZoKrates framework. Hereby, the verification costs are reduced by a factor of 187 compared to current approaches such as BTC Relay.

At EUROCRYPT 2004, Naccache et al. showed that the projective coordinates representation of the resulting point of an elliptic curve scalar multiplication potentially allows to recover some bits of the scalar. However, this attack has received little attention by the scientific community, and the status of deployed mitigations to prevent it in widely adopted cryptography libraries is unknown. In this paper, we aim to fill this gap, by analyzing several cryptography libraries in this context. To demonstrate the applicability of the attack, we use a side-channel attack to exploit this vulnerability within libgcrypt in the context of ECDSA. To the best of our knowledge, this is the first practical attack instance. It targets the insecure binary extended Euclidean algorithm implementation using a microarchitectural side-channel attack that allows recovering the projective representation of the output point of scalar multiplication during ECDSA signature generation. We captured 100k traces to estimate the number of traces an attacker would need to compromise the libgcrypt ECDSA implementation, resulting in less than 2k for commonly used elliptic curve secp256r1, demonstrating the attack feasibility. During exploitation, we found two additional vulnerabilities. However, we remark the purpose of this paper is not merely exploiting a library but about providing an analysis on the projective coordinates vulnerability status in widely deployed open-source libraries, filling a gap between its original description in the academic literature and the adoption of countermeasures to thwart it in real-world applications.

The optimization of the main key compression bottlenecks of the supersingular isogeny key encapsulation mechanism (SIKE) has been a target of research in the last few years. Significant improvements were introduced in the recent works of Costello et al. and Zanon et al. The combination of the techniques in previous works reduced the running time of binary torsion basis generation in decompression by a factor of 29 compared to previous work. On the other hand, generating such a basis still takes almost a million cycles on an Intel Core i5-6267U Skylake. In this paper, we continue the work of Zanon et al. and introduce a technique that drops the complexity of binary torsion basis generation by a factor log p in the number of underlying field multiplications. In particular, our experimental results show that a basis can be generated in about 1,300 cycles, attaining an improvement by a factor more than 600. Although this result eliminates one of the key compression bottlenecks, many other bottlenecks remain. In addition, we give further improvements for the ternary torsion generation with significant impact on the related decompression procedure. Moreover, a new trade-off between ciphertext sizes vs decapsulation speed and storage is introduced and achieves a 1.7 times faster decapsulation.

The one-out-of-many proof is a cryptographic zero-knowledge construction enabling the prover to demonstrate knowledge of a secret element among the given public list of cryptographic commitments opening to zero. This method is relying on standard Decisional Diffie-Hellman security assumptions and can result in efficient accountable ring signature schemes [4] and proofs of set memberships [5] with a signature size smaller than all existing alternative schemes relying on standard assumptions. This construction also serves as a fundamental building block for numerous recent blockchain privacy protocols including Anonymous Zether, Zerocoin, Lelantus, Lelantus-MW, Triptych and Triptych-2. One-out-of-many proofs require O(logN)-sized communication and can be implemented in O(N) time for the verifier and O(NlogN) time for the prover. In this work, we introduce a new method of instantiating one-out-of-many proofs which reduces the proof generation time by an order of magnitude. In certain practical applications our method also helps to fasten the verification process of multiple simultaneously generated proofs. Our approach still results in shorter proofs comprised of only a logarithmic number of commitments and does not compromise the highly efficient batch verification properties endemic to the original construction. We believe this work can also foster further research towards building more efficient one-out-of-many proofs which are extremely useful constructions in the blockchain privacy space and beyond.

Mathematics and cryptography have a long history together, with the ups and downs inherent in any long relationship. Whether it is a marriage of convenience or a love match, their progeny have lives of their own and have had an impact on the world. This invited lecture will briefly recall some high points from the past, give speculation and encouragement for the future of this marriage, and give counseling on how to improve communication, resolve conflicts, and play well together, based on personal experience and lessons learned.

In a joint effort to fight the COVID-19 pandemic, Apple Inc. and Google Inc. recently partnered to develop a contact tracing technology, inspired by the DP-3T and TCN protocols, to help governments and health agencies reduce the spread of the virus, with user privacy and security central to the design. The partnership announcement included technical specifications of the planned technology, which has great potential for widespread adoption due to the global reach of the two companies. At the same time, the anonymous distributed setting for contact tracing as well as other aspects of the specifications create opportunities for attackers to mount common attacks on the technology. In this work, we provide a security analysis of these specifications, the initial version of which was communicated early on to Apple Inc. in April this year, soon after announcement of the specifications. We show that the current specifications may introduce significant risks to society due to the common attacks and propose novel mitigation strategies for these risks that do not require major changes to the technology and are easy to adopt. To the best of our knowledge, ours is the first contact tracing proposal to mitigate the risks of all these common attacks in the anonymous distributed setting without introducing architectural changes. Our analysis focuses mostly on system security considerations, which have not been well covered previously, yet also includes novel information security considerations. We leave out of scope a discussion on how important or effective the technology is in fighting the pandemic.

Picnic is a digital signature algorithm designed to provide security against attacks by quantum computers. The design uses only symmetric-key primitives, and is an efficient instantiation of the MPC-in-the-head paradigm. In this work, we explore the Picnic design in great detail. We investigate and benchmark different parameter choices and show that there exist better parameter choices than those in the current specification. We also present improvements to the MPC protocol that shorten signatures and reduce signing time. The proposed MPC changes tailor the protocol to the circuit of interest in Picnic, but may also be of independent interest. Taken together, these changes give a new instantiation of Picnic that signs messages 7.9 to 13.9 times faster, and verifies signatures 4.5 to 5.5 times faster than the existing ``Picnic2'' design, while having nearly the same signature sizes.

The COVID-19 pandemic has posed a unique challenge for the world to find solutions, ranging from vaccines to ICT solutions to slow down the virus spreading. Due to the highly contagious nature of the virus, social distancing is one fundamental measure which has already adopted by many countries. At the technical level, this prioritises contact tracing solutions, which can alert the users who have been in close contact with the infected persons and meanwhile allow heath authorities to take proper actions. In this paper, we examine several existing privacy-aware contact tracing solutions and analyse their (dis)advantages. At the end, we describe several major observations and outline an interdisciplinary research agenda towards more comprehensive and effective privacy-aware contact tracing solutions.

In this work we present a duplex-based authenticated encryption scheme Friet based on a new permutation called Friet-P. We designed Friet-P with a novel approach for cryptographic permutations and block ciphers that takes fault-attack resistance into account and that we introduce in this paper. In this method, we build a permutation $f_C$ to be embedded in a larger one, $f$ . First, we define $f$ as a sequence of steps that all abide a chosen error-correcting code $C$, i.e., that map $C$-codewords to $C$-codewords. Then, we embed $f_C$ in $f$ by first encoding its input to an element of $C$, applying $f$ and then decoding back from $C$. This last step detects a fault when the output of $f$ is not in $C$. We motivate the design of the permutation we use in Friet and report on performance in soft- and hardware. We evaluate the fault-detection capabilities of the software and simulated hardware implementations with attacks. Finally, we perform a leakage evaluation. Our code is available at https://github.com/thisimon/Friet.git.

The golden collision problem asks us to find a single, special collision among the outputs of a pseudorandom function. This generalizes meet-in-the-middle problems, and is thus applicable in many contexts, such as cryptanalysis of the NIST post-quantum candidate SIKE. The main quantum algorithms for this problem are memory-intensive, and the costs of quantum memory may be very high. The quantum circuit model implies a linear cost for random access, which annihilates the exponential advantage of the previous quantum collision-finding algorithms over Grover's algorithm or classical van Oorschot-Wiener. Assuming that quantum memory is costly to access but free to maintain, we provide new quantum algorithms for the golden collision problem with high memory requirements but low gate costs. Under the assumption of a two-dimensional connectivity layout, we provide better quantum parallelization methods for generic and golden collision finding. This lowers the quantum security of the golden collision and meet-in-the-middle problems, including SIKE.

We prove that the equivalence of two fundamental problems in the theory of computing. For every polynomial $t(n)\geq (1+\varepsilon)n, \varepsilon>0$, the following are equivalent: - One-way functions exists (which in turn is equivalent to the existence of secure private-key encryption schemes, digital signatures, pseudorandom generators, pseudorandom functions, commitment schemes, and more); - $t$-time bounded Kolmogorov Complexity, $K^t$, is mildly hard-on-average (i.e., there exists a polynomial $p(n)>0$ such that no $\PPT$ algorithm can compute $K^t$, for more than a $1-\frac{1}{p(n)}$ fraction of $n$-bit strings). In doing so, we present the first natural, and well-studied, computational problem characterizing the feasibility of the central private-key primitives and protocols in Cryptography.

Pattern matching is one of the most fundamental and important paradigms in several application domains such as digital forensics, cyber threat intelligence, or genomic and medical data analysis. While it is a straightforward operation when performed on plaintext data, it becomes a challenging task when the privacy of both the analyzed data and the analysis patterns must be preserved. In this paper, we propose new provably correct, secure, and relatively efficient (compared to similar existing schemes) public and private key based constructions that allow arbitrary pattern matching over encrypted data while protecting both the data to be analyzed and the patterns to be matched. That is, except the pattern provider (resp. the data owner), all other involved parties in the proposed constructions will learn nothing about the patterns to be searched (resp. the data to be inspected). Compared to existing solutions, the constructions we propose has some interesting properties: (1) the size of the ciphertext is linear to the size of plaintext and independent of the sizes and the number of the analysis patterns; (2) the sizes of the issued trapdoors are constant on the size of the data to be analyzed; and (3) the search complexity is linear on the size of the data to be inspected and is constant on the sizes of the analysis patterns. The conducted evaluations show that our constructions drastically improve the performance of the most efficient state of the art solution.

Blockchain Sharding is a blockchain performance enhancement approach. By splitting a blockchain into several parallel-run committees (shards), it helps increase transaction throughput, reduce resources required, and increase reward expectation for participants. Recently, several flexible sharding methods that can tolerate up to $n/2$ Byzantine nodes ($n/2$ security level) have been proposed. However, these methods suffer from two main drawbacks. First, in a non-sharding blockchain, nodes can have different weight (power or stake) to create a consensus. So an adversary needs to control half of the overall weight of the system in order for a piece of faulty information to be accepted into the blockchain ($p/2$ security level). In blockchain sharding, all nodes carry the same weight. Thus, it is only under the assumption that the honest participants are creating as many nodes as they can that a $n/2$ security level blockchain sharding reaches the $p/2$ security level. Secondly, when some nodes leave the system, other nodes need to be reassigned, frequently, from shard to shard in order to maintain the security level of the system. In this paper, we present Multichain MWPoW, a $p/2$ security level blockchain sharding architecture that does not require honest participants to create multiple nodes and requires less node reassignment when some nodes leave the system. It combines the Multiple Winners Proof of Work consensus protocol (MWPoW) with the flexibility of $n/2$ blockchain sharding. Our experiments show that Multichain MWPoW outperforms existing blockchain sharding approaches in terms of security, transaction throughput and flexibility.