International Association
for Cryptologic Research

We explore the possibility of obtaining general-purpose obfuscation for all circuits by way of making only simple, local, functionality preserving random perturbations in the circuit structure. Towards this goal, we use the additional structure provided by reversible circuits, but no additional algebraic structure.

We start by formulating a new (and relatively weak) obfuscation task regarding the ability to obfuscate random circuits of bounded length. We call such obfuscators random input & output (RIO) obfuscators. We then show how to construct indistinguishability obfuscators for all (unbounded length) circuits given only an RIO obfuscator --- under a new assumption regarding the pseudorandomness of sufficiently long random reversible circuits with known functionality, which in turn builds on a conjecture made by Gowers (Comb. Prob. Comp. '96) regarding the pseudorandomness of bounded-size random reversible circuits. Furthermore, the constructed obfuscators satisfy a new measure of security - called random output indistinguishability (ROI) obfuscation - which is significantly stronger than IO and may be of independent interest.

We then investigate the possibility of constructing RIO obfuscators using local, functionality preserving perturbations. Our approach is rooted in statistical mechanics and can be thought of as locally ``thermalizing'' a circuit while preserving its functionality. We provide candidate constructions along with a pathway for analyzing the security of such strategies.

Given the power of program obfuscation, viability of the proposed approach would provide an alternative route to realizing almost all cryptographic tasks under hardness assumptions that are very different from standard ones. Furthermore, our specific candidate obfuscators are relatively efficient: the obfuscated version of an n-wire, m-gate (reversible) circuit with security parameter k has n wires and poly(n,k)m gates. We hope that our initial exploration will motivate further study of this alternative path to cryptography.

We study a fundamental problem in Multi-Party Computation, which we call the Multiple Millionaires’ Problem (MMP). Given a set of private integer inputs, the problem is to identify the subset of inputs that equal the maximum (or minimum) of that set, without revealing any further information on the inputs beyond what is implied by the desired output. Such a problem is a natural extension of the Millionaires’ Problem, which is the very first Multi-Party Computation problem that was presented in Andrew Yao’s seminal work [31]. A closely related problem is MaxP, in which the value of the maximum is sought. We propose several approaches towards the solution of those fundamental problems as well as concrete solutions, and compare their performance. As applications of privacy-preserving computation are more and more commonly implemented in industrial systems, MMP and MaxP become important building blocks in privacy-preserving statistics, machine learning, auctions and other domains. One of the prominent advantages of our novel protocols is their simplicity. As they solve fundamental problems that are essential building blocks in various application scenarios, we believe that our systematic study of solutions to those problems, and the comparison between them, will serve well future researchers and practitioners of secure distributed computing.

Distributed models for differential privacy (DP), such as the local and shuffle models, allow for differential privacy without having to trust a single central dataholder. They do however typically require adding more noise than the central model. One commonly iterated remark is that achieving DP with similar accuracy as in the central model is directly achievable by \textit{emulating the trusted party}, using general multiparty computation (MPC), which computes a canonical DP mechanism such as the Laplace or Gaussian mechanism. There have been a few works proposing concrete protocols for doing this but as of yet, all of them either require honest majorities, only allow passive corruptions, only allow computing aggregate functions, lack formal claims of what type of DP is achieved or are not computable in polynomial time by a finite computer. In this work, we propose the first efficiently computable protocol for emulating a dataholder running the geometric mechanism, and which retains its security and DP properties in the presence of dishonest majorities and active corruptions. To this end, we first analyse why current definitions of computational DP are unsuitable for this setting and introduce a new version of computational DP, SIM$^*$-CDP. We then demonstrate the merit of this new definition by proving that our protocol satisfies it. Further, we use the protocol to compute two-party inner products with computational DP and with similar levels of accuracy as in the central model, being the first to do so. Finally, we provide an open-sourced implementation of our protocol and benchmark its practical performance.

We present a general method to simplify soundness proofs under certain conditions. Given an adversary $\mathcal{A}$ able to break a scheme $S$ with non-negligible probability $t$, we define the concept of $\textit{trace}$ of a $\textit{winning configuration}$, which is already implicitly used in soundness proofs. If a scheme can be constructed that (1) takes a random configuration $e$, being the inputs and execution environment of $\mathcal{A}$, (2) "guesses" a trace, (3) modifies $e$ based on its guess so that the modified configuration $e'$ is statistically indistinguishable from the original one, (4) is then able to execute $\mathcal{A}$ correctly under the condition that $e'$ is a winning configuration and that $B$'s guess of the trace was correct, and finally (5) that during its execution $\mathcal{A}$ is unable extract any information about $B$'s guess, then the probability of $B$ winning can be expressed as a simple function of $t$ and the bit-length of the trace, namely $\frac{t}{2^m}$. Soundness then results if $2^m$ is polynomial in the security parameter.

To illustrate the concept, a concrete application of this method to a simple binary voting scheme is then described in detail.

Efficient polynomial multiplication routines are critical to the performance of lattice-based post-quantum cryptography (PQC). As PQC standards only recently started to emerge, CPUs still lack specialized instructions to accelerate such routines. Meanwhile, deep learning has grown immeasurably in importance. Its workloads call for teraflops-level of processing power for linear algebra operations, mainly matrix multiplication. Computer architects have responded by introducing ISA extensions, coprocessors and special-purpose cores to accelerate such operations. In particular, Apple ships an undocumented matrix-multiplication coprocessor, AMX, in hundreds of millions of mobile phones, tablets and personal computers. Our work repurposes AMX to implement polynomial multiplication and applies it to the NTRU cryptosystem, setting new speed records on the Apple M1 and M3 systems-on-chip (SoCs).

Let n stands for the length of digital signatures with quadratic multivariate public rule in n variables. We construct postquantum secure procedure to sign O(n^t), t ≥1 digital documents with the signature of size n in time O(n^{3+t}). It allows to sign O(n^t), t <1 in time O(n^4). The procedure is defined in terms of Algebraic Cryptography. Its security rests on the semigroup based protocol of Noncommutative Cryptography referring to complexity of the decomposition of the collision element into composition into given generators. The protocol uses the semigroup of Eulerian transformations of variety (K*)^n where K* is a nontrivial multiplicative group of the finite commutative ring K. Its execution complexity is O(n^3). Additionally we use this protocol to define asymmetric cryptosystem with the space of plaintexts and ciphertexts (K*)^n which allows users to encrypt and decrypt O(n^t) documents of size n in time O(n^{3+[t]}) where [x] stands for the flow function from x. Finally we suggest protocol based cryptosystem working with plaintext space (K*)^n and the space of ciphertext K^n which allows decryption of O(n^t), t>1 documents of size n in time O(n^{t+3}), t>1. The multivariate encryption map has linear degree O(n) and density O(n^4). We discuss the idea of public key with Eulerian transformations which allows to sign O(n^t), t≥0 documents in time O(n^{t+2}). The idea of delivery and usage of several Eulerian and quadratic transformations is also discussed.

Homomorphic encryption enables public computation over encrypted data. In the past few decades, homomorphic encryption has become a staple of both the theory and practice of cryptography. Nevertheless, while there is a general loose understanding of what it means for a scheme to be homomorphic, to date there is no single unifying minimal definition that captures all schemes. In this work, we propose a new definition, which we refer to as combinatorially homomorphic encryption, which attempts to give a broad base that captures the intuitive meaning of homomorphic encryption and draws a clear line between trivial and nontrivial homomorphism.

Our notion relates the ability to accomplish some task when given a ciphertext, to accomplishing the same task without the ciphertext, in the context of communication complexity. Thus, we say that a scheme is combinatorially homomorphic if there exists a communication complexity problem $f(x,y)$ (where $x$ is Alice's input and $y$ is Bob's input) which requires communication $c$, but can be solved with communication less than $c$ when Alice is given in addition also an encryption $E_k(y)$ of Bob's input (using Bob's key $k$).

