International Association
for Cryptologic Research

The shuffle model has been extensively investigated in the distributed differential privacy (DP) literature. For a class of useful computational tasks, the shuffle model allows us to achieve privacy-utility tradeoff similar to those in the central model, while shifting the trust from a central data curator to a ``trusted shuffle'' which can be implemented through either trusted hardware or cryptography. Very recently, several works explored cryptographic instantiations of a new type of shuffle with relaxed security, called {\it differentially oblivious (DO) shuffles}. These works demonstrate that by relaxing the shuffler's security from simulation-style secrecy to differential privacy, we can achieve asymptotical efficiency improvements. A natural question arises, can we replace the shuffler in distributed DP mechanisms with a DO-shuffle while retaining a similar privacy-utility tradeoff?

In this paper, we prove an optimal privacy amplification theorem by composing any locally differentially private (LDP) mechanism with a DO-shuffler, achieving parameters that tightly match the shuffle model. Moreover, we explore multi-message protocols in the DO-shuffle model, and construct mechanisms for the real summation and histograph problems. Our error bounds approximate the best known results in the multi-message shuffle-model up to sub-logarithmic factors. Our results also suggest that just like in the shuffle model, allowing each client to send multiple messages is fundamentally more powerful than restricting to a single message.

Fairness is one of the fundamental properties for multiparty computation (MPC) protocols. Although fair MPC protocols for general functions is shown to be impossible with a dishonest majority, a variant of fairness called ``fairness with penalty'' has been explored recently. A MPC protocol provides fairness with penalty if either all participants can get the output, or the dishonest parties who break the protocol after getting the output will be financially penalized. Fairness with penalty is enabled by previous works leveraging the emerging distributed ledger systems (DLS), e.g. Bitcoin and Ethereum. They utilize the scripting functionality provided by the DLSs to make automatic penalty practical without relying on any trusted third party. However, there is also a significant number of DLSs that do not provide the scripting functionality. In this paper, we propose the ROSE protocol which enables fairness with penalty while only requiring the underlying DLS can verify and broadcast digital signatures on transactions. This requirement can be fulfilled by almost all DLSs, including the scriptless DLSs. To the best of our knowledge, it is still unknown how to realize fairness with penalty on scriptless DLSs before our work. We also provide a implementation of ROSE. The experimental results show that applying ROSE only brings little computation and communication overhead.

The security of proof-of-work blockchain protocols critically relies on incentives. Their operators, called miners, receive rewards for creating blocks containing user-generated transactions. Each block rewards its creator with newly minted tokens and with transaction fees paid by the users. The protocol stability is violated if any of the miners surpasses a threshold ratio of the computational power; she is then motivated to deviate with selfish mining and increase her rewards.

Previous analyses of selfish mining strategies assumed constant rewards. But with statistics from operational systems, we show that there are occasional whales~-- blocks with exceptional rewards. Modeling this behavior implies a state-space that grows exponentially with the parameters, becoming prohibitively large for existing analysis tools.

We present the WeRLman framework to analyze such models. WeRLman uses deep Reinforcement Learning (RL), inspired by the state-of-the-art AlphaGo Zero algorithm. Directly extending AlphaGo Zero to a stochastic model leads to high sampling noise, which is detrimental to the learning process. Therefore, WeRLman employs novel variance reduction techniques by exploiting the recurrent nature of the system and prior knowledge of transition probabilities. Evaluating WeRLman against models we can accurately solve demonstrates it achieves unprecedented accuracy in deep RL for blockchain.

We use WeRLman to analyze the incentives of a rational miner in various settings and upper-bound the security threshold of Bitcoin-like blockchains. The previously known bound, with constant rewards, stands at~0.25. We show that considering whale transactions reduces this threshold considerably. In particular, with Bitcoin historical fees and its future minting policy, its threshold for deviation will drop to~0.2 in 10 years,~0.17 in 20 years, and to~0.12 in 30 years. With recent fees from the Ethereum smart-contract platform, the threshold drops to~0.17. These are below the common sizes of large miners.

