Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2020 | Book

An Attack on Some Signature Schemes Constructed from Five-Pass Identification Schemes Read chapter Read first chapter

Cryptology and Network Security

19th International Conference, CANS 2020, Vienna, Austria, December 14–16, 2020, Proceedings

Editors: Stephan Krenn, Haya Shulman, Serge Vaudenay

Publisher: Springer International Publishing

Book Series : Lecture Notes in Computer Science

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

This book constitutes the refereed proceedings of the 19th International Conference on Cryptology and Network Security, CANS 2020, held in Vienna, Austria, in December 2020.*

The 30 full papers were carefully reviewed and selected from 118 submissions. The papers focus on topics such as cybersecurity; credentials; elliptic curves; payment systems; privacy-enhancing tools; lightweight cryptography; and codes and lattices.

*The conference was held virtually due to the COVID-19 pandemic.

Table of Contents

Frontmatter

Best Papers

Frontmatter
An Attack on Some Signature Schemes Constructed from Five-Pass Identification Schemes
Abstract
We present a generic forgery attack on signature schemes constructed from 5-round identification schemes made non-interactive with the Fiat-Shamir transform. The attack applies to ID schemes that use parallel repetition to decrease the soundness error. The attack can be mitigated by increasing the number of parallel repetitions, and our analysis of the attack facilitates parameter selection.
We apply the attack to MQDSS, a post-quantum signature scheme relying on the hardness of the MQ-problem. Concretely, forging a signature for the L1 instance of MQDSS, which should provide 128 bits of security, can be done in \(\approx \) \(2^{95}\) operations. We verify the validity of the attack by implementing it for round-reduced versions of MQDSS, and the designers have revised their parameter choices accordingly.
We also survey other post-quantum signature algorithms and find the attack succeeds against PKP-DSS (a signature scheme based on the hardness of the permuted kernel problem) and list other schemes that may be affected. Finally, we use our analysis to choose parameters and investigate the performance of a 5-round variant of the Picnic scheme.
Daniel Kales, Greg Zaverucha
Energy Analysis of Lightweight AEAD Circuits
Abstract
The selection criteria for NIST’s Lightweight Crypto Standardization (LWC) have been slowly shifting towards the lightweight efficiency of designs, given that a large number of candidates already establish their security claims on conservative, well-studied paradigms. The research community has accumulated a decent level of experience on authenticated encryption primitives, thanks mostly to the recently completed CAESAR competition, with the advent of the NIST LWC, the de facto focus is now on evaluating efficiency of the designs with respect to hardware metrics like area, throughput, power and energy.
In this paper, we focus on a less investigated metric under the umbrella term lightweight, i.e. energy consumption. Quantitatively speaking, energy is the sum total electrical work done by a voltage source and thus is a critical metric of lightweight efficiency. Among the thirty-two second round candidates, we give a detailed evaluation of the ten that only make use of a lightweight or semi-lightweight block cipher at their core. We use this pool of candidates to investigate a list of generic implementation choices that have considerable effect on both the size and the energy consumption of modes of operation circuit, which function as an authenticated encryption primitive.
In the second part of the paper, we shift our focus to threshold implementations that offer protection against first order power analysis attacks. There has been no study focusing on energy efficiency of such protected implementations and as such the optimizations involved in such circuits are not well established. We explore the simplest possible protected circuit: the one in which only the state path of the underlying block cipher is shared, and we explore how design choices like number of shares, implementation of the masked s-box and the circuit structure of the AEAD scheme affect the energy consumption.
Andrea Caforio, Fatih Balli, Subhadeep Banik
Cross-Site Search Attacks: Unauthorized Queries over Private Data
Abstract
Cross-site search attacks allow a rogue website to expose private, sensitive user-information from web applications. The attacker exploits timing and other side channels to extract the information, using cleverly-designed cross-site queries.
In this work, we present a systematic approach to the study of cross-site search attacks. We begin with a comprehensive taxonomy, clarifying the relationships between different types of cross-site search attacks, as well as relationships to other attacks. We then present, analyze, and compare cross-site search attacks; We present new attacks that have improved efficiency and can circumvent browser defenses, and compare to already-published attacks. We developed and present a reproducibility framework, which allows study and evaluation of different cross-site attacks and defenses.
We also discuss defenses against cross-site search attacks, for both browsers and servers. We argue that server-based defenses are essential, including restricting cross-site search requests.
Bar Meyuhas, Nethanel Gelernter, Amir Herzberg

Cybersecurity

