检索结果-内蒙古大学图书馆

A new constant-time parallel algorithm for merging

JOURNAL OF SUPERCOMPUTING 2019年第2期75卷 968-983页

作者： Bahig, Hazem M. Ain Shams Univ Fac Sci Dept Math Div Comp Sci Cairo 11566 Egypt Hail Univ Comp Sci & Engn Coll Hail Saudi Arabia

Merging is the process of constructing a sorted array C from two sorted arrays A and B of lengths nA and nB, respectively, such that array C contains the elements of arrays A and B. The problem is a fundamental subroutine in many applications such as tree reconstruction, database design, and sorting. In this paper, we present a constant-time integer merging algorithm on a shared memory model with a concurrent read operation. No constant-time algorithm for integer merging on this model was designed previously. The algorithm, which is based on cross-rank and address strategy, works when the elements of the inputs belong to the integer domain. The presented algorithm has the following advantages:- (1) running in constant time;(2) stable;(3) simple;(4) optimal when the domain of integers is less than or equal to the size of the inputs and the number of processors is equal to size of the inputs;and (5) deterministic.

关键词： Integer merging Parallel algorithm Shared memory Concurrent read constant-time algorithm

来源：评论

学校读者我要写书评

暂无评论

A constant time algorithm for some optimization problems in rotagraphs and fasciagraphs

引用

DISCRETE APPLIED MATHEMATICS 2016年 208卷 27-40页

作者： Bouznif, M. Moncel, J. Preissmann, M. Univ Grenoble Alpes G SCOP F-38000 Grenoble France CNRS G SCOP F-38000 Grenoble France CNRS LAAS 7 Ave Colonel Roche F-31400 Toulouse France Univ Toulouse Univ Toulouse 1 IUT Rodez LAAS F-31000 Toulouse France

This paper deals with optimization problems on rotagraphs and fasciagraphs. These graphs are repetitive structures that generalize grids and toroidal grids, respectively. We develop a theoretical framework and get linear-time and constant-time generic algorithms for wide classes of combinatorial problems which are defined in a purely combinatorial way. These classes of problems include in particular many classical optimization problems that are NP-complete in general. Our results unify in a single framework many results of the literature, in particular on the topic of domination - and its variants - in grids. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Combinatorial optimization problems constant-time algorithm Grids Fasciagraphs Rotagraphs Min-Plus algebra

来源：评论

学校读者我要写书评

暂无评论

Probabilistic root finding in code-based cryptography

引用

JOURNAL OF CRYPTOGRAPHIC ENGINEERING 2024年第1期14卷 71-85页

作者： Marchiori, Dunia Custodio, Ricardo Panario, Daniel Moura, Lucia Univ Fed Santa Catarina Programa Posgrad Ciencia Comp Florianopolis Brazil Carleton Univ Sch Math & Stat Ottawa ON Canada Univ Ottawa Sch Elect Engn & Comp Sci Ottawa ON Canada

Probabilistic algorithms for finding roots of polynomials have not been applied to code-based cryptography before. One obstacle is their non-constant execution time, since runtime variations can be exploited by side-channel attack techniques. We aim to create a constant-time approach to probabilistic algorithms, so cryptosystems can benefit from these algorithms' efficiency, especially when considering larger parameters. Our countermeasure prevents that the execution time of a probabilistic root-finding algorithm be dependent on the degree of the input polynomial and makes it dependent only on the cryptosystem parameters. We compare the performance of our proposal to other root-finding algorithms already used in code-based cryptography and related works. We also show that our countermeasure can be applied to other root-finding algorithms successfully. In general, our method is faster than a variant of the Berlekamp Trace algorithm, the exhaustive algorithm in Classic McEliece and the additive Fast Fourier Transform algorithm for plausible parameters with larger finite fields.

关键词： Post-quantum cryptography Code-based cryptography Root-finding algorithms Probabilistic root finding Timing side-channel attack constant-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Testing Proximity to Subspaces: Approximate l∞ Minimization in constant time

引用

algorithmICA 2020年第5期82卷 1277-1297页

作者： Hayashi, Kohei Yoshida, Yuichi Natl Inst Adv Ind Sci & Technol Artificial Intelligence Res Ctr Koto Ku 2-3-26 Aomi Tokyo 1350064 Japan Natl Inst Informat Principles Informat Res Div Chiyoda Ku 2-1-2 Hitotsubashi Tokyo 1018430 Japan Preferred Networks Inc Chiyoda Ku 1-6-1 Otemachi Tokyo 1000004 Japan

