International Association
for Cryptologic Research

Hardness of approximation aims to establish lower bounds on the approximability of optimization problems in NP and beyond. We continue the study of hardness of approximation for problems beyond NP, specifically for \emph{stochastic} constraint satisfaction problems (SCSPs). An SCSP with $k$ alternations is a list of constraints over variables grouped into $2k$ blocks, where each constraint has constant arity. An assignment to the SCSP is defined by two players who alternate in setting values to a designated block of variables, with one player choosing their assignments uniformly at random and the other player trying to maximize the number of satisfied constraints.

In this paper, we establish hardness of approximation for SCSPs based on interactive proofs. For $k \leq O(\log n)$, we prove that it is $AM[k]$-hard to approximate, to within a constant, the value of SCSPs with $k$ alternations and constant arity. Before, this was known only for $k = O(1)$.

Furthermore, we introduce a natural class of $k$-round interactive proofs, denoted $IR[k]$ (for \emph{interactive reducibility}), and show that several protocols (e.g., the sumcheck protocol) are in $IR[k]$. Using this notion, we extend our inapproximability to all values of $k$: we show that for every $k$, approximating an SCSP instance with $O(k)$ alternations and constant arity is $IR[k]$-hard.

While hardness of approximation for CSPs is achieved by constructing suitable PCPs, our results for SCSPs are achieved by constructing suitable IOPs (interactive oracle proofs). We show that every language in $AM[k \leq O(\log n)]$ or in $IR[k]$ has an $O(k)$-round IOP whose verifier has \emph{constant} query complexity (\emph{regardless} of the number of rounds $k$). In particular, we derive a ``sumcheck protocol'' whose verifier reads $O(1)$ bits from the entire interaction transcript.

We introduce the problem of \emph{Verifiable Relation Sharing} (VRS) where a client wishes to share a vector of secret data items among several servers (the verifiers) while proving in zero-knowledge that the shared data satisfies some properties. This combined task of sharing and proving generalizes notions like verifiable secret sharing and zero-knowledge proofs over secret-shared data. We study VRS from a theoretical perspective and focus on its round complexity. \smallskip

As our main contribution, we show that every efficiently-computable relation can be realized by a VRS with an optimal round complexity of two rounds where the first round is input-independent (offline round). The protocol achieves full UC-security against an active adversary that is allowed to corrupt any $t$-subset of the parties that may include the client together with some of the verifiers. For a small (logarithmic) number of parties, we achieve an optimal resiliency threshold of $t=0.5(k+1)$, and for a large (polynomial) number of parties, we achieve an almost-optimal resiliency threshold of $t=0.5(k+1)(1-\epsilon)$ for an arbitrarily small constant $\epsilon>0$. Both protocols can be based on sub-exponentially hard injective one-way functions. If the parties have an access to a collision resistance hash function, we can derive \emph{statistical everlasting security}, i.e., the protocols are secure against adversaries that are computationally bounded during the protocol execution and become computationally unbounded after the protocol execution.

\smallskip Previous 2-round solutions achieve smaller resiliency thresholds and weaker security notions regardless of the underlying assumptions. As a special case, our protocols give rise to 2-round offline/online constructions of multi-verifier zero-knowledge proofs (MVZK). Such constructions were previously obtained under the same type of assumptions that are needed for non-interactive zero-knowledge proofs (NIZK), i.e., public-key assumptions or random-oracle type assumptions (Abe et al., Asiacrypt 2002; Groth and Ostrovsky, Crypto 2007; Boneh et al., Crypto 2019; Yang, and Wang, Eprint 2022). Our work shows, for the first time, that in the presence of an honest majority these assumptions can be replaced with more conservative ``Minicrypt''-type assumptions like injective one-way functions and collision-resistance hash functions. Indeed, our MVZK protocols provide a round-efficient substitute for NIZK in settings where honest-majority is present. Additional applications are also presented.