Frontmatter
Stronger Targeted Poisoning Attacks Against Malware Detection
Abstract
Attacks on machine learning systems such as malware detectors and recommendation systems are becoming a major threat. Data poisoning attacks are the primary method used; they inject a small amount of poisoning points into a training set of the machine learning model, aiming to degrade the overall accuracy of the model. Targeted data poisoning is a variant of data poisoning attacks that injects malicious data into the model to cause a misclassification of the targeted input data while keeping almost the same overall accuracy as the unpoisoned model. Sasaki et al. first applied targeted data poisoning to malware detection and proposed an algorithm to generate poisoning points to misclassify targeted malware as goodware. Their algorithm achieved \(85\%\) an attack success rate by adding \(15\%\) poisoning points for malware dataset with continuous variables while restricting the increase in the test error on nontargeted data to at most \(10\%\). In this paper, we consider common defensive methods called data sanitization defenses, against targeted data poisoning and propose a defense-aware attack algorithm. Moreover, we propose a stronger targeted poisoning algorithm based on the theoretical analysis of the optimal attack strategy proposed by Steinhardt et al. The computational cost of our algorithm is much less than that of existing targeted poisoning algorithms. As a result, our new algorithm achieves a \(91\%\) attack success rate for malware dataset with continuous variables by adding the same \(15\%\) poisoning points and is approximately \(10^3\) times faster in terms of the computational time needed to generate poison data than Sasaki’s algorithm.
Shintaro Narisada, Shoichiro Sasaki, Seira Hidano, Toshihiro Uchibayashi, Takuo Suganuma, Masahiro Hiji, Shinsaku Kiyomoto
STDNeut: Neutralizing Sensor, Telephony System and Device State Information on Emulated Android Environments
Abstract
Sophisticated malware employs various emulation-detection techniques to bypass the dynamic analysis systems that are running on top of virtualized environments. Hence, a defense mechanism needs to be incorporated in emulation based analysis platforms to mitigate the emulation-detection strategies opted by malware. In this paper, first we design an emulation-detection library that has configurable capabilities ranging from basic to advanced detection techniques like distributed detection and GPS information. We use this library to arm several existing malware with different levels of emulation-detection capabilities and study the efficacy of anti-emulation-detection measures of well known emulator driven dynamic analysis frameworks. Furthermore, we propose STDNeut (Sensor, Telephony system, and Device state information Neutralizer) – a configurable anti-emulation-detection mechanism that defends against the basic as well as advanced emulation-detection techniques regardless of which layer of Android OS the attack is performed on. Finally, we perform various experiments to show the effectiveness of STDNeut. Experimental results show that STDNeut can effectively execute a malware without being detected as an emulated platform.
Saurabh Kumar, Debadatta Mishra, Biswabandan Panda, Sandeep K. Shukla
HMAC and “Secure Preferences”: Revisiting Chromium-Based Browsers Security
Abstract
Google disabled years ago the possibility to freely modify some internal configuration parameters, so options like silently (un)install browser extensions, changing the home page or the search engine were banned. This capability was as simple as adding/removing some lines from a plain text file called Secure Preferences file automatically created by Chromium the first time it was launched. Concretely, Google introduced a security mechanism based on a cryptographic algorithm named Hash-based Message Authentication Code (HMAC) to avoid users and applications other than the browser modifying the Secure Preferences file. This paper demonstrates that it is possible to perform browser hijacking, browser extension fingerprinting, and remote code execution attacks as well as silent browser extensions (un)installation by coding a platform-independent proof-of-concept changeware that exploits the HMAC, allowing for free modification of the Secure Preferences file. Last but not least, we analyze the security of the four most important Chromium-based browsers: Brave, Chrome, Microsoft Edge, and Opera, concluding that all of them suffer from the same security pitfall.
Pablo Picazo-Sanchez, Gerardo Schneider, Andrei Sabelfeld
Detecting Word Based DGA Domains Using Ensemble Models
Abstract
Domain Generation Algorithm (DGA) is a popular technique used by many malware developers in recent times. Nowadays, DGA is an evasive technique used by many of the Advanced Persistent Threat (APT) groups and Botnets to bypass host and network-level detection mechanisms. Legacy malware developers used to hard code the IP address of control and command server in malware payload. But, this led to identifying malicious IP address by reverse engineering the malware payload. Drawbacks in this hardcoding IP mechanism led to the idea of character-based Domain Generation Algorithms, where attackers generate a list of domain names using traditional cryptographic principles of pseudo-random number generators (PRNGs). Recent advances in malware research, machine learning address this problem to a large extent. Lately, malware developers came up with a new variant of DGA called word-list based DGA. In this approach, the malware uses a set of words from the dictionary to construct meaningful substrings that resembles real domain names. In this paper, we propose a new method for detecting Word-list based DGA domain names using ensemble approaches with 15 features (both lexical and network-level). Added to this, we generated syntactic data using CTGAN (GAN-based data synthesizer that can generate synthetic data) to measure the robustness of our model. In our experiment, C5.0 stands out as the best with prediction accuracy of 0.9503 and out of 30000 synthetically generated malicious domains names, 1351 classified as benign.
P. V. Sai Charan, Sandeep K. Shukla, P. Mohan Anand

