International Association
for Cryptologic Research

We present a construction of indistinguishability obfuscation for null quantum circuits (null-iO) with respect to a classical oracle, assuming the quantum hardness of the learning with errors (LWE) problem. Heuristically instantiating the classical oracle with quantum-secure indistinguishability obfuscation for classical circuits gives us the first candidate construction of null-iO for quantum circuits. This scheme establishes the feasibility of a series of new cryptographic primitives that, prior to our work, were unknown to exist even making heuristic assumptions. Specifically, we obtain (in some cases additionally assuming indistinguishability obfuscation for classical circuits):

* A witness encryption (WE) scheme for QMA.

* A publicly-verifiable non-interactive zero-knowledge (NIZK) argument for QMA.

* A two-message publicly-verifiable witness-indistinguishable (ZAPR) argument for QMA.

* An attribute-based encryption (ABE) scheme for BQP.

* A secret sharing scheme for monotone QMA.

University of Lübeck is a modern and renowned research university specialized in Computer Science and Engineering, Medicine and Life Sciences.

The young and growing Institute for IT Security performs cutting-edge research in security-critical applications and their protection in insecure environments. Explored methods range from secure computation methods and cryptographic protocols to software and hardware mechanisms for protecting system security. In addition, we analyze security of existing systems as well as the improvement and automation of analysis techniques for protocols and implementations.

Your Profile:
In order to complement our team, we are looking for a full-time PhD researcher in one the following topics:

• Analysis and design of trusted execution environments and secure microarchitectures
• Secure distributed computing
• Automated code analysis and application security analysis

Required Qualifications:
As ideal candidate, you are highly motivated, independent and able to perform creative and deep research. Your main areas of interest are in system security and/or applied cryptography and you have experience in the areas of cryptography, algorithms, code analysis, embedded programming, and/or machine learning.
You have a MSc degree in Computer Science, Applied Mathematics, Information and Computer Engineering, or comparable related field and an excellent command of written and spoken English.

We offer excellent working conditions in an international team of cutting-edge researchers and ample opportunity to collaborate with renowned researchers worldwide.

Closing date for applications:

Contact: Thomas Eisenbarth: its.bewerbungen@uni-luebeck.de
Please apply by April 15 and mention position code 1011/21.

More information: https://www.its.uni-luebeck.de/en/jobs.html

Modern implementations of homomorphic encryption (HE) rely heavily on polynomial arithmetic over a finite field. This is particularly true of the CKKS, BFV, and BGV HE schemes. Two of the biggest performance bottlenecks in HE primitives and applications are polynomial modular multiplication and the forward and inverse number- theoretic transform (NTT). Here, we introduce Intel® Homomorphic Encryption Acceleration Library (Intel® HEXL), a C++ library which provides optimized implementations of polynomial arithmetic for Intel® processors. Intel HEXL takes advantage of the recent Intel® Advanced Vector Extensions 512 (Intel® AVX512) instruction set to provide state- of-the-art implementations of the NTT and modular multiplication. On the forward and inverse NTT, Intel HEXL provides up to 7.2x and 6.7x speedup, respectively, over a native C++ implementation. Intel HEXL also provides up to 6.0x speedup on the element-wise vector-vector modular multiplication, and 1.7x speedup on the element-wise vector- scalar modular multiplication. Intel HEXL is available open-source at https://github.com/intel/hexl under the Apache 2.0 license.

We propose an efficient quantum algorithm for a specific quantum state discrimination problem. An immediate corollary of our result is a polynomial time quantum algorithm for the Dihedral Coset Problem with a smooth modulus. This, in particular, implies that $\text{poly}(n)$-unique-SVP is in BQP.

