Abstract

In this paper we show that standard model black-box reduc-tions naturally lift to various setup assumptions, such as random oracle(ROM) or ideal cipher model. Concretely, we prove that a black-boxreduction from a security notion P to security notion Q in the standard model can be turned into a non-programmable black-box reduction fromPOtoQOin a model with a the setup assumption O, where P_O and Q_O are the natural extensions of P and Q to a model with setup assumption O. Our results rely on a generalization of the recent framework by Hofheinz and Nguyen (PKC 2019) to support primitives which make use of atrusted setup. Our framework encompasses standard idealized settings like the random oracle and the ideal cipher model. At the core of ourmain result lie novel properties of negligible functions that can be ofindependent interest.

Abstract

Abstract

Vickrey auctions "in the wild" are rare due to distrust to participants colluding. Prior work has shown that vanilla Vickrey auctions while dominant are not a credible mechanism, that is participants benefit from collusions. We show the existence of a credible Vickrey mechanism variant. We prove security of our construction against an adaptive probabilistic polynomial time adversary. Finally we prove the impossibility of a credible first price or second price auction with half or more of the participants colluding.
A key property of our construction is it preserves privacy of the auctioned item distribution along with the utility function of the bidders. We show that lack of the latter property is crucial in the presence of a corruptible auctioneer for any multi-round auction mechanism. Lack of the former implies bidder collusions against the auctioneer.

Abstract

A game-based cryptographic proof is a relation that estab-lishes equivalence between probabilistic sequences of actions by real andideal world players. The author of a proof selects ahardness assumptionsystemfor their proof upon which to base their subsequent statements. Inthis paper, we prove the existence of proof-invariant transformations forvarying hardness assumptions. We show that for two systems satisfyingcertain algebraic properties any proof in one system has an equivalentvalid proof in the other. This validates Kurosawa’s remark about theexistence of proof similarities.Our result implies a correspondence between the Learning With Errors(LWE) problems and both the Elliptic Curve Discrete Log problem(ECDLP) and the Discrete Logarithm (DLOG) problem. To illustrate thisresult, we provide a series of example transformations in the appendix. The concrete result of this paper is a prototype proof translation tool.

Abstract

In this paper we explore the impact of data encoding on the design of arithmetic circuits based on residue number system (RNS). Specifically, we show that departing from the conventional representation of residues as integers in weighed binary format and appropriately selecting a non-weighed encoding, efficient circuits in terms of power, area and performance are possible. A quantitative analysis reports savings of the order of 45% for some complexity-related metrics of practical interest.