Credentials

Frontmatter
Distance-Bounding, Privacy-Preserving Attribute-Based Credentials
Abstract
Distance-bounding anonymous credentials could be used for any location proofs that do not need to identify the prover and thus could make even notoriously invasive mechanisms such as location-based services privacy-preserving. There is, however, no secure distance-bounding protocol for general attribute-based anonymous credentials. Brands and Chaum’s (EUROCRYPT’93) protocol combining distance-bounding and Schnorr identification comes close, but does not fulfill the requirements of modern distance-bounding protocols. For that, we need a secure distance-bounding zero-knowledge proof-of-knowledge resisting mafia fraud, distance fraud, distance hijacking and terrorist fraud.
Our approach is another attempt toward combining distance bounding and Schnorr to construct a distance-bounding zero-knowledge proof-of-knowledge. We construct such a protocol and prove it secure in the (extended) DFKO model for distance bounding. We also performed a symbolic verification of security properties needed for resisting these attacks, implemented in Tamarin.
Encouraged by results from Singh et al. (NDSS’19), we take advantage of lessened constraints on how much can be sent in the fast phase of the distance-bounding protocol and achieve a more efficient protocol. We also provide a version that does not rely on being able to send more than one bit at a time which yields the same properties except for (full) terrorist fraud resistance.
Daniel Bosk, Simon Bouget, Sonja Buchegger
Trenchcoat: Human-Computable Hashing Algorithms for Password Generation
Abstract
The average user has between 90–130 online accounts [17], and around \(3\times 10^{11}\) passwords are in use this year [10]. Most people are terrible at remembering “random” passwords, so they reuse or create similar passwords using a combination of predictable words, numbers, and symbols [16]. Previous password-generation or management protocols have imposed so large a cognitive load that users have abandoned them in favor of insecure yet simpler methods (e.g., writing them down or reusing minor variants).
We describe a range of candidate human-computable “hash” functions suitable for use as password generators - as long as the human (with minimal education assumptions) keeps a single, easily-memorizable ‘master’ secret - and rate them by various metrics, including effective security. These functions hash master-secrets with user accounts to produce sub-secrets that can be used as passwords; \(F_R(\)s\(, w) \longrightarrow y\), which takes a website w and produces a password y, parameterized by the master secret s, which may or may not be a string.
We exploit the unique configuration R of each user’s associative and implicit memory (detailed in Sect. 2) to ensure that sources of randomness unique to each user are present in each F. An adversary cannot compute or verify \(F_R\) efficiently since R is unique to each individual; in that sense, our hash function is similar to a physically unclonable function [37]. For the algorithms we propose, the user need only complete primitive operations such as addition, spatial navigation or searching. Critically, most of our methods are also accessible to neurodiverse, or cognitively or physically differently-abled persons.
Given the nature of these functions, it is not possible to directly use traditional cryptographic methods for analysis; so, we use an array of approaches, mainly related to entropy, to illustrate and analyze the same. We draw on cognitive, neuroscientific, and cryptographic research to use these functions as improved password management and creation systems, and present results from a survey (n = 134 individuals, with each candidate performing 2 schemes) investigating real-world usage of these methods and how people currently come up with their passwords. We also survey 400 websites to collate current password advice.
Ruthu Hulikal Rooparaghunath, T. S. Harikrishnan, Debayan Gupta
Provably Secure Scalable Distributed Authentication for Clouds
Abstract
One of the most used authentication methods is based on short secrets like password, where usually the hash of the secrets are stored in a central database. In case of server compromise the secrets are vulnerable to theft. A possible solution to this problem to apply distributed systems. We propose a mutual authentication protocol with key agreement, where identity verification is carried out by multiple servers applying secret sharing technology on server side. The protocol results in a session key which provides the confidentiality of the later messages between the participants. In our solution we also achieve robustness and scalability as well. To show that the proposed protocol is provably secure, we apply the threshold hybrid corruption model. We assume that among the randomly chosen k servers, there is always at least one uncorrupted and the authentication server reveals at most the long-lived keys. We prove that the protocol is secure in the random oracle model, if Message Authentication Code (MAC) is universally unforgeable under an adaptive chosen-message attack, the symmetric encryption scheme is indistinguishable under chosen plaintext attack, moreover Elliptic Curve Computational Diffie-Hellman assumption holds in the elliptic curve group.
Andrea Huszti, Norbert Oláh
Forward-Secure 0-RTT Goes Live: Implementation and Performance Analysis in QUIC
Abstract
Modern cryptographic protocols, such as TLS 1.3 and QUIC, can send cryptographically protected data in “zero round-trip times (0-RTT)”, that is, without the need for a prior interactive handshake. Such protocols meet the demand for communication with minimal latency, but those currently deployed in practice achieve only rather weak security properties, as they may not achieve forward security for the first transmitted payload message and require additional countermeasures against replay attacks.
Recently, 0-RTT protocols with full forward security and replay resilience have been proposed in the academic literature. These are based on puncturable encryption, which uses rather heavy building blocks, such as cryptographic pairings. Some constructions were claimed to have practical efficiency, but it is unclear how they compare concretely to protocols deployed in practice, and we currently do not have any benchmark results that new protocols can be compared with.
We provide the first concrete performance analysis of a modern 0-RTT protocol with full forward security, by integrating the Bloom Filter Encryption scheme of Derler et al. (EUROCRYPT 2018) in the Chromium QUIC implementation and comparing it to Google’s original QUIC protocol. We find that for reasonable deployment parameters, the server CPU load increases approximately by a factor of eight and the memory consumption on the server increases significantly, but stays below 400 MB even for medium-scale deployments that handle up to 50K connections per day. The difference of the size of handshake messages is small enough that transmission time on the network is identical, and therefore not significant.
We conclude that while current 0-RTT protocols with full forward security come with significant computational overhead, their use in practice is feasible, and may be used in applications where the increased CPU and memory load can be tolerated in exchange for full forward security and replay resilience on the cryptographic protocol level. Our results serve as a first benchmark that can be used to assess the efficiency of 0-RTT protocols potentially developed in the future.
Fynn Dallmeier, Jan P. Drees, Kai Gellert, Tobias Handirk, Tibor Jager, Jonas Klauke, Simon Nachtigall, Timo Renzelmann, Rudi Wolf