The Ring-LWE over two-to-power cyclotomic integer rings has been the hard computational problem for lattice cryptographic constructions. Its hardness and the conjectured hardness of approximating ideal SIVP for ideal lattices in two-to-power cyclotomic fields have been the fundamental open problems in lattice cryptography and the complexity theory of computational problems of ideal lattices. In this paper we present a general theory of sublattice attack on the Ring-LWE with not only the Gaussian error distribution but also general error distributions. By the usage of our sublattice attack we prove that the decision Ring-LWE over two-to-power cyclotomic integer rings with certain polynomially bounded modulus parameters when degrees d_n = 2^{n−1} going to the infinity can be solved by a polynomial (in d_n) time algorithm for wide error distributions with widths in the range of Peikert-Regev-Stephens-Davidowitz hardness reduction results in their STOC 2017 paper. Hence we also prove that approximating idealSIV Ppoly(dn) with some polynomial factors for ideal lattices in two-to-power cyclotomic fields can be solved within quantum polynomial time. Therefore the lattice cryptographic constructions can not be based on the ”hardness” of Ring-LWE over two-to-power cyclotomic integer rings even in the classical computational model.

Digital signatures are used to verify the authenticity of digital messages, that is, to know with a high level of certainty, that a digital message was created by a known sender and was not altered in any way. This is usually achieved by using asymmetric cryptography, where a secret key is used by the signer, and the corresponding public key is used by those who wish to verify the signed data. In many use-cases, such as blockchain, the history and order of the signed data, thus the signatures themselves, are important. In blockchains specifically, the threat is forks, where one can double-spend its crypto-currency if one succeeds to publish two valid transactions on two different branches of the chain. We introduce a single private/public key pair signature scheme using verifiable random function, that binds a signer to its signature history. The scheme enforces a single ordered signatures' history using a deterministic verifiable chain of signature functions that also reveals the secret key in case of misbehaviors.

Blockchain-based cryptocurrencies offer an appealing alternative to Fiat currencies, due to their decentralized and borderless nature. However the decentralized settings make the authentication process more challenging: Standard cryptographic methods often rely on the ability of users to reliably store a (large) secret information. What happens if one user's key is lost or stolen? Blockchain systems lack of fallback mechanisms that allow one to recover from such an event, whereas the traditional banking system has developed and deploys quite effective solutions.

In this work, we develop new cryptographic techniques to integrate security policies (developed in the traditional banking domain) in the blockchain settings. We propose a system where a smart contract is given the custody of the user's funds and has the ability to invoke a two-factor authentication (2FA) procedure in case of an exceptional event (e.g., a particularly large transaction or a key recovery request). To enable this, the owner of the account secret-shares the answers of some security questions among a committee of users. When the 2FA mechanism is triggered, the committee members can provide the smart contract with enough information to check whether an attempt was successful, and nothing more.

We then design a protocol that securely and efficiently implements such a functionality: The protocol is round-optimal, is robust to the corruption of a subset of committee members, supports low-entropy secrets, and is concretely efficient. As a stepping stone towards the design of this protocol, we introduce a new threshold homomorphic encryption scheme for linear predicates from bilinear maps, which might be of independent interest.

To substantiate the practicality of our approach, we implement the above protocol as a smart contract in Ethereum and show that it can be used today as an additional safeguard for suspicious transactions, at minimal added cost. We also implement a second scheme where the smart contract additionally requests a signature from a physical hardware token, whose verification key is registered upfront by the owner of the funds. We show how to integrate the widely used universal two-factor authentication (U2F) tokens in blockchain environments, thus enabling the deployment of our system with available hardware.

Code that is highly optimized poses a problem for program-level verification: programmers can employ various clever tricks that are non-trivial to reason about. For cryptography on low-power devices, it is nonetheless crucial that implementations be functionally correct, secure, and efficient. These are usually crafted in hand-optimized machine code that eschew conventional control flow as much as possible.

We have formally verified such code: a library which implements elliptic curve cryptography on 8-bit AVR microcontrollers. The chosen implementation is the most efficient currently known for this microarchitecture. It consists of over 3000 lines of assembly instructions. Building on earlier work, we use the Why3 platform to model the code and prove verification conditions, using automated provers. We expect the approach to be re-usable and adaptable, and it allows for validation. Furthermore, an error in the original implementation was found and corrected, at the same time reducing its memory footprint. This shows that practical verification of cutting-edge code is not only possible, but can in fact add to its efficiency—and is clearly necessary.