Benefiting from its independence of leakage model, side-channel collision attack is one of the most common distinguishers and attracts wide attention. Although several improvements have been given, its performance on attacking a single collision value has not been significantly improved. Its optimization and efficiency is still an open problem. To solve this, we theoretically analyze the quantitative relationship between encryptions and collisions in this paper, and propose an efficient side-channel attack named Collision-Paired Correlation Attack (CPCA) for low noise scenarios to guarantee that the side with fewer samples in a collision to be detected is completely paired. This optimizes the inefficient utilization of collision information in the existing collision attacks. Moreover, to further exploit the collision information, we maximize the collision pairing, and this optimization significantly improves CPCA and extends our CPCA to large noise scenarios. Finally, to reduce computation complexity, we further optimize our CPCA to a CPA-like distinguisher. Our further theoretical study fully illustrates that our CPCA provides the upper security bound of CECA, and experimental results fully show its superiority.

Collision-resistant hash functions (CRH) are a fundamental and ubiquitous cryptographic primitive. Several recent works have studied a relaxation of CRH called t-way multi-collision-resistant hash functions (t-MCRH). These are families of functions for which it is computationally hard to find a t-way collision, even though such collisions are abundant (and even (t-1)-way collisions may be easy to find). The case of t=2 corresponds to standard CRH, but it is natural to study t-MCRH for larger values of t.

Multi-collision-resistance seems to be a qualitatively weaker property than standard collision-resistance. In particular, Komargodski et al. (Eurocrypt, 2018) showed that there does not exist a blackbox transformation of MCRH into CRH. Nevertheless, in this work we show a non-blackbox transformation of any moderately shrinking t-MCRH, for t in {3,4}, into an (infinitely often secure) CRH. This transformation is non-constructive - we can prove the existence of a CRH but cannot explicitly point out a construction.

Our result partially extends to larger values of t. In particular, we show that for suitable values of t>t', we can transform a t-MCRH into a t'-MCRH, at the cost of reducing the shrinkage of the resulting hash function family and settling for infinitely often security. This result utilizes the list-decodability properties of Reed-Solomon codes.

This paper represents a cumulative review of the serial statistical test over the canonical values used in testing and freely generated values. Also in this paper, we study by simulation, the variation of second type error, depending on certain factors: the range of p1,the length of the bit string represented by n and the value of m-bit pattern.

This paper improves upon two fundamental and closely related primitives in fault-tolerant distributed computing---Byzantine reliable broadcast (BRB) and asynchronous verifiable information dispersal (AVID). We make improvements asymptotically (for our AVID construction), concretely (much lower hidden constants), and practically (having 3 steps, using hash functions only, and avoiding using online error correction on the bulk data).

The state of the art BRB protocol of Das, Xiang, and Ren (DXR BRB, CCS 2021) uses hash functions only and achieves a communication overhead of $O(nL + kn^2)$, where $n$, $L$, and $k$ are the number of replicas, the message length, and the security parameter, respectively. More precisely, DXR BRB incurs a concrete communication of $7nL + 2kn^2$, with a large constant 7 for the bulk data term (i.e., the $nL$ term). Das, Xiang, and Ren asked an open question if it is possible "from a practical point of view to make the hidden constants small." Two other limitations of DXR BRB that authors emphasized are that "higher computation costs due to encoding and decoding of the message" due to applying error correcting codes on bulk data and the fact that "in the presence of malicious nodes, each honest node may have to try decoding $f$ times" due to the use of an online error correcting algorithm. Meanwhile, the state of the art AVID protocols achieve $O(L+kn^2)$ communication assuming trusted setup. Apparently, there is a mismatch between BRB and AVID protocols: another natural open problem is whether it is possible to build a setup-free AVID protocol with $O(L+kn^2)$ communication.

