International Association
for Cryptologic Research

This paper introduces Brakedown, the first built system that provides linear-time SNARKs for NP, meaning the prover incurs $O(N)$ finite field operations to prove the satisfiability of an $N$-sized R1CS instance. Brakedown’s prover is faster, both concretely and asymptotically, than prior SNARK implementations. Brakedown does not require a trusted setup and is plausibly post-quantum secure. Furthermore, it is compatible with arbitrary finite fields of sufficient size; this property is new amongst implemented arguments with sublinear proof sizes.

To design Brakedown, we observe that recent work of Bootle, Chiesa, and Groth (BCG, TCC 2020) provides a polynomial commitment scheme that, when combined with the linear-time interactive proof system of Spartan (CRYPTO 2020), yields linear-time IOPs and SNARKs for R1CS (a similar theoretical result was previously established by BCG, but our approach is conceptually simpler, and crucial for achieving high-speed SNARKs). A core ingredient in the polynomial commitment scheme that we distill from BCG is a linear-time encodable code. Existing constructions of such codes are believed to be impractical. Nonetheless, we design and engineer a new one that is practical in our context.

We also implement a variant of Brakedown that uses Reed-Solomon codes instead of our linear-time encodable codes; we refer to this variant as Shockwave. Shockwave is not a linear-time SNARK, but it provides shorter proofs and lower verification times than Brakedown (it also provides a faster prover than prior plausibly post-quantum SNARKs).

As a modest additional contribution, we observe that one can render the aforementioned SNARK zero knowledge and reduce the proof size and verifier time from $O(\sqrt{N})$ to $polylog(N)$---while maintaining a linear-time prover---by outsourcing the verifier’s work via one layer of proof composition with an existing zkSNARK as the "outer" proof system.

At ITCS 2010, Dziembowski, Pietrzak and Wichs introduced Non-malleable Codes (NMCs). Non-malleability is one of the strongest and most challenging notions of security considered in cryptography and protects against tampering attacks. In the context of coding schemes, non-malleability requires that it be infeasible to tamper the codeword of a message into the codeword of a related message. A natural and well-studied model of tampering is the 2-split-state model where the codeword consists of two independently tamperable states. As with standard error-correcting codes, it is of great importance to build codes with high rates. Cheraghchi and Guruswami (ITCS 2014) showed that one cannot obtain NMCs in the 2-split state model with rate better than 1/2. Since its inception, this area has witnessed huge strides leading to the construction of a constant-rate NMC in the 2-split state model due to Aggarwal and Obremski (FOCS 2020). However, the rate of this construction -- roughly 1/1,500,000 -- is nowhere close to the best achievable rate of 1/2! In this work, we dramatically improve this status quo by building a rate booster that converts any augmented non-malleable code into an augmented non-malleable code with a rate of 1/3. Using similar, but simpler techniques we also obtain rate boosters that convert any unbalanced (with sources of unequal length) non-malleable 2-source extractor into an unbalanced non-malleable 2-source extractor with rate 1/2. The beauty of our construction lies in its simplicity. In particular, if we apply our rate booster to the non-malleable code construction by Aggarwal, Dodis and Lovett (STOC 2014), then all we need is one instance of the inner-product extractor, one instance of a seeded extractor, and an affine-evasive function for the construction to work.

Multiplicative complexity is a relevant complexity measure for many advanced cryptographic protocols such as multi-party computation, fully homomorphic encryption, and zero-knowledge proofs, where processing AND gates is more expensive than processing XOR gates. For Boolean functions, multiplicative complexity is defined as the minimum number of AND gates that are sufficient to implement a function with a circuit over the basis (AND, XOR, NOT). In this paper, we study the multiplicative complexity of cubic Boolean functions. We propose a method to implement a cubic Boolean function with a small number of AND gates and provide upper bounds on the multiplicative complexity that are better than the known generic bounds.

The increasing adoption of machine learning inference in applications has led to a corresponding increase in concerns surrounding the privacy guarantees offered by existing mechanisms for inference. Such concerns have motivated the construction of efficient secure inference protocols that allow parties to perform inference without revealing their sensitive information. Recently, there has been a proliferation of such proposals, rapidly improving efficiency. However, most of these protocols assume that the client is semi-honest, that is, the client does not deviate from the protocol; yet in practice, clients are many, have varying incentives, and can behave arbitrarily. To demonstrate that a malicious client can completely break the security of semi-honest protocols, we first develop a new model-extraction attack against many state-of-the-art secure inference protocols. Our attack enables a malicious client to learn model weights with 22x-312x fewer queries than the best black-box model-extraction attack and scales to much deeper networks.

