International Association
for Cryptologic Research

We present the first systematic security evaluation of multi-attribute range search schemes on symmetrically encrypted data. We present four database reconstruction attacks that apply to a broad class of schemes and rely on volume and search pattern leakage. For schemes achieving efficiency by decomposing a query into a small number of subqueries, we further show how to exploit their structure pattern, i.e., co-occurrences of subqueries. We introduce a flexible framework for building secure range search schemes by adapting a broad class of geometric search data structures (including range trees and quadtrees) to operate on encrypted data. We give four concrete range search schemes within our framework that support queries on an arbitrary number of dimensions (attributes) and offer a sliding scale of efficiency and security trade-offs. We provide a security proof for any scheme derived from our framework and a thorough analysis of the leakage of our concrete schemes, characterizing the set of equivalent databases and demonstrating information theoretic limitations on reconstruction attacks. Our attacks are the first that do not require the observation of the access pattern to reconstruct data from range queries in two and higher dimensions. Our work shows that for range queries, structure pattern leakage can be as vulnerable to attacks as access pattern leakage. We give a comprehensive evaluation of our schemes and attacks with a complexity analysis, a prototype implementation, and an experimental assessment on real-world datasets.

NTRUEncrypt is one of the first lattice-based encryption schemes. Furthermore, one of the first fully homomorphic encryption (FHE) schemes were built on the NTRU problem. What makes NTRU appealing when designing cryptosystems is the age of the problem and relatively good performance results when compared to ring learning with errors.

Unfortunately, current fully homomorphic schemes based on NTRU became extremely impractical duo to efficient sublattice attacks. Roughly speaking, these types of (leveled) homomorphic encryption schemes, to support a reasonable depth of the circuit we want to evaluate, require publishing RLWE or NTRU encryptions with a very large modulus. Unfortunately, recovering the sublattice and breaking the NTRU problem for such large moduli turns out to be easy, and to compensate, one would need to choose an impractically large dimension. We call NTRU instances with a too large modulus ``overstretched''. Due to the sublattice attacks, any serious work on practical NTRU-based fully homomorphic encryption essentially stopped.

In this paper, we reactivate research on practical FHE that can be based on NTRU. To do so, we design an efficient bootstrapping scheme in which the noise growth is small enough to keep the modulus to dimension ratio relatively small, thus avoiding the negative consequences of ``overstretching'' the modulus. Our bootstrapping algorithm is an accumulation-type bootstrapping scheme analogous to FHEW/TFHE. Finally, we show that we can use the bootstrapping procedure to compute any function over $\mathbb{Z}_p$. Consequently, we obtain one of the fastest FHE schemes to compute arithmetic circuits over finite fields.

Recently, there has been an increase in the popularity of messaging applications that use end-to-end encryption. Among them were Telegram (in October 2021 it has 550 million active users), Signal (in January 2022 it has over 50 million downloads in the Google Play Store), WhatsApp (according to Statista, in 2021 it has over 2 billion active users), Wire (until January 2022 it has been downloaded for over 1 million times on Android devices). Two distinct protocols underlying these applications are noted: MTProto (developed in Russia by Nikolai Durov) and Signal (developed in the US by Moxie Marlinspike). This paper presents the two protocols and examines from the point of view of the primitive cryptographic security used and how the authenticated encryption, key derivation and asynchronous messaging are performed.