In this work, we answer all these open questions in the affirmative. We first provide a hash-based BRB protocol that improves concretely on DXR BRB, having low constants and avoiding using online error correction on bulk data. Our key insight is to encode the consistency proof, not just the message. Our technique allows disseminating the message and proof together. Then we provide the first setup-free AVID protocol achieving $O(L+kn^2)$ communication. Both our BRB and AVID protocols are practical because they have 3 steps, a multiplicative factor of 3 for the bulk data term, use hash functions only, and they avoid applying online error correction on bulk data.

We present gOTzilla, a protocol for interactive zero-knowledge proofs for large disjunctive statements of the following format: given publicly known circuit $C$, and set of values $Y = \{y_1, \ldots, y_n\}$, prove knowledge of a witness $x$ such that $C(x) = y_1 \lor C(x) = y_2 \lor \cdots \lor C(x) = y_n$. These type of statements are extremely important for the proof of assets (PoA) problem in cryptocurrencies where a prover wants to prove the knowledge of a secret key $sk$ that associates with the hash of a public key $H(pk)$ posted on the ledger.

gOTzilla is based on the MPC in the head (MPCitH) paradigm and is based on the observation that if we restructure the proof statement to an equivalent of proving knowledge of $(x,y)$ such that $(C(x) = y) \land (y = y_1 \lor \cdots \lor y = y_n))$, then we can reduce the disjunction of equalities to 1-out-of-N oblivious transfer (OT). We additionally provide a concrete, efficient extension of our protocol for the case where $C$ combines algebraic and non-algebraic statements (which is the case in the PoA application). We achieve an asymptotic communication cost of $O(\log n)$ plus the proof size of the underlying MPCitH protocol. While related work has similar asymptotic complexity, our approach results in concrete performance improvements. We implement our protocol and provide benchmarks. Concretely, for a set of size 1 million entries, the total run-time of our protocol is 14.89 seconds using 48 threads, with 6.18 MB total communication, which is about 4x faster compared to the state of the art when considering a disjunctive statement with algebraic and non-algebraic elements.

NIST SP 800-22 describes 15 statistical tests and suggests that they can be used for the evaluation of random and pseudorandom number generators in cryptographic applications. The Chinese standard GM/T 0005-2012 describes similar tests. The weakest of pseudorandom number generators will easily pass these tests, which promotes false confidence in insecure systems. Evaluation of pseudorandom generators and sequences should be based on cryptanalytic principles. Implementation validation should be focused on algorithmic correctness, not the randomness of output. For true random (entropy sources), the focus should be on the true entropy content and reliability of the construction and health tests. If the SP 800-22 is to be revised, we suggest the new SP focuses on evaluating stochastic models for entropy sources as the SP 800-90 series currently does not address this issue in depth. We further suggest that pseudorandom generators are analyzed for their suitability for post-quantum cryptography and lack of (asymmetric) backdoors or covert channels. We illustrate this by discussing the ``reference generators'' in SP 800-22 Appendix D, none of which are suitable for use in modern cryptography.

Hardness of approximation aims to establish lower bounds on the approximability of optimization problems in NP and beyond. We continue the study of hardness of approximation for problems beyond NP, specifically for \emph{stochastic} constraint satisfaction problems (SCSPs). An SCSP with $k$ alternations is a list of constraints over variables grouped into $2k$ blocks, where each constraint has constant arity. An assignment to the SCSP is defined by two players who alternate in setting values to a designated block of variables, with one player choosing their assignments uniformly at random and the other player trying to maximize the number of satisfied constraints.

In this paper, we establish hardness of approximation for SCSPs based on interactive proofs. For $k \leq O(\log n)$, we prove that it is $AM[k]$-hard to approximate, to within a constant, the value of SCSPs with $k$ alternations and constant arity. Before, this was known only for $k = O(1)$.