Motivated by the severity of our attack, we design and implement MUSE, an efficient two-party secure inference protocol resilient to malicious clients. MUSE introduces a novel cryptographic protocol for conditional disclosure of secrets to switch between authenticated additive secret shares and garbled circuit labels, and an improved Beaver's triple generation procedure which is 8x-12.5x faster than existing techniques.

These protocols allow MUSE to push a majority of its cryptographic overhead into a preprocessing phase: compared to the equivalent semi-honest protocol (which is close to state-of-the-art), MUSE's online phase is only 1.7x-2.2x slower and uses 1.4x more communication. Overall, MUSE is 13.4x-21x faster and uses 2x-3.6x less communication than existing secure inference protocols which defend against malicious clients.

Leakage detection tests have become an indispensable tool for testing implementations featuring side channel countermeasures such as masking. Whilst moment-based techniques such as the Welch’s t-test are universally powerful if there is leakage in a central moment, they naturally fail if this is not the case. Distribution-based techniques such as the χ2-test then come to the rescue, but they have shown not to be robust with regards to noise. In this paper, we propose a novel leakage detection technique based on Neyman’s smoothness test. We find that our new test is robust with respect to noise (similar to the merit of Welch’s t-test), and can pick up on leakage that is not located in central moments (similar to the merit of the χ2-test). We also find that there is a sweet-spot where Neyman’s test outperforms both the t-test and the χ2-test. Realistic measurements confirm that such a sweet-spot is relevant in practice for detecting implementation flaws.

We propose a new hash function Reinforced Concrete for the proof systems that support lookup tables, concretely Plookup based on KZG commitments or FRI. It has two solid advantages over predecessors: (a) Table lookups instead of (big) modular reductions are much faster both in ZK and plain computations thus making verifiable computation protocols based on recursive proofs (current trend) much more efficient; (b) the security is no longer solely based on (high) algebraic degree but rather on more traditional AES-like components inheriting decades of public scrutiny. Our design also employs a novel and fast field-to-tables conversion, which is of independent interest and can be used in other Plookup-friendly constructions. The new hash function is suitable for a wide range of applications like privacy-preserving cryptocurrencies, verifiable encryption, protocols with state membership proofs, or verifiable computation. It may serve as a drop-in replacement for various prime-field hashes such as variants of MiMC, Poseidon, Pedersen hash, and others.

In cryptography, the private simultaneous messages (PSM) and conditional disclosure of secrets (CDS) are closely related fundamental primitives. We consider $k$-party PSM and CDS protocols for a function $f$ with a $\rho$-bit common random string, where each party $P_i$ generates an $\lambda_i$-bit message ($i\in[k]$), and sends it to a referee $P_0$.

