International Association
for Cryptologic Research

We study the round complexity of zero-knowledge for QMA (the quantum analogue of NP). Assuming the quantum quasi-polynomial hardness of the learning with errors (LWE) problem, we obtain the following results: - 2-Round statistical witness indistinguishable (WI) arguments for QMA. - 4-Round statistical zero-knowledge arguments for QMA in the plain model, additionally assuming the existence of quantum fully homomorphic encryption. This is the first protocol for constant-round statistical zero-knowledge arguments for QMA. - 2-Round computational (statistical, resp.) zero-knowledge for QMA in the timing model, additionally assuming the existence of post-quantum non-parallelizing functions (time-lock puzzles, resp.).

All of these protocols match the best round complexity known for the corresponding protocols for NP with security against classical adversaries. Along the way, we introduce and construct the notions of sometimes-extractable oblivious transfer and sometimes-simulatable zero-knowledge, which might be of independent interest.

Encrypted databases systems and searchable encryption schemes still leak critical information (e.g.: access patterns) and require a choice between privacy and efficiency. We show that using ORAM schemes as a black-box is not a panacea and that optimizations are still possible by improving the data structures. We design an ORAM-based secure database that is built from the ground up: we replicate the typical data structure of a database system using different optimized ORAM constructions and derive a new solution for oblivious searches on databases. Our construction has a lower bandwidth overhead than state-of-the-art ORAM constructions by moving client-side computations to a proxy with an intermediate (rigorously defined) level of trust, instantiated as a server-side isolated execution environment. We formally prove the security of our construction and show that its access patterns depend only on public information. We also provide an implementation compatible with SQL databases (PostgresSQL). Our system is 1.2 times to 4 times faster than state-of-the-art ORAM-based solutions.

Stake-based multiparty cryptographic primitives operate in a setting where participants are associated with their stake, security is argued against an adversary that is bounded by the total stake it possesses —as opposed to number of parties— and we are interested in scalability, i.e., the complexity of critical operations depends only logarithmically in the number of participants (that are assumed to be numerous).

In this work we put forth a new stake-based primitive, stake-based threshold multisignatures (STM, or “Mithril” signatures), which allows the aggregation of individual signatures into a compact multisignature pro- vided the stake that supports a given message exceeds a stake threshold. This is achieved by having for each message a pseudorandomly sampled subset of participants eligible to issue an individual signature; this ensures the scalability of signing, aggregation and verification.

We formalize the primitive in the universal composition setting and propose efficient constructions for STMs. We also showcase that STMs are eminently useful in the cryptocurrency setting by providing two applications: (i) stakeholder decision-making for Proof of Work (PoW) blockchains, specifically, Bitcoin, and (ii) fast bootstrapping for Proof of Stake (PoS) blockchains.

The celebrated PCP Theorem states that any language in NP can be decided via a verifier that reads $O(1)$ bits from a polynomially long proof. Interactive oracle proofs (IOP), a generalization of PCPs, allow the verifier to interact with the prover for multiple rounds while reading a small number of bits from each prover message. While PCPs are relatively well understood, the power captured by IOPs (beyond NP) has yet to be fully explored.

We present a generalization of the PCP theorem for interactive languages. We show that any language decidable by a $k(n)$-round IP has a $k(n)$-round public-coin IOP, where the verifier makes its decision by reading only $O(1)$ bits from each (polynomially long) prover message and $O(1)$ bits from each of its own (random) messages to the prover. Our proof relies on a new notion of PCPs that we construct called index-decodable PCPs, which may be of independent interest.

We are then able to bring transformations that previously applied only for IPs into the realm of IOPs. We show IOP-to-IOP transformations that preserve query complexity and achieve: (i) private-coins to public-coins; (ii) round reduction; and (iii) imperfect to perfect completeness.

