International Association
for Cryptologic Research

Private function evaluation (PFE) is a special type of MPC protocols that, in addition to the input privacy, can preserve the function privacy. In this work, we propose a PFE scheme for RAM. In particular, we first design an efficient 4-server distributed ORAM scheme with amortized communication $O(\log n)$ per access (both reading and writing). We then simulate a RISC RAM machine over the MPC platform, hiding (i) the memory access pattern, (ii) the machine state (including registers, program counter, condition flag, etc.), and (iii) the executed instructions. Our scheme can naturally support a simplified TinyRAM instruction set; if a public RAM program $P$ with given inputs $x$ needs to execute $z$ instruction cycles, our PFE scheme is able to securely evaluate $P(x)$ on private $P$ and $x$ within $5z+1$ online rounds. We prototype and benchmark our system for set intersection, binary search, quicksort, and heapsort algorithms. For instance, to obliviously perform the binary search algorithm on a $2^{10}$ array takes $5.81s$ with function privacy.

This note presents some techniques to slightly reduce the size of EdDSA and ECDSA signatures without lowering their security or breaking compatibility with existing signers, at the cost of an increase in signature verification time; verifying a 64-byte Ed25519 signature truncated to 60 bytes has an average cost of 4.1 million cycles on 64-bit x86 (i.e. about 35 times the cost of verifying a normal, untruncated signature).

In this paper, we formalize the plaintext-awareness notion in the superposition access model in which a quantum adversary may implement the encryption oracle in a quantum device and make superposition queries to the decryption oracle. Due to various possible ways an adversary can access the decryption oracles, we present six security definitions to capture the plaintext-awareness notion with respect to each way of access. We study the relationships between these definitions and present various implications and non-implications. Classically, the strongest plaintext-awareness notion (PA2) accompanied by the indistinguishability under chosen-plaintext attack (IND-CPA) notion yields the indistinguishability under chosen-ciphertext attack (INDCCA) notion. We show that the PA2 notion is not sufficient to show the above relation when targeting the IND-qCCA notion (Boneh-Zhandry definition, Crypto 2013). However, our proposed post-quantum PA2 notion with superposition decryption queries fulfils this implication.

Decision trees are among the most widespread machine learning model used for data classification, in particular due to their interpretability that makes it easy to explain their prediction. In this paper, we propose a novel solution for the private classification of a client request in a non-interactive manner. In contrast to existing solutions to this problem, which are either interactive or require evaluating all the branches of the decision tree, our approach only evaluates a single branch of the tree. Our protocol is based on two primitives that we also introduce in this paper and that maybe of independent interest : Blind Node Selection and Blind Array Access. Those contributions are based on recent advances in homomorphic cryptography, such as the functional bootstrapping mechanism recently proposed for the Fully Homomorphic Encryption over the Torus scheme TFHE. Our private decision tree evaluation algorithm is highly efficient as it requires only one round of communication and d comparisons, with d being the depth of the tree, while other state-of-the-art non-interactive protocols need 2^d comparisons.

Currently deployed public-key cryptosystems will be vulnerable to attacks by full- scale quantum computers. Consequently, quantum resistant cryptosystems are in high demand, and lattice-based cryptosystems, based on a hard problem known as Learning With Errors (LWE), have emerged as strong contenders for standardization. In this work, we train transformers to perform modular arithmetic and combine half-trained models with statistical cryptanalysis techniques to propose SALSA: a machine learning attack on LWE-based cryptographic schemes. SALSA can fully recover secrets for small-to-mid size LWE instances with sparse binary secrets, and may scale to attack real-world LWE-based cryptosystems.

Secure multiparty computation (MPC) models scenarios, where a set of mutually distrusting parties wish to compute some task over their private inputs. Assuming that the majority of the parties are honest and that the parties have access to a broadcast channel, every function can be computed with full security. Conversely, if either an honest majority or a broadcast channel cannot be assumed (as is the case in various real-world settings), then there are functionalities that cannot be computed with full security. Understanding the exact power of each of these assumptions is a valuable goal. In this paper, we study full security for solitary output functionalities (where only a single party receives an output). We focus on three-party functionalities in the point-to-point model (without broadcast), assuming an honest majority. We develop new techniques for analyzing the security of MPC protocols in the point-to-point model. Using these techniques, we are able to give a characterization for several interesting classes of solitary output three-party functionalities (including Boolean and ternary-output functionalities over a polynomial-size domain) that are computable with full security in the setting of an honest majority without a broadcast channel. Furthermore, using our techniques, we make progress in understanding the set of solitary output three-party functionalities that can be computed with full security, assuming broadcast but no honest majority. Specifically, we extend the set of such functionalities that are known to be computable, due to Halevi et al. [TCC ’19].

