International Association
for Cryptologic Research

We consider that multiple noisy observations of a remote source are used by different nodes in the same network to compute a function of the noisy observations under joint secrecy, joint privacy, and individual storage constraints, as well as a distortion constraint on the function computed. Suppose that an eavesdropper has access to one of the noisy observations in addition to the public messages exchanged between legitimate nodes. This model extends previous models by 1) considering a remote source as the source of dependency between the correlated random variables observed at different nodes; 2) allowing the function computed to be a distorted version of the target function, which allows to reduce the storage rate as compared to a reliable function computation scenario in addition to reducing secrecy and privacy leakages; 3) introducing a privacy metric that measures the information leakage about the remote source to the fusion center in addition to the classic privacy metric that measures the leakage to an eavesdropper; 4) considering two transmitting nodes to compute a function rather than one node. Single-letter inner and outer bounds are provided for the considered lossy function computation problem, and exact lossy rate regions are characterized for two special cases in which either the computed function is partially invertible or the function is invertible and the measurement channel of the eavesdropper is physically degraded with respect to the measurement channel of the fusion center.

The problem of reliable function computation is extended by imposing privacy, secrecy, and storage constraints on a remote source whose noisy measurements are observed by multiple parties. The main additions to the classic function computation problem include 1) privacy leakage to an eavesdropper is measured with respect to the remote source rather than the transmitting terminals' observed sequences; 2) the information leakage to a fusion center with respect to the remote source is considered as another privacy leakage metric; 3) two transmitting node observations are used to compute a function. Inner and outer bounds on the rate regions are derived for lossless single-function computation with two transmitting nodes, which recover previous results in the literature, and for special cases that consider invertible functions exact rate regions are characterized.

Bitcoin is the most secure blockchain in the world, supported by the immense hash power of its Proof-of-Work miners, but consumes huge amount of energy. Proof-of-Stake chains are energy-efficient, have fast finality and accountability, but face several fundamental security issues: susceptibility to non-slashable long-range safety attacks, non-slashable transaction censorship and stalling attacks and difficulty to bootstrap new PoS chains from low token valuation. We propose Babylon, a blockchain platform which combines the best of both worlds by reusing the immense Bitcoin hash power to enhance the security of PoS chains. Babylon provides a data-available timestamping service, securing PoS chains by allowing them to timestamp data-available block checkpoints, fraud proofs and censored transactions on Babylon. Babylon miners merge mine with Bitcoin and thus the platform has zero additional energy cost. The security of a Babylon-enhanced PoS protocol is formalized by a cryptoeconomic security theorem which shows slashable safety and liveness guarantees.

The ever-increasing cohort of cryptocurrency users saw a sharp increase in different types of crypto-wallets in the past decade. However, different wallets are non-uniformly adopted in the population today; Specifically, emerging multi-device wallets, even with improved security and availability guarantees over their counterparts, are yet to receive proportionate attention and adoption. This work presents a data-driven investigation into the perceptions of cryptocurrency users towards multi-device wallets today, using a survey of255crypto-wallet users. Our results revealed two significant groups within our participants—Newbies and Non-newbies. These two groups statistically significantly differ in their usage of crypto-wallets. However, both of these groups were concerned with the possibility of their keys getting compromised and yet are unfamiliar with the guarantees offered by multi-device wallets. After educating the participants about the more secure multi-device wallets, around 70% of the participants preferred them; However, almost one-third of participants were still not comfortable using them. Our qualitative analysis revealed a gap between the actual security guarantees and mental models for these participants—they were afraid that using multi-device wallets will result in losing control over keys (and in effect funds) due to the distribution of key shares. We also investigated the preferred default settings for crypto-wallets across our participants, since multi-device wallets allow a wide range of key-share distribution settings. In the distributed server settings of the multi-device wallets, the participants preferred a smaller number of reputed servers (as opposed to a large non-reputed pool). Moreover, considerations about the threat model further affected their preferences, signifying a need for contextualizing default settings. We conclude the discussion by identifying concrete, actionable design avenues for future multi-device wallet developers to improve adoption.

