International Association
for Cryptologic Research

Comparison of integers, a traditional topic in secure multiparty computation since Yao's pioneering work on "Millionaires' Problem" (FOCS 1982), is also well studied in card-based cryptography. For the problem, Miyahara et al. (Theoretical Computer Science, 2020) proposed a protocol using binary cards (i.e., cards with two kinds of symbols) that is highly efficient in terms of numbers of cards and shuffles, and its extension to number cards (i.e., cards with distinct symbols). In this paper, with a different design strategy which we name "Tug-of-War technique", we propose new protocols based on binary cards and on number cards. For binary cards, our protocol improves the previous protocol asymptotically (in bit lengths of input integers) in terms of numbers of cards and shuffles when adopting ternary encoding of input integers. For number cards, at the cost of increasing the number of cards, our protocol improves the number of shuffles of the previous protocol even with binary encoding, and more with $q$-ary encoding where $q > 2$.

The increase in leakage power from advanced tech nodes elevates the risk of static power side-channel (S-PSC) attacks. While protective measures exist, they involve a security cost trade-off. Hardware Trojans, particularly PSC-based ones, represent another significant threat. Despite acknowledging the link between static power leakage, advanced tech nodes, and vulnerability to S-PSC attacks, the role of the components at the heart of this sensitive interplay – the standard cells – has not been extensively studied in commercial-grade IC design. We analyze this relationship for commercial 28nm and 65nm nodes using a regular AES design. Our CAD framework permits design optimization while assessing S-PSC vulnerability. Contrary to the belief that high-performance designs are more vulnerable, we find timing constraints and threshold-voltage cell ratios are pivotal factors. Also, we discover that an attacker can deploy highly effective, stealthy PSC-based Trojans without any gate overheads or compromising timing paths.

Given $\ell$ parties with sets $X_1, \dots, X_\ell$ of size $n$, we would like to securely compute the intersection $\cap_{i=1}^\ell X_i$, if it is larger than $n-t$ for some threshold $t$, without revealing any other additional information. It has previously been shown (Ghosh and Simkin, Crypto 2019) that this function can be securely computed with a communication complexity that only depends on $t$ and in particular does not depend on $n$. For small values of $t$, this results in protocols that have a communication complexity that is sublinear in the size of the inputs. Current protocols either rely on fully homomorphic encryption or have an at least quadratic dependency on the parameter $t$.

In this work, we construct protocols with a quasilinear dependency on $t$ from simple assumptions like additively homomorphic encryption and oblivious transfer. All existing approaches, including ours, rely on protocols for computing a single bit, which indicates whether the intersection is larger than $n-t$ without actually computing it. Our key technical contribution, which may be of independent interest, takes any such protocol with secret shared outputs and communication complexity $\mathcal{O}(\lambda \ell \cdot\mathrm{poly}(t))$, where $\lambda$ is the security parameter, and transforms it into a protocol with communication complexity $\mathcal{O}(\lambda^2 \ell t \cdot\mathrm{polylog}(t))$.

In this work we study Invertible Bloom Lookup Tables (IBLTs) with small failure probabilities. IBLTs are highly versatile data structures that have found applications in set reconciliation protocols, error-correcting codes, and even the design of advanced cryptographic primitives. For storing $n$ elements and ensuring correctness with probability at least $1 - \delta$, existing IBLT constructions require $\Omega(n(\frac{\log(1/\delta)}{\log(n)}+1))$ space and they crucially rely on fully random hash functions.

We present new constructions of IBLTs that are simultaneously more space efficient and require less randomness. For storing $n$ elements with a failure probability of at most $\delta$, our data structure only requires $\mathcal{O}(n + \log(1/\delta)\log\log(1/\delta))$ space and $\mathcal{O}(\log(\log(n)/\delta))$-wise independent hash functions.

As a key technical ingredient we show that hashing $n$ keys with any $k$-wise independent hash function $h:U \to [Cn]$ for some sufficiently large constant $C$ guarantees with probability $1 - 2^{-\Omega(k)}$ that at least $n/2$ keys will have a unique hash value. Proving this is highly non-trivial as $k$ approaches $n$. We believe that the techniques used to prove this statement may be of independent interest.