We show that this definition indeed captures pre-existing notions of homomorphic encryption and (suitable variants are) sufficiently strong to derive prior known implications of homomorphic encryption in a conceptually appealing way. These include constructions of (lossy) public-key encryption from homomorphic private-key encryption, as well as collision-resistant hash functions and private information retrieval schemes.

Event date: 9 September to 13 September 2024

Event date: 5 April 2024
Submission deadline: 2 February 2024
Notification: 5 March 2024

Event date: 30 July to 2 August 2024
Submission deadline: 28 February 2024
Notification: 3 May 2024

Event date: 1 July 2024
Submission deadline: 1 July 2024

POSITION OVERVIEW Position title: Assistant Professor, Security and Privacy Salary range: The salary range for this position is $115,000 - $125,000 academic year (nine-month basis) for Assistant Professors. Starting salary is commensurate with qualifications and experience. The posted UC salary scales set the minimum pay determined by rank and/or step at appointment. “Off-scale salaries” and other components of pay, i.e., a salary that is higher than the published system-wide salary at the designated rank and step, are offered when necessary to meet competitive conditions. See salary scales titled (Faculty--Ladder Ranks-- Business/Economics/Engineering) Percent time: Full-time, 100% Anticipated start: July 1, 2024, with the academic year beginning in September 2024. Degree requirements must be met by June 30, 2025 for employment beyond that date.

