International Association
for Cryptologic Research

Despite the fundamental importance of delay functions, repeated squaring in RSA groups (Rivest, Shamir and Wagner '96) is the only candidate offering both a useful structure and a realistic level of practicality. Somewhat unsatisfyingly, its sequentiality is provided directly by assumption (i.e., the function is assumed to be a delay function).

We prove sharp thresholds on the sequentiality of all generic-ring delay functions relative to an RSA modulus based on the hardness of factoring in the standard model. In particular, we show that generically speeding-up repeated squaring (even with a preprocessing stage and any polynomial number parallel processors) is equivalent to factoring.

More generally, based on the (essential) hardness of factoring, we prove that any generic-ring function is in fact a delay function, admitting a sharp sequentiality threshold that is determined by our notion of sequentiality depth. Moreover, we show that generic-ring functions admit not only sharp sequentiality thresholds, but also sharp pseudorandomness thresholds.

Due to its simplicity, succinctness, and performance, Groth16 is currently the most widely deployed succinct (zero-knowledge) argument of knowledge (SNARK) system. Groth16 is known to be perfectly zero-knowledge and knowledge sound in the generic (and algebraic) group model. However, the existing security arguments for Groth16 are silent about the soundness of the proof system in the presence of simulated proofs --- a common requirement for both the composable security and game-hopping style security analysis of protocols built using such argument systems. This important gap let to a line of work on simulation-extractable, also called simulation knowledge sound, succinct proof systems. Groth16 itself cannot satisfy the strongest notion of simulation-extractability that implies proof non-malleability --- in fact, proofs are perfectly randomizable. Surprisingly, in this short note we show that Groth16 does satisfy a weaker notion of simulation-extractability implying statement non-malleability. This property is often sufficient for typical applications that motivate the use of strong simulation-extractability. Notably, one can obtain UC security using efficient compilers.

A novel Nakamoto-like consensus was proposed by Tang et al. (ACISP 2019) to speed up the convergence (block finality) rate by determining a weight of a block in the blockchain by a tunable potential function of the block hash. However, the convergence of the scheme was evaluated only in an experimental way and a sudden utilization of another blockchain was not clearly explained. This article asymptotically analyses the convergence of Nakamoto-like consensus of Tang et al. by proposing a general framework for formalizing consensus schemes comprising both the classical Nakamoto consensus (bitcoin consensus) and the consensus of Tang et al. The framework contains two categories of schemes, namely, small-step consensus like the bitcoin consensus and giant-step consensus of Tang et al. Furthermore, the essence of the second chain, the even-trigger, is shown to be a necessity of realizing giant-step consensus.

We revisit the definition of efficient algorithms and argue, that the standard runtime classes, strict probabilistic polynomial time (PPT) and expected probabilistic polynomial time (EPT) are “unnatural” from a cryptographic perspective. They are not closed under indistinguishability. Applied to EPT, this suggests computationally expected polynomial time (CEPT), the class of runtimes which are (computationally) indistinguishable from EPT. We analyse the behaviour of CEPT for zero-knowledge proofs and designated adversaries in the setting of uniform complexity (following Goldreich (JC’93)). A designated adversary is (only) efficient in the protocol it is designed to attack. This security notion, first proposed in Feige’s thesis [Fei90], is very natural, but there are obstructions to achieving it. Prior work on handling (designated) EPT adversaries by Katz and Lindell (TCC’05) requires superpolynomial hardness assumptions, whereas the work of Goldreich (TCC’07) requires “nice” adversarial behaviour under rewinding. We provide easy-to-check criteria for zero-knowledge protocols with black-box simulation in the plain model, which show that many (all known?) such protocols handle designated CEPT adversaries in CEPT.

In this report, we analyze the security of the trust establishment protocol used in the Olvid messaging protocol. The latter relies on the PV-SAS-MCA message cross-authentication protocol by Pasini an Vaudenay based on short authenticated strings (SAS). In order to make the implementation portable across different platforms, Olvid proposed particular instantiations of the underlying primitives used in PV-SAS-MCA in addition to some other minor modifications. Here, we show that these changes have no impact on the security of the scheme. More precisely, we formally prove that the trust establishment protocol used in Olvid is a secure message cross-authentication protocol. The proof of security is in the random-oracle model and relies on the security of the underlying pseudorandom generator. It also assumes users know each other and have an authentic channel between them.

Data-oblivious algorithms are a key component of many secure computation protocols.

In this work, we show that advances in secure multiparty shuffling algorithms can be used to increase the efficiency of several key cryptographic tools.

The key observation is that many secure computation protocols rely heavily on secure shuffles. The best data-oblivious shuffling algorithms require $O(n \log n)$, operations, but in the two-party or multiparty setting, secure shuffling can be achieved with only $O(n)$ communication.

Leveraging the efficiency of secure multiparty shuffling, we give novel algorithms that improve the efficiency of securely sorting sparse lists, secure stable compaction, and securely merging two sorted lists.

Securely sorting private lists is a key component of many larger secure computation protocols. The best data-oblivious sorting algorithms for sorting a list of $n$ elements require $O(n \log n)$ comparisons. Using black-box access to a linear-communication secure shuffle, we give a secure algorithm for sorting a list of length $n$ with $t \ll n$ nonzero elements with communication $O(t \log^2 n + n)$, which beats the best oblivious algorithms when the number of nonzero elements, $t$, satisfies $t < n/\log^2 n$.

Secure compaction is the problem of removing dummy elements from a list, and is essentially equivalent to sorting on 1-bit keys. The best oblivious compaction algorithms run in $O(n)$-time, but they are unstable, i.e., the order of the remaining elements is not preserved. Using black-box access to a linear-communication secure shuffle, we give a stable compaction algorithm with only $O(n)$ communication.

Our main result is a novel secure merge protocol. The best previous algorithms for securely merging two sorted lists into a sorted whole required $O(n \log n)$ secure operations. Using black-box access to an $O(n)$-communication secure shuffle, we give the first secure merge algorithm that requires only $O(n \log \log n)$ communication. Our algorithm takes as input $n$ secret-shared values, and outputs a secret-sharing of the sorted list.

All our algorithms are generic, i.e., they can be implemented using generic secure computations techniques and make black-box access to a secure shuffle.

Our techniques extend naturally to the multiparty situation (with a constant number of parties) as well as to handle malicious adversaries without changing the asymptotic efficiency.

These algorithm have applications to securely computing database joins and order statistics on private data as well as multiparty Oblivious RAM protocols.

As a popular paradigm, crowd-sensing network emerges to achieve sensory data collection and task allocation to mobile users. On one hand these sensory data could be private and sensitive, and on the other hand, data transmission separately could incur heavy communication overhead. Fortunately, the technique of homomorphic encryption (HE) allows the addictive and/or multiplicative operations over the encrypted data as well as privacy protection. Therefore, several data aggregation schemes based on HE are proposed for crowd-sensing network. However, most of the existing schemes do not support ciphertext comparison efficiently, thus data center cannot process ciphertexts with flexibility. To address this challenge, we propose a comparable homomorphic encryption (CompHE) scheme based on Lagrange’s interpolation theorem, which enables ciphertext comparison between multiple users in crowdsensing network. Based on the Partial Discrete Logarithm and Decisional Diffie-Hellman assumption, the proposed CompHE scheme is provably secure in the random oracle model. Performance analysis confirms that the proposed scheme have improved the computational efficiency compared with existing schemes.

FPGAs offer many-fold acceleration to various application domains, and have become a part of cloud-based computation. However, their cloud-use introduce Cloud Service Provider (CSP) as trusted parties, who can access the hardware designs in plaintext. Therefore, the intellectual property of hardware designers is not protected against a dishonest cloud. In this paper, we propose a scheme for the confidentiality of accelerators on cloud, without limiting CSP to maintain their resources freely. Our proposed scheme is based on Proxy Re-Encryption which allows the developers to upload their accelerators to the CSPs under encryption. The CSPs cannot decrypt them; however, alter the encryption that allows the target FPGAs they pick to decrypt. In addition, our scheme allows metering the use of accelerators.

Low energy consumption is an important factor in today's technologies as many devices run on a battery and there are new applications which require long runtimes with very small batteries. As many of these devices are connected to some kind of network, they require encryption/decryption to securely transmit data. Hence, the energy consumption of the cipher is an important factor for the battery life. We evaluate the energy consumption of lightweight ciphers implemented on a custom 65nm ASIC. Since the energies to measure are very small, we first introduce, compare and evaluate two techniques to precisely measure the energy consumption of a real cryptographic core. In our comparative investigations, using the PRINCE block cipher we examine the effect of the design architecture (round-based versus unrolled) on the amount of energy consumption. In addition to considering other effects (like fixed key versus random key), we compare round-based implementations of different block ciphers (PRINCE, MIDORI and SKINNY) under similar settings providing first such practical investigations.

Deterministic ECC-based signatures including deterministic ECDSA and EdDSA are becoming popular to be applied to blockchain and Internet of Things. Their security has received a considerable attention, and there have existed some differential fault attacks against them. However, the attacks have some problems such as high computational complexity and strict requirement of fault injection. In this paper eight efficient lattice-based fault attacks(and one differential fault attack) against deterministic ECDSA and two ones against EdDSA are proposed. All the fault models of such attacks are the random storage faults of intermediate values during signature, by which some faulty and one correct signatures are obtained to construct the models of lattice attacks(or the equations with two unknown) and thereby recover the private key.

Unlike the previous differential fault attacks based on storage faults, our attacks do not need to guess the number and location of the faulty bits, and are still effective while the previous attacks are computationally infeasible. Moreover, compared with the previous lattice-based fault attacks against the non-deterministic signatures with random nonces, our attacks have more fault models besides the faulty nonce k, and only need random fault injection. We demonstrate the effectiveness of the attacks by simulations, which shows our attacks pose real threats to deterministic signature. The upper bound of the number of the faulty bits is just slightly less than the key length. We also discuss the corresponding countermeasures against our attacks.

Recently, in Asiacrypt 2019, Bonnetain et. al have shown attacks by quantum adversaries on FX construction and Even-Mansour Cipher without using superposition queries to the encryption oracle. In this work, we use a similar approach to mount new attacks on HCTR and HCH construction. In addition, we mount attacks on HCTR, Tweakable-HCTR and HCH using the superposition queries to the encryption oracle using strategies proposed by Leander and May in Asiacrypt 2017 and Kaplan et. al in Crypto 2016.

Recently, a new code based signature scheme, called LESS, was proposed with three concrete instantiations, each aiming to provide 128 bits of classical security. Two instantiations (LESS-I and LESS-II) are based on the conjectured hardness of the linear code equivalence problem, while a third instantiation, LESS-III, is based on the conjectured hardness of the permutation code equivalence problem for weakly self-dual codes. We give an improved algorithm for solving both these problems over sufficiently large finite fields. Our implementation breaks LESS-I and LESS-III in approximately 45 seconds and 2 seconds respectively on a laptop. Since the field size for LESS-II is relatively small $(\mathbb{F}_7)$ our algorithm does not improve on existing methods. Nonetheless, we estimate that LESS-II can be broken with approximately $2^{44}$ row operations.

Aiming to strengthen classical secret-sharing to make it a more directly useful primitive for human end-users, we develop definitions, theorems, and efficient constructions for what we call "adept" secret-sharing. Our primary concerns are the properties we call "privacy", "authenticity", and "error correction". Privacy strengthens the classical requirement by ensuring maximal confidentiality even if the dealer does not employ fresh, uniformly random coins with each sharing. That might happen either intentionally--to enable reproducible secret-sharing--or unintentionally, when an entropy source fails. Authenticity is a shareholder's guarantee that a secret recovered using his or her share will coincide with the value the dealer committed to at the time the secret was shared. Error correction is the guarantee that recovery of a secret will succeed, also identifying the valid shares, exactly when there is a unique explanation as to which shares implicate what secret. These concerns arise organically from a desire to create general-purpose libraries and apps for secret sharing that can withstand both strong adversaries and routine operational errors.

Cloud Storage Providers (CSPs) offer solutions to relieve users from locally storing vast amounts of data, including personal and sensitive ones. While users may desire to retain some privacy on the data they outsource, CSPs are interested in reducing the total storage space by employing compression techniques such as deduplication. We propose a new cryptographic primitive that simultaneously realizes both requirements: Multi-Key Revealing Encryption (MKRE). The goal of MKRE is to disclose the result of a pre-defined function over multiple ciphertexts, even if the ciphertexts were generated using different keys, while revealing nothing else about the data. We present a formal model and a security definition for MKRE and provide a construction of MKRE for generalized deduplication that only uses symmetric key primitives in a black-box way. Our construction allows (a) cloud providers to reduce the storage space by using generalized deduplication to compress encrypted data across users, and (b) each user to maintain a certain privacy level for the outsourced information. Our scheme can be proven secure in the random oracle model (and we argue that this is a necessary evil). We develop a proof-of-concept implementation of our solution. For a test data set, our MKRE construction achieves secure generalized deduplication with a compression ratio of 87% for 1KB file chunks and 82.2% for 8KB chunks. Finally, our experiments show that, compared to generalized deduplication setup with un-encrypted files, adding privacy via MKRE introduces a compression overhead of less than 3% and reduces the storage throughput by at most 6.9%.

In this note, we study the security of oblivious transfer protocols in the presence of adversarial superposition queries. We define a security notion for the sender against a corrupted receiver that makes a superposition query. We present an oblivious transfer protocol that is secure against a quantum receiver restricted to a classical query but it is insecure when the receiver makes a quantum query. In addition, we present an OT protocol that resists to the attack presented in this paper. However, we leave presenting a security proof for this protocol as a direction for the future work.

Abstract--- This paper demonstrates fast and compact implementations of Elliptic Curve Cryptography (ECC) for efficient key agreement over Curve25519. Curve25519 has been recently adopted as a key exchange method for several applications such as connected small devices as well as cloud, and included in the National Institute of Standards and Technology (NIST) recommendations for public key cryptography. This paper presents three different performance level designs including lightweight, area-time efficient, and high-performance architectures. Lightweight hardware implementations are used for several Internet of Things (IoT) applications due to their resources being at premium. Our lightweight architecture utilizes 90% less resources compared to the best previous work while it is still more optimized in term of A\cdot T (area\timestime). For efficient implementation from either time or utilized resources, our area-time efficient architecture can establish almost 7,000 key sessions per second which is 64% faster than the previous works. The area-time efficient architecture uses well scheduled interleaved multiplication combined with a reduction algorithm. Additionally, we offer a fast architecture for high performance applications based on the 4-level Karatsuba method and Carry-Compact Addition (CCA). Our high-performance architecture also outperforms previous work in terms of A\cdot T. The results show 9% and 29% improvement in A\cdot T and A_{d}\cdot T (DSP_count\timestime), respectively. All architectures are variable-base-point implemented on the Xilinx Zynq-7020 FPGA family where performance and implementation metrics are reported and compared. Finally, various side-channel attack countermeasures are embedded in the proposed architectures.

In Paillier's scheme, $c=y^{m}x^{n}\,\mathrm{mod}\,n^{2},\,m \in Z_{n},\,x \in Z_{n^{2}}^{*},\,n=PQ$ is a product of two large primes. Damgård and Jurik generalized Paillier's scheme to reduce the ciphertext expansion, $c=y^{m}x^{n^{s}}\,\mathrm{mod}\,n^{s+1},\,m \in Z_{n^{s}},\,x \in Z_{n^{s+1}}^{*}$. In this paper, we propose a new generalization of Paillier's scheme and prove that our scheme is IND-CPA secure under $k$-subgroup assumption for $\Pi_{k}$. Compared to Damgård and Jurik's generalization, our scheme has three advantages. (a)We use the modulus $P^{a}Q^{b}$ instead of $P^{a}Q^{a}$, so it is more general. (b)We use a general $y$ satisfying $P^{a-1} | order_{P^{a}}(y), \,Q^{b-1} | order_{Q^{b}}(y)$ instead of $y=(1+PQ)^{j}x \,\mathrm{mod}\,N$ which is used in Damgård and Jurik's generalization. (c)Our decryption scheme is more efficient than Damgård and Jurik's generalization system.

Performance in hardware has typically played a major role in differentiating among leading candidates in cryptographic standardization efforts. Winners of two past NIST cryptographic contests (Rijndael in case of AES and Keccak in case of SHA-3) were ranked consistently among the two fastest candidates when implemented using FPGAs and ASICs. Hardware implementations of cryptographic operations may quite easily outperform software implementations for at least a subset of major performance metrics, such as speed, power consumption, and energy usage, as well as in terms of security against physical attacks, including side-channel analysis. Using hardware also permits much higher flexibility in trading one subset of these properties for another. A large number of candidates at the early stages of the standardization process makes the accurate and fair comparison very challenging. Nevertheless, in all major past cryptographic standardization efforts, future winners were identified quite early in the evaluation process and held their lead until the standard was selected. Additionally, identifying some candidates as either inherently slow or costly in hardware helped to eliminate a subset of candidates, saving countless hours of cryptanalysis. Finally, early implementations provided a baseline for future design space explorations, paving a way to more comprehensive and fairer benchmarking at the later stages of a given cryptographic competition. In this paper, we first summarize, compare, and analyze results reported by other groups until mid-May 2020, i.e., until the end of Round 2 of the NIST PQC process. We then outline our own methodology for implementing and benchmarking PQC candidates using both hardware and software/hardware co-design approaches. We apply our hardware approach to 6 lattice-based CCA-secure Key Encapsulation Mechanisms (KEMs), representing 4 NIST PQC submissions. We then apply a software-hardware co-design approach to 12 lattice-based CCA-secure KEMs, representing 8 Round 2 submissions. We hope that, combined with results reported by other groups, our study will provide NIST with helpful information regarding the relative performance of a significant subset of Round 2 PQC candidates, assuming that at least their major operations, and possibly the entire algorithms, are off-loaded to hardware.

In this paper we develop symbolic and computational representations for a class of cryptographic modes of operation, where the symbolic representations are modeled as elements of a term algebra, and we apply them to the analysis of the computational security of the modes. We derive two different conditions on the symbolic representations, a simple one that is sufficient for security, and a more complex one that is both necessary and sufficient, and prove that these properties hold. The problem of deciding computational security then is reduced to the problem of solving certain disunification problems. We also discuss how these results can be extended.

This paper subsumes and replaces the paper ``Symbolic Security Criteria for Blockwise Adaptive Secure Modes of Encryption." (IACR eprint 2017/1152)

Ever since COVID-19 started grasping world’s geographies one by one, countries have been struggling to tackle with this emergency by stretching their healthcare infrastructure beyond the boundary. World is now also trying to find ways to “live with the virus” or coping with the “new normal”. In this effort, contact tracing is thought to be a vital tool which can quickly figure out persons that have come into vicinity of an infected person. Some countries have adopted centralized contact tracing in the perception that it is the most effective and easy solution. Centralized contact tracing has been in the centre of debate as it is a potential tool for launching mass surveillance. So objecting to this, decentralized model has been introduced which gives the control fully to the citizens. However, in decentralized model, the onus is completely on the users to act accordingly if they get a risk notification for coming in close contact with a COVID-19 positive patient. Decentralize model will fail if the large mass of users do not act accordingly after receiving the risk notification. Therefore, a balance needs to strike between the centralized and decentralized models given the socio-economic impact of this pandemic.

In this article, we take a hybrid approach and propose PHyCT that guarantees fail-safe, privacy, and security. This system acts like a decentralized one, where identities of users remain anonymous to the central authority. However, if there is a case of infection, the infected user and the central authority can together only reveal the identities of the users who have come in close contact. This feature enables to handle the situation if there are too many non-compliant users who do not report after getting infection exposure notification. Users who have not come into close contact of any infected person remain anonymous.