Elliptic Curves

Frontmatter
Semi-commutative Masking: A Framework for Isogeny-Based Protocols, with an Application to Fully Secure Two-Round Isogeny-Based OT
Abstract
We define semi-commutative invertible masking structures which aim to capture the methodology of exponentiation-only protocol design (such as discrete logarithm and isogeny-based cryptography). We give an instantiation based on the semi-commutative action of isogenies of supersingular elliptic curves, in the style of the SIDH key-exchange protocol. We then construct an oblivious transfer protocol using this new structure and prove that it UC-securely realises the oblivious transfer functionality in the random-oracle-hybrid model against passive adversaries with static corruptions. Moreover, we show that it satisfies the security properties required by the compiler of Döttling et al. (Eurocrypt 2020), achieving the first fully UC-secure two-round OT protocol based on supersingular isogenies.
Cyprien Delpech de Saint Guilhem, Emmanuela Orsini, Christophe Petit, Nigel P. Smart
Optimized and Secure Pairing-Friendly Elliptic Curves Suitable for One Layer Proof Composition
Abstract
A zero-knowledge proof is a method by which one can prove knowledge of general non-deterministic polynomial (NP) statements. SNARKs are in addition non-interactive, short and cheap to verify. This property makes them suitable for recursive proof composition, that is proofs attesting to the validity of other proofs. To achieve this, one moves the arithmetic operations to the exponents. Recursive proof composition has been empirically demonstrated for pairing-based SNARKs via tailored constructions of expensive pairing-friendly elliptic curves namely a pair of 753-bit MNT curves, so that one curve’s order is the other curve’s base field order and vice-versa. The ZEXE construction restricts to one layer proof composition and uses a pair of curves, BLS12-377 and CP6-782, which improve significantly the arithmetic on the first curve. In this work we construct a new pairing-friendly elliptic curve to be used with BLS12-377, which is STNFS-secure and fully optimized for one layer composition. We propose to name the new curve BW6-761. This work shows that it is at least five times faster to verify a composed SNARK proof on this curve compared to the previous state-of-the-art, and proposes an optimized Rust implementation that is almost thirty times faster than the one available in ZEXE library.
Youssef El Housni, Aurore Guillevic
Curves with Fast Computations in the First Pairing Group
Abstract
Pairings are a powerful tool to build advanced cryptographic schemes. The most efficient way to instantiate a pairing scheme is through Pairing-Friendly Elliptic Curves.
Because a randomly picked elliptic curve will not support an efficient pairing (the embedding degree will usually be too large to make any computation practical), a pairing-friendly curve has to be carefully constructed. This has led to famous curves, e.g. Barreto-Naehrig curves.
However, the computation of the Discrete Logarithm Problem on the finite-field side has received much interest and its complexity has recently decreased. Hence the need to propose new curves has emerged.
In this work, we give one new curve that is specifically tailored to be fast over the first pairing-group, which is well suited for several cryptographic schemes, such as group signatures, and their variants, or accumulators.
Rémi Clarisse, Sylvain Duquesne, Olivier Sanders
Revisiting ECM on GPUs
Abstract
Modern public-key cryptography is a crucial part of our contemporary life where a secure communication channel with another party is needed. With the advance of more powerful computing architectures – especially Graphics Processing Units (GPUs) – traditional approaches like RSA and Diffie-Hellman schemes are more and more in danger of being broken.
We present a highly optimized implementation of Lenstra’s ECM algorithm customized for GPUs. Our implementation uses state-of-the-art elliptic curve arithmetic and optimized integer arithmetic while providing the possibility of arbitrarily scaling ECM’s parameters allowing an application even for larger discrete logarithm problems. Furthermore, the proposed software is not limited to any specific GPU generation and is to the best of our knowledge the first implementation supporting multiple device computation. To this end, for a bound of \(B_1 = {8 192}\) and a modulus size of 192 bit, we achieve a throughput of 214 thousand ECM trials per second on a modern RTX 2080 Ti GPU considering only the first stage of ECM. To solve the Discrete Logarithm Problem for larger bit sizes, our software can easily support larger parameter sets such that a throughput of 2 781 ECM trials per second is achieved using \(B_1={50\, 000}\), \(B_2 = {5\, 000\, 000}\), and a modulus size of 448 bit.
Jonas Wloka, Jan Richter-Brockmann, Colin Stahlke, Thorsten Kleinjung, Christine Priplata, Tim Güneysu