The COVID-19 pandemic has caused many countries to deploy novel digital contact tracing (DCT) systems to boost the efficiency of manual tracing of infection chains. In this paper, we systematically analyze DCT solutions and categorize them based on their design approaches and architectures. We analyze them with regard to effectiveness, security, privacy, and ethical aspects and compare prominent solutions with regard to these requirements. In particular, we discuss the shortcomings of the Google and Apple Exposure Notification API (GAEN) that is currently widely adopted all over the world. We find that the security and privacy of GAEN has considerable deficiencies as it can be compromised by severe large-scale attacks. We also discuss other proposed approaches for contact tracing, including our proposal TRACECORONA, that are based on Diffie-Hellman (DH) key exchange and aims at tackling shortcomings of existing solutions. Our extensive analysis shows thatTRACECORONA fulfills the above security requirements better than deployed state-of-the-art approaches. We have implementedTRACECORONA and its beta test version has been used by more than 2000 users without any major functional problems1, demonstrating that there are no technical reasons requiring to make compromises with regard to the requirements of DCTapproaches.

Interpose PUF~(iPUF) is a strong PUF construction that was shown to be vulnerable against empirical machine learning as well as PAC learning attacks. In this work, we extend the PAC Learning results of Interpose PUF to prove that the variants of iPUF are also learnable in the PAC model under the Linear Threshold Function representation class.

We present Shanrang, the first fully asynchronous proactive secret sharing scheme with dynamic committee support. Even in the worst possible network environment, where messages could have arbitrary latencies, Shanrang allows a dynamic committee to store a secret and periodically refresh the secret shares in a distributed fashion. When the committee changes, both the old committee and the new committee jointly refresh and transfer the shares to the new committee, without revealing the secret to the adversary.

With n parties, Shanrang tolerates n/4 Byzantine faults and maintains liveness as long as the messages are delivered. In contrast to prior work, Shanrang makes no assumptions on the network latency. Designing an asynchronous protocol is challenging because it is impossible to distinguish an adversary sending no messages from an honest party whose messages have not arrived yet. We evaluated Shanrang on geographically distributed machines and we found Shanrang achieved 200 seconds for handing off between 2 committees of 41 parties. Shanrang requires O(λn3 log n) messages and runs in expected O(log n) rounds for every handoff. To show Shanrang is robust even in a harsh network environ- ment, we test Shanrang on the Tor network and it shows robust performance.

In light of continued innovation in money and payments, many central banks are exploring the creation of a central bank digital currency (CBDC), a new form of central bank money which supplements existing central bank reserve account balances and physical currency.

This paper presents Hamilton, a flexible transaction processor design that supports a range of models for a CBDC and minimizes data storage in the core transaction processor by storing unspent funds as opaque hashes. Hamilton supports users custodying their own funds or custody provided by financial intermediaries.

We describe and evaluate two implementations: the atomizer architecture which provides a globally ordered history of transactions but is limited in throughput (170,000 transactions per second), and the 2PC architecture that scales peak throughput almost linearly with resources (up to a measured throughput of 1.7M transactions per second) but does not provide a globally ordered list of transactions.

We released our two architectures under the MIT open source license at https://github.com/mit-dci/opencbdc-tx.

Since its introduction at Asiacrypt 2017, the CKKS approximate homomorphic encryption scheme has become one of the most widely used and implemented homomorphic encryption schemes. Due to the approximate nature of the scheme, application developers using CKKS must ensure that the evaluation output is within a tolerable error of the corresponding cleartext computation. This is achieved by scaling the underlying raw data by an appropriate amount, known as the scale parameter, in order to preserve a certain amount of significant figures. Unfortunately, there is no clear guidance available for choosing an appro- priate scale parameter, with a trial-and-error approach typically advised. In this work, we significantly improve the state-of-affairs and present the following main contributions. We give a comprehensive theoretical and experimental analysis of CKKS noise, that considers noise coming from the encoding and homomorphic evaluation operations separately. This enables us to give the first explicit definition for precision in the CKKS context. Additionally, we demonstrate the applicability of our analysis to determine convergence properties of iterative algorithms that are commonly used in applications.