Closing date for applications:

Contact: Ioannis Demertzis or Alvaro Cardenas

More information: https://recruit.ucsc.edu/JPF01635

AIT is Austria's s largest research and technology organisation for applied research, located in Vienna.
The cryptography team is conducting research in the domain of public key cryptography, including secure communication, privacy-enhancing technologies, and long-term and post-quantum security. Our research covers the full spectrum from idea creation to the development of prototypes and demonstrators.

The team is seeking to grow, and is therefore looking for a PhD-student in the fields of privacy and security in distributed systems.

Through our AIT-PhD programme with 150 internationals students, conducted in collaboration with renowned universities, applicants will have the opportunity to conduct their PhD thesis in collaboration with our experts and our national and international project partners from industry or other research institutions.

Requirements:

• Applicants are required to hold a MSc degree (or equivalent) in computer science, mathematics, or a related field
• Basic knowledge of cryptography (at least one course specializing on cryptography) is expected
• Special interest in applied research and the solution of practical problems, in particular in the areas of cryptography and information security
• High level of commitment and ability to work in a team
• Good knowledge of a programming language (e.g., C/C++, Rust, Java, Python) and software development is a plus
• Very good written and oral English skills; knowledge of German is not a requirement

AIT values diversity and is committed to equality.

The minimum gross annual salary on a full-time basis (38,5 h / week) according to the collective agreement is EUR 53.578,--. The actual salary will be determined individually, based on your qualifications and experience. In addition, we offer company benefits, flexible working conditions, individual training and career opportunities.

All applications (including cover letter and full CV) need to be submitted using the following link: https://jobs.ait.ac.at/Job/224352

Closing date for applications:

Contact: Stephan Krenn (stephan.krenn[at]ait.ac.at)

More information: https://jobs.ait.ac.at/Job/224352

The School of Cyber Science and Engineering (formerly known as the School of Information Security Engineering) of Shanghai Jiao Tong University was founded in October 2000. It was the first school-level training base for high-level information security professionals in China and was jointly established by the Ministry of Education of China, the Ministry of Science and Technology of China, and the Shanghai Municipal People’s Government. The undergraduate and postgraduate students of the school mainly come from the top 100 key high schools and 985/double first-class universities in China. The school is ranked among the best cyberspace security nationwide every year. The school has a solid foundation and strength in the field of academic research and technological innovation on cyberspace security. The school is committed to building a world-class academic research center, cultivating the talents of the country and society. The school is in great demand of a number of world renowned professors, outstanding young researchers, full-time research fellows and post-doctors. The school now has a few positions available at the rank of tenure-track Assistant/Associate Professors, tenured Full Professors as well as Research Assistants/Associates and Post-Doctors in theory and practice of cyberspace security.

Applicants should have (a) a doctoral degree in Computer Science, Electronic Engineering, Communication, Mathematics or Statistics; (b) an established track record in research and scholarship; (c) expertise in the cryptographic and security research areas; and (d) a demonstrated commitment to excellence in teaching.