Payment Systems

Frontmatter
Arcula: A Secure Hierarchical Deterministic Wallet for Multi-asset Blockchains
Abstract
This work presents Arcula, a new design for hierarchical deterministic wallets that brings identity-based public keys to the blockchain. Arcula is built on top of provably secure cryptographic primitives. It generates all its cryptographic secrets from a user-provided seed and enables the derivation of new public keys based on the identities of users, without requiring any secret information. Unlike other wallets, it achieves all these properties while being secure against privilege escalation. We formalize the security model of hierarchical deterministic wallets and prove that an attacker compromising an arbitrary number of users within an Arcula wallet cannot escalate his privileges and compromise users higher in the access hierarchy. Our design works out-of-the-box with any blockchain that enables the verification of signatures on arbitrary messages. We evaluate its usage in a real-world scenario on the Bitcoin Cash network.
Adriano Di Luzio, Danilo Francati, Giuseppe Ateniese
Detecting Covert Cryptomining Using HPC
Abstract
Cybercriminals have been exploiting cryptocurrencies to commit various unique financial frauds. Covert cryptomining - which is defined as an unauthorized harnessing of victims’ computational resources to mine cryptocurrencies - is one of the prevalent ways nowadays used by cybercriminals to earn financial benefits. Such exploitation of resources causes financial losses to the victims.
In this paper, we present our efficient approach to detect covert cryptomining on users’ machine. Our solution is a generic solution that, unlike currently available solutions to detect covert cryptomining, is not tailored to a specific cryptocurrency or a particular form of cryptomining. In particular, we focus on the core mining algorithms and utilize Hardware Performance Counters (HPC) to create clean signatures that grasp the execution pattern of these algorithms on a processor. We built a complete implementation of our solution employing advanced machine learning techniques. We evaluated our methodology on two different processors through an exhaustive set of experiments. In our experiments, we considered all the cryptocurrencies mined by the top-10 mining pools, which collectively represent the largest share of the cryptomining market. Our results show that our classifier can achieve a near-perfect classification with samples of length as low as five seconds. Due to its robust and practical design, our solution can even adapt to zero-day cryptocurrencies. Finally, we believe our solution is scalable and can be deployed to tackle the uprising problem of covert cryptomining.
Ankit Gangwal, Samuele Giuliano Piazzetta, Gianluca Lain, Mauro Conti
Lightweight Virtual Payment Channels
Abstract
Blockchain systems have severe scalability limitations e.g., long confirmation delays. Layer-2 protocols are designed to address such limitations. The most prominent class of such protocols are payment channel networks e.g., the Lightning Network for Bitcoin where pairs of participants create channels that can be concatenated into networks. These allow payments across the network without interaction with the blockchain. A drawback is that all intermediary nodes within a payment path must be online. Virtual Channels, as recently proposed by Dziembowski et al. (CCS’18), allow payments without this limitation. However, these can only be implemented on blockchains with smart contract capability therefore limiting its applicability. Our work proposes the notion of –Lightweight– Virtual Payment Channels, i.e. only requiring timelocks and multisignatures, enabling Virtual Channels on a larger range of blockchain systems of which a prime example is Bitcoin. More concretely, other contributions of this work are (1) to introduce a fully-fledged formalization of our construction, and (2) to present a simulation based proof of security in Canetti’s UC Framework.
Maxim Jourenko, Mario Larangeira, Keisuke Tanaka

Privacy-Enhancing Tools