Smart contracts are a new form of software that will revolutionize how software is written, IT systems are maintained, and applications and whole businesses are built. Smart contracts are composable and autonomous pieces of software that run on decentralized blockchains, which makes them tamperproof and unstoppable. In this paper, we describe the Internet Computer (IC), which is a radical new design of blockchain that unleashes the full potential of smart contracts, overcoming the limitations of smart contracts on traditional blockchains with respect to speed, storage costs, and computational capacity. This allows smart contracts for the first time to implement fully decentralized applications that are hosted end to end on blockchain. The IC consists of a set of cryptographic protocols that connects independently operated nodes into a collection of blockchains. These blockchains host and execute ``canisters'', the IC’s form of smart contracts. Canisters can store data, perform very general computations on that data, and provide a complete technology stack, serving web pages directly to end users. Computational and storage costs are covered by a ``reverse-gas model'', where canister developers pre-pay costs in cycles that are obtained from ICP, the native token of the IC. ICP tokens are also used for governance: the IC is governed by a decentralized autonomous organization, or DAO, which, among other things, determines changes to the topology of the network and upgrades to the protocol.

In 2019, Gabizon, Williamson, and Ciobotaru introduced PlonK – a fast and flexible ZK-SNARK with an updatable and universal structured reference string. PlonK uses a grand product argument to check permutations of wire values, and exploits convenient interactions between multiplicative subgroups and Lagrange bases. The following year, Gabizon and Williamson used similar techniques to develop plookup – a ZK-SNARK that can verify that each element from a list of queries can be found in a public lookup table. In this paper, we present PlonKup, a fully succinct ZK-SNARK that integrates the ideas from plookup into PlonK in an efficient way.

Recently, Ateniese et al. (CRYPTO 2019) proposed a new cryptographic primitive called matchmaking encryption (ME), which provides fine-grained access control over encrypted data by allowing both the sender and receiver to specify access control policies. The encrypted message can be decrypted correctly if and only if the attributes of the sender and receiver simultaneously meet each other's specified policies. In current ME, when users from different organizations need secret communication, they need to be managed by a single-authority center. However, it is more reasonable if users from different domains obtain secret keys from their own authority centers, respectively. Inspired by this, we extend ME to cross-domain scenarios. Specifically, we introduce the concept of the cross-domain ME and instantiate it in the identity-based setting (i.e., cross-domain identity-based ME). Then, we first formulate and design a cross-domain identity-based ME (IB-ME) scheme and prove its privacy and authenticity in the random oracle model. Further, we extend the cross-domain IB-ME to the multi-receiver setting and give the formal definition, concrete scheme and security proof. Finally, we analyze and implement the schemes, which confirms the efficiency feasibility.

About Status

As a product, Status is an open source, Ethereum-based app that gives users the power to chat, transact, and access a revolutionary world of DApps on the decentralized web. But Status is also building foundational infrastructure for the whole Ethereum ecosystem, including the Nimbus ETH 1.0 and 2.0 clients, the Keycard hardware wallet, and the Waku messaging protocol (a continuation of Whisper).

The role:

You’ll work within a small team to contribute to the design and implementation of the next generation of distributed storage solutions. This effort aligns well with the storage requirements for both the Status chat client as well as the Ethereum ecosystem at large. Familiarity with message propagation in loosely connected networks, DHTs, gossiping and routing mechanisms is highly desirable. Experience with massively distributed systems is a plus. Familiarity with off the shelf networking stacks such as libp2p or devp2p is also desirable.

Responsibilities:

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.

Strong understanding of p2p building blocks such as gossiping, routing and discovery (DHTs), Nat traversal.

Strong understanding of TCP and UDP protocols.

Strong understanding of encryption and key exchange mechanisms.

Ability to interpret and implement solutions based on academic research.

You must have:

Strong passion for blockchain technology and decentralisation.

Strong academic or engineering background.