A multilinear polynomial is a multivariate polynomial that is linear in each variable. This paper presents a scheme to commit to multilinear polynomials and to later prove evaluations of committed polynomials. The construction of the scheme is generic and relies on additively homomorphic schemes to commit to univariate polynomials. As the construction requires to check that several committed univariate polynomials do not exceed given, separate bounds, the paper also gives a method to batch executions of any degree-check protocol on homomorphic commitments. For a multilinear polynomial in n ≥ 2 variables, the instantiation of the scheme with a hiding version of KZG commitments (Kate, Zaverucha and Goldberg at Asiacrypt 2010) gives a pairing-based scheme with evaluations proofs in which the prover sends n + 3 first-group elements, performs at most 5 · 2n−1 + 1 first-group scalar multiplication and uses only n+2 random field elements to achieve the zero-knowledge property. Verification requires at most 2n + 2 first-group scalar multiplications, two second-group scalar multiplications and three pairing computations.

Payment channels allow a sender to do multiple transactions with a receiver without recording each single transaction on-chain. While most of the current constructions for payment channels focus on UTXO-based cryptocurrencies with reduced scripting capabilities (e.g., Bitcoin or Monero), little attention has been given to the possible benefits of adapting such constructions to cryptocurrencies based on the account model and offering a Turing complete language (e.g., Ethereum). The focus of this work is to implement efficient payment channels tailored to the capabilities of account-based cryptocurrencies with Turing-complete language support in order to provide scalable payments that are interoperable across different cryptocurrencies and unlinkable for third-parties (e.g., payment intermediaries). More concretely, we continue the line of research on cryptocurrency universal payment channels (UPC) which facilitate interoperable payment channel transactions across different ledgers in a hub-and-spoke model, by offering greater scalability than point-to-point architectures. Our design proposes two different versions, UPC and AUPC. For UPC we formally describe the protocol ideas sketched in previous work and evaluate our proof-of-concept implementation. Then, AUPC further extends the concept of universal payment channels by payment unlinkability against the intermediary server.

A Single Sign-On (SSO) system allows users to access different remote services while authenticating only once. SSO can greatly improve the usability and security of online activities by dispensing with the need to securely remember or store tens or hundreds of authentication secrets. On the downside, today's SSO providers can track users' online behavior, and collect personal data that service providers want to see asserted before letting a user access their resources.

In this work, we propose a new policy-based Single Sign-On service, i.e., a system that produces access tokens that are conditioned on the user's attributes fulfilling a specified policy. Our solution is based on multi-party computation and threshold cryptography, and generates access tokens of standardized format. The central idea is to distribute the role of the SSO provider among several entities, in order to shield user attributes and access patterns from each individual entity. We provide a formal security model and analysis in the Universal Composability framework, against proactive adversaries. Our implementation and benchmarking show the practicality of our system for many real-world use cases.

Digital Signatures are ubiquitous in modern computing. One of the most widely used digital signature schemes is ECDSA due to its use in TLS, various Blockchains such as Bitcoin and Etherum, and many other applications. Yet the formal analysis of ECDSA is comparatively sparse. In particular, all known security results for ECDSA rely on some idealized model such as the generic group model or the programmable (bijective) random oracle model.

In this work, we study the question whether these strong idealized models are necessary for proving the security of ECDSA. Specifically, we focus on the programmability of ECDSA's "conversion function" which maps an elliptic curve point into its $x$-coordinate modulo the group order. Unfortunately, our main results are negative. We establish, by means of a meta reductions, that an algebraic security reduction for ECDSA can only exist if the security reduction is allowed to program the conversion function. As a consequence, a meaningful security proof for ECDSA is unlikely to exist without strong idealization.

Transport Layer Security (TLS) 1.3 and the Signal protocol are very important and widely used security protocols. We show that the key update function in TLS 1.3 and the symmetric key ratchet in Signal can be modelled as non-additive synchronous stream ciphers. This means that the efficient Time Memory Tradeoff Attacks for stream ciphers can be applied. The implication is that TLS 1.3, QUIC, DTLS 1.3, and Signal offers a lower security level against TMTO attacks than expected from the key sizes. We provide detailed analyses of the key update mechanisms in TLS 1.3 and Signal, illustrate the importance of ephemeral key exchange, and show that the process that DTLS 1.3 and QUIC use to calculate AEAD limits is flawed. We provide many concrete recommendations for the analyzed protocols.

The SandboxAQ team is looking for a Standardization Engineer to help functionalize the next generation of cybersecurity systems. A successful candidate will represent SandboxAQ in cryptography and information security standard bodies, leading our global standardization activities. The candidate should have a proven track record of participation and contribution to standard bodies, and should be comfortable with cryptographic algorithms and secure protocols. The candidate will be part of a diverse team consisting of cryptographers, mathematicians, ML experts, and physicists, where they will play a key role in efficient and effective enablement of the technologies being developed.

