IACR News
Updates on the COVID-19 situation are on the
Announcement channel.
Here you can see all recent updates to the IACR webpage. These updates are also available:
21 August 2022
Xavier Bultel, Cristina Onete
Modern-day mobile communications allow users to connect from any place, at any time. However, this ubiquitous access comes at the expense of their privacy. Currently, the operators providing mobile service to users learn call-and SMS-metadata, and even the contents of those exchanges. A main reason behind this is the Lawful-Interception (LI) requirement, by which serving networks must provide this (meta-)data to authorities, given a warrant. At ESORICS 2021, Arfaoui et al. pioneered a primitive called Lawful-Interception Key-Exchange, which achieves the best of both worlds: (provably) privacy-enhanced communications, and finegrained fine-grained, limited access to user data. Their work had two important shortcomings. First, their protocol required pairings which, while sufficiently efficient, might not always be available in the mobile setting. More importantly, that scheme was only applicable in a domestic setting, where the concerned users (Alice and Bob) were subject to the same LI authorities. The case of roaming was left as an open question. In this paper we answer that open question. We extend the framework of Arfaoui et al. to allow Alice and Bob (now subject to potentially two sets of authorities) to establish a secure channel that guarantees the strong properties afforded by the LIKE schemes of ESORICS 2021. Our construction is pairing-free, faster than that of Arfaoui et al., and its security relies on standard assumptions.
Behnam Zahednejad
With the rapid development of Internet of Things (IoT), designing a secure two-factor authentication scheme for these network is
increasingly demanding. Recently, historical bigdata has gained interest
as a novel authentication factor in this area. In this paper, we focus on a
recent authentication scheme using bigdata (Liu et al.’s scheme) which
claims to provide additional security properties such as Perfect Forward
Secrecy (PFS), Key Compromise Impersonation (KCI) resilience and
Server Compromise Impersonation (SCI) resilience. However, assuming
a real strong attacker, rather than a weak one. we show that their scheme
not only fails to provide KCI and SCI, but also doesn’t provide real two-factor security, revocability and suffers inside attack. Then we propose
our novel scheme which can indeed provide two-factor security, PFS ,
KCI and inside attack resilience and revocability of the client. Further,
our performance analysis shows that our scheme has reduced modular
exponentiation operation and multiplication for both client and server
compared to Liu et al.’s scheme which reduces the execution time by one
third i.e. 6 ms and 30 ms (0.3 ms and 4 ms) for IoT device (server) for
security levels of λ = 128, λ = 256 respectively
Huachuang Sun, Haifeng Sun, Kevin Singh, Akhil Sai Peddireddy, Harshad Patil, Jianwei Liu, Weikeng Chen
Proving discrete log equality for groups of the same order is addressed by Chaum and Pedersen's seminal work. However, there has not been a lot of work in proving discrete log equality for groups of different orders.
This paper presents an efficient solution, which leverages a technique we call delegated Schnorr. The discovery of this technique is guided by a design methodology that we call the inspection model, and we find it useful for protocol designs.
We show two applications of this technique on the Findora blockchain:
**Maxwell-Zerocash switching:** There are two privacy-preserving transfer protocols on the Findora blockchain, one follows the Maxwell construction and uses Pedersen commitments over Ristretto, one follows the Zerocash construction and uses Rescue over BLS12-381. We present an efficient protocol to convert assets between these two constructions while preserving the privacy.
**Zerocash with secp256k1 keys:** Bitcoin, Ethereum, and many other chains do signatures on secp256k1. There is a strong need for ZK applications to not depend on special curves like Jubjub, but be compatible with secp256k1. Due to FFT unfriendliness of secp256k1, many proof systems (e.g., Groth16, Plonk, FRI) are infeasible. We present a solution using Bulletproofs over curve secq256k1 ("q") and delegated Schnorr which connects Bulletproofs to TurboPlonk over BLS12-381.
We conclude the paper with (im)possibility results about Zerocash with only access to a deterministic ECDSA signing oracle, which is the case when working with MetaMask. This result shows the limitations of the techniques in this paper. This paper is under a bug bounty program through a grant from Findora Foundation.
**Maxwell-Zerocash switching:** There are two privacy-preserving transfer protocols on the Findora blockchain, one follows the Maxwell construction and uses Pedersen commitments over Ristretto, one follows the Zerocash construction and uses Rescue over BLS12-381. We present an efficient protocol to convert assets between these two constructions while preserving the privacy.
**Zerocash with secp256k1 keys:** Bitcoin, Ethereum, and many other chains do signatures on secp256k1. There is a strong need for ZK applications to not depend on special curves like Jubjub, but be compatible with secp256k1. Due to FFT unfriendliness of secp256k1, many proof systems (e.g., Groth16, Plonk, FRI) are infeasible. We present a solution using Bulletproofs over curve secq256k1 ("q") and delegated Schnorr which connects Bulletproofs to TurboPlonk over BLS12-381.
We conclude the paper with (im)possibility results about Zerocash with only access to a deterministic ECDSA signing oracle, which is the case when working with MetaMask. This result shows the limitations of the techniques in this paper. This paper is under a bug bounty program through a grant from Findora Foundation.
Brooklyn Zelenka
Hash chains are a simple way to generate pseudorandom data, but are inefficient in situations that require long chains. This can cause unnecessary overhead for use cases including logical clocks, synchronizing the heads of a pseudorandom stream, or non-interactive key agreement. This paper presents the “skip ratchet”, a novel pseudorandom function that can be efficiently incremented by arbitrary intervals.
Meltem Sonmez Turan
Multiplicative Complexity (MC) is defined as the minimum number of AND gates required to implement a function with a circuit over the basis AND, XOR, NOT. This complexity measure is relevant for many advanced cryptographic protocols such as fully homomorphic encryption, multi-party computation, and zero-knowledge proofs, where processing AND gates is more expensive than processing XOR gates. Although there is no known asymptotically efficient technique to compute the MC of a random Boolean function, bounds on the MC of Boolean functions are successfully used to to show existence of Boolean functions with a particular MC.
In 2000, Boyar et al. showed that, for all $n\geq 0$, at most $2^{k^2+2k+2kn+n+1}$ $n$-variable Boolean functions can be computed with $k$ AND gates. This bound is used to prove the existence of a 8-variable Boolean functions with MC greater than 7. In this paper, we improve the Boyar et al. bound.
Francesca Falzon, Evangelia Anna Markatou, Zachary Espiritu, Roberto Tamassia
This work addresses expressive queries over encrypted data by presenting the first systematic study of multi-attribute range search on a symmetrically encrypted database outsourced to an honest-but-curious server. Prior work includes a thorough analysis of single-attribute range search schemes (e.g. Demertzis et al. 2016) and a proposed high-level approach for multi-attribute schemes (De Capitani di Vimercati et al. 2021). We first introduce a flexible framework for building secure range search schemes with an arbitrary number of attributes (dimensions) by adapting a broad class of geometric search data structures to operate on encrypted data. Our framework encompasses widely used data structures such as multi-dimensional range trees and quadtrees, and has strong security properties that we formally prove. We then develop six concrete highly parallelizable range search schemes within our framework that offer a sliding scale of efficiency and security tradeoffs to suit the needs of the application. We evaluate our schemes with a formal complexity and security analysis, a prototype implementation, and an experimental evaluation on real-world datasets.
Jonas Janneck, Anas Boudi, Anselme Tueno, Matthew Akram
We address the problem of privately evaluating a branching program on encrypted data. This scenario is a 2-party protocol consisting of a server and a client. The server privately holds a branching program which is a representation of a boolean function using a directed acyclic graph. The client holds a secret input to the branching program. The goal of the computation is to evaluate the client's input on the server program such that only the result is revealed to the client, and nothing is revealed to the server. To solve this problem Ishai-Paskin introduced a public-key encryption scheme that is based on Damgård-Jurik additively homomorphic encryption and has the property, that given a branching program $P$ and an encryption $c$ of an input $y$, it is possible to efficiently compute a succinct ciphertext $c'$ corresponding to $P(y)$. The entire computation is done by the server relying on the fact that Damgård-Jurik scheme has length-flexible ciphertexts which allows multiplications between ciphertexts of different sizes under the same encryption key. Although the decryption of the Damgård-Jurik scheme is theoretically efficient, the size of $c'$ and the decoding time depend on the depth of the branching program. In this paper, we propose a new scheme where the input is instead encrypted using fully homomorphic encryption and discuss different variants and optimizations. The entire computation is also done by the server but the size of the resulting ciphertext is independent of the depth of the program. We implement Ishai-Paskin and our scheme and show that the running time of our scheme is an order of magnitude smaller.
Juliane Krämer, Patrick Struck
The qINDqCPA security notion for public-key encryption schemes by Gagliardoni et al. (PQCrypto'21) models security against adversaries which are able to obtain ciphertexts in superposition. Defining this security notion requires a special type of quantum operator. Known constructions differ in which keys are necessary to construct this operator, depending on properties of the encryption scheme. We argue—for the typical setting of securing communication between Alice and Bob—that in order to apply the notion, the quantum operator should be realizable for challengers knowing only the public key. This is already known to be the case for a wide range of public-key encryption schemes, in particular, those exhibiting the so-called recoverability property which allows to recover the message from a ciphertext using the randomness instead of the secret key. The open question is whether there are real-world public-key encryption schemes for which the notion is not applicable, considering the aforementioned observation on the keys known by the challenger. We answer this question in the affirmative by showing that applying the qINDqCPA security notion to the OAEP construction requires the challenger to know the secret key. We conclude that the qINDqCPA security notion might need to be refined to eventually yield a universally applicable PKE notion of quantum security with a quantum indistinguishability phase.
Xiaojie Guo
This work addresses the security flaw in the original VeriFL protocol and proposes a patched protocol that is secure against any static malicious adversary with a certain threshold and only introduces moderate modifications to the original protocol.
Alexandre Belling, Azam Soleimanian, Olivier Bégassat
SNARK is a well-known family of cryptographic tools that is increasingly used in the field of computation integrity at scale. In this area, multiple works have introduced SNARK friendly cryptographic primitives - hashing, but also encryption and signature verification - which are used in many applications. Despite all the efforts to create cryptographic primitives that can be proved faster, it remains a major performance hole in practice. In this paper, we present a recursive technique that can improve the efficiency of the prover by an order of magnitude compared to proving MiMC hashes (a snark-friendly hash function, Albrecht et al. 2016) with a Groth16 (Eurocrypt 2016) proof. We use GKR (a well-known public-coin argument system by Goldwasser et al., STOC 2008) to prove the integrity of hash computations and embed the GKR verifier inside a SNARK circuit. The challenge comes from the fact that GKR is a public-coin interactive protocol, and applying Fiat-Shamir naively may result in worse performances than applying existing techniques directly. This is because Fiat-Shamir itself is involved with hash computation over a large string. We take advantage of a property that SNARK schemes commonly have to build a protocol in which for the Fiat-Shamir hashes have very short inputs. The technique we present is generic and can be applied to over most known SNARK scheme and any public-coin argument system in place of GKR. It outputs an augmented proof system combining the performances of the two.
Yuhei Watanabe, Hideki Yamamoto, Hirotaka Yoshida
This paper presents results of performance evaluation of NIST Lightweight Cryptography standardization finalists which are implemented by us. Our implementation method puts on the target to reduce RAM consumption on embedded devices. Our target microcontrollers are AVR ATmega 128 and ARM Cortex-M3. We apply our implementation method to five AEAD schemes which include four finalists of the NIST lightweight cryptography standardization and demonstrate the performance evaluation on target microcontrollers. From our performance evaluation of the RAM size, we have achieved 117-byte TinyJAMBU-128 on ATmega 128 and 140-byte TinyJAMBU-128 on ARM Cortex-M3. Our implementation of TinyJAMBU-128 has the smallest RAM of all the target AEAD schemes.
Tuong Ngoc Nguyen, Anh The Ta, Huy Quoc Le, Dung Hoang Duong, Willy Susilo, Fuchun Guo, Kazuhide Fukushima, Shinsaku Kiyomoto
Unique ring signatures (URS) were introduced by Franklin and Zhang (FC 2012) as a unification of linkable and traceable ring signatures. In URS, each member within a ring can only produce, on behalf of the ring, at most one signature for a message. Applications of URS potentially are e-voting systems and e–token systems. In blockchain technology, URS has been implemented for mixing contracts. However, existing URS schemes are based on the Discrete Logarithm Problem, which is insecure in the post-quantum setting. In this paper, we design a new lattice-based URS scheme where the signature size is logarithmic in the number of ring members. The proposed URS exploits a Merkle tree-based accumulator as a building block in the lattice setting. Our scheme is secure under the Short Integer Solution and Learning With Rounding assumptions in the random oracle model.
Marten van Dijk, Chenglu Jin
Analysis of advanced Physical Unclonable Function (PUF) applications and protocols rely on assuming that a PUF behaves like a random oracle, that is, upon receiving a challenge, a uniform random response with replacement is selected, measurement noise is added, and the resulting response is returned. In order to justify such an assumption, we need to rely on digital interface computation that into some extent remains confidential -- otherwise, information about PUF challenge response pairs leak with which the adversary can train a prediction model for the PUF.
We introduce a theoretical framework that allows the adversary to have a prediction model (with typical accuracy of 75% for predicting response bits for state-of-the-art silicon PUF designs). We do not require any confidential digital computing or digital secrets while we can still prove rigorous statements about the bit security of a system that interfaces with the PUF. In particular, we prove the bit security of a PUF based random oracle construction; this merges the PUF framework with fuzzy extractors.
We introduce a theoretical framework that allows the adversary to have a prediction model (with typical accuracy of 75% for predicting response bits for state-of-the-art silicon PUF designs). We do not require any confidential digital computing or digital secrets while we can still prove rigorous statements about the bit security of a system that interfaces with the PUF. In particular, we prove the bit security of a PUF based random oracle construction; this merges the PUF framework with fuzzy extractors.
Damien Robert
Let ? ∶ ? → ?′ be an N-isogeny between elliptic curves (or abelian varieties) over a finite field ?_?. We show that there always exist an efficient representation of ? that takes polylogarithmic ?(log^?(1) ? log ?) space and which can evaluate ? at any point ? ∈ ?(?_{?^?}) in polylogarithmic ?(log^?(1) ?) arithmetic operations in ?_{?^?}.
Furthermore, this efficient representation can be computed by evaluating ? on ?(log ?) points defined over extensions of degree ?(log ?) over ?_?. In particular, if ? is represented by the equation ?(?) = 0 of its kernel ?, then using Vélu’s formula the efficient representation can be computed in time ? ̃(? log ? + log^2 ?).
17 August 2022
Luan Luan, Chunxiang Gu, Yonghui Zheng, Yanan Shi
Lattice enumeration is a linear-space algorithm for solving the shortest lattice vector problem(SVP). Extreme pruning is a practical technique for accelerating lattice enumeration, which has mature theoretical analysis and practical implementation. However, these works are still remain to be done for discrete pruning. In this paper, we improve the discrete pruned enumeration (DP enumeration), and give a solution to the problem proposed by Leo Ducas et Damien Stehle about the cost estimation of discrete pruning. Our contribution is on the following three aspects:
First, we refine the algorithm both from theoretical and practical aspects. Discrete pruning using natural number representation lies on a randomness assumption of lattice point distribution, which has an obvious paradox in the original analysis. We rectify this assumption to fix the problem, and correspondingly modify some details of DP enumeration. We also improve the binary search algorithm for cell enumeration radius with polynomial time complexity, and refine the cell decoding algorithm. Besides, we propose to use a truncated lattice reduction algorithm -- k-tours-BKZ as reprocessing method when a round of enumeration failed.
Second, we propose a cost estimation simulator for DP enumeration. Based on the investigation of lattice basis stability during reprocessing, we give a method to simulate the squared length of Gram-Schmidt orthogonalization basis quickly, and give the fitted cost estimation formulae of sub-algorithms in CPU-cycles through intensive experiments. The success probability model is also modified based on the rectified assumption. We verify the cost estimation simulator on middle size SVP challenge instances, and the simulation results are very close to the actual performance of DP enumeration.
Third, we give a method to calculate the optimal parameter setting to minimize the running time of DP enumeration. We compare the efficiency of our optimized DP enumeration with extreme pruning enumeration in solving SVP challenge instances. The experimental results in medium dimension and simulation results in high dimension both show that the discrete pruning method could outperform extreme pruning. An open-source implementation of DP enumeration with its simulator is also provided.
First, we refine the algorithm both from theoretical and practical aspects. Discrete pruning using natural number representation lies on a randomness assumption of lattice point distribution, which has an obvious paradox in the original analysis. We rectify this assumption to fix the problem, and correspondingly modify some details of DP enumeration. We also improve the binary search algorithm for cell enumeration radius with polynomial time complexity, and refine the cell decoding algorithm. Besides, we propose to use a truncated lattice reduction algorithm -- k-tours-BKZ as reprocessing method when a round of enumeration failed.
Second, we propose a cost estimation simulator for DP enumeration. Based on the investigation of lattice basis stability during reprocessing, we give a method to simulate the squared length of Gram-Schmidt orthogonalization basis quickly, and give the fitted cost estimation formulae of sub-algorithms in CPU-cycles through intensive experiments. The success probability model is also modified based on the rectified assumption. We verify the cost estimation simulator on middle size SVP challenge instances, and the simulation results are very close to the actual performance of DP enumeration.
Third, we give a method to calculate the optimal parameter setting to minimize the running time of DP enumeration. We compare the efficiency of our optimized DP enumeration with extreme pruning enumeration in solving SVP challenge instances. The experimental results in medium dimension and simulation results in high dimension both show that the discrete pruning method could outperform extreme pruning. An open-source implementation of DP enumeration with its simulator is also provided.
Peyman Momeni, Sergey Gorbunov, Bohan Zhang
While blockchain systems are quickly gaining popularity, front-running remains a major obstacle to fair exchange. In this paper, we show how to apply identity-based encryption (IBE) to prevent front-running with minimal bandwidth overheads. In our approach, to decrypt a block of N transactions, the number of messages sent across the network only grows linearly with the size of decrypting committees, S. That is, to decrypt a set of N transactions sequenced at a specific block, a committee only needs to exchange S decryption shares (independent of N ). In comparison, previous solutions are based on threshold decryption schemes, where each transaction in a block must be decrypted separately by the committee, resulting in bandwidth overhead of N × S. Along the way, we present a model for fair block processing and build a prototype implementation. We show that on a sample of 1000 messages with 1000 validators our system saves 42.53 MB of bandwidth which is 99.6% less compared with the standard threshold decryption paradigm.
Öznur MUT SAĞDIÇOĞLU, Serhat Sağdıçoğlu, Ebru Küçükkubaş
Differential cryptanalysis is one of the most effective methods for evaluating the security level of block ciphers. For this, an attacker tries to find a differential or a characteristic with a high probability that distinguishes a block cipher from a random permutation to obtain the secret key. Although it is theoretically possible to compute the probability of a differential for a block cipher, there are two problems to compute it practically. The first problem is that it is computationally impossible to compute differential probability by trying all plaintext pairs. The second problem is that the probability of a differential over all choices of the plaintext and key might be different from the probability of the differential over all plaintexts for a fixed key. Thus, to evaluate the security against the differential cryptanalysis, one must assume both the hypothesis of stochastic equivalence and the Markov model. However, the hypothesis of stochastic equivalence does not hold in general. Indeed, we show on simple ciphers that the hypothesis of stochastic equivalence does not hold. Moreover, we observe that the differential probability is not equal to the expected differential probability. For these results, we study plateau characteristics for a 4-bit cipher and a 16-bit super box. As a result, when considering differential cryptanalysis, one must be careful about the gap between the theoretical and the practical security of block ciphers.
Ruiqi Mi, Haodong Jiang, Zhenfeng Zhang
Resistance to key misuse attacks is a vital property for key encapsulation mechanisms(KEMs)in NIST-PQC standardization process. In key mismatch attack, the adversary recovers reused secret key with the help of an oracle $\mathcal{O}$ that indicates whether the shared key matches or not. Key mismatch attack is more powerful when fewer oracle queries are required. A series of works tried to reduce query times, Qin et al. [AISACRYPT 2021] gave a systematic approach to finding lower bound of oracle queries for a category of KEMs, including NIST’s third-round candidate Kyber and Saber.
In this paper, we found the aforementioned bound can be bypassed by combining Qin et al. (AISACRYPT 2021)’s key mismatch attack with a standard lattice attack. In particular, we explicitly build the relationship between the number of queries to the oracle and the bit security of the lattice-based KEMs. Our attack is inspired by the fact that each oracle query reveals partial information of reused secrets, and affects the mean and the covariance parameter of secrets, making the attack on lattice easier. In addition, We quantify such effect in theory and estimate the security loss for all NIST second-round candidate KEMs.Specifically, Our improved attack reduces the number of queries for Kyber512 by 34% from 1312 queries with bit security 107 to 865 with bit security 32. For Kyber768 and Kyber1024, our improved attack reduces the number of queries by 29% and 27% with bit security is 32.
In this paper, we found the aforementioned bound can be bypassed by combining Qin et al. (AISACRYPT 2021)’s key mismatch attack with a standard lattice attack. In particular, we explicitly build the relationship between the number of queries to the oracle and the bit security of the lattice-based KEMs. Our attack is inspired by the fact that each oracle query reveals partial information of reused secrets, and affects the mean and the covariance parameter of secrets, making the attack on lattice easier. In addition, We quantify such effect in theory and estimate the security loss for all NIST second-round candidate KEMs.Specifically, Our improved attack reduces the number of queries for Kyber512 by 34% from 1312 queries with bit security 107 to 865 with bit security 32. For Kyber768 and Kyber1024, our improved attack reduces the number of queries by 29% and 27% with bit security is 32.
Hao Chung, Elisaweta Masserova, Elaine Shi, Sri AravindaKrishnan Thyagarajan
The recent work of Chung et al. suggested new formal foundations for side-contract-resilient fair exchange protocols. In this paper, we suggest new constructions that achieve a coalition-resistant Nash equilibrium, and moreover, our constructions improve over Chung et al. in the following senses: 1) we achieve optimistic reponsiveness; and 2) we reduce the amount of collateral from the parties.
Haiyan Wang, Penghui (Owen) Liu, Xiaoxiong Zhong, Weizhe Zhang
The time sequence-based outsourcing makes new demands for related access control continue to grow increasingly in cloud computing. In this paper, we propose a practical password-based access control framework for such media cloudization relying on content control based on the time-sequence attribute, which is designed over prime-order groups. First, the scheme supports
multi-keyword search simultaneously in any monotonic boolean formulas, and enables media owner to control content encryption key for different time-periods using an updatable password; Second, the scheme supports the key self-retrievability of content encryption key, which is more suitable for the cloud-based media applications with massive users. Then, we show that the proposed scheme is provably secure in the standard model. Finally, the detailed result of performance evaluation shows the proposed scheme is efficient and practical for cloud-based media applications.