We consider the subspace proximity problem: Given a vector x. Rn and a basis matrix V. Rnxm, the objective is to determine whether x is close to the subspace spanned by V. Although the problem is solvable by linear programming, it is time consuming especially when n is large. In this paper, we propose a quick tester that solves the problem correctly with high probability. Our tester runs in time independent of n and can be used as a sieve before computing the exact distance between x and the subspace. The number of coordinates of x queried by our tester is O( m log m ), where is an error parameter, and we show almost matching lower bounds. By experiments, we demonstrate the scalability and applicability of our tester using synthetic and real data sets.

关键词： constant-time algorithm Property testing Subspace proximity problem VC dimension

来源：评论

学校读者我要写书评

暂无评论

On constant-time QC-MDPC Decoders with Negligible Failure Rate 1

引用

8th International Workshop on Code-Based Cryptography (CBCrypto)

作者： Drucker, Nir Gueron, Shay Kostic, Dusan Univ Haifa Haifa Israel Amazon Seattle WA 98109 USA Ecole Polytech Fed Lausanne Lausanne Switzerland

ISBN: (数字)9783030540746

ISBN: (纸本)9783030540746;9783030540739

The QC-MDPC code-based KEM Bit Flipping Key Encapsulation (BIKE) is one of the Round-2 candidates of the NIST PQC standardization project. It has a variant that is proved to be IND-CCA secure. The proof models the KEM with some black-box ("ideal") primitives. Specifically, the decapsulation invokes an ideal primitive called "decoder", required to deliver its output with a negligible Decoding Failure Rate (DFR). The concrete instantiation of BIKE substitutes this ideal primitive with a new decoding algorithm called "Backflip", that is shown to have the required negligible DFR. However, it runs in a variable number of steps and this number depends on the input and on the key. This paper proposes a decoder that has a negligible DFR and also runs in a fixed (and small) number of steps. We propose that the instantiation of BIKE uses this decoder with our recommended parameters. We study the decoder's DFR as a function of the scheme's parameters to obtain a favorable balance between the communication bandwidth and the number of steps that the decoder runs. In addition, we build a constant-time software implementation of the proposed instantiation, and show that its performance characteristics are quite close to the IND-CPA variant. Finally, we discuss a subtle gap that needs to be resolved for every IND-CCA secure KEM (BIKE included) where the decapsulation has nonzero failure probability: the difference between average DFR and "worst-case" failure probability per key and ciphertext.

关键词： BIKE QC-MDPC codes IND-CCA constant-time algorithm constant-time implementation

来源：评论

学校读者我要写书评

暂无评论

Fast polynomial inversion for post quantum QC-MDPC cryptography

引用

INFORMATION AND COMPUTATION 2021年 281卷 104799-104799页

作者： Drucker, Nir Gueron, Shay Kostic, Dusan Univ Haifa Haifa Israel Amazon Seattle WA USA Ecole Polytech Fed Lausanne Lausanne Switzerland

New post-quantum Key Encapsulation Mechanism (KEM) designs, evaluated as part of the NIST PQC standardization Project, pose challenging tradeoffs between communication bandwidth and computational overheads. Several KEM designs evaluated in Round-2 of the project are based on QC-MDPC codes. BIKE-2 uses the smallest communication bandwidth, but its key generation requires a costly polynomial inversion. In this paper, we provide details on the optimized polynomial inversion algorithm for QC-MDPC codes (originally proposed in the conference version of this work). This algorithm makes the runtime of BIKE-2 key generation tolerable. It brings a speedup of 11.4x over the commonly used NTL library, and 83.5x over OpenSSL. We achieve additional speedups by leveraging the latest Intel's Vector-PCLMULQDQ instructions, 14.3x over NTL and 103.9x over OpenSSL. Our algorithm and implementation were the reason that BIKE team chose BIKE-2 as the only scheme for its Round-3 specification (now called BIKE). (C) 2021 The Authors. Published by Elsevier Inc.

关键词： Polynomial inversion BIKE QC-MDPC codes constant-time algorithm constant-time implementation NIST PQC round-3

来源：评论

学校读者我要写书评

暂无评论

Fast Polynomial Inversion for Post Quantum QC-MDPC Cryptography 1

引用

4th International Symposium on Cyber Security Cryptography and Machine Learning (CSCML)

作者： Drucker, Nir Gueron, Shay Kostic, Dusan Univ Haifa Haifa Israel Amazon Seattle WA USA EPFL Switzerland Lausanne Switzerland

ISBN: (数字)9783030497859

ISBN: (纸本)9783030497859;9783030497842

