International Association
for Cryptologic Research

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.

When designing a classical substitution-permutation network (SPN) permutation, every non-trivial choice of the S-box and of the affine layer provides security after a finite number of rounds. However, this is not necessarily the case for partial SPN (P-SPN) ciphers: Since the nonlinear part does not cover the full state, there may exist highly non-trivial choices of linear layers which, for example, do not provide security against statistical attacks.

Quite surprisingly, this direction has hardly been considered in the literature. For example, LowMC uses different linear layers in each round in order to avoid the problem, but this solution is quite expensive, both computationally and memory-wise. Zorro, another construction with an incomplete nonlinear layer, simply reuses the AES matrix, but this introduces weaknesses.

Working from an attacker's perspective and focusing on P-SPN ciphers, in this paper we present conditions which allow to set up attacks based on infinitely long invariant subspace trails -- even when using highly non-trivial linear layers. We also analyze the case in which the trail is not invariant, yet still an infinite number of rounds can be covered. In this paper, we consider two scenarios, namely active and inactive S-boxes. For the first case, we also provide a tool which is able to determine whether a given linear layer matrix is vulnerable against attacks based on our observations.

Finally, we point out that besides P-SPN ciphers, our results may also have a crucial impact on the HADES design strategy recently presented at Eurocrypt 2020, which mixes rounds with full S-box layers and rounds with partial S-box layers in order to guarantee security and achieve good performance in the target applications.

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 how a modified recursive composition may be applied to a particular SNARK construction which does not have a sublinear-time verifier. However, they omit details about this method and do not prove that it satisfies any security property. Nonetheless, schemes based on this idea have already been implemented in software.

In this work we present a collection of results that establish the theoretical foundations for a significant 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.

Collusion-free (CF) and collusion-preserving (CP) protocols offer alternatives to standard multi-party computation (MPC) in settings where subliminal communication is undesirable, e.g., in decentralizing mediators in mediated games. However, all existing solutions make too strong and uninstantiable assumptions on the setups, such as physical presence of the parties, access to physical envelopes and opaque ballot boxes, or extreme isolation, where the only means of communication is a star-topology network among the parties with a special resource, the mediator, at its center---and the mediator needs to be aware of the function to be computed. 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 application scenarios.

In this work we provide the first solution to collusion preserving computation which uses weaker and more common assumptions than the above, i.e., an authenticated broadcast functionality and access to honestly generated trusted hardware tokens. We prove that our protocol is collusion-preserving secure (in short, CP secure) as long as no parties abort. In the case of an aborting adversary our protocol loses CP security, but still achieves standard security---against monolithic adversaries---and additionally identifies a corrupted party.

Leveraging the above identifiability property, we augment our protocol with a collateral and compensation mechanism which ensures that it is not profitable to abort, thereby obtaining CP security against incentive driven adversaries. To define (and prove) this latter result, we combine the Rational Protocol Design (RPD) methodology by Garay et al. [FOCS 2013] with the CP framework of Alwen 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 protocols in the CP/CF literature, our protocols preserve, as a fallback, the traditional security properties---i.e., security against monolithic adversaries---even when the setup (i.e., the hardware tokens) is compromised or corrupted.

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. In such cases governments are more legitimate to adopt exceptional measures that limit civil rights, usually receiving large support from their citizens.

The COVID-19 pandemic is currently affecting the freedom and life style 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 the privacy of their citizens as part of 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, PACT and the Apple&Google exposure notification system that through a decentralized approach 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 systems. We focus in particular on the DP-3T system (still our analysis is significant also for PACT and Apple&Google systems) that has been endorsed by Apple&Google. The endorsement has the impact of integrating in the forthcoming update of Android and iOS special features like a synchronous rotation of the BLE MAC address of the smartphone with the update of the pseudonyms of the DP-3T system.

Based on recent literature and new findings, we discuss how a government can exploit the use of DP-3T to successfully mount privacy attacks as part of a mass surveillance program.

Interestingly, we also show that the privacy issues in DP-3T are not intrinsic in any BLE-based contact tracing system. Indeed, we propose a different system named $\textsf{Pronto-C2}$ that, in our view, enjoys a much better resilience with respect to mass surveillance attacks still relying on BLE. $\textsf{Pronto-C2}$ is based on a paradigm shift: instead of asking smartphones to send keys to the Big Brother (this corresponds to the approach of DP-3T), we construct a decentralized BLE-based ACT system where smartphones anonymously and confidentially talk to each other in the presence of the Big Brother.

$\textsf{Pronto-C2}$ 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 very useful to defeat COVID-19, and our proposal goes straight in this direction.

Building on the protocol of Gennaro and Goldfeder (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 the first 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 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 utilisation. 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 paper we throw light on some of the issues and challenges pertaining to the adaption of mobile contact tracing for fighting COVID-19. In essence we proposed an Evaluation framework for mobile contact tracing solutions to determine their feasibility and effectiveness. We evaluate some of the available contact tracing solutions in light of our proposed framework. Furthermore we presented possible attacks that could be launched against contact tracing solutions with 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.