Feedback
Follow Us
Publication

Fast polynomial inversion for post quantum QC-MDPC cryptography

By Nir Drucker, Shay Gueron, Dusan Kostic
2020
Download Copy BibTeX
Share
Download
Copy BibTeX
Share
The NIST PQC standardization project evaluates multiple new designs for post-quantum Key Encapsulation Mechanisms (KEMs). Some of them present challenging tradeoffs between communication band-width 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 pa-per shows an optimized constant-time polynomial inversion method that makes the computation costs of BIKE-2 key generation tolerable. We re-port a speedup of 11.8×over the commonly used NTL library, and 55.5×over OpenSSL. We achieve additional speedups by leveraging the latest Intel’s Vector-PCLMULQDQ instructions on a laptop machine, 14.3× over NTL and 96.8× over OpenSSL. With this, BIKE-2 becomes a competitive variant of BIKE.
Research areas
Tags

Latest news

Work with us

See more jobs See more jobs
Senior Applied Scientist, Amazon
US, NY, New York
We are seeking a motivated and experienced Senior Applied Scientist with expertise in Machine Learning (ML), Artificial Intelligence (AI), Big Data, and Service Oriented Architecture. You should have a deep understanding of the digital advertising business and scaled marketing across communication channels. In this role, you will collaborate with a cross-functional team of talented scientists and engineers to innovate, iterate, and solve real-world marketing problems with cutting-edge AWS technologies. You will lead in-depth analyses of the key problems faced by Amazon Ads customers and the challenges faced by marketing teams in meeting customer needs at scale. To address these problems, you will build innovative large-scale ML/AI solutions such as bespoke omni-channel recommender systems, and specialized LLM-powered assistants for customers and marketers. You will independently drive research and prototyping to deliver functional proofs of concept (POCs), and then partner with engineers to inform the technology roadmap and deploy successful POCs as scalable batch and real-time applications in production. Key job responsibilities • Define and execute a research and development plan that enables data-driven marketing decisions and delivers inspiring customer experiences • Evaluate, evolve, and invent scientific techniques to effectively address customer needs and business problems • Establish and drive science prototyping best practices to ensure coherence and integrity of data feeding into production ML/AI solutions • Collaborate with colleagues across science and engineering disciplines for rapid prototyping at scale • Partner with engineering teams to solve complex technical problems, define system-level requirements, develop implementation plans, and guide the adaptation of techniques to meet production needs • Partner with product managers and stakeholders to define forward-looking product visions and prospective business use-cases • Drive and lead of culture of data-driven innovation within and outside across Amazon Ads Marketing organization • Influence organizational vision across Ads Marketing organization About the team The Marketing Decisions Science team provides AI/ML products to enable Amazon Ads Marketing to deliver relevant and compelling guidance, education, and inspiration to prospective and active advertisers across marketing channels. We own the product, technology, and deployment roadmap for AI/ML products across Amazon Ads Marketing. We analyze the needs, experiences, and behaviors of Amazon advertisers at petabytes scale, to deliver the right marketing communications to the right advertiser at the right time. Our products enable applications and synergies across Ads organization, spanning marketing, product, and sales use cases.
Sr. Data Scientist, Generative AI Innovation Center
US, NY, New York
Are you looking to work at the forefront of Machine Learning and AI? Would you be excited to apply cutting edge Generative AI algorithms to solve real world problems with significant impact? The Generative AI Innovation Center at AWS is a new strategic team that helps AWS customers implement Generative AI solutions and realize transformational business opportunities. This is a team of strategists, data scientists, engineers, and solution architects working step-by-step with customers to build bespoke solutions that harness the power of generative AI. The team helps customers imagine and scope the use cases that will create the greatest value for their businesses, select and train and fine tune the right models, define paths to navigate technical or business challenges, develop proof-of-concepts, and make plans for launching solutions at scale. The GenAI Innovation Center team provides guidance on best practices for applying generative AI responsibly and cost efficiently. You will work directly with customers and innovate in a fast-paced organization that contributes to game-changing projects and technologies. You will design and run experiments, research new algorithms, and find new ways of optimizing risk, profitability, and customer experience. We’re looking for Data Scientists capable of using GenAI and other techniques to design, evangelize, and implement state-of-the-art solutions for never-before-solved problems. This position requires that the candidate selected be a US Citizen. Key job responsibilities As an Data Scientist, you will - Collaborate with AI/ML scientists and architects to Research, design, develop, and evaluate cutting-edge generative AI algorithms to address real-world challenges - Interact with customers directly to understand the business problem, help and aid them in implementation of generative AI solutions, deliver briefing and deep dive sessions to customers and guide customer on adoption patterns and paths to production - Create and deliver best practice recommendations, tutorials, blog posts, sample code, and presentations adapted to technical, business, and executive stakeholder - Provide customer and market feedback to Product and Engineering teams to help define product direction A day in the life About AWS Diverse Experiences AWS values diverse experiences. Even if you do not meet all of the qualifications and skills listed in the job description, we encourage candidates to apply. If your career is just starting, hasn’t followed a traditional path, or includes alternative experiences, don’t let it stop you from applying. Why AWS? Amazon Web Services (AWS) is the world’s most comprehensive and broadly adopted cloud platform. We pioneered cloud computing and never stopped innovating — that’s why customers from the most successful startups to Global 500 companies trust our robust suite of products and services to power their businesses. Inclusive Team Culture Here at AWS, it’s in our nature to learn and be curious. Our employee-led affinity groups foster a culture of inclusion that empower us to be proud of our differences. Ongoing events and learning experiences, including our Conversations on Race and Ethnicity (CORE) and AmazeCon (gender diversity) conferences, inspire us to never stop embracing our uniqueness. Mentorship & Career Growth We’re continuously raising our performance bar as we strive to become Earth’s Best Employer. That’s why you’ll find endless knowledge-sharing, mentorship and other career-advancing resources here to help you develop into a better-rounded professional. Work/Life Balance We value work-life harmony. Achieving success at work should never come at the expense of sacrifices at home, which is why flexible work hours and arrangements are part of our culture. When we feel supported in the workplace and at home, there’s nothing we can’t achieve in the cloud.
Senior Economist, Device Economics
US, WA, Seattle
Device Economics is looking for a senior economist experienced in causal inference, machine learning, empirical industrial organization, and scaled systems to work on business problems to advance critical resource allocation and pricing decisions in the Amazon Devices org. Senior roles lead vision setting, methods innovation, and act as thought leaders to Devices finance and business executives. Output will be included in scaled systems to automate existing processes and to maximize business and customer objectives. Amazon Devices designs and builds Amazon first-party consumer electronics products to delight and engage customers. Amazon Devices represents a highly complex space with 100+ products across several product categories (e-readers [Kindle], tablets [Fire Tablets], smart speakers and audio assistants [Echo], wifi routers [eero], and video doorbells and cameras [Ring and Blink]), for sale both online and in offline retailers in several regions. The space becomes more complex with dynamic product offering with new product launches and new marketplace launches. The Device Economics team leads in analyzing these complex marketplace dynamics to enable science-driven decision making in the Devices org. Device Economics achieves this through scientific applications that provide deep understanding of customer preferences. Our team’s outputs inform product development decisions, investments in future product categories, and product pricing and promotion. We have achieved substantial impact on the Devices business, and will achieve more. Device Economics seeks an experienced economist adept in measuring customer preferences and behaviors with proven capacity to innovate, scale measurement, drive rigor, and mentor talent. The candidate will work with Amazon Devices science leadership to refine science roadmaps, models, and priorities for innovation and simplification, and advance adoption of insights to influence important resource allocation and prioritization decisions. Effective communication skills (verbal and written) are required to ensure success of this collaboration. The candidate must be passionate about advancing science for business and customer impact.
Research Scientist, Prime Video
US, WA, Seattle
Prime Video is a first-stop entertainment destination offering customers a vast collection of premium programming in one app available across thousands of devices. On Prime Video, customers can find their favorite movies, series, documentaries, and live sports – including Amazon MGM Studios-produced series and movies Road House, The Lord of the Rings: The Rings of Power, Fallout, Reacher, The Boys, and The Idea of You; licensed fan favorites Dawson’s Creek and IF; Prime member exclusive access to coverage of live sports including Thursday Night Football, WNBA, and NWSL, and acclaimed sports documentaries including Bye Bye Barry and Federer; and programming from partners such as Apple TV+, Max, Crunchyroll, and MGM+ via Prime Video add-on subscriptions, as well as more than 500 free ad-supported (FAST) Channels. Prime members in the U.S. can share a variety of benefits, including Prime Video, by using Amazon Household. Prime Video is one benefit among many that provides savings, convenience, and entertainment as part of the Prime membership. All customers, regardless of whether they have a Prime membership or not, can rent or buy titles, including blockbusters such as Challengers and The Fall Guy, via the Prime Video Store, and can enjoy content such as Jury Duty and Bosch: Legacy free with ads on Freevee. Customers can also go behind the scenes of their favorite movies and series with exclusive X-Ray access. For more info visit www.amazon.com/primevideo. Are you interested in shaping the future of entertainment? Prime Video's technology teams are creating best-in-class digital video experience. As a Prime Video technologist, you’ll have end-to-end ownership of the product, user experience, design, and technology required to deliver state-of-the-art experiences for our customers. You’ll get to work on projects that are fast-paced, challenging, and varied. You’ll also be able to experiment with new possibilities, take risks, and collaborate with remarkable people. We’ll look for you to bring your diverse perspectives, ideas, and skill-sets to make Prime Video even better for our customers. With global opportunities for talented technologists, you can decide where a career Prime Video Tech takes you! Key job responsibilities As a Research Scientist at Prime Video, you will have end-to-end ownership of the product, related research and experimentation, applying advanced machine learning techniques in computer vision (CV), natural language processing (NLP), multimedia understanding and so on. You’ll work on diverse projects that enhance Prime Video’s recommendation systems, image/video understanding, and content personalization, driving impactful innovations for our global audience. Other responsibilities include: • Lead cutting-edge research in computer vision and natural language processing, applying it to video-centric media challenges. • Develop scalable machine learning models to enhance media asset generation, content discovery, and personalization. • Collaborate closely with engineering teams to integrate your models into production systems at scale, ensuring optimal performance and reliability. • Actively participate in publishing your research in leading conferences and journals. • Lead a team of skilled research scientists, you will shape the research strategy, create forward-looking roadmaps, and effectively communicate progress and insights to senior leadership • Stay up-to-date with the latest advancements in AI and machine learning to drive future research initiatives.
Applied Scientist , Gen AI
IL, Haifa
AWS Utility Computing (UC) provides product innovations — from foundational services such as Amazon’s Simple Storage Service (S3) and Amazon Elastic Compute Cloud (EC2), to consistently released new product innovations that continue to set AWS’s services and features apart in the industry. As a member of the UC organization, you’ll support the development and management of Compute, Database, Storage, Internet of Things (Iot), Platform, and Productivity Apps services in AWS, including support for customers who require specialized security solutions for their cloud services. Are you an inventive, curious, and driven Applied Scientist with a strong background in AI and Deep Learning? Join Amazon’s AWS Multimodal generative AI science team and be a catalyst for groundbreaking advancements in Computer Vision, Generative AI, and foundational models. As part of the AWS Multimodal generative AI science team, you’ll lead innovative research projects, develop state-of-the-art algorithms, and pioneer solutions that will directly impact millions of Amazon customers. Leveraging Amazon’s vast computing power, you’ll work alongside a supportive and diverse group of top-tier scientists and engineers, contributing to products that redefine the industry. Key job responsibilities * Lead research initiatives in Multimodal generative AI, pushing the boundaries of model efficiency, accuracy, and scalability. * Design, implement, and evaluate deep learning models in a production environment. * Collaborate with cross-functional teams to transfer research outcomes into scalable AWS services. * Publish in top-tier conferences and journals, keeping Amazon at the forefront of innovation. * Mentor and guide other scientists and engineers, fostering a culture of scientific curiosity and excellence. About the team About AWS Diverse Experiences AWS values diverse experiences. Even if you do not meet all of the preferred qualifications and skills listed in the job description, we encourage candidates to apply. If your career is just starting, hasn’t followed a traditional path, or includes alternative experiences, don’t let it stop you from applying. Why AWS? Amazon Web Services (AWS) is the world’s most comprehensive and broadly adopted cloud platform. We pioneered cloud computing and never stopped innovating — that’s why customers from the most successful startups to Global 500 companies trust our robust suite of products and services to power their businesses. Inclusive Team Culture: Here at AWS, it’s in our nature to learn and be curious. Our employee-led affinity groups foster a culture of inclusion that empower us to be proud of our differences. Ongoing events and learning experiences, including our Conversations on Race and Ethnicity (CORE) and AmazeCon (gender diversity) conferences, inspire us to never stop embracing our uniqueness. Mentorship & Career Growth We’re continuously raising our performance bar as we strive to become Earth’s Best Employer. That’s why you’ll find endless knowledge-sharing, mentorship and other career-advancing resources here to help you develop into a better-rounded professional. Work/Life Balance We value work-life harmony. Achieving success at work should never come at the expense of sacrifices at home, which is why we strive for flexibility as part of our working culture. When we feel supported in the workplace and at home, there’s nothing we can’t achieve.
Applied Scientist, Generative Artificial Intelligence (AI) Innovation Center
AU, NSW, Sydney
AWS Sales, Marketing, and Global Services (SMGS) is responsible for driving revenue, adoption, and growth from the largest and fastest growing small- and mid-market accounts to enterprise-level customers including public sector. The AWS Global Support team interacts with leading companies and believes that world-class support is critical to customer success. AWS Support also partners with a global list of customers that are building mission-critical applications on top of AWS services. The Generative Artificial Intelligence (AI) Innovation Center team at AWS provides opportunities to innovate in a fast-paced organization that contributes to game-changing projects and technologies leveraging cutting-edge generative AI algorithms. As an Applied Scientist, you'll partner with technology and business teams to build solutions that surprise and delight our customers. We’re looking for Applied Scientists capable of using generative AI and other ML techniques to design, evangelize, and implement state-of-the-art solutions for never-before-solved problems. Key job responsibilities - Collaborate with scientists and engineers to research, design and develop cutting-edge generative AI algorithms to address real-world challenges - Work across customer engagement to understand what adoption patterns for generative AI are working and rapidly share them across teams and leadership - Interact with customers directly to understand the business problem, help and aid them in implementation of generative AI solutions, deliver briefing and deep dive sessions to customers and guide customer on adoption patterns and paths for generative AI - Create and deliver best practice recommendations, tutorials, blog posts, sample code, and presentations adapted to technical, business, and executive stakeholder - Provide customer and market feedback to Product and Engineering teams to help define product direction. A day in the life Here at AWS, we embrace our differences. We are committed to furthering our culture of inclusion. We have ten employee-led affinity groups, reaching 40,000 employees in over 190 chapters globally. We have innovative benefit offerings, and host annual and ongoing learning experiences, including our Conversations on Race and Ethnicity (CORE) and AmazeCon (gender diversity) conferences. Amazon’s culture of inclusion is reinforced within our 16 Leadership Principles, which remind team members to seek diverse perspectives, learn and be curious, and earn trust. About the team Diverse Experiences AWS values diverse experiences. Even if you do not meet all of the qualifications and skills listed in the job description, we encourage candidates to apply. If your career is just starting, hasn’t followed a traditional path, or includes alternative experiences, don’t let it stop you from applying. Why AWS? Amazon Web Services (AWS) is the world’s most comprehensive and broadly adopted cloud platform. We pioneered cloud computing and never stopped innovating — that’s why customers from the most successful startups to Global 500 companies trust our robust suite of products and services to power their businesses. Inclusive Team Culture Here at AWS, it’s in our nature to learn and be curious. Our employee-led affinity groups foster a culture of inclusion that empower us to be proud of our differences. Ongoing events and learning experiences, including our Conversations on Race and Ethnicity (CORE) and AmazeCon (gender diversity) conferences, inspire us to never stop embracing our uniqueness. Mentorship & Career Growth We’re continuously raising our performance bar as we strive to become Earth’s Best Employer. That’s why you’ll find endless knowledge-sharing, mentorship and other career-advancing resources here to help you develop into a better-rounded professional. Work/Life Balance We value work-life harmony. Achieving success at work should never come at the expense of sacrifices at home, which is why we strive for flexibility as part of our working culture. When we feel supported in the workplace and at home, there’s nothing we can’t achieve in the cloud. What if I don’t meet all the requirements? That’s okay! We hire people who have a passion for learning and are curious. You will be supported in your career development here at AWS. You will have plenty of opportunities to build your technical, leadership, business and consulting skills. Your onboarding will set you up for success, including a combination of formal and informal training. You’ll also have a chance to gain AWS certifications and access mentorship programs. You will learn from and collaborate with some of the brightest technical minds in the industry today.
Applied Scientist , Sponsored Products Ads Response Prediction
US, WA, Seattle
** This position is open to all candidates in Palo Alto, CA, Seattle, WA, NYC and Arlington, VA ** Amazon Ads Response Prediction team is your choice, if you want to join a highly motivated, collaborative, and fun-loving team with a strong entrepreneurial spirit and bias for action. We are seeking an experienced and motivated Machine Learning Applied Scientist who loves to innovate at the intersection of customer experience, deep learning, and high-scale machine-learning systems. Amazon Advertising operates at the intersection of eCommerce and advertising, and is investing heavily in building a world-class advertising business. We are defining and delivering a collection of self-service performance advertising products that drive discovery and sales. Our products are strategically important to our Retail and Marketplace businesses driving long-term growth. We deliver billions of ad impressions and millions of clicks daily and are breaking fresh ground to create world-class products to improve both shopper and advertiser experience. With a broad mandate to experiment and innovate, we grow at an unprecedented rate with a seemingly endless range of new opportunities. We are looking for a talented Machine Learning Applied Scientist for our Amazon Ads Response Prediction team to grow the business. We are providing advanced real-time machine learning services to connect shoppers with right ads on all platforms and surfaces worldwide. Through the deep understanding of both shoppers and products, we help shoppers discover new products they love, be the most efficient way for advertisers to meet their customers, and helps Amazon continuously innovate on behalf of all customers. Key job responsibilities As a Machine Learning Applied Scientist, you will: * Conduct deep data analysis to derive insights to the business, and identify gaps and new opportunities * Develop scalable and effective machine-learning models and optimization strategies to solve business problems * Run regular A/B experiments, gather data, and perform statistical analysis * Work closely with software engineers to deliver end-to-end solutions into production * Improve the scalability, efficiency and automation of large-scale data analytics, model training, deployment and serving * Conduct research on new machine-learning modeling to optimize all aspects of Sponsored Products business About the team We are pioneers in applying advanced machine learning and generative AI algorithms in Sponsored Products business. We empower every customer with a customized discovery experiences from back-end optimization (such as customized response prediction models) to front-end CX innovation (such as widgets), to help shoppers feel understood and shop efficiently on and off Amazon.
Sr. Research Scientist, Special Projects
US, WA, Seattle
Innovators wanted! Are you an entrepreneur? A builder? A dreamer? This role is part of an Amazon Special Projects team that takes the company’s Think Big leadership principle to the extreme. We focus on creating entirely new products and services with a goal of positively impacting the lives of our customers. No industries or subject areas are out of bounds. If you’re interested in innovating at scale to address big challenges in the world, this is the team for you. Here at Amazon, we embrace our differences. We are committed to furthering our culture of inclusion. We have thirteen employee-led affinity groups, reaching 40,000 employees in over 190 chapters globally. We are constantly learning through programs that are local, regional, and global. Amazon’s culture of inclusion is reinforced within our 16 Leadership Principles, which remind team members to seek diverse perspectives, learn and be curious, and earn trust. Our team highly values work-life balance, mentorship and career growth. We believe striking the right balance between your personal and professional life is critical to life-long happiness and fulfillment. We care about your career growth and strive to assign projects and offer training that will challenge you to become your best.
Sr. Economist, People Experience and Technology Central Science
US, VA, Arlington
The Central Science Team within Amazon’s People Experience and Technology org (PXTCS) uses economics, behavioral science, statistics, and machine learning to proactively identify mechanisms and process improvements which simultaneously improve Amazon and the lives, well-being, and the value of work to Amazonians. We are an interdisciplinary team, which combines the talents of science and engineering to develop and deliver solutions that measurably achieve this goal. We are looking for a Senior Economist who is able to provide structure around complex business problems, hone those complex problems into specific, scientific questions, and test those questions to generate insights. The ideal candidate will work with various science, engineering, operations, and analytics teams to estimate models and algorithms on large scale data, design pilots and measure their impact, and transform successful prototypes into improved policies and programs at scale. They will lead teams of researchers to produce robust, objective research results and insights which can be communicated to a broad audience inside and outside of Amazon. Ideal candidates will work closely with business partners to develop science that solves the most important business challenges. They will work well in a team setting with individuals from diverse disciplines and backgrounds. They will serve as an ambassador for science and a scientific resource for business teams, so that scientific processes permeate throughout the HR organization to the benefit of Amazonians and Amazon. Ideal candidates will own the development of scientific models and manage the data analysis, modeling, and experimentation that is necessary for estimating and validating models. They will be customer-centric – clearly communicating scientific approaches and findings to business leaders, listening to and incorporate their feedback, and delivering successful scientific solutions. This position is for an individual contributor role, but a successful candidate could have the opportunity to take on 1-3 direct reports. Key job responsibilities Use structural economic modeling to evaluate the impact of policies on employee outcomes, and examine how external labor market and economic conditions impact Amazon's ability to hire and retain talent. A day in the life Work with teammates to apply economic methods to business problems. This might include identifying the appropriate research questions, writing code to estimate a structural model, or writing and presenting a document with findings to business leaders. Our economists also collaborate with partner teams throughout the process, from understanding their challenges, to developing a research agenda that will address those challenges, to help them implement solutions. About the team We are a multidisciplinary team that combines the talents of science and engineering to develop innovative solutions to make Amazon Earth's Best Employer.
Applied Scientist, Enterprise Engineering
US, WA, Seattle
Enterprise Engineering is seeking an exceptional Senior Applied Scientist to join our AppSense team, which is revolutionizing Software Asset Management at Amazon and beyond. As a key member of our applied science team, you will leverage cutting-edge machine learning, natural language processing, and data analytics techniques to solve complex challenges in software discovery, cost optimization, and intelligent decision-making. Your work will directly impact Amazon's ability to manage its vast software portfolio efficiently, driving significant cost savings and operational improvements. In this role, you will have the opportunity to invent and implement novel scientific approaches that address critical business problems at the product level. You will collaborate closely with product managers, engineers, and business stakeholders to translate scientific innovations into practical, scalable solutions that enhance AppSense's capabilities and deliver value to our customers. Key job responsibilities * Lead the design, implementation, and delivery of scientifically complex solutions for AppSense, focusing on areas such as automated software discovery, intelligent cost optimization, and predictive analytics * Develop and apply state-of-the-art machine learning models to improve software categorization, usage prediction, and anomaly detection * Create innovative natural language processing solutions for contract analysis, optimization, and automated report generation * Design and implement advanced recommendation systems for software stack optimization based on job roles and team compositions * Develop reinforcement learning algorithms for automated license management, including predictive maintenance to prevent unexpected expirations or overage charges * Develop AI-driven negotiation assistants and collaborative budgeting tools with ML-powered spend forecasting * Create sentiment analysis models to gauge software satisfaction from user feedback and support tickets About the team The AppSense team is at the forefront of transforming software asset management at Amazon. We're building a comprehensive platform that provides visibility, control, and optimization for Amazon's vast software portfolio. Our mission is to leverage cutting-edge technology to help businesses discover, manage, and optimize their software assets, driving significant cost savings and operational efficiencies. As part of the applied science team within AppSense, you'll work alongside talented scientists, engineers, and product managers who are passionate about solving complex problems at scale. We foster a culture of innovation, encouraging team members to push the boundaries of what's possible in software asset management. Your contributions will directly impact Amazon's bottom line and have the potential to shape the future of how organizations manage their software ecosystems.
View from space of a connected network around planet Earth representing the Internet of Things.
Have feedback?
Let us know by taking this short survey
Get started
Amazon.com | Conditions of Use | Privacy | © 1996-2024 Amazon.com, Inc. or its affiliates
Follow Us