Furthermore, we introduce a natural class of $k$-round interactive proofs, denoted $IR[k]$ (for \emph{interactive reducibility}), and show that several protocols (e.g., the sumcheck protocol) are in $IR[k]$. Using this notion, we extend our inapproximability to all values of $k$: we show that for every $k$, approximating an SCSP instance with $O(k)$ alternations and constant arity is $IR[k]$-hard.

While hardness of approximation for CSPs is achieved by constructing suitable PCPs, our results for SCSPs are achieved by constructing suitable IOPs (interactive oracle proofs). We show that every language in $AM[k \leq O(\log n)]$ or in $IR[k]$ has an $O(k)$-round IOP whose verifier has \emph{constant} query complexity (\emph{regardless} of the number of rounds $k$). In particular, we derive a ``sumcheck protocol'' whose verifier reads $O(1)$ bits from the entire interaction transcript.

We introduce the problem of \emph{Verifiable Relation Sharing} (VRS) where a client wishes to share a vector of secret data items among several servers (the verifiers) while proving in zero-knowledge that the shared data satisfies some properties. This combined task of sharing and proving generalizes notions like verifiable secret sharing and zero-knowledge proofs over secret-shared data. We study VRS from a theoretical perspective and focus on its round complexity. \smallskip

As our main contribution, we show that every efficiently-computable relation can be realized by a VRS with an optimal round complexity of two rounds where the first round is input-independent (offline round). The protocol achieves full UC-security against an active adversary that is allowed to corrupt any $t$-subset of the parties that may include the client together with some of the verifiers. For a small (logarithmic) number of parties, we achieve an optimal resiliency threshold of $t=0.5(k+1)$, and for a large (polynomial) number of parties, we achieve an almost-optimal resiliency threshold of $t=0.5(k+1)(1-\epsilon)$ for an arbitrarily small constant $\epsilon>0$. Both protocols can be based on sub-exponentially hard injective one-way functions. If the parties have an access to a collision resistance hash function, we can derive \emph{statistical everlasting security}, i.e., the protocols are secure against adversaries that are computationally bounded during the protocol execution and become computationally unbounded after the protocol execution.

\smallskip Previous 2-round solutions achieve smaller resiliency thresholds and weaker security notions regardless of the underlying assumptions. As a special case, our protocols give rise to 2-round offline/online constructions of multi-verifier zero-knowledge proofs (MVZK). Such constructions were previously obtained under the same type of assumptions that are needed for non-interactive zero-knowledge proofs (NIZK), i.e., public-key assumptions or random-oracle type assumptions (Abe et al., Asiacrypt 2002; Groth and Ostrovsky, Crypto 2007; Boneh et al., Crypto 2019; Yang, and Wang, Eprint 2022). Our work shows, for the first time, that in the presence of an honest majority these assumptions can be replaced with more conservative ``Minicrypt''-type assumptions like injective one-way functions and collision-resistance hash functions. Indeed, our MVZK protocols provide a round-efficient substitute for NIZK in settings where honest-majority is present. Additional applications are also presented.

The COVID-19 pandemic has caused many countries to deploy novel digital contact tracing (DCT) systems to boost the efficiency of manual tracing of infection chains. In this paper, we systematically analyze DCT solutions and categorize them based on their design approaches and architectures. We analyze them with regard to effectiveness, security, privacy, and ethical aspects and compare prominent solutions with regard to these requirements. In particular, we discuss the shortcomings of the Google and Apple Exposure Notification API (GAEN) that is currently widely adopted all over the world. We find that the security and privacy of GAEN has considerable deficiencies as it can be compromised by severe large-scale attacks. We also discuss other proposed approaches for contact tracing, including our proposal TRACECORONA, that are based on Diffie-Hellman (DH) key exchange and aims at tackling shortcomings of existing solutions. Our extensive analysis shows thatTRACECORONA fulfills the above security requirements better than deployed state-of-the-art approaches. We have implementedTRACECORONA and its beta test version has been used by more than 2000 users without any major functional problems1, demonstrating that there are no technical reasons requiring to make compromises with regard to the requirements of DCTapproaches.