We implement training of neural networks in secure multi-party computation (MPC) using quantization commonly used in said setting. We are the first to present an MNIST classifier purely trained in MPC that comes within 0.2 percent of the accuracy of the same convolutional neural network trained via plaintext computation. More concretely, we have trained a network with two convolutional and two dense layers to 99.2% accuracy in 3.5 hours (under one hour for 99% accuracy). We have also implemented AlexNet for CIFAR-10, which converges in a few hours. We develop novel protocols for exponentiation and inverse square root. Finally, we present experiments in a range of MPC security models for up to ten parties, both with honest and dishonest majority as well as semi-honest and malicious security.

Bitcoin is the most secure blockchain in the world, supported by the immense hash power of its Proof-of-Work miners. Proof-of-Stake chains are energy-efficient, have fast finality and some accountability, but face several security issues: susceptibility to non-slashable long-range safety attacks, non-accountable transaction censorship and stalling attacks and difficulty to bootstrap PoS chains from low token valuation. We show these security issues are inherent in any PoS chain without an external trusted source, and propose a new protocol Babylon, where an off-the-shelf PoS protocol uses Bitcoin as an external source of trust to resolve these issues. An impossibility result justifies the optimality of Babylon. Our results shed light on the general question of how much security a PoS chain can derive from an external trusted chain by only making succinct commitments to the trusted chain.

In this work, we propose generic and novel adaptations to the binary Plaintext-Checking (PC) oracle based side-channel attacks for Kyber KEM. Binary PC oracle-based side-channel attacks are fairly generic and easy to mount on a given target, as the attacker requires very minimal information about the target device. However, these attacks have an inherent disadvantage of requiring a few thousand traces to perform full key recovery, as they only recover a single bit of information per trace. We propose novel parallel PC oracle based side-channel attacks, which are capable of recovering an arbitrary P number of bits of information about the secret key in a single trace. We experimentally validated our attacks on the fastest implementation of unprotected Kyber KEM in the pqm4 library on the ARM Cortex-M4 microcontroller. Our experiments yielded improvements in the range of 2.89x and 7.65x in the number of queries, compared to state-of-the-art binary PC oracle attacks, while arbitrarily higher improvements are possible for a motivated attacker, given the generic nature of our attack. Finally, we also conduct a thorough study of the capability of our attack in different attack scenarios, based on the presence/absence of a clone device, and also partial key recovery. We also show that our proposed attacks are able to achieve the lowest number of queries for key recovery, even over implementations protected with low-cost countermeasures such as shuffling. Our work therefore, concretely demonstrates the power of PC oracle attacks on Kyber KEM, thereby stressing the need for concrete countermeasures such as masking.

We propose NTT implementations with each supporting at least one parameter of NTRU and one parameter of NTRU Prime. Our implementations are based on size-1440, size-1536, and size-1728 convolutions without algebraic assumptions on the target polynomial rings. We also propose several improvements for the NTT computation. Firstly, we introduce dedicated radix-(2,3) butterflies combining Good–Thomas FFT and vector-radix FFT. In general, there are six dedicated radix-(2, 3) butterflies and they together support implicit permutations. Secondly, for odd prime radices, we show that the multiplications for one output can be replaced with additions/subtractions. We demonstrate the idea for radix-3 and show how to extend it to any odd prime. Our improvement also applies to radix-(2, 3) butterflies. Thirdly, we implement an incomplete version of Good–Thomas FFT for addressing potential code size issues. For NTRU, our polynomial multiplications outperform the state-of-the-art by 2.8%−10.3%. For NTRU Prime, our polynomial multiplications are slower than the state-of-the-art. However, the SotA exploits the specific structure of coefficient rings or polynomial moduli, while our NTT-based multiplications exploit neither and apply across different schemes. This reduces the engineering effort, including testing and verification.