Principal component analysis(PCA) is one of the most pop-ular linear dimensionality reduction techniques in machine learning. Inthis paper, we try to present a method for performing PCA on encrypted data using a homomorphic encryption scheme. In a client-server model where the server performs computations on the encrypted data,it (server) does not require to perform any matrix operations like multiplication, inversion, etc. on the encrypted data. This reduces the number of computations significantly since matrix operations on encrypted data are very computationally expensive. For our purpose, we used the CKKS homomorphic encryption scheme since it is most suitable for machine learning tasks allowing approximate computations on real numbers.We also present the experimental results of our proposed Homomorphic PCA(HPCA) algorithm on a few datasets. We measure the R2 score on the reconstructed data and use it as an evaluation metric for our HPCA algorithm.

Solving a polynomial system over a finite field is an NP-complete problem of fundamental importance in both pure and applied mathematics. In~particular, the security of the so-called multivariate public-key cryptosystems, such as HFE of Patarin and UOV of Kipnis et~al., is based on the postulated hardness of solving quadratic polynomial systems over a finite field. Lokshtanov et al.~(2017) were the first to introduce a probabilistic algorithm that, in the worst-case, solves a Boolean polynomial system in time $O^{*}(2^{\delta n})$, for some $\delta \in (0, 1)$ depending only on the degree of the system, thus beating the brute-force complexity $O^{*}(2^n)$. Later, B\"jorklund et al.~(2019) and then Dinur~(2021) improved this method and devised probabilistic algorithms with a smaller exponent coefficient $\delta$.

We survey the theory behind these probabilistic algorithms, and we illustrate the results that we obtained by implementing them in C. In~particular, for random quadratic Boolean systems, we estimate the practical complexities of the algorithms and their probabilities of success as their parameters change.

Event date: to
Submission deadline: 29 October 2021
Notification: 20 May 2022

Applications are invited from Indian Nationals (bright candidates) for the recruitment of four (04) Research Associates purely on a temporary basis in the Applied Statistics Division of the Indian Statistical Institute. Ph.D. with research work in Cryptology and related areas are encouraged to apply. For details please visit https://www.isical.ac.in/jobs

Closing date for applications:

Contact: Mridul Nandi (pnc.asd.isi@gmail.com)

More information: https://www.isical.ac.in/sites/default/files/jobs/Advertisement%20-%20ASD.pdf

We offer a post-doctoral position until end of August 2023 in the area of side channels as part of the ERC funded project SEAL (Sound and Early Assessment of Leakage for Embedded Software) .

Under the supervision of Prof. Elisabeth Oswald, you will strengthen the existing team of three post-docs and one PhD student working on the SEAL project.

We are looking, in particular, for post docs with an interest in provable leakage resilience, or language/compiler based security (in an embedded software context), but we will consider researchers with a different interest within the side channel area too. You must have prior expertise in side channel related research (or compiler/language based security) (evidenced via papers).

The post will be filled as soon as a viable candidate has been identified.

The Cybersecurity Research group is part of a newly established, vibrant research environment in the sunny south of Austria. We are a team of 10 researchers working across a range of topics in the area of applied cryptography/cybersecurity. You can find an overview of team members, and activities under www.cybersecurityresearch.at.

To apply, please email your CV, and a brief statement why you think you fit the description to the contact below.

For questions, please use the same contact, supplied below.

Closing date for applications:

Contact: Elisabeth Oswald, elisabeth . oswald @ aau . at

Event date: 1 December to 3 December 2021
Submission deadline: 27 August 2021
Notification: 5 November 2021

This paper proves, for two examples of a randomized ROM PKE C, that derandomizing C degrades ROM OW-CPA security by a factor close to the number of hash queries. The first example can be explained by the size of the message space of C but the second cannot. This paper also gives a concrete example of a randomized non-ROM PKE C that appears to have the same properties regarding known attacks.