We consider bounds for the optimal length $\rho$ of the common random string among $k$ parties (or, {\it randomness complexity}) in PSM and CDS protocols with perfect and statistical privacy through combinatorial and entropic arguments. ($i$) We provide general connections from the optimal total length $\lambda = \sum_{i\in[k]}\lambda_i$ of the messages (or, {\it communication complexity}) to the randomness complexity $\rho$. ($ii$) We also prove randomness lower bounds in PSM and CDS protocols for general functions. ($iii$) We further prove randomness lower bounds for several important explicit functions. They contain the following results: For PSM protocols with perfect privacy, we prove $\rho\ge \lambda-1$ and $\rho\le \lambda$ as the general connection. To prove the upper bound, we provide a new technique for randomness sparsification for {\it perfect}\/ privacy, which would be of independent interest. From the general connection, we prove $\rho\ge 2^{(k-1)n}-1$ for a general function $f:(\{0,1\}^n)^k\rightarrow\{0,1\}$ under universal reconstruction, in which $P_0$ is independent of $f$. This implies that the Feige-Killian-Naor protocol for a general function [Proc.~STOC '94, pp.554--563]\ is optimal with respect to randomness complexity. We also provide a randomness lower bound $\rho> kn-2$ for a generalized inner product function. This implies the optimality of the $2$-party PSM protocol for the inner-product function of Liu, Vaikuntanathan, and Wee [Proc.~CRYPTO 2017, pp.758--790]. For CDS protocols with perfect privacy, we show $\rho\ge\lambda-\sigma$ and $\rho\le\lambda$ as the general connection by similar arguments to those for PSM protocols, where $\sigma$ is the length of secrets. We also obtain randomness lower bounds $\rho\ge (k-1)\sigma$ for XOR, AND, and generalized inner product functions. These imply the optimality of Applebaum and Arkis's $k$-party CDS protocol for a general function [Proc. TCC 2018, pp.317--344]\ up to a constant factor in a large $k$.

This article presents Lelantus-CLA, an adaptation of Lelantus for use with the Mimblewimble protocol and confidential assets. Whereas Mimblewimble achieves a limited amount of privacy by merging transactions that occur in the same block, Lelantus uses a logarithmic-size proof of membership to effectively enable merging across different blocks. At a high level, this allows value to be added to a common pool and then spent privately, but only once. We explain how to adapt this construction to Mimblewimble, while at the same time simplifying the protocol where possible.

Confidential assets is a mechanism that allows multiple currencies to co-exist in the same ledger and (optionally) enables transactions to be conducted without disclosing the currency.

Finally, we also describe how we can use Bulletproof “coloring” to enable offline payments, thus addressing one of the original shortcomings of Mimblewimble.

An encrypted search algorithm (ESA) allows a user to encrypt its data while preserving the ability to search over it. As all practical solutions leak some information, cryptanalysis plays an important role in the area of encrypted search. Starting with the work by Islam et al. (NDSS'12), many attacks have been proposed that exploit different leakage profiles under various assumptions. While they aim to improve our common understanding of leakage, it is difficult to draw definite conclusions about their practical risk. This uncertainty stems from many limitations including a lack of reproducibility due to closed-source implementations, empirical evaluations conducted on small and/or unrealistic data, and reliance on very strong assumptions that can significantly affect accuracy. Particularly, assumptions made about the query distribution do not have any empirical basis because datasets containing users' queries are hard to find.

In this work, we address the main limitations of leakage cryptanalysis. First, we design and implement an open-source framework called LEAKER that can evaluate the major leakage attacks against a given dataset and can serve as a common leakage analysis reference for the community. We identify new real-world datasets that capture different use cases for ESAs and, for the first time, include real-world user queries. Finally, we use LEAKER to evaluate known attacks on our datasets to assess their practical risks and gain insights about the properties that increase or diminish their accuracy.

This article provides new constant-time encodings $\mathbb{F}_{\!q}^* \to E(\mathbb{F}_{\!q})$ to ordinary elliptic $\mathbb{F}_{\!q}$-curves $E$ of $j$-invariants $0$, $1728$ having a small prime divisor of the Frobenius trace. Therefore all curves of $j = 1728$ are covered. This is also true for the Barreto--Naehrig curves BN512, BN638 from the international cryptographic standards ISO/IEC 15946-5, TCG Algorithm Registry, and FIDO ECDAA Algorithm. Many $j = 1728$ curves as well as BN512, BN638 do not have $\mathbb{F}_{\!q}$-isogenies of small degree from other elliptic curves. So, in fact, only universal SW (Shallue--van de Woestijne) encoding was previously applicable to them. However this encoding (in contrast to ours) can not be computed at the cost of one exponentiation in the field $\mathbb{F}_{\!q}$.

We formally define polynomial packing methods and initiate a unified study of related concepts in various contexts of cryptography. This includes homomorphic encryption (HE) packing and reverse multiplication-friendly embedding (RMFE) in information-theoretically secure multi-party computation (MPC). We prove several upper bounds or impossibility results on packing methods for $\mathbb{Z}_{p^k}$ or $\mathbb{F}_{p^k}$-messages into $\mathbb{Z}_{p^t}[x]/f(x)$ regarding (i) packing density, (ii) level-consistency, and (iii) surjectivity. These results have implications on recent development of HE-based MPC over $\mathbb{Z}_{2^k}$ secure against actively corrupted majority and provide new proofs for upper bounds on RMFE.

This paper presents AdVeil, a privacy-preserving advertising ecosystem with formal guarantees for end users. AdVeil is built around an untrusted advertising network which is responsible for brokering the display of advertisement to users. This ad network targets relevant ads to users without learning any of the users' personal information in the process. Our targeting protocol combines private information retrieval with standard, locality-sensitive hashing based techniques for nearest neighbor search. By running ad targeting in this way, users of AdVeil have full control over and transparency into the contents of their targeting profile.

AdVeil additionally supports private metrics for ad interactions, allowing the ad network to correctly charge advertisers and pay websites for publishing ads. This is done without the ad network learning which user interacted with an ad, only that some honest user did. AdVeil achieves this using an anonymizing proxy (e.g., Tor) to transit batched user reports along with unlinkable anonymous tokens with metadata to certify the authenticity of each report.

We build a prototype implementation of AdVeil which we evaluate on a range of parameters to demonstrate the applicability of AdVeil to a real-world deployment. Our evaluation shows that AdVeil scales to ad networks with millions of ads, using state-of-the-art single-server private information retrieval. A selection of ads from a database of 1 million ads can be targeted to a user in approximately 10 seconds with a single 32-core server, and can be parallelized further with more servers. Targeting is performed out-of-band (e.g., on a weekly basis) while ad delivery happens in real time as users browse the web. Verifying report validity (for fraud prevention) requires less than 300 microseconds of server computation per report.

In this work we present two commitment schemes based on hardness assumptions arising from supersingular elliptic curve isogeny graphs, which possess strong security properties. The first is based on the CGL hash function while the second is based on the SIDH framework, both of which require a trusted third party for the setup phrase. The proofs of security of these protocols depend on properties of non-backtracking random walks on regular graphs. The optimal efficiency of these protocols depends on the size of a certain constant, defined in the paper, related to relevant isogeny graphs, which we give conjectural upper bounds for.

ChaCha is a high-throughput stream cipher designed with the aim of ensuring high-security margins while achieving high performance on software platforms. RISC-V, an emerging, free, and open Instruction Set Architecture (ISA) is being developed with many instruction set extensions (ISE). ISEs are a native concept in RISC-V to support a relatively small RISC-V ISA to suit different use-cases including cryptographic acceleration via either standard or custom ISEs. This paper proposes a lightweight ISE to support ChaCha on RISC-V architectures. This approach targets embedded computing systems such as IoT edge devices that don't support a vector engine. The proposed ISE is designed to accelerate the computation of the ChaCha block function and align with the RISC-V design principles. We show that our proposed ISEs help to improve the efficiency of the ChaCha block function. The ISE-assisted implementation of ChaCha encryption speeds up at least $5.4\times$ and $3.4\times$ compared to the OpenSSL baseline and ISA-based optimised implementation, respectively. For encrypting short messages, the ISE-assisted implementation gains a comparative performance compared to the implementations using very high area overhead vector extensions.

A post-doctoral position in the area of information-theoretic security and cryptography is available at the Information Theory Section of Simula UiB, Bergen, Norway. The position is two years, with the possibility of extension.

Simula UiB is a research center owned by Simula Research Laboratory and the University of Bergen. The goal of Simula UiB is to increase the security expertise in Norway through research and education. For further details, see our webpage http://simula-uib.com.

We have a solid background in coding, information theory, communication theory, and many related areas. Currently, our research focus includes various topics in private information retrieval (PIR), private computation (PC), coding for property testing, coding for zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs), and privacy-preserving technologies in general. We are looking for a candidate with a solid background within one/several of these research areas and algebraic coding theory.

We are also looking for interested candidates who:

have completed, or are about to complete, a PhD degree in information theory or a suitably related relevant field

have an excellent academic track record and will be looking for publications in relevant venues

have an excellent level of spoken and written English possesses good interpersonal and communication skills

are willing to work as part of an international team

Simula UiB Offers:

Excellent opportunities for performing high-quality research, as part of a highly competent and motivated team of international researchers and engineers;

An informal and inclusive international working environment

Generous support for travel and opportunities to build international networks,

Modern office facilities located at Marineholmen in the city center of Bergen

A competitive salary. Starting salary from NOK 543 500

There are numerous benefits: company cabin, BabyBonus arrangements, sponsored social events, generous equipment budgets, comprehensive travel/health insurance policy, Relocation assistance, etc.

Closing date for applications:

Contact:

Chief Research Scientist Eirik Rosnes, eirikrosnes@simula.no,

Research Scientist Hsuan-Yin Lin, lin@simula.no,

Administrative questions: bergen@simula.no

More information: https://www.simula.no/about/job/post-doctoral-position-coding-and-information-theory

We are looking for talented and motivated Post-docs to work on the ERC AdG project PROCONTRA: Smart-Contract Protocols: Theory for Applications. The project is about theoretical and applied aspects of blockchain and smart contracts. The ideal candidates should have a Ph.D. degree in cryptography (or related field) from a leading university, and a proven record of publications in top cryptography/security/TCS venues. We offer a competitive salary, a budget for conference travel and research visit, and membership in a young and vibrant team with several international contacts (for more see: www.crypto.edu.pl). A successful candidate will be given substantial academic freedom and can work on a variety of research problems related to the main theme of the project.

Closing date for applications:

Contact: Stefan Dziembowski

More information: https://www.crypto.edu.pl/post-doc

The NIST Multi-Party Threshold Cryptography project has an open call (2021a), till September 13, 2021, for feedback on selected topics of criteria for multi-party threshold schemes.

Details here: https://csrc.nist.gov/projects/threshold-cryptography

Consider also joining the TC forum: https://csrc.nist.gov/projects/threshold-cryptography/email-list

The Security and Cryptography Lab of EPFL has postdoc positions to fill. We welcome the application of researchers with a recent PhD. The position is for one year, renewable.

Postdocs run their own research and are expected to interact with PhD students and to contribute to the lab projects. Our lab is active in cryptographic designs and analysis. fundamental and applied cryptography, security and privacy, and biometric systems.

EPFL is a top-ranked academic institute. It is located in beautiful Switzerland. We offer good environment and conditions.

Closing date for applications:

Contact: Serge Vaudenay <job_lasec@epfl.ch>

Please submit your detailed cv, list of publications, motivation, references, and availability.

More information: https://lasec.epfl.ch

Fujitsu is hiring research engineers for our research lab based out of Sunnyvale, CA. We are looking for skilled developers with a research background who enjoy building systems and helping to write academic papers about them. This job will have a large open-source component, so someone who is comfortable working in the open-source space would be an ideal candidate. The role offers flexible office time with the potential to work from home for a large fraction of your time.

Job Responsibilities:

• Design and develop secure blockchain and blockchain-based systems, and write academic papers about them when possible.
• Assist in the creation and maintenance of blockchain open-source projects, and help with research projects based on them. Engage and participate in the open-source blockchain community.
• Help developers build your research systems into production-ready systems.
• Collaborate with researchers both within and outside of Fujitsu to work towards building cutting-edge systems.

Requirements:

• A master’s degree in computer science or a related field, or relevant experience in research and development
• Some track record of research publications. We don’t expect you to publish every year in top venues, but we do want evidence of familiarity with research.
• Experience in open-source development, or a willingness to learn.

Closing date for applications:

Contact: Hart Montgomery (hmontgomery@fujitsu.com)

Fujitsu is hiring strong cryptographic researchers for our research lab based out of Sunnyvale, CA. We are looking for researchers who can successfully publish in top venues, collaborate with others in industry and academia, and evangelize cryptography and security within Fujitsu. The role offers flexible office time (including the potential to mostly work from home) and could be fully remote for exceptionally strong candidates.

Job Responsibilities:

• Conduct research in cryptography and related fields (i.e. distributed systems, security, and general theory) and publish it in top conferences. While researchers have wide latitude to work on whatever problems they deem interesting in the field, we do expect that at least some portion of research time will be spent on problems that are more relevant to Fujitsu’s business.
• Collaborate with others in both academia and industry on exciting research problems. Promote Fujitsu as a leader in the field of cryptography and computer security.
• Contribute to new Fujitsu technologies and IP, and help research engineers and developers shepherd the “practical” portion of your research into new business offerings.

Requirements:

• Ph.D. in computer science or a related field.
• A strong track record of publishing in top conferences in cryptography and related fields.
• A vision for the future direction of your research and ideas for how it can be impactful both academically and on Fujitsu’s business.

Closing date for applications:

Contact: Hart Montgomery (hmontgomery@fujitsu.com)