In this paper we show that PSPACE is equal to 4th level in the polynomial hierarchy. We also deduce a lot of important consequences. True quantified Boolean formula is indeed generalisation of the Boolean Satisfiability Problem, where determining of interpretation that satisfies a given Boolean formula is replaced by existence of Boolean functions that makes a given QBF to be tautology. Such functions are called the Skolem functions. The essential idea of the proof is to show that for any (fully) quantified Boolean formula ϕ we can obtain a formula ϕ′ which is in the forth level of the polynomial hierarchy, no more than polynomial in the size of a given ϕ, such that the truth of ϕ can be determined from the truth of ϕ′. The idea is to skolemize, and then use additional formulas from the second level of the polynomial hierarchy inside the skolemized prefix to enforce that the skolem variables indeed depend only on the universally quantified variables they are supposed to. However, some dependence is lost when the quantification is reversed. It is called "XOR issue" in the paper because the functional dependence can be expressed by means of an XOR formula. Thus, it is needed to locate these XORs. The last can be done locally for each leaf/ branch/ iteration (keep in mind the algebraic normal form (ANF)), i.e. in polynomial time, since all arguments are specified.

In this paper, we investigate the possibility of performing Gaussian elimination for arbitrary binary matrices on hardware. In particular, we presented a generic approach for hardware-based Gaussian elimination, which is able to process both non-singular and singular matrices. Previous works on hardware-based Gaussian elimination can only process non-singular ones. However, a plethora of cryptosystems, for instance, quantum-safe key encapsulation mechanisms based on rank-metric codes, ROLLO and RQC, which are among NIST post-quantum cryptography standardization round-2 candidates, require performing Gaussian elimination for random matrices regardless of the singularity. We accordingly implemented an optimized and parameterized Gaussian eliminator for (singular) matrices over binary fields, making the intense computation of linear algebra feasible and efficient on hardware. To the best of our knowledge, this work solves for the first time eliminating a singular matrix on reconfigurable hardware and also describes the a generic hardware architecture for rank-code based cryptographic schemes. The experimental results suggest hardware-based Gaussian elimination can be done in linear time regardless of the matrix type.

Side-Channel Analysis (SCA) allows extracting secret keys manipulated by cryptographic primitives through leakages of their physical implementations. Supervised attacks, known to be optimal, can theoretically defeat any counter-measure, including masking, by learning the dependency between the leakage and the secret through the profiling phase. However, defeating masking is less trivial when it comes to unsupervised attacks. While classical strategies such as CPA or LRA have been extended to masked implementations, we show that these extensions only hold for Boolean and arithmetic schemes. Therefore, we propose a new unsupervised strategy, the Joint Moments Regression (JMR), able to defeat any masking schemes (multiplicative, affine, polynomial, inner product...), which are gaining popularity in real implementations. The main idea behind JMR is to directly regress the leakage model of the shares by fitting a system based on higher-order joint moments conditions. We show that this idea can be seen as part of a more general framework known as the Generalized Method of Moments (GMM). This offers strong mathematical foundations on which we can rely on to derive optimizations of JMR. Simulation experiments show that our proposal outperforms state-of-the-art attacks, even in the case of Boolean and arithmetic masking. Eventually, we apply this strategy to provide, to the best of our knowledge, the first unsupervised attack (successful in practice) on the protected AES implementation proposed by the ANSSI for SCA research, which embed an affine masking and shuffling counter-measures.

Event date: 30 November to 2 December 2022
Submission deadline: 22 August 2022
Notification: 3 October 2022