Interpose PUF~(iPUF) is a strong PUF construction that was shown to be vulnerable against empirical machine learning as well as PAC learning attacks. In this work, we extend the PAC Learning results of Interpose PUF to prove that the variants of iPUF are also learnable in the PAC model under the Linear Threshold Function representation class.

We present Shanrang, the first fully asynchronous proactive secret sharing scheme with dynamic committee support. Even in the worst possible network environment, where messages could have arbitrary latencies, Shanrang allows a dynamic committee to store a secret and periodically refresh the secret shares in a distributed fashion. When the committee changes, both the old committee and the new committee jointly refresh and transfer the shares to the new committee, without revealing the secret to the adversary.

With n parties, Shanrang tolerates n/4 Byzantine faults and maintains liveness as long as the messages are delivered. In contrast to prior work, Shanrang makes no assumptions on the network latency. Designing an asynchronous protocol is challenging because it is impossible to distinguish an adversary sending no messages from an honest party whose messages have not arrived yet. We evaluated Shanrang on geographically distributed machines and we found Shanrang achieved 200 seconds for handing off between 2 committees of 41 parties. Shanrang requires O(λn3 log n) messages and runs in expected O(log n) rounds for every handoff. To show Shanrang is robust even in a harsh network environ- ment, we test Shanrang on the Tor network and it shows robust performance.

In light of continued innovation in money and payments, many central banks are exploring the creation of a central bank digital currency (CBDC), a new form of central bank money which supplements existing central bank reserve account balances and physical currency.

This paper presents Hamilton, a flexible transaction processor design that supports a range of models for a CBDC and minimizes data storage in the core transaction processor by storing unspent funds as opaque hashes. Hamilton supports users custodying their own funds or custody provided by financial intermediaries.

We describe and evaluate two implementations: the atomizer architecture which provides a globally ordered history of transactions but is limited in throughput (170,000 transactions per second), and the 2PC architecture that scales peak throughput almost linearly with resources (up to a measured throughput of 1.7M transactions per second) but does not provide a globally ordered list of transactions.

We released our two architectures under the MIT open source license at https://github.com/mit-dci/opencbdc-tx.

Since its introduction at Asiacrypt 2017, the CKKS approximate homomorphic encryption scheme has become one of the most widely used and implemented homomorphic encryption schemes. Due to the approximate nature of the scheme, application developers using CKKS must ensure that the evaluation output is within a tolerable error of the corresponding cleartext computation. This is achieved by scaling the underlying raw data by an appropriate amount, known as the scale parameter, in order to preserve a certain amount of significant figures. Unfortunately, there is no clear guidance available for choosing an appro- priate scale parameter, with a trial-and-error approach typically advised. In this work, we significantly improve the state-of-affairs and present the following main contributions. We give a comprehensive theoretical and experimental analysis of CKKS noise, that considers noise coming from the encoding and homomorphic evaluation operations separately. This enables us to give the first explicit definition for precision in the CKKS context. Additionally, we demonstrate the applicability of our analysis to determine convergence properties of iterative algorithms that are commonly used in applications.