Anonymous identity-based identification scheme in the ad-hoc group is a multi-party cryptographic primitive that allows participants to form an ad-hoc group and prove membership anonymously in such a group. In this paper, we cryptanalyze an ad-hoc anonymous identity-based identification scheme proposed by Barapatre and Rangan and show that the scheme is not secure against key-only universal impersonation attack. We note that anyone can impersonate as a valid group member to convince the honest verifier successfully, even without knowing the group secret key. Moreover, we proposed a fix on the scheme and provide a security proof for our fixed scheme. The fixed scheme we proposed fulfills the security requirements of an ad-hoc anonymous identity-based identification scheme that are correctness, soundness, and anonymity.

Data trading is an emerging business, in which data sellers provide buyers with, for example, their private datasets and get paid from buyers. In many scenarios, sellers prefer to sell pieces of data, such as statistical results derived from the dataset, rather than the entire dataset. Meanwhile, buyers wish to hide the results they retrieve. Since it is not preferable to rely on a trusted third party (TTP), we are wondering, in the absence of TTP, whether there exists a \emph{practical} mechanism satisfying the following requirements: the seller Sarah receives the payment if and only if she \emph{obliviously} returns the buyer Bob the \emph{correct} evaluation result of a function delegated by Bob on her dataset, and Bob can only derive the result for which he pays. Despite a lot of attention data trading has received, a \emph{desirable} mechanism for this scenario is still missing. This is due to the fact that general solutions are inefficient when the size of datasets is considerable or the evaluated function is complicated, and that existing efficient cryptographic techniques cannot fully capture the features of our scenario or can only address very limited computing tasks.

In this paper, we propose the \emph{first desirable} mechanism that is practical and supports a wide variety of computing tasks --- evaluation of arbitrary functions that can be represented as polynomials. We introduce a new cryptographic notion called \emph{blind polynomial evaluation} and instantiate it with an explicit protocol. We further combine this notion with the blockchain paradigm to provide a \emph{practical} framework that can satisfy the requirements mentioned above.

