International Association
for Cryptologic Research

It is known that fully homomorphic encryption (FHE) can be used to build efficient (labeled) Private Set Intersection protocols in the unbalanced setting, where one of the sets is much larger than the other (Chen et al. (CCS'17, CCS'18)). In this paper we demonstrate multiple algorithmic improvements upon these works. In particular, our protocol has an asymptotically better computation cost, requiring only $\bigO(\sqrt{\| X \|})$ homomorphic multiplications, and communication complexity sublinear in the larger set size $\| X \|$.

We demonstrate that our protocol is significantly better than that of Chen et al. (CCS'18) for many practical parameters, especially in terms of online communication cost. For example, when intersecting $2^{28}$ and 2048 item sets, our protocol reduces the online computation time by more than 71% and communication by more than 63%. When intersecting $2^{24}$ and 4096 item sets, our protocol reduces the online computation time by 27% and communication by 63%. Our comparison to other state-of-the-art unbalanced PSI protocols shows that our protocol has the best total communication complexity when $\| X \| \geq 2^{24}$. For labeled PSI our protocol also outperforms Chen et al. (CCS'18). When intersecting $2^{20}$ and $256$ item sets, with the larger set having associated 288-byte labels, our protocol reduces the online computation time by more than 67% and communication by 34%.

Finally, we demonstrate a modification that results in nearly constant communication cost in the larger set size $\| X \|$, but impractically high computation complexity on today's CPUs. For example, to intersect a $210$-item set with sets of size $2^{22}$, $2^{24}$, or $2^{26}$, our proof-of-concept implementation requires only 0.76 MB of online communication, which is more than a 24-fold improvement over Chen et al. (CCS'18).

A secret sharing scheme enables the dealer to share a secret among $n$ parties. A classic secret sharing scheme takes the number $n$ of parties and the secret as the input. If $n$ is not known in advance, the classic secret sharing scheme may fail. Komargodski, Naor, and Yogev \cite[TCC 2016]{KNY16} first proposed the evolving secret sharing scheme that only takes the secret as the input. In the work \cite[TCC 2016]{KNY16}, \cite[TCC 2017]{KC17} and \cite[Eurocrypt 2020]{BO20}, evolving threshold and ramp secret sharing schemes were extensively investigated. However, all of their constructions except for the first construction in \cite{BO20} are inspired by the scheme given in \cite{KNY16}, namely, these schemes rely on the scheme for st-connectivity which allows to generate infinite number of shares.

In this work, we revisit evolving secret sharing schemes and present three constructions that take completely different approach. Most of the previous schemes mentioned above have more combinatorial flavor, while our schemes are more algebraic in nature. More precisely speaking, our evolving secret sharing schemes are obtained via either the Shamir secret sharing or arithmetic secret sharing from algebraic geometry codes alone. Our first scheme is an evolving $k$-threshold secret sharing scheme with share size $k^{1+\epsilon}\log t$ for any constant $\epsilon>0$. Thus, our scheme achieves almost the same share size as in \cite[TCC 2016]{KNY16}. Moreover, our scheme is obtained by a direct construction while the scheme in \cite[TCC 2016]{KNY16} that achieves the $(k-1)\log t$ share size is obtained by a recursive construction which makes their structure complicated. Our second scheme is an evolving $k_t$-threshold secret sharing scheme with any sequence $\{k_t\}_{t=1}^\infty$ of threshold values that has share size $t^4$. This scheme improves the share size by $\log t$ given in \cite{KC17} where a dynamic evolving $k_t$-threshold secret sharing scheme with the share size $O(t^4\log t)$ was proposed. In addition, we also show that if the threshold values $k_t$ grow in rate $\lfloor \beta t\rfloor$ for a real $\beta\in(0,1)$, then we have a dynamic evolving threshold secret sharing scheme with the share size $O(t^{4\beta})$. For $\beta<0.25$, this scheme has sub-linear share size which was not known before. Our last scheme is an evolving $(\Ga t,\Gb t)$-ramp secret sharing scheme with constant share size. One major feature of this ramp scheme is that it is multiplicative as the scheme is also an arithmetic secret sharing scheme. We note that the same technique in \cite{KC17} can also transform all of our schemes to a robust scheme as our scheme is linear.\footnote{We note that by replacing the building block scheme with an arithmetic secret sharing scheme, the evolving $(\Ga t,\Gb t)$-ramp secret sharing scheme in \cite{BO20} can also be multiplicative. However, their share size is much bigger than ours as each party hold multiple shares. }