Core Responsibilities

• Research and design new cryptographic primitives or protocols.
• Represent SandboxAQ’s interests in standard bodies.
• Contribute technically to the standardization of internal innovative designs and technologies.
• Work closely with the R&D, engineering teams and product manager teams, and help develop PoCs of the proposed standards.
• Help on organizing events related to standards or to research.

Closing date for applications:

Contact: Carlos Aguilar-Melchor <carlos.aguilar@sandboxaq.com>
Martin Albrecht <martin.albrecht@sandboxaq.com>

More information: https://www.sandboxaq.com/careers-list?gh_jid=4884446004

We are seeking a highly skilled and experienced Lead Cryptography Software Engineer to lead the development of a composable cryptographic library implementing post quantum cryptography. As the Lead Cryptographer, you will be responsible for designing, developing, and implementing cryptographic protocols and algorithms that are resistant to quantum attacks. You will work closely with our team of software developers to ensure that the cryptographic library is robust, efficient, and easy to use.

Core Responsibilities:

• Design, develop, and implement cryptographic protocols and algorithms that are resistant to quantum attacks.
• Lead the development of a disruptive composable cryptographic library that can be used in various applications and systems.
• Work closely with software developers and researchers to ensure that the cryptographic library is robust, efficient, and easy to use.
• Stay up-to-date with the latest developments in post quantum cryptography and integrate them into the library.
• Collaborate with other cryptographers and security experts to ensure that the library meets the highest security standards.
• Provide technical guidance and mentorship to junior members of the team.
• Manage the Open Source version of the library including the publication pipeline (from the internal repository) as well as the resulting artifacts (e.g. Python/Rust/Go packages)

Closing date for applications:

Contact: Carlos Aguilar-Melchor <carlos.aguilar@sandboxaq.com>

More information: https://www.sandboxaq.com/careers-list?gh_jid=4872332004

The SandboxAQ team is looking for a software engineer to help functionalize the next generation of cryptographic systems. A successful candidate will be comfortable with user space Linux development, network engineering, cryptographic algorithms and secure protocols. They will be part of a diverse team consisting of cryptographers, mathematicians, ML experts, and physicists, where they will play a key role in efficient and effective enablement of the technologies being developed.

Core Responsibilities

• Participating in the development of our cryptographic framework:
  • Design and implement various API along the cryptographic stack (from block ciphers to creating VPN tunnels)
  • Support for new tunneling protocols
• Provide guidance on software development scope, capacity, prioritization and best practices
• Perform profiling, identify potential performance tradeoffs

Closing date for applications:

Contact: Carlos Aguilar-Melchor <carlos.aguilar@sandboxaq.com>

More information: https://www.sandboxaq.com/careers-list?gh_jid=4800134004

We are inviting applications for a fully-funded PhD position at the Cluster of Excellence CASA. As the successful candidate, you will join the project Robust Certification of Quantum Devices and conduct fundamental research in the areas of:

Nonlocal games and self-testing

Quantum information and cryptography

Group and representation theory

At Bochum, you can expect a vibrant atmosphere of excellent research that spans across many areas of computer science and mathematics. In addition to an exciting research project and a friendly and stimulating work environment, we can offer a generous travel budget that allows for attending relevant conferences and summer schools to present your work to the international community, visiting collaborators, etc. The PhD program is entirely in English. You will be employed on a fully-funded position (100%, E13 salary) with an initial appointment of three years. The starting date is negotiable, but ideally in fall 2023. Your profile:

By default, you have a MSc degree (or be close to completing one) in computer science, mathematics, physics or related fields. Outstanding candidates with a BSc degree will also be considered.

You have an excellent track record in classes related to quantum information and cryptography, and/or more generally in mathematics and theoretical computer science.

You are curiosity driven, enjoy combining creativity with mathematical precision, and are open to interdisciplinary collaborations.

You are fluent in written and spoken English (no German required).

To apply, please email qi@rub.de with subject “CASA PhD Position” and the following information:

Brief cover letter describing your background and research interests.

CV, including transcripts (BSc + MSc).

Electronic contact details of 2 referees.

Any other relevant material (MSc thesis draft, BSc thesis, publications, …).

Applications received by July 10, 2023 will receive full consideration. We strongly encourage applications from members of any underrepresented group.

Closing date for applications:

Contact: qi@rub.de