Frontmatter
Chosen-Ciphertext Secure Multi-identity and Multi-attribute Pure FHE
Abstract
A multi-identity pure fully homomorphic encryption (MIFHE) enables a server to perform arbitrary computation on the ciphertexts that are encrypted under different identities. In case of multi-attribute pure FHE (MAFHE), the ciphertexts are associated with different attributes. Clear and McGoldrick (CANS 2014) gave the first chosen-plaintext attack secure MIFHE and MAFHE based on indistinguishability obfuscation. In this study, we focus on building MIFHE and MAFHE which are secure under type 1 of chosen-ciphertext attack (CCA1) security model. In particular, using witness pseudorandom functions (Zhandry, TCC 2016) and multi-key pure FHE or MFHE (Mukherjee and Wichs, EUROCRYPT 2016) we propose the following constructions:
  • CCA secure identity-based encryption (IBE) that enjoys an optimal size ciphertexts, which we extend to a CCA1 secure MIFHE scheme.
  • CCA secure attribute-based encryption (ABE) having an optimal size ciphertexts, which we transform into a CCA1 secure MAFHE scheme.
By optimal size, we mean that the bit-length of a ciphertext is the bit-length of the message plus a security parameter multiplied with a constant. Known constructions of multi-identity(attribute) FHEs are either leveled, that is, support only bounded depth circuit evaluations or secure in a weaker CPA security model. With our new approach, we achieve both CCA1 security and evaluation on arbitrary depth circuits for multi-identity(attribute) FHE schemes.
Tapas Pal, Ratna Dutta
Linear Complexity Private Set Intersection for Secure Two-Party Protocols
Abstract
In this paper, we propose a new private set intersection (PSI) protocol with bi-oblivious data transfer that computes the following functionality. The two parties (\(P_1\) and \(P_2\)) input two sets of items (X and Y, respectively) and one of the parties (\(P_2\)) outputs \(f_i(b_i)\) for each \(y_i \in Y\), where \(b_i\) is 0 or 1 depending on the truth value of \(y_i {\mathop {\in }\limits ^{?}} X\) and \(f_i\) is defined by the other party (\(P_1\)) as taking 1-bit input and outputting the party’s (\(P_1\)’s) data to be transferred. This functionality is generally required when the PSI protocol is used as a part of a larger secure two-party secure computation such as threshold PSI or any function of the whole intersecting set in general. Pinkas et al. presented a PSI protocol at Eurocrypt 2019 for this functionality, which has linear complexity only in communication. While there are PSI protocols with linear computation and communication complexities in the classical PSI setting where the intersection itself is revealed to one party, to the best of our knowledge, there is no PSI protocol, which outputs a function of the membership results and satisfies linear complexity in both communication and computation. We present the first PSI protocol that outputs only a function of the membership results with linear communication and computation complexities. While creating the protocol, as a side contribution, we provide a one-time batch oblivious programmable pseudo-random function based on garbled Bloom filters. We also implemented our protocol and provide performance results.
Ferhat Karakoç, Alptekin Küpçü
Compact Multi-Party Confidential Transactions
Abstract
“Confidential Transactions”, integrated transactions of commitments, signatures, and zero-knowledge range proofs, are favored for their ability to hide transaction amounts. In the real world, multi-party fund transfers are highly desirable for personal and business security. Unfortunately, existing unproven Multi-Party Confidential Transactions are linear in the (exact) number of co-owners; hence they are not compact, very scalable, nor private (leak number of users and their public information). In this study, we provide provably secure private, compact Multi-Party Confidential Transactions, in both the “unanimous” N-out-of-N and “threshold” T-out-of-N settings. Unlike other schemes, our multi-party transactions have the size of single-owner transactions and hide the number of participants. To the best of our knowledge, ours is the first proven secure multi-party and threshold confidential transaction protocol.
Jayamine Alupotha, Xavier Boyen, Ernest Foo
Simulation Extractable Versions of Groth’s zk-SNARK Revisited
Abstract
Among various NIZK arguments, zk-SNARKs are the most efficient constructions in terms of proof size and verification which are two critical criteria for large scale applications. Currently, Groth’s construction, \(\textsf {Groth16}\), from Eurocrypt’16 is the most efficient and widely deployed one. However, it is proven to achieve only knowledge soundness, which does not prevent attacks from the adversaries who have seen simulated proofs. There has been considerable progress in modifying \(\textsf {Groth16}\) to achieve simulation extractability to guarantee the non-malleability of proofs. We revise the Simulation Extractable (SE) version of \(\textsf {Groth16}\) proposed by Bowe and Gabizon that has the most efficient prover and \(\mathsf {crs}\) size among the candidates, although it adds Random Oracle (RO) to the original construction. We present a new version which requires 4 parings in the verification, instead of 5. We also get rid of the RO at the cost of a collision resistant hash function and a single new element in the \(\mathsf {crs}\). Our construction is proven in the generic group model and seems to result in the most efficient SE variant of \(\textsf {Groth16}\) in most dimensions.
Karim Baghery, Zaira Pindado, Carla Ràfols
Efficient Composable Oblivious Transfer from CDH in the Global Random Oracle Model
Abstract
Oblivious Transfer (OT) is a fundamental cryptographic protocol that finds a number of applications, in particular, as an essential building block for two-party and multi-party computation. We construct the first universally composable (UC) protocol for oblivious transfer secure against active static adversaries based on the Computational Diffie-Hellman (CDH) assumption. Our protocol is proven secure in the observable Global Random Oracle model. We start by constructing a protocol that realizes an OT functionality with a selective failure issue, but shown to be sufficient to instantiate efficient OT extension protocols. In terms of complexity, this protocol only requires the computation of 6 modular exponentiations and the communication of 5 group elements, five binary strings of security parameter length, and two binary strings of message length. Finally, we lift this weak construction to obtain a protocol that realizes the standard OT functionality (without any selective failures) at an additional cost of computing 9 modular exponentiations and communicating 4 group elements, four binary strings of security parameter length and two binary strings of message length. As an intermediate step before constructing our CDH based protocols, we design generic OT protocols from any OW-CPA secure public-key encryption scheme with certain properties, which could potentially be instantiated from more assumptions other than CDH.
Bernardo David, Rafael Dowsley