This work considers two prominent key management problems in the blockchain space: (i) allowing a (distributed) blockchain system to securely airdrop/send some tokens to a potential client Bob, who is yet to set up the required cryptographic key for the system, and (ii) creating a (distributed) cross-chain bridge that allows interoperability at scale by allowing a (changing) set of nodes in a blockchain to perform transactions on the other blockchain. The existing solutions for the first problem need Bob to either generate and maintain private keys locally for the first time in his life — a usability bottleneck — or place trust in third-party custodial services — a privacy and censorship nightmare. Towards solving both problems in a distributed setting against a threshold-bounded adversary, distributed key generation (DKG) based solutions are actively employed; here, a set of servers generate the transactions in a distributed manner and link them to clients’ ids. Nevertheless, these solutions introduce computation and communication overhead that is linear in the number of keys and do not scale well even for a million keys, especially for proactive security against a mobile adversary. This work presents a Keys-On-Demand (D-KODE) distributed protocol suite that lets the blockchain system securely generate the public key of any Bob against a mobile threshold adversary. Multiple servers, here, compute discrete-log private/public keys on the fly through distributed pseudo-random function evaluations on the queried public string. D-KODE also introduces a proactive security mechanism for the employed black-box secret-sharing based DKG to maintain the system’s longitudinal security. The proposed protocol scales well for a very high number of keys as its communication and computation complexity is independent of the number of keys. Our experimental analysis demonstrates that, for a 20-node network with a 2/3 honest majority, D-KODE starts to outperform the state of the art as the number of keys reaches 94K. D-KODE is practical as it takes less than 100msec to generate a secret key for a single-threaded server in a 20-node setup

The Institute of Information Security and Dependability at KIT is looking for two PostDocs in privacy-preserving cryptographic protocols. Experiences with secure multi-party computation and MPC compilers or UC-based security modeling are desired. A track record in this field is expected, including publications at reputable conferences such as Crypto, Eurocrypt, ACM CCS, PETS, etc.