The school will provide highly competitive remuneration packages and assist applicants to apply for various national, provincial and ministerial level talent programs such as “Outstanding Youth Talents Program”, Shanghai “Talents Program”,etc. We will also assist on employment of spouses, schooling for children and medical care.

Closing date for applications:

Contact:
Chaoping Xing, emial: xingcp@sjtu.edu.cn; Ni Liang, email: liangni@sjtu.edu.cn

The Luxembourg Institute of Science and Technology (LIST) is a Research and Technology Organization (RTO) active in the fields of materials, environment and IT. By transforming scientific knowledge into technologies, smart data and tools, LIST empowers citizens in their choices, public authorities in their decisions and businesses in their strategies.

How will you contribute? Your specific mission includes, but is not limited to, participating into the following activities along with the project partners:

• To design and develop privacy-preserving federated data management technologies
• To prototype privacy-preserving technologies for cyberthreat intelligence, data analysis or cybersecurity
• To develop open-source software
• To validate the effectiveness of developed technologies You are in charge of disseminating and promoting the research activities that will be carried out, whether through publications, prototype development or technical reports

You’re highly motivated and have proven skills in federated data processing such as applying simple statistics or advanced machine learning tools, to improve the utility of the obtained information. You have already good experience in collaborative cyber threat intelligence systems that use advanced analytics solutions an can offer significant advantages over the local systems by detecting cyberattacks early and promptly responding to them. And last, but not least, you’re a great practitioner of privacy-enhancing techniques such as secure multiparty computation, homomorphic encryption, and anonymization. Is Your profile described below? Are you our future colleague? Apply now! As to join us, you:

• Hold a PhD. degree in Computer Science or related disciplines
• Have good programming skills (particularly experience on Python and C++)
• Have good track record on applied cryptography, such as secure multiparty computation and homomorphic encryption. Knowledge on secure aggregation techniques or zero-knowledge proofs is a plus.
• Demonstrate strong interest and experience in anonymization techniques such as differential privacy, Google’s RAPPOR

Closing date for applications:

Contact: Orhan Ermis

More information: https://app.skeeled.com/offer/6554879c69ccf56b0c1432df?utm_id=60fed4c509c80d16d1bbe536&utm_medium=OFFERS_PORTAL&language=en&show_description=true

Salary: GBP 36,024 to 41,732 per annum depending on experience

Fixed Term Contract until 30th September 2025

Closing Date: Monday 15th January

This post will work on challenges around decentralized identity and personal data, and approaches across distributed platforms such as Distributed Ledgers.