Lightweight Cryptography

Frontmatter
Integral Cryptanalysis of Reduced-Round Tweakable TWINE
Abstract
Tweakable TWINE (T-TWINE) is the first lightweight dedicated tweakable block cipher family built on Generalized Feistel Structure (GFS). T-TWINE family is an extension of the conventional block cipher TWINE with minimal modification by adding a simple tweak based on the SKINNY’s tweakey schedule. Similar to TWINE, T-TWINE has two variants, namely T-TWINE-80 and T-TWINE-128. The two variants have the same block size of 64 bits and a variable key length of 80 and 128 bits. In this paper, we study the implications for adding the tweak on the security of T-TWINE against the integral cryptanalysis. In particular, we first utilize the bit-based division property to search for the longest integral distinguisher. As a result, we are able to perform a distinguishing attack against 19 rounds using \(2^{6} \times 2^{63} = 2^{69}\) chosen tweak-plaintext combinations. We then convert this attack to key recovery attacks against 26 and 27 rounds (out of 36) of T-TWINE-80 and T-TWINE-128, respectively. By prepending one round before the distinguisher and using dynamically chosen plaintexts, we manage to extend the attack one more round without using the full codebook of the plaintext. Therefore, we are able to attack 27 and 28 rounds of T-TWINE-80 and T-TWINE-128, respectively.
Muhammad ElSheikh, Amr M. Youssef
RiCaSi: Rigorous Cache Side Channel Mitigation via Selective Circuit Compilation
Abstract
Cache side channels constitute a persistent threat to crypto implementations. In particular, block ciphers are prone to attacks when implemented with a simple lookup-table approach. Implementing crypto as software evaluations of circuits avoids this threat but is very costly.
We propose an approach that combines program analysis and circuit compilation to support the selective hardening of regular C implementations against cache side channels. We implement this approach in our toolchain RiCaSi. RiCaSi avoids unnecessary complexity and overhead if it can derive sufficiently strong security guarantees for the original implementation. If necessary, RiCaSi produces a circuit-based, hardened implementation. For this, it leverages established circuit-compilation technology from the area of secure computation. A final program analysis step ensures that the hardening is, indeed, effective.
Heiko Mantel, Lukas Scheidel, Thomas Schneider, Alexandra Weber, Christian Weinert, Tim Weißmantel
Assembly or Optimized C for Lightweight Cryptography on RISC-V?
Abstract
A major challenge when applying cryptography on constrained environments is the trade-off between performance and security. In this work, we analyzed different strategies for the optimization of several candidates of NIST’s lightweight cryptography standardization project on a RISC-V architecture. In particular, we studied the general impact of optimizing symmetric-key algorithms in assembly and in plain C. Furthermore, we present optimized implementations, achieving a speed-up of up to 81% over available implementations, and discuss general implementation strategies.
Fabio Campos, Lars Jellema, Mauk Lemmen, Lars Müller, Amber Sprenkels, Benoit Viguier

Codes and Lattices