Blockchain as an enabler to current Internet infrastructure has provided many unique features and revolutionized current distributed systems into a new era. Its decentralization, immutability, and transparency have attracted many applications to adopt the design philosophy of blockchain and customize various replicated solutions. Under the hood of blockchain, consensus protocols play the most important role to achieve distributed replication systems. The distributed system community has extensively studied the technical components of consensus to reach agreement among a group of nodes. Due to trust issues, it is hard to design a resilient system in practical situations because of the existence of various faults. Byzantine fault-tolerant (BFT) state machine replication (SMR) is regarded as an ideal candidate that can tolerate arbitrary faulty behaviors. However, the inherent complexity of BFT consensus protocols and their rapid evolution makes it hard to practically adapt themselves into application domains. There are many excellent Byzantine-based replicated solutions and ideas that have been contributed to improving performance, availability, or resource efficiency. This paper conducts a systematic and comprehensive study on BFT consensus protocols with a specific focus on the blockchain era. We explore both general principles and practical schemes to achieve consensus under Byzantine settings. We then survey, compare, and categorize the state-of-the-art solutions to understand BFT consensus in detail. For each representative protocol, we conduct an in-depth discussion of its most important architectural building blocks as well as the key techniques they used. We aim that this paper can provide system researchers and developers a concrete view of the current design landscape and help them find solutions to concrete problems. Finally, we present several critical challenges and some potential research directions to advance the research on exploring BFT consensus protocols in the age of blockchains.

The 2014 European eIDAS regulation regulates strong electronic authentication and legally binding electronic signatures. Both require user "sole control". Historically smartcards are used based on direct interaction between user and relying party. Here sole control is provided by giving users both physical possession and control of the cryptographic key used for signing/authentication through a PIN. Such **classical** sole control is required in the 1999 electronic signature directive by some interpretations. The eIDAS regulation repeals the directive and explicitly relaxes its sole control requirements in a trade-off between security and usability. This allows user interaction to be outsourced to intermediary parties (authentication providers, signing services). This also allows mobile applications as user friendly alternatives for smartcards. However, current mobile platforms are only equipped with limited cryptographic hardware not supporting secure knowledge factors (PINs) controlling keys. The eIDAS relaxation raises concerns on sole control; intermediary parties should not be able to act as man-in-the-middle and impersonate users. In this paper we present a simple cryptographic design for signing and authentication on standard mobile platforms providing classical sole control. We argue that our design can meet the highest eIDAS requirements, effectively introducing a new signature category in a 2016 decision of the European Commission. We also sketch a SECDSA based implementation of the European Digital Identity Wallet recently proposed by the European Commission as part of the eIDAS regulation update.

Deep Learning based Side-Channel Attacks (DL-SCA) are considered as fundamental threats against secure cryptographic implementations. Side-channel attacks aim to recover a secret key using the least number of leakage traces. In DL-SCA, this often translates in having a model with the highest possible accuracy. Increasing an attack’s accuracy is particularly important when an attacker targets public-key cryptographic implementations where the recovery of each secret key bits is directly related to the model’s accuracy. Commonly used in the deep learning field, ensemble models are a well suited method that combine the predictions of multiple models to increase the ensemble accuracy by reducing the correlation between their errors. Linked to this correlation, the diversity is considered as an indicator of the ensemble model performance. In this paper, we propose a new loss, namely Ensembling Loss (EL), that generates an ensemble model which increases the diversity between the members. Based on the mutual information between the ensemble model and its related label, we theoretically demonstrate how the ensemble members interact during the training process. We also study how an attack’s accuracy gain translates to a drastic reduction of the remaining time complexity of a side-channel attacks through multiple scenarios on public-key implementations. Finally, we experimentally evaluate the benefits of our new learning metric on RSA and ECC secure implementations. The Ensembling Loss increases by up to $6.8\%$ the performance of the ensemble model while the remaining brute-force is reduced by up to $2^{22}$ operations depending on the attack scenario.

The keys of modern cryptographic algorithms have an enormous size, so the testing of the algorithm performance for all key combinations, will take practically an infinite time. To avoid this, the sampling method is used, where a much smaller number of keys is tested and then the estimation of the algorithm performance for all the keys is calculated with a predetermined sampling error. For each sampling key, an output sample of the algorithm must be generated and tested. Therefore, in order to have sampling results as close as possible to the real performance of the algorithm, the key question is whether the selection of the keys should be random or it must follow some rules. If the selection of the keys is completely random, there is a high probability that the tests will not find some "weak" or "equivalent" keys, which give non-random or similar outputs and therefore reduce the total number of active keys. But if the sampling keys are selected with some specific criteria, there is a much greater probability of detecting any weak or equivalent key. In this study an optimal key selection methodology is proposed, which combines the random and the non-random key selection.