Experience with low level/strongly typed languages (C/C++/Go/Rust or Java/C#).

Experience with Open Source software.

Experience building networking heavy applications and p2p networking specifically

Bonus points if you have:

Contributed to an blockchain-related, open source project.

Experience with Nim.

Experience with libp2p / devp2p, networking, cryptography.

Worked on storage and file systems.

Closing date for applications:

Contact: Email: angel@status.im Discord: LilChiChi#0021

More information: https://jobs.status.im/?gh_jid=3704158

As part of the teaching and research role, the Lecturer contributes to at least one of the interdisciplinary cybersecurity research areas such as applied cryptography, blockchain, privacy-preserving machine learning etc., and will engage in teaching, including the development of education resources and new course units; and research of cutting-edge cyber security technologies and practices.

You should have a PhD (or nearly finish PhD) and demonstrate expertise in one or more of the following research areas: cryptography (including zero-knowledge proofs, secure multi-party computation and other advanced primitives), interdisciplinary cybersecurity, human aspects of cybersecurity, secure critical infrastructures, blockchain technology, security of AI and machine learning, and security requirements engineering.

Interested party can apply through this link: https://careers.pageuppeople.com/513/cw/en/job/629426/lecturersenior-lecturer-identified-position-women

Closing date for applications:

Contact: Joseph Liu ( joseph . liu @ monash . edu )

More information: https://careers.pageuppeople.com/513/cw/en/job/629426/lecturersenior-lecturer-identified-position-women

Applications are invited for the M.S. and Ph.D. positions in Information Security at the Department of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung, Taiwan. Successful candidates will work at CANSEC Lab on various topics in Applied Cryptology under the supervision of Arijit Karati. Expertise in post-quantum cryptography, secure vehicle communication, edge computing, satellite communication, and 6G security may be beneficial. We are seeking students dedicated to their research and are highly motivated. There are currently 05 openings (03 for M.S. and 02 are Ph.D.).

Responsibilities:
Aside from academic work, students must participate in various activities, either in a group or individually, including (but not limited to):

Security protocol design and implementation.

Assessment of the security and performance metric.

On a regular basis, meet with supervisor and share study findings.

Maintain the lab's ethics and rules.

Requirements:
Students must meet the following major requirements in addition to the university's fundamental admission policies (https://cse.nsysu.edu.tw/?Lang=en):

Strong motivation on applied cryptology and cybersecurity.

Understanding of technological advancements.

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).

Method to join CANSEC:

Send recent CV to arijit.karati@mail.cse.nsysu.edu.tw

Two rounds of interview (optional based on CV)
Candidates must apply properly through the ONLINE portal after satisfying the prerequisites.

Closing date for applications:

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