About Pagoda
Pagoda is shepherding a future where NEAR becomes the blockchain operating system. We believe that re-inventing how software is made and distributed is our greatest opportunity to open economic access to those who are not fully integrated into the global economy. Our products empower people to find opportunity, invent new experiences, and collaborate. Let's build an Open Web world. A world where people control their assets, data, and power of governance.

About The Role
Pagoda is looking for a software engineer with experience building and maintaining cryptography and Zero-Knowledge projects. You will be the in-house expert on cryptography and Zero-Knowledge technology. You will initiate, implement, and lead a variety of projects in this area, including integrating the results of Zero-Knowledge research done by teams in the Near community into NEAR Protocol. Your work will have a major impact on the scalability and decentralization of NEAR Protocol.

What You'll Be Doing:

Apply advances in cryptography and Zero-Knowledge technology to improve security, scalability, and decentralization of NEAR Protocol.

Audit external ZK projects in the NEAR ecosystem and seek opportunities to integrate them into NEAR Protocol

Act as a subject matter expert and provide consultation to internal and external teams on Zero-Knowledge technology

What We're Looking For:

Knowledge and experience with cryptography

Knowledge and experience with Zero-Knowledge

Demonstrated experience writing well-structured, clean, maintainable code

Ability to learn new languages, APIs and SDKs quickly

Knowledge of Rust or other low-level language

Strong communication and remote friendly working skills

Bachelor’s Degree in Computer Science or related fields is a must

Familiarity with Ethereum development and related technologies (web3.js, ethers.js etc)

Familiarity with other crypto or blockchain technologies

Closing date for applications:

Contact: Jo Mount, Senior Recruiter - NEAR-Pagoda

More information: https://boards.greenhouse.io/pagoda/jobs/6736262002?gh_jid=6736262002

The Universitat Oberta de Catalunya (UOC) is a leading university of quality online education that is rooted in Catalonia and open to the world. It offers people lifelong learning to help them and society advance, while carrying out research into the knowledge society. It is the 2nd Spanish-speaking online educational institution in the world with more than 70.000 students in the academic year 2017/2018.

UOC has a research center, the Internet Interdisciplinary Institute (IN3), specialized in studying the study of the Internet and the effects of the interaction between digital technologies and human activity. Inside this research center there are 10 renowed research groups, one of them is the K-riptography and Information Security for Open Networks (KISON).

KISON is a research group focused on creating technologies for the protection of the security of networks, the information transmitted through them and the privacy of their users. The KISON group research lines focus on the compatibility of the security of decentralized networks (e.g. ad-hoc, P2P or IoT networks) and the protection of information in the Internet (especially multimedia contents) with users' rights to privacy.

We offer a two-year post-doc research position and a three-year PhD student position.

See the details at UOC website.

Closing date for applications:

Contact: Helena Rifà-Pous

More information: https://selection.uoc.edu/web/offersjob/offerdetails.aspx?offerID=90896BA916D3CDFD2D61A6285C121189E58DFA9D755F8FA3E04CC901FF357818

LIP6 and QAT teams have recently introduced several new protocols and approaches for the cryptographic verification of delegated quantum computations: - robust verification (PRX Quantum, 2021, arXiv:2109.04042) - multiparty verification (arXiv:2303.08865) - general framework for verification (arXiv:2206.00631) We are looking for a strong #phdstudent in cryptography to continue push the boundaries of what can be done to build trust in a future quantum-enabled computing environment. We are especially looking for motivated students mastering one or more of the following techniques: - composable security frameworks - post-quantum cryptography - construction of pseudo-random functions - random-oracle model Quantum mechanics fluency is not a necessity at first but can be acquired by interactions with the team. The PhD will be localized at LIP6 and Ecole normale supérieure (Paris), with opportunities to visit other research groups within Europe. Supervision will be done jointly by Elham Kashefi and Harold Ollivier. Funding is already secured. Send a CV + transcript + and motivation letter before june 30.

Closing date for applications:

Contact: Elham Kashefi (ekashefi@gmail.com) Harold Ollivier (harold.ollivier@inria.fr)

More information: https://qat.inria.fr

It all started with ECDSA nonces and keys duplications in a large amount of X.509 certificates generated by Cisco ASA security gateways, detected through TLS campaigns analysis.

After some statistics and blackbox keys recovery, it continued by analyzing multiple firmwares for those hardware devices and virtual appliances to unveil the root causes of these collisions. It ended up with keygens to recover RSA keys, ECDSA keys and signatures nonces.