Businesses that are subject to AML/CTF regulation must meet their KYC obligations. In this context, to establish and verify a customer’s identity, the customer is required to share personal information with these businesses. This creates a Pareto dominated situation where a customer’s privacy is typically traded off for the mandated transparency requirements. In addition, this privacy erosion also reduces the security and safety of the customer as shared personal information can be passed on or stolen and used against the best interest of the customer (e.g. identity theft). Recent innovations in self-sovereign identity and zero-knowledge cryptography, along with proper ecosystem design, allow for a novel approach to KYC that protects the customer’s privacy without reducing transparency. The proposed solution concept, zkKYC, removes the need for the customer to share any personal information with a regulated business for the purpose of KYC, and yet provides the transparency to allow for a customer to be identified if and when that is ruled necessary by a designated governing entity (e.g. regulator, law enforcement). This approach breaks the traditional privacy vs. transparency trade-off and provides structured transparency, resulting in a net positive outcome for all parties involved.

This paper presents a new family of linear codes, namely the expanded Gabidulin codes. Exploiting the existing fast decoder of Gabidulin codes, we propose an efficient algorithm to decode these new codes when the noise vector satisfies a certain condition. Further more, these new codes enjoy an excellent error-correcting capability because of the optimality of their parent Gabidulin codes. Based on different masking techniques, we give two encryption schemes by using expanded Gabidulin codes in the McEliece setting. According to our analysis, both of these two cryptosystems can resist the existing structural attacks. Compared to some other code-based cryptosystems, our proposals have obvious advantage in public-key representation without using the cyclic or quasi-cyclic structure.

Advances in cryptography have enabled the features of confidentiality, security, and integrity on small embedded devices such as IoT devices. While mathematically strong, the platform on which an algorithm is implemented plays a significant role in the security of the final product. Side-channel attacks exploit the variations in the system’s physical characteristics to obtain information about the sensitive data. In our scenario, a software implementation of a cryptographic algorithm is flashed on devices from different manufactures with the same instruction set configured for identical execution. To analyze the influence of the microarchitecture on side-channel leakage, we acquire thirty-two sets of power traces from four physical devices. While we notice minor differences in the leakage behaviour for different physical boards from the same manufacturer, our results confirm that the difference in microarchitecture implementations will leak different side-channel information. We also show that TVLA leakage prediction should be treated with caution as it is sensitive to both false positives and negatives.

Practical side-channel attacks on recent devices may be challenging due to the poor quality of acquired signals. It can originate from different factors, such as the growing architecture complexity, especially in System-on-Chips, creating unpredictable and concurrent operation of multiple signal sources on the device.

This work makes use of mixture distributions to formalize this complexity, allowing us to explain the benefit of using a technique like Scatter, where different samples of the traces are aggregated into the same distribution. Some observations of the conditional mixture distributions are made in order to model the leakage in such context. From this, we infer local coherency of information held in the distribution as a general property of side-channel leakage in mixture distributions. This leads us to introduce how spatial analysis tools, such as Moran's Index, can be used to significantly improve non-profiled attacks compared to other techniques from the state-of-the-art. Exploitation of this technique is experimentally shown very promising, as demonstrated on two AES implementations including masking and shuffling countermeasures.

Symmetric Searchable Encryption (SSE) allows users to outsource encrypted data to a possibly untrusted remote location while simultaneously being able to perform keyword search directly through the stored ciphertexts. An ideal SSE scheme should reveal no information about the content of the encrypted information nor about the searched keywords and their mapping to the stored files. However, most of the existing SSE schemes fail to fulfill this property since in every search query, some information potentially valuable to a malicious adversary is leaked. The leakage becomes even bigger if the underlying SSE scheme is dynamic. In this paper, we minimize the leaked information by proposing a forward and backward private SSE scheme in a multi-client setting. Our construction achieves optimal search and update costs. In contrast to many recent works, each search query only requires one round of interaction between a user and the cloud service provider. In order to guarantee the security and privacy of the scheme and support the multi-client model (i.e. synchronization between users), we exploit the functionality offered by AMD's Secure Encrypted Virtualization (SEV).