We are looking for bright and motivated PhD students to work in the topics of information security and cryptography. The students will join the Cybersecurity and applied Cryptography group led by Prof. Katerina Mitrokotsa (https://cybersecurity.unisg.ch/). The students are expected to work on topics that include security and privacy issues for resource-constrained devices (e.g., sensors) that rely on external untrusted servers in order to perform computations. More precisely, the student shall be working on investigating efficient authentication and verifiable delegation of computation mechanisms that provide: i) provable security guarantees, and ii) rigorous privacy guarantees. The positions are funded with a competitive salary and the workplace is in beautiful St. Gallen in Switzerland.
Research areas: Research areas include but are not limited to:

• Verifiable computation
• Secure Multi Party Computation
• Privacy-preserving authentication
• Cryptographic primitives
• Privacy-preserving biometric authentication

Your Profile:

• A MSc degree in Computer Science, Applied Mathematics or a relevant field;
• Strong mathematical and algorithmic CS background;
• Excellent programming skills;
• Excellent written and verbal communication skills in English.

Final Deadline for applications: 1 August 2022
Starting date: By mutual agreement
Apply online: Send your cv, transcripts, motivation letter and research statement by email to Prof. Katerina Mitrokotsa

Closing date for applications:

Contact: Katerina Mitrokotsa

We formalize security properties of zero-knowledge protocols and their proofs in EasyCrypt. Specifically, we focus on sigma-protocols (three-round protocols). Most importantly, we also cover properties whose security proofs require the use of rewinding; prior work has focused on properties that do not need this more advanced technique. On our way we give generic definitions of the main properties associated with sigma protocols, both in the computational and information-theoretical setting. We give generic derivations of soundness, (malicious-verifier) zero-knowledge, and proof of knowledge from simpler assumptions with proofs which rely on rewinding. Also, we address sequential composition of sigma protocols. Finally, we illustrate the applicability of our results on three zero-knowledge protocols: Fiat-Shamir (for quadratic residues), Schnorr (for discrete logarithms), and Blum (for Hamiltonian cycles, NP-complete).

Traitor tracing schemes [Chor–Fiat–Naor, Crypto ’94] help content distributors fight against piracy and are defined with the content distributor as a trusted authority having access to the secret keys of all users. While the traditional model caters well to its original motivation, its centralized nature makes it unsuitable for many scenarios. For usage among mutually untrusted parties, a notion of *ad hoc* traitor tracing (naturally with the capability of broadcast and revocation) is proposed and studied in this work. Such a scheme allows users in the system to generate their own public/secret key pairs, without trusting any other entity. To encrypt, a list of public keys is used to identify the set of recipients, and decryption is possible with a secret key for any of the public keys in the list. In addition, there is a tracing algorithm that given a list of recipients’ public keys and a pirate decoder capable of decrypting ciphertexts encrypted to them, identifies at least one recipient whose secret key must have been used to construct the said decoder.

Two constructions are presented. The first is based on obfuscation and has constant-size ciphertext, yet its decryption time is linear in the number of recipients. The second is a generic transformation that reduces decryption time at the cost of increased ciphertext size. A lower bound on the trade-off between ciphertext size and decryption time is shown, indicating that the two constructions achieve all possible optimal trade-offs. The lower bound also applies to general attribute-based encryption and may be of independent interest.

Advancements in computer vision and machine learning breakthroughs over the years have paved the way for automated X-ray inspection (AXI) of printed circuit boards (PCBs). However, there is no standard dataset to verify the capabilities and limitations of such advancements in practice due to the lack of publicly available datasets for PCB X-ray inspection. Furthermore, there is a lack of diverse PCB X-ray datasets that encompass images from X-ray Computed Tomography (CT). To address the lack of data, we developed the first comprehensive publicly available dataset, "FICS PCB X-ray," to aid in the development of robust PCB-AXI methodologies. The dataset consists of diverse images from the tomographic image domain, along with challenging cases of unaligned, raw X-ray data of PCBs. Further, the dataset contains projection data and the reconstructed volume which is converted into a Tiff stack. Annotated X-ray layer images are also available for image processing and machine learning tasks. This paper summarizes the existing databases and their limitations, and proposes a new dataset, "FICS PCB X-ray''.

Financial dark pool trading venues are designed to keep pre-trade order information secret so that it cannot be misused by others. However, dark pools are vulnerable to an operator misusing the information in their system. Prior work has used MPC to tackle this problem by assuming that the dark pool is operated by a small set of two or three MPC parties. However, this raises the question of who plays the role of these operating parties and whether this scenario could be applied in the real world. In this work, we implement an MPC-based dark pool trading venue with up to 100 parties. This configuration would allow a real-world implementation where the operating parties are the active participants that trade in the venue (i.e., a ``no operator'' model), or where the parties are the main stakeholders of the venue (e.g., members of a non-profit partnership such as Plato). We use AWS cloud to empirically test the performance of the system. Results demonstrate that the system can achieve trading throughput required for some real-world venues, while the cost of hosting the system is negligible compared with the savings expected from guaranteeing no information leakage.

The lattice sieving algorithm based on list-decoding of Becker-Ducas-Gama-Laarhoven (SODA 2016) is currently at the center of cryptanalysis cost estimates of candidate lattice schemes for post-quantum standardization.

Yet, only an idealized version of this algorithm has been carefully modelled, i.e. given an efficient list-decoding oracle for a perfectly random spherical code. In this work, we propose an experimental analysis of the actual algorithm. The difficulty lies in estimating the probabilistic defect with respect to perfectly random spherical codes for the task at hand. While it should be in principle infeasible to run the algorithm in cryptographically relevant dimensions, a few tricks allow to nevertheless measure experimentally the relevant quantity.

Concretely, we conclude on an overhead factor of about $2^{6}$ on the number of gates in the RAM model compared to the idealized model for dimensions around $380$ after an appropriate re-parametrization. Part of this overhead can be traded for extra memory, at a costly rate. We also clarify that these overheads apply to an internal routine, and discuss how they can be partially mitigated in the whole attack.