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:
31 January 2022
Aydin Abadi, Steven J. Murdoch
An "Authorised Push Payment" (APP) fraud refers to the case where fraudsters deceive a victim to make payments to bank accounts controlled by them. The total amount of money stolen via APP frauds is swiftly growing. Although regulators have provided guidelines to improve victims' protection, the guidelines are vague and the victims are not receiving sufficient protection. To facilitate victims' reimbursement, in this work, we propose a protocol called "Payment with Dispute Resolution" (PwDR) and formally define it. The protocol lets an honest victim prove its innocence to a third-party dispute resolver while preserving the protocol participants' privacy. It makes black-box use of a standard online banking system. We evaluate its asymptotic cost and runtime via a prototype implementation. Our evaluation indicates that the protocol is efficient. It imposes only O(1) overheads to the customer and bank. Also, it takes a dispute resolver 0.09 milliseconds to settle a dispute between the two parties.
Soundes Marzougui, Vincent Ulitzsch, Mehdi Tibouchi, Jean-Pierre Seifert
We present an end-to-end (equivalent) key recovery attack on the Dilithium lattice-based signature scheme, one of the top contenders in the NIST postquantum cryptography competition. The attack is based on a small side-channel leakage we identified in a bit unpacking procedure inside Dilithium signature generation. We then combine machine-learning based profiling with various algorithmic techniques, including least squares regression and integer linear programming, in order to leverage this small leakage into essentially full key recovery: we manage to recover, from a moderate number of side-channel traces, enough information to sign arbitrary messages. We confirm the practicality of our technique using concrete experiments against the ARM Cortext-M4 implementation of Dilithium, and verify that our attack is robust to real-world conditions such as noisy power measurements.
This attack appears difficult to protect against reliably without strong side-channel countermeasures such as masking of the entire signing algorithm, and underscores the necessity of implementing such countermeasures despite their known high cost.
Varun Madathil, Alessandra Scafuro, Kemafor Anyanwu, Sen Qiao, Akash Pateria, Binil Starly
Technology is being used increasingly for lowering the trust barrier in domains where collaboration and cooperation are necessary, but reliability and efficiency are critical due to high stakes. An example is an industrial marketplace where many suppliers must participate in production while ensuring reliable outcomes; hence, partnerships must be pursued with care. Online marketplaces like Xometry facilitate partnership formation by vetting suppliers and mediating the marketplace. However, such an approach requires that all trust be vested in the middleman. This centralizes control, making the system vulnerable to being biased towards specific providers. The use of blockchains is now being explored to bridge the trust gap needed to support decentralizing marketplaces, allowing suppliers and customers to interact more directly by using the information on the blockchain. A typical scenario is the need to preserve privacy in certain interactions initiated by the buyer (e.g., protecting a buyer’s intellectual property during outsourcing negotiations). In this work, we initiate the formal study of matching between suppliers and buyers when buyer-privacy is required for some marketplace interactions and make the following contributions. First, we devise a formal security definition for private interactive matching in the Universally Composable (UC) Model that captures the privacy and correctness properties expected in specific supply chain marketplace interactions. Second, we provide a lean protocol based on any programmable blockchain, anonymous group signatures, and public-key encryption. Finally, we implement the protocol by instantiating some of the blockchain logic by extending the BigChainDB blockchain platform.
Matthias Fitzi, Xuechao Wang, Sreeram Kannan, Aggelos Kiayias, Nikos Leonardos, Pramod Viswanath, Gerui Wang
Resource-based consensus is the backbone of permissionless distributed ledger systems. The security of such protocols relies fundamentally on the level of resources actively engaged in the system. The variety of different resources (and related proof protocols, some times referred to as PoX in the literature) raises the fundamental question whether it is possible to utilize many of them in tandem and build multi-resource consensus protocols. The challenge in combining different resources is to achieve fungibility between them, in the sense that security would hold as long as the cumulative adversarial power across all resources is bounded.
In this work, we put forth Minotaur, a multi-resource blockchain consensus protocol that combines proof of work (PoW) and proof-of-stake (PoS), and we prove it optimally fungible. At the core of our design, Minotaur operates in epochs while continuously sampling the active computational power to provide a fair exchange between the two resources, work and stake. Further, we demonstrate the ability of Minotaur to handle a higher degree of work fluctuation as compared to the Bitcoin blockchain; we also generalize Minotaur to any number of resources.
We demonstrate the simplicity of Minotaur via implementing a full stack client in Rust (available open source). We use the client to test the robustness of Minotaur to variable mining power and combined work/stake attacks and demonstrate concrete empirical evidence towards the suitability of Minotaur to serve as the consensus layer of a real-world blockchain.
In this work, we put forth Minotaur, a multi-resource blockchain consensus protocol that combines proof of work (PoW) and proof-of-stake (PoS), and we prove it optimally fungible. At the core of our design, Minotaur operates in epochs while continuously sampling the active computational power to provide a fair exchange between the two resources, work and stake. Further, we demonstrate the ability of Minotaur to handle a higher degree of work fluctuation as compared to the Bitcoin blockchain; we also generalize Minotaur to any number of resources.
We demonstrate the simplicity of Minotaur via implementing a full stack client in Rust (available open source). We use the client to test the robustness of Minotaur to variable mining power and combined work/stake attacks and demonstrate concrete empirical evidence towards the suitability of Minotaur to serve as the consensus layer of a real-world blockchain.
Zhihui Lin, Prosanta Gope, Jianting Ning, Biplab Sikdar
The transition from paper-based information to Electronic Health Records (EHRs) has driven various advancements in the modern healthcare industry. In many cases, patients need to share their EHR with healthcare professionals. Given the sensitive and security-critical nature of EHRs, it is essential to consider the security and privacy issues of storing and sharing EHR. However, existing security solutions are excessively encrypting the whole database, where for each access request the entire database is required to be decrypted, which is a time-consuming process. On the other hand, the use of EHR for medical research (e.g. development of precision medicine, diagnostics techniques etc.) as well optimisation of practises in healthcare organisations, requires the EHR to be analysed and for that they should be easily accessible without compromising the privacy of the patient. In this paper, we propose an efficient technique called E-Tenon that not only securely keeps all EHR publicly accessible but also provides the desirable security features. To the best of our knowledge, this is the first work in which an Open Database is used for protecting EHR. The proposed concept of E-Tenon empowers patients to securely share their EHR under multi-level, fine-grained access policies defined by themselves. Analyses show that our system outperforms existing solutions in terms of computational complexity.
Nitin Agrawal, James Bell, Adrià Gascón, Matt J. Kusner
We address the problem of efficiently verifying a commitment in a two-party computation. This addresses the scenario where a party P1 commits to a value x to be used in a subsequent secure computation with another party P2 that wants to receive assurance that P1 did not cheat, i.e. that x was indeed the value inputted into the secure computation. Our constructions operate in the publicly verifiable covert (PVC) security model, which is a relaxation of the malicious model of MPC appropriate in settings where P1 faces a reputational harm if caught cheating.
We introduce the notion of PVC commitment scheme and indexed hash functions to build commitments schemes tailored to the PVC framework, and propose constructions for both arithmetic and Boolean circuits that result in very efficient circuits. From a practical standpoint, our constructions for Boolean circuits are 60× faster to evaluate securely, and use 36× less communication than baseline methods based on hashing. Moreover, we show that our constructions are tight in terms of required non-linear operations, by proving lower bounds on the nonlinear gate count of commitment verification circuits. Finally, we present a technique to amplify the security properties our constructions that allows to efficiently recover malicious guarantees with statistical security.
Mingxing Hu, Zhen Liu
Ring signatures enable a user to sign messages on behalf of an arbitrary set of users, called the ring. The anonymity of the scheme guarantees that the signature does not reveal which member of the ring signed the message. The notion of linkable ring signatures (LRS) is an extension of the concept of ring signatures such that there is a public way of determining whether two signatures have been produced by the same signer. Lattice-based LRS is an important and active research line, since lattice-based cryptography has attracted more attention due to its distinctive features especially the quantum resistant. However, all the existing lattice-based LRS relied on random oracle heuristics, i.e., no lattice-based LRS in the standard model has been introduced so far.
In this paper, we present a lattice-based LRS scheme based on the well- studied standard lattice assumptions (SIS and LWE) in the standard model.
Funda Özdemir, Çetin Kaya Koç
This paper presents the development of cryptography since Shannon's seminal paper ``Communication Theory of Secrecy Systems'' in 1949.
Pedro Geraldo M. R. Alves, Jheyne N. Ortiz, Diego F. Aranha
Recent works challenged the Number-Theoretic Transform (NTT) as the most efficient method for
polynomial multiplication in GPU implementations of Fully Homomorphic Encryption schemes such
as CKKS and BFV. In particular, these works argue that the Discrete Galois Transform (DGT) is a
better candidate for this particular case. However, these claims were never rigorously validated, and
only intuition was used to argue in favor of each transform. This work brings some light on the dis-
cussion by developing similar CUDA implementations of the CKKS cryptosystem, differing only in
the underlying transform and related data structure. We ran several experiments and collected perfor-
mance metrics in different contexts, ranging from the basic direct comparison between the transforms
to measuring the impact of each one on the inference phase of the logistic regression algorithm. Our
observations suggest that, despite some specific polynomial ring configurations, the DGT in a stan-
dalone implementation does not offer the same performance as the NTT. However, when we consider
the entire cryptosystem, we noticed that the effects of the higher arithmetic density of the DGT on
other parts of the implementation is substantial, implying a considerable performance improvement
of up to 15% on the homomorphic multiplication. Furthermore, this speedup is consistent when we
consider a more complex application, indicating that the DGT suits better the target architecture.
Sarah Arpin, Mingjie Chen, Kristin E. Lauter, Renate Scheidler, Katherine E. Stange, Ha T. N. Tran
In supersingular isogeny-based cryptography, the path-finding problem reduces to the endomorphism ring problem. Can path-finding be reduced to knowing just one endomorphism? It is known that a small endomorphism enables polynomial-time path-finding and endomorphism ring computation (Love-Boneh [36]). As this paper neared completion, it was shown that the endomorphism ring problem in the presence of one known endomorphism reduces to a vectorization problem (Wesolowski [54]). In this paper, we give explicit classical and quantum algorithms for path-finding to an initial curve using the knowledge of one endomorphism. An endomorphism gives an explicit orientation of a supersingular elliptic curve. We use the theory of oriented supersingular isogeny graphs and algorithms for taking ascending/descending/horizontal steps on such graphs. Although the most general runtimes are subexponential, we show that every supersingular elliptic curve has (potentially large) endomorphisms whose exposure would lead to a classical polynomial-time path-finding algorithm.
Dingfeng Ye, Jun Xu, Guifang Huang, Lei Hu
Existing lattice signature schemes are much less efficient than encryption schemes due to the rejection sampling paradigm. We give a new construction which avoids rejection sampling by using temporary public keys and structured secrets in a Bliss type scheme. Structured secrets also improve existing lattice encryption schemes to nearly the same extreme efficiency. Our signing algorithm is comparative with this optimized encryption efficiency. Our signature scheme allows the same key pair work as an encryption scheme. For lightweight implementation, our techniques allow integrating of public-key encryption and signature in a simple circuit which only needs to do small integer additions as the main part of computation.
Karim Eldefrawy, Nicholas Genise, Rutuja Kshirsagar, Moti Yung
We look at two basic coding theoretic and cryptographic mechanisms developed separately and investigate relationships between them and their implications. The first mechanism is Proactive Secret Sharing (PSS), which allows randomization and repair of shares using information from other shares. PSS enables constructing secure multi-party computation protocols that can withstand mobile dynamic attacks.
This self-recovery and the redundancy of uncorrupted shares allows a system to overcome recurring faults throughout its lifetime, eventually finishing the computation (or continuing forever to maintain stored data). The second mechanismis Regenerating Codes (RC) which were extensively studied and adopted in distributed storage systems. RC are error correcting (or erasure handling) codes capable of recovering a block of a distributively held codeword from other servers' blocks. This self-healing nature enables more robustness of a code distributed over different machines. Given that the two mechanisms have a built-in self-healing (leading to stabilizing) and that both can be based on Reed Solomon Codes, it is natural to formally investigate deeper relationships between them.
We prove that a PSS scheme can be converted into an RC scheme, and that under some conditions RC can be utilized to instantiate a PSS scheme. This allows us, in turn, to leverage recent results enabling more efficient polynomial interpolation (due to Guruswami and Wooters) to improve the efficiency of a PSS scheme. We also show that if parameters are not carefully calibrated, such interpolation techniques (allowing partial word leakage) may be used to attack a PSS scheme over time. Secondly, the above relationships give rise to extended (de)coding notions. Our first example is mapping the generalized capabilities of adversaries (called generalized adversary structures) from the PSS realm into the RC one. Based on this we define a new variant of RC we call Generalized-decoding Regenerating Code (GRC) where not all network servers have a uniform sub-codeword (motivated by non-uniform probability of attacking different servers case). We finally highlight several interesting research directions due to our results, e.g., designing new improved GRC, and more adaptive RC re-coding techniques.
This self-recovery and the redundancy of uncorrupted shares allows a system to overcome recurring faults throughout its lifetime, eventually finishing the computation (or continuing forever to maintain stored data). The second mechanismis Regenerating Codes (RC) which were extensively studied and adopted in distributed storage systems. RC are error correcting (or erasure handling) codes capable of recovering a block of a distributively held codeword from other servers' blocks. This self-healing nature enables more robustness of a code distributed over different machines. Given that the two mechanisms have a built-in self-healing (leading to stabilizing) and that both can be based on Reed Solomon Codes, it is natural to formally investigate deeper relationships between them.
We prove that a PSS scheme can be converted into an RC scheme, and that under some conditions RC can be utilized to instantiate a PSS scheme. This allows us, in turn, to leverage recent results enabling more efficient polynomial interpolation (due to Guruswami and Wooters) to improve the efficiency of a PSS scheme. We also show that if parameters are not carefully calibrated, such interpolation techniques (allowing partial word leakage) may be used to attack a PSS scheme over time. Secondly, the above relationships give rise to extended (de)coding notions. Our first example is mapping the generalized capabilities of adversaries (called generalized adversary structures) from the PSS realm into the RC one. Based on this we define a new variant of RC we call Generalized-decoding Regenerating Code (GRC) where not all network servers have a uniform sub-codeword (motivated by non-uniform probability of attacking different servers case). We finally highlight several interesting research directions due to our results, e.g., designing new improved GRC, and more adaptive RC re-coding techniques.
Huy Quoc Le, Dung Hoang Duong, Willy Susilo, Josef Pieprzyk
Spatial Encryption (SE), which involves encryption and decryption with affine/vector objects, was introduced by Boneh and Hamburg at Asiacrypt 2008. Since the introduction, SE has been shown as a versatile and elegant tool for implementing many other important primitives such as (Hierarchical) Identity-based Encryption ((H)IBE), Broadcast (H)IBE, Attribute-based Encryption, Forward-secure cryptosystems.
In this paper, we revisit SE toward a more compact SE in the lattice setting. In doing that, we introduce a novel primitive called Delegatable Multiple Inner Product Encryption (DMIPE), which is a delegatable generalization of Inner Product Encryption (IPE) but different from the Hierarchical IPE (HIPE) (Okamoto and Takashima at Asiacrypt 2009). We point out that DMIPE and SE are equivalent in the sense that there are security-preserving conversions between them. As a proof of concept, we then successfully instantiate a concrete DMIPE construction relying on the hardness of the decisional learning with errors problem. The DMIPE design in turn implies a more compact lattice-based SE in terms of sizes, in comparison with SEs converted from HIPE (e.g., Xagawa’s HIPE at PKC 2013) using the framework by Chen at al. (Designs, Codes, and Cryptography, 2014). Furthermore, we show that SE can also be used to implement the Allow-/Deny-list encryption, which subsumes, e.g., puncturable encryption (Green and Miers at IEEE S&P 2015) among others
In this paper, we revisit SE toward a more compact SE in the lattice setting. In doing that, we introduce a novel primitive called Delegatable Multiple Inner Product Encryption (DMIPE), which is a delegatable generalization of Inner Product Encryption (IPE) but different from the Hierarchical IPE (HIPE) (Okamoto and Takashima at Asiacrypt 2009). We point out that DMIPE and SE are equivalent in the sense that there are security-preserving conversions between them. As a proof of concept, we then successfully instantiate a concrete DMIPE construction relying on the hardness of the decisional learning with errors problem. The DMIPE design in turn implies a more compact lattice-based SE in terms of sizes, in comparison with SEs converted from HIPE (e.g., Xagawa’s HIPE at PKC 2013) using the framework by Chen at al. (Designs, Codes, and Cryptography, 2014). Furthermore, we show that SE can also be used to implement the Allow-/Deny-list encryption, which subsumes, e.g., puncturable encryption (Green and Miers at IEEE S&P 2015) among others
Nir Drucker, Tomer Pelleg
Harvey butterflies and their variants are core primitives in many optimized number-theoretic transform (NTT) implementations, such as those used by the HElib and SEAL homomorphic encryption libraries. However, these butterflies are not constant-time algorithms and may leak secret data when incorrectly implemented. Luckily for SEAL and HElib, the compilers optimize the code to run in constant-time. We claim that relying on the compiler is risky and demonstrate how a simple code modification can cause leakage, which can reduce the hardness of the ring learning with errors (R-LWE) instances used by these libraries, for example, from 2^128 to 2^104.
Andrej Bogdanov, Miguel Cueto Noval, Charlotte Hoffmann, Alon Rosen
The continuous learning with errors (CLWE) problem was recently introduced by Bruna et al. (STOC 2021). They showed that its hardness implies infeasibility of learning Gaussian mixture models, while its tractability implies efficient Discrete Gaussian Sampling and thus asymptotic improvements in worst-case lattice algorithms. No reduction between CLWE and LWE is currently known, in either direction.
We propose four public-key encryption schemes based on the hardness of CLWE, with varying tradeoffs between decryption and security errors, and different discretization techniques. Some of our schemes are based on hCLWE, a homogeneous variant, which is no easier than CLWE. Our schemes yield a polynomial-time algorithm for solving hCLWE, and hence also CLWE, using a Statistical Zero-Knowledge oracle.
N. Nalla Anandakumar, M. Sazadur Rahman, Mridha Md Mashahedur Rahman, Rasheed Kibria, Upoma Das, Farimah Farahmandi, Fahim Rahman, Mark M. Tehranipoor
Intellectual property (IP) cores are essential to creating modern system-on-chips (SoCs). Protecting the IPs deployed in modern SoCs has become more difficult as the IP houses have been established across the globe over the past three decades. The threat posed by IP piracy and overuse has been a topic of research for the past decade or so and has led to creation of a field called watermarking. IP watermarking aims of detecting unauthorized IP usage by embedding excess, nonfunctional circuitry into the SoC. Unfortunately, prior work has been built upon assumptions that cannot be met within the modern SoC design and verification processes. In this paper, we first provide an extensive overview of the current state-of-the-art IP watermarking. Then, we challenge these dated assumptions and propose a new path for future effective IP watermarking approaches suitable for today's complex SoCs in which IPs are deeply embedded.
Thomas Häner, Mathias Soeken
We determine the exact AND-gate cost of checking if $a\leq x < b$, where $a$ and $b$ are constant integers. Perhaps surprisingly, we find that the cost of interval checking never exceeds that of a single comparison and, in some cases, it is even lower.
30 January 2022
Visa Research, Palo Alto, CA
Visa Research is a team of world-class research scientists. Our mission is to conduct research on the most challenging problems in the payment industry and provide technical thought leadership for the company’s future. Visa Research engages with internal and external partners to identify and research critical ideas that may have an impact to the payment ecosystem. Our research agenda focuses on three key areas: Artificial Intelligence, Security, and the Future of Payments.
The Visa Research Advanced Cryptography team is seeking researchers in the following areas:
For further details and to apply on-line:
The Visa Research Advanced Cryptography team is seeking researchers in the following areas:
- Multi-Party Computation
- Fully Homomorphic Encryption/Lattice-Based Cryptography
- Zero-Knowledge Proofs
- Privacy-Preserving Machine Learning
- Digital Currencies
- Identity and Authentication
For further details and to apply on-line:
- newly graduated or soon to graduate: https://smrtr.io/7MtBQ
- all other applicants: https://smrtr.io/7R_bd
Closing date for applications:
Contact: Gaven Watson
More information: https://smrtr.io/7R_bd
COSIC, KU Leuven
COSIC is looking for motivated PhD students to work on the implementation aspects of post-quantum cryptographic algorithms:
Post-quantum cryptography is a new class of cryptographic algorithms, which resist attacks from quantum computers. They will mostly replace existing public key algorithms (RSA and ECC). Efficient implementations in hardware (FPGA, ASIC) are an essential aspect for their acceptance as replacement. On top, the implementations also need to resist physical attacks, e.g. side-channel and fault attacks.
This research position will focus on the efficient and attack resistant implementations of novel post-quantum cryptographic algorithms.
Closing date for applications:
Contact: ingrid.verbauwhede[at]esat.kuleuven.be
More information: https://www.esat.kuleuven.be/cosic/vacancies/
26 January 2022
Wollongong, Australia, 13 July - 17 July 2022
Event date: 13 July to 17 July 2022
Submission deadline: 7 February 2022
Notification: 15 April 2022
Submission deadline: 7 February 2022
Notification: 15 April 2022