The FIDO2 standard is widely-used class of challenge-response type protocols that allows to authenticate to an online service using a hardware token. Barbosa et al. (CRYPTO `21) provided the first formal security model and analysis for the FIDO2 standard. However, their model has two shortcomings: (1) it does not include privacy, one of the key features claimed by FIDO2 (2) their model and proofs apply only to tokens that store all secret keys locally.

In contrast, due to limited memory, most existing FIDO2 tokens use one of the following approaches to handle an unlimited number of keys. Key derivation derives a fresh per-server secret key from a common seed. Key wrapping stores an encryption of the key on the server and retrieves them for each authentication. These approaches substantially complicate the protocols and their security analysis. In particular, they bear additional risks for privacy and security of FIDO2 that are not captured in the model Barbosa et al. model.

In this paper, we revisit the security of the FIDO2 as implemented in practice. Our contributions are as follows. (1) We adapt the model of Barbosa et al. so as to capture authentication tokens using key derivation or key wrapping. (2) In our adapted model, we provide the first formal definition of privacy for FIDO2 and show that these common FIDO2 token implementations are secure in our model, if the underlying building blocks are chosen appropriately. (3) Finally, we address the unsolved problem of global key revocation in FIDO2. We first provide appropriate syntax of a revocation procedure and extend our model to support this feature. We then provide the first secure global key revocation protocol for FIDO2. Our solution is based on the popular BIP32 standard used in cryptocurrency wallets.

We introduce Zef, the first Byzantine-Fault Tolerant (BFT) protocol to support payments in anonymous digital coins at arbitrary scale. Zef follows the communication and security model of FastPay: both protocols are asynchronous, low-latency, linearly-scalable, and powered by partially-trusted sharded authorities. In contrast with FastPay, user accounts in Zef are uniquely-identified and safely removable. Zef coins are bound to an account by a digital certificate and otherwise stored off-chain by their owners. To create and redeem coins, users interact with the protocol via privacy-preserving operations: Zef uses randomized commitments and NIZK proofs to hide coin values; and, created coins are made unlinkable using the blind and randomizable threshold anonymous credentials of Coconut. Besides the detailed specifications and our analysis of the protocol, we are making available an open-source implementation of Zef in Rust. Our extensive benchmarks on AWS confirm textbook linear scalability and demonstrate a confirmation time under one second at nominal capacity. Compared to existing anonymous payment systems based on a blockchain, this represents a latency speedup of three orders of magnitude, with no theoretical limit on throughput.

Zero-Knowledge protocols have increasingly become both popular and practical in recent years due to their applicability in many areas such as blockchain systems. Unfortunately, public verifiability and small proof sizes of zero-knowledge protocols currently come at the price of strong assumptions, large prover time, or both, when considering statements with millions of gates. In this regime, the most prover-efficient protocols are in the designated verifier setting, where proofs are only valid to a single party that must keep a secret state.

In this work, we bridge this gap between designated-verifier proofs and public verifiability by {\em distributing the verifier}. Here, a set of verifiers can then verify a proof and, if a given threshold $t$ of the $n$ verifiers is honest and trusted, can act as guarantors for the validity of a statement. We achieve this while keeping the concrete efficiency of current designated-verifier proofs, and present constructions that have small concrete computation and communication cost. We present practical protocols in the setting of threshold verifiers with $t

We construct new private-information-retrieval protocols in the single-server setting. Our schemes allow a client to privately fetch a sequence of database records from a server, while the server answers each query in average time sublinear in the database size. Specifically, we introduce the first single-server private-information-retrieval schemes that have sublinear amortized server time, require sublinear additional storage, and allow the client to make her queries adaptively. Our protocols rely only on standard cryptographic assumptions (decision Diffie-Hellman, quadratic residuosity, learning with errors, etc.). They work by having the client first fetch a small "hint" about the database contents from the server. Generating this hint requires server time linear in the database size. Thereafter, the client can use the hint to make a bounded number of adaptive queries to the server, which the server answers in sub-linear time--yielding sublinear amortized cost. Finally, we give a lower bound proving that our most efficient scheme is optimal with respect to the trade-off it achieves between server online time and client storage.

We improve upon the security of (tweakable) correlation-robust hash functions, which are essential components of garbling schemes and oblivious-transfer extension schemes. We in particular focus on constructions from permutations, and improve upon the work by Guo et al. (IEEE S&P '20) in terms of security and efficiency.

We present a tweakable one-call construction which matches the security of the most secure two-call construction -- the resulting security bound takes form O((p+q)q/2^n), where q is the number of construction evaluations and p is the number of direct adversarial queries to the underlying n-bit permutation, which is modeled as random. Moreover, we present a new two-call construction with much better security degradation -- in particular, for applications of interest, where only a constant number of evaluations per tweak are made, the security degrades as O((sqrt(q)p+q^2)/2^n).

Our security proof relies on on the sum-capture theorems (Babai ’02; Steinberger ’12, Cogliati and Seurin ’18), as well as on new balls-into-bins combinatorial lemmas for limited independence ball-throws.

Of independent interest, we also provide a self-contained concrete security treatment of oblivious transfer extension.

Event date: 26 May 2022
Submission deadline: 27 January 2022
Notification: 27 February 2022

Event date: 7 September to 9 September 2022
Submission deadline: 23 May 2022
Notification: 11 July 2022

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

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

Event date: 29 August to 31 August 2022
Submission deadline: 25 March 2022
Notification: 25 May 2022

Event date: 7 November to 10 November 2022
Submission deadline: 24 May 2022
Notification: 28 August 2022