Frontmatter
Attack on LAC Key Exchange in Misuse Situation
Abstract
LAC is a Ring Learning With Error based cryptosystem that has been proposed to the NIST call for post-quantum standardization and passed the first round of the submission process. The particularity of LAC is to use an error-correction code ensuring a high security level with small key sizes and small ciphertext sizes. LAC team proposes a CPA secure cryptosystem, LAC.CPA, and a CCA secure one, LAC.CCA, obtained by applying the Fujisaki-Okamoto transformation on LAC.CPA. In this paper, we study the security of LAC Key Exchange (KE) mechanism, using LAC.CPA, in a misuse context: when the same secret key is reused for several key exchanges and an active adversary has access to a mismatch oracle. This oracle indicates information on the possible mismatch at the end of the KE protocol. In this context, we show that an attacker needs at most 8 queries to the oracle to retrieve one coefficient of a static secret key. This result has been experimentally confirmed using the reference and optimized implementations of LAC. Since our attack can break the CPA version in a misuse context, the Authenticated KE protocol, based on the CCA version, is not impacted. However, this research provides a tight estimation of LAC resilience against this type of attacks.
Aurélien Greuet, Simon Montoya, Guénaël Renault
Enhancing Code Based Zero-Knowledge Proofs Using Rank Metric
Abstract
The advent of quantum computers is a threat to most currently deployed cryptographic primitives. Among these, zero-knowledge proofs play an important role, due to their numerous applications. The primitives and protocols presented in this work base their security on the difficulty of solving the Rank Syndrome Decoding (RSD) problem. This problem is believed to be hard even in the quantum model. We first present a perfectly binding commitment scheme. Using this scheme, we are able to build an interactive zero-knowledge proof to prove: the knowledge of a valid opening of a committed value, and that the valid openings of three committed values satisfy a given linear relation, and, more generally, any bitwise relation. With the above protocols it becomes possible to prove the relation of two committed values for an arbitrary circuit, with quasi-linear communication complexity and a soundness error of 2/3. To our knowledge, this is the first quantum resistant zero-knowledge protocol for arbitrary circuits based on the RSD problem. An important contribution of this work is the selection of a set of parameters, and an a full implementation, both for our proposal in the rank metric and for the original LPN based one by Jain et al. in the Hamming metric, from which we took the inspiration. Beside demonstrating the practicality of both constructions, we provide evidence of the convenience of rank metric, by reporting performance benchmarks and a detailed comparison.
Emanuele Bellini, Philippe Gaborit, Alexandros Hasikos, Victor Mateu
A Secure Algorithm for Rounded Gaussian Sampling
Abstract
Presented in this paper is a new Gaussian sampler targeted at lattice-based signatures. It is the first secure algorithm for implementing the Box-Muller Gaussian sampling algorithm, which produces continuous Gaussian samples. The samples can be made discrete by rounding and this method has recently been shown to suffice for the purpose of discrete Gaussian sampling for lattice-based signatures. Rounded Gaussians allow quick transformations from samples of low standard deviation to samples with a high standard deviation. This makes them well-suited to producing the wide distributions needed for the target primitives. Current state-of-the-art methods sample wide distributions with multiple samples from a narrow distribution, joined by a convolution algorithm, for each single sample. The number of required samples per output sample grows with the width of the distribution. The rounded Gaussian method allows sampling wide distributions with complexity which is constant with increasing standard deviation. The main contribution of the work is a novel, low-memory algorithm, based on the CORDIC family of algorithms, for the fixed-point and secure evaluation of the elementary functions necessary for the Box-Muller continuous sampling method. It is the first secure, continuous sampler for the production of rounded Gaussian distributions. A proof-of-concept implementation of the algorithm is used to demonstrate that Box-Muller sampling is a competitive alternative to sampling the discrete Gaussian distribution, for lattice-based signatures.
Séamus Brannigan, Maire O’Neill, Ayesha Khalid, Ciara Rafferty
Accelerating Lattice Based Proxy Re-encryption Schemes on GPUs
Abstract
Proxy Re-Encryption (PRE) is an indispensable tool in many public-key cryptographic schemes that enables users to delegate decryption rights to other users via a proxy. In this work, we present a high performance implementation of PRE schemes on NVIDIA GPUs. We target two lattice based PRE schemes, BV-PRE and Ring-GSW PRE defined over polynomial rings. We design a parallel Number Theoretic Transform (NTT) procedure capable of working on arbitrary precision moduli (in CRT form) and demonstrate several low level and GPU optimizations techniques to accelerate the PRE schemes.
For the same or higher security settings our results show 39x to 228x factors of improvement in performance with a peak throughput of 6.3 Mbps when compared to the CPU implementation of the BV-PRE scheme in the PALISADE lattice crypto software library. Similarly, for the Ring-GSW PRE scheme we achieve a peak throughput of 49 Mbps and up to 11x improvement in performance.
Gyana Sahu, Kurt Rohloff
Backmatter
Metadata
Title
Cryptology and Network Security
Editors
Stephan Krenn
Haya Shulman
Serge Vaudenay
Copyright Year
2020
Electronic ISBN
978-3-030-65411-5
Print ISBN
978-3-030-65410-8
DOI
https://doi.org/10.1007/978-3-030-65411-5

Premium Partner

    Image Credits