The current article describes our journey understanding Cisco ASA randomness issues through years, leading to CVE-2023-20107 [CVE-2023-20107, CSCvm90511]. More generally, it also provides technical and practical feedback on what can and cannot be done regarding entropy sources in association with DRBGs and other random processing mechanisms.

In recent years, progress in practical applications of secure multi-party computation (MPC), fully homomorphic encryption (FHE), and zero-knowledge proofs (ZK) motivate people to explore symmetric-key cryptographic algorithms, as well as corresponding cryptanalysis techniques (such as differential cryptanalysis, linear cryptanalysis), over general finite fields $\mathbb{F}$ or the additive group induced by $\mathbb{F}^n$. This investigation leads to the break of some MPC/FHE/ZK-friendly symmetric-key primitives, the United States format-preserving encryption standard FF3-1 and the South-Korean standards FEA-1 and FEA-2. In this paper, we revisit linear cryptanalysis and give general results of linear approximations over arbitrary finite Abelian groups. We consider the nonlinearity, which is the maximal non-trivial linear approximation, to characterize the resistance of a function against linear cryptanalysis. The lower bound of the nonlinearity of a function $F:G\rightarrow H$ over an arbitrary finite Abelian group was first given by Pott in 2004. However, the result was restricted to the case that the size of $G$ divides the size of $H$ due to its connection to relative difference sets. We complete the generalization from $\mathbb{F}_2^n$ to finite Abelian groups and give the lower bound of $\lambda_F$ for all different cases. Our result is deduced by the new links that we established between linear cryptanalysis and differential cryptanalysis over general finite Abelian groups.

Amortized bootstrapping offers a way to refresh multiple ciphertexts of a fully homomorphic encryption scheme in parallel more efficiently than refreshing a single ciphertext at a time. Micciancio and Sorrell (ICALP 2018) first proposed the technique to bootstrap $n$ LWE ciphertexts simultaneously, reducing the total cost from $\tilde{O}(n^2)$ to $\tilde{O}(3^\epsilon n^{1+\frac{1}{\epsilon}})$ for arbitrary $\epsilon > 0$. Several recent works have further improved the asymptotic cost. Despite these amazing progresses in theoretical efficiency, none of them demonstrates the practicality of batched LWE ciphertext bootstrapping. Moreover, most of these works only support limited functional bootstrapping, i.e. only supporting the evaluation of some specific type of function when performing bootstrapping.

In this work, we propose a construction that is not only asymptotically efficient (requiring only $\tilde{O}(n)$ polynomial multiplications for bootstrapping of $n$ LWE ciphertexts) but also concretely efficient. We implement our scheme as a C++ library and show that it takes $< 5$ms per LWE ciphertext to bootstrap for a binary gate, which is an order of magnitude faster than the state-of-the-art C++ implementation on LWE ciphertext bootstrapping in OpenFHE. Furthermore, our construction supports batched arbitrary functional bootstrapping. For a 9-bit messages space, our scheme takes ${\sim}6.7$ms per LWE ciphertext to evaluate an arbitrary function with bootstrapping, which is about two to three magnitudes faster than all the existing schemes that achieve a similar functionality and message space.

In this work, we focus on maliciously secure 3PC for binary circuits with honest majority. While the state-of-the-art (Boyle et al. CCS 2019) has already achieved the same amortized communication as the best-known semi-honest protocol (Araki et al. CCS 2016), they suffer from a large computation overhead: when comparing with the best-known implementation result (Furukawa et al. Eurocrypt 2017) which requires $9\times$ communication cost of Araki et al., the protocol by Boyle et al. is around $4.5\times$ slower than that of Furukawa et al.

In this paper, we design a maliciously secure 3PC protocol that matches the same communication as Araki et al. with comparable concrete efficiency as Furukawa et al. To obtain our result, we manage to apply the distributed zero-knowledge proofs (Boneh et al. Crypto 2019) for verifying computations over $\mathbb{Z}_2$ by using \emph{prime} fields and explore the algebraic structure of prime fields to make the computation of our protocol friendly for native CPU computation.

Experiment results show that our protocol is around $3.5\times$ faster for AES circuits than Boyle et al. We also applied our protocol to the binary part (e.g. comparison and truncation) of secure deep neural network inference, and results show that we could reduce the time cost of achieving malicious security in the binary part by more than $67\%$.

Besides our main contribution, we also find a hidden security issue in many of the current probabilistic truncation protocols, which may be of independent interest.