Uncloneable encryption, introduced by Broadbent and Lord (TQC'20), is an encryption scheme with the following attractive feature: an adversary cannot create multiple ciphertexts which encrypt to the same message as the original ciphertext. The constructions proposed by Broadbent and Lord have the disadvantage that they only guarantee one-time security; that is, the encryption key can only be used once to encrypt the message.

In this work, we study uncloneable encryption schemes, where the encryption key can be re-used to encrypt multiple messages. We present two constructions from minimal cryptographic assumptions: (i) a private-key uncloneable encryption scheme assuming post-quantum one-way functions and, (ii) a public-key uncloneable encryption scheme assuming a post-quantum public-key encryption scheme.

We consider a set of security and privacy problems under reliability and storage constraints that can be tackled by using codes and particularly focus on the secret-key agreement problem. Polar subcodes (PSCs) are polar codes (PCs) with dynamically-frozen symbols and have a larger code minimum distance than PCs with only statically-frozen symbols. A randomized nested PSC construction, where the low-rate code is a PSC and the high-rate code is a PC, is proposed for successive cancellation list (SCL) and sequential decoders. This code construction aims to perform lossy compression with side information, i.e., Wyner-Ziv (WZ) coding. Nested PSCs are used in the key agreement problem with physical identifiers and two terminals since WZ-coding constructions significantly improve on Slepian-Wolf coding constructions such as fuzzy extractors. Significant gains in terms of the secret-key vs. storage rate ratio as compared to nested PCs with the same list sizes are illustrated to show that nested PSCs significantly improve on all existing code constructions. The performance of the nested PSCs is shown to improve with larger list sizes, unlike the nested PCs considered. A design procedure to efficiently construct nested PSCs and possible improvements to the nested PSC designs are also provided.

Do you want beneficial technologies being shaped by your ideas? Whether in the areas of mobility solutions, consumer goods, industrial technology or energy and building technology – with us, you will have the chance to improve quality of life all across the globe. Welcome to Bosch.

The Robert Bosch GmbH is looking forward to your application!

Job Description

• As a PhD in our research group you are contributing to research and development projects in an open source context.
• This includes understanding, evaluating and applying Privacy-Preserving Computing Technologies (PPCTs) including Computing On Encrypted Data techniques, Trusted Execution Environments, and methods for Statistical Disclosure Control.
• Embedded into a team of security and cloud technology experts, you apply your knowledge on PPCTs to design, implement and evaluate PPCT-based solutions in the context of the Franco-German BMBF/MESRI-funded CRYPTECS research project.
• Thanks to your insights, you help combine PPCTs and Cloud Native technologies to make PPCTs ready for use in an industrial context.
• Your responsibility includes the design, development and prototypical implementation of PPCT solutions. You push the state of the art in the field of PPCTs and publish your results together with renowned researchers from the international CRYPTECS consortium.

Qualifications

• Education: Very good master’s degree in computer science or related discipline, ideally combined with initial experience in the area of Cloud Native technologies
• Personality: Positive team player, who is highly motivated, has an innovative mindset, is eager to learn new things, and is passionate about applied research
• Working Practice: Initial hands-on experience with software development, ideally in an open source context
• Experience and Knowledge: Knowledge in the area of cryptography, ideally experience in PPCTs and modern Cloud Native technologies
• Languages: Fluent in English (written and spoken)
<

Closing date for applications:

Contact:
Need support during your application?
Kevin Heiner (Human Resources), Phone: +49 711 811 12223
Need further information about the job?
Dr. Sven Trieflinger (Functional Department), Phone: +49 711 811 24801

More information: https://smrtr.io/5fm_3

A Statistical Information Theoretic Secure (SITS) system utilizing the Chinese Remainder Theorem (CRT), coupled with Fully Homomorphic Encryption (FHE) for Distributed Communication-less Secure Multiparty Computation (DCLSMPC) of any Distributed Unknown Finite State Machine (DUFSM) is presented. Namely, secret shares of the input(s) and output(s) are passed to/from the computing parties, while there is no communication between them throughout the computation. We propose a novel approach of transition table representation and polynomial representation for arithmetic circuits evaluation, joined with a CRT secret sharing scheme and FHE to achieve SITS communication-less within computational secure execution of DUFSM. We address the severe limitation of FHE implementation over a single server to cope with a malicious or Byzantine server. We use several distributed memory-efficient solutions that are significantly better than the majority vote in replicated state machines, where each participant maintains an FHE replica. A Distributed Unknown Finite State Machine (DUFSM) is achieved when the transition table is secret shared or when the (possible zero value) coefficients of the polynomial are secret shared, implying communication-less SMPC of an unknown finite state machine.

In proof-of-stake (PoS) blockchains, stakeholders that extend the chain are selected according to the amount of stake they own. In S\&P 2019 the ``Ouroboros Crypsinous'' system of Kerber et al.\ (and concurrently Ganesh et al.\ in EUROCRYPT 2019) presented a mechanism that hides the identity of the stakeholder when adding blocks, hence preserving anonymity of stakeholders both during payment and mining in the Ouroboros blockchain. They focus on anonymizing the messages of the blockchain protocol, but suggest that potential identity leaks from the network-layer can be removed as well by employing anonymous broadcast channels.

In this work we show that this intuition is flawed. Even ideal anonymous broadcast channels do not suffice to protect the identity of the stakeholder who proposes a block.

We make the following contributions. First, we show a formal network-attack against Ouroboros Crypsinous, where the adversary can leverage network delays to distinguish who is the stakeholder that added a block on the blockchain. Second, we abstract the above attack and show that whenever the adversary has control over the network delay -- within the synchrony bound -- loss of anonymity is inherent for any protocol that provides liveness guarantees. We do so, by first proving that it is impossible to devise a (deterministic) state-machine replication protocol that achieves basic liveness guarantees and better than $(1-2\f)$ anonymity at the same time (where $\f$ is the fraction of corrupted parties). We then connect this result to the PoS setting by presenting the tagging and reverse tagging attack that allows an adversary, across several executions of the PoS protocol, to learn the stake of a target node, by simply delaying messages for the target. We demonstrate that our assumption on the delaying power of the adversary is realistic by describing how our attack could be mounted over the Zcash blockchain network (even when Tor is used). We conclude by suggesting approaches that can mitigate such attacks.

We study uncloneable quantum encryption schemes for classical messages as recently proposed by Broadbent and Lord. We focus on the information-theoretic setting and give several limitations on the structure and security of these schemes: Concretely, 1) We give an explicit cloning-indistinguishable attack that succeeds with probability $\frac12 + \mu/16$ where $\mu$ is related to the largest eigenvalue of the resulting quantum ciphertexts. 2) For a uniform message distribution, we partially characterize the scheme with the minimal success probability for cloning attacks. 3) Under natural symmetry conditions, we prove that the rank of the ciphertext density operators has to grow at least logarithmically in the number of messages to ensure uncloneable security. 4) The \emph{simultaneous} one-way-to-hiding (O2H) lemma is an important technique in recent works on uncloneable encryption and quantum copy protection. We give an explicit example which shatters the hope of reducing the multiplicative "security loss" constant in this lemma to below 9/8.