The NIST PQC standardization project evaluates multiple new designs for post-quantum Key Encapsulation Mechanisms (KEMs). Some of them present challenging tradeoffs between communication bandwidth and computational overheads. An interesting case is the set of QC-MDPC based KEMs. Here, schemes that use the Niederreiter framework require only half the communication bandwidth compared to schemes that use the McEliece framework. However, this requires costly polynomial inversion during the key generation, which is prohibitive when ephemeral keys are used. One example is BIKE, where the BIKE-1 variant uses McEliece and the BIKE-2 variant uses Niederreiter. This paper shows an optimized constant-time polynomial inversion method that makes the computation costs of BIKE-2 key generation tolerable. We report a speedup of 11.8x over the commonly used NTL library, and 55.5x over OpenSSL. We achieve additional speedups by leveraging the latest Intel's Vector-PCLMULQDQ instructions on a laptop machine, 14.3x over NTL and 96.8x over OpenSSL. With this, BIKE-2 becomes a competitive variant of BIKE.

关键词： Polynomial inversion BIKE QC-MDPC codes constant-time algorithm constant-time implementation

来源：评论

学校读者我要写书评

暂无评论

Acceleration of the Shiftable O(1) algorithm for Bilateral Filtering and Nonlocal Means

引用

IEEE TRANSACTIONS ON IMAGE PROCESSING 2013年第4期22卷 1291-1300页

作者： Chaudhury, Kunal N. Princeton Univ Program Appl & Computat Math Princeton NJ 08544 USA

A direct implementation of the bilateral filter requires O(sigma(2)(s)) operations per pixel, where sigma(s) is the (effective) width of the spatial kernel. A fast implementation of the bilateral filter that required O(1) operations per pixel with respect to sigma(s) was recently proposed. This was done by using trigonometric functions for the range kernel of the bilateral filter, and by exploiting their so-called shiftability property. In particular, a fast implementation of the Gaussian bilateral filter was realized by approximating the Gaussian range kernel using raised cosines. Later, it was demonstrated that this idea could be extended to a larger class of filters, including the popular non-local means filter. As already observed, a flip side of this approach was that the run time depended on the width sigma(r) of the range kernel. For an image with dynamic range [0, T], the run time scaled as O(T-2/sigma(2)(r)) with sigma(r). This made it difficult to implement narrow range kernels, particularly for images with large dynamic range. In this paper, we discuss this problem, and propose some simple steps to accelerate the implementation, in general, and for small sigma(r) in particular. We provide some experimental results to demonstrate the acceleration that is achieved using these modifications.

关键词： Bilateral filter constant-time algorithm Gaussian kernel max filter nonlocal means O(1) complexity recursive filter running maximum shiftability truncation

来源：评论

学校读者我要写书评

暂无评论

Hardware software co-design of a fast bilateral filter in FPGA

Hardware software co-design of a fast bilateral filter in FP...

引用

10th Annual Conference of the IEEE-India-Council (INDICON)

作者： Pal, Chandrajit Chaudhury, Kunal N. Samanta, Asit Chakrabarti, Amlan Ghosh, Ranjan Univ Calcutta AK Choudhury Sch Informat Technol Kolkata 700073 W Bengal India Princeton Univ PACM Princeton NJ 08544 USA Univ Calcutta Inst Radiophys & Elect Kolkata 700073 W Bengal India

ISBN: (纸本)9781479922741;9781479922758

Bilateral filters are widely used in computer vision and digital imaging applications such as denoising, video abstraction, demosaicing, optical-flow estimation etc. to name a few. Its smoothing and edge preserving characteristics suites perfectly for image and video processing applications, yet its high computational complexity makes real-time hardware implementation a challenging task. This paper provides an efficient Field Programmable Gate Array (FPGA) based implementation of an edge preserving fast bilateral filter on a hardware software co-design environment of a most recent algorithm preserving the boundaries, spikes and canyons in presence of noise. Further, the four stage parallel pipelined architecture greatly improves the speed of operation. Moreover, our separable kernel implementation of the filtering hardware increases the speed of execution by almost five times than the traditional convolution filtering, while utilizing less hardware resource.

关键词： Bilateral filter edge-preserving smoothing constant-time algorithm O(1) complexity raised cosines FPGA system generator VHDL

来源：评论

学校读者我要写书评

暂无评论

Hardware software co-design of a fast bilateral filter in FPGA

Hardware software co-design of a fast bilateral filter in FP...

引用

Annual IEEE India Conference

作者： Chandrajit Pal Kunal N. Chaudhury Asit Samanta Amlan Chakrabarti Ranjan Ghosh A.K Choudhury School of Information Technology University of Calcutta Program in Applied and Computational Mathematics (PACM) Princeton University Institute of RadioPhysics and Electronics University of Calcutta

ISBN: (纸本)9781479922765

关键词： Bilateral filter edge-preserving smoothing constant-time algorithm O(1) complexity raised cosines FPGA system generator VHDL

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：