You will be a member of the KASTEL Security Research Labs (https://zentrum.kastel.kit.edu) and the Topic "Engineering Secure Systems" of the Helmholtz Association. Your research is dealing with cryptographic protocols for privacy-preserving computations, e.g., applied to mobility or production systems. It will result in both theoretical security concepts (protocol designs, security proofs, etc.) and their practical implementation (e.g., a demonstrator) for some application domain. The contract will initially be limited to 1 year, but can be extended.

If you are interested, please send an email including your CV and a list of publications to andy.rupp@rub.de. Applications will be reviewed continuously until the positions are filled.

Closing date for applications:

Contact: Andy Rupp (andy.rupp@rub.de)

You will join the team responsible for the security architecture of Qualcomm Snapdragon processors. The team works at a system level spanning across hardware, software and infrastructure while striving for industry-leading solutions. This team interacts with product management, customers (e.g., OEMs), partners and HW/SW engineering teams to find the optimal security solutions.
Snapdragon processors are used in different types of devices ranging from mobile phones to televisions, cars, ultra-book laptops etc. Our processors are designed to meet security requirements ranging from content protection to enterprise security, using virtualization, HW security enclaves, factory key provisioning, and secure updates.
In this position you will perform the following tasks:

• Define HW crypto security requirements (functional, performance, security etc)
• Define HW/SW partitioning to address next challenges in cryptography such as PQC and Crypto Agility
• Define crypto and HW blocks that contribute to the overall SoC Security Architecture
• Design of mechanisms thwarting side channel attacks
• Monitor evaluation of crypto IP resistance and robustness
• Competitive analysis of security IPs and features
• Investigate future/roadmap security related technologies,
• Participation in academic conference and industrial/research security working groups.

Minimum Qualifications: MS or Bachelor in Computer Science, Mathematics or Electrical Engineering plus 5+ years industry experience in one or more of the following areas

• Cryptographic primitives, cryptographic protocols and their implementation
• Design of HW/SW security blocks such as HW cryptographic engines
• HW/SW threat analysis, security analysis or/and risk analysis
• Smart Card and secure HW technologies
• Security certifications: process and requirements.

Additional skills in the following areas are a plus:

• Academic and industry research (publications, conferences)
• Leadership & management background
• Excellent communication and teamwork skills are required

Closing date for applications:

Contact: Nicolas Courtois

More information: https://qualcomm.wd5.myworkdayjobs.com/en-US/External/details/Embedded-Crypto-Expert---Sophia-Antipolis--France_3024348-1?locationCountry=54c5b6971ffb4bf0b116fe7651ec789a

Event date: 26 July to 28 July 2022
Submission deadline: 15 March 2022
Notification: 25 May 2022

Event date: 10 July to 16 July 2022
Submission deadline: 1 April 2022
Notification: 15 May 2022

Event date: 31 August to 2 September 2022
Submission deadline: 26 March 2022
Notification: 30 May 2022

Your Challenge Help bring research to life and drive your career forward with the National Research Council of Canada (NRC), Canada's largest research and technology organization. We are looking for an early-career Research Associate to support our Digital Technologies research centre (DT). The Research Associate would be someone who shares our core values of Integrity, Excellence, Respect and Creativity. Help bring research to life and drive your career forward with the National Research Council of Canada (NRC), Canada's largest research and technology organization. Working with the NRC is an exciting opportunity to pursue a research career both independently and with a dynamic research team. We are looking for a Research Associate to join NRC’s Digital Technologies Research Centre (NRC-DT). The Digital Technologies Research Centre collects multiple research teams who focus on machine learning, advanced analytics, computer vision, bioinformatics, cyber security, natural language processing, quantum computing and other branches of digital technologies and artificial intelligence. The primary responsibility of the researcher in this position is to support the goals of NRC and the activities of the Digital Technologies Research Centre in conducting research of international calibre in applied quantum computing, including quantum algorithms and software, quantum error correction, theoretical models of quantum computing and other related areas. The researcher will work in a team environment with other researchers and technical experts in world-class facilities. The researcher will participate in the development and execution of an original research agenda in collaboration with NRC colleagues and with academic and commercial partners across Canada. The researcher will be called upon to contribute to collaborative research projects in support of NRC’s Applied Quantum Computing challenge program.

Closing date for applications:

Contact: Human Resources at: NRC.NRCHiring-EmbaucheCNRC.CNRC@nrc-cnrc.gc.ca

More information: https://recruitment-recrutement.nrc-cnrc.gc.ca/job-invite/15641

The Cryptanalysis Taskforce at Nanyang Technological University in Singapore led by Prof. Jian Guo is seeking for candidates to fill several post-doctoral research fellow positions on symmetric-key cryptography. Topics include but are not limited to the following sub-areas:

• tool aided cryptanalysis, such as MILP, CP, STP, and SAT
• machine learning aided cryptanalysis and designs
• privacy-preserving friendly symmetric-key designs
• quantum cryptanalysis
• provable security
• cryptanalysis against SHA-2, SHA-3, and AES
• threshold cryptography

Established in 2014, the Cryptanalysis Taskforce is a group with about ten members currently dedicated for research in symmetric-key cryptography. Since establishment, the team has been active in both publications in and services for IACR. It has done quite some cryptanalysis work on various important targets such as SHA-3 and AES, and is expanding its interests to the areas mentioned above, with strong funding support from the university, industry partners, and government agencies in Singapore. We offer globally competitive salary package with extremely low tax (around 5%), as well as excellent environment dedicating for top-venues publication orientated research in Singapore. The contract will be initially for one year, and has the possibility to be extended. Candidates are expected to have proven record of publications in IACR conferences (Asiacrypt, Crypto, Eurocrypt). Interested candidates are to send their CV and 2 reference letters to Jian Guo. Review of applicants will start immediately until the positions are filled. More information about the Cryptanalysis Taskforce research group can be found via https://team.crypto.sg

Closing date for applications:

Contact: Jian Guo, guojian@ntu.edu.sg, with subject [IACR-CATF]

More information: https://team.crypto.sg

We are looking for a Postdoc fellow in the area of security of wireless IoT networks.
The project is jointly conducted between Mohammed VI Polytechnic University, Morocco, and EPFL Switzerland.
To apply, please send your cv with your list of publications.

Closing date for applications:

Contact: Mehdi Amhoud, email : elmehdi.amhoud(at)um6p.ma

About Protocol Labs Protocol Labs drives breakthroughs in computing to push humanity forward. Protocol Labs is a product-development lab, but behind the protocols and tools we build, behind the research and implementations, are passionate people, teammates and community members. We are a fully distributed company. Our team of more than 150 members works remotely and in the open to improve the internet — humanity's most important technology — as we explore new advances at the intersection of many exciting fields (crypto, networks, distributed systems) and cultures (startups, research, open source, distributed work). Seeking an experienced cryptographer to help us research and develop state of the art cryptosystems to upgrade the internet. Research at Protocol Labs This isn't an ordinary Research Scientist position. Your expertise is mostly driven by both a hunger to learn and a need to work toward solving important problems. Our research scientists are granted both the freedom to develop their knowledge by working on novel applications, and a responsibility to contribute those skills toward advancing the flagship projects of Protocol Labs. You’ll feel at home working with us if your knowledge and optimism enables you to name a few unusual possible approaches when you’re first presented with a problem that people often consider intractable. We see cryptography often acting as the last line of defense in a world that’s rife with malicious actors. We examine a broad spectrum of potential projects, like Filecoin, that rely on providing various cryptographic guarantees to users. Achieving these guarantees in practice often requires drawing from or advancing the frontiers of cryptographic protocols. As a result, we seek cryptographers who can discover, conceive, incorporate, and implement new techniques.

Closing date for applications:

Contact: Apply here- https://boards.greenhouse.io/protocollabs/jobs/4283969004

More information: https://boards.greenhouse.io/protocollabs/jobs/4283969004

The submission deadline for CRYPTO 2022 is 16 February 2022 (AoE) and the submission server is now open.

Instructions for authors and the link to submission server can be found here https://crypto.iacr.org/2022/papersubmission.php.

We describe a straightforward method to generate a random prime q such that the multiplicative group GF(q)* also has a random large prime-order subgroup. The described algorithm also yields this order p as well as a p'th primitive root of unity. The methods here are efficient asymptotically, but due to large constants may not be very useful in practical settings.

The past couple of decades witnessed a tremendous expansion in the IoT world that gathers now billions of devices, sensors, users and transactions. The aspirations of ubiquitous computing have changed the computing world drastically, from a parallel point of view, to distributed, then grid and cloud computing – all these just to keep up with the proliferation of devices and the users’ expectations. Alongside with this fast development, many issues appeared, especially in terms of scalability and security. Regardless of protocol, device, applications or technologies used, there will be critical data involved and, therefore, vulnerabilities that can affect the performance of the system or be exploited maliciously. The higher the number of devices, the more constraints appear and along with these constraints the existing models and technologies become overwhelmed and simply not enough. The size of the IoT and its autonomous character make it impossible to sustain and implement a centralized authentication system. Therefore, to allow reliable peer authentication and to approach a trust level management, we propose discussing a model based on blockchain technology. Blockchain is a revolutionary technology, modeled by a linear sequence of blocks, considered to be the future of wireless networks security. We rely on this new data structure to address two major components of security in mobile networks: authentication and trust.