International Association
for Cryptologic Research

Iterative methods are a standard technique in many areas of scientific computing. The key idea is that a function is applied repeatedly until the resulting sequence converges to the correct answer. When applying such methods in a secure computation methodology (for example using MPC, FHE, or SGX) one either needs to perform enough steps to ensure convergence irrespective of the input data, or one needs to perform a convergence test within the algorithm, and this itself leads to a leakage of data. Using the Banach Fixed Point theorem, and its extensions, we show that this data-leakage can be quantified. We then apply this to a secure (via MPC) implementation of the PageRank methodology. For PageRank we show that allowing this small amount of data-leakage produces a much more efficient secure implementation, and that for many underlying graphs this `leakage' is already known to any attacker.

Bitcoin transfers value on a public ledger of transactions anyone can verify. Coin ownership is defined in terms of public keys. Despite potential use for private transfers, research has shown that users’ activity can often be traced in practice. Businesses have been built on dragnet surveillance of Bitcoin users because of this lack of strong privacy, which harms its fungibility, a basic property of functional money. Although the public nature of this design lacks strong guarantees for privacy, it does not rule it out. A number of methods have been proposed to strengthen privacy. Among these is CoinJoin, an approach based on multiparty transactions that can introduce ambiguity and break common assumptions that underlie heuristics used for deanonymization. Existing implementations of CoinJoin have several limitations which may partly explain the lack of their widespread adoption. This work introduces WabiSabi, a new protocol for centrally coordinated CoinJoin implementations utilizing keyed verification anonymous credentials and homomorphic value commitments. This improves earlier approaches which utilize blind signatures in both privacy and flexibility, enabling novel use cases and reduced overhead.

Threshold ECDSA signatures provide a higher level of security to a crypto wallet since it requires more than t parties out of n parties to sign a transaction. The state-of-the-art bandwidth efficient threshold ECDSA used the additive homomorphic Castagnos and Laguillaumie (CL) encryption based on an unknown order group G, together with a number of zero-knowledge proofs in G. In this paper, we propose compact zero-knowledge proofs for threshold ECDSA to lower the communication bandwidth, as well as the computation cost. The proposed zero-knowledge proofs include the discrete-logarithm relation in G and the well-formedness of a CL ciphertext.

When applied to two-party ECDSA, we can lower the bandwidth of the key generation algorithm by 47%, and the running time for the key generation and signing algorithms are boosted by about 35% and 104% respectively. When applied to threshold ECDSA, our first scheme is more optimized for the key generation algorithm (about 70% lower bandwidth and 70% faster computation in key generation, at a cost of 20% larger bandwidth in signing), while our second scheme has an all-rounded performance improvement (about 60% lower bandwidth, 27% faster computation in key generation without additional cost in signing).

The Brakerski-Gentry-Vaikuntanathan (BGV) and Brakerski/Fan-Vercauteren (BFV) schemes are the two main homomorphic encryption (HE) schemes to perform exact computations over finite fields and integers. Although the schemes work with the same plaintext space, there are significant differences in their noise management, algorithms for the core homomorphic multiplication operation, message encoding, and practical usability. The main goal of our work is to revisit both schemes, focusing on closing the gap between the schemes by improving their noise growth, computational complexity of the core algorithms, and usability. The other goal of our work is to provide both theoretical and experimental performance comparison of BGV and BFV.

More precisely, we propose an improved variant of BFV where the encryption operation is modified to significantly reduce the noise growth, which makes the BFV noise growth somewhat better than for BGV (in contrast to prior results showing that BGV has smaller noise growth for larger plaintext moduli). We also modify the homomorphic multiplication procedure, which is the main bottleneck in BFV, to reduce its algorithmic complexity. Our work introduces several other novel optimizations, including lazy scaling in BFV homomorphic multiplication and an improved BFV decryption procedure in the Residue Number System (RNS) representation. We also develop a usable variant of BGV as a more efficient alternative to BFV for common practical scenarios.

We implement our improved variants of BFV and BGV in PALISADE and evaluate their experimental performance for several benchmark computations. Our results suggest that BGV is faster for intermediate and large plaintext moduli, which are often used in practical scenarios with ciphertext packing, while BFV is faster for small plaintext moduli.

Anonymous tokens have recent applications in private Internet browsing and anonymous statistics collection. We develop new schemes in order to include public metadata such as expiration dates for tokens. This inclusion enables planned mass revocation of tokens without distributing new keys, which for natural instantiations can give 77 - 90 % amortized traffic savings compared to Privacy Pass (Davidson et al., 2018) and PrivateStats (Huang et al., 2021), respectively. By transforming the public key, we are able to append public metadata to several existing protocols without having to change the security proofs in any substantial way.

Additional contributions include expanded definitions and a description of how anonymous tokens can improve the privacy in dp3t-like digital contact tracing applications. We also show how to create efficient and conceptually simple tokens with public metadata and public verifiability from pairings.

We study when (dual) Vandermonde systems of the form ${V}_T^{{(\intercal)}} \cdot \vec{z} = s\cdot \vec{w}$ admit a solution $\vec{z}$ over a ring $\mathcal{R}$, where ${V}_T$ is the Vandermonde matrix defined by a set $T$ and where the "slack" $s$ is a measure of the quality of solutions. To this end, we propose the notion of $(s,t)$-subtractive sets over a ring $\mathcal{R}$, with the property that if $S$ is $(s,t)$-subtractive then the above (dual) Vandermonde systems defined by any $t$-subset $T \subseteq S$ are solvable over $\mathcal{R}$. The challenge is then to find large sets $S$ while minimising (the norm of) $s$ when given a ring $\mathcal{R}$.

By constructing families of $(s,t)$-subtractive sets $S$ of size $n = $ poly over cyclotomic rings $\mathcal{R} = \mathbb{Z}[\zeta_{p^\ell}]$ for prime $p$, we construct Schnorr-like lattice-based proofs of knowledge for the SIS relation ${A} \cdot \vec{x} = s \cdot \vec{y} \bmod q$ with $O(1/n)$ knowledge error, and $s = 1$ in case $p = $ poly. Our technique slots naturally into the lattice Bulletproof framework from Crypto'20, producing lattice-based succinct arguments for NP with better parameters.

We then give matching impossibility results constraining $n$ relative to $s$, which suggest that our Bulletproof-compatible protocols are optimal unless fundamentally new techniques are discovered. Noting that the knowledge error of lattice Bulletproofs is \(\Omega(\log k/n)\) for witnesses in \(\mathcal{R}^k\) and subtractive set size \(n\), our result represents a barrier to practically efficient lattice-based succinct arguments in the Bulletproof framework.

Beyond these main results, the concept of $(s,t)$-subtractive sets bridges group-based threshold cryptography to lattice settings, which we demonstrate by relating it to distributed pseudorandom functions.

Company's mission: Original solutions for the security and economic demands of data and data owners.

Seniority level: Open to discussion. Lack of industry experience can be compensated by academic achievements.

Industry: Information Technology, Cybersecurity, Data Science.

Available employment types: full-time, part-time, in-person, remote.

Responsibilities:

• Stay current with advances in cryptography, related areas, and the underlying mathematical subjects.
• Understand and implement existing cryptographic constructions in the literature and industry.
• Help to design and to evaluate new cryptographic schemes and protocols.

Minimum Qualifications:

• Ph.D. in Computer Science, Mathematics, Engineering, or another related field.
• Fluency in at least one of the following programming languages: C, C++, Python, Ruby, Go, Java.
• Reasonable proficiency in several topics in discrete mathematics (in particular, logic, group theory, probability, number theory, and linear algebra).

Preferred:

• Track record of peer-reviewed publications related to cryptography and mathematics in general.
• Experience with cryptanalysis.

Benefits:

• Work with challenging problems for deploying real-world applications of significant impact in the industry.
• Direct contact with crypto experts in in-depth discussions and analysis of ongoing projects.
• Learn from veterans from the industry of new technologies.
• Incentives for writing scientific papers, patents, and participating in academic conferences and other related events.
• Budget for investing in continued education (books, courses, seminars, certifications, among others).
• Visa sponsorship (when applicable).
• Dental, vision, and health insurance (for full-time employees).
• Salary to be defined according to the seniority and employment level.

Closing date for applications:

Contact: David Silva, david@x-logos.com

DFINITY has a world-class team of computer science researchers that is experiencing rapid growth as we approach the Internet Computer’s public launch. We have multiple openings across a broad range of seniority and fields with a focus on security and practical performance. Below are some examples of relevant research areas - but unique combinations or variations are ok.

• Cryptography
• Distributed systems
• Formal verification
• Networking
• Computer
• Operating systems
• Embedded system
• Pen testing

Please see our careers page for more information.

Closing date for applications:

Contact: Jens Groth: jens AT dfinity.org

More information: https://dfinity.org/careers

Do you like designing and implementing secure systems? Are you passionate about code simplicity, quality, and performance? Do you think that cryptographic tools such as zero-knowledge proofs and threshold crypto are heavily under-utilized? This is a unique opportunity to work with exceptional engineering teams creating the Internet Computer and bring advanced cryptographic algorithms to practical use. For more information about the position, please refer to our careers page.

Closing date for applications:

Contact: Jens Groth: jens AT dfinity.org

More information: https://dfinity.org/careers

We would like to announce open postdoc and (fully-funded) phd positions.

We are searching for candidates who are enthusiastic about driving forward the field of quantum cryptography (including post-quantum crypto), especially provable quantum security. The research takes place in the context of an ERC project that targets formally verified quantum cryptographic proofs.

For more information, see the link below. Please forward this to anyone potentially interested, and do not hesitate to contact me.

Closing date for applications:

Contact: Dominique Unruh, unruh@ut.ee

More information: https://crypto.cs.ut.ee/Main/PostdocInPost-QuantumCryptography

We revisit private optimization and learning from an information processing view. The main contribution of this paper is twofold. First, different from the classic cryptographic framework of operation-by-operation obfuscation, a novel private learning and inference framework via either data-dependent or random transformation on the sample domain is proposed. Second, we propose a novel security analysis framework, termed probably approximately correct (PAC) inference resistance, which bridges the information loss in data processing and prior knowledge. Through data mixing, we develop an information theoretical security amplifier with a foundation of PAC security.

We study the applications of such a framework from generalized linear regression models to modern learning techniques, such as deep learning. On the information theoretical privacy side, we compare three privacy interpretations: ambiguity, statistical indistinguishability (Differential Privacy) and PAC inference resistance, and precisely describe the information leakage of our framework. We show the advantages of this new random transform approach with respect to underlying privacy guarantees, computational efficiency and utility for fully connected neural networks.

We propose a novel MPC framework, Manticore, in the multiparty setting, with full threshold and semi-honest security model, supporting a combination of real number arithmetic (arithmetic shares), Boolean arithmetic (Boolean shares) and garbled circuits (Yao shares). In contrast to prior work [MZ17, MR18], Manticore never overflows, an important feature for machine learning applications. It achieves this without compromising efficiency or security. Compared to other overflow-free recent techniques such as MP-SPDZ [EGKRS20] that convert arithmetic to Boolean shares, we introduce a novel highly efficient modular lifting/truncation method that stays in the arithmetic domain. We revisit some of the basic MPC operations such as real-valued polynomial evaluation, division, logarithm, exponential and comparison by employing our modular lift in combination with existing efficient conversions between arithmetic, Boolean and Yao shares. Furthermore, we provide a highly efficient and scalable implementation supporting logistic regression models with real-world training data sizes and high numerical precision through PCA and blockwise variants (for memory and runtime optimizations). On a dataset of 50 million rows and 50 columns distributed among two players, it completes in one day with at least 10 decimal digits of precision.Our logistic regression solution placed first at Track 3 of the annual iDASH’2020 Competition. Finally, we mention a novel oblivious sorting algorithm built using Manticore.

Gaussian sampling over the integers is one of the fundamental building blocks of lattice-based cryptography. In particular, it can't be avoided in trapdoor sampling until now. However, it's still a challenging work how to construct a generic, efficient, and isochronous Gaussian sampler. In this paper, our contribution is three-fold.

First, we propose a secure, efficient exponential Bernoulli sampling algorithm. It can be applied to Gaussian samplers based on rejection samplings. We apply it to FALCON, a candidate of round 3 of the NIST post-quantum cryptography standardization project, and reduce its signature generation time by 13.66%-15.52%.

Second, we develop a new Gaussian sampler based on rejection sampling. Our Algorithm can securely sample from Gaussian distributions with different standard deviations and arbitrary centers. We apply it to PALISADE (S&P'18), an open-source lattice cryptography library. The new implementation of trapdoor sampling in PALISADE has better performance while resisting timing attacks.

Third, we improve the efficiency of the COSAC sampler (PQC'20). The new COSAC sampler is 1.46x-1.63x faster than the original and has the lowest expected number of trials among all Gaussian samplers based on rejection samplings. But it needs a more efficient algorithm sampling from the normal distribution to improve its performance.

The module learning with errors (MLWE) problem is one of the most promising candidates for constructing quantum-resistant cryptosystems. In this work, we propose an open-source framework to automatically adjust the level of parallelism for MLWE-based key exchange protocols to maximize the protocol execution efficiency. We observed that the number of key exchanges handled by primitive functions in parallel, and the dimension of the grids in the GPUs have significant impacts on both the latencies and throughputs of MLWE key exchange protocols. By properly adjusting the related parameters, in the experiments, we show that performance of MLWE based key exchange protocols can be improved across GPU platforms.

Deep learning-based side-channel analysis (SCA) became the de facto standard in the profiling SCA. Still, this does not mean it is trivial to find neural networks that perform well for any setting. Based on the developed neural network architectures, we can distinguish between small neural networks that are easier to tune and less prone to overfitting but can have insufficient capacity to model the data. On the other hand, large neural networks would have sufficient capacity but can overfit and are more difficult to tune. This always brings an interesting trade-off between simplicity and performance.

This paper proposes using a pruning strategy and recently proposed Lottery Ticket Hypothesis to improve the deep learning-based SCA. We demonstrate that we can find smaller neural networks that perform on the level of larger networks, where we manage to reduce the number of weights by more than 90% on average. Additionally, we show that pruning can help prevent overfitting and the effects of imbalanced data, reaching top attack performance for small networks when larger networks do not manage to break the target at all.

Xagawa and Yamakawa (PQCrypto 2019) proved the transformation SXY can tightly turn DS secure PKEs into IND-qCCA secure KEMs in the quantum random oracle model (QROM). But transformations such as KC, TPunc that turn PKEs with standard security (OW-CPA or IND-CPA) into DS secure PKEs still suffer from quadratic security loss in the QROM. In this paper, we give a tighter security reduction for the transformation KC that turns OW-CPA secure deterministic PKEs into modified DS secure PKEs in the QROM. We use the Measure-Rewind-Measure One-Way to Hiding Lemma recently introduced by Kuchta et al. (EUROCRYPT 2020) to avoid the square-root advantage loss. Moreover, we extend it to the case that underlying PKEs are not perfectly correct. Combining with other transformations, we finally obtain a generic KEM from any IND-CPA secure PKE. Our security reduction has roughly the same tightness as the result of Kuchta et al. without any other assumptions and we achieve the stronger IND-qCCA security. We also give a similar result for another KEM transformation achieving the same security notion from any OW-CPA secure deterministic PKE.

This paper introduces M-Circuits, a program representation which generalizes arithmetic and binary circuits. This new representation is motivated by the way modern multi-party computation (MPC) systems based on linear secret sharing schemes actually operate. We then show how this representation also allows one to construct zero knowledge proof (ZKP) systems based on the MPC-in-the-head paradigm. The use of the M-Circuit program abstraction then allows for a number of program-specific optimizations to be applied generically. It also allows to separate complexity and security optimizations for program compilation from those for application protocols (MPC or ZKP).

Being one of the winning algorithms of the CAESAR competition and currently a second round candidate of the NIST lightweight cryptography standardization project, the authenticated encryption scheme Ascon (designed by Dobraunig, Eichlseder, Mendel, and Schl{\"{a}}ffer) has withstood extensive self and third-party cryptanalysis. The best known attack on Ascon could only penetrate up to $7$ (out of $12$) rounds due to Li et al. (ToSC Vol I, 2017). However, it violates the data limit of $2^{64}$ blocks per key specified by the designers. Moreover, the best known distinguishers of Ascon in the AEAD context reach only 6 rounds. To fill these gaps, we revisit the security of 7-round Ascon in the nonce-respecting setting without violating the data limit as specified in the design. First, we introduce a new superpoly-recovery technique named as \textit{partial polynomial multiplication} for which computations take place between the so-called degree-$d$ homogeneous parts of the involved Boolean functions for a $2d$-dimensional cube. We apply this method to 7-round Ascon and present several key recovery attacks. Our best attack can recover the 128-bit secret key with a time complexity of about $2^{123}$ 7-round Ascon permutations and requires $2^{64}$ data and $2^{101}$ bits memory. Also, based on division properties, we identify several 60 dimensional cubes whose superpolies are constant zero after 7 rounds. We further improve the cube distinguishers for 4, 5 and 6 rounds. Although our results are far from threatening the security of full 12-round Ascon, they provide new insights in the security analysis of Ascon.

Many lattice-based encryption schemes are subject to a very small probability of decryption failures. It has been shown that an adversary can efficiently recover the secret key using a number of ciphertexts that cause such a decryption failure. In PKC~2019, D'Anvers~et~al. introduced `failure boosting', a technique to speed up the search for decryption failures. In this work we first improve the state-of-the-art multitarget failure boosting attacks. We then improve the cost calculation of failure boosting and extend the applicability of these calculations to permit cost calculations of real-world schemes. Using our newly developed methodologies we determine the multitarget decryption failure attack cost for all parameter sets of Saber and Kyber, showing among others that the quantum security of Saber can theoretically be reduced from 172 bits to 145 bits in specific circumstances. We then discuss the applicability of decryption failure attack in real-world scenarios, showing that an attack might not be practical to execute.

In this paper we prove quantum indifferentiability of the sponge construction instantiated with random (invertible) permutations. With this result we bring the post-quantum security of the standardized SHA-3 hash function to the level matching its security against classical adversaries. To achieve our result, we generalize the compressed-oracle technique of Zhandry (Crypto'19) by defining and proving correctness of a compressed permutation oracle. We believe our technique will find applications in many more cryptographic constructions.