This work considers two prominent key management problems in the blockchain space: (i) allowing a (distributed) blockchain system to securely airdrop/send some tokens to a potential client Bob, who is yet to set up the required cryptographic key for the system, and (ii) creating a (distributed) cross-chain bridge that allows interoperability at scale by allowing a (changing) set of nodes in a blockchain to perform transactions on the other blockchain. The existing solutions for the first problem need Bob to either generate and maintain private keys locally for the first time in his life — a usability bottleneck — or place trust in third-party custodial services — a privacy and censorship nightmare. Towards solving both problems in a distributed setting against a threshold-bounded adversary, distributed key generation (DKG) based solutions are actively employed; here, a set of servers generate the transactions in a distributed manner and link them to clients’ ids. Nevertheless, these solutions introduce computation and communication overhead that is linear in the number of keys and do not scale well even for a million keys, especially for proactive security against a mobile adversary. This work presents a Keys-On-Demand (D-KODE) distributed protocol suite that lets the blockchain system securely generate the public key of any Bob against a mobile threshold adversary. Multiple servers, here, compute discrete-log private/public keys on the fly through distributed pseudo-random function evaluations on the queried public string. D-KODE also introduces a proactive security mechanism for the employed black-box secret-sharing based DKG to maintain the system’s longitudinal security. The proposed protocol scales well for a very high number of keys as its communication and computation complexity is independent of the number of keys. Our experimental analysis demonstrates that, for a 20-node network with a 2/3 honest majority, D-KODE starts to outperform the state of the art as the number of keys reaches 94K. D-KODE is practical as it takes less than 100msec to generate a secret key for a single-threaded server in a 20-node setup

The Institute of Information Security and Dependability at KIT is looking for two PostDocs in privacy-preserving cryptographic protocols. Experiences with secure multi-party computation and MPC compilers or UC-based security modeling are desired. A track record in this field is expected, including publications at reputable conferences such as Crypto, Eurocrypt, ACM CCS, PETS, etc.

You will be a member of the KASTEL Security Research Labs (https://zentrum.kastel.kit.edu) and the Topic "Engineering Secure Systems" of the Helmholtz Association. Your research is dealing with cryptographic protocols for privacy-preserving computations, e.g., applied to mobility or production systems. It will result in both theoretical security concepts (protocol designs, security proofs, etc.) and their practical implementation (e.g., a demonstrator) for some application domain. The contract will initially be limited to 1 year, but can be extended.

If you are interested, please send an email including your CV and a list of publications to andy.rupp@rub.de. Applications will be reviewed continuously until the positions are filled.

Closing date for applications:

Contact: Andy Rupp (andy.rupp@rub.de)

You will join the team responsible for the security architecture of Qualcomm Snapdragon processors. The team works at a system level spanning across hardware, software and infrastructure while striving for industry-leading solutions. This team interacts with product management, customers (e.g., OEMs), partners and HW/SW engineering teams to find the optimal security solutions.
Snapdragon processors are used in different types of devices ranging from mobile phones to televisions, cars, ultra-book laptops etc. Our processors are designed to meet security requirements ranging from content protection to enterprise security, using virtualization, HW security enclaves, factory key provisioning, and secure updates.
In this position you will perform the following tasks:

• Define HW crypto security requirements (functional, performance, security etc)
• Define HW/SW partitioning to address next challenges in cryptography such as PQC and Crypto Agility
• Define crypto and HW blocks that contribute to the overall SoC Security Architecture
• Design of mechanisms thwarting side channel attacks
• Monitor evaluation of crypto IP resistance and robustness
• Competitive analysis of security IPs and features
• Investigate future/roadmap security related technologies,
• Participation in academic conference and industrial/research security working groups.

Minimum Qualifications: MS or Bachelor in Computer Science, Mathematics or Electrical Engineering plus 5+ years industry experience in one or more of the following areas

• Cryptographic primitives, cryptographic protocols and their implementation
• Design of HW/SW security blocks such as HW cryptographic engines
• HW/SW threat analysis, security analysis or/and risk analysis
• Smart Card and secure HW technologies
• Security certifications: process and requirements.

Additional skills in the following areas are a plus:

• Academic and industry research (publications, conferences)
• Leadership & management background
• Excellent communication and teamwork skills are required

Closing date for applications:

Contact: Nicolas Courtois

More information: https://qualcomm.wd5.myworkdayjobs.com/en-US/External/details/Embedded-Crypto-Expert---Sophia-Antipolis--France_3024348-1?locationCountry=54c5b6971ffb4bf0b116fe7651ec789a

Event date: 26 July to 28 July 2022
Submission deadline: 15 March 2022
Notification: 25 May 2022