Recently, several cryptosystems have been proposed based semidirect products of various algebraic structures. Efficient attacks against several of them have already been given, including one very general attack which, unfortunately, does not apply to the MOBS system. The purpose of this note is to provide an observation that can be used as a point-of-attack for similar systems, and show how it can be used to efficiently cryptanalyze the MOBS system.

Doubly Efficient Private Information Retrieval (DEPIR) enables queries to an externally held database while hiding the identity of the queried indices, strengthening standard Private Information Retrieval (Chor, Goldreich, Kushilevitz, Sudan FOCS'95) with an efficiency requirement that the computational demands of both client and server are sublinear in the database size. The first DEPIR candidate constructions were recently put forth, based on a new type of assumption relating to indistinguishability of moderate-degree polynomials from random functions when given permuted versions of their evaluation graphs (Boyle, Ishai, Pass, Wootters TCC'17 and Canetti, Holmgren, Richelson TCC'17). To aid in the cryptanalytic study of this new assumption, the work of (BIPW TCC'17) put forth a simpler ``toy conjecture'' variant.

In this note, we present an attack that provably breaks the BIPW TCC'17 toy conjecture. The attack identifies a natural embedding of permuted samples into a higher-dimensional linear space for which permuted polynomial samples will be rank deficient. We note, however, that our attack does not apply to the real assumption underlying the constructions, and thus the candidates still stand. We discuss extensions of the attack and present an alternative ``new toy conjecture'' for future study.