The NTRU problem is a promising candidate to build efficient Fully Homomorphic Encryption (FHE). However, all the existing proposals (e.g. LTV, YASHE) need so-called `overstretched' parameters of NTRU to enable homomorphic operations. It was shown by Albrecht et al. (CRYPTO 2016) that these parameters are vulnerable against subfield lattice attacks.

Based on a recent, more detailed analysis of the overstretched NTRU assumption by Ducas and van Woerden (ASIACRYPT 2021), we construct two FHE schemes whose NTRU parameters lie outside the overstretched range. The first scheme is based solely on NTRU and demonstrates competitive performance against the state-of-the-art FHE schemes including TFHE. Our second scheme, which is based on both the NTRU and LWE assumptions, outperforms TFHE with a 28% faster bootstrapping and 45% smaller bootstrapping and key-switching keys.

A forward-secure public-key encryption (PKE) scheme prevents eavesdroppers from decrypting past ciphertexts in order to mitigate the damage caused by a potential secret key compromise. In prior works, forward security in a non-interactive setting, such as forward-secure PKE, is achieved by constantly updating (secret) keys. In this paper, we formalize the notion of blockchain-based forward-secure PKE and show the feasibility of constructing a forward-secure PKE scheme without key update (i.e. both the public key and the secret key are immutable), assuming the existence of a proof-of-stake blockchain with the distinguishable forking property introduced by Goyal, et al. (TCC 2017). Our construction uses the proof-of-stake blockchain as an immutable decryption log and witness encryption by Garg, et al. (STOC 2013) to ensure that the same ciphertext cannot be decrypted twice, thereby rendering a compromised secret key useless with respect to decryption of past ciphertext the legitimate user has already decrypted.

Public-key encryption with keyword search (PEKS) does not provide trapdoor privacy, i.e., keyword information is leaked through trapdoors. To prevent this information leakage, public key authenticated encryption with keyword search (PAEKS) has been proposed, where a sender's secret key is required for encryption, and a trapdoor is associated with not only a keyword but also the sender. Liu et al. (ASIACCS 2022) proposed a generic construction of PAEKS based on word-independent smooth projective hash functions (SPHFs) and PEKS. In this paper, we propose a new generic construction of PAEKS. The basic construction methodology is the same as that of the Liu et al. construction, where each keyword is converted into an extended keyword using SPHFs, and PEKS is used for extended keywords. Nevertheless, our construction is more efficient than Liu et al.'s in the sense that we only use one SPHF, but Liu et al. used two SPHFs. In addition, for consistency we considered a security model that is stronger than Liu et al.'s. Briefly, Liu et al. considered only keywords even though a trapdoor is associated with not only a keyword but also a sender. Thus, a trapdoor associated with a sender should not work against ciphertexts generated by the secret key of another sender, even if the same keyword is associated. Our consistency definition considers a multi-sender setting and captures this case. In addition, for indistinguishability against chosen keyword attack (IND-CKA) and indistinguishability against inside keyword guessing attack (IND-IKGA), we use a stronger security model defined by Qin et al. (ProvSec 2021), where an adversary is allowed to query challenge keywords to the encryption and trapdoor oracles. We also highlight several issues associated with the Liu et al. construction in terms of hash functions, e.g., their construction does not satisfy the consistency that they claimed to hold.

We build the first sub-linear (in fact, potentially constant-time) public-key searchable encryption system: − server can publish a public key $PK$. − anybody can build an encrypted index for document $D$ under $PK$. − client holding the index can obtain a token $z_w$ from the server to check if a keyword $w$ belongs to $D$. − search using $z_w$ is almost as fast (e.g., sub-linear) as the non-private search. − server granting the token does not learn anything about the document $D$, beyond the keyword $w$. − yet, the token $z_w$ is specific to the pair $(D, w)$: the client does not learn if other keywords $w'\neq w$ belong to $D$, or if w belongs to other, freshly indexed documents $D'$. − server cannot fool the client by giving a wrong token $z_w$. We call such a primitive Encapsulated Search Index (ESI). Our ESI scheme can be made $(t, n)$- distributed among $n$ servers in the best possible way: non-interactive, verifiable, and resilient to any coalition of up to $(t − 1)$ malicious servers. We also introduce the notion of delegatable ESI and show how to extend our construction to this setting. Our solution — including public indexing, sub-linear search, delegation, and distributed token generation — is deployed as a commercial application by Atakama.

The South African Reserve Bank Research Chair in the Faculty of Commerce at the University of Cape Town is inviting applications for PhD students and Postdoctoral Research Fellows. The overarching theme of the fellowships is “the future of finance” and students and recent graduates with a background in economics, computer science, mathematics, finance, and related disciplines are invited to apply. Any of the following research areas is of particular interest: Central bank digital currencies Financial interconnectedness Cybersecurity Successful applicants will work within a research group that strives for academic excellence and is interested in all aspects of central bank digital currencies (including financial stability, privacy, interoperability, and inclusivity), as well as all aspects of cybersecurity (in particular economic and network models of cybersecurity). Applications open now and are considered on a rolling basis until 30 April or until the positions are filled. Appointments are for as soon as is feasible. The tenure of the Postdoctoral fellowship is for up to three years, while the tenure for PhD positions is usually three years, but can be extended for up to five years. Due to the ongoing pandemic, successful applicants can choose to work remotely in 2022. Postdoctoral fellows receive a fellowship of R350,000 per annum and no benefits are included in the value of the fellowship. An additional travel allowance of R30,000 p.a. is available for successful applicants. The successful applicant will be required to comply with the University’s approved policies, procedures and practises for the postdoctoral sector. PhD students receive a fellowship of R210,000 p.a. and an additional travel allowance of R20,000 p.a. in addition to access to university-wide funding for conference travel. We typically arrange for PhD students to spend at least one semester at a leading international university and help organize an internship at a leading international policy institution. PhD students are expected to have extremely strong quantitative skills.

Closing date for applications:

Contact: anda.ngcaba@uct.ac.za

More information: https://www.finhub.org.za/vacancies#research_team

Leaders in Blockchain Security Quantstamp's mission is to secure the decentralized internet, and has protected over $100B in digital asset risk from hackers. More than 200 startups, foundations and enterprises work with Quantstamp to keep their innovative products safe. Auditing Engineer (Full-time/Part-time, Remote) - Background in Computer Science or any related field such as Mathematics & Physics. - Loves to find bugs in software systems and has a great eye for detail. - Fluent English communication, both written and spoken. Fluence in reading simple to medium complexity Solidity smart contracts. Understands the most common security pitfalls with Solidity smart contracts. Understands the basics of blockchain. Responsibilities Perform code reviews/audits of blockchain projects in small teams of engineers. Interact with other team members to discuss the likelihood and impact of findings. Write and review audit reports before they are shared with the customer. Optional opportunities Interact with customers to clarify technical requirements and to answer technical questions. Perform research on a new topic in the crypto space and provide internal “Lunch and Learn” (LnL) sessions. There is an option to also record and publish LnLs on YouTube or other social media platforms. Perks Competitive compensation package (commensurate to experience) + performance and referral bonuses. Free gym membership or any virtual alternative of your choice. Rent your own desk in a co-working space or work from anywhere at any time. 100% remote and flexible working hours. Learn about the hottest and newest products and trends in the crypto space before they appear on any news outlets. Generous paid time off, including maternity/paternity leave. Retirement/pension plan. Join quarterly all-expenses paid retreats in exotic/exclusive locations with the whole team.

Closing date for applications:

Contact: Peter Slankis - Head of Talent Acquisition

More information: https://quantstamp.com/

The Cybersecurity-Cryptography team at Telecom Paris invites applications for a full professor position in Cybersecurity. Application deadline: 18 April 2022. Link to the call: https://institutminestelecom.recruitee.com/l/en/o/professeur-en-cybersecurite-securite-des-donnees-et-des-communications-dans-les-infrastructures-numeriques-a-telecom-paris-fh-cdi

Closing date for applications:

Contact: Please feel free to reach out to Hieu Phan (hieu.phan@telecom-paris.fr) or any member of the Cybersecurity-Cryptography team (https://www.telecom-paris.fr/C2) for more information.

We present the first truly explicit constructions of non-malleable codes against tampering by bounded polynomial size circuits. These objects imply unproven circuit lower bounds and our construction is secure provided E requires exponential size nondeterministic circuits, an assumption from the derandomization literature. Prior works on NMC for polysize circuits, either required an untamperable CRS [Cheraghchi, Guruswami ITCS'14; Faust, Mukherjee, Venturi, Wichs EUROCRYPT'14] or very strong cryptographic assumptions [Ball, Dachman-Soled, Kulkarni, Lin, Malkin EUROCRYPT'18; Dachman-Soled, Komargodski, Pass CRYPTO'21]. Both of works in the latter category only achieve non-malleability with respect to efficient distinguishers and, more importantly, utilize cryptographic objects for which no provably secure instantiations are known outside the random oracle model. In this sense, none of the prior yields fully explicit codes from non-heuristic assumptions. Our assumption is not known to imply the existence of one-way functions, which suggests that cryptography is unnecessary for non-malleability against this class. Technically, security is shown by non-deterministically reducing polynomial size tampering to split-state tampering. The technique is general enough that it allows us to to construct the first seedless non-malleable extractors [Cheraghchi, Guruswami TCC'14] for sources sampled by polynomial size circuits [Trevisan, Vadhan FOCS'00] (resp. recognized by polynomial size circuits [Shaltiel CC'11]) and tampered by polynomial size circuits. Our construction is secure assuming E requires exponential size $\Sigma_4$-circuits (resp. $\Sigma_3$-circuits), this assumption is the state-of-the-art for extracting randomness from such sources (without non-malleability). We additionally observe that non-malleable codes and non-malleable secret sharing [Goyal, Kumar STOC'18] are essentially equivalent with respect to polynomial size tampering. In more detail, assuming E is hard for exponential size nondeterministic circuits, any efficient secret sharing scheme can be made non-malleable against polynomial size circuit tampering. Unfortunately, all of our constructions only achieve inverse polynomial (statistical) security. Extending a result from [Applebaum, Artemenko, Shaltiel, Yang CC'16] we show it is impossible to do better using black-box reductions. However, we extend the notion of relative error from [Applebaum, Artemenko, Shaltiel, Yang CC'16] to non-malleable extractors and show that they can be constructed from similar assumptions. We additionally observe that relative-error non-malleable extractors can be utilized to render a broad class of cryptographic primitives tamper and leakage resilient, while preserving negligible security guarantees.

One of the ultimate goals of symmetric-key cryptography is to find a rigorous theoretical framework for building block ciphers from small components, such as cryptographic $S$-boxes, and then argue why iterating such small components for sufficiently many rounds would yield a secure construction. Unfortunately, a fundamental obstacle towards reaching this goal comes from the fact that traditional security proofs cannot get security beyond $2^{-n}$, where $n$ is the size of the corresponding component.

As a result, prior provably secure approaches --- which we call "big-box cryptography" --- always made $n$ larger than the security parameter, which led to several problems: (a) the design was too coarse to really explain practical constructions, as (arguably) the most interesting design choices happening when instantiating such "big-boxes" were completely abstracted out; (b) the theoretically predicted number of rounds for the security of this approach was always dramatically smaller than in reality, where the "big-box" building block could not be made as ideal as required by the proof. For example, Even-Mansour (and, more generally, key-alternating) ciphers completely ignored the substitution-permutation network (SPN) paradigm which is at the heart of most real-world implementations of such ciphers.

In this work, we introduce a novel paradigm for justifying the security of existing block ciphers, which we call small-box cryptography. Unlike the "big-box" paradigm, it allows one to go much deeper inside the existing block cipher constructions, by only idealizing a small (and, hence, realistic!) building block of very small size $n$, such as an 8-to-32-bit $S$-box. It then introduces a clean and rigorous mixture of proofs and hardness conjectures which allow one to lift traditional, and seemingly meaningless, "at most $2^{-n}$ security proofs for reduced-round idealized variants of the existing block ciphers, into meaningful, full-round security justifications of the actual ciphers used in the real world.

We then apply our framework to the analysis of SPN ciphers (e.g, generalizations of AES), getting quite reasonable and plausible concrete hardness estimates for the resulting ciphers. We also apply our framework to the design of stream ciphers. Here, however, we focus on the simplicity of the resulting construction, for which we managed to find a direct "big-box"-style security justification, under a well studied and widely believed eXact Linear Parity with Noise (XLPN) assumption.

Overall, we hope that our work will initiate many follow-up results in the area of small-box cryptography.

Forward security (FS) ensures that corrupting the current secret key in the system preserves the privacy or integrity of the prior usages of the system. Achieving forward security is especially hard in the setting of public-key encryption (PKE), where time is divided into periods, and in each period the receiver derives the next-period secret key from their current secret key, while the public key stays constant. Indeed, all current constructions of FS-PKE are built from hierarchical identity-based encryption (HIBE) and are rather complicated. Motivated by applications to secure messaging, recent works of Jost et al. (Eurocrypt’19) and Alwen et al. (CRYPTO’20) consider a natural relaxation of FS-PKE, which they term updatable PKE (UPKE). In this setting, the transition to the next period can be initiated by any sender, who can compute a special update ciphertext. This ciphertext directly produces the next-period public key and can be processed by the receiver to compute the next-period secret key. If done honestly, future (regular) ciphertexts produced with the new public key can be decrypted with the new secret key, but past such ciphertexts cannot be decrypted with the new secret key. Moreover, this is true even if all other previous-period updates were initiated by untrusted senders. Both papers also constructed a very simple UPKE scheme based on the CDH assumption in the random oracle model. However, they left open the question of building such schemes in the standard model, or based on other (e.g., post-quantum) assumptions, without using the heavy HIBE techniques. In this work, we construct two efficient UPKE schemes in the standard model, based on the DDH and LWE assumptions, respectively. Somewhat interestingly, our constructions gain their efficiency (compared to prior FS-PKE schemes) by using tools from the area of circular-secure and leakage resilient public-key encryption schemes (rather than HIBE).

Recent advances in Fully Homomorphic Encryption (FHE) allow for a practical evaluation of non-trivial functions over encrypted data. In particular, novel approaches for combining ciphertexts broadened the scope of prospective applications. However, for arithmetic circuits, the overall complexity grows with the desired precision and there is only a limited space for parallelization.

In this paper, we put forward several methods for fully parallel addition of multi-digit integers encrypted with the TFHE scheme. Since these methods handle integers in a special representation, we also revisit the signum function, firstly addressed by Bourse et al., and we propose a method for the maximum of two numbers; both with particular respect to parallelization. On top of that, we outline an approach for multiplication by a known integer.

According to our experiments, the fastest approach for parallel addition of 31-bit encrypted integers in an idealized setting with 32 threads is estimated to be more than 6x faster than the fastest sequential approach. Finally, we demonstrate our algorithms on an evaluation of a practical neural network.

The study of randomness has always been a topic of significant relevance, and the importance of this topic in cryptography is undeniable. In this paper, we are going to provide a short introduction regarding pseudo-random number generators, their applications in cryptography and an analysis of the Discrete Fourier Transform statistical test. Our contribution is that of compiling the results of multiple runs on several popular pseudo-random number generators, and a Python implementation for computing the probability of a type II error. We intend to underline the weak points of the Discrete Fourier Transform test by showcasing results on large amounts of data, and showcase how testing bigger sequences of bits can help reduce the probability of type II errors.

The task of combining cryptographic keys, some of which may be maliciously formed, into one key, which is (pseudo)random is a central task in cryptographic systems. For example, it is a crucial component in the widely used TLS and Signal protocols. From an analytical standpoint, current security proofs model such key combiners as dual-PRFs -- a function which is a PRF when keyed by either of its two inputs -- guaranteeing pseudo-randomness if one of the keys is compromised or even maliciously chosen by an adversary.

However, in practice, implementations of key combiners significantly depart from the ``dual-PRF'' standard set by provable schemes. Specifically, existing implementations typically use heuristic approaches and rely on strong assumptions that are only known to be satisfied in ideal models (such as modelling underlying hash functions as random oracles), or which are not justified at all by known security results. We describe several cases of deployed protocols where this is the case, focussing on the use of HKDF as a dual-PRF. Unfortunately, such strong assumptions on cryptographic hash functions tend not to withstand the test of time, often leading to deployed systems that eventually become completely insecure; experience also shows that upgrading already-deployed cryptography from deprecated hash functions to newer ones is a slow process that can take many years. Finally, we consider it sub-optimal that the new hybrid key exchange protocols combining classical and post-quantum key exchanges and that are in the process of development risk more deeply embedding the improper use of key combiners.

In this work, we narrow the gap between theory and practice for key combiners. In particular, we give a construction of a dual-PRF that can be used as a drop-in replacement for current heuristic key combiners in a range of protocols. Our construction follows a theoretical construction by Bellare and Lysyanskaya, and is based on concrete hardness assumptions, phrased in the spirit of one-wayness. Therefore, our construction provides security unless extremely strong attacks against the underlying cryptographic hash function are discovered. Moreover, since these assumptions are considered post-quantum secure, our constructions can safely be used in new hybrid protocols. From a practical perspective, our dual-PRF construction is highly efficient, adding only a negligible overhead of a few microseconds compared to currently used (heuristic) approaches. We believe that our approach exemplifies a perfect middle-ground for practically efficient constructions that are supported by realistic hardness assumptions.

Proofs of Retrievability (PoR) protocols ensure that a client can fully retrieve a large outsourced file from an untrusted server. Good PoRs should have low communication complexity, small storage overhead and clear security guarantees with tight security bounds. The focus of this work is to design good PoR schemes with simple security proofs. To this end, we use the Constructive Cryptography (CC) setting by Maurer [13]. We propose a framework for the design of secure and efficient PoR schemes based on Locally Correctable Codes (LCC). We give a first instantiation of our framework using the high rate lifted codes introduced by Guo et al. [5]. This yields an infinite family of good PoRs. We assert their security by solving a finite geometry problem, giving an explicit formula for the probability of an adversary to fool the client. Using the local correctability properties of Tanner codes, we get another instantiation of our framework and derive an analogous formula for the success probability of the audit.

In this paper, we study zero-knowledge (ZK) proofs for circuit satisfiability that can prove to n verifiers at a time efficiently. The proofs are secure against the collusion of a prover and a subset of $t$ verifiers. We refer to such ZK proofs as multi-verifier zero-knowledge (MVZK) proofs, and focus on the case that a majority of verifiers are honest (i.e., $t < n/2$). We construct efficient MVZK protocols where the prover sends one message to each verifier, while the verifiers only exchange one round of messages (or, to achieve information-theoretic security, the number of rounds between verifiers is logarithmic to the circuit size).

In addition to the round complexity, our MVZK protocols in the computational setting achieve particularly high practicality. These protocols are streamable and only require a memory proportional to what is needed to evaluate the circuit in the clear. In terms of communication cost, when $t < n/2$, the prover sends $1/2 + o(1)$ field elements per multiplication gate to every verifier. When the threshold of corrupted verifiers $t < n(1/2 − \epsilon)$ for any $0 < \epsilon < 1/2$, we can further reduce the communication to $O(1/n)$ field elements per multiplication gate per verifier.

This text serves as a general guide to secure multiparty computation based on secret-sharing, focusing more on practical aspects of the techniques and constructions rather than their theoretical grounds. It is intended to serve as a

This work in progress currently includes an introduction to several core concepts in secure multiparty computation, an overview of simulation-based security, and detailed constructions for honest and two-thirds honest majority MPC, and also dishonest majority in the preprocessing model.