The Computer Science Research Centre at the University of Surrey is seeking to recruit a full-time researcher to the Surrey Centre for Cyber Security (SCCS). The successful candidate will join the DECaDE Next Stage Digital Economy Centre for the Decentralised Digital Economy (http://decade.ac.uk), a multidisciplinary UKRI-funded Centre with the University of Surrey, the University of Edinburgh, and the Digital Catapult.

The Centre is initially focused on three themes: value co-creation in the digital economy, data trusts for identity and data, and the world of work and the gig economy.

Surrey is recognized by the National Cyber Security Centre as an Academic Centre of Excellence in Cyber Security Research, and offers a thriving research environment with world leading researchers. We were also recognised as Cyber University of the Year 2023 in the National Cyber Awards. Our research includes security and privacy, verification, cryptography, distributed systems, and networked systems.

The position offers the platform for the research fellow to develop skills to become an independent researcher and to contribute to the DECaDE vision. The successful candidate will work within a team under the direction of Professor Steve Schneider. Significant interaction with project partners is encouraged, and the dissemination strategy may involve national and international travel, with many personal development opportunities.

Closing date for applications:

Contact: Contact: Professor Steve Schneider: s.schneider@surrey.ac.uk

More information: https://jobs.surrey.ac.uk/Vacancy.aspx?id=13775

The existence of "unstructured" hard languages in $\mathsf{NP} \,\cap\,\mathsf{coNP}$ is an intriguing open question. Bennett and Gill (SICOMP, 1981) asked whether $\mathsf{P}$ is separated from $\mathsf{NP} \cap \mathsf{coNP}$ relative to a random oracle, a question that remained open ever since. While a hard language in $\mathsf{NP} \,\cap\,\mathsf{coNP}$ can be constructed in a black-box way from a one-way permutation, for which only few (structured) candidates exist, Bitansky et al. (SICOMP, 2021) ruled out such a construction based on an injective one-way function, an unstructured primitive that is easy to instantiate heuristically. In fact, the latter holds even with a black-box use of indistinguishability obfuscation.

We give the first evidence for the existence of unstructured hard languages in $\mathsf{NP} \,\cap\,\mathsf{coNP}$ by showing that if $\mathsf{UP} \not \subseteq \mathsf{RP}$, which follows from the existence of injective one-way functions, the answer to Bennett and Gill's question is affirmative: with probability 1 over a random oracle $\cal O$, we have that $\mathsf{P}^{\cal O} \neq \mathsf{NP}^{\cal O} \cap \mathsf{coNP}^{\cal O}$. Our proof gives a constructive non-black-box approach for obtaining candidate hard languages in $\mathsf{NP} \,\cap\,\mathsf{coNP}$ from cryptographic hash functions.

The above conditional separation builds on a new construction of non-interactive zero-knowledge (NIZK) proofs, with a computationally unbounded prover, to convert a hard promise problem into a hard language. We obtain such NIZK proofs for $\mathsf{NP}$, with a uniformly random reference string, from a special kind of hash function which is implied by (an unstructured) random oracle. This should be contrasted with previous constructions of such NIZK proofs that are based on one-way permutations or other structured primitives, as well as with (computationally sound) NIZK arguments in the random oracle model.

Quantum Fourier Transformation (QFT) plays a key role in quantum computation theory. But its transform size has never discussed. In practice, the Xilinx LogiCORE IP Fast Fourier Transform core has the maximum transform size $N=2^{16}$. Taking into account the Planck constant $\hbar=6.62607015\times 10^{-34}$ and the difficulty to physically implement basic operator {\footnotesize $\left[ \begin{array}{cc} 1& 0\\ 0 & \exp(-2\pi\,i/N)\\ \end{array} \right]$} on some qubits, we think $N=2^{120}$ could be an upper bound for the transform size of QFT.

Maiorana--McFarland type constructions are basically concatenating the truth tables of linear functions on a smaller number of variables to obtain highly nonlinear ones on larger inputs. Such functions and their different variants have significant applications in cryptology and coding theory. Straightforward hardware implementation of such functions may require exponential resources on the number of inputs. In this paper, we study such constructions in detail and provide implementation strategies for a selected subset of this class with polynomial many gates over the number of inputs. We demonstrate that such implementations cover the requirement of cryptographic primitives to a great extent. Several existing constructions are revisited in this direction and exact implementations are provided with specific depth and gate counts in the hardware implementation. Related combinatorial as well as circuit complexity-related results of theoretical nature are also analyzed in this regard. Finally we present a novel construction of a new class of balanced Boolean functions having very low absolute indicator and very high nonlinearity that can be implemented in polynomial circuit size over the number of inputs. In conclusion, we present that these constructions have immediate applications to resist the signature generation in Differential Fault Attack (DFA) and to implement functions on large number of variables in designing ciphers for the paradigm of Fully Homomorphic Encryption (FHE).

The popularity of cloud computing has made outsourced databases prevalent in real-world applications. To protect data security, numerous encrypted outsourced databases have been proposed for this paradigm. However, the maintenance of encrypted databases has scarcely been addressed. In this paper, we focus on a typical maintenance task --- functional dependency (FD) discovery. We develop novel FD protocols in encrypted databases while guaranteeing minimal leakages: nothing is revealed besides the database size and the actual discovered FDs. As far as we know, we are the first to formally define secure FD discovery with minimal leakage.

We present two oblivious FD protocols and prove them secure in the presence of the persistent adversary (monitoring processes on the server). The first protocol leverages Oblivious RAM (ORAM) and is suitable for dynamic databases. The second protocol relies on oblivious sorting and is more practical in static databases due to high parallelism. We also present a thorough experimental evaluation of the proposed methods.