Similar results were independently obtained by (Blackwell and Wootters, ArXiv'21).

Some key agreement schemes, such as Diffie--Hellman key agreement, reduce to Rabi--Sherman key agreement, in which Alice sends $ab$ to Charlie, Charlie sends $bc$ to Alice, they agree on key $a(bc) = (ab)c$, where multiplicative notation here indicates some specialized associative binary operation.

All non-interactive key agreement schemes, where each peer independently determines a single delivery to the other, reduce to this case, because the ability to agree implies the existence of an associative operation. By extending the associative operation’s domain, the key agreement scheme can be enveloped into a mathematical ring, such that all cryptographic values are ring elements, and all key agreement computations are ring multiplications. (A smaller envelope, a semigroup instead of a ring, is also possible.)

Security relies on the difficulty of division: here, meaning an operator $/$ such that $((ab)/b)b = ab$. Security also relies on the difficulty of the less familiar wedge operation $[ab, b, bc] \mapsto abc$.

When Rabi--Sherman key agreement is instantiated as Diffie--Hellman key agreement: its multiplication amounts to modular exponentiation; its division amounts to the discrete logarithm problem; the wedge operation amounts to the computational Diffie--Hellman problem.

Ring theory is well-developed and implies efficient division algorithms in some specific rings, such as matrix rings over fields. Semigroup theory, though less widely-known, also implies efficient division in specific semigroups, such as group-like semigroups.

The rarity of key agreement schemes with well-established security suggests that easy multiplication with difficult division (and wedges) is elusive.

Reduction of key agreement to ring or semigroup multiplication is not a panacea for cryptanalysis. Nonetheless, novel proposals for key agreement perhaps ought to run the gauntlet of a checklist for vulnerability to well-known division strategies that generalize across several forms of multiplication. Ambitiously applying this process of elimination to a plethora of diverse rings or semigroups might also, if only by a fluke, leave standing a few promising schemes, which might then deserve a more focused cryptanalysis.

Who We Are

PQShield is a cybersecurity startup that specialises in post-quantum cryptography. Based in Paris, PQShield SAS concentrates the research activities of PQShield. Our mission is to come up with innovative algorithmic and/or protocol-level solutions to real-world cryptographic problems. Besides post-quantum cryptographic primitives, our research interests include advanced cryptosystems/protocols such as secure messaging, threshold schemes, and multiparty computation.

Who We Are Looking For

We are looking for cryptographers with expertise in fields pertaining, but not limited, to post-quantum cryptography. Recruits will work with the team and provide new insights on research topics such as advanced cryptographic primitives, improvements to state-of-the-art practical cryptographic schemes, or constructions and proofs of security in models such as the QROM.

Skills we are interested in:

• Deep knowledge of a relevant cryptographic field. We want future recruits to impulse new directions for our research and expand the spectrum of expertise of PQShield.
• Adaptability. You will be expected to work with a diverse team on projects that can cover various cryptographic fields.
• Dissemination of results. Working at PQShield entails publishing new research in top cryptographic conferences, and advertising our team’s work through invited talks, workshops, or blog articles.

What We Offer

• Competitive salaries. Yearly salaries start at 45,000 € for post-docs, and 65,000 € for full-fledged researchers.
• Stimulating environment. You will work with some of the best researchers in theoretical and practical aspects of post-quantum cryptography.
• Flexible work conditions. PQShield SAS has spacious and fully equipped offices in the heart of Paris. In addition, remote working and more specific arrangements (e.g. academic mobility programmes) are possible.

How To Apply
Please send your CV and cover letter to jobs (at) pqshield.com.

Closing date for applications:

Contact: jobs(at)pqshield.com

More information: https://www.linkedin.com/jobs/view/2704606293/

Applications are invited for the Ph.D. position in Information Security at the Department of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung, Taiwan. The successful candidate will work under the guidance of Arijit Karati on the diverse topics in Applied Cryptology.

Responsibilities:
Apart from academic work, student must involve in several activities in a group or individually, such as (not limited to):

Design and implementation of security protocol.

Assesment of the security and performance metric.

Meeting with the supervisor.

Requirements:
Apart from the university's basic admission policies (https://cse.nsysu.edu.tw/?Lang=en), students are desired to have following key requirements:

Strong motivation on information security.

Knowledge of modern technology.

Knowledge of basic mathematics for cryptography.

Knowledge of at least two programming languages, such as Python/Java/C/C++.

Scholarship:

Under the university policy.

Project funding (based on students' performance).

What students can expect:

Cooperation from the supervisor and labmates.

The rich culture in research and related activities.

Flexibility in communication, e.g., English.

What the supervisor can expect:

Apart from academic and research works, students are expected to have good moral character.

Hardworking and dedication.

Closing date for applications:

Contact: Arijit Karati (arijit.karati@mail.cse.nsysu.edu.tw)

We are the Vac team (https://vac.dev/), and we are building a communications tool with security, censorship resistance and privacy in mind; Vac, Waku v2 and Ethereum Messaging for more.

Can you help us research and develop new and existing technologies in secure messaging?

Key Responsibilities:
- Research and develop open protocols for secure messaging. Think zkSNARKs based spam protection/settlement, data consistency in distributed open and hostile environments, incentivized running of nodes, and similar {example a, b, c….}
- Use a layered protocol approach that is mindful and explicit about what it requires, what it provides, under what threat models, and with what trade-offs.
-Combine cryptoeconomics and traditional technologies to create a sustainable distributed and fault-tolerant system.
- Write and maintain Nim code.
- Research and design core functionality.
- Provide feedback on overall design decisions and participate in code reviews.
- Use libp2p to build application-level protocols.
- Build incentivized, distributed systems.
- Interpret and implement solutions based on academic research.

Skills Knowledge and Expertise
[Don’t worry if you don’t meet all of these criteria, we’d still love to hear from you anyway if you think you’d be a great fit for this role!]
- A passion for blockchain technology, privacy-preserving technology and decentralization ; a strong alignment to our principles: https://status.im/about/#our-principles
- Very strong academic or engineering background (PhD-level or equivalent in industry); relevant research experience
- Experience with Zero Knowledge proofs and related technologies.
- Experience with low level/strongly typed languages (C/C++/Go/Rust or Java/C#).
- Experience with Open Source software.
- Experience designing incentive systems and writing/deploying smart contracts in Ethereum.

Bonus points if:
- Contributed to a blockchain or privacy-preserving-related, open source project.
- Experience with Nim.
- Experience with libp2p / devp2p, networking, cryptography.

Closing date for applications:

Contact: Angel via discord @ LilChiChi#0021

More information: https://jobs.status.im/en/jobs/17893

Event date: 10 November to 11 November 2021

Event date: 25 November to 26 November 2021
Submission deadline: 15 October 2021

Event date: 17 October 2021

The Institute for Computer Architecture and Computer Engineering (Institut für Technische Informatik, ITI) at the University of Stuttgart seeks applications for a research position in the field of secure hardware for postquantum cryptography. The position is associated with the BMBF project QuantumQAP, which aims at developing hybrid quantum-classical optimization methods for improving secure FPGA implementations of postquantum algorithms. The work will involve Thales Germany and three further partners; regular visits to project partners’ sites will be expected. The position is foreseen for PhD candidates.

Located in Stuttgart, one of Europe’s main economic hubs, the Institute offers you an inspiring working atmosphere in a successful international team. The remuneration is according to the German public-service salary grade TV-L E13.

To qualify for this position, you need an above-average Master’s degree in Computer Science, Electrical Engineering or a related discipline. Moreover, we expect proven skills or experiences in at least one of the three areas listed below (and credible interest in the other two):

1. Design of digital circuits on FPGA platforms, including their specification in VHDL, synthesis, simulation on different levels of abstraction.
2. Hardware-oriented security, ideally with a focus on resilience of cryptographic implementations against physical attacks (side-channel analysis, fault-injections).
3. Applied post-quantum cryptography, with an in-depth knowledge of the NIST finalists CRYSTALS-DILITHIUM, FALCON, Classic McElliece, and SIKE KEM.

To apply, please send, by email, your cover letter (explicitly explaining your interest in the topic and pointing out which of the three above-mentioned areas you feel competent in), CV and scans of your Master’s and Bachelor’s degree certificates including the transcripts with all grades. You can add, optionally, reference letters, existing publications, or other supplementary materials you consider relevant, or links to such materials. We will not answer applications which do not discuss qualifications for this project.

Closing date for applications:

Contact: Prof. Dr. Ilia Polian Institut für Technische Informatik Pfaffenwaldring 47 D-70569 Stuttgart, Germany ilia.polian@informatik.uni-stuttgart.de

More information: https://www.iti.uni-stuttgart.de/en/chairs/hocos/open_positions/

We propose a second-order masking of the AES in hardware that requires an order of magnitude less random bits per encryption compared to previous work. The design and its security analysis are based on recent results by Beyne et al. from Asiacrypt 2020. Applying these results to the AES required overcoming significant engineering challenges by introducing new design techniques. Since the security analysis is based on linear cryptanalysis, the masked cipher needs to have sufficient diffusion and the S-box sharing must be highly nonlinear. Hence, in order to apply the changing of the guards technique, a detailed study of its effect on the diffusion of the linear layer becomes important. The security analysis is automated using an SMT solver. Furthermore, we propose a sharpening of the glitch-extended probing model that results in improvements to our concrete security bounds. Finally, it is shown how to amortize randomness costs over multiple evaluations of the masked cipher.

Physical side-channel attacks like power analysis pose a serious threat to cryptographic devices in real-world applications. Consequently, devices implement algorithmic countermeasures like masking. In the past, works on the design and verification of masked software implementations have mostly focused on simple microprocessors that find usage on smart cards. However, many other applications such as in the automotive industry require side-channel protected cryptographic computations on much more powerful CPUs. In such situations, the security loss due to complex architectural side-effects, the corresponding performance degradation, as well as discussions of suitable probing models and verification techniques are still vastly unexplored research questions. We answer these questions and perform a comprehensive analysis of more complex processor architectures in the context of masking-related side effects. First, we analyze the RISC-V SweRV core — featuring a 9-stage pipeline, two execution units, and load/store buffers — and point out a significant gap between security in a simple software probing model and practical security on such CPUs. More concretely, we show that architectural side effects of complex CPU architectures can significantly reduce the protection order of masked software, both via formal analysis in the hardware probing model, as well as empirically via gate-level timing simulations. We then discuss the options of fixing these problems in hardware or leaving them as constraints to software. Based on these software constraints, we formulate general rules for the design of masked software on more complex CPUs. Finally, we compare several implementation strategies for masking schemes and present in a case study that designing secure masked software for complex CPUs is still possible with overhead as low as 13%.

We present an actively secure threshold scheme in the setting of Hard Homogenous Spaces (HHS) which allows &#64257;ne-grained access structures. More precisely, we elevate a given passively secure isogeny based threshold scheme to an actively secure setting. We prove the active security and simulatability of our advanced schemes. By de&#64257;ning some characterising properties, we are able to expand the range of secret sharing schemes which support the given scheme. Furthermore, we show that Shamir’s scheme has our generalised properties, and thereby our approach truly represents a less restrictive generalisation.

As humanity struggles to contain the global COVID pandemic, privacy concerns are emerging regarding confinement, tracing and testing.

The scientific debate concerning privacy of the COVID tracing efforts has been intense, especially focusing on the choice between centralised and decentralised tracing apps. The privacy concerns regarding COVID \underline{testing}, however, have not received as much attention even though the privacy at stake is arguably even higher. COVID tests require the collection of samples. Those samples possibly contain viral material but inevitably also human DNA. Patient DNA is not necessary for the test but it is technically impossible to avoid collecting it. The unlawful preservation, or misuse, of such samples at a massive scale may hence disclose patient DNA information with far-reaching privacy consequences.

Inspired by the cryptographic concept of ``Indistinguishability under Chosen Plaintext Attack'', this paper poses the blueprint of novel types of tests allowing to detect viral presence without leaving persisting traces of the patient's DNA.

Deep Learning Side-Channel Attacks (DLSCAs) have become a realistic threat to implementations of cryptographic algorithms, such as Advanced Encryption Standard (AES). By utilizing deep-learning models to analyze side-channel measurements, the attacker is able to derive the secret key of the cryptographic alrgorithm. However, when traces have multiple leakage intervals for a specific attack point, the majority of existing works train neural networks on these traces directly, without a preprocess step for each leakage interval. This degenerates the quality of profiling traces due to noise and non-primary components. In this paper, we first divide the multi-leaky traces into leakage intervals and train models on different intervals separately. Afterwards, we concatenate these neural networks to build the final network, which is called multi-input model. We test the proposed multi-input model on traces captured from STM32F3 microcontroller implementations of AES-128 and show a 2-fold improvement over the previous single-input attacks.

Higher-order power residues have enabled the construction of numerous public-key encryption schemes, authentication schemes, and digital signatures. Their explicit characterization is however challenging; an algorithm of Caranay and Scheidler computes $p$-th power residue symbols, with $p \le 13$ an odd prime, provided that primary elements in the corresponding cyclotomic field can be efficiently found.

In this paper, we describe a new, generic algorithm to compute primary elements in cyclotomic fields; which we apply for $p=3,5,7,11,13$. A key insight is a careful selection of fundamental units as put forward by D\'enes.

This solves an essential step in the Caranay--Scheidler algorithm. We give a unified view of the problem. Finally, we provide the first efficient deterministic algorithm for the computation of the 9-th and 16-th power residue symbols.

Abstract. in this paper, we improve the results of linear approximation of SNOW-V and SNOW-Vi.We optimized the automatic search program by replacing the S-box part with accurate characterizations of the Walsh spectral of S-boxes, which results in a series of trails with higher correlations. On the basis of existing results, we investigate the common features of linear approximation trails with high correlation, and search for more trails by exhausting free masks. By summing up the correlations of trails with the same input and output masks, we get closer to the real correlation. As a result, we get a linear approximation with a correlation -2^{-47.76},which results in a correlation attack on SNOW-V and SNOW-Vi with a time complexity 2^{246:53}, data complexity 2^{237.5} and memory complexity 2^{238.77}.

ZUC-256 is a stream cipher designed for 5G applications and is currently being under evaluation for standardized algorithms in 5G mobile telecommunications by Security Algorithms Group of Experts (SAGE). A notable feature of the round update function of ZUC-256 is that many operations are defined over different fields, which significantly increases the difficulty to analyze the algorithm. In this paper, we develop new techniques to carefully control the interactions between these operations defined over different fields. Moreover, while the designers expect that only simple input differences can be exploited to mount a practical attack on 27 initialization rounds, which is indeed implied in the 28-round practical attack discovered by Babbage and Maximov, we demonstrate that much more complex input differences can be utilized to achieve practical attacks on more rounds of ZUC-256. At the first glance, our techniques are somewhat similar to that developed by Wang et al. for the MD-SHA hash family. However, as ZUC-256 is quite different from the MD-SHA hash family, we are indeed dealing with different problems and overcoming new obstacles. With the discovered complex input differences, we are able to present the first practical distinguishing attacks on 31 out of 33 rounds of ZUC-256 and 30 out of 33 rounds of the new version of ZUC-256 called ZUC-256-v2, respectively. It is unpredictable whether our attacks can be further extended to more rounds with more advanced techniques. Based on the current attacks, we believe that the full 33 initialization rounds are marginal.