The k-XOR problem can be generically formulated as the following: given many n-bit strings generated uniformly at random, find k distinct of them which XOR to zero. This generalizes collision search (two equal elements) to a k-tuple of inputs.

This problem has become ubiquitous in cryptanalytic algorithms. Applications include variants in which the XOR operation is replaced by a modular addition (k-SUM) or other non-commutative operations (e.g., the composition of permutations). The case where a single solution exists on average is of special importance.

The generic study of quantum algorithms k-XOR (and variants) was started by Grassi et al. (ASIACRYPT 2018), in the case where many solutions exist. At EUROCRYPT 2020, Naya-Plasencia and Schrottenloher defined a class of "quantum merging algorithms" obtained by combining quantum search. They represented these algorithms by a set of "merging trees" and obtained the best ones through linear optimization of their parameters.

In this paper, we give a new, simplified representation of merging trees that makes their analysis easier. As a consequence, we improve the quantum time complexity of the Single-solution k-XOR problem by relaxing one of the previous constraints, and making use of quantum walks. Our algorithms subsume or improve over all previous quantum generic algorithms for Single-solution k-XOR. For example, we give an algorithm for 4-XOR (or 4-SUM) in quantum time $\widetilde{\mathcal{O}}(2^{7n/24})$.

In this work, we study disappearing cryptography in the bounded storage model. Here, a component of the transmission, say a ciphertext, a digital signature, or even a program, is streamed bit by bit. The stream is so large for anyone to store in its entirety, meaning the transmission effectively disappears once the stream stops.

We first propose the notion of online obfuscation, capturing the goal of disappearing programs in the bounded storage model. We give a negative result for VBB security in this model, but propose candidate constructions for a weaker security goal, namely VGB security. We then demonstrate the utility of VGB online obfuscation, showing that it can be used to generate disappearing ciphertexts and signatures. All of our applications are NOT possible in the standard model of cryptography, regardless of computational assumptions used.

We push a little further the study of two characterizations of almost perfect nonlinear (APN) functions introduced in our recent monograph. We state open problems about them, and we revisit in their perspective a well-known result from Dobbertin on APN exponents. This leads us to new results about APN power functions and more general APN polynomials with coefficients in a subfield F_{2^k} , which ease the research of such functions and of differentially uniform functions, and simplifies the related proofs by avoiding tedious calculations. In a second part, we give slightly simpler proofs than in the same monograph, of two known results on Boolean functions, one of which deserves to be better known but needed clarification, and the other needed correction.

Current proofs of current multi-signature schemes yield bounds on adversary advantage that are loose, failing to match the indications of cryptanalysis, and failing to justify security of implementations of the schemes in the 256-bit groups that are the choice of practioners. We bridge this gap via proofs in the Algebraic Group Model (AGM). For classical 3-round schemes we give AGM proofs with tight bounds. We then give a new 2-round multi-signature scheme, as efficient as prior ones, for which we prove a tight AGM bound. These results are obtained via a framework in which a reduction is broken into a chain of sub-reductions involving intermediate problems. By giving as many as possible of the sub-reductions tightly in the standard model, we minimize use of the AGM, and also hedge the AGM